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