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 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 } 574