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