[patch] convert -Walloca pass to ranger
Aldy Hernandez
aldyh@redhat.com
Mon Oct 5 09:51:00 GMT 2020
The walloca pass is a mess. It has all sorts of heuristics to divine
problematic ranges fed into alloca, none of them very good, and all of
them unreadable. The mess therein was actually one of the original
motivators for the ranger project (along with array bounds checking).
The attached patch is a conversion of the pass to ranger. It's mostly
an exercise in removing code. The entire pass almost reduces to:
+ // If the user specified a limit, use it.
+ int_range_max r;
+ if (warn_limit_specified_p (is_vla)
+ && TREE_CODE (len) == SSA_NAME
+ && query.range_of_expr (r, len, stmt)
+ && !r.varying_p ())
+ {
+ // The invalid bits are anything outside of [0, MAX_SIZE].
+ static int_range<2> invalid_range (build_int_cst (size_type_node, 0),
+ build_int_cst (size_type_node,
+ max_size),
+ VR_ANTI_RANGE);
+
+ r.intersect (invalid_range);
+ if (r.undefined_p ())
+ return alloca_type_and_limit (ALLOCA_OK);
+
+ return alloca_type_and_limit (ALLOCA_BOUND_MAYBE_LARGE,
+ wi::to_wide (integer_zero_node));
}
That is, if the range of the integer passed to alloca is outside of
[0,MAX_SIZE], warn, otherwise it's ok. Plain and simple.
You will notice I removed the nuanced errors we gave before-- like
trying to guess whether the problematic range came by virtue of a signed
cast conversion. These specific errors were never part of the original
design, they were just stuff we could guess by how the IL looked. It
was non-exact and fragile. Now we just say the alloca argument may be
too large, period.
It the future, I would even like to remove the specific range the ranger
was able to compute from the error message itself. As will become
obvious, the ranger can get pretty outrageous ranges that are entirely
non-obvious by looking at the code. Peppering the error messages with
these ranges will ultimately just confuse the user. But alas, that's a
problem for another patch to solve.
This patch goes on top of the ranger which Andrew just posted. It's
likely to be adjusted as the ranger is committed.
gcc/ChangeLog:
* gimple-ssa-warn-alloca.c (enum alloca_type): Remove
ALLOCA_BOUND_UNKNOWN and ALLOCA_CAST_FROM_SIGNED.
(warn_limit_specified_p): New.
(alloca_call_type_by_arg): Remove.
(cast_from_signed_p): Remove.
(is_max): Remove.
(alloca_call_type): Remove heuristics and replace with call
into
ranger.
(pass_walloca::execute): Instantiate ranger.
gcc/testsuite/ChangeLog:
* gcc.dg/Walloca-1.c: Adjust for ranger.
* gcc.dg/Walloca-12.c: Same.
* gcc.dg/Walloca-13.c: Same.
* gcc.dg/Walloca-2.c: Same.
* gcc.dg/Walloca-3.c: Same.
* gcc.dg/Walloca-6.c: Same.
diff --git a/gcc/gimple-ssa-warn-alloca.c b/gcc/gimple-ssa-warn-alloca.c
index 9e80e5dbbd9..33824a7a091 100644
--- a/gcc/gimple-ssa-warn-alloca.c
+++ b/gcc/gimple-ssa-warn-alloca.c
@@ -36,6 +36,7 @@ along with GCC; see the file COPYING3. If not see
#include "calls.h"
#include "cfgloop.h"
#include "intl.h"
+#include "gimple-range.h"
static unsigned HOST_WIDE_INT adjusted_warn_limit (bool);
@@ -99,12 +100,6 @@ enum alloca_type {
// Alloca argument may be too large.
ALLOCA_BOUND_MAYBE_LARGE,
- // Alloca argument is bounded but of an indeterminate size.
- ALLOCA_BOUND_UNKNOWN,
-
- // Alloca argument was casted from a signed integer.
- ALLOCA_CAST_FROM_SIGNED,
-
// Alloca appears in a loop.
ALLOCA_IN_LOOP,
@@ -135,6 +130,15 @@ public:
}
};
+/* Return TRUE if the user specified a limit for either VLAs or
ALLOCAs. */
+
+static bool
+warn_limit_specified_p (bool is_vla)
+{
+ unsigned HOST_WIDE_INT max = is_vla ? warn_vla_limit : warn_alloca_limit;
+ return max != HOST_WIDE_INT_MAX;
+}
+
/* Return the value of the argument N to -Walloca-larger-than= or
-Wvla-larger-than= adjusted for the target data model so that
when N == HOST_WIDE_INT_MAX, the adjusted value is set to
@@ -158,183 +162,15 @@ adjusted_warn_limit (bool idx)
return limits[idx];
}
-
-// NOTE: When we get better range info, this entire function becomes
-// irrelevant, as it should be possible to get range info for an SSA
-// name at any point in the program.
-//
-// We have a few heuristics up our sleeve to determine if a call to
-// alloca() is within bounds. Try them out and return the type of
-// alloca call with its assumed limit (if applicable).
-//
-// Given a known argument (ARG) to alloca() and an EDGE (E)
-// calculating said argument, verify that the last statement in the BB
-// in E->SRC is a gate comparing ARG to an acceptable bound for
-// alloca(). See examples below.
-//
-// If set, ARG_CASTED is the possible unsigned argument to which ARG
-// was casted to. This is to handle cases where the controlling
-// predicate is looking at a casted value, not the argument itself.
-// arg_casted = (size_t) arg;
-// if (arg_casted < N)
-// goto bb3;
-// else
-// goto bb5;
-//
-// MAX_SIZE is WARN_ALLOCA= adjusted for VLAs. It is the maximum size
-// in bytes we allow for arg.
-
-static class alloca_type_and_limit
-alloca_call_type_by_arg (tree arg, tree arg_casted, edge e,
- unsigned HOST_WIDE_INT max_size)
-{
- basic_block bb = e->src;
- gimple_stmt_iterator gsi = gsi_last_bb (bb);
- gimple *last = gsi_stmt (gsi);
-
- const offset_int maxobjsize = tree_to_shwi (max_object_size ());
-
- /* When MAX_SIZE is greater than or equal to PTRDIFF_MAX treat
- allocations that aren't visibly constrained as OK, otherwise
- report them as (potentially) unbounded. */
- alloca_type unbounded_result = (max_size < maxobjsize.to_uhwi ()
- ? ALLOCA_UNBOUNDED : ALLOCA_OK);
-
- if (!last || gimple_code (last) != GIMPLE_COND)
- {
- return alloca_type_and_limit (unbounded_result);
- }
-
- enum tree_code cond_code = gimple_cond_code (last);
- if (e->flags & EDGE_TRUE_VALUE)
- ;
- else if (e->flags & EDGE_FALSE_VALUE)
- cond_code = invert_tree_comparison (cond_code, false);
- else
- return alloca_type_and_limit (unbounded_result);
-
- // Check for:
- // if (ARG .COND. N)
- // goto <bb 3>;
- // else
- // goto <bb 4>;
- // <bb 3>:
- // alloca(ARG);
- if ((cond_code == LE_EXPR
- || cond_code == LT_EXPR
- || cond_code == GT_EXPR
- || cond_code == GE_EXPR)
- && (gimple_cond_lhs (last) == arg
- || gimple_cond_lhs (last) == arg_casted))
- {
- if (TREE_CODE (gimple_cond_rhs (last)) == INTEGER_CST)
- {
- tree rhs = gimple_cond_rhs (last);
- int tst = wi::cmpu (wi::to_widest (rhs), max_size);
- if ((cond_code == LT_EXPR && tst == -1)
- || (cond_code == LE_EXPR && (tst == -1 || tst == 0)))
- return alloca_type_and_limit (ALLOCA_OK);
- else
- {
- // Let's not get too specific as to how large the limit
- // may be. Someone's clearly an idiot when things
- // degrade into "if (N > Y) alloca(N)".
- if (cond_code == GT_EXPR || cond_code == GE_EXPR)
- rhs = integer_zero_node;
- return alloca_type_and_limit (ALLOCA_BOUND_MAYBE_LARGE,
- wi::to_wide (rhs));
- }
- }
- else
- {
- /* Analogous to ALLOCA_UNBOUNDED, when MAX_SIZE is greater
- than or equal to PTRDIFF_MAX, treat allocations with
- an unknown bound as OK. */
- alloca_type unknown_result
- = (max_size < maxobjsize.to_uhwi ()
- ? ALLOCA_BOUND_UNKNOWN : ALLOCA_OK);
- return alloca_type_and_limit (unknown_result);
- }
- }
-
- // Similarly, but check for a comparison with an unknown LIMIT.
- // if (LIMIT .COND. ARG)
- // alloca(arg);
- //
- // Where LIMIT has a bound of unknown range.
- //
- // Note: All conditions of the form (ARG .COND. XXXX) where covered
- // by the previous check above, so we only need to look for (LIMIT
- // .COND. ARG) here.
- tree limit = gimple_cond_lhs (last);
- if ((gimple_cond_rhs (last) == arg
- || gimple_cond_rhs (last) == arg_casted)
- && TREE_CODE (limit) == SSA_NAME)
- {
- wide_int min, max;
- value_range_kind range_type = get_range_info (limit, &min, &max);
-
- if (range_type == VR_UNDEFINED || range_type == VR_VARYING)
- return alloca_type_and_limit (ALLOCA_BOUND_UNKNOWN);
-
- // ?? It looks like the above `if' is unnecessary, as we never
- // get any VR_RANGE or VR_ANTI_RANGE here. If we had a range
- // for LIMIT, I suppose we would have taken care of it in
- // alloca_call_type(), or handled above where we handle (ARG
.COND. N).
- //
- // If this ever triggers, we should probably figure out why and
- // handle it, though it is likely to be just an ALLOCA_UNBOUNDED.
- return alloca_type_and_limit (unbounded_result);
- }
-
- return alloca_type_and_limit (unbounded_result);
-}
-
-// Return TRUE if SSA's definition is a cast from a signed type.
-// If so, set *INVALID_CASTED_TYPE to the signed type.
-
-static bool
-cast_from_signed_p (tree ssa, tree *invalid_casted_type)
-{
- gimple *def = SSA_NAME_DEF_STMT (ssa);
- if (def
- && !gimple_nop_p (def)
- && gimple_assign_cast_p (def)
- && !TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (def))))
- {
- *invalid_casted_type = TREE_TYPE (gimple_assign_rhs1 (def));
- return true;
- }
- return false;
-}
-
-// Return TRUE if X has a maximum range of MAX, basically covering the
-// entire domain, in which case it's no range at all.
-
-static bool
-is_max (tree x, wide_int max)
-{
- return wi::max_value (TREE_TYPE (x)) == max;
-}
-
// Analyze the alloca call in STMT and return the alloca type with its
// corresponding limit (if applicable). IS_VLA is set if the alloca
// call was created by the gimplifier for a VLA.
-//
-// If the alloca call may be too large because of a cast from a signed
-// type to an unsigned type, set *INVALID_CASTED_TYPE to the
-// problematic signed type.
static class alloca_type_and_limit
-alloca_call_type (gimple *stmt, bool is_vla, tree *invalid_casted_type)
+alloca_call_type (range_query &query, gimple *stmt, bool is_vla)
{
gcc_assert (gimple_alloca_call_p (stmt));
- bool tentative_cast_from_signed = false;
tree len = gimple_call_arg (stmt, 0);
- tree len_casted = NULL;
- wide_int min, max;
- edge_iterator ei;
- edge e;
gcc_assert (!is_vla || warn_vla_limit >= 0);
gcc_assert (is_vla || warn_alloca_limit >= 0);
@@ -361,118 +197,9 @@ alloca_call_type (gimple *stmt, bool is_vla, tree
*invalid_casted_type)
return alloca_type_and_limit (ALLOCA_OK);
}
- // Check the range info if available.
- if (TREE_CODE (len) == SSA_NAME)
- {
- value_range_kind range_type = get_range_info (len, &min, &max);
- if (range_type == VR_RANGE)
- {
- if (wi::leu_p (max, max_size))
- return alloca_type_and_limit (ALLOCA_OK);
- else
- {
- // A cast may have created a range we don't care
- // about. For instance, a cast from 16-bit to
- // 32-bit creates a range of 0..65535, even if there
- // is not really a determinable range in the
- // underlying code. In this case, look through the
- // cast at the original argument, and fall through
- // to look at other alternatives.
- //
- // We only look at through the cast when its from
- // unsigned to unsigned, otherwise we may risk
- // looking at SIGNED_INT < N, which is clearly not
- // what we want. In this case, we'd be interested
- // in a VR_RANGE of [0..N].
- //
- // Note: None of this is perfect, and should all go
- // away with better range information. But it gets
- // most of the cases.
- gimple *def = SSA_NAME_DEF_STMT (len);
- if (gimple_assign_cast_p (def))
- {
- tree rhs1 = gimple_assign_rhs1 (def);
- tree rhs1type = TREE_TYPE (rhs1);
-
- // Bail if the argument type is not valid.
- if (!INTEGRAL_TYPE_P (rhs1type))
- return alloca_type_and_limit (ALLOCA_OK);
-
- if (TYPE_UNSIGNED (rhs1type))
- {
- len_casted = rhs1;
- range_type = get_range_info (len_casted, &min, &max);
- }
- }
- // An unknown range or a range of the entire domain is
- // really no range at all.
- if (range_type == VR_VARYING
- || (!len_casted && is_max (len, max))
- || (len_casted && is_max (len_casted, max)))
- {
- // Fall through.
- }
- else if (range_type == VR_ANTI_RANGE)
- return alloca_type_and_limit (ALLOCA_UNBOUNDED);
-
- if (range_type != VR_VARYING)
- {
- const offset_int maxobjsize
- = wi::to_offset (max_object_size ());
- alloca_type result = (max_size < maxobjsize
- ? ALLOCA_BOUND_MAYBE_LARGE : ALLOCA_OK);
- return alloca_type_and_limit (result, max);
- }
- }
- }
- else if (range_type == VR_ANTI_RANGE)
- {
- // There may be some wrapping around going on. Catch it
- // with this heuristic. Hopefully, this VR_ANTI_RANGE
- // nonsense will go away, and we won't have to catch the
- // sign conversion problems with this crap.
- //
- // This is here to catch things like:
- // void foo(signed int n) {
- // if (n < 100)
- // alloca(n);
- // ...
- // }
- if (cast_from_signed_p (len, invalid_casted_type))
- {
- // Unfortunately this also triggers:
- //
- // __SIZE_TYPE__ n = (__SIZE_TYPE__)blah;
- // if (n < 100)
- // alloca(n);
- //
- // ...which is clearly bounded. So, double check that
- // the paths leading up to the size definitely don't
- // have a bound.
- tentative_cast_from_signed = true;
- }
- }
- // No easily determined range and try other things.
- }
-
- // If we couldn't find anything, try a few heuristics for things we
- // can easily determine. Check these misc cases but only accept
- // them if all predecessors have a known bound.
- class alloca_type_and_limit ret = alloca_type_and_limit (ALLOCA_OK);
- FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->preds)
- {
- gcc_assert (!len_casted || TYPE_UNSIGNED (TREE_TYPE (len_casted)));
- ret = alloca_call_type_by_arg (len, len_casted, e, max_size);
- if (ret.type != ALLOCA_OK)
- break;
- }
-
- if (ret.type != ALLOCA_OK && tentative_cast_from_signed)
- ret = alloca_type_and_limit (ALLOCA_CAST_FROM_SIGNED);
-
+ struct alloca_type_and_limit ret = alloca_type_and_limit (ALLOCA_OK);
// If we have a declared maximum size, we can take it into account.
- if (ret.type != ALLOCA_OK
- && gimple_call_builtin_p (stmt, BUILT_IN_ALLOCA_WITH_ALIGN_AND_MAX))
+ if (gimple_call_builtin_p (stmt, BUILT_IN_ALLOCA_WITH_ALIGN_AND_MAX))
{
tree arg = gimple_call_arg (stmt, 2);
if (compare_tree_int (arg, max_size) <= 0)
@@ -485,9 +212,37 @@ alloca_call_type (gimple *stmt, bool is_vla, tree
*invalid_casted_type)
? ALLOCA_BOUND_MAYBE_LARGE : ALLOCA_OK);
ret = alloca_type_and_limit (result, wi::to_wide (arg));
}
+ return ret;
+ }
+
+ // If the user specified a limit, use it.
+ int_range_max r;
+ if (warn_limit_specified_p (is_vla)
+ && TREE_CODE (len) == SSA_NAME
+ && query.range_of_expr (r, len, stmt)
+ && !r.varying_p ())
+ {
+ // The invalid bits are anything outside of [0, MAX_SIZE].
+ static int_range<2> invalid_range (build_int_cst (size_type_node, 0),
+ build_int_cst (size_type_node,
+ max_size),
+ VR_ANTI_RANGE);
+
+ r.intersect (invalid_range);
+ if (r.undefined_p ())
+ return alloca_type_and_limit (ALLOCA_OK);
+
+ return alloca_type_and_limit (ALLOCA_BOUND_MAYBE_LARGE,
+ wi::to_wide (integer_zero_node));
}
- return ret;
+ const offset_int maxobjsize = tree_to_shwi (max_object_size ());
+ /* When MAX_SIZE is greater than or equal to PTRDIFF_MAX treat
+ allocations that aren't visibly constrained as OK, otherwise
+ report them as (potentially) unbounded. */
+ alloca_type unbounded_result = (max_size < maxobjsize.to_uhwi ()
+ ? ALLOCA_UNBOUNDED : ALLOCA_OK);
+ return alloca_type_and_limit (unbounded_result);
}
// Return TRUE if STMT is in a loop, otherwise return FALSE.
@@ -503,6 +258,7 @@ in_loop_p (gimple *stmt)
unsigned int
pass_walloca::execute (function *fun)
{
+ gimple_ranger ranger;
basic_block bb;
FOR_EACH_BB_FN (bb, fun)
{
@@ -535,9 +291,8 @@ pass_walloca::execute (function *fun)
else if (warn_alloca_limit < 0)
continue;
- tree invalid_casted_type = NULL;
class alloca_type_and_limit t
- = alloca_call_type (stmt, is_vla, &invalid_casted_type);
+ = alloca_call_type (ranger, stmt, is_vla);
unsigned HOST_WIDE_INT adjusted_alloca_limit
= adjusted_warn_limit (false);
@@ -599,13 +354,6 @@ pass_walloca::execute (function *fun)
}
}
break;
- case ALLOCA_BOUND_UNKNOWN:
- warning_at (loc, wcode,
- (is_vla
- ? G_("%Gvariable-length array bound is unknown")
- : G_("%G%<alloca%> bound is unknown")),
- stmt);
- break;
case ALLOCA_UNBOUNDED:
warning_at (loc, wcode,
(is_vla
@@ -618,17 +366,6 @@ pass_walloca::execute (function *fun)
warning_at (loc, wcode,
"%Guse of %<alloca%> within a loop", stmt);
break;
- case ALLOCA_CAST_FROM_SIGNED:
- gcc_assert (invalid_casted_type != NULL_TREE);
- warning_at (loc, wcode,
- (is_vla
- ? G_("%Gargument to variable-length array "
- "may be too large due to "
- "conversion from %qT to %qT")
- : G_("%Gargument to %<alloca%> may be too large "
- "due to conversion from %qT to %qT")),
- stmt, invalid_casted_type, size_type_node);
- break;
case ALLOCA_ARG_IS_ZERO:
warning_at (loc, wcode,
(is_vla
diff --git a/gcc/testsuite/gcc.dg/Walloca-1.c
b/gcc/testsuite/gcc.dg/Walloca-1.c
index 85e9160e845..ed1fa929398 100644
--- a/gcc/testsuite/gcc.dg/Walloca-1.c
+++ b/gcc/testsuite/gcc.dg/Walloca-1.c
@@ -24,8 +24,7 @@ void foo1 (size_t len, size_t len2, size_t len3)
char *s = alloca (123);
useit (s); // OK, constant argument to alloca
- s = alloca (num); // { dg-warning "large due to conversion" "" {
target lp64 } }
- // { dg-warning "unbounded use of 'alloca'" "" { target { ! lp64 } }
.-1 }
+ s = alloca (num); // { dg-warning "may be too large" }
useit (s);
s = alloca (30000); /* { dg-warning "is too large" } */
diff --git a/gcc/testsuite/gcc.dg/Walloca-12.c
b/gcc/testsuite/gcc.dg/Walloca-12.c
index 059c5f32129..d2d9413ab1e 100644
--- a/gcc/testsuite/gcc.dg/Walloca-12.c
+++ b/gcc/testsuite/gcc.dg/Walloca-12.c
@@ -8,5 +8,5 @@ void g (unsigned int n)
{
if (n == 7)
n = 11;
- f (__builtin_alloca (n)); /* { dg-warning "unbounded use of 'alloca'"
} */
+ f (__builtin_alloca (n)); /* { dg-warning "may be too large" } */
}
diff --git a/gcc/testsuite/gcc.dg/Walloca-13.c
b/gcc/testsuite/gcc.dg/Walloca-13.c
index 12e9f6c9281..99d62065e26 100644
--- a/gcc/testsuite/gcc.dg/Walloca-13.c
+++ b/gcc/testsuite/gcc.dg/Walloca-13.c
@@ -8,5 +8,5 @@ void g (int *p, int *q)
{
__SIZE_TYPE__ n = (__SIZE_TYPE__)(p - q);
if (n < 100)
- f (__builtin_alloca (n)); // { dg-bogus "may be too large due to
conversion" "" { xfail { *-*-* } } }
+ f (__builtin_alloca (n)); // { dg-bogus "may be too large" "" {
xfail { *-*-* } } }
}
diff --git a/gcc/testsuite/gcc.dg/Walloca-2.c
b/gcc/testsuite/gcc.dg/Walloca-2.c
index 766ff8d8af3..1cf9165c59f 100644
--- a/gcc/testsuite/gcc.dg/Walloca-2.c
+++ b/gcc/testsuite/gcc.dg/Walloca-2.c
@@ -24,7 +24,7 @@ g2 (int n)
{
void *p;
if (n < 2000)
- p = __builtin_alloca (n); // { dg-warning "large due to conversion" }
+ p = __builtin_alloca (n); // { dg-warning "may be too large" }
else
p = __builtin_malloc (n);
f (p);
@@ -36,9 +36,7 @@ g3 (int n)
void *p;
if (n > 0 && n < 3000)
{
- p = __builtin_alloca (n); // { dg-warning "'alloca' may be too
large" "" { target lp64} }
- // { dg-message "note:.*argument may be as large as 2999" "note"
{ target lp64 } .-1 }
- // { dg-warning "unbounded use of 'alloca'" "" { target { ! lp64
} } .-2 }
+ p = __builtin_alloca (n); // { dg-warning "may be too large" }
}
else
p = __builtin_malloc (n);
diff --git a/gcc/testsuite/gcc.dg/Walloca-3.c
b/gcc/testsuite/gcc.dg/Walloca-3.c
index f5840673da0..b8000ff1249 100644
--- a/gcc/testsuite/gcc.dg/Walloca-3.c
+++ b/gcc/testsuite/gcc.dg/Walloca-3.c
@@ -13,7 +13,7 @@ g1 (__SIZE_TYPE__ n)
{
void *p;
if (n < LIMIT)
- p = __builtin_alloca (n); // { dg-warning "'alloca' bound is unknown" }
+ p = __builtin_alloca (n); // { dg-warning "may be too large" }
else
p = __builtin_malloc (n);
f (p);
@@ -27,7 +27,7 @@ g2 (unsigned short n)
{
void *p;
if (n < SHORT_LIMIT)
- p = __builtin_alloca (n); // { dg-warning "'alloca' bound is unknown" }
+ p = __builtin_alloca (n); // { dg-warning "may be too large" }
else
p = __builtin_malloc (n);
f (p);
diff --git a/gcc/testsuite/gcc.dg/Walloca-6.c
b/gcc/testsuite/gcc.dg/Walloca-6.c
index 16b5d6f729d..ebe08aec838 100644
--- a/gcc/testsuite/gcc.dg/Walloca-6.c
+++ b/gcc/testsuite/gcc.dg/Walloca-6.c
@@ -1,7 +1,6 @@
/* { dg-do compile } */
/* { dg-require-effective-target alloca } */
/* { dg-options "-Walloca-larger-than=256 -O2" } */
-/* { dg-xfail-if "Currently broken but Andrew's work should fix this" {
*-*-* } } */
void f (void*);
void g (__SIZE_TYPE__ n)
More information about the Gcc-patches
mailing list