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