1/* IPA predicates.
2 Copyright (C) 2003-2024 Free Software Foundation, Inc.
3 Contributed by Jan Hubicka
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"
24#include "backend.h"
25#include "tree.h"
26#include "cgraph.h"
27#include "tree-vrp.h"
28#include "alloc-pool.h"
29#include "symbol-summary.h"
30#include "sreal.h"
31#include "ipa-cp.h"
32#include "ipa-prop.h"
33#include "ipa-fnsummary.h"
34#include "real.h"
35#include "fold-const.h"
36#include "tree-pretty-print.h"
37#include "gimple.h"
38#include "gimplify.h"
39#include "data-streamer.h"
40
41
42/* Check whether two set of operations have same effects. */
43static bool
44expr_eval_ops_equal_p (expr_eval_ops ops1, expr_eval_ops ops2)
45{
46 if (ops1)
47 {
48 if (!ops2 || ops1->length () != ops2->length ())
49 return false;
50
51 for (unsigned i = 0; i < ops1->length (); i++)
52 {
53 expr_eval_op &op1 = (*ops1)[i];
54 expr_eval_op &op2 = (*ops2)[i];
55
56 if (op1.code != op2.code
57 || op1.index != op2.index
58 || !vrp_operand_equal_p (op1.val[0], op2.val[0])
59 || !vrp_operand_equal_p (op1.val[1], op2.val[1])
60 || !types_compatible_p (type1: op1.type, type2: op2.type))
61 return false;
62 }
63 return true;
64 }
65 return !ops2;
66}
67
68/* Add clause CLAUSE into the predicate P.
69 When CONDITIONS is NULL do not perform checking whether NEW_CLAUSE
70 is obviously true. This is useful only when NEW_CLAUSE is known to be
71 sane. */
72
73void
74ipa_predicate::add_clause (conditions conditions, clause_t new_clause)
75{
76 int i;
77 int i2;
78 int insert_here = -1;
79 int c1, c2;
80
81 /* True clause. */
82 if (!new_clause)
83 return;
84
85 /* False clause makes the whole predicate false. Kill the other variants. */
86 if (new_clause == (1 << ipa_predicate::false_condition))
87 {
88 *this = false;
89 return;
90 }
91 if (*this == false)
92 return;
93
94 /* No one should be silly enough to add false into nontrivial clauses. */
95 gcc_checking_assert (!(new_clause & (1 << ipa_predicate::false_condition)));
96
97 /* Look where to insert the new_clause. At the same time prune out
98 new_clauses of P that are implied by the new new_clause and thus
99 redundant. */
100 for (i = 0, i2 = 0; i <= max_clauses; i++)
101 {
102 m_clause[i2] = m_clause[i];
103
104 if (!m_clause[i])
105 break;
106
107 /* If m_clause[i] implies new_clause, there is nothing to add. */
108 if ((m_clause[i] & new_clause) == m_clause[i])
109 {
110 /* We had nothing to add, none of clauses should've become
111 redundant. */
112 gcc_checking_assert (i == i2);
113 return;
114 }
115
116 if (m_clause[i] < new_clause && insert_here < 0)
117 insert_here = i2;
118
119 /* If new_clause implies clause[i], then clause[i] becomes redundant.
120 Otherwise the clause[i] has to stay. */
121 if ((m_clause[i] & new_clause) != new_clause)
122 i2++;
123 }
124
125 /* Look for clauses that are obviously true. I.e.
126 op0 == 5 || op0 != 5. */
127 if (conditions)
128 for (c1 = ipa_predicate::first_dynamic_condition;
129 c1 < num_conditions; c1++)
130 {
131 condition *cc1;
132 if (!(new_clause & (1 << c1)))
133 continue;
134 cc1 = &(*conditions)[c1 - ipa_predicate::first_dynamic_condition];
135 /* We have no way to represent !changed and !is_not_constant
136 and thus there is no point for looking for them. */
137 if (cc1->code == changed || cc1->code == is_not_constant || cc1->code == not_sra_candidate)
138 continue;
139 for (c2 = c1 + 1; c2 < num_conditions; c2++)
140 if (new_clause & (1 << c2))
141 {
142 condition *cc2 =
143 &(*conditions)[c2 - ipa_predicate::first_dynamic_condition];
144 if (cc1->operand_num == cc2->operand_num
145 && vrp_operand_equal_p (cc1->val, cc2->val)
146 && cc2->code != is_not_constant
147 && cc2->code != not_sra_candidate
148 && cc2->code != changed
149 && expr_eval_ops_equal_p (ops1: cc1->param_ops, ops2: cc2->param_ops)
150 && cc2->agg_contents == cc1->agg_contents
151 && cc2->by_ref == cc1->by_ref
152 && types_compatible_p (type1: cc2->type, type2: cc1->type)
153 && cc1->code == invert_tree_comparison (cc2->code,
154 HONOR_NANS (cc1->val)))
155 return;
156 }
157 }
158
159
160 /* We run out of variants. Be conservative in positive direction. */
161 if (i2 == max_clauses)
162 return;
163 /* Keep clauses in decreasing order. This makes equivalence testing easy. */
164 m_clause[i2 + 1] = 0;
165 if (insert_here >= 0)
166 for (; i2 > insert_here; i2--)
167 m_clause[i2] = m_clause[i2 - 1];
168 else
169 insert_here = i2;
170 m_clause[insert_here] = new_clause;
171}
172
173
174/* Do THIS &= P. */
175
176ipa_predicate &
177ipa_predicate::operator &= (const ipa_predicate &p)
178{
179 /* Avoid busy work. */
180 if (p == false || *this == true)
181 {
182 *this = p;
183 return *this;
184 }
185 if (*this == false || p == true || this == &p)
186 return *this;
187
188 int i;
189
190 /* See how far ipa_predicates match. */
191 for (i = 0; m_clause[i] && m_clause[i] == p.m_clause[i]; i++)
192 {
193 gcc_checking_assert (i < max_clauses);
194 }
195
196 /* Combine the ipa_predicates rest. */
197 for (; p.m_clause[i]; i++)
198 {
199 gcc_checking_assert (i < max_clauses);
200 add_clause (NULL, new_clause: p.m_clause[i]);
201 }
202 return *this;
203}
204
205
206
207/* Return THIS | P2. */
208
209ipa_predicate
210ipa_predicate::or_with (conditions conditions,
211 const ipa_predicate &p) const
212{
213 /* Avoid busy work. */
214 if (p == false || *this == true || *this == p)
215 return *this;
216 if (*this == false || p == true)
217 return p;
218
219 /* OK, combine the predicates. */
220 ipa_predicate out = true;
221
222 for (int i = 0; m_clause[i]; i++)
223 for (int j = 0; p.m_clause[j]; j++)
224 {
225 gcc_checking_assert (i < max_clauses && j < max_clauses);
226 out.add_clause (conditions, new_clause: m_clause[i] | p.m_clause[j]);
227 }
228 return out;
229}
230
231
232/* Having partial truth assignment in POSSIBLE_TRUTHS, return false
233 if predicate P is known to be false. */
234
235bool
236ipa_predicate::evaluate (clause_t possible_truths) const
237{
238 int i;
239
240 /* True remains true. */
241 if (*this == true)
242 return true;
243
244 gcc_assert (!(possible_truths & (1 << ipa_predicate::false_condition)));
245
246 /* See if we can find clause we can disprove. */
247 for (i = 0; m_clause[i]; i++)
248 {
249 gcc_checking_assert (i < max_clauses);
250 if (!(m_clause[i] & possible_truths))
251 return false;
252 }
253 return true;
254}
255
256/* Return the probability in range 0...REG_BR_PROB_BASE that the predicated
257 instruction will be recomputed per invocation of the inlined call. */
258
259int
260ipa_predicate::probability (conditions conds,
261 clause_t possible_truths,
262 vec<inline_param_summary> inline_param_summary) const
263{
264 int i;
265 int combined_prob = REG_BR_PROB_BASE;
266
267 /* True remains true. */
268 if (*this == true)
269 return REG_BR_PROB_BASE;
270
271 if (*this == false)
272 return 0;
273
274 gcc_assert (!(possible_truths & (1 << ipa_predicate::false_condition)));
275
276 /* See if we can find clause we can disprove. */
277 for (i = 0; m_clause[i]; i++)
278 {
279 gcc_checking_assert (i < max_clauses);
280 if (!(m_clause[i] & possible_truths))
281 return 0;
282 else
283 {
284 int this_prob = 0;
285 int i2;
286 if (!inline_param_summary.exists ())
287 return REG_BR_PROB_BASE;
288 for (i2 = 0; i2 < num_conditions; i2++)
289 if ((m_clause[i] & possible_truths) & (1 << i2))
290 {
291 if (i2 >= ipa_predicate::first_dynamic_condition)
292 {
293 condition *c =
294 &(*conds)[i2 - ipa_predicate::first_dynamic_condition];
295 if (c->code == ipa_predicate::changed
296 && (c->operand_num <
297 (int) inline_param_summary.length ()))
298 {
299 int iprob =
300 inline_param_summary[c->operand_num].change_prob;
301 this_prob = MAX (this_prob, iprob);
302 }
303 else
304 this_prob = REG_BR_PROB_BASE;
305 }
306 else
307 this_prob = REG_BR_PROB_BASE;
308 }
309 combined_prob = MIN (this_prob, combined_prob);
310 if (!combined_prob)
311 return 0;
312 }
313 }
314 return combined_prob;
315}
316
317
318/* Dump conditional COND. */
319
320void
321dump_condition (FILE *f, conditions conditions, int cond)
322{
323 condition *c;
324 if (cond == ipa_predicate::false_condition)
325 fprintf (stream: f, format: "false");
326 else if (cond == ipa_predicate::not_inlined_condition)
327 fprintf (stream: f, format: "not inlined");
328 else
329 {
330 c = &(*conditions)[cond - ipa_predicate::first_dynamic_condition];
331 fprintf (stream: f, format: "op%i", c->operand_num);
332 if (c->agg_contents)
333 fprintf (stream: f, format: "[%soffset: " HOST_WIDE_INT_PRINT_DEC "]",
334 c->by_ref ? "ref " : "", c->offset);
335
336 for (unsigned i = 0; i < vec_safe_length (v: c->param_ops); i++)
337 {
338 expr_eval_op &op = (*(c->param_ops))[i];
339 const char *op_name = op_symbol_code (op.code);
340
341 if (op_name == op_symbol_code (ERROR_MARK))
342 op_name = get_tree_code_name (op.code);
343
344 fprintf (stream: f, format: ",(");
345
346 if (!op.val[0])
347 {
348 switch (op.code)
349 {
350 case FLOAT_EXPR:
351 case FIX_TRUNC_EXPR:
352 case FIXED_CONVERT_EXPR:
353 case VIEW_CONVERT_EXPR:
354 CASE_CONVERT:
355 if (op.code == VIEW_CONVERT_EXPR)
356 fprintf (stream: f, format: "VCE");
357 fprintf (stream: f, format: "(");
358 print_generic_expr (f, op.type);
359 fprintf (stream: f, format: ")" );
360 break;
361
362 default:
363 fprintf (stream: f, format: "%s", op_name);
364 }
365 fprintf (stream: f, format: " #");
366 }
367 else if (!op.val[1])
368 {
369 if (op.index)
370 {
371 print_generic_expr (f, op.val[0]);
372 fprintf (stream: f, format: " %s #", op_name);
373 }
374 else
375 {
376 fprintf (stream: f, format: "# %s ", op_name);
377 print_generic_expr (f, op.val[0]);
378 }
379 }
380 else
381 {
382 fprintf (stream: f, format: "%s ", op_name);
383 switch (op.index)
384 {
385 case 0:
386 fprintf (stream: f, format: "#, ");
387 print_generic_expr (f, op.val[0]);
388 fprintf (stream: f, format: ", ");
389 print_generic_expr (f, op.val[1]);
390 break;
391
392 case 1:
393 print_generic_expr (f, op.val[0]);
394 fprintf (stream: f, format: ", #, ");
395 print_generic_expr (f, op.val[1]);
396 break;
397
398 case 2:
399 print_generic_expr (f, op.val[0]);
400 fprintf (stream: f, format: ", ");
401 print_generic_expr (f, op.val[1]);
402 fprintf (stream: f, format: ", #");
403 break;
404
405 default:
406 fprintf (stream: f, format: "*, *, *");
407 }
408 }
409 fprintf (stream: f, format: ")");
410 }
411
412 if (c->code == ipa_predicate::is_not_constant)
413 {
414 fprintf (stream: f, format: " not constant");
415 return;
416 }
417 if (c->code == ipa_predicate::changed)
418 {
419 fprintf (stream: f, format: " changed");
420 return;
421 }
422 if (c->code == ipa_predicate::not_sra_candidate)
423 {
424 fprintf (stream: f, format: " not sra candidate");
425 return;
426 }
427 fprintf (stream: f, format: " %s ", op_symbol_code (c->code));
428 print_generic_expr (f, c->val);
429 }
430}
431
432
433/* Dump clause CLAUSE. */
434
435static void
436dump_clause (FILE *f, conditions conds, clause_t clause)
437{
438 int i;
439 bool found = false;
440 fprintf (stream: f, format: "(");
441 if (!clause)
442 fprintf (stream: f, format: "true");
443 for (i = 0; i < ipa_predicate::num_conditions; i++)
444 if (clause & (1 << i))
445 {
446 if (found)
447 fprintf (stream: f, format: " || ");
448 found = true;
449 dump_condition (f, conditions: conds, cond: i);
450 }
451 fprintf (stream: f, format: ")");
452}
453
454
455/* Dump THIS to F. CONDS a vector of conditions used when evaluating
456 ipa_predicates. When NL is true new line is output at the end of dump. */
457
458void
459ipa_predicate::dump (FILE *f, conditions conds, bool nl) const
460{
461 int i;
462 if (*this == true)
463 dump_clause (f, conds, clause: 0);
464 else
465 for (i = 0; m_clause[i]; i++)
466 {
467 if (i)
468 fprintf (stream: f, format: " && ");
469 dump_clause (f, conds, clause: m_clause[i]);
470 }
471 if (nl)
472 fprintf (stream: f, format: "\n");
473}
474
475
476void
477ipa_predicate::debug (conditions conds) const
478{
479 dump (stderr, conds);
480}
481
482
483/* Remap predicate THIS of former function to be predicate of duplicated function.
484 POSSIBLE_TRUTHS is clause of possible truths in the duplicated node,
485 INFO is inline summary of the duplicated node. */
486
487ipa_predicate
488ipa_predicate::remap_after_duplication (clause_t possible_truths)
489{
490 int j;
491 ipa_predicate out = true;
492 for (j = 0; m_clause[j]; j++)
493 if (!(possible_truths & m_clause[j]))
494 return false;
495 else
496 out.add_clause (NULL, new_clause: possible_truths & m_clause[j]);
497 return out;
498}
499
500
501/* Translate all conditions from callee representation into caller
502 representation and symbolically evaluate predicate THIS into new predicate.
503
504 INFO is ipa_fn_summary of function we are adding predicate into, CALLEE_INFO
505 is summary of function predicate P is from. OPERAND_MAP is array giving
506 callee formal IDs the caller formal IDs. POSSSIBLE_TRUTHS is clause of all
507 callee conditions that may be true in caller context. TOPLEV_PREDICATE is
508 predicate under which callee is executed. OFFSET_MAP is an array of
509 offsets that need to be added to conditions, negative offset means that
510 conditions relying on values passed by reference have to be discarded
511 because they might not be preserved (and should be considered offset zero
512 for other purposes). */
513
514ipa_predicate
515ipa_predicate::remap_after_inlining (class ipa_fn_summary *info,
516 class ipa_node_params *params_summary,
517 class ipa_fn_summary *callee_info,
518 const vec<int> &operand_map,
519 const vec<HOST_WIDE_INT> &offset_map,
520 clause_t possible_truths,
521 const ipa_predicate &toplev_predicate)
522{
523 int i;
524 ipa_predicate out = true;
525
526 /* True ipa_predicate is easy. */
527 if (*this == true)
528 return toplev_predicate;
529 for (i = 0; m_clause[i]; i++)
530 {
531 clause_t clause = m_clause[i];
532 int cond;
533 ipa_predicate clause_predicate = false;
534
535 gcc_assert (i < max_clauses);
536
537 for (cond = 0; cond < num_conditions; cond++)
538 /* Do we have condition we can't disprove? */
539 if (clause & possible_truths & (1 << cond))
540 {
541 ipa_predicate cond_predicate;
542 /* Work out if the condition can translate to predicate in the
543 inlined function. */
544 if (cond >= ipa_predicate::first_dynamic_condition)
545 {
546 struct condition *c;
547
548 int index = cond - ipa_predicate::first_dynamic_condition;
549 c = &(*callee_info->conds)[index];
550 /* See if we can remap condition operand to caller's operand.
551 Otherwise give up. */
552 if (!operand_map.exists ()
553 || (int) operand_map.length () <= c->operand_num
554 || operand_map[c->operand_num] == -1
555 /* TODO: For non-aggregate conditions, adding an offset is
556 basically an arithmetic jump function processing which
557 we should support in future. */
558 || ((!c->agg_contents || !c->by_ref)
559 && offset_map[c->operand_num] > 0)
560 || (c->agg_contents && c->by_ref
561 && offset_map[c->operand_num] < 0))
562 cond_predicate = true;
563 else
564 {
565 struct agg_position_info ap;
566 HOST_WIDE_INT offset_delta = offset_map[c->operand_num];
567 if (offset_delta < 0)
568 {
569 gcc_checking_assert (!c->agg_contents || !c->by_ref);
570 offset_delta = 0;
571 }
572 gcc_assert (!c->agg_contents
573 || c->by_ref || offset_delta == 0);
574 ap.offset = c->offset + offset_delta;
575 ap.agg_contents = c->agg_contents;
576 ap.by_ref = c->by_ref;
577 cond_predicate = add_condition (summary: info, params_summary,
578 operand_num: operand_map[c->operand_num],
579 type: c->type, aggpos: &ap, code: c->code,
580 val: c->val, param_ops: c->param_ops);
581 }
582 }
583 /* Fixed conditions remains same, construct single
584 condition predicate. */
585 else
586 cond_predicate = ipa_predicate::predicate_testing_cond (i: cond);
587 clause_predicate = clause_predicate.or_with (conditions: info->conds,
588 p: cond_predicate);
589 }
590 out &= clause_predicate;
591 }
592 out &= toplev_predicate;
593 return out;
594}
595
596
597/* Read predicate from IB. */
598
599void
600ipa_predicate::stream_in (class lto_input_block *ib)
601{
602 clause_t clause;
603 int k = 0;
604
605 do
606 {
607 gcc_assert (k <= max_clauses);
608 clause = m_clause[k++] = streamer_read_uhwi (ib);
609 }
610 while (clause);
611
612 /* Zero-initialize the remaining clauses in OUT. */
613 while (k <= max_clauses)
614 m_clause[k++] = 0;
615}
616
617
618/* Write predicate P to OB. */
619
620void
621ipa_predicate::stream_out (struct output_block *ob)
622{
623 int j;
624 for (j = 0; m_clause[j]; j++)
625 {
626 gcc_assert (j < max_clauses);
627 streamer_write_uhwi (ob, m_clause[j]);
628 }
629 streamer_write_uhwi (ob, 0);
630}
631
632
633/* Add condition to condition list SUMMARY. OPERAND_NUM, TYPE, CODE, VAL and
634 PARAM_OPS correspond to fields of condition structure. AGGPOS describes
635 whether the used operand is loaded from an aggregate and where in the
636 aggregate it is. It can be NULL, which means this not a load from an
637 aggregate. */
638
639ipa_predicate
640add_condition (class ipa_fn_summary *summary,
641 class ipa_node_params *params_summary,
642 int operand_num,
643 tree type, struct agg_position_info *aggpos,
644 enum tree_code code, tree val, expr_eval_ops param_ops)
645{
646 int i, j;
647 struct condition *c;
648 struct condition new_cond;
649 HOST_WIDE_INT offset;
650 bool agg_contents, by_ref;
651 expr_eval_op *op;
652
653 if (params_summary)
654 ipa_set_param_used_by_ipa_predicates (info: params_summary, i: operand_num, val: true);
655
656 if (aggpos)
657 {
658 offset = aggpos->offset;
659 agg_contents = aggpos->agg_contents;
660 by_ref = aggpos->by_ref;
661 }
662 else
663 {
664 offset = 0;
665 agg_contents = false;
666 by_ref = false;
667 }
668
669 gcc_checking_assert (operand_num >= 0);
670 for (i = 0; vec_safe_iterate (v: summary->conds, ix: i, ptr: &c); i++)
671 {
672 if (c->operand_num == operand_num
673 && c->code == code
674 && types_compatible_p (type1: c->type, type2: type)
675 && vrp_operand_equal_p (c->val, val)
676 && c->agg_contents == agg_contents
677 && expr_eval_ops_equal_p (ops1: c->param_ops, ops2: param_ops)
678 && (!agg_contents || (c->offset == offset && c->by_ref == by_ref)))
679 return ipa_predicate::predicate_testing_cond (i);
680 }
681 /* Too many conditions. Give up and return constant true. */
682 if (i == ipa_predicate::num_conditions - ipa_predicate::first_dynamic_condition)
683 return true;
684
685 new_cond.operand_num = operand_num;
686 new_cond.code = code;
687 new_cond.type = unshare_expr_without_location (type);
688 new_cond.val = val ? unshare_expr_without_location (val) : val;
689 new_cond.agg_contents = agg_contents;
690 new_cond.by_ref = by_ref;
691 new_cond.offset = offset;
692 new_cond.param_ops = vec_safe_copy (src: param_ops);
693
694 for (j = 0; vec_safe_iterate (v: new_cond.param_ops, ix: j, ptr: &op); j++)
695 {
696 if (op->val[0])
697 op->val[0] = unshare_expr_without_location (op->val[0]);
698 if (op->val[1])
699 op->val[1] = unshare_expr_without_location (op->val[1]);
700 }
701
702 vec_safe_push (v&: summary->conds, obj: new_cond);
703
704 return ipa_predicate::predicate_testing_cond (i);
705}
706

source code of gcc/ipa-predicate.cc