1/* Pointer Bounds Checker optimization pass. 2 Copyright (C) 2014-2015 Free Software Foundation, Inc. 3 Contributed by Ilya Enkovich (ilya.enkovich@intel.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 "hash-set.h" 25#include "machmode.h" 26#include "vec.h" 27#include "double-int.h" 28#include "input.h" 29#include "alias.h" 30#include "symtab.h" 31#include "options.h" 32#include "wide-int.h" 33#include "inchash.h" 34#include "tree.h" 35#include "fold-const.h" 36#include "target.h" 37#include "tree-cfg.h" 38#include "tree-pass.h" 39#include "is-a.h" 40#include "cfgloop.h" 41#include "stringpool.h" 42#include "tree-ssa-alias.h" 43#include "tree-ssanames.h" 44#include "tree-ssa-operands.h" 45#include "tree-ssa-address.h" 46#include "tree-ssa.h" 47#include "predict.h" 48#include "dominance.h" 49#include "cfg.h" 50#include "basic-block.h" 51#include "tree-ssa-loop-niter.h" 52#include "gimple-expr.h" 53#include "gimple.h" 54#include "tree-phinodes.h" 55#include "gimple-ssa.h" 56#include "ssa-iterators.h" 57#include "gimple-pretty-print.h" 58#include "gimple-iterator.h" 59#include "gimplify.h" 60#include "gimplify-me.h" 61#include "hashtab.h" 62#include "tm.h" 63#include "hard-reg-set.h" 64#include "function.h" 65#include "rtl.h" 66#include "flags.h" 67#include "statistics.h" 68#include "real.h" 69#include "fixed-value.h" 70#include "insn-config.h" 71#include "expmed.h" 72#include "dojump.h" 73#include "explow.h" 74#include "calls.h" 75#include "emit-rtl.h" 76#include "varasm.h" 77#include "stmt.h" 78#include "expr.h" 79#include "tree-chkp.h" 80#include "ipa-chkp.h" 81#include "diagnostic.h" 82 83enum check_type 84{ 85 CHECK_LOWER_BOUND, 86 CHECK_UPPER_BOUND 87}; 88 89struct pol_item 90{ 91 tree cst; 92 tree var; 93}; 94 95struct address_t 96{ 97 vec<struct pol_item> pol; 98}; 99 100/* Structure to hold check informtation. */ 101struct check_info 102{ 103 /* Type of the check. */ 104 check_type type; 105 /* Address used for the check. */ 106 address_t addr; 107 /* Bounds used for the check. */ 108 tree bounds; 109 /* Check statement. Can be NULL for removed checks. */ 110 gimple stmt; 111}; 112 113/* Structure to hold checks information for BB. */ 114struct bb_checks 115{ 116 vec<struct check_info, va_heap, vl_ptr> checks; 117}; 118 119static void chkp_collect_value (tree ssa_name, address_t &res); 120 121#define chkp_bndmk_fndecl \ 122 (targetm.builtin_chkp_function (BUILT_IN_CHKP_BNDMK)) 123#define chkp_intersect_fndecl \ 124 (targetm.builtin_chkp_function (BUILT_IN_CHKP_INTERSECT)) 125#define chkp_checkl_fndecl \ 126 (targetm.builtin_chkp_function (BUILT_IN_CHKP_BNDCL)) 127#define chkp_checku_fndecl \ 128 (targetm.builtin_chkp_function (BUILT_IN_CHKP_BNDCU)) 129 130static vec<struct bb_checks, va_heap, vl_ptr> check_infos = vNULL; 131 132/* Comparator for pol_item structures I1 and I2 to be used 133 to find items with equal var. Also used for polynomial 134 sorting. */ 135static int 136chkp_pol_item_compare (const void *i1, const void *i2) 137{ 138 const struct pol_item *p1 = (const struct pol_item *)i1; 139 const struct pol_item *p2 = (const struct pol_item *)i2; 140 141 if (p1->var == p2->var) 142 return 0; 143 else if (p1->var > p2->var) 144 return 1; 145 else 146 return -1; 147} 148 149/* Find polynomial item in ADDR with var equal to VAR 150 and return its index. Return -1 if item was not 151 found. */ 152static int 153chkp_pol_find (address_t &addr, tree var) 154{ 155 int left = 0; 156 int right = addr.pol.length () - 1; 157 int n; 158 159 while (right >= left) 160 { 161 n = (left + right) / 2; 162 163 if (addr.pol[n].var == var 164 || (var && addr.pol[n].var 165 && TREE_CODE (var) == ADDR_EXPR 166 && TREE_CODE (addr.pol[n].var) == ADDR_EXPR 167 && TREE_OPERAND (var, 0) == TREE_OPERAND (addr.pol[n].var, 0))) 168 return n; 169 else if (addr.pol[n].var > var) 170 right = n - 1; 171 else 172 left = n + 1; 173 } 174 175 return -1; 176} 177 178/* Return constant CST extended to size type. */ 179static tree 180chkp_extend_const (tree cst) 181{ 182 if (TYPE_PRECISION (TREE_TYPE (cst)) < TYPE_PRECISION (size_type_node)) 183 return build_int_cst_type (size_type_node, tree_to_shwi (cst)); 184 185 return cst; 186} 187 188/* Add polynomial item CST * VAR to ADDR. */ 189static void 190chkp_add_addr_item (address_t &addr, tree cst, tree var) 191{ 192 int n = chkp_pol_find (addr, var); 193 194 cst = chkp_extend_const (cst); 195 196 if (n < 0) 197 { 198 struct pol_item item; 199 item.cst = cst; 200 item.var = var; 201 202 addr.pol.safe_push (item); 203 addr.pol.qsort (&chkp_pol_item_compare); 204 } 205 else 206 { 207 addr.pol[n].cst = fold_build2 (PLUS_EXPR, TREE_TYPE (addr.pol[n].cst), 208 addr.pol[n].cst, cst); 209 if (TREE_CODE (addr.pol[n].cst) == INTEGER_CST 210 && integer_zerop (addr.pol[n].cst)) 211 addr.pol.ordered_remove (n); 212 } 213} 214 215/* Subtract polynomial item CST * VAR from ADDR. */ 216static void 217chkp_sub_addr_item (address_t &addr, tree cst, tree var) 218{ 219 int n = chkp_pol_find (addr, var); 220 221 cst = chkp_extend_const (cst); 222 223 if (n < 0) 224 { 225 struct pol_item item; 226 item.cst = fold_build2 (MINUS_EXPR, TREE_TYPE (cst), 227 integer_zero_node, cst); 228 item.var = var; 229 230 addr.pol.safe_push (item); 231 addr.pol.qsort (&chkp_pol_item_compare); 232 } 233 else 234 { 235 addr.pol[n].cst = fold_build2 (MINUS_EXPR, TREE_TYPE (addr.pol[n].cst), 236 addr.pol[n].cst, cst); 237 if (TREE_CODE (addr.pol[n].cst) == INTEGER_CST 238 && integer_zerop (addr.pol[n].cst)) 239 addr.pol.ordered_remove (n); 240 } 241} 242 243/* Add address DELTA to ADDR. */ 244static void 245chkp_add_addr_addr (address_t &addr, address_t &delta) 246{ 247 unsigned int i; 248 for (i = 0; i < delta.pol.length (); i++) 249 chkp_add_addr_item (addr, delta.pol[i].cst, delta.pol[i].var); 250} 251 252/* Subtract address DELTA from ADDR. */ 253static void 254chkp_sub_addr_addr (address_t &addr, address_t &delta) 255{ 256 unsigned int i; 257 for (i = 0; i < delta.pol.length (); i++) 258 chkp_sub_addr_item (addr, delta.pol[i].cst, delta.pol[i].var); 259} 260 261/* Mutiply address ADDR by integer constant MULT. */ 262static void 263chkp_mult_addr (address_t &addr, tree mult) 264{ 265 unsigned int i; 266 for (i = 0; i < addr.pol.length (); i++) 267 addr.pol[i].cst = fold_build2 (MULT_EXPR, TREE_TYPE (addr.pol[i].cst), 268 addr.pol[i].cst, mult); 269} 270 271/* Return 1 if we may prove ADDR has a constant value with 272 determined sign, which is put into *SIGN. Otherwise 273 return 0. */ 274static bool 275chkp_is_constant_addr (const address_t &addr, int *sign) 276{ 277 *sign = 0; 278 279 if (addr.pol.length () == 0) 280 return true; 281 else if (addr.pol.length () > 1) 282 return false; 283 else if (addr.pol[0].var) 284 return false; 285 else if (integer_zerop (addr.pol[0].cst)) 286 *sign = 0; 287 else if (tree_int_cst_sign_bit (addr.pol[0].cst)) 288 *sign = -1; 289 else 290 *sign = 1; 291 292 return true; 293} 294 295/* Dump ADDR into dump_file. */ 296static void 297chkp_print_addr (const address_t &addr) 298{ 299 unsigned int n = 0; 300 for (n = 0; n < addr.pol.length (); n++) 301 { 302 if (n > 0) 303 fprintf (dump_file, " + "); 304 305 if (addr.pol[n].var == NULL_TREE) 306 print_generic_expr (dump_file, addr.pol[n].cst, 0); 307 else 308 { 309 if (TREE_CODE (addr.pol[n].cst) != INTEGER_CST 310 || !integer_onep (addr.pol[n].cst)) 311 { 312 print_generic_expr (dump_file, addr.pol[n].cst, 0); 313 fprintf (dump_file, " * "); 314 } 315 print_generic_expr (dump_file, addr.pol[n].var, 0); 316 } 317 } 318} 319 320/* Compute value of PTR and put it into address RES. 321 PTR has to be ADDR_EXPR. */ 322static void 323chkp_collect_addr_value (tree ptr, address_t &res) 324{ 325 tree obj = TREE_OPERAND (ptr, 0); 326 address_t addr; 327 328 switch (TREE_CODE (obj)) 329 { 330 case INDIRECT_REF: 331 chkp_collect_value (TREE_OPERAND (obj, 0), res); 332 break; 333 334 case MEM_REF: 335 chkp_collect_value (TREE_OPERAND (obj, 0), res); 336 addr.pol.create (0); 337 chkp_collect_value (TREE_OPERAND (obj, 1), addr); 338 chkp_add_addr_addr (res, addr); 339 addr.pol.release (); 340 break; 341 342 case ARRAY_REF: 343 chkp_collect_value (build_fold_addr_expr (TREE_OPERAND (obj, 0)), res); 344 addr.pol.create (0); 345 chkp_collect_value (TREE_OPERAND (obj, 1), addr); 346 chkp_mult_addr (addr, array_ref_element_size (obj)); 347 chkp_add_addr_addr (res, addr); 348 addr.pol.release (); 349 break; 350 351 case COMPONENT_REF: 352 { 353 tree str = TREE_OPERAND (obj, 0); 354 tree field = TREE_OPERAND (obj, 1); 355 chkp_collect_value (build_fold_addr_expr (str), res); 356 addr.pol.create (0); 357 chkp_collect_value (component_ref_field_offset (obj), addr); 358 chkp_add_addr_addr (res, addr); 359 addr.pol.release (); 360 if (DECL_FIELD_BIT_OFFSET (field)) 361 { 362 addr.pol.create (0); 363 chkp_collect_value (fold_build2 (TRUNC_DIV_EXPR, size_type_node, 364 DECL_FIELD_BIT_OFFSET (field), 365 size_int (BITS_PER_UNIT)), 366 addr); 367 chkp_add_addr_addr (res, addr); 368 addr.pol.release (); 369 } 370 } 371 break; 372 373 default: 374 chkp_add_addr_item (res, integer_one_node, ptr); 375 break; 376 } 377} 378 379/* Compute value of PTR and put it into address RES. */ 380static void 381chkp_collect_value (tree ptr, address_t &res) 382{ 383 gimple def_stmt; 384 enum gimple_code code; 385 enum tree_code rhs_code; 386 address_t addr; 387 tree rhs1; 388 389 if (TREE_CODE (ptr) == INTEGER_CST) 390 { 391 chkp_add_addr_item (res, ptr, NULL); 392 return; 393 } 394 else if (TREE_CODE (ptr) == ADDR_EXPR) 395 { 396 chkp_collect_addr_value (ptr, res); 397 return; 398 } 399 else if (TREE_CODE (ptr) != SSA_NAME) 400 { 401 chkp_add_addr_item (res, integer_one_node, ptr); 402 return; 403 } 404 405 /* Now we handle the case when polynomial is computed 406 for SSA NAME. */ 407 def_stmt = SSA_NAME_DEF_STMT (ptr); 408 code = gimple_code (def_stmt); 409 410 /* Currently we do not walk through statements other 411 than assignment. */ 412 if (code != GIMPLE_ASSIGN) 413 { 414 chkp_add_addr_item (res, integer_one_node, ptr); 415 return; 416 } 417 418 rhs_code = gimple_assign_rhs_code (def_stmt); 419 rhs1 = gimple_assign_rhs1 (def_stmt); 420 421 switch (rhs_code) 422 { 423 case SSA_NAME: 424 case INTEGER_CST: 425 case ADDR_EXPR: 426 chkp_collect_value (rhs1, res); 427 break; 428 429 case PLUS_EXPR: 430 case POINTER_PLUS_EXPR: 431 chkp_collect_value (rhs1, res); 432 addr.pol.create (0); 433 chkp_collect_value (gimple_assign_rhs2 (def_stmt), addr); 434 chkp_add_addr_addr (res, addr); 435 addr.pol.release (); 436 break; 437 438 case MINUS_EXPR: 439 chkp_collect_value (rhs1, res); 440 addr.pol.create (0); 441 chkp_collect_value (gimple_assign_rhs2 (def_stmt), addr); 442 chkp_sub_addr_addr (res, addr); 443 addr.pol.release (); 444 break; 445 446 case MULT_EXPR: 447 if (TREE_CODE (rhs1) == SSA_NAME 448 && TREE_CODE (gimple_assign_rhs2 (def_stmt)) == INTEGER_CST) 449 { 450 chkp_collect_value (rhs1, res); 451 chkp_mult_addr (res, gimple_assign_rhs2 (def_stmt)); 452 } 453 else if (TREE_CODE (gimple_assign_rhs2 (def_stmt)) == SSA_NAME 454 && TREE_CODE (rhs1) == INTEGER_CST) 455 { 456 chkp_collect_value (gimple_assign_rhs2 (def_stmt), res); 457 chkp_mult_addr (res, rhs1); 458 } 459 else 460 chkp_add_addr_item (res, integer_one_node, ptr); 461 break; 462 463 default: 464 chkp_add_addr_item (res, integer_one_node, ptr); 465 break; 466 } 467} 468 469/* Fill check_info structure *CI with information about 470 check STMT. */ 471static void 472chkp_fill_check_info (gimple stmt, struct check_info *ci) 473{ 474 ci->addr.pol.create (0); 475 ci->bounds = gimple_call_arg (stmt, 1); 476 chkp_collect_value (gimple_call_arg (stmt, 0), ci->addr); 477 ci->type = (gimple_call_fndecl (stmt) == chkp_checkl_fndecl 478 ? CHECK_LOWER_BOUND 479 : CHECK_UPPER_BOUND); 480 ci->stmt = stmt; 481} 482 483/* Release structures holding check information 484 for current function. */ 485static void 486chkp_release_check_info (void) 487{ 488 unsigned int n, m; 489 490 if (check_infos.exists ()) 491 { 492 for (n = 0; n < check_infos.length (); n++) 493 { 494 for (m = 0; m < check_infos[n].checks.length (); m++) 495 if (check_infos[n].checks[m].addr.pol.exists ()) 496 check_infos[n].checks[m].addr.pol.release (); 497 check_infos[n].checks.release (); 498 } 499 check_infos.release (); 500 } 501} 502 503/* Create structures to hold check information 504 for current function. */ 505static void 506chkp_init_check_info (void) 507{ 508 struct bb_checks empty_bbc; 509 int n; 510 511 empty_bbc.checks = vNULL; 512 513 chkp_release_check_info (); 514 515 check_infos.create (last_basic_block_for_fn (cfun)); 516 for (n = 0; n < last_basic_block_for_fn (cfun); n++) 517 { 518 check_infos.safe_push (empty_bbc); 519 check_infos.last ().checks.create (0); 520 } 521} 522 523/* Find all checks in current function and store info about them 524 in check_infos. */ 525static void 526chkp_gather_checks_info (void) 527{ 528 basic_block bb; 529 gimple_stmt_iterator i; 530 531 if (dump_file && (dump_flags & TDF_DETAILS)) 532 fprintf (dump_file, "Gathering information about checks...\n"); 533 534 chkp_init_check_info (); 535 536 FOR_EACH_BB_FN (bb, cfun) 537 { 538 struct bb_checks *bbc = &check_infos[bb->index]; 539 540 if (dump_file && (dump_flags & TDF_DETAILS)) 541 fprintf (dump_file, "Searching checks in BB%d...\n", bb->index); 542 543 for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i)) 544 { 545 gimple stmt = gsi_stmt (i); 546 547 if (gimple_code (stmt) != GIMPLE_CALL) 548 continue; 549 550 if (gimple_call_fndecl (stmt) == chkp_checkl_fndecl 551 || gimple_call_fndecl (stmt) == chkp_checku_fndecl) 552 { 553 struct check_info ci; 554 555 chkp_fill_check_info (stmt, &ci); 556 bbc->checks.safe_push (ci); 557 558 if (dump_file && (dump_flags & TDF_DETAILS)) 559 { 560 fprintf (dump_file, "Adding check information:\n"); 561 fprintf (dump_file, " bounds: "); 562 print_generic_expr (dump_file, ci.bounds, 0); 563 fprintf (dump_file, "\n address: "); 564 chkp_print_addr (ci.addr); 565 fprintf (dump_file, "\n check: "); 566 print_gimple_stmt (dump_file, stmt, 0, 0); 567 } 568 } 569 } 570 } 571} 572 573/* Return 1 if check CI against BOUNDS always pass, 574 -1 if check CI against BOUNDS always fails and 575 0 if we cannot compute check result. */ 576static int 577chkp_get_check_result (struct check_info *ci, tree bounds) 578{ 579 gimple bnd_def; 580 address_t bound_val; 581 int sign, res = 0; 582 583 if (dump_file && (dump_flags & TDF_DETAILS)) 584 { 585 fprintf (dump_file, "Trying to compute result of the check\n"); 586 fprintf (dump_file, " check: "); 587 print_gimple_stmt (dump_file, ci->stmt, 0, 0); 588 fprintf (dump_file, " address: "); 589 chkp_print_addr (ci->addr); 590 fprintf (dump_file, "\n bounds: "); 591 print_generic_expr (dump_file, bounds, 0); 592 fprintf (dump_file, "\n"); 593 } 594 595 if (TREE_CODE (bounds) != SSA_NAME) 596 { 597 if (dump_file && (dump_flags & TDF_DETAILS)) 598 fprintf (dump_file, " result: bounds tree code is not ssa_name\n"); 599 return 0; 600 } 601 602 bnd_def = SSA_NAME_DEF_STMT (bounds); 603 /* Currently we handle cases when bounds are result of bndmk 604 or loaded static bounds var. */ 605 if (gimple_code (bnd_def) == GIMPLE_CALL 606 && gimple_call_fndecl (bnd_def) == chkp_bndmk_fndecl) 607 { 608 bound_val.pol.create (0); 609 chkp_collect_value (gimple_call_arg (bnd_def, 0), bound_val); 610 if (ci->type == CHECK_UPPER_BOUND) 611 { 612 address_t size_val; 613 size_val.pol.create (0); 614 chkp_collect_value (gimple_call_arg (bnd_def, 1), size_val); 615 chkp_add_addr_addr (bound_val, size_val); 616 size_val.pol.release (); 617 chkp_add_addr_item (bound_val, integer_minus_one_node, NULL); 618 } 619 } 620 else if (gimple_code (bnd_def) == GIMPLE_ASSIGN 621 && gimple_assign_rhs1 (bnd_def) == chkp_get_zero_bounds_var ()) 622 { 623 if (dump_file && (dump_flags & TDF_DETAILS)) 624 fprintf (dump_file, " result: always pass with zero bounds\n"); 625 return 1; 626 } 627 else if (gimple_code (bnd_def) == GIMPLE_ASSIGN 628 && gimple_assign_rhs1 (bnd_def) == chkp_get_none_bounds_var ()) 629 { 630 if (dump_file && (dump_flags & TDF_DETAILS)) 631 fprintf (dump_file, " result: always fails with none bounds\n"); 632 return -1; 633 } 634 else if (gimple_code (bnd_def) == GIMPLE_ASSIGN 635 && TREE_CODE (gimple_assign_rhs1 (bnd_def)) == VAR_DECL) 636 { 637 tree bnd_var = gimple_assign_rhs1 (bnd_def); 638 tree var; 639 tree size; 640 641 if (!DECL_INITIAL (bnd_var) 642 || DECL_INITIAL (bnd_var) == error_mark_node) 643 { 644 if (dump_file && (dump_flags & TDF_DETAILS)) 645 fprintf (dump_file, " result: cannot compute bounds\n"); 646 return 0; 647 } 648 649 gcc_assert (TREE_CODE (DECL_INITIAL (bnd_var)) == ADDR_EXPR); 650 var = TREE_OPERAND (DECL_INITIAL (bnd_var), 0); 651 652 bound_val.pol.create (0); 653 chkp_collect_value (DECL_INITIAL (bnd_var), bound_val); 654 if (ci->type == CHECK_UPPER_BOUND) 655 { 656 if (TREE_CODE (var) == VAR_DECL) 657 { 658 if (DECL_SIZE (var) 659 && !chkp_variable_size_type (TREE_TYPE (var))) 660 size = DECL_SIZE_UNIT (var); 661 else 662 { 663 if (dump_file && (dump_flags & TDF_DETAILS)) 664 fprintf (dump_file, " result: cannot compute bounds\n"); 665 return 0; 666 } 667 } 668 else 669 { 670 gcc_assert (TREE_CODE (var) == STRING_CST); 671 size = build_int_cst (size_type_node, 672 TREE_STRING_LENGTH (var)); 673 } 674 675 address_t size_val; 676 size_val.pol.create (0); 677 chkp_collect_value (size, size_val); 678 chkp_add_addr_addr (bound_val, size_val); 679 size_val.pol.release (); 680 chkp_add_addr_item (bound_val, integer_minus_one_node, NULL); 681 } 682 } 683 else 684 { 685 if (dump_file && (dump_flags & TDF_DETAILS)) 686 fprintf (dump_file, " result: cannot compute bounds\n"); 687 return 0; 688 } 689 690 if (dump_file && (dump_flags & TDF_DETAILS)) 691 { 692 fprintf (dump_file, " bound value: "); 693 chkp_print_addr (bound_val); 694 fprintf (dump_file, "\n"); 695 } 696 697 chkp_sub_addr_addr (bound_val, ci->addr); 698 699 if (!chkp_is_constant_addr (bound_val, &sign)) 700 { 701 if (dump_file && (dump_flags & TDF_DETAILS)) 702 fprintf (dump_file, " result: cannot compute result\n"); 703 704 res = 0; 705 } 706 else if (sign == 0 707 || (ci->type == CHECK_UPPER_BOUND && sign > 0) 708 || (ci->type == CHECK_LOWER_BOUND && sign < 0)) 709 { 710 if (dump_file && (dump_flags & TDF_DETAILS)) 711 fprintf (dump_file, " result: always pass\n"); 712 713 res = 1; 714 } 715 else 716 { 717 if (dump_file && (dump_flags & TDF_DETAILS)) 718 fprintf (dump_file, " result: always fail\n"); 719 720 res = -1; 721 } 722 723 bound_val.pol.release (); 724 725 return res; 726} 727 728/* Try to compare bounds value and address value 729 used in the check CI. If we can prove that check 730 always pass then remove it. */ 731static void 732chkp_remove_check_if_pass (struct check_info *ci) 733{ 734 int result = 0; 735 736 if (dump_file && (dump_flags & TDF_DETAILS)) 737 { 738 fprintf (dump_file, "Trying to remove check: "); 739 print_gimple_stmt (dump_file, ci->stmt, 0, 0); 740 } 741 742 result = chkp_get_check_result (ci, ci->bounds); 743 744 if (result == 1) 745 { 746 gimple_stmt_iterator i = gsi_for_stmt (ci->stmt); 747 748 if (dump_file && (dump_flags & TDF_DETAILS)) 749 fprintf (dump_file, " action: delete check (always pass)\n"); 750 751 gsi_remove (&i, true); 752 unlink_stmt_vdef (ci->stmt); 753 release_defs (ci->stmt); 754 ci->stmt = NULL; 755 } 756 else if (result == -1) 757 { 758 if (dump_file && (dump_flags & TDF_DETAILS)) 759 fprintf (dump_file, " action: keep check (always fail)\n"); 760 warning_at (gimple_location (ci->stmt), OPT_Wchkp, 761 "memory access check always fail"); 762 } 763 else if (result == 0) 764 { 765 if (dump_file && (dump_flags & TDF_DETAILS)) 766 fprintf (dump_file, " action: keep check (cannot compute result)\n"); 767 } 768} 769 770/* For bounds used in CI check if bounds are produced by 771 intersection and we may use outer bounds instead. If 772 transformation is possible then fix check statement and 773 recompute its info. */ 774static void 775chkp_use_outer_bounds_if_possible (struct check_info *ci) 776{ 777 gimple bnd_def; 778 tree bnd1, bnd2, bnd_res = NULL; 779 int check_res1, check_res2; 780 781 if (TREE_CODE (ci->bounds) != SSA_NAME) 782 return; 783 784 bnd_def = SSA_NAME_DEF_STMT (ci->bounds); 785 if (gimple_code (bnd_def) != GIMPLE_CALL 786 || gimple_call_fndecl (bnd_def) != chkp_intersect_fndecl) 787 return; 788 789 if (dump_file && (dump_flags & TDF_DETAILS)) 790 { 791 fprintf (dump_file, "Check if bounds intersection is redundant: \n"); 792 fprintf (dump_file, " check: "); 793 print_gimple_stmt (dump_file, ci->stmt, 0, 0); 794 fprintf (dump_file, " intersection: "); 795 print_gimple_stmt (dump_file, bnd_def, 0, 0); 796 fprintf (dump_file, "\n"); 797 } 798 799 bnd1 = gimple_call_arg (bnd_def, 0); 800 bnd2 = gimple_call_arg (bnd_def, 1); 801 802 check_res1 = chkp_get_check_result (ci, bnd1); 803 check_res2 = chkp_get_check_result (ci, bnd2); 804 if (check_res1 == 1) 805 bnd_res = bnd2; 806 else if (check_res1 == -1) 807 bnd_res = bnd1; 808 else if (check_res2 == 1) 809 bnd_res = bnd1; 810 else if (check_res2 == -1) 811 bnd_res = bnd2; 812 813 if (bnd_res) 814 { 815 if (dump_file && (dump_flags & TDF_DETAILS)) 816 { 817 fprintf (dump_file, " action: use "); 818 print_generic_expr (dump_file, bnd2, 0); 819 fprintf (dump_file, " instead of "); 820 print_generic_expr (dump_file, ci->bounds, 0); 821 fprintf (dump_file, "\n"); 822 } 823 824 ci->bounds = bnd_res; 825 gimple_call_set_arg (ci->stmt, 1, bnd_res); 826 update_stmt (ci->stmt); 827 chkp_fill_check_info (ci->stmt, ci); 828 } 829} 830 831/* Try to find checks whose bounds were produced by intersection 832 which does not affect check result. In such check outer bounds 833 are used instead. It allows to remove excess intersections 834 and helps to compare checks. */ 835static void 836chkp_remove_excess_intersections (void) 837{ 838 basic_block bb; 839 840 if (dump_file && (dump_flags & TDF_DETAILS)) 841 fprintf (dump_file, "Searching for redundant bounds intersections...\n"); 842 843 FOR_EACH_BB_FN (bb, cfun) 844 { 845 struct bb_checks *bbc = &check_infos[bb->index]; 846 unsigned int no; 847 848 /* Iterate through all found checks in BB. */ 849 for (no = 0; no < bbc->checks.length (); no++) 850 if (bbc->checks[no].stmt) 851 chkp_use_outer_bounds_if_possible (&bbc->checks[no]); 852 } 853} 854 855/* Try to remove all checks which are known to alwyas pass. */ 856static void 857chkp_remove_constant_checks (void) 858{ 859 basic_block bb; 860 861 if (dump_file && (dump_flags & TDF_DETAILS)) 862 fprintf (dump_file, "Searching for redundant checks...\n"); 863 864 FOR_EACH_BB_FN (bb, cfun) 865 { 866 struct bb_checks *bbc = &check_infos[bb->index]; 867 unsigned int no; 868 869 /* Iterate through all found checks in BB. */ 870 for (no = 0; no < bbc->checks.length (); no++) 871 if (bbc->checks[no].stmt) 872 chkp_remove_check_if_pass (&bbc->checks[no]); 873 } 874} 875 876/* Return fast version of string function FNCODE. */ 877static tree 878chkp_get_nobnd_fndecl (enum built_in_function fncode) 879{ 880 /* Check if we are allowed to use fast string functions. */ 881 if (!flag_chkp_use_fast_string_functions) 882 return NULL_TREE; 883 884 tree fndecl = NULL_TREE; 885 886 switch (fncode) 887 { 888 case BUILT_IN_MEMCPY_CHKP: 889 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMCPY_NOBND); 890 break; 891 892 case BUILT_IN_MEMPCPY_CHKP: 893 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMPCPY_NOBND); 894 break; 895 896 case BUILT_IN_MEMMOVE_CHKP: 897 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMMOVE_NOBND); 898 break; 899 900 case BUILT_IN_MEMSET_CHKP: 901 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMSET_NOBND); 902 break; 903 904 case BUILT_IN_CHKP_MEMCPY_NOCHK_CHKP: 905 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMCPY_NOBND_NOCHK); 906 break; 907 908 case BUILT_IN_CHKP_MEMPCPY_NOCHK_CHKP: 909 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMPCPY_NOBND_NOCHK); 910 break; 911 912 case BUILT_IN_CHKP_MEMMOVE_NOCHK_CHKP: 913 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMMOVE_NOBND_NOCHK); 914 break; 915 916 case BUILT_IN_CHKP_MEMSET_NOCHK_CHKP: 917 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMSET_NOBND_NOCHK); 918 break; 919 920 default: 921 break; 922 } 923 924 if (fndecl) 925 fndecl = chkp_maybe_clone_builtin_fndecl (fndecl); 926 927 return fndecl; 928} 929 930 931/* Return no-check version of string function FNCODE. */ 932static tree 933chkp_get_nochk_fndecl (enum built_in_function fncode) 934{ 935 /* Check if we are allowed to use fast string functions. */ 936 if (!flag_chkp_use_nochk_string_functions) 937 return NULL_TREE; 938 939 tree fndecl = NULL_TREE; 940 941 switch (fncode) 942 { 943 case BUILT_IN_MEMCPY_CHKP: 944 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMCPY_NOCHK); 945 break; 946 947 case BUILT_IN_MEMPCPY_CHKP: 948 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMPCPY_NOCHK); 949 break; 950 951 case BUILT_IN_MEMMOVE_CHKP: 952 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMMOVE_NOCHK); 953 break; 954 955 case BUILT_IN_MEMSET_CHKP: 956 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMSET_NOCHK); 957 break; 958 959 case BUILT_IN_CHKP_MEMCPY_NOBND_CHKP: 960 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMCPY_NOBND_NOCHK); 961 break; 962 963 case BUILT_IN_CHKP_MEMPCPY_NOBND_CHKP: 964 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMPCPY_NOBND_NOCHK); 965 break; 966 967 case BUILT_IN_CHKP_MEMMOVE_NOBND_CHKP: 968 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMMOVE_NOBND_NOCHK); 969 break; 970 971 case BUILT_IN_CHKP_MEMSET_NOBND_CHKP: 972 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMSET_NOBND_NOCHK); 973 break; 974 975 default: 976 break; 977 } 978 979 if (fndecl) 980 fndecl = chkp_maybe_clone_builtin_fndecl (fndecl); 981 982 return fndecl; 983} 984 985/* Find memcpy, mempcpy, memmove and memset calls, perform 986 checks before call and then call no_chk version of 987 functions. We do it on O2 to enable inlining of these 988 functions during expand. 989 990 Also try to find memcpy, mempcpy, memmove and memset calls 991 which are known to not write pointers to memory and use 992 faster function versions for them. */ 993static void 994chkp_optimize_string_function_calls (void) 995{ 996 basic_block bb; 997 998 if (dump_file && (dump_flags & TDF_DETAILS)) 999 fprintf (dump_file, "Searching for replaceable string function calls...\n"); 1000 1001 FOR_EACH_BB_FN (bb, cfun) 1002 { 1003 gimple_stmt_iterator i; 1004 1005 for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i)) 1006 { 1007 gimple stmt = gsi_stmt (i); 1008 tree fndecl; 1009 1010 if (gimple_code (stmt) != GIMPLE_CALL 1011 || !gimple_call_with_bounds_p (stmt)) 1012 continue; 1013 1014 fndecl = gimple_call_fndecl (stmt); 1015 1016 if (!fndecl || DECL_BUILT_IN_CLASS (fndecl) != BUILT_IN_NORMAL) 1017 continue; 1018 1019 if (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMCPY_CHKP 1020 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMPCPY_CHKP 1021 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMMOVE_CHKP 1022 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMSET_CHKP) 1023 { 1024 tree dst = gimple_call_arg (stmt, 0); 1025 tree dst_bnd = gimple_call_arg (stmt, 1); 1026 bool is_memset = DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMSET_CHKP; 1027 tree size = gimple_call_arg (stmt, is_memset ? 3 : 4); 1028 tree fndecl_nochk; 1029 gimple_stmt_iterator j; 1030 basic_block check_bb; 1031 address_t size_val; 1032 int sign; 1033 bool known; 1034 1035 /* We may replace call with corresponding __chkp_*_nobnd 1036 call in case destination pointer base type is not 1037 void or pointer. */ 1038 if (POINTER_TYPE_P (TREE_TYPE (dst)) 1039 && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (dst))) 1040 && !chkp_type_has_pointer (TREE_TYPE (TREE_TYPE (dst)))) 1041 { 1042 tree fndecl_nobnd 1043 = chkp_get_nobnd_fndecl (DECL_FUNCTION_CODE (fndecl)); 1044 1045 if (fndecl_nobnd) 1046 fndecl = fndecl_nobnd; 1047 } 1048 1049 fndecl_nochk = chkp_get_nochk_fndecl (DECL_FUNCTION_CODE (fndecl)); 1050 1051 if (fndecl_nochk) 1052 fndecl = fndecl_nochk; 1053 1054 if (fndecl != gimple_call_fndecl (stmt)) 1055 { 1056 if (dump_file && (dump_flags & TDF_DETAILS)) 1057 { 1058 fprintf (dump_file, "Replacing call: "); 1059 print_gimple_stmt (dump_file, stmt, 0, 1060 TDF_VOPS|TDF_MEMSYMS); 1061 } 1062 1063 gimple_call_set_fndecl (stmt, fndecl); 1064 1065 if (dump_file && (dump_flags & TDF_DETAILS)) 1066 { 1067 fprintf (dump_file, "With a new call: "); 1068 print_gimple_stmt (dump_file, stmt, 0, 1069 TDF_VOPS|TDF_MEMSYMS); 1070 } 1071 } 1072 1073 /* If there is no nochk version of function then 1074 do nothing. Otherwise insert checks before 1075 the call. */ 1076 if (!fndecl_nochk) 1077 continue; 1078 1079 /* If size passed to call is known and > 0 1080 then we may insert checks unconditionally. */ 1081 size_val.pol.create (0); 1082 chkp_collect_value (size, size_val); 1083 known = chkp_is_constant_addr (size_val, &sign); 1084 size_val.pol.release (); 1085 1086 /* If we are not sure size is not zero then we have 1087 to perform runtime check for size and perform 1088 checks only when size is not zero. */ 1089 if (!known) 1090 { 1091 gimple check = gimple_build_cond (NE_EXPR, 1092 size, 1093 size_zero_node, 1094 NULL_TREE, 1095 NULL_TREE); 1096 1097 /* Split block before string function call. */ 1098 gsi_prev (&i); 1099 check_bb = insert_cond_bb (bb, gsi_stmt (i), check); 1100 1101 /* Set position for checks. */ 1102 j = gsi_last_bb (check_bb); 1103 1104 /* The block was splitted and therefore we 1105 need to set iterator to its end. */ 1106 i = gsi_last_bb (bb); 1107 } 1108 /* If size is known to be zero then no checks 1109 should be performed. */ 1110 else if (!sign) 1111 continue; 1112 else 1113 j = i; 1114 1115 size = size_binop (MINUS_EXPR, size, size_one_node); 1116 if (!is_memset) 1117 { 1118 tree src = gimple_call_arg (stmt, 2); 1119 tree src_bnd = gimple_call_arg (stmt, 3); 1120 1121 chkp_check_mem_access (src, fold_build_pointer_plus (src, size), 1122 src_bnd, j, gimple_location (stmt), 1123 integer_zero_node); 1124 } 1125 1126 chkp_check_mem_access (dst, fold_build_pointer_plus (dst, size), 1127 dst_bnd, j, gimple_location (stmt), 1128 integer_one_node); 1129 1130 } 1131 } 1132 } 1133} 1134 1135/* Intrumentation pass inserts most of bounds creation code 1136 in the header of the function. We want to move bounds 1137 creation closer to bounds usage to reduce bounds lifetime. 1138 We also try to avoid bounds creation code on paths where 1139 bounds are not used. */ 1140static void 1141chkp_reduce_bounds_lifetime (void) 1142{ 1143 basic_block bb = FALLTHRU_EDGE (ENTRY_BLOCK_PTR_FOR_FN (cfun))->dest; 1144 gimple_stmt_iterator i; 1145 1146 for (i = gsi_start_bb (bb); !gsi_end_p (i); ) 1147 { 1148 gimple dom_use, use_stmt, stmt = gsi_stmt (i); 1149 basic_block dom_bb; 1150 ssa_op_iter iter; 1151 imm_use_iterator use_iter; 1152 use_operand_p use_p; 1153 tree op; 1154 bool want_move = false; 1155 bool deps = false; 1156 1157 if (gimple_code (stmt) == GIMPLE_CALL 1158 && gimple_call_fndecl (stmt) == chkp_bndmk_fndecl) 1159 want_move = true; 1160 1161 if (gimple_code (stmt) == GIMPLE_ASSIGN 1162 && POINTER_BOUNDS_P (gimple_assign_lhs (stmt)) 1163 && gimple_assign_rhs_code (stmt) == VAR_DECL) 1164 want_move = true; 1165 1166 if (!want_move) 1167 { 1168 gsi_next (&i); 1169 continue; 1170 } 1171 1172 /* Check we do not increase other values lifetime. */ 1173 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE) 1174 { 1175 op = USE_FROM_PTR (use_p); 1176 1177 if (TREE_CODE (op) == SSA_NAME 1178 && gimple_code (SSA_NAME_DEF_STMT (op)) != GIMPLE_NOP) 1179 { 1180 deps = true; 1181 break; 1182 } 1183 } 1184 1185 if (deps) 1186 { 1187 gsi_next (&i); 1188 continue; 1189 } 1190 1191 /* Check all usages of bounds. */ 1192 if (gimple_code (stmt) == GIMPLE_CALL) 1193 op = gimple_call_lhs (stmt); 1194 else 1195 { 1196 gcc_assert (gimple_code (stmt) == GIMPLE_ASSIGN); 1197 op = gimple_assign_lhs (stmt); 1198 } 1199 1200 dom_use = NULL; 1201 dom_bb = NULL; 1202 1203 FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, op) 1204 { 1205 if (is_gimple_debug (use_stmt)) 1206 continue; 1207 1208 if (dom_bb && 1209 dominated_by_p (CDI_DOMINATORS, 1210 dom_bb, gimple_bb (use_stmt))) 1211 { 1212 dom_use = use_stmt; 1213 dom_bb = NULL; 1214 } 1215 else if (dom_bb) 1216 dom_bb = nearest_common_dominator (CDI_DOMINATORS, dom_bb, 1217 gimple_bb (use_stmt)); 1218 else if (!dom_use) 1219 dom_use = use_stmt; 1220 else if (stmt_dominates_stmt_p (use_stmt, dom_use)) 1221 dom_use = use_stmt; 1222 else if (!stmt_dominates_stmt_p (dom_use, use_stmt) 1223 /* If dom_use and use_stmt are PHI nodes in one BB 1224 then it is OK to keep any of them as dom_use. 1225 stmt_dominates_stmt_p returns 0 for such 1226 combination, so check it here manually. */ 1227 && (gimple_code (dom_use) != GIMPLE_PHI 1228 || gimple_code (use_stmt) != GIMPLE_PHI 1229 || gimple_bb (use_stmt) != gimple_bb (dom_use)) 1230 ) 1231 { 1232 dom_bb = nearest_common_dominator (CDI_DOMINATORS, 1233 gimple_bb (use_stmt), 1234 gimple_bb (dom_use)); 1235 dom_use = NULL; 1236 } 1237 } 1238 1239 /* In case there is a single use, just move bounds 1240 creation to the use. */ 1241 if (dom_use || dom_bb) 1242 { 1243 if (dump_file && (dump_flags & TDF_DETAILS)) 1244 { 1245 fprintf (dump_file, "Moving creation of "); 1246 print_generic_expr (dump_file, op, 0); 1247 fprintf (dump_file, " down to its use.\n"); 1248 } 1249 1250 if (dom_use && gimple_code (dom_use) == GIMPLE_PHI) 1251 { 1252 dom_bb = get_immediate_dominator (CDI_DOMINATORS, 1253 gimple_bb (dom_use)); 1254 dom_use = NULL; 1255 } 1256 1257 if (dom_bb == bb 1258 || (dom_use && gimple_bb (dom_use) == bb)) 1259 { 1260 if (dump_file && (dump_flags & TDF_DETAILS)) 1261 fprintf (dump_file, "Cannot move statement bacause there is no " 1262 "suitable dominator block other than entry block.\n"); 1263 1264 gsi_next (&i); 1265 } 1266 else 1267 { 1268 if (dom_bb) 1269 { 1270 gimple_stmt_iterator last = gsi_last_bb (dom_bb); 1271 if (!gsi_end_p (last) && stmt_ends_bb_p (gsi_stmt (last))) 1272 gsi_move_before (&i, &last); 1273 else 1274 gsi_move_after (&i, &last); 1275 } 1276 else 1277 { 1278 gimple_stmt_iterator gsi = gsi_for_stmt (dom_use); 1279 gsi_move_before (&i, &gsi); 1280 } 1281 1282 update_stmt (stmt); 1283 } 1284 } 1285 else 1286 gsi_next (&i); 1287 } 1288} 1289 1290/* Initilize checker optimization pass. */ 1291static void 1292chkp_opt_init (void) 1293{ 1294 check_infos.create (0); 1295 1296 calculate_dominance_info (CDI_DOMINATORS); 1297 calculate_dominance_info (CDI_POST_DOMINATORS); 1298 1299 /* With LTO constant bounds vars may be not initialized by now. 1300 Get constant bounds vars to handle their assignments during 1301 optimizations. */ 1302 chkp_get_zero_bounds_var (); 1303 chkp_get_none_bounds_var (); 1304} 1305 1306/* Finalise checker optimization pass. */ 1307static void 1308chkp_opt_fini (void) 1309{ 1310 chkp_fix_cfg (); 1311} 1312 1313/* Checker optimization pass function. */ 1314static unsigned int 1315chkp_opt_execute (void) 1316{ 1317 chkp_opt_init(); 1318 1319 /* This optimization may introduce new checks 1320 and thus we put it before checks search. */ 1321 chkp_optimize_string_function_calls (); 1322 1323 chkp_gather_checks_info (); 1324 1325 chkp_remove_excess_intersections (); 1326 1327 chkp_remove_constant_checks (); 1328 1329 chkp_reduce_bounds_lifetime (); 1330 1331 chkp_release_check_info (); 1332 1333 chkp_opt_fini (); 1334 1335 return 0; 1336} 1337 1338/* Pass gate. */ 1339static bool 1340chkp_opt_gate (void) 1341{ 1342 return chkp_function_instrumented_p (cfun->decl) 1343 && (flag_chkp_optimize > 0 1344 || (flag_chkp_optimize == -1 && optimize > 0)); 1345} 1346 1347namespace { 1348 1349const pass_data pass_data_chkp_opt = 1350{ 1351 GIMPLE_PASS, /* type */ 1352 "chkpopt", /* name */ 1353 OPTGROUP_NONE, /* optinfo_flags */ 1354 TV_NONE, /* tv_id */ 1355 PROP_ssa | PROP_cfg, /* properties_required */ 1356 0, /* properties_provided */ 1357 0, /* properties_destroyed */ 1358 0, /* todo_flags_start */ 1359 TODO_verify_il 1360 | TODO_update_ssa /* todo_flags_finish */ 1361}; 1362 1363class pass_chkp_opt : public gimple_opt_pass 1364{ 1365public: 1366 pass_chkp_opt (gcc::context *ctxt) 1367 : gimple_opt_pass (pass_data_chkp_opt, ctxt) 1368 {} 1369 1370 /* opt_pass methods: */ 1371 virtual opt_pass * clone () 1372 { 1373 return new pass_chkp_opt (m_ctxt); 1374 } 1375 1376 virtual bool gate (function *) 1377 { 1378 return chkp_opt_gate (); 1379 } 1380 1381 virtual unsigned int execute (function *) 1382 { 1383 return chkp_opt_execute (); 1384 } 1385 1386}; // class pass_chkp_opt 1387 1388} // anon namespace 1389 1390gimple_opt_pass * 1391make_pass_chkp_opt (gcc::context *ctxt) 1392{ 1393 return new pass_chkp_opt (ctxt); 1394} 1395