]>
Commit | Line | Data |
---|---|---|
4669dd83 | 1 | /* IPA predicates. |
fbd26352 | 2 | Copyright (C) 2003-2019 Free Software Foundation, Inc. |
4669dd83 | 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" | |
b9a58fc5 | 31 | #include "ipa-fnsummary.h" |
4669dd83 | 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 | ||
1297cbcd | 390 | INFO is ipa_fn_summary of function we are adding predicate into, CALLEE_INFO |
4669dd83 | 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 | |
2e966e2a | 401 | predicate::remap_after_inlining (class ipa_fn_summary *info, |
402 | class ipa_fn_summary *callee_info, | |
4669dd83 | 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 | |
2e966e2a | 486 | predicate::stream_in (class lto_input_block *ib) |
4669dd83 | 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 | |
2e966e2a | 525 | add_condition (class ipa_fn_summary *summary, int operand_num, |
c47e61e1 | 526 | poly_int64 size, struct agg_position_info *aggpos, |
4669dd83 | 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 | |
b7bd8833 | 552 | && known_eq (c->size, size) |
4669dd83 | 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 | } |