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
chkp_pol_item_compare(const void * i1,const void * i2)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
chkp_pol_find(address_t & addr,tree var)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
chkp_extend_const(tree cst)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
chkp_add_addr_item(address_t & addr,tree cst,tree var)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
chkp_sub_addr_item(address_t & addr,tree cst,tree var)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
chkp_add_addr_addr(address_t & addr,address_t & delta)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
chkp_sub_addr_addr(address_t & addr,address_t & delta)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
chkp_mult_addr(address_t & addr,tree mult)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
chkp_is_constant_addr(const address_t & addr,int * sign)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
chkp_print_addr(const address_t & addr)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
chkp_collect_addr_value(tree ptr,address_t & res)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
chkp_collect_value(tree ptr,address_t & res)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
chkp_fill_check_info(gimple * stmt,struct check_info * ci)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
chkp_release_check_info(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
chkp_init_check_info(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
chkp_gather_checks_info(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
chkp_get_check_result(struct check_info * ci,tree bounds)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
chkp_remove_check_if_pass(struct check_info * ci)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
chkp_use_outer_bounds_if_possible(struct check_info * ci)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
chkp_remove_excess_intersections(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
chkp_remove_constant_checks(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
chkp_get_nobnd_fndecl(enum built_in_function fncode)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
chkp_get_nochk_fndecl(enum built_in_function fncode)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
chkp_optimize_string_function_calls(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
chkp_reduce_bounds_lifetime(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
chkp_opt_init(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
chkp_opt_fini(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
chkp_opt_execute(void)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
chkp_opt_gate(void)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:
pass_chkp_opt(gcc::context * ctxt)1327 pass_chkp_opt (gcc::context *ctxt)
1328 : gimple_opt_pass (pass_data_chkp_opt, ctxt)
1329 {}
1330
1331 /* opt_pass methods: */
clone()1332 virtual opt_pass * clone ()
1333 {
1334 return new pass_chkp_opt (m_ctxt);
1335 }
1336
gate(function *)1337 virtual bool gate (function *)
1338 {
1339 return chkp_opt_gate ();
1340 }
1341
execute(function *)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 *
make_pass_chkp_opt(gcc::context * ctxt)1352 make_pass_chkp_opt (gcc::context *ctxt)
1353 {
1354 return new pass_chkp_opt (ctxt);
1355 }
1356