2018-05-29 Richard Biener <rguenther@suse.de>
[official-gcc.git] / gcc / tree-chkp-opt.c
blob5a005a6a7b63da9044b4572167b9f98d9ce7dc5e
1 /* Pointer Bounds Checker optimization pass.
2 Copyright (C) 2014-2018 Free Software Foundation, Inc.
3 Contributed by Ilya Enkovich (ilya.enkovich@intel.com)
5 This file is part of GCC.
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.
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.
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/>. */
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"
40 enum check_type
42 CHECK_LOWER_BOUND,
43 CHECK_UPPER_BOUND
46 struct pol_item
48 tree cst;
49 tree var;
52 struct address_t
54 vec<struct pol_item> pol;
57 /* Structure to hold check informtation. */
58 struct check_info
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;
70 /* Structure to hold checks information for BB. */
71 struct bb_checks
73 vec<struct check_info, va_heap, vl_ptr> checks;
76 static void chkp_collect_value (tree ssa_name, address_t &res);
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))
87 static vec<struct bb_checks, va_heap, vl_ptr> check_infos;
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)
95 const struct pol_item *p1 = (const struct pol_item *)i1;
96 const struct pol_item *p2 = (const struct pol_item *)i2;
98 if (p1->var == p2->var)
99 return 0;
100 else if (p1->var > p2->var)
101 return 1;
102 else
103 return -1;
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)
112 int left = 0;
113 int right = addr.pol.length () - 1;
114 int n;
116 while (right >= left)
118 n = (left + right) / 2;
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;
132 return -1;
135 /* Return constant CST extended to size type. */
136 static tree
137 chkp_extend_const (tree cst)
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));
142 return cst;
145 /* Add polynomial item CST * VAR to ADDR. */
146 static void
147 chkp_add_addr_item (address_t &addr, tree cst, tree var)
149 int n = chkp_pol_find (addr, var);
151 cst = chkp_extend_const (cst);
153 if (n < 0)
155 struct pol_item item;
156 item.cst = cst;
157 item.var = var;
159 addr.pol.safe_push (item);
160 addr.pol.qsort (&chkp_pol_item_compare);
162 else
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);
172 /* Subtract polynomial item CST * VAR from ADDR. */
173 static void
174 chkp_sub_addr_item (address_t &addr, tree cst, tree var)
176 int n = chkp_pol_find (addr, var);
178 cst = chkp_extend_const (cst);
180 if (n < 0)
182 struct pol_item item;
183 item.cst = fold_build2 (MINUS_EXPR, TREE_TYPE (cst),
184 integer_zero_node, cst);
185 item.var = var;
187 addr.pol.safe_push (item);
188 addr.pol.qsort (&chkp_pol_item_compare);
190 else
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);
200 /* Add address DELTA to ADDR. */
201 static void
202 chkp_add_addr_addr (address_t &addr, address_t &delta)
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);
209 /* Subtract address DELTA from ADDR. */
210 static void
211 chkp_sub_addr_addr (address_t &addr, address_t &delta)
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);
218 /* Mutiply address ADDR by integer constant MULT. */
219 static void
220 chkp_mult_addr (address_t &addr, tree mult)
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);
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)
234 *sign = 0;
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;
251 return true;
254 /* Dump ADDR into dump_file. */
255 static void
256 chkp_print_addr (const address_t &addr)
258 unsigned int n = 0;
259 for (n = 0; n < addr.pol.length (); n++)
261 if (n > 0)
262 fprintf (dump_file, " + ");
264 if (addr.pol[n].var == NULL_TREE)
265 print_generic_expr (dump_file, addr.pol[n].cst);
266 else
268 if (TREE_CODE (addr.pol[n].cst) != INTEGER_CST
269 || !integer_onep (addr.pol[n].cst))
271 print_generic_expr (dump_file, addr.pol[n].cst);
272 fprintf (dump_file, " * ");
274 print_generic_expr (dump_file, addr.pol[n].var);
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)
284 tree obj = TREE_OPERAND (ptr, 0);
285 address_t addr;
287 switch (TREE_CODE (obj))
289 case INDIRECT_REF:
290 chkp_collect_value (TREE_OPERAND (obj, 0), res);
291 break;
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;
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;
310 case COMPONENT_REF:
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))
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 ();
330 break;
332 default:
333 chkp_add_addr_item (res, integer_one_node, ptr);
334 break;
338 /* Compute value of PTR and put it into address RES. */
339 static void
340 chkp_collect_value (tree ptr, address_t &res)
342 gimple *def_stmt;
343 enum gimple_code code;
344 enum tree_code rhs_code;
345 address_t addr;
346 tree rhs1;
348 if (TREE_CODE (ptr) == INTEGER_CST)
350 chkp_add_addr_item (res, ptr, NULL);
351 return;
353 else if (TREE_CODE (ptr) == ADDR_EXPR)
355 chkp_collect_addr_value (ptr, res);
356 return;
358 else if (TREE_CODE (ptr) != SSA_NAME)
360 chkp_add_addr_item (res, integer_one_node, ptr);
361 return;
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);
369 /* Currently we do not walk through statements other
370 than assignment. */
371 if (code != GIMPLE_ASSIGN)
373 chkp_add_addr_item (res, integer_one_node, ptr);
374 return;
377 rhs_code = gimple_assign_rhs_code (def_stmt);
378 rhs1 = gimple_assign_rhs1 (def_stmt);
380 switch (rhs_code)
382 case SSA_NAME:
383 case INTEGER_CST:
384 case ADDR_EXPR:
385 chkp_collect_value (rhs1, res);
386 break;
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;
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;
405 case MULT_EXPR:
406 if (TREE_CODE (rhs1) == SSA_NAME
407 && TREE_CODE (gimple_assign_rhs2 (def_stmt)) == INTEGER_CST)
409 chkp_collect_value (rhs1, res);
410 chkp_mult_addr (res, gimple_assign_rhs2 (def_stmt));
412 else if (TREE_CODE (gimple_assign_rhs2 (def_stmt)) == SSA_NAME
413 && TREE_CODE (rhs1) == INTEGER_CST)
415 chkp_collect_value (gimple_assign_rhs2 (def_stmt), res);
416 chkp_mult_addr (res, rhs1);
418 else
419 chkp_add_addr_item (res, integer_one_node, ptr);
420 break;
422 default:
423 chkp_add_addr_item (res, integer_one_node, ptr);
424 break;
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)
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;
442 /* Release structures holding check information
443 for current function. */
444 static void
445 chkp_release_check_info (void)
447 unsigned int n, m;
449 if (check_infos.exists ())
451 for (n = 0; n < check_infos.length (); n++)
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 ();
458 check_infos.release ();
462 /* Create structures to hold check information
463 for current function. */
464 static void
465 chkp_init_check_info (void)
467 struct bb_checks empty_bbc;
468 int n;
470 empty_bbc.checks = vNULL;
472 chkp_release_check_info ();
474 check_infos.create (last_basic_block_for_fn (cfun));
475 for (n = 0; n < last_basic_block_for_fn (cfun); n++)
477 check_infos.safe_push (empty_bbc);
478 check_infos.last ().checks.create (0);
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)
487 basic_block bb;
488 gimple_stmt_iterator i;
490 if (dump_file && (dump_flags & TDF_DETAILS))
491 fprintf (dump_file, "Gathering information about checks...\n");
493 chkp_init_check_info ();
495 FOR_EACH_BB_FN (bb, cfun)
497 struct bb_checks *bbc = &check_infos[bb->index];
499 if (dump_file && (dump_flags & TDF_DETAILS))
500 fprintf (dump_file, "Searching checks in BB%d...\n", bb->index);
502 for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
504 gimple *stmt = gsi_stmt (i);
506 if (gimple_code (stmt) != GIMPLE_CALL)
507 continue;
509 if (gimple_call_fndecl (stmt) == chkp_checkl_fndecl
510 || gimple_call_fndecl (stmt) == chkp_checku_fndecl)
512 struct check_info ci;
514 chkp_fill_check_info (stmt, &ci);
515 bbc->checks.safe_push (ci);
517 if (dump_file && (dump_flags & TDF_DETAILS))
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);
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)
538 gimple *bnd_def;
539 address_t bound_val;
540 int sign, res = 0;
542 if (dump_file && (dump_flags & TDF_DETAILS))
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");
554 if (TREE_CODE (bounds) != SSA_NAME)
556 if (dump_file && (dump_flags & TDF_DETAILS))
557 fprintf (dump_file, " result: bounds tree code is not ssa_name\n");
558 return 0;
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)
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)
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);
579 else if (gimple_code (bnd_def) == GIMPLE_ASSIGN
580 && gimple_assign_rhs1 (bnd_def) == chkp_get_zero_bounds_var ())
582 if (dump_file && (dump_flags & TDF_DETAILS))
583 fprintf (dump_file, " result: always pass with zero bounds\n");
584 return 1;
586 else if (gimple_code (bnd_def) == GIMPLE_ASSIGN
587 && gimple_assign_rhs1 (bnd_def) == chkp_get_none_bounds_var ())
589 if (dump_file && (dump_flags & TDF_DETAILS))
590 fprintf (dump_file, " result: always fails with none bounds\n");
591 return -1;
593 else if (gimple_code (bnd_def) == GIMPLE_ASSIGN
594 && TREE_CODE (gimple_assign_rhs1 (bnd_def)) == VAR_DECL)
596 tree bnd_var = gimple_assign_rhs1 (bnd_def);
597 tree var;
598 tree size;
600 if (!DECL_INITIAL (bnd_var)
601 || DECL_INITIAL (bnd_var) == error_mark_node)
603 if (dump_file && (dump_flags & TDF_DETAILS))
604 fprintf (dump_file, " result: cannot compute bounds\n");
605 return 0;
608 gcc_assert (TREE_CODE (DECL_INITIAL (bnd_var)) == ADDR_EXPR);
609 var = TREE_OPERAND (DECL_INITIAL (bnd_var), 0);
611 bound_val.pol.create (0);
612 chkp_collect_value (DECL_INITIAL (bnd_var), bound_val);
613 if (ci->type == CHECK_UPPER_BOUND)
615 if (VAR_P (var))
617 if (DECL_SIZE (var)
618 && !chkp_variable_size_type (TREE_TYPE (var)))
619 size = DECL_SIZE_UNIT (var);
620 else
622 if (dump_file && (dump_flags & TDF_DETAILS))
623 fprintf (dump_file, " result: cannot compute bounds\n");
624 return 0;
627 else
629 gcc_assert (TREE_CODE (var) == STRING_CST);
630 size = build_int_cst (size_type_node,
631 TREE_STRING_LENGTH (var));
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);
642 else
644 if (dump_file && (dump_flags & TDF_DETAILS))
645 fprintf (dump_file, " result: cannot compute bounds\n");
646 return 0;
649 if (dump_file && (dump_flags & TDF_DETAILS))
651 fprintf (dump_file, " bound value: ");
652 chkp_print_addr (bound_val);
653 fprintf (dump_file, "\n");
656 chkp_sub_addr_addr (bound_val, ci->addr);
658 if (!chkp_is_constant_addr (bound_val, &sign))
660 if (dump_file && (dump_flags & TDF_DETAILS))
661 fprintf (dump_file, " result: cannot compute result\n");
663 res = 0;
665 else if (sign == 0
666 || (ci->type == CHECK_UPPER_BOUND && sign > 0)
667 || (ci->type == CHECK_LOWER_BOUND && sign < 0))
669 if (dump_file && (dump_flags & TDF_DETAILS))
670 fprintf (dump_file, " result: always pass\n");
672 res = 1;
674 else
676 if (dump_file && (dump_flags & TDF_DETAILS))
677 fprintf (dump_file, " result: always fail\n");
679 res = -1;
682 bound_val.pol.release ();
684 return res;
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)
693 int result = 0;
695 if (dump_file && (dump_flags & TDF_DETAILS))
697 fprintf (dump_file, "Trying to remove check: ");
698 print_gimple_stmt (dump_file, ci->stmt, 0);
701 result = chkp_get_check_result (ci, ci->bounds);
703 if (result == 1)
705 gimple_stmt_iterator i = gsi_for_stmt (ci->stmt);
707 if (dump_file && (dump_flags & TDF_DETAILS))
708 fprintf (dump_file, " action: delete check (always pass)\n");
710 gsi_remove (&i, true);
711 unlink_stmt_vdef (ci->stmt);
712 release_defs (ci->stmt);
713 ci->stmt = NULL;
715 else if (result == -1)
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");
722 else if (result == 0)
724 if (dump_file && (dump_flags & TDF_DETAILS))
725 fprintf (dump_file, " action: keep check (cannot compute result)\n");
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)
736 gimple *bnd_def;
737 tree bnd1, bnd2, bnd_res = NULL;
738 int check_res1, check_res2;
740 if (TREE_CODE (ci->bounds) != SSA_NAME)
741 return;
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;
748 if (dump_file && (dump_flags & TDF_DETAILS))
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");
758 bnd1 = gimple_call_arg (bnd_def, 0);
759 bnd2 = gimple_call_arg (bnd_def, 1);
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;
772 if (bnd_res)
774 if (dump_file && (dump_flags & TDF_DETAILS))
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");
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);
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)
797 basic_block bb;
799 if (dump_file && (dump_flags & TDF_DETAILS))
800 fprintf (dump_file, "Searching for redundant bounds intersections...\n");
802 FOR_EACH_BB_FN (bb, cfun)
804 struct bb_checks *bbc = &check_infos[bb->index];
805 unsigned int no;
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]);
814 /* Try to remove all checks which are known to alwyas pass. */
815 static void
816 chkp_remove_constant_checks (void)
818 basic_block bb;
820 if (dump_file && (dump_flags & TDF_DETAILS))
821 fprintf (dump_file, "Searching for redundant checks...\n");
823 FOR_EACH_BB_FN (bb, cfun)
825 struct bb_checks *bbc = &check_infos[bb->index];
826 unsigned int no;
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]);
835 /* Return fast version of string function FNCODE. */
836 static tree
837 chkp_get_nobnd_fndecl (enum built_in_function fncode)
839 /* Check if we are allowed to use fast string functions. */
840 if (!flag_chkp_use_fast_string_functions)
841 return NULL_TREE;
843 tree fndecl = NULL_TREE;
845 switch (fncode)
847 case BUILT_IN_MEMCPY_CHKP:
848 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMCPY_NOBND);
849 break;
851 case BUILT_IN_MEMPCPY_CHKP:
852 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMPCPY_NOBND);
853 break;
855 case BUILT_IN_MEMMOVE_CHKP:
856 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMMOVE_NOBND);
857 break;
859 case BUILT_IN_MEMSET_CHKP:
860 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMSET_NOBND);
861 break;
863 case BUILT_IN_CHKP_MEMCPY_NOCHK_CHKP:
864 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMCPY_NOBND_NOCHK);
865 break;
867 case BUILT_IN_CHKP_MEMPCPY_NOCHK_CHKP:
868 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMPCPY_NOBND_NOCHK);
869 break;
871 case BUILT_IN_CHKP_MEMMOVE_NOCHK_CHKP:
872 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMMOVE_NOBND_NOCHK);
873 break;
875 case BUILT_IN_CHKP_MEMSET_NOCHK_CHKP:
876 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMSET_NOBND_NOCHK);
877 break;
879 default:
880 break;
883 if (fndecl)
884 fndecl = chkp_maybe_clone_builtin_fndecl (fndecl);
886 return fndecl;
890 /* Return no-check version of string function FNCODE. */
891 static tree
892 chkp_get_nochk_fndecl (enum built_in_function fncode)
894 /* Check if we are allowed to use fast string functions. */
895 if (!flag_chkp_use_nochk_string_functions)
896 return NULL_TREE;
898 tree fndecl = NULL_TREE;
900 switch (fncode)
902 case BUILT_IN_MEMCPY_CHKP:
903 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMCPY_NOCHK);
904 break;
906 case BUILT_IN_MEMPCPY_CHKP:
907 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMPCPY_NOCHK);
908 break;
910 case BUILT_IN_MEMMOVE_CHKP:
911 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMMOVE_NOCHK);
912 break;
914 case BUILT_IN_MEMSET_CHKP:
915 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMSET_NOCHK);
916 break;
918 case BUILT_IN_CHKP_MEMCPY_NOBND_CHKP:
919 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMCPY_NOBND_NOCHK);
920 break;
922 case BUILT_IN_CHKP_MEMPCPY_NOBND_CHKP:
923 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMPCPY_NOBND_NOCHK);
924 break;
926 case BUILT_IN_CHKP_MEMMOVE_NOBND_CHKP:
927 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMMOVE_NOBND_NOCHK);
928 break;
930 case BUILT_IN_CHKP_MEMSET_NOBND_CHKP:
931 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMSET_NOBND_NOCHK);
932 break;
934 default:
935 break;
938 if (fndecl)
939 fndecl = chkp_maybe_clone_builtin_fndecl (fndecl);
941 return fndecl;
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.
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)
955 basic_block bb;
957 if (dump_file && (dump_flags & TDF_DETAILS))
958 fprintf (dump_file, "Searching for replaceable string function calls...\n");
960 FOR_EACH_BB_FN (bb, cfun)
962 gimple_stmt_iterator i;
964 for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
966 gimple *stmt = gsi_stmt (i);
967 tree fndecl;
969 if (!is_gimple_call (stmt)
970 || !gimple_call_with_bounds_p (stmt)
971 || !gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
972 continue;
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)
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;
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))))
998 tree fndecl_nobnd
999 = chkp_get_nobnd_fndecl (DECL_FUNCTION_CODE (fndecl));
1001 if (fndecl_nobnd)
1002 fndecl = fndecl_nobnd;
1005 fndecl_nochk = chkp_get_nochk_fndecl (DECL_FUNCTION_CODE (fndecl));
1007 if (fndecl_nochk)
1008 fndecl = fndecl_nochk;
1010 if (fndecl != gimple_call_fndecl (stmt))
1012 if (dump_file && (dump_flags & TDF_DETAILS))
1014 fprintf (dump_file, "Replacing call: ");
1015 print_gimple_stmt (dump_file, stmt, 0,
1016 TDF_VOPS|TDF_MEMSYMS);
1019 gimple_call_set_fndecl (stmt, fndecl);
1021 if (dump_file && (dump_flags & TDF_DETAILS))
1023 fprintf (dump_file, "With a new call: ");
1024 print_gimple_stmt (dump_file, stmt, 0,
1025 TDF_VOPS|TDF_MEMSYMS);
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;
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 ();
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)
1047 gimple *check = gimple_build_cond (NE_EXPR,
1048 size,
1049 size_zero_node,
1050 NULL_TREE,
1051 NULL_TREE);
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 ());
1058 /* Set position for checks. */
1059 j = gsi_last_bb (check_bb);
1061 /* The block was splitted and therefore we
1062 need to set iterator to its end. */
1063 i = gsi_last_bb (bb);
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;
1072 size = size_binop (MINUS_EXPR, size, size_one_node);
1073 if (!is_memset)
1075 tree src = gimple_call_arg (stmt, 2);
1076 tree src_bnd = gimple_call_arg (stmt, 3);
1078 chkp_check_mem_access (src, fold_build_pointer_plus (src, size),
1079 src_bnd, j, gimple_location (stmt),
1080 integer_zero_node);
1083 chkp_check_mem_access (dst, fold_build_pointer_plus (dst, size),
1084 dst_bnd, j, gimple_location (stmt),
1085 integer_one_node);
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)
1100 basic_block bb = FALLTHRU_EDGE (ENTRY_BLOCK_PTR_FOR_FN (cfun))->dest;
1101 gimple_stmt_iterator i;
1103 for (i = gsi_start_bb (bb); !gsi_end_p (i); )
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;
1114 if (gimple_code (stmt) == GIMPLE_CALL
1115 && gimple_call_fndecl (stmt) == chkp_bndmk_fndecl)
1116 want_move = true;
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;
1123 if (!want_move)
1125 gsi_next (&i);
1126 continue;
1129 /* Check we do not increase other values lifetime. */
1130 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
1132 op = USE_FROM_PTR (use_p);
1134 if (TREE_CODE (op) == SSA_NAME
1135 && gimple_code (SSA_NAME_DEF_STMT (op)) != GIMPLE_NOP)
1137 deps = true;
1138 break;
1142 if (deps)
1144 gsi_next (&i);
1145 continue;
1148 /* Check all usages of bounds. */
1149 if (gimple_code (stmt) == GIMPLE_CALL)
1150 op = gimple_call_lhs (stmt);
1151 else
1153 gcc_assert (gimple_code (stmt) == GIMPLE_ASSIGN);
1154 op = gimple_assign_lhs (stmt);
1157 dom_use = NULL;
1158 dom_bb = NULL;
1160 FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, op)
1162 if (is_gimple_debug (use_stmt))
1163 continue;
1165 if (dom_bb &&
1166 dominated_by_p (CDI_DOMINATORS,
1167 dom_bb, gimple_bb (use_stmt)))
1169 dom_use = use_stmt;
1170 dom_bb = NULL;
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))
1189 dom_bb = nearest_common_dominator (CDI_DOMINATORS,
1190 gimple_bb (use_stmt),
1191 gimple_bb (dom_use));
1192 dom_use = NULL;
1196 /* In case there is a single use, just move bounds
1197 creation to the use. */
1198 if (dom_use || dom_bb)
1200 if (dump_file && (dump_flags & TDF_DETAILS))
1202 fprintf (dump_file, "Moving creation of ");
1203 print_generic_expr (dump_file, op);
1204 fprintf (dump_file, " down to its use.\n");
1207 if (dom_use && gimple_code (dom_use) == GIMPLE_PHI)
1209 dom_bb = get_immediate_dominator (CDI_DOMINATORS,
1210 gimple_bb (dom_use));
1211 dom_use = NULL;
1214 if (dom_bb == bb
1215 || (dom_use && gimple_bb (dom_use) == bb))
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");
1221 gsi_next (&i);
1223 else
1225 if (dom_bb)
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);
1233 else
1235 gimple_stmt_iterator gsi = gsi_for_stmt (dom_use);
1236 gsi_move_before (&i, &gsi);
1239 gimple_set_vdef (stmt, NULL_TREE);
1240 gimple_set_vuse (stmt, NULL_TREE);
1241 update_stmt (stmt);
1244 else
1245 gsi_next (&i);
1249 /* Initilize checker optimization pass. */
1250 static void
1251 chkp_opt_init (void)
1253 check_infos.create (0);
1255 calculate_dominance_info (CDI_DOMINATORS);
1256 calculate_dominance_info (CDI_POST_DOMINATORS);
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 ();
1265 /* Finalise checker optimization pass. */
1266 static void
1267 chkp_opt_fini (void)
1269 chkp_fix_cfg ();
1271 free_dominance_info (CDI_POST_DOMINATORS);
1274 /* Checker optimization pass function. */
1275 static unsigned int
1276 chkp_opt_execute (void)
1278 chkp_opt_init();
1280 /* This optimization may introduce new checks
1281 and thus we put it before checks search. */
1282 chkp_optimize_string_function_calls ();
1284 chkp_gather_checks_info ();
1286 chkp_remove_excess_intersections ();
1288 chkp_remove_constant_checks ();
1290 chkp_reduce_bounds_lifetime ();
1292 chkp_release_check_info ();
1294 chkp_opt_fini ();
1296 return 0;
1299 /* Pass gate. */
1300 static bool
1301 chkp_opt_gate (void)
1303 return chkp_function_instrumented_p (cfun->decl)
1304 && (flag_chkp_optimize > 0
1305 || (flag_chkp_optimize == -1 && optimize > 0));
1308 namespace {
1310 const pass_data pass_data_chkp_opt =
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 */
1324 class pass_chkp_opt : public gimple_opt_pass
1326 public:
1327 pass_chkp_opt (gcc::context *ctxt)
1328 : gimple_opt_pass (pass_data_chkp_opt, ctxt)
1331 /* opt_pass methods: */
1332 virtual opt_pass * clone ()
1334 return new pass_chkp_opt (m_ctxt);
1337 virtual bool gate (function *)
1339 return chkp_opt_gate ();
1342 virtual unsigned int execute (function *)
1344 return chkp_opt_execute ();
1347 }; // class pass_chkp_opt
1349 } // anon namespace
1351 gimple_opt_pass *
1352 make_pass_chkp_opt (gcc::context *ctxt)
1354 return new pass_chkp_opt (ctxt);