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

source code of gcc/ipa-predicate.cc