1 /* IPA predicates.
2 Copyright (C) 2003-2021 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 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 << 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 << 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 = 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 - 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 - 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 predicate &
174 predicate::operator &= (const 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 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 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 predicate
or_with(conditions conditions,const predicate & p)207 predicate::or_with (conditions conditions,
208 const 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 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)233 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 << 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)257 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 << 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 >= predicate::first_dynamic_condition)
289 {
290 condition *c =
291 &(*conds)[i2 - predicate::first_dynamic_condition];
292 if (c->code == 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 == predicate::false_condition)
322 fprintf (f, "false");
323 else if (cond == predicate::not_inlined_condition)
324 fprintf (f, "not inlined");
325 else
326 {
327 c = &(*conditions)[cond - 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 == predicate::is_not_constant)
410 {
411 fprintf (f, " not constant");
412 return;
413 }
414 if (c->code == 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 < 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 predicates. When NL is true new line is output at the end of dump. */
449
450 void
dump(FILE * f,conditions conds,bool nl)451 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)469 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 predicate
remap_after_duplication(clause_t possible_truths)480 predicate::remap_after_duplication (clause_t possible_truths)
481 {
482 int j;
483 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 predicate
remap_after_inlining(class ipa_fn_summary * info,class ipa_node_params * params_summary,class ipa_fn_summary * callee_info,vec<int> operand_map,vec<HOST_WIDE_INT> offset_map,clause_t possible_truths,const predicate & toplev_predicate)507 predicate::remap_after_inlining (class ipa_fn_summary *info,
508 class ipa_node_params *params_summary,
509 class ipa_fn_summary *callee_info,
510 vec<int> operand_map,
511 vec<HOST_WIDE_INT> offset_map,
512 clause_t possible_truths,
513 const predicate &toplev_predicate)
514 {
515 int i;
516 predicate out = true;
517
518 /* True 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 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 predicate cond_predicate;
534 /* Work out if the condition can translate to predicate in the
535 inlined function. */
536 if (cond >= predicate::first_dynamic_condition)
537 {
538 struct condition *c;
539
540 c = &(*callee_info->conds)[cond
541 -
542 predicate::first_dynamic_condition];
543 /* See if we can remap condition operand to caller's operand.
544 Otherwise give up. */
545 if (!operand_map.exists ()
546 || (int) operand_map.length () <= c->operand_num
547 || operand_map[c->operand_num] == -1
548 /* TODO: For non-aggregate conditions, adding an offset is
549 basically an arithmetic jump function processing which
550 we should support in future. */
551 || ((!c->agg_contents || !c->by_ref)
552 && offset_map[c->operand_num] > 0)
553 || (c->agg_contents && c->by_ref
554 && offset_map[c->operand_num] < 0))
555 cond_predicate = true;
556 else
557 {
558 struct agg_position_info ap;
559 HOST_WIDE_INT offset_delta = offset_map[c->operand_num];
560 if (offset_delta < 0)
561 {
562 gcc_checking_assert (!c->agg_contents || !c->by_ref);
563 offset_delta = 0;
564 }
565 gcc_assert (!c->agg_contents
566 || c->by_ref || offset_delta == 0);
567 ap.offset = c->offset + offset_delta;
568 ap.agg_contents = c->agg_contents;
569 ap.by_ref = c->by_ref;
570 cond_predicate = add_condition (info, params_summary,
571 operand_map[c->operand_num],
572 c->type, &ap, c->code,
573 c->val, c->param_ops);
574 }
575 }
576 /* Fixed conditions remains same, construct single
577 condition predicate. */
578 else
579 cond_predicate = predicate::predicate_testing_cond (cond);
580 clause_predicate = clause_predicate.or_with (info->conds,
581 cond_predicate);
582 }
583 out &= clause_predicate;
584 }
585 out &= toplev_predicate;
586 return out;
587 }
588
589
590 /* Read predicate from IB. */
591
592 void
stream_in(class lto_input_block * ib)593 predicate::stream_in (class lto_input_block *ib)
594 {
595 clause_t clause;
596 int k = 0;
597
598 do
599 {
600 gcc_assert (k <= max_clauses);
601 clause = m_clause[k++] = streamer_read_uhwi (ib);
602 }
603 while (clause);
604
605 /* Zero-initialize the remaining clauses in OUT. */
606 while (k <= max_clauses)
607 m_clause[k++] = 0;
608 }
609
610
611 /* Write predicate P to OB. */
612
613 void
stream_out(struct output_block * ob)614 predicate::stream_out (struct output_block *ob)
615 {
616 int j;
617 for (j = 0; m_clause[j]; j++)
618 {
619 gcc_assert (j < max_clauses);
620 streamer_write_uhwi (ob, m_clause[j]);
621 }
622 streamer_write_uhwi (ob, 0);
623 }
624
625
626 /* Add condition to condition list SUMMARY. OPERAND_NUM, TYPE, CODE, VAL and
627 PARAM_OPS correspond to fields of condition structure. AGGPOS describes
628 whether the used operand is loaded from an aggregate and where in the
629 aggregate it is. It can be NULL, which means this not a load from an
630 aggregate. */
631
632 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)633 add_condition (class ipa_fn_summary *summary,
634 class ipa_node_params *params_summary,
635 int operand_num,
636 tree type, struct agg_position_info *aggpos,
637 enum tree_code code, tree val, expr_eval_ops param_ops)
638 {
639 int i, j;
640 struct condition *c;
641 struct condition new_cond;
642 HOST_WIDE_INT offset;
643 bool agg_contents, by_ref;
644 expr_eval_op *op;
645
646 if (params_summary)
647 ipa_set_param_used_by_ipa_predicates (params_summary, operand_num, true);
648
649 if (aggpos)
650 {
651 offset = aggpos->offset;
652 agg_contents = aggpos->agg_contents;
653 by_ref = aggpos->by_ref;
654 }
655 else
656 {
657 offset = 0;
658 agg_contents = false;
659 by_ref = false;
660 }
661
662 gcc_checking_assert (operand_num >= 0);
663 for (i = 0; vec_safe_iterate (summary->conds, i, &c); i++)
664 {
665 if (c->operand_num == operand_num
666 && c->code == code
667 && types_compatible_p (c->type, type)
668 && vrp_operand_equal_p (c->val, val)
669 && c->agg_contents == agg_contents
670 && expr_eval_ops_equal_p (c->param_ops, param_ops)
671 && (!agg_contents || (c->offset == offset && c->by_ref == by_ref)))
672 return predicate::predicate_testing_cond (i);
673 }
674 /* Too many conditions. Give up and return constant true. */
675 if (i == predicate::num_conditions - predicate::first_dynamic_condition)
676 return true;
677
678 new_cond.operand_num = operand_num;
679 new_cond.code = code;
680 new_cond.type = unshare_expr_without_location (type);
681 new_cond.val = val ? unshare_expr_without_location (val) : val;
682 new_cond.agg_contents = agg_contents;
683 new_cond.by_ref = by_ref;
684 new_cond.offset = offset;
685 new_cond.param_ops = vec_safe_copy (param_ops);
686
687 for (j = 0; vec_safe_iterate (new_cond.param_ops, j, &op); j++)
688 {
689 if (op->val[0])
690 op->val[0] = unshare_expr_without_location (op->val[0]);
691 if (op->val[1])
692 op->val[1] = unshare_expr_without_location (op->val[1]);
693 }
694
695 vec_safe_push (summary->conds, new_cond);
696
697 return predicate::predicate_testing_cond (i);
698 }
699