1 /* IPA predicates.
2 Copyright (C) 2003-2018 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 "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"
37
38
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. */
43
44 void
add_clause(conditions conditions,clause_t new_clause)45 predicate::add_clause (conditions conditions, clause_t new_clause)
46 {
47 int i;
48 int i2;
49 int insert_here = -1;
50 int c1, c2;
51
52 /* True clause. */
53 if (!new_clause)
54 return;
55
56 /* False clause makes the whole predicate false. Kill the other variants. */
57 if (new_clause == (1 << predicate::false_condition))
58 {
59 *this = false;
60 return;
61 }
62 if (*this == false)
63 return;
64
65 /* No one should be silly enough to add false into nontrivial clauses. */
66 gcc_checking_assert (!(new_clause & (1 << predicate::false_condition)));
67
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++)
72 {
73 m_clause[i2] = m_clause[i];
74
75 if (!m_clause[i])
76 break;
77
78 /* If m_clause[i] implies new_clause, there is nothing to add. */
79 if ((m_clause[i] & new_clause) == m_clause[i])
80 {
81 /* We had nothing to add, none of clauses should've become
82 redundant. */
83 gcc_checking_assert (i == i2);
84 return;
85 }
86
87 if (m_clause[i] < new_clause && insert_here < 0)
88 insert_here = i2;
89
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++;
94 }
95
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++)
101 {
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))
112 {
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;
124 }
125 }
126
127
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;
139 }
140
141
142 /* Do THIS &= P. */
143
144 predicate &
145 predicate::operator &= (const predicate &p)
146 {
147 /* Avoid busy work. */
148 if (p == false || *this == true)
149 {
150 *this = p;
151 return *this;
152 }
153 if (*this == false || p == true || this == &p)
154 return *this;
155
156 int i;
157
158 /* See how far predicates match. */
159 for (i = 0; m_clause[i] && m_clause[i] == p.m_clause[i]; i++)
160 {
161 gcc_checking_assert (i < max_clauses);
162 }
163
164 /* Combine the predicates rest. */
165 for (; p.m_clause[i]; i++)
166 {
167 gcc_checking_assert (i < max_clauses);
168 add_clause (NULL, p.m_clause[i]);
169 }
170 return *this;
171 }
172
173
174
175 /* Return THIS | P2. */
176
177 predicate
or_with(conditions conditions,const predicate & p)178 predicate::or_with (conditions conditions,
179 const predicate &p) const
180 {
181 /* Avoid busy work. */
182 if (p == false || *this == true || *this == p)
183 return *this;
184 if (*this == false || p == true)
185 return p;
186
187 /* OK, combine the predicates. */
188 predicate out = true;
189
190 for (int i = 0; m_clause[i]; i++)
191 for (int j = 0; p.m_clause[j]; j++)
192 {
193 gcc_checking_assert (i < max_clauses && j < max_clauses);
194 out.add_clause (conditions, m_clause[i] | p.m_clause[j]);
195 }
196 return out;
197 }
198
199
200 /* Having partial truth assignment in POSSIBLE_TRUTHS, return false
201 if predicate P is known to be false. */
202
203 bool
evaluate(clause_t possible_truths)204 predicate::evaluate (clause_t possible_truths) const
205 {
206 int i;
207
208 /* True remains true. */
209 if (*this == true)
210 return true;
211
212 gcc_assert (!(possible_truths & (1 << predicate::false_condition)));
213
214 /* See if we can find clause we can disprove. */
215 for (i = 0; m_clause[i]; i++)
216 {
217 gcc_checking_assert (i < max_clauses);
218 if (!(m_clause[i] & possible_truths))
219 return false;
220 }
221 return true;
222 }
223
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. */
226
227 int
probability(conditions conds,clause_t possible_truths,vec<inline_param_summary> inline_param_summary)228 predicate::probability (conditions conds,
229 clause_t possible_truths,
230 vec<inline_param_summary> inline_param_summary) const
231 {
232 int i;
233 int combined_prob = REG_BR_PROB_BASE;
234
235 /* True remains true. */
236 if (*this == true)
237 return REG_BR_PROB_BASE;
238
239 if (*this == false)
240 return 0;
241
242 gcc_assert (!(possible_truths & (1 << 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 0;
250 else
251 {
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))
258 {
259 if (i2 >= predicate::first_dynamic_condition)
260 {
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 ()))
266 {
267 int iprob =
268 inline_param_summary[c->operand_num].change_prob;
269 this_prob = MAX (this_prob, iprob);
270 }
271 else
272 this_prob = REG_BR_PROB_BASE;
273 }
274 else
275 this_prob = REG_BR_PROB_BASE;
276 }
277 combined_prob = MIN (this_prob, combined_prob);
278 if (!combined_prob)
279 return 0;
280 }
281 }
282 return combined_prob;
283 }
284
285
286 /* Dump conditional COND. */
287
288 void
dump_condition(FILE * f,conditions conditions,int cond)289 dump_condition (FILE *f, conditions conditions, int cond)
290 {
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
297 {
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)
304 {
305 fprintf (f, " not constant");
306 return;
307 }
308 if (c->code == predicate::changed)
309 {
310 fprintf (f, " changed");
311 return;
312 }
313 fprintf (f, " %s ", op_symbol_code (c->code));
314 print_generic_expr (f, c->val);
315 }
316 }
317
318
319 /* Dump clause CLAUSE. */
320
321 static void
dump_clause(FILE * f,conditions conds,clause_t clause)322 dump_clause (FILE *f, conditions conds, clause_t clause)
323 {
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))
331 {
332 if (found)
333 fprintf (f, " || ");
334 found = true;
335 dump_condition (f, conds, i);
336 }
337 fprintf (f, ")");
338 }
339
340
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. */
343
344 void
dump(FILE * f,conditions conds,bool nl)345 predicate::dump (FILE *f, conditions conds, bool nl) const
346 {
347 int i;
348 if (*this == true)
349 dump_clause (f, conds, 0);
350 else
351 for (i = 0; m_clause[i]; i++)
352 {
353 if (i)
354 fprintf (f, " && ");
355 dump_clause (f, conds, m_clause[i]);
356 }
357 if (nl)
358 fprintf (f, "\n");
359 }
360
361
362 void
debug(conditions conds)363 predicate::debug (conditions conds) const
364 {
365 dump (stderr, conds);
366 }
367
368
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. */
372
373 predicate
remap_after_duplication(clause_t possible_truths)374 predicate::remap_after_duplication (clause_t possible_truths)
375 {
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;
384 }
385
386
387 /* Translate all conditions from callee representation into caller
388 representation and symbolically evaluate predicate THIS into new predicate.
389
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). */
399
400 predicate
remap_after_inlining(struct ipa_fn_summary * info,struct ipa_fn_summary * callee_info,vec<int> operand_map,vec<int> offset_map,clause_t possible_truths,const predicate & toplev_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)
407 {
408 int i;
409 predicate out = true;
410
411 /* True predicate is easy. */
412 if (*this == true)
413 return toplev_predicate;
414 for (i = 0; m_clause[i]; i++)
415 {
416 clause_t clause = m_clause[i];
417 int cond;
418 predicate clause_predicate = false;
419
420 gcc_assert (i < max_clauses);
421
422 for (cond = 0; cond < num_conditions; cond++)
423 /* Do we have condition we can't disprove? */
424 if (clause & possible_truths & (1 << cond))
425 {
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)
430 {
431 struct condition *c;
432
433 c = &(*callee_info->conds)[cond
434 -
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
450 {
451 struct agg_position_info ap;
452 HOST_WIDE_INT offset_delta = offset_map[c->operand_num];
453 if (offset_delta < 0)
454 {
455 gcc_checking_assert (!c->agg_contents || !c->by_ref);
456 offset_delta = 0;
457 }
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);
467 }
468 }
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);
475 }
476 out &= clause_predicate;
477 }
478 out &= toplev_predicate;
479 return out;
480 }
481
482
483 /* Read predicate from IB. */
484
485 void
stream_in(struct lto_input_block * ib)486 predicate::stream_in (struct lto_input_block *ib)
487 {
488 clause_t clause;
489 int k = 0;
490
491 do
492 {
493 gcc_assert (k <= max_clauses);
494 clause = m_clause[k++] = streamer_read_uhwi (ib);
495 }
496 while (clause);
497
498 /* Zero-initialize the remaining clauses in OUT. */
499 while (k <= max_clauses)
500 m_clause[k++] = 0;
501 }
502
503
504 /* Write predicate P to OB. */
505
506 void
stream_out(struct output_block * ob)507 predicate::stream_out (struct output_block *ob)
508 {
509 int j;
510 for (j = 0; m_clause[j]; j++)
511 {
512 gcc_assert (j < max_clauses);
513 streamer_write_uhwi (ob, m_clause[j]);
514 }
515 streamer_write_uhwi (ob, 0);
516 }
517
518
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. */
523
524 predicate
add_condition(struct ipa_fn_summary * summary,int operand_num,HOST_WIDE_INT size,struct agg_position_info * aggpos,enum tree_code code,tree val)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)
528 {
529 int i;
530 struct condition *c;
531 struct condition new_cond;
532 HOST_WIDE_INT offset;
533 bool agg_contents, by_ref;
534
535 if (aggpos)
536 {
537 offset = aggpos->offset;
538 agg_contents = aggpos->agg_contents;
539 by_ref = aggpos->by_ref;
540 }
541 else
542 {
543 offset = 0;
544 agg_contents = false;
545 by_ref = false;
546 }
547
548 gcc_checking_assert (operand_num >= 0);
549 for (i = 0; vec_safe_iterate (summary->conds, i, &c); i++)
550 {
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);
558 }
559 /* Too many conditions. Give up and return constant true. */
560 if (i == predicate::num_conditions - predicate::first_dynamic_condition)
561 return true;
562
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);
571
572 return predicate::predicate_testing_cond (i);
573 }
574