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