contrib/gcc-8.0/gcc/gimple-ssa-warn-alloca.c

   1 /* Warn on problematic uses of alloca and variable length arrays.
   2    Copyright (C) 2016-2018 Free Software Foundation, Inc.
   3    Contributed by Aldy Hernandez <aldyh@redhat.com>.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 3, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "backend.h"
  25 #include "tree.h"
  26 #include "gimple.h"
  27 #include "tree-pass.h"
  28 #include "ssa.h"
  29 #include "gimple-pretty-print.h"
  30 #include "diagnostic-core.h"
  31 #include "fold-const.h"
  32 #include "gimple-iterator.h"
  33 #include "tree-ssa.h"
  34 #include "params.h"
  35 #include "tree-cfg.h"
  36 #include "calls.h"
  37 #include "cfgloop.h"
  38 #include "intl.h"
  39
  40 const pass_data pass_data_walloca = {
  41   GIMPLE_PASS,
  42   "walloca",
  43   OPTGROUP_NONE,
  44   TV_NONE,
  45   PROP_cfg, // properties_required
  46   0,        // properties_provided
  47   0,        // properties_destroyed
  48   0,        // properties_start
  49   0,        // properties_finish
  50 };
  51
  52 class pass_walloca : public gimple_opt_pass
  53 {
  54 public:
  55   pass_walloca (gcc::context *ctxt)
  56     : gimple_opt_pass(pass_data_walloca, ctxt), first_time_p (false)
  57   {}
  58   opt_pass *clone () { return new pass_walloca (m_ctxt); }
  59   void set_pass_param (unsigned int n, bool param)
  60     {
  61       gcc_assert (n == 0);
  62       first_time_p = param;
  63     }
  64   virtual bool gate (function *);
  65   virtual unsigned int execute (function *);
  66
  67  private:
  68   // Set to TRUE the first time we run this pass on a function.
  69   bool first_time_p;
  70 };
  71
  72 bool
  73 pass_walloca::gate (function *fun ATTRIBUTE_UNUSED)
  74 {
  75   // The first time this pass is called, it is called before
  76   // optimizations have been run and range information is unavailable,
  77   // so we can only perform strict alloca checking.
  78   if (first_time_p)
  79     return warn_alloca != 0;
  80
  81   return ((unsigned HOST_WIDE_INT) warn_alloca_limit > 0
  82           || (unsigned HOST_WIDE_INT) warn_vla_limit > 0);
  83 }
  84
  85 // Possible problematic uses of alloca.
  86 enum alloca_type {
  87   // Alloca argument is within known bounds that are appropriate.
  88   ALLOCA_OK,
  89
  90   // Alloca argument is KNOWN to have a value that is too large.
  91   ALLOCA_BOUND_DEFINITELY_LARGE,
  92
  93   // Alloca argument may be too large.
  94   ALLOCA_BOUND_MAYBE_LARGE,
  95
  96   // Alloca argument is bounded but of an indeterminate size.
  97   ALLOCA_BOUND_UNKNOWN,
  98
  99   // Alloca argument was casted from a signed integer.
 100   ALLOCA_CAST_FROM_SIGNED,
 101
 102   // Alloca appears in a loop.
 103   ALLOCA_IN_LOOP,
 104
 105   // Alloca argument is 0.
 106   ALLOCA_ARG_IS_ZERO,
 107
 108   // Alloca call is unbounded.  That is, there is no controlling
 109   // predicate for its argument.
 110   ALLOCA_UNBOUNDED
 111 };
 112
 113 // Type of an alloca call with its corresponding limit, if applicable.
 114 struct alloca_type_and_limit {
 115   enum alloca_type type;
 116   // For ALLOCA_BOUND_MAYBE_LARGE and ALLOCA_BOUND_DEFINITELY_LARGE
 117   // types, this field indicates the assumed limit if known or
 118   // integer_zero_node if unknown.  For any other alloca types, this
 119   // field is undefined.
 120   wide_int limit;
 121   alloca_type_and_limit ();
 122   alloca_type_and_limit (enum alloca_type type,
 123                          wide_int i) : type(type), limit(i) { }
 124   alloca_type_and_limit (enum alloca_type type) : type(type) { }
 125 };
 126
 127 // NOTE: When we get better range info, this entire function becomes
 128 // irrelevant, as it should be possible to get range info for an SSA
 129 // name at any point in the program.
 130 //
 131 // We have a few heuristics up our sleeve to determine if a call to
 132 // alloca() is within bounds.  Try them out and return the type of
 133 // alloca call with its assumed limit (if applicable).
 134 //
 135 // Given a known argument (ARG) to alloca() and an EDGE (E)
 136 // calculating said argument, verify that the last statement in the BB
 137 // in E->SRC is a gate comparing ARG to an acceptable bound for
 138 // alloca().  See examples below.
 139 //
 140 // If set, ARG_CASTED is the possible unsigned argument to which ARG
 141 // was casted to.  This is to handle cases where the controlling
 142 // predicate is looking at a casted value, not the argument itself.
 143 //    arg_casted = (size_t) arg;
 144 //    if (arg_casted < N)
 145 //      goto bb3;
 146 //    else
 147 //      goto bb5;
 148 //
 149 // MAX_SIZE is WARN_ALLOCA= adjusted for VLAs.  It is the maximum size
 150 // in bytes we allow for arg.
 151
 152 static struct alloca_type_and_limit
 153 alloca_call_type_by_arg (tree arg, tree arg_casted, edge e, unsigned max_size)
 154 {
 155   basic_block bb = e->src;
 156   gimple_stmt_iterator gsi = gsi_last_bb (bb);
 157   gimple *last = gsi_stmt (gsi);
 158   if (!last || gimple_code (last) != GIMPLE_COND)
 159     return alloca_type_and_limit (ALLOCA_UNBOUNDED);
 160
 161   enum tree_code cond_code = gimple_cond_code (last);
 162   if (e->flags & EDGE_TRUE_VALUE)
 163     ;
 164   else if (e->flags & EDGE_FALSE_VALUE)
 165     cond_code = invert_tree_comparison (cond_code, false);
 166   else
 167     return alloca_type_and_limit (ALLOCA_UNBOUNDED);
 168
 169   // Check for:
 170   //   if (ARG .COND. N)
 171   //     goto <bb 3>;
 172   //   else
 173   //     goto <bb 4>;
 174   //   <bb 3>:
 175   //   alloca(ARG);
 176   if ((cond_code == LE_EXPR
 177        || cond_code == LT_EXPR
 178        || cond_code == GT_EXPR
 179        || cond_code == GE_EXPR)
 180       && (gimple_cond_lhs (last) == arg
 181           || gimple_cond_lhs (last) == arg_casted))
 182     {
 183       if (TREE_CODE (gimple_cond_rhs (last)) == INTEGER_CST)
 184         {
 185           tree rhs = gimple_cond_rhs (last);
 186           int tst = wi::cmpu (wi::to_widest (rhs), max_size);
 187           if ((cond_code == LT_EXPR && tst == -1)
 188               || (cond_code == LE_EXPR && (tst == -1 || tst == 0)))
 189             return alloca_type_and_limit (ALLOCA_OK);
 190           else
 191             {
 192               // Let's not get too specific as to how large the limit
 193               // may be.  Someone's clearly an idiot when things
 194               // degrade into "if (N > Y) alloca(N)".
 195               if (cond_code == GT_EXPR || cond_code == GE_EXPR)
 196                 rhs = integer_zero_node;
 197               return alloca_type_and_limit (ALLOCA_BOUND_MAYBE_LARGE,
 198                                             wi::to_wide (rhs));
 199             }
 200         }
 201       else
 202         return alloca_type_and_limit (ALLOCA_BOUND_UNKNOWN);
 203     }
 204
 205   // Similarly, but check for a comparison with an unknown LIMIT.
 206   //   if (LIMIT .COND. ARG)
 207   //     alloca(arg);
 208   //
 209   //   Where LIMIT has a bound of unknown range.
 210   //
 211   // Note: All conditions of the form (ARG .COND. XXXX) where covered
 212   // by the previous check above, so we only need to look for (LIMIT
 213   // .COND. ARG) here.
 214   tree limit = gimple_cond_lhs (last);
 215   if ((gimple_cond_rhs (last) == arg
 216        || gimple_cond_rhs (last) == arg_casted)
 217       && TREE_CODE (limit) == SSA_NAME)
 218     {
 219       wide_int min, max;
 220       value_range_type range_type = get_range_info (limit, &min, &max);
 221
 222       if (range_type == VR_UNDEFINED || range_type == VR_VARYING)
 223         return alloca_type_and_limit (ALLOCA_BOUND_UNKNOWN);
 224
 225       // ?? It looks like the above `if' is unnecessary, as we never
 226       // get any VR_RANGE or VR_ANTI_RANGE here.  If we had a range
 227       // for LIMIT, I suppose we would have taken care of it in
 228       // alloca_call_type(), or handled above where we handle (ARG .COND. N).
 229       //
 230       // If this ever triggers, we should probably figure out why and
 231       // handle it, though it is likely to be just an ALLOCA_UNBOUNDED.
 232       return alloca_type_and_limit (ALLOCA_UNBOUNDED);
 233     }
 234
 235   return alloca_type_and_limit (ALLOCA_UNBOUNDED);
 236 }
 237
 238 // Return TRUE if SSA's definition is a cast from a signed type.
 239 // If so, set *INVALID_CASTED_TYPE to the signed type.
 240
 241 static bool
 242 cast_from_signed_p (tree ssa, tree *invalid_casted_type)
 243 {
 244   gimple *def = SSA_NAME_DEF_STMT (ssa);
 245   if (def
 246       && !gimple_nop_p (def)
 247       && gimple_assign_cast_p (def)
 248       && !TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (def))))
 249     {
 250       *invalid_casted_type = TREE_TYPE (gimple_assign_rhs1 (def));
 251       return true;
 252     }
 253   return false;
 254 }
 255
 256 // Return TRUE if X has a maximum range of MAX, basically covering the
 257 // entire domain, in which case it's no range at all.
 258
 259 static bool
 260 is_max (tree x, wide_int max)
 261 {
 262   return wi::max_value (TREE_TYPE (x)) == max;
 263 }
 264
 265 // Analyze the alloca call in STMT and return the alloca type with its
 266 // corresponding limit (if applicable).  IS_VLA is set if the alloca
 267 // call was created by the gimplifier for a VLA.
 268 //
 269 // If the alloca call may be too large because of a cast from a signed
 270 // type to an unsigned type, set *INVALID_CASTED_TYPE to the
 271 // problematic signed type.
 272
 273 static struct alloca_type_and_limit
 274 alloca_call_type (gimple *stmt, bool is_vla, tree *invalid_casted_type)
 275 {
 276   gcc_assert (gimple_alloca_call_p (stmt));
 277   bool tentative_cast_from_signed = false;
 278   tree len = gimple_call_arg (stmt, 0);
 279   tree len_casted = NULL;
 280   wide_int min, max;
 281   edge_iterator ei;
 282   edge e;
 283
 284   gcc_assert (!is_vla || (unsigned HOST_WIDE_INT) warn_vla_limit > 0);
 285   gcc_assert (is_vla || (unsigned HOST_WIDE_INT) warn_alloca_limit > 0);
 286
 287   // Adjust warn_alloca_max_size for VLAs, by taking the underlying
 288   // type into account.
 289   unsigned HOST_WIDE_INT max_size;
 290   if (is_vla)
 291     max_size = (unsigned HOST_WIDE_INT) warn_vla_limit;
 292   else
 293     max_size = (unsigned HOST_WIDE_INT) warn_alloca_limit;
 294
 295   // Check for the obviously bounded case.
 296   if (TREE_CODE (len) == INTEGER_CST)
 297     {
 298       if (tree_to_uhwi (len) > max_size)
 299         return alloca_type_and_limit (ALLOCA_BOUND_DEFINITELY_LARGE,
 300                                       wi::to_wide (len));
 301       if (integer_zerop (len))
 302         return alloca_type_and_limit (ALLOCA_ARG_IS_ZERO);
 303
 304       return alloca_type_and_limit (ALLOCA_OK);
 305     }
 306
 307   // Check the range info if available.
 308   if (TREE_CODE (len) == SSA_NAME)
 309     {
 310       value_range_type range_type = get_range_info (len, &min, &max);
 311       if (range_type == VR_RANGE)
 312         {
 313           if (wi::leu_p (max, max_size))
 314             return alloca_type_and_limit (ALLOCA_OK);
 315           else
 316             {
 317               // A cast may have created a range we don't care
 318               // about.  For instance, a cast from 16-bit to
 319               // 32-bit creates a range of 0..65535, even if there
 320               // is not really a determinable range in the
 321               // underlying code.  In this case, look through the
 322               // cast at the original argument, and fall through
 323               // to look at other alternatives.
 324               //
 325               // We only look at through the cast when its from
 326               // unsigned to unsigned, otherwise we may risk
 327               // looking at SIGNED_INT < N, which is clearly not
 328               // what we want.  In this case, we'd be interested
 329               // in a VR_RANGE of [0..N].
 330               //
 331               // Note: None of this is perfect, and should all go
 332               // away with better range information.  But it gets
 333               // most of the cases.
 334               gimple *def = SSA_NAME_DEF_STMT (len);
 335               if (gimple_assign_cast_p (def))
 336                 {
 337                   tree rhs1 = gimple_assign_rhs1 (def);
 338                   tree rhs1type = TREE_TYPE (rhs1);
 339
 340                   // Bail if the argument type is not valid.
 341                   if (!INTEGRAL_TYPE_P (rhs1type))
 342                     return alloca_type_and_limit (ALLOCA_OK);
 343
 344                   if (TYPE_UNSIGNED (rhs1type))
 345                     {
 346                       len_casted = rhs1;
 347                       range_type = get_range_info (len_casted, &min, &max);
 348                     }
 349                 }
 350               // An unknown range or a range of the entire domain is
 351               // really no range at all.
 352               if (range_type == VR_VARYING
 353                   || (!len_casted && is_max (len, max))
 354                   || (len_casted && is_max (len_casted, max)))
 355                 {
 356                   // Fall through.
 357                 }
 358               else if (range_type == VR_ANTI_RANGE)
 359                 return alloca_type_and_limit (ALLOCA_UNBOUNDED);
 360               else if (range_type != VR_VARYING)
 361                 return alloca_type_and_limit (ALLOCA_BOUND_MAYBE_LARGE, max);
 362             }
 363         }
 364       else if (range_type == VR_ANTI_RANGE)
 365         {
 366           // There may be some wrapping around going on.  Catch it
 367           // with this heuristic.  Hopefully, this VR_ANTI_RANGE
 368           // nonsense will go away, and we won't have to catch the
 369           // sign conversion problems with this crap.
 370           //
 371           // This is here to catch things like:
 372           // void foo(signed int n) {
 373           //   if (n < 100)
 374           //     alloca(n);
 375           //   ...
 376           // }
 377           if (cast_from_signed_p (len, invalid_casted_type))
 378             {
 379               // Unfortunately this also triggers:
 380               //
 381               // __SIZE_TYPE__ n = (__SIZE_TYPE__)blah;
 382               // if (n < 100)
 383               //   alloca(n);
 384               //
 385               // ...which is clearly bounded.  So, double check that
 386               // the paths leading up to the size definitely don't
 387               // have a bound.
 388               tentative_cast_from_signed = true;
 389             }
 390         }
 391       // No easily determined range and try other things.
 392     }
 393
 394   // If we couldn't find anything, try a few heuristics for things we
 395   // can easily determine.  Check these misc cases but only accept
 396   // them if all predecessors have a known bound.
 397   struct alloca_type_and_limit ret = alloca_type_and_limit (ALLOCA_OK);
 398   FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->preds)
 399     {
 400       gcc_assert (!len_casted || TYPE_UNSIGNED (TREE_TYPE (len_casted)));
 401       ret = alloca_call_type_by_arg (len, len_casted, e, max_size);
 402       if (ret.type != ALLOCA_OK)
 403         break;
 404     }
 405
 406   if (ret.type != ALLOCA_OK && tentative_cast_from_signed)
 407     ret = alloca_type_and_limit (ALLOCA_CAST_FROM_SIGNED);
 408
 409   // If we have a declared maximum size, we can take it into account.
 410   if (ret.type != ALLOCA_OK
 411       && gimple_call_builtin_p (stmt, BUILT_IN_ALLOCA_WITH_ALIGN_AND_MAX))
 412     {
 413       tree arg = gimple_call_arg (stmt, 2);
 414       if (compare_tree_int (arg, max_size) <= 0)
 415         ret = alloca_type_and_limit (ALLOCA_OK);
 416       else
 417         ret = alloca_type_and_limit (ALLOCA_BOUND_MAYBE_LARGE,
 418                                      wi::to_wide (arg));
 419     }
 420
 421   return ret;
 422 }
 423
 424 // Return TRUE if STMT is in a loop, otherwise return FALSE.
 425
 426 static bool
 427 in_loop_p (gimple *stmt)
 428 {
 429   basic_block bb = gimple_bb (stmt);
 430   return
 431     bb->loop_father && bb->loop_father->header != ENTRY_BLOCK_PTR_FOR_FN (cfun);
 432 }
 433
 434 unsigned int
 435 pass_walloca::execute (function *fun)
 436 {
 437   basic_block bb;
 438   FOR_EACH_BB_FN (bb, fun)
 439     {
 440       for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si);
 441            gsi_next (&si))
 442         {
 443           gimple *stmt = gsi_stmt (si);
 444           location_t loc = gimple_location (stmt);
 445
 446           if (!gimple_alloca_call_p (stmt))
 447             continue;
 448
 449           const bool is_vla
 450             = gimple_call_alloca_for_var_p (as_a <gcall *> (stmt));
 451
 452           // Strict mode whining for VLAs is handled by the front-end,
 453           // so we can safely ignore this case.  Also, ignore VLAs if
 454           // the user doesn't care about them.
 455           if (is_vla
 456               && (warn_vla > 0 || !warn_vla_limit))
 457             continue;
 458
 459           if (!is_vla && (warn_alloca || !warn_alloca_limit))
 460             {
 461               if (warn_alloca)
 462                 warning_at (loc, OPT_Walloca, G_("use of %<alloca%>"));
 463               continue;
 464             }
 465
 466           tree invalid_casted_type = NULL;
 467           struct alloca_type_and_limit t
 468             = alloca_call_type (stmt, is_vla, &invalid_casted_type);
 469
 470           // Even if we think the alloca call is OK, make sure it's not in a
 471           // loop, except for a VLA, since VLAs are guaranteed to be cleaned
 472           // up when they go out of scope, including in a loop.
 473           if (t.type == ALLOCA_OK && !is_vla && in_loop_p (stmt))
 474             t = alloca_type_and_limit (ALLOCA_IN_LOOP);
 475
 476           enum opt_code wcode
 477             = is_vla ? OPT_Wvla_larger_than_ : OPT_Walloca_larger_than_;
 478           char buff[WIDE_INT_MAX_PRECISION / 4 + 4];
 479           switch (t.type)
 480             {
 481             case ALLOCA_OK:
 482               break;
 483             case ALLOCA_BOUND_MAYBE_LARGE:
 484               if (warning_at (loc, wcode,
 485                               is_vla ? G_("argument to variable-length array "
 486                                           "may be too large")
 487                               : G_("argument to %<alloca%> may be too large"))
 488                   && t.limit != 0)
 489                 {
 490                   print_decu (t.limit, buff);
 491                   inform (loc, G_("limit is %u bytes, but argument "
 492                                   "may be as large as %s"),
 493                           is_vla ? warn_vla_limit : warn_alloca_limit, buff);
 494                 }
 495               break;
 496             case ALLOCA_BOUND_DEFINITELY_LARGE:
 497               if (warning_at (loc, wcode,
 498                               is_vla ? G_("argument to variable-length array "
 499                                           "is too large")
 500                               : G_("argument to %<alloca%> is too large"))
 501                   && t.limit != 0)
 502                 {
 503                   print_decu (t.limit, buff);
 504                   inform (loc, G_("limit is %u bytes, but argument is %s"),
 505                           is_vla ? warn_vla_limit : warn_alloca_limit, buff);
 506                 }
 507               break;
 508             case ALLOCA_BOUND_UNKNOWN:
 509               warning_at (loc, wcode,
 510                           is_vla ? G_("variable-length array bound is unknown")
 511                           : G_("%<alloca%> bound is unknown"));
 512               break;
 513             case ALLOCA_UNBOUNDED:
 514               warning_at (loc, wcode,
 515                           is_vla ? G_("unbounded use of variable-length array")
 516                           : G_("unbounded use of %<alloca%>"));
 517               break;
 518             case ALLOCA_IN_LOOP:
 519               gcc_assert (!is_vla);
 520               warning_at (loc, wcode, G_("use of %<alloca%> within a loop"));
 521               break;
 522             case ALLOCA_CAST_FROM_SIGNED:
 523               gcc_assert (invalid_casted_type != NULL_TREE);
 524               warning_at (loc, wcode,
 525                           is_vla ? G_("argument to variable-length array "
 526                                       "may be too large due to "
 527                                       "conversion from %qT to %qT")
 528                           : G_("argument to %<alloca%> may be too large "
 529                                "due to conversion from %qT to %qT"),
 530                           invalid_casted_type, size_type_node);
 531               break;
 532             case ALLOCA_ARG_IS_ZERO:
 533               warning_at (loc, wcode,
 534                           is_vla ? G_("argument to variable-length array "
 535                                       "is zero")
 536                           : G_("argument to %<alloca%> is zero"));
 537               break;
 538             default:
 539               gcc_unreachable ();
 540             }
 541         }
 542     }
 543   return 0;
 544 }
 545
 546 gimple_opt_pass *
 547 make_pass_walloca (gcc::context *ctxt)
 548 {
 549   return new pass_walloca (ctxt);
 550 }