Hi folks!
I've been working on a plugin to warn on unbounded uses of alloca() to
help find questionable uses in glibc and other libraries. It occurred
to me that the broader community could benefit from it, as it has found
quite a few interesting cases. So, I've reimplemented it as an actual
pass, lest it be lost in plugin la-la land and bit-rot.
Before I sink any more time cleaning it up, would this be something
acceptable into the compiler? It doesn't have anything glibc specific,
except possibly the following idiom which I allow:
if (gate_function (length))
alloca(length);
...and the above is probably common enough that we should handle it.
The testcase has a lot of examples of what the pass handles.
Thoughts?
Aldy
p.s. The pass currently warns on all uses of VLAs. I'm not completely
sold on this idea, so perhaps we could remove it, or gate it with a flag.
gcc/
* Makefile.in (OBJS): Add walloca.o.
* common.opt (Walloca): New.
(Walloca-strict): New.
(Walloca-max-size): New.
* passes.def: Add pass_walloca.
* tree-pass.h (make_pass_walloca): New.
* walloca.c: New pass.
gcc/c-family/
Add Walloca and Walloca-strict entries.
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 776f6d7..6964de1 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1537,6 +1537,7 @@ OBJS = \
varpool.o \
vmsdbgout.o \
vtable-verify.o \
+ walloca.o \
web.o \
wide-int.o \
wide-int-print.o \
diff --git a/gcc/c-family/c.opt b/gcc/c-family/c.opt
index 83fd84c..816f854 100644
--- a/gcc/c-family/c.opt
+++ b/gcc/c-family/c.opt
@@ -275,6 +275,14 @@ Wall
C ObjC C++ ObjC++ Warning
Enable most warning messages.
+Walloca
+LangEnabledBy(C ObjC C++ ObjC++,Wall)
+; in common.opt
+
+Walloca-strict
+LangEnabledBy(C ObjC C++ ObjC++)
+; in common.opt
+
Warray-bounds
LangEnabledBy(C ObjC C++ ObjC++,Wall)
; in common.opt
diff --git a/gcc/common.opt b/gcc/common.opt
index f0d7196..a4ed603 100644
--- a/gcc/common.opt
+++ b/gcc/common.opt
@@ -545,6 +545,18 @@ Waggressive-loop-optimizations
Common Var(warn_aggressive_loop_optimizations) Init(1) Warning
Warn if a loop with constant number of iterations triggers undefined behavior.
+Walloca
+Common Var(warn_alloca) Warning
+Warn on unbounded uses of alloca and all uses of variable-length arrays.
+
+Walloca-strict
+Common Var(warn_alloca_strict) Init(0) Warning
+Warn on all uses of alloca or variable-length arrays.
+
+Walloca-max-size=
+Common Joined RejectNegative UInteger Var(warn_alloca_max_size) Init(4000)
Warning
+Maximum size of alloca argument to allow without warning.
+
Warray-bounds
Common Var(warn_array_bounds) Warning
Warn if an array is accessed out of bounds.
diff --git a/gcc/passes.def b/gcc/passes.def
index 3647e90..4b503e8 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -303,6 +303,7 @@ along with GCC; see the file COPYING3. If not see
NEXT_PASS (pass_simduid_cleanup);
NEXT_PASS (pass_lower_vector_ssa);
NEXT_PASS (pass_cse_reciprocals);
+ NEXT_PASS (pass_walloca);
NEXT_PASS (pass_reassoc, false /* insert_powi_p */);
NEXT_PASS (pass_strength_reduction);
NEXT_PASS (pass_split_paths);
diff --git a/gcc/testsuite/gcc.dg/Walloca-1.c b/gcc/testsuite/gcc.dg/Walloca-1.c
new file mode 100644
index 0000000..23c5123
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/Walloca-1.c
@@ -0,0 +1,89 @@
+/* { dg-do compile } */
+/* { dg-options "-Walloca -O -Walloca-max-size=2000" } */
+
+#define alloca __builtin_alloca
+
+typedef unsigned long size_t;
+extern size_t strlen(const char *);
+
+extern void useit (char *);
+
+int num;
+
+void test_walloca (size_t len, size_t len2, size_t len3)
+{
+ int i;
+
+ for (i=0; i < 123; ++i)
+ {
+ char *s = alloca (566); /* { dg-warning "alloca within a loop" } */
+ useit (s);
+ }
+
+ char *s = alloca (123);
+ useit (s); // OK, constant argument to alloca
+
+ s = alloca (num); /* { dg-warning "unbounded use" } */
+ useit (s);
+
+ s = alloca(90000); /* { dg-warning "is too big" } */
+ useit (s);
+
+ if (len < 2000)
+ {
+ s = alloca(len); // OK, bounded
+ useit (s);
+ }
+
+ if (len + len2 < 2000) // OK, bounded
+ {
+ s = alloca(len + len2);
+ useit (s);
+ }
+
+ if (len3 <= 2001)
+ {
+ s = alloca(len3); /* { dg-warning "alloca is too big" } */
+ useit(s);
+ }
+}
+
+// Test __libc_use_alloca hack from glibc.
+extern int __libc_alloca_cutoff (size_t size) __attribute__ ((const));
+extern __inline __attribute__ ((__always_inline__))
+int
+__libc_use_alloca (size_t size)
+{
+ return (__builtin_expect (size <= 4000 / 4, 1)
+ || __builtin_expect (__libc_alloca_cutoff (size), 1));
+}
+
+void test_libc_use_alloca_from_glibc (const char *tocode)
+{
+ size_t len = strlen (tocode) + 3;
+ _Bool usealloca = __libc_use_alloca (len);
+ void *ptr;
+
+ if (usealloca)
+ ptr = __builtin_alloca (len); // OK, uses __libc_use_alloca.
+ else
+ ptr = __builtin_malloc (len);
+
+ useit(ptr);
+}
+
+void test_vlas (int num)
+{
+ char str2[num]; /* { dg-warning "unbounded use" } */
+ useit(str2);
+
+ num = 98;
+ for (int i=0; i < 1234; ++i) {
+ char str[num]; // OK, VLA in a loop, but it is a
+ // known size *AND* the compiler takes
+ // care of cleaning up between
+ // iterations with
+ // __builtin_stack_restore.
+ useit(str);
+ }
+}
diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index 36299a6..57b61f4 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -469,6 +469,7 @@ extern simple_ipa_opt_pass *make_pass_ipa_oacc
(gcc::context *ctxt);
extern simple_ipa_opt_pass *make_pass_ipa_oacc_kernels (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_gen_hsail (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_warn_nonnull_compare (gcc::context *ctxt);
+extern gimple_opt_pass *make_pass_walloca (gcc::context *ctxt);
/* IPA Passes */
extern simple_ipa_opt_pass *make_pass_ipa_lower_emutls (gcc::context *ctxt);
diff --git a/gcc/walloca.c b/gcc/walloca.c
new file mode 100644
index 0000000..531827c
--- /dev/null
+++ b/gcc/walloca.c
@@ -0,0 +1,266 @@
+/* Pass to warn on problematic uses of alloca and variable
+ length arrays.
+
+ Copyright (C) 2016 Free Software Foundation, Inc.
+ Contributed by Aldy Hernandez <al...@redhat.com>.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
+
+// Note: This pass needs range information (VRP) and will silently not
+// work without optimization.
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "backend.h"
+#include "tree.h"
+#include "gimple.h"
+#include "tree-pass.h"
+#include "ssa.h"
+#include "gimple-pretty-print.h"
+#include "diagnostic-core.h"
+#include "fold-const.h"
+#include "gimple-iterator.h"
+#include "tree-ssa.h"
+#include "params.h"
+#include "tree-cfg.h"
+#include "calls.h"
+#include "cfgloop.h"
+
+const pass_data pass_data_walloca = {
+ GIMPLE_PASS,
+ "walloca",
+ OPTGROUP_NONE,
+ TV_NONE,
+ PROP_cfg, // properties_required
+ 0, // properties_provided
+ 0, // properties_destroyed
+ 0, // properties_start
+ 0, // properties_finish
+};
+
+class pass_walloca : public gimple_opt_pass
+{
+public:
+ pass_walloca (gcc::context *ctxt)
+ : gimple_opt_pass(pass_data_walloca, ctxt)
+ {}
+ virtual bool gate (function *) { return warn_alloca || warn_alloca_strict; }
+ virtual unsigned int execute (function *);
+};
+
+// Possible warnings for unbounded alloca use.
+enum unbounded_warn_type {
+ // No warning. We're within bounds.
+ UNBOUNDED_OK,
+ // Warn: argument to alloca is too big.
+ UNBOUNDED_ARG_TOO_BIG,
+ // Warn: unbounded for any other reason.
+ UNBOUNDED_UNKNOWN
+};
+
+// We have a few heuristics up our sleeve to determine if a call to
+// alloca() is within bounds. Try them out and return TRUE if the
+// alloca call will be bounded.
+//
+// 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.
+//
+// Returns the type of warning to issue or UNBOUNDED_OK for no warning.
+
+static unbounded_warn_type
+bounded_arg_to_alloca_p (tree arg, edge e)
+{
+ // All the tests bellow depend on the jump being on the TRUE path.
+ if (!(e->flags & EDGE_TRUE_VALUE))
+ return UNBOUNDED_UNKNOWN;
+
+ basic_block bb = e->src;
+ gimple_stmt_iterator gsi = gsi_last_bb (bb);
+ gimple *last = gsi_stmt (gsi);
+ if (!last || gimple_code (last) != GIMPLE_COND)
+ return UNBOUNDED_UNKNOWN;
+
+ /* Check for:
+ if (ARG <= CONSTANT)
+ goto <bb 3>;
+ else
+ goto <bb 4>;
+ <bb 3>:
+ alloca(ARG);
+ */
+ if (gimple_cond_code (last) == LE_EXPR
+ && gimple_cond_lhs (last) == arg
+ && TREE_CODE (gimple_cond_rhs (last)) == INTEGER_CST)
+ return
+ tree_to_uhwi (gimple_cond_rhs (last)) > (unsigned) warn_alloca_max_size
+ ? UNBOUNDED_ARG_TOO_BIG : UNBOUNDED_OK;
+
+ /* Check for a common glibc idiom:
+ <bb 3>:
+ _52 = __libc_alloca_cutoff (ARG);
+ if (_52 != 0)
+ goto <bb 3>;
+ else
+ goto <bb 4>;
+ <bb 3>:
+ alloca(ARG);
+
+ In reality, we check for any function having an ARGument used in
+ the alloca call. */
+ // Check: if (_52 != 0)
+ if (gimple_cond_code (last) != NE_EXPR)
+ return UNBOUNDED_UNKNOWN;
+ tree lhs = gimple_cond_lhs (last);
+ tree rhs = gimple_cond_rhs (last);
+ if (TREE_CODE (lhs) != SSA_NAME || !integer_zerop (rhs))
+ return UNBOUNDED_UNKNOWN;
+ // Check: _52 = some_function (...,ARG,...);
+ gimple *def_stmt = SSA_NAME_DEF_STMT (lhs);
+ if (!is_gimple_call (def_stmt))
+ return UNBOUNDED_UNKNOWN;
+ tree fndecl = gimple_call_fndecl (def_stmt);
+ if (!fndecl)
+ return UNBOUNDED_UNKNOWN;
+ for (unsigned i = 0; i < gimple_call_num_args (def_stmt); ++i)
+ if (gimple_call_arg (def_stmt, i) == arg)
+ return UNBOUNDED_OK;
+ return UNBOUNDED_UNKNOWN;
+}
+
+// Given an alloca call in STMT, return UNBOUNDED_OK if the argument
+// to alloca is known to have a bound, otherwise return the type of
+// warning to issue.
+
+static unbounded_warn_type
+bounded_alloca_p (gimple *stmt)
+{
+ gcc_assert (gimple_alloca_call_p (stmt));
+ tree len = gimple_call_arg (stmt, 0);
+
+ // Check for the obviously bounded case.
+ if (TREE_CODE (len) == INTEGER_CST)
+ return tree_to_uhwi (len) > (unsigned) warn_alloca_max_size
+ ? UNBOUNDED_ARG_TOO_BIG : UNBOUNDED_OK;
+
+ if (TREE_CODE (len) != SSA_NAME)
+ return UNBOUNDED_UNKNOWN;
+
+ // Check range info if available.
+ wide_int min, max;
+ enum value_range_type range_type = get_range_info (len, &min, &max);
+ if (range_type == VR_RANGE
+ && wi::fits_uhwi_p (max)
+ && max.to_uhwi () <= (unsigned) warn_alloca_max_size)
+ return UNBOUNDED_OK;
+
+ // Even if we have range info, it may be wrong. So we have a few
+ // heuristics for things we can easily determine. Check these misc
+ // cases and accept them, but only if all predecessors are known to
+ // have a known bound.
+ basic_block bb = gimple_bb (stmt);
+ for (unsigned ix = 0; ix < EDGE_COUNT (bb->preds); ix++)
+ {
+ unbounded_warn_type w
+ = bounded_arg_to_alloca_p (len, EDGE_PRED (bb, ix));
+ if (w != UNBOUNDED_OK)
+ return w;
+ }
+ return UNBOUNDED_OK;
+}
+
+// Return OPT_Walloca_strict if -Walloca-strict was passed, otherwise
+// return OPT_Walloca.
+
+static enum opt_code
+OPT_Wcode (void)
+{
+ return warn_alloca_strict ? OPT_Walloca_strict : OPT_Walloca;
+}
+
+unsigned int
+pass_walloca::execute (function *fun)
+{
+ basic_block bb;
+ FOR_EACH_BB_FN (bb, fun)
+ {
+ for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si);
+ gsi_next (&si))
+ {
+ gimple *stmt = gsi_stmt (si);
+ location_t loc = gimple_location (stmt);
+
+ if (!gimple_alloca_call_p (stmt)
+ || gimple_call_num_args (stmt) < 1) // Just in case.
+ continue;
+
+ // Interestingly, GCC emits two types of __builtin_alloca's,
+ // the traditional __builtin_alloca and a
+ // __builtin_alloca_with_align. The latter gets generated
+ // for VLA's, which means we can kill two birds with one
+ // code. There is no need to handle VLA's separately.
+
+ unbounded_warn_type w = bounded_alloca_p (stmt);
+ tree fndecl = gimple_call_fn (stmt);
+ if (w != UNBOUNDED_OK)
+ {
+ if (w == UNBOUNDED_UNKNOWN)
+ warning_at (loc, OPT_Wcode (), "unbounded use of alloca");
+ else if (w == UNBOUNDED_ARG_TOO_BIG)
+ warning_at (loc, OPT_Wcode (),
+ "possible argument to alloca is too big");
+ else
+ gcc_unreachable ();
+ continue;
+ }
+
+ if (!bb->loop_father
+ // ?? Functions with no loops get a loop_father? I
+ // don't get it. The following conditional seems to do
+ // the trick to exclude such nonsense.
+ || bb->loop_father->header == ENTRY_BLOCK_PTR_FOR_FN (fun))
+ goto strict_warning;
+
+ // Do not warn on VLAs occurring in a loop, since VLAs are
+ // guaranteed to be cleaned up when they go out of scope.
+ // That is, there is a corresponding __builtin_stack_restore
+ // at the end of the scope in which the VLA occurs.
+ while (TREE_CODE (fndecl) == ADDR_EXPR)
+ fndecl = TREE_OPERAND (fndecl, 0);
+ if (DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
+ && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_ALLOCA_WITH_ALIGN)
+ goto strict_warning;
+
+ warning_at (loc, OPT_Wcode (), "use of alloca within a loop");
+ continue;
+
+ strict_warning:
+ if (warn_alloca_strict)
+ warning_at (loc, OPT_Walloca_strict,
+ "use of alloca with -Walloca-strict");
+ }
+ }
+ return 0;
+}
+
+gimple_opt_pass *
+make_pass_walloca (gcc::context *ctxt)
+{
+ return new pass_walloca (ctxt);
+}
