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