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 } 551