Daily bump.
[official-gcc.git] / gcc / ipa-predicate.c
blob6ef02b18f4c07fc2d0956f0177b0f290183a1fed
1 /* IPA predicates.
2 Copyright (C) 2003-2018 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
10 version.
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.
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/>. */
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 "symbol-summary.h"
29 #include "alloc-pool.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 "data-streamer.h"
39 /* Add clause CLAUSE into the predicate P.
40 When CONDITIONS is NULL do not perform checking whether NEW_CLAUSE
41 is obviously true. This is useful only when NEW_CLAUSE is known to be
42 sane. */
44 void
45 predicate::add_clause (conditions conditions, clause_t new_clause)
47 int i;
48 int i2;
49 int insert_here = -1;
50 int c1, c2;
52 /* True clause. */
53 if (!new_clause)
54 return;
56 /* False clause makes the whole predicate false. Kill the other variants. */
57 if (new_clause == (1 << predicate::false_condition))
59 *this = false;
60 return;
62 if (*this == false)
63 return;
65 /* No one should be silly enough to add false into nontrivial clauses. */
66 gcc_checking_assert (!(new_clause & (1 << predicate::false_condition)));
68 /* Look where to insert the new_clause. At the same time prune out
69 new_clauses of P that are implied by the new new_clause and thus
70 redundant. */
71 for (i = 0, i2 = 0; i <= max_clauses; i++)
73 m_clause[i2] = m_clause[i];
75 if (!m_clause[i])
76 break;
78 /* If m_clause[i] implies new_clause, there is nothing to add. */
79 if ((m_clause[i] & new_clause) == m_clause[i])
81 /* We had nothing to add, none of clauses should've become
82 redundant. */
83 gcc_checking_assert (i == i2);
84 return;
87 if (m_clause[i] < new_clause && insert_here < 0)
88 insert_here = i2;
90 /* If new_clause implies clause[i], then clause[i] becomes redundant.
91 Otherwise the clause[i] has to stay. */
92 if ((m_clause[i] & new_clause) != new_clause)
93 i2++;
96 /* Look for clauses that are obviously true. I.e.
97 op0 == 5 || op0 != 5. */
98 if (conditions)
99 for (c1 = predicate::first_dynamic_condition;
100 c1 < num_conditions; c1++)
102 condition *cc1;
103 if (!(new_clause & (1 << c1)))
104 continue;
105 cc1 = &(*conditions)[c1 - predicate::first_dynamic_condition];
106 /* We have no way to represent !changed and !is_not_constant
107 and thus there is no point for looking for them. */
108 if (cc1->code == changed || cc1->code == is_not_constant)
109 continue;
110 for (c2 = c1 + 1; c2 < num_conditions; c2++)
111 if (new_clause & (1 << c2))
113 condition *cc1 =
114 &(*conditions)[c1 - predicate::first_dynamic_condition];
115 condition *cc2 =
116 &(*conditions)[c2 - predicate::first_dynamic_condition];
117 if (cc1->operand_num == cc2->operand_num
118 && cc1->val == cc2->val
119 && cc2->code != is_not_constant
120 && cc2->code != predicate::changed
121 && cc1->code == invert_tree_comparison (cc2->code,
122 HONOR_NANS (cc1->val)))
123 return;
128 /* We run out of variants. Be conservative in positive direction. */
129 if (i2 == max_clauses)
130 return;
131 /* Keep clauses in decreasing order. This makes equivalence testing easy. */
132 m_clause[i2 + 1] = 0;
133 if (insert_here >= 0)
134 for (; i2 > insert_here; i2--)
135 m_clause[i2] = m_clause[i2 - 1];
136 else
137 insert_here = i2;
138 m_clause[insert_here] = new_clause;
142 /* Do THIS &= P. */
144 predicate &
145 predicate::operator &= (const predicate &p)
147 /* Avoid busy work. */
148 if (p == false || *this == true)
150 *this = p;
151 return *this;
153 if (*this == false || p == true || this == &p)
154 return *this;
156 int i;
158 /* See how far predicates match. */
159 for (i = 0; m_clause[i] && m_clause[i] == p.m_clause[i]; i++)
161 gcc_checking_assert (i < max_clauses);
164 /* Combine the predicates rest. */
165 for (; p.m_clause[i]; i++)
167 gcc_checking_assert (i < max_clauses);
168 add_clause (NULL, p.m_clause[i]);
170 return *this;
175 /* Return THIS | P2. */
177 predicate
178 predicate::or_with (conditions conditions,
179 const predicate &p) const
181 /* Avoid busy work. */
182 if (p == false || *this == true || *this == p)
183 return *this;
184 if (*this == false || p == true)
185 return p;
187 /* OK, combine the predicates. */
188 predicate out = true;
190 for (int i = 0; m_clause[i]; i++)
191 for (int j = 0; p.m_clause[j]; j++)
193 gcc_checking_assert (i < max_clauses && j < max_clauses);
194 out.add_clause (conditions, m_clause[i] | p.m_clause[j]);
196 return out;
200 /* Having partial truth assignment in POSSIBLE_TRUTHS, return false
201 if predicate P is known to be false. */
203 bool
204 predicate::evaluate (clause_t possible_truths) const
206 int i;
208 /* True remains true. */
209 if (*this == true)
210 return true;
212 gcc_assert (!(possible_truths & (1 << predicate::false_condition)));
214 /* See if we can find clause we can disprove. */
215 for (i = 0; m_clause[i]; i++)
217 gcc_checking_assert (i < max_clauses);
218 if (!(m_clause[i] & possible_truths))
219 return false;
221 return true;
224 /* Return the probability in range 0...REG_BR_PROB_BASE that the predicated
225 instruction will be recomputed per invocation of the inlined call. */
228 predicate::probability (conditions conds,
229 clause_t possible_truths,
230 vec<inline_param_summary> inline_param_summary) const
232 int i;
233 int combined_prob = REG_BR_PROB_BASE;
235 /* True remains true. */
236 if (*this == true)
237 return REG_BR_PROB_BASE;
239 if (*this == false)
240 return 0;
242 gcc_assert (!(possible_truths & (1 << predicate::false_condition)));
244 /* See if we can find clause we can disprove. */
245 for (i = 0; m_clause[i]; i++)
247 gcc_checking_assert (i < max_clauses);
248 if (!(m_clause[i] & possible_truths))
249 return 0;
250 else
252 int this_prob = 0;
253 int i2;
254 if (!inline_param_summary.exists ())
255 return REG_BR_PROB_BASE;
256 for (i2 = 0; i2 < num_conditions; i2++)
257 if ((m_clause[i] & possible_truths) & (1 << i2))
259 if (i2 >= predicate::first_dynamic_condition)
261 condition *c =
262 &(*conds)[i2 - predicate::first_dynamic_condition];
263 if (c->code == predicate::changed
264 && (c->operand_num <
265 (int) inline_param_summary.length ()))
267 int iprob =
268 inline_param_summary[c->operand_num].change_prob;
269 this_prob = MAX (this_prob, iprob);
271 else
272 this_prob = REG_BR_PROB_BASE;
274 else
275 this_prob = REG_BR_PROB_BASE;
277 combined_prob = MIN (this_prob, combined_prob);
278 if (!combined_prob)
279 return 0;
282 return combined_prob;
286 /* Dump conditional COND. */
288 void
289 dump_condition (FILE *f, conditions conditions, int cond)
291 condition *c;
292 if (cond == predicate::false_condition)
293 fprintf (f, "false");
294 else if (cond == predicate::not_inlined_condition)
295 fprintf (f, "not inlined");
296 else
298 c = &(*conditions)[cond - predicate::first_dynamic_condition];
299 fprintf (f, "op%i", c->operand_num);
300 if (c->agg_contents)
301 fprintf (f, "[%soffset: " HOST_WIDE_INT_PRINT_DEC "]",
302 c->by_ref ? "ref " : "", c->offset);
303 if (c->code == predicate::is_not_constant)
305 fprintf (f, " not constant");
306 return;
308 if (c->code == predicate::changed)
310 fprintf (f, " changed");
311 return;
313 fprintf (f, " %s ", op_symbol_code (c->code));
314 print_generic_expr (f, c->val);
319 /* Dump clause CLAUSE. */
321 static void
322 dump_clause (FILE *f, conditions conds, clause_t clause)
324 int i;
325 bool found = false;
326 fprintf (f, "(");
327 if (!clause)
328 fprintf (f, "true");
329 for (i = 0; i < predicate::num_conditions; i++)
330 if (clause & (1 << i))
332 if (found)
333 fprintf (f, " || ");
334 found = true;
335 dump_condition (f, conds, i);
337 fprintf (f, ")");
341 /* Dump THIS to F. CONDS a vector of conditions used when evauating
342 predicats. When NL is true new line is output at the end of dump. */
344 void
345 predicate::dump (FILE *f, conditions conds, bool nl) const
347 int i;
348 if (*this == true)
349 dump_clause (f, conds, 0);
350 else
351 for (i = 0; m_clause[i]; i++)
353 if (i)
354 fprintf (f, " && ");
355 dump_clause (f, conds, m_clause[i]);
357 if (nl)
358 fprintf (f, "\n");
362 void
363 predicate::debug (conditions conds) const
365 dump (stderr, conds);
369 /* Remap predicate THIS of former function to be predicate of duplicated function.
370 POSSIBLE_TRUTHS is clause of possible truths in the duplicated node,
371 INFO is inline summary of the duplicated node. */
373 predicate
374 predicate::remap_after_duplication (clause_t possible_truths)
376 int j;
377 predicate out = true;
378 for (j = 0; m_clause[j]; j++)
379 if (!(possible_truths & m_clause[j]))
380 return false;
381 else
382 out.add_clause (NULL, possible_truths & m_clause[j]);
383 return out;
387 /* Translate all conditions from callee representation into caller
388 representation and symbolically evaluate predicate THIS into new predicate.
390 INFO is ipa_fn_summary of function we are adding predicate into, CALLEE_INFO
391 is summary of function predicate P is from. OPERAND_MAP is array giving
392 callee formal IDs the caller formal IDs. POSSSIBLE_TRUTHS is clausule of all
393 callee conditions that may be true in caller context. TOPLEV_PREDICATE is
394 predicate under which callee is executed. OFFSET_MAP is an array of of
395 offsets that need to be added to conditions, negative offset means that
396 conditions relying on values passed by reference have to be discarded
397 because they might not be preserved (and should be considered offset zero
398 for other purposes). */
400 predicate
401 predicate::remap_after_inlining (struct ipa_fn_summary *info,
402 struct ipa_fn_summary *callee_info,
403 vec<int> operand_map,
404 vec<int> offset_map,
405 clause_t possible_truths,
406 const predicate &toplev_predicate)
408 int i;
409 predicate out = true;
411 /* True predicate is easy. */
412 if (*this == true)
413 return toplev_predicate;
414 for (i = 0; m_clause[i]; i++)
416 clause_t clause = m_clause[i];
417 int cond;
418 predicate clause_predicate = false;
420 gcc_assert (i < max_clauses);
422 for (cond = 0; cond < num_conditions; cond++)
423 /* Do we have condition we can't disprove? */
424 if (clause & possible_truths & (1 << cond))
426 predicate cond_predicate;
427 /* Work out if the condition can translate to predicate in the
428 inlined function. */
429 if (cond >= predicate::first_dynamic_condition)
431 struct condition *c;
433 c = &(*callee_info->conds)[cond
435 predicate::first_dynamic_condition];
436 /* See if we can remap condition operand to caller's operand.
437 Otherwise give up. */
438 if (!operand_map.exists ()
439 || (int) operand_map.length () <= c->operand_num
440 || operand_map[c->operand_num] == -1
441 /* TODO: For non-aggregate conditions, adding an offset is
442 basically an arithmetic jump function processing which
443 we should support in future. */
444 || ((!c->agg_contents || !c->by_ref)
445 && offset_map[c->operand_num] > 0)
446 || (c->agg_contents && c->by_ref
447 && offset_map[c->operand_num] < 0))
448 cond_predicate = true;
449 else
451 struct agg_position_info ap;
452 HOST_WIDE_INT offset_delta = offset_map[c->operand_num];
453 if (offset_delta < 0)
455 gcc_checking_assert (!c->agg_contents || !c->by_ref);
456 offset_delta = 0;
458 gcc_assert (!c->agg_contents
459 || c->by_ref || offset_delta == 0);
460 ap.offset = c->offset + offset_delta;
461 ap.agg_contents = c->agg_contents;
462 ap.by_ref = c->by_ref;
463 cond_predicate = add_condition (info,
464 operand_map[c->operand_num],
465 c->size, &ap, c->code,
466 c->val);
469 /* Fixed conditions remains same, construct single
470 condition predicate. */
471 else
472 cond_predicate = predicate::predicate_testing_cond (cond);
473 clause_predicate = clause_predicate.or_with (info->conds,
474 cond_predicate);
476 out &= clause_predicate;
478 out &= toplev_predicate;
479 return out;
483 /* Read predicate from IB. */
485 void
486 predicate::stream_in (struct lto_input_block *ib)
488 clause_t clause;
489 int k = 0;
493 gcc_assert (k <= max_clauses);
494 clause = m_clause[k++] = streamer_read_uhwi (ib);
496 while (clause);
498 /* Zero-initialize the remaining clauses in OUT. */
499 while (k <= max_clauses)
500 m_clause[k++] = 0;
504 /* Write predicate P to OB. */
506 void
507 predicate::stream_out (struct output_block *ob)
509 int j;
510 for (j = 0; m_clause[j]; j++)
512 gcc_assert (j < max_clauses);
513 streamer_write_uhwi (ob, m_clause[j]);
515 streamer_write_uhwi (ob, 0);
519 /* Add condition to condition list SUMMARY. OPERAND_NUM, SIZE, CODE and VAL
520 correspond to fields of condition structure. AGGPOS describes whether the
521 used operand is loaded from an aggregate and where in the aggregate it is.
522 It can be NULL, which means this not a load from an aggregate. */
524 predicate
525 add_condition (struct ipa_fn_summary *summary, int operand_num,
526 HOST_WIDE_INT size, struct agg_position_info *aggpos,
527 enum tree_code code, tree val)
529 int i;
530 struct condition *c;
531 struct condition new_cond;
532 HOST_WIDE_INT offset;
533 bool agg_contents, by_ref;
535 if (aggpos)
537 offset = aggpos->offset;
538 agg_contents = aggpos->agg_contents;
539 by_ref = aggpos->by_ref;
541 else
543 offset = 0;
544 agg_contents = false;
545 by_ref = false;
548 gcc_checking_assert (operand_num >= 0);
549 for (i = 0; vec_safe_iterate (summary->conds, i, &c); i++)
551 if (c->operand_num == operand_num
552 && c->size == size
553 && c->code == code
554 && c->val == val
555 && c->agg_contents == agg_contents
556 && (!agg_contents || (c->offset == offset && c->by_ref == by_ref)))
557 return predicate::predicate_testing_cond (i);
559 /* Too many conditions. Give up and return constant true. */
560 if (i == predicate::num_conditions - predicate::first_dynamic_condition)
561 return true;
563 new_cond.operand_num = operand_num;
564 new_cond.code = code;
565 new_cond.val = val;
566 new_cond.agg_contents = agg_contents;
567 new_cond.by_ref = by_ref;
568 new_cond.offset = offset;
569 new_cond.size = size;
570 vec_safe_push (summary->conds, new_cond);
572 return predicate::predicate_testing_cond (i);