Mercurial > hg > CbC > CbC_gcc
comparison gcc/ipa-predicate.c @ 111:04ced10e8804
gcc 7
author | kono |
---|---|
date | Fri, 27 Oct 2017 22:46:09 +0900 |
parents | |
children | 84e7813d76e9 |
comparison
equal
deleted
inserted
replaced
68:561a7518be6b | 111:04ced10e8804 |
---|---|
1 /* IPA predicates. | |
2 Copyright (C) 2003-2017 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 | |
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 } |