gcc/
[official-gcc.git] / gcc / tree-chkp-opt.c
blob4f9d8803e3ad93f3a61beefc6cd5507be4dbeb77
1 /* Pointer Bounds Checker optimization pass.
2 Copyright (C) 2014-2015 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 "alias.h"
25 #include "symtab.h"
26 #include "options.h"
27 #include "tree.h"
28 #include "fold-const.h"
29 #include "target.h"
30 #include "tree-cfg.h"
31 #include "tree-pass.h"
32 #include "cfgloop.h"
33 #include "stringpool.h"
34 #include "tree-ssa-alias.h"
35 #include "tree-ssanames.h"
36 #include "tree-ssa-operands.h"
37 #include "tree-ssa-address.h"
38 #include "tree-ssa.h"
39 #include "predict.h"
40 #include "dominance.h"
41 #include "cfg.h"
42 #include "basic-block.h"
43 #include "tree-ssa-loop-niter.h"
44 #include "gimple-expr.h"
45 #include "gimple.h"
46 #include "tree-phinodes.h"
47 #include "gimple-ssa.h"
48 #include "ssa-iterators.h"
49 #include "gimple-pretty-print.h"
50 #include "gimple-iterator.h"
51 #include "gimplify.h"
52 #include "gimplify-me.h"
53 #include "tm.h"
54 #include "hard-reg-set.h"
55 #include "function.h"
56 #include "rtl.h"
57 #include "flags.h"
58 #include "insn-config.h"
59 #include "expmed.h"
60 #include "dojump.h"
61 #include "explow.h"
62 #include "calls.h"
63 #include "emit-rtl.h"
64 #include "varasm.h"
65 #include "stmt.h"
66 #include "expr.h"
67 #include "tree-chkp.h"
68 #include "ipa-chkp.h"
69 #include "diagnostic.h"
71 enum check_type
73 CHECK_LOWER_BOUND,
74 CHECK_UPPER_BOUND
77 struct pol_item
79 tree cst;
80 tree var;
83 struct address_t
85 vec<struct pol_item> pol;
88 /* Structure to hold check informtation. */
89 struct check_info
91 /* Type of the check. */
92 check_type type;
93 /* Address used for the check. */
94 address_t addr;
95 /* Bounds used for the check. */
96 tree bounds;
97 /* Check statement. Can be NULL for removed checks. */
98 gimple stmt;
101 /* Structure to hold checks information for BB. */
102 struct bb_checks
104 vec<struct check_info, va_heap, vl_ptr> checks;
107 static void chkp_collect_value (tree ssa_name, address_t &res);
109 #define chkp_bndmk_fndecl \
110 (targetm.builtin_chkp_function (BUILT_IN_CHKP_BNDMK))
111 #define chkp_intersect_fndecl \
112 (targetm.builtin_chkp_function (BUILT_IN_CHKP_INTERSECT))
113 #define chkp_checkl_fndecl \
114 (targetm.builtin_chkp_function (BUILT_IN_CHKP_BNDCL))
115 #define chkp_checku_fndecl \
116 (targetm.builtin_chkp_function (BUILT_IN_CHKP_BNDCU))
118 static vec<struct bb_checks, va_heap, vl_ptr> check_infos = vNULL;
120 /* Comparator for pol_item structures I1 and I2 to be used
121 to find items with equal var. Also used for polynomial
122 sorting. */
123 static int
124 chkp_pol_item_compare (const void *i1, const void *i2)
126 const struct pol_item *p1 = (const struct pol_item *)i1;
127 const struct pol_item *p2 = (const struct pol_item *)i2;
129 if (p1->var == p2->var)
130 return 0;
131 else if (p1->var > p2->var)
132 return 1;
133 else
134 return -1;
137 /* Find polynomial item in ADDR with var equal to VAR
138 and return its index. Return -1 if item was not
139 found. */
140 static int
141 chkp_pol_find (address_t &addr, tree var)
143 int left = 0;
144 int right = addr.pol.length () - 1;
145 int n;
147 while (right >= left)
149 n = (left + right) / 2;
151 if (addr.pol[n].var == var
152 || (var && addr.pol[n].var
153 && TREE_CODE (var) == ADDR_EXPR
154 && TREE_CODE (addr.pol[n].var) == ADDR_EXPR
155 && TREE_OPERAND (var, 0) == TREE_OPERAND (addr.pol[n].var, 0)))
156 return n;
157 else if (addr.pol[n].var > var)
158 right = n - 1;
159 else
160 left = n + 1;
163 return -1;
166 /* Return constant CST extended to size type. */
167 static tree
168 chkp_extend_const (tree cst)
170 if (TYPE_PRECISION (TREE_TYPE (cst)) < TYPE_PRECISION (size_type_node))
171 return build_int_cst_type (size_type_node, tree_to_shwi (cst));
173 return cst;
176 /* Add polynomial item CST * VAR to ADDR. */
177 static void
178 chkp_add_addr_item (address_t &addr, tree cst, tree var)
180 int n = chkp_pol_find (addr, var);
182 cst = chkp_extend_const (cst);
184 if (n < 0)
186 struct pol_item item;
187 item.cst = cst;
188 item.var = var;
190 addr.pol.safe_push (item);
191 addr.pol.qsort (&chkp_pol_item_compare);
193 else
195 addr.pol[n].cst = fold_build2 (PLUS_EXPR, TREE_TYPE (addr.pol[n].cst),
196 addr.pol[n].cst, cst);
197 if (TREE_CODE (addr.pol[n].cst) == INTEGER_CST
198 && integer_zerop (addr.pol[n].cst))
199 addr.pol.ordered_remove (n);
203 /* Subtract polynomial item CST * VAR from ADDR. */
204 static void
205 chkp_sub_addr_item (address_t &addr, tree cst, tree var)
207 int n = chkp_pol_find (addr, var);
209 cst = chkp_extend_const (cst);
211 if (n < 0)
213 struct pol_item item;
214 item.cst = fold_build2 (MINUS_EXPR, TREE_TYPE (cst),
215 integer_zero_node, cst);
216 item.var = var;
218 addr.pol.safe_push (item);
219 addr.pol.qsort (&chkp_pol_item_compare);
221 else
223 addr.pol[n].cst = fold_build2 (MINUS_EXPR, TREE_TYPE (addr.pol[n].cst),
224 addr.pol[n].cst, cst);
225 if (TREE_CODE (addr.pol[n].cst) == INTEGER_CST
226 && integer_zerop (addr.pol[n].cst))
227 addr.pol.ordered_remove (n);
231 /* Add address DELTA to ADDR. */
232 static void
233 chkp_add_addr_addr (address_t &addr, address_t &delta)
235 unsigned int i;
236 for (i = 0; i < delta.pol.length (); i++)
237 chkp_add_addr_item (addr, delta.pol[i].cst, delta.pol[i].var);
240 /* Subtract address DELTA from ADDR. */
241 static void
242 chkp_sub_addr_addr (address_t &addr, address_t &delta)
244 unsigned int i;
245 for (i = 0; i < delta.pol.length (); i++)
246 chkp_sub_addr_item (addr, delta.pol[i].cst, delta.pol[i].var);
249 /* Mutiply address ADDR by integer constant MULT. */
250 static void
251 chkp_mult_addr (address_t &addr, tree mult)
253 unsigned int i;
254 for (i = 0; i < addr.pol.length (); i++)
255 addr.pol[i].cst = fold_build2 (MULT_EXPR, TREE_TYPE (addr.pol[i].cst),
256 addr.pol[i].cst, mult);
259 /* Return 1 if we may prove ADDR has a constant value with
260 determined sign, which is put into *SIGN. Otherwise
261 return 0. */
262 static bool
263 chkp_is_constant_addr (const address_t &addr, int *sign)
265 *sign = 0;
267 if (addr.pol.length () == 0)
268 return true;
269 else if (addr.pol.length () > 1)
270 return false;
271 else if (addr.pol[0].var)
272 return false;
273 else if (integer_zerop (addr.pol[0].cst))
274 *sign = 0;
275 else if (tree_int_cst_sign_bit (addr.pol[0].cst))
276 *sign = -1;
277 else
278 *sign = 1;
280 return true;
283 /* Dump ADDR into dump_file. */
284 static void
285 chkp_print_addr (const address_t &addr)
287 unsigned int n = 0;
288 for (n = 0; n < addr.pol.length (); n++)
290 if (n > 0)
291 fprintf (dump_file, " + ");
293 if (addr.pol[n].var == NULL_TREE)
294 print_generic_expr (dump_file, addr.pol[n].cst, 0);
295 else
297 if (TREE_CODE (addr.pol[n].cst) != INTEGER_CST
298 || !integer_onep (addr.pol[n].cst))
300 print_generic_expr (dump_file, addr.pol[n].cst, 0);
301 fprintf (dump_file, " * ");
303 print_generic_expr (dump_file, addr.pol[n].var, 0);
308 /* Compute value of PTR and put it into address RES.
309 PTR has to be ADDR_EXPR. */
310 static void
311 chkp_collect_addr_value (tree ptr, address_t &res)
313 tree obj = TREE_OPERAND (ptr, 0);
314 address_t addr;
316 switch (TREE_CODE (obj))
318 case INDIRECT_REF:
319 chkp_collect_value (TREE_OPERAND (obj, 0), res);
320 break;
322 case MEM_REF:
323 chkp_collect_value (TREE_OPERAND (obj, 0), res);
324 addr.pol.create (0);
325 chkp_collect_value (TREE_OPERAND (obj, 1), addr);
326 chkp_add_addr_addr (res, addr);
327 addr.pol.release ();
328 break;
330 case ARRAY_REF:
331 chkp_collect_value (build_fold_addr_expr (TREE_OPERAND (obj, 0)), res);
332 addr.pol.create (0);
333 chkp_collect_value (TREE_OPERAND (obj, 1), addr);
334 chkp_mult_addr (addr, array_ref_element_size (obj));
335 chkp_add_addr_addr (res, addr);
336 addr.pol.release ();
337 break;
339 case COMPONENT_REF:
341 tree str = TREE_OPERAND (obj, 0);
342 tree field = TREE_OPERAND (obj, 1);
343 chkp_collect_value (build_fold_addr_expr (str), res);
344 addr.pol.create (0);
345 chkp_collect_value (component_ref_field_offset (obj), addr);
346 chkp_add_addr_addr (res, addr);
347 addr.pol.release ();
348 if (DECL_FIELD_BIT_OFFSET (field))
350 addr.pol.create (0);
351 chkp_collect_value (fold_build2 (TRUNC_DIV_EXPR, size_type_node,
352 DECL_FIELD_BIT_OFFSET (field),
353 size_int (BITS_PER_UNIT)),
354 addr);
355 chkp_add_addr_addr (res, addr);
356 addr.pol.release ();
359 break;
361 default:
362 chkp_add_addr_item (res, integer_one_node, ptr);
363 break;
367 /* Compute value of PTR and put it into address RES. */
368 static void
369 chkp_collect_value (tree ptr, address_t &res)
371 gimple def_stmt;
372 enum gimple_code code;
373 enum tree_code rhs_code;
374 address_t addr;
375 tree rhs1;
377 if (TREE_CODE (ptr) == INTEGER_CST)
379 chkp_add_addr_item (res, ptr, NULL);
380 return;
382 else if (TREE_CODE (ptr) == ADDR_EXPR)
384 chkp_collect_addr_value (ptr, res);
385 return;
387 else if (TREE_CODE (ptr) != SSA_NAME)
389 chkp_add_addr_item (res, integer_one_node, ptr);
390 return;
393 /* Now we handle the case when polynomial is computed
394 for SSA NAME. */
395 def_stmt = SSA_NAME_DEF_STMT (ptr);
396 code = gimple_code (def_stmt);
398 /* Currently we do not walk through statements other
399 than assignment. */
400 if (code != GIMPLE_ASSIGN)
402 chkp_add_addr_item (res, integer_one_node, ptr);
403 return;
406 rhs_code = gimple_assign_rhs_code (def_stmt);
407 rhs1 = gimple_assign_rhs1 (def_stmt);
409 switch (rhs_code)
411 case SSA_NAME:
412 case INTEGER_CST:
413 case ADDR_EXPR:
414 chkp_collect_value (rhs1, res);
415 break;
417 case PLUS_EXPR:
418 case POINTER_PLUS_EXPR:
419 chkp_collect_value (rhs1, res);
420 addr.pol.create (0);
421 chkp_collect_value (gimple_assign_rhs2 (def_stmt), addr);
422 chkp_add_addr_addr (res, addr);
423 addr.pol.release ();
424 break;
426 case MINUS_EXPR:
427 chkp_collect_value (rhs1, res);
428 addr.pol.create (0);
429 chkp_collect_value (gimple_assign_rhs2 (def_stmt), addr);
430 chkp_sub_addr_addr (res, addr);
431 addr.pol.release ();
432 break;
434 case MULT_EXPR:
435 if (TREE_CODE (rhs1) == SSA_NAME
436 && TREE_CODE (gimple_assign_rhs2 (def_stmt)) == INTEGER_CST)
438 chkp_collect_value (rhs1, res);
439 chkp_mult_addr (res, gimple_assign_rhs2 (def_stmt));
441 else if (TREE_CODE (gimple_assign_rhs2 (def_stmt)) == SSA_NAME
442 && TREE_CODE (rhs1) == INTEGER_CST)
444 chkp_collect_value (gimple_assign_rhs2 (def_stmt), res);
445 chkp_mult_addr (res, rhs1);
447 else
448 chkp_add_addr_item (res, integer_one_node, ptr);
449 break;
451 default:
452 chkp_add_addr_item (res, integer_one_node, ptr);
453 break;
457 /* Fill check_info structure *CI with information about
458 check STMT. */
459 static void
460 chkp_fill_check_info (gimple stmt, struct check_info *ci)
462 ci->addr.pol.create (0);
463 ci->bounds = gimple_call_arg (stmt, 1);
464 chkp_collect_value (gimple_call_arg (stmt, 0), ci->addr);
465 ci->type = (gimple_call_fndecl (stmt) == chkp_checkl_fndecl
466 ? CHECK_LOWER_BOUND
467 : CHECK_UPPER_BOUND);
468 ci->stmt = stmt;
471 /* Release structures holding check information
472 for current function. */
473 static void
474 chkp_release_check_info (void)
476 unsigned int n, m;
478 if (check_infos.exists ())
480 for (n = 0; n < check_infos.length (); n++)
482 for (m = 0; m < check_infos[n].checks.length (); m++)
483 if (check_infos[n].checks[m].addr.pol.exists ())
484 check_infos[n].checks[m].addr.pol.release ();
485 check_infos[n].checks.release ();
487 check_infos.release ();
491 /* Create structures to hold check information
492 for current function. */
493 static void
494 chkp_init_check_info (void)
496 struct bb_checks empty_bbc;
497 int n;
499 empty_bbc.checks = vNULL;
501 chkp_release_check_info ();
503 check_infos.create (last_basic_block_for_fn (cfun));
504 for (n = 0; n < last_basic_block_for_fn (cfun); n++)
506 check_infos.safe_push (empty_bbc);
507 check_infos.last ().checks.create (0);
511 /* Find all checks in current function and store info about them
512 in check_infos. */
513 static void
514 chkp_gather_checks_info (void)
516 basic_block bb;
517 gimple_stmt_iterator i;
519 if (dump_file && (dump_flags & TDF_DETAILS))
520 fprintf (dump_file, "Gathering information about checks...\n");
522 chkp_init_check_info ();
524 FOR_EACH_BB_FN (bb, cfun)
526 struct bb_checks *bbc = &check_infos[bb->index];
528 if (dump_file && (dump_flags & TDF_DETAILS))
529 fprintf (dump_file, "Searching checks in BB%d...\n", bb->index);
531 for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
533 gimple stmt = gsi_stmt (i);
535 if (gimple_code (stmt) != GIMPLE_CALL)
536 continue;
538 if (gimple_call_fndecl (stmt) == chkp_checkl_fndecl
539 || gimple_call_fndecl (stmt) == chkp_checku_fndecl)
541 struct check_info ci;
543 chkp_fill_check_info (stmt, &ci);
544 bbc->checks.safe_push (ci);
546 if (dump_file && (dump_flags & TDF_DETAILS))
548 fprintf (dump_file, "Adding check information:\n");
549 fprintf (dump_file, " bounds: ");
550 print_generic_expr (dump_file, ci.bounds, 0);
551 fprintf (dump_file, "\n address: ");
552 chkp_print_addr (ci.addr);
553 fprintf (dump_file, "\n check: ");
554 print_gimple_stmt (dump_file, stmt, 0, 0);
561 /* Return 1 if check CI against BOUNDS always pass,
562 -1 if check CI against BOUNDS always fails and
563 0 if we cannot compute check result. */
564 static int
565 chkp_get_check_result (struct check_info *ci, tree bounds)
567 gimple bnd_def;
568 address_t bound_val;
569 int sign, res = 0;
571 if (dump_file && (dump_flags & TDF_DETAILS))
573 fprintf (dump_file, "Trying to compute result of the check\n");
574 fprintf (dump_file, " check: ");
575 print_gimple_stmt (dump_file, ci->stmt, 0, 0);
576 fprintf (dump_file, " address: ");
577 chkp_print_addr (ci->addr);
578 fprintf (dump_file, "\n bounds: ");
579 print_generic_expr (dump_file, bounds, 0);
580 fprintf (dump_file, "\n");
583 if (TREE_CODE (bounds) != SSA_NAME)
585 if (dump_file && (dump_flags & TDF_DETAILS))
586 fprintf (dump_file, " result: bounds tree code is not ssa_name\n");
587 return 0;
590 bnd_def = SSA_NAME_DEF_STMT (bounds);
591 /* Currently we handle cases when bounds are result of bndmk
592 or loaded static bounds var. */
593 if (gimple_code (bnd_def) == GIMPLE_CALL
594 && gimple_call_fndecl (bnd_def) == chkp_bndmk_fndecl)
596 bound_val.pol.create (0);
597 chkp_collect_value (gimple_call_arg (bnd_def, 0), bound_val);
598 if (ci->type == CHECK_UPPER_BOUND)
600 address_t size_val;
601 size_val.pol.create (0);
602 chkp_collect_value (gimple_call_arg (bnd_def, 1), size_val);
603 chkp_add_addr_addr (bound_val, size_val);
604 size_val.pol.release ();
605 chkp_add_addr_item (bound_val, integer_minus_one_node, NULL);
608 else if (gimple_code (bnd_def) == GIMPLE_ASSIGN
609 && gimple_assign_rhs1 (bnd_def) == chkp_get_zero_bounds_var ())
611 if (dump_file && (dump_flags & TDF_DETAILS))
612 fprintf (dump_file, " result: always pass with zero bounds\n");
613 return 1;
615 else if (gimple_code (bnd_def) == GIMPLE_ASSIGN
616 && gimple_assign_rhs1 (bnd_def) == chkp_get_none_bounds_var ())
618 if (dump_file && (dump_flags & TDF_DETAILS))
619 fprintf (dump_file, " result: always fails with none bounds\n");
620 return -1;
622 else if (gimple_code (bnd_def) == GIMPLE_ASSIGN
623 && TREE_CODE (gimple_assign_rhs1 (bnd_def)) == VAR_DECL)
625 tree bnd_var = gimple_assign_rhs1 (bnd_def);
626 tree var;
627 tree size;
629 if (!DECL_INITIAL (bnd_var)
630 || DECL_INITIAL (bnd_var) == error_mark_node)
632 if (dump_file && (dump_flags & TDF_DETAILS))
633 fprintf (dump_file, " result: cannot compute bounds\n");
634 return 0;
637 gcc_assert (TREE_CODE (DECL_INITIAL (bnd_var)) == ADDR_EXPR);
638 var = TREE_OPERAND (DECL_INITIAL (bnd_var), 0);
640 bound_val.pol.create (0);
641 chkp_collect_value (DECL_INITIAL (bnd_var), bound_val);
642 if (ci->type == CHECK_UPPER_BOUND)
644 if (TREE_CODE (var) == VAR_DECL)
646 if (DECL_SIZE (var)
647 && !chkp_variable_size_type (TREE_TYPE (var)))
648 size = DECL_SIZE_UNIT (var);
649 else
651 if (dump_file && (dump_flags & TDF_DETAILS))
652 fprintf (dump_file, " result: cannot compute bounds\n");
653 return 0;
656 else
658 gcc_assert (TREE_CODE (var) == STRING_CST);
659 size = build_int_cst (size_type_node,
660 TREE_STRING_LENGTH (var));
663 address_t size_val;
664 size_val.pol.create (0);
665 chkp_collect_value (size, size_val);
666 chkp_add_addr_addr (bound_val, size_val);
667 size_val.pol.release ();
668 chkp_add_addr_item (bound_val, integer_minus_one_node, NULL);
671 else
673 if (dump_file && (dump_flags & TDF_DETAILS))
674 fprintf (dump_file, " result: cannot compute bounds\n");
675 return 0;
678 if (dump_file && (dump_flags & TDF_DETAILS))
680 fprintf (dump_file, " bound value: ");
681 chkp_print_addr (bound_val);
682 fprintf (dump_file, "\n");
685 chkp_sub_addr_addr (bound_val, ci->addr);
687 if (!chkp_is_constant_addr (bound_val, &sign))
689 if (dump_file && (dump_flags & TDF_DETAILS))
690 fprintf (dump_file, " result: cannot compute result\n");
692 res = 0;
694 else if (sign == 0
695 || (ci->type == CHECK_UPPER_BOUND && sign > 0)
696 || (ci->type == CHECK_LOWER_BOUND && sign < 0))
698 if (dump_file && (dump_flags & TDF_DETAILS))
699 fprintf (dump_file, " result: always pass\n");
701 res = 1;
703 else
705 if (dump_file && (dump_flags & TDF_DETAILS))
706 fprintf (dump_file, " result: always fail\n");
708 res = -1;
711 bound_val.pol.release ();
713 return res;
716 /* Try to compare bounds value and address value
717 used in the check CI. If we can prove that check
718 always pass then remove it. */
719 static void
720 chkp_remove_check_if_pass (struct check_info *ci)
722 int result = 0;
724 if (dump_file && (dump_flags & TDF_DETAILS))
726 fprintf (dump_file, "Trying to remove check: ");
727 print_gimple_stmt (dump_file, ci->stmt, 0, 0);
730 result = chkp_get_check_result (ci, ci->bounds);
732 if (result == 1)
734 gimple_stmt_iterator i = gsi_for_stmt (ci->stmt);
736 if (dump_file && (dump_flags & TDF_DETAILS))
737 fprintf (dump_file, " action: delete check (always pass)\n");
739 gsi_remove (&i, true);
740 unlink_stmt_vdef (ci->stmt);
741 release_defs (ci->stmt);
742 ci->stmt = NULL;
744 else if (result == -1)
746 if (dump_file && (dump_flags & TDF_DETAILS))
747 fprintf (dump_file, " action: keep check (always fail)\n");
748 warning_at (gimple_location (ci->stmt), OPT_Wchkp,
749 "memory access check always fail");
751 else if (result == 0)
753 if (dump_file && (dump_flags & TDF_DETAILS))
754 fprintf (dump_file, " action: keep check (cannot compute result)\n");
758 /* For bounds used in CI check if bounds are produced by
759 intersection and we may use outer bounds instead. If
760 transformation is possible then fix check statement and
761 recompute its info. */
762 static void
763 chkp_use_outer_bounds_if_possible (struct check_info *ci)
765 gimple bnd_def;
766 tree bnd1, bnd2, bnd_res = NULL;
767 int check_res1, check_res2;
769 if (TREE_CODE (ci->bounds) != SSA_NAME)
770 return;
772 bnd_def = SSA_NAME_DEF_STMT (ci->bounds);
773 if (gimple_code (bnd_def) != GIMPLE_CALL
774 || gimple_call_fndecl (bnd_def) != chkp_intersect_fndecl)
775 return;
777 if (dump_file && (dump_flags & TDF_DETAILS))
779 fprintf (dump_file, "Check if bounds intersection is redundant: \n");
780 fprintf (dump_file, " check: ");
781 print_gimple_stmt (dump_file, ci->stmt, 0, 0);
782 fprintf (dump_file, " intersection: ");
783 print_gimple_stmt (dump_file, bnd_def, 0, 0);
784 fprintf (dump_file, "\n");
787 bnd1 = gimple_call_arg (bnd_def, 0);
788 bnd2 = gimple_call_arg (bnd_def, 1);
790 check_res1 = chkp_get_check_result (ci, bnd1);
791 check_res2 = chkp_get_check_result (ci, bnd2);
792 if (check_res1 == 1)
793 bnd_res = bnd2;
794 else if (check_res1 == -1)
795 bnd_res = bnd1;
796 else if (check_res2 == 1)
797 bnd_res = bnd1;
798 else if (check_res2 == -1)
799 bnd_res = bnd2;
801 if (bnd_res)
803 if (dump_file && (dump_flags & TDF_DETAILS))
805 fprintf (dump_file, " action: use ");
806 print_generic_expr (dump_file, bnd2, 0);
807 fprintf (dump_file, " instead of ");
808 print_generic_expr (dump_file, ci->bounds, 0);
809 fprintf (dump_file, "\n");
812 ci->bounds = bnd_res;
813 gimple_call_set_arg (ci->stmt, 1, bnd_res);
814 update_stmt (ci->stmt);
815 chkp_fill_check_info (ci->stmt, ci);
819 /* Try to find checks whose bounds were produced by intersection
820 which does not affect check result. In such check outer bounds
821 are used instead. It allows to remove excess intersections
822 and helps to compare checks. */
823 static void
824 chkp_remove_excess_intersections (void)
826 basic_block bb;
828 if (dump_file && (dump_flags & TDF_DETAILS))
829 fprintf (dump_file, "Searching for redundant bounds intersections...\n");
831 FOR_EACH_BB_FN (bb, cfun)
833 struct bb_checks *bbc = &check_infos[bb->index];
834 unsigned int no;
836 /* Iterate through all found checks in BB. */
837 for (no = 0; no < bbc->checks.length (); no++)
838 if (bbc->checks[no].stmt)
839 chkp_use_outer_bounds_if_possible (&bbc->checks[no]);
843 /* Try to remove all checks which are known to alwyas pass. */
844 static void
845 chkp_remove_constant_checks (void)
847 basic_block bb;
849 if (dump_file && (dump_flags & TDF_DETAILS))
850 fprintf (dump_file, "Searching for redundant checks...\n");
852 FOR_EACH_BB_FN (bb, cfun)
854 struct bb_checks *bbc = &check_infos[bb->index];
855 unsigned int no;
857 /* Iterate through all found checks in BB. */
858 for (no = 0; no < bbc->checks.length (); no++)
859 if (bbc->checks[no].stmt)
860 chkp_remove_check_if_pass (&bbc->checks[no]);
864 /* Return fast version of string function FNCODE. */
865 static tree
866 chkp_get_nobnd_fndecl (enum built_in_function fncode)
868 /* Check if we are allowed to use fast string functions. */
869 if (!flag_chkp_use_fast_string_functions)
870 return NULL_TREE;
872 tree fndecl = NULL_TREE;
874 switch (fncode)
876 case BUILT_IN_MEMCPY_CHKP:
877 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMCPY_NOBND);
878 break;
880 case BUILT_IN_MEMPCPY_CHKP:
881 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMPCPY_NOBND);
882 break;
884 case BUILT_IN_MEMMOVE_CHKP:
885 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMMOVE_NOBND);
886 break;
888 case BUILT_IN_MEMSET_CHKP:
889 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMSET_NOBND);
890 break;
892 case BUILT_IN_CHKP_MEMCPY_NOCHK_CHKP:
893 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMCPY_NOBND_NOCHK);
894 break;
896 case BUILT_IN_CHKP_MEMPCPY_NOCHK_CHKP:
897 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMPCPY_NOBND_NOCHK);
898 break;
900 case BUILT_IN_CHKP_MEMMOVE_NOCHK_CHKP:
901 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMMOVE_NOBND_NOCHK);
902 break;
904 case BUILT_IN_CHKP_MEMSET_NOCHK_CHKP:
905 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMSET_NOBND_NOCHK);
906 break;
908 default:
909 break;
912 if (fndecl)
913 fndecl = chkp_maybe_clone_builtin_fndecl (fndecl);
915 return fndecl;
919 /* Return no-check version of string function FNCODE. */
920 static tree
921 chkp_get_nochk_fndecl (enum built_in_function fncode)
923 /* Check if we are allowed to use fast string functions. */
924 if (!flag_chkp_use_nochk_string_functions)
925 return NULL_TREE;
927 tree fndecl = NULL_TREE;
929 switch (fncode)
931 case BUILT_IN_MEMCPY_CHKP:
932 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMCPY_NOCHK);
933 break;
935 case BUILT_IN_MEMPCPY_CHKP:
936 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMPCPY_NOCHK);
937 break;
939 case BUILT_IN_MEMMOVE_CHKP:
940 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMMOVE_NOCHK);
941 break;
943 case BUILT_IN_MEMSET_CHKP:
944 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMSET_NOCHK);
945 break;
947 case BUILT_IN_CHKP_MEMCPY_NOBND_CHKP:
948 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMCPY_NOBND_NOCHK);
949 break;
951 case BUILT_IN_CHKP_MEMPCPY_NOBND_CHKP:
952 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMPCPY_NOBND_NOCHK);
953 break;
955 case BUILT_IN_CHKP_MEMMOVE_NOBND_CHKP:
956 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMMOVE_NOBND_NOCHK);
957 break;
959 case BUILT_IN_CHKP_MEMSET_NOBND_CHKP:
960 fndecl = builtin_decl_implicit (BUILT_IN_CHKP_MEMSET_NOBND_NOCHK);
961 break;
963 default:
964 break;
967 if (fndecl)
968 fndecl = chkp_maybe_clone_builtin_fndecl (fndecl);
970 return fndecl;
973 /* Find memcpy, mempcpy, memmove and memset calls, perform
974 checks before call and then call no_chk version of
975 functions. We do it on O2 to enable inlining of these
976 functions during expand.
978 Also try to find memcpy, mempcpy, memmove and memset calls
979 which are known to not write pointers to memory and use
980 faster function versions for them. */
981 static void
982 chkp_optimize_string_function_calls (void)
984 basic_block bb;
986 if (dump_file && (dump_flags & TDF_DETAILS))
987 fprintf (dump_file, "Searching for replaceable string function calls...\n");
989 FOR_EACH_BB_FN (bb, cfun)
991 gimple_stmt_iterator i;
993 for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
995 gimple stmt = gsi_stmt (i);
996 tree fndecl;
998 if (gimple_code (stmt) != GIMPLE_CALL
999 || !gimple_call_with_bounds_p (stmt))
1000 continue;
1002 fndecl = gimple_call_fndecl (stmt);
1004 if (!fndecl || DECL_BUILT_IN_CLASS (fndecl) != BUILT_IN_NORMAL)
1005 continue;
1007 if (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMCPY_CHKP
1008 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMPCPY_CHKP
1009 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMMOVE_CHKP
1010 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMSET_CHKP)
1012 tree dst = gimple_call_arg (stmt, 0);
1013 tree dst_bnd = gimple_call_arg (stmt, 1);
1014 bool is_memset = DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMSET_CHKP;
1015 tree size = gimple_call_arg (stmt, is_memset ? 3 : 4);
1016 tree fndecl_nochk;
1017 gimple_stmt_iterator j;
1018 basic_block check_bb;
1019 address_t size_val;
1020 int sign;
1021 bool known;
1023 /* We may replace call with corresponding __chkp_*_nobnd
1024 call in case destination pointer base type is not
1025 void or pointer. */
1026 if (POINTER_TYPE_P (TREE_TYPE (dst))
1027 && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (dst)))
1028 && !chkp_type_has_pointer (TREE_TYPE (TREE_TYPE (dst))))
1030 tree fndecl_nobnd
1031 = chkp_get_nobnd_fndecl (DECL_FUNCTION_CODE (fndecl));
1033 if (fndecl_nobnd)
1034 fndecl = fndecl_nobnd;
1037 fndecl_nochk = chkp_get_nochk_fndecl (DECL_FUNCTION_CODE (fndecl));
1039 if (fndecl_nochk)
1040 fndecl = fndecl_nochk;
1042 if (fndecl != gimple_call_fndecl (stmt))
1044 if (dump_file && (dump_flags & TDF_DETAILS))
1046 fprintf (dump_file, "Replacing call: ");
1047 print_gimple_stmt (dump_file, stmt, 0,
1048 TDF_VOPS|TDF_MEMSYMS);
1051 gimple_call_set_fndecl (stmt, fndecl);
1053 if (dump_file && (dump_flags & TDF_DETAILS))
1055 fprintf (dump_file, "With a new call: ");
1056 print_gimple_stmt (dump_file, stmt, 0,
1057 TDF_VOPS|TDF_MEMSYMS);
1061 /* If there is no nochk version of function then
1062 do nothing. Otherwise insert checks before
1063 the call. */
1064 if (!fndecl_nochk)
1065 continue;
1067 /* If size passed to call is known and > 0
1068 then we may insert checks unconditionally. */
1069 size_val.pol.create (0);
1070 chkp_collect_value (size, size_val);
1071 known = chkp_is_constant_addr (size_val, &sign);
1072 size_val.pol.release ();
1074 /* If we are not sure size is not zero then we have
1075 to perform runtime check for size and perform
1076 checks only when size is not zero. */
1077 if (!known)
1079 gimple check = gimple_build_cond (NE_EXPR,
1080 size,
1081 size_zero_node,
1082 NULL_TREE,
1083 NULL_TREE);
1085 /* Split block before string function call. */
1086 gsi_prev (&i);
1087 check_bb = insert_cond_bb (bb, gsi_stmt (i), check);
1089 /* Set position for checks. */
1090 j = gsi_last_bb (check_bb);
1092 /* The block was splitted and therefore we
1093 need to set iterator to its end. */
1094 i = gsi_last_bb (bb);
1096 /* If size is known to be zero then no checks
1097 should be performed. */
1098 else if (!sign)
1099 continue;
1100 else
1101 j = i;
1103 size = size_binop (MINUS_EXPR, size, size_one_node);
1104 if (!is_memset)
1106 tree src = gimple_call_arg (stmt, 2);
1107 tree src_bnd = gimple_call_arg (stmt, 3);
1109 chkp_check_mem_access (src, fold_build_pointer_plus (src, size),
1110 src_bnd, j, gimple_location (stmt),
1111 integer_zero_node);
1114 chkp_check_mem_access (dst, fold_build_pointer_plus (dst, size),
1115 dst_bnd, j, gimple_location (stmt),
1116 integer_one_node);
1123 /* Intrumentation pass inserts most of bounds creation code
1124 in the header of the function. We want to move bounds
1125 creation closer to bounds usage to reduce bounds lifetime.
1126 We also try to avoid bounds creation code on paths where
1127 bounds are not used. */
1128 static void
1129 chkp_reduce_bounds_lifetime (void)
1131 basic_block bb = FALLTHRU_EDGE (ENTRY_BLOCK_PTR_FOR_FN (cfun))->dest;
1132 gimple_stmt_iterator i;
1134 for (i = gsi_start_bb (bb); !gsi_end_p (i); )
1136 gimple dom_use, use_stmt, stmt = gsi_stmt (i);
1137 basic_block dom_bb;
1138 ssa_op_iter iter;
1139 imm_use_iterator use_iter;
1140 use_operand_p use_p;
1141 tree op;
1142 bool want_move = false;
1143 bool deps = false;
1145 if (gimple_code (stmt) == GIMPLE_CALL
1146 && gimple_call_fndecl (stmt) == chkp_bndmk_fndecl)
1147 want_move = true;
1149 if (gimple_code (stmt) == GIMPLE_ASSIGN
1150 && POINTER_BOUNDS_P (gimple_assign_lhs (stmt))
1151 && gimple_assign_rhs_code (stmt) == VAR_DECL)
1152 want_move = true;
1154 if (!want_move)
1156 gsi_next (&i);
1157 continue;
1160 /* Check we do not increase other values lifetime. */
1161 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
1163 op = USE_FROM_PTR (use_p);
1165 if (TREE_CODE (op) == SSA_NAME
1166 && gimple_code (SSA_NAME_DEF_STMT (op)) != GIMPLE_NOP)
1168 deps = true;
1169 break;
1173 if (deps)
1175 gsi_next (&i);
1176 continue;
1179 /* Check all usages of bounds. */
1180 if (gimple_code (stmt) == GIMPLE_CALL)
1181 op = gimple_call_lhs (stmt);
1182 else
1184 gcc_assert (gimple_code (stmt) == GIMPLE_ASSIGN);
1185 op = gimple_assign_lhs (stmt);
1188 dom_use = NULL;
1189 dom_bb = NULL;
1191 FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, op)
1193 if (is_gimple_debug (use_stmt))
1194 continue;
1196 if (dom_bb &&
1197 dominated_by_p (CDI_DOMINATORS,
1198 dom_bb, gimple_bb (use_stmt)))
1200 dom_use = use_stmt;
1201 dom_bb = NULL;
1203 else if (dom_bb)
1204 dom_bb = nearest_common_dominator (CDI_DOMINATORS, dom_bb,
1205 gimple_bb (use_stmt));
1206 else if (!dom_use)
1207 dom_use = use_stmt;
1208 else if (stmt_dominates_stmt_p (use_stmt, dom_use))
1209 dom_use = use_stmt;
1210 else if (!stmt_dominates_stmt_p (dom_use, use_stmt)
1211 /* If dom_use and use_stmt are PHI nodes in one BB
1212 then it is OK to keep any of them as dom_use.
1213 stmt_dominates_stmt_p returns 0 for such
1214 combination, so check it here manually. */
1215 && (gimple_code (dom_use) != GIMPLE_PHI
1216 || gimple_code (use_stmt) != GIMPLE_PHI
1217 || gimple_bb (use_stmt) != gimple_bb (dom_use))
1220 dom_bb = nearest_common_dominator (CDI_DOMINATORS,
1221 gimple_bb (use_stmt),
1222 gimple_bb (dom_use));
1223 dom_use = NULL;
1227 /* In case there is a single use, just move bounds
1228 creation to the use. */
1229 if (dom_use || dom_bb)
1231 if (dump_file && (dump_flags & TDF_DETAILS))
1233 fprintf (dump_file, "Moving creation of ");
1234 print_generic_expr (dump_file, op, 0);
1235 fprintf (dump_file, " down to its use.\n");
1238 if (dom_use && gimple_code (dom_use) == GIMPLE_PHI)
1240 dom_bb = get_immediate_dominator (CDI_DOMINATORS,
1241 gimple_bb (dom_use));
1242 dom_use = NULL;
1245 if (dom_bb == bb
1246 || (dom_use && gimple_bb (dom_use) == bb))
1248 if (dump_file && (dump_flags & TDF_DETAILS))
1249 fprintf (dump_file, "Cannot move statement bacause there is no "
1250 "suitable dominator block other than entry block.\n");
1252 gsi_next (&i);
1254 else
1256 if (dom_bb)
1258 gimple_stmt_iterator last = gsi_last_bb (dom_bb);
1259 if (!gsi_end_p (last) && stmt_ends_bb_p (gsi_stmt (last)))
1260 gsi_move_before (&i, &last);
1261 else
1262 gsi_move_after (&i, &last);
1264 else
1266 gimple_stmt_iterator gsi = gsi_for_stmt (dom_use);
1267 gsi_move_before (&i, &gsi);
1270 update_stmt (stmt);
1273 else
1274 gsi_next (&i);
1278 /* Initilize checker optimization pass. */
1279 static void
1280 chkp_opt_init (void)
1282 check_infos.create (0);
1284 calculate_dominance_info (CDI_DOMINATORS);
1285 calculate_dominance_info (CDI_POST_DOMINATORS);
1287 /* With LTO constant bounds vars may be not initialized by now.
1288 Get constant bounds vars to handle their assignments during
1289 optimizations. */
1290 chkp_get_zero_bounds_var ();
1291 chkp_get_none_bounds_var ();
1294 /* Finalise checker optimization pass. */
1295 static void
1296 chkp_opt_fini (void)
1298 chkp_fix_cfg ();
1301 /* Checker optimization pass function. */
1302 static unsigned int
1303 chkp_opt_execute (void)
1305 chkp_opt_init();
1307 /* This optimization may introduce new checks
1308 and thus we put it before checks search. */
1309 chkp_optimize_string_function_calls ();
1311 chkp_gather_checks_info ();
1313 chkp_remove_excess_intersections ();
1315 chkp_remove_constant_checks ();
1317 chkp_reduce_bounds_lifetime ();
1319 chkp_release_check_info ();
1321 chkp_opt_fini ();
1323 return 0;
1326 /* Pass gate. */
1327 static bool
1328 chkp_opt_gate (void)
1330 return chkp_function_instrumented_p (cfun->decl)
1331 && (flag_chkp_optimize > 0
1332 || (flag_chkp_optimize == -1 && optimize > 0));
1335 namespace {
1337 const pass_data pass_data_chkp_opt =
1339 GIMPLE_PASS, /* type */
1340 "chkpopt", /* name */
1341 OPTGROUP_NONE, /* optinfo_flags */
1342 TV_NONE, /* tv_id */
1343 PROP_ssa | PROP_cfg, /* properties_required */
1344 0, /* properties_provided */
1345 0, /* properties_destroyed */
1346 0, /* todo_flags_start */
1347 TODO_verify_il
1348 | TODO_update_ssa /* todo_flags_finish */
1351 class pass_chkp_opt : public gimple_opt_pass
1353 public:
1354 pass_chkp_opt (gcc::context *ctxt)
1355 : gimple_opt_pass (pass_data_chkp_opt, ctxt)
1358 /* opt_pass methods: */
1359 virtual opt_pass * clone ()
1361 return new pass_chkp_opt (m_ctxt);
1364 virtual bool gate (function *)
1366 return chkp_opt_gate ();
1369 virtual unsigned int execute (function *)
1371 return chkp_opt_execute ();
1374 }; // class pass_chkp_opt
1376 } // anon namespace
1378 gimple_opt_pass *
1379 make_pass_chkp_opt (gcc::context *ctxt)
1381 return new pass_chkp_opt (ctxt);