111
|
1 /* IPA predicates.
|
131
|
2 Copyright (C) 2003-2018 Free Software Foundation, Inc.
|
111
|
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
|
|
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
|
|
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
|
|
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
|
|
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
|
|
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
|
|
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
|
|
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
|
|
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
|
|
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
|
|
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
|
|
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
|
|
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
|
|
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 }
|