2 Copyright (C) 2003-2023 Free Software Foundation, Inc.
3 Contributed by Jan Hubicka
5 This file is part of GCC.
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
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
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/>. */
23 #include "coretypes.h"
28 #include "alloc-pool.h"
29 #include "symbol-summary.h"
31 #include "ipa-fnsummary.h"
33 #include "fold-const.h"
34 #include "tree-pretty-print.h"
37 #include "data-streamer.h"
40 /* Check whether two set of operations have same effects. */
42 expr_eval_ops_equal_p (expr_eval_ops ops1
, expr_eval_ops ops2
)
46 if (!ops2
|| ops1
->length () != ops2
->length ())
49 for (unsigned i
= 0; i
< ops1
->length (); i
++)
51 expr_eval_op
&op1
= (*ops1
)[i
];
52 expr_eval_op
&op2
= (*ops2
)[i
];
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
))
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
72 ipa_predicate::add_clause (conditions conditions
, clause_t new_clause
)
83 /* False clause makes the whole predicate false. Kill the other variants. */
84 if (new_clause
== (1 << ipa_predicate::false_condition
))
92 /* No one should be silly enough to add false into nontrivial clauses. */
93 gcc_checking_assert (!(new_clause
& (1 << ipa_predicate::false_condition
)));
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
98 for (i
= 0, i2
= 0; i
<= max_clauses
; i
++)
100 m_clause
[i2
] = m_clause
[i
];
105 /* If m_clause[i] implies new_clause, there is nothing to add. */
106 if ((m_clause
[i
] & new_clause
) == m_clause
[i
])
108 /* We had nothing to add, none of clauses should've become
110 gcc_checking_assert (i
== i2
);
114 if (m_clause
[i
] < new_clause
&& insert_here
< 0)
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
)
123 /* Look for clauses that are obviously true. I.e.
124 op0 == 5 || op0 != 5. */
126 for (c1
= ipa_predicate::first_dynamic_condition
;
127 c1
< num_conditions
; c1
++)
130 if (!(new_clause
& (1 << c1
)))
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
)
137 for (c2
= c1
+ 1; c2
< num_conditions
; c2
++)
138 if (new_clause
& (1 << c2
))
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
)))
157 /* We run out of variants. Be conservative in positive direction. */
158 if (i2
== max_clauses
)
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];
167 m_clause
[insert_here
] = new_clause
;
174 ipa_predicate::operator &= (const ipa_predicate
&p
)
176 /* Avoid busy work. */
177 if (p
== false || *this == true)
182 if (*this == false || p
== true || this == &p
)
187 /* See how far ipa_predicates match. */
188 for (i
= 0; m_clause
[i
] && m_clause
[i
] == p
.m_clause
[i
]; i
++)
190 gcc_checking_assert (i
< max_clauses
);
193 /* Combine the ipa_predicates rest. */
194 for (; p
.m_clause
[i
]; i
++)
196 gcc_checking_assert (i
< max_clauses
);
197 add_clause (NULL
, p
.m_clause
[i
]);
204 /* Return THIS | P2. */
207 ipa_predicate::or_with (conditions conditions
,
208 const ipa_predicate
&p
) const
210 /* Avoid busy work. */
211 if (p
== false || *this == true || *this == p
)
213 if (*this == false || p
== true)
216 /* OK, combine the predicates. */
217 ipa_predicate out
= true;
219 for (int i
= 0; m_clause
[i
]; i
++)
220 for (int j
= 0; p
.m_clause
[j
]; j
++)
222 gcc_checking_assert (i
< max_clauses
&& j
< max_clauses
);
223 out
.add_clause (conditions
, m_clause
[i
] | p
.m_clause
[j
]);
229 /* Having partial truth assignment in POSSIBLE_TRUTHS, return false
230 if predicate P is known to be false. */
233 ipa_predicate::evaluate (clause_t possible_truths
) const
237 /* True remains true. */
241 gcc_assert (!(possible_truths
& (1 << ipa_predicate::false_condition
)));
243 /* See if we can find clause we can disprove. */
244 for (i
= 0; m_clause
[i
]; i
++)
246 gcc_checking_assert (i
< max_clauses
);
247 if (!(m_clause
[i
] & possible_truths
))
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. */
257 ipa_predicate::probability (conditions conds
,
258 clause_t possible_truths
,
259 vec
<inline_param_summary
> inline_param_summary
) const
262 int combined_prob
= REG_BR_PROB_BASE
;
264 /* True remains true. */
266 return REG_BR_PROB_BASE
;
271 gcc_assert (!(possible_truths
& (1 << ipa_predicate::false_condition
)));
273 /* See if we can find clause we can disprove. */
274 for (i
= 0; m_clause
[i
]; i
++)
276 gcc_checking_assert (i
< max_clauses
);
277 if (!(m_clause
[i
] & possible_truths
))
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
))
288 if (i2
>= ipa_predicate::first_dynamic_condition
)
291 &(*conds
)[i2
- ipa_predicate::first_dynamic_condition
];
292 if (c
->code
== ipa_predicate::changed
294 (int) inline_param_summary
.length ()))
297 inline_param_summary
[c
->operand_num
].change_prob
;
298 this_prob
= MAX (this_prob
, iprob
);
301 this_prob
= REG_BR_PROB_BASE
;
304 this_prob
= REG_BR_PROB_BASE
;
306 combined_prob
= MIN (this_prob
, combined_prob
);
311 return combined_prob
;
315 /* Dump conditional COND. */
318 dump_condition (FILE *f
, conditions conditions
, int cond
)
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");
327 c
= &(*conditions
)[cond
- ipa_predicate::first_dynamic_condition
];
328 fprintf (f
, "op%i", c
->operand_num
);
330 fprintf (f
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
"]",
331 c
->by_ref
? "ref " : "", c
->offset
);
333 for (unsigned i
= 0; i
< vec_safe_length (c
->param_ops
); i
++)
335 expr_eval_op
&op
= (*(c
->param_ops
))[i
];
336 const char *op_name
= op_symbol_code (op
.code
);
338 if (op_name
== op_symbol_code (ERROR_MARK
))
339 op_name
= get_tree_code_name (op
.code
);
349 case FIXED_CONVERT_EXPR
:
350 case VIEW_CONVERT_EXPR
:
352 if (op
.code
== VIEW_CONVERT_EXPR
)
355 print_generic_expr (f
, op
.type
);
360 fprintf (f
, "%s", op_name
);
368 print_generic_expr (f
, op
.val
[0]);
369 fprintf (f
, " %s #", op_name
);
373 fprintf (f
, "# %s ", op_name
);
374 print_generic_expr (f
, op
.val
[0]);
379 fprintf (f
, "%s ", op_name
);
384 print_generic_expr (f
, op
.val
[0]);
386 print_generic_expr (f
, op
.val
[1]);
390 print_generic_expr (f
, op
.val
[0]);
391 fprintf (f
, ", #, ");
392 print_generic_expr (f
, op
.val
[1]);
396 print_generic_expr (f
, op
.val
[0]);
398 print_generic_expr (f
, op
.val
[1]);
403 fprintf (f
, "*, *, *");
409 if (c
->code
== ipa_predicate::is_not_constant
)
411 fprintf (f
, " not constant");
414 if (c
->code
== ipa_predicate::changed
)
416 fprintf (f
, " changed");
419 fprintf (f
, " %s ", op_symbol_code (c
->code
));
420 print_generic_expr (f
, c
->val
);
425 /* Dump clause CLAUSE. */
428 dump_clause (FILE *f
, conditions conds
, clause_t clause
)
435 for (i
= 0; i
< ipa_predicate::num_conditions
; i
++)
436 if (clause
& (1 << i
))
441 dump_condition (f
, conds
, i
);
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. */
451 ipa_predicate::dump (FILE *f
, conditions conds
, bool nl
) const
455 dump_clause (f
, conds
, 0);
457 for (i
= 0; m_clause
[i
]; i
++)
461 dump_clause (f
, conds
, m_clause
[i
]);
469 ipa_predicate::debug (conditions conds
) const
471 dump (stderr
, conds
);
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. */
480 ipa_predicate::remap_after_duplication (clause_t possible_truths
)
483 ipa_predicate out
= true;
484 for (j
= 0; m_clause
[j
]; j
++)
485 if (!(possible_truths
& m_clause
[j
]))
488 out
.add_clause (NULL
, possible_truths
& m_clause
[j
]);
493 /* Translate all conditions from callee representation into caller
494 representation and symbolically evaluate predicate THIS into new predicate.
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). */
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
)
516 ipa_predicate out
= true;
518 /* True ipa_predicate is easy. */
520 return toplev_predicate
;
521 for (i
= 0; m_clause
[i
]; i
++)
523 clause_t clause
= m_clause
[i
];
525 ipa_predicate clause_predicate
= false;
527 gcc_assert (i
< max_clauses
);
529 for (cond
= 0; cond
< num_conditions
; cond
++)
530 /* Do we have condition we can't disprove? */
531 if (clause
& possible_truths
& (1 << cond
))
533 ipa_predicate cond_predicate
;
534 /* Work out if the condition can translate to predicate in the
536 if (cond
>= ipa_predicate::first_dynamic_condition
)
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;
557 struct agg_position_info ap
;
558 HOST_WIDE_INT offset_delta
= offset_map
[c
->operand_num
];
559 if (offset_delta
< 0)
561 gcc_checking_assert (!c
->agg_contents
|| !c
->by_ref
);
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
);
575 /* Fixed conditions remains same, construct single
576 condition predicate. */
578 cond_predicate
= ipa_predicate::predicate_testing_cond (cond
);
579 clause_predicate
= clause_predicate
.or_with (info
->conds
,
582 out
&= clause_predicate
;
584 out
&= toplev_predicate
;
589 /* Read predicate from IB. */
592 ipa_predicate::stream_in (class lto_input_block
*ib
)
599 gcc_assert (k
<= max_clauses
);
600 clause
= m_clause
[k
++] = streamer_read_uhwi (ib
);
604 /* Zero-initialize the remaining clauses in OUT. */
605 while (k
<= max_clauses
)
610 /* Write predicate P to OB. */
613 ipa_predicate::stream_out (struct output_block
*ob
)
616 for (j
= 0; m_clause
[j
]; j
++)
618 gcc_assert (j
< max_clauses
);
619 streamer_write_uhwi (ob
, m_clause
[j
]);
621 streamer_write_uhwi (ob
, 0);
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
632 add_condition (class ipa_fn_summary
*summary
,
633 class ipa_node_params
*params_summary
,
635 tree type
, struct agg_position_info
*aggpos
,
636 enum tree_code code
, tree val
, expr_eval_ops param_ops
)
640 struct condition new_cond
;
641 HOST_WIDE_INT offset
;
642 bool agg_contents
, by_ref
;
646 ipa_set_param_used_by_ipa_predicates (params_summary
, operand_num
, true);
650 offset
= aggpos
->offset
;
651 agg_contents
= aggpos
->agg_contents
;
652 by_ref
= aggpos
->by_ref
;
657 agg_contents
= false;
661 gcc_checking_assert (operand_num
>= 0);
662 for (i
= 0; vec_safe_iterate (summary
->conds
, i
, &c
); i
++)
664 if (c
->operand_num
== operand_num
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
);
673 /* Too many conditions. Give up and return constant true. */
674 if (i
== ipa_predicate::num_conditions
- ipa_predicate::first_dynamic_condition
)
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
);
686 for (j
= 0; vec_safe_iterate (new_cond
.param_ops
, j
, &op
); j
++)
689 op
->val
[0] = unshare_expr_without_location (op
->val
[0]);
691 op
->val
[1] = unshare_expr_without_location (op
->val
[1]);
694 vec_safe_push (summary
->conds
, new_cond
);
696 return ipa_predicate::predicate_testing_cond (i
);