gcc/ipa-predicate.cc

   1 /* IPA predicates.
   2    Copyright (C) 2003-2024 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 "alloc-pool.h"
  29 #include "symbol-summary.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 "gimplify.h"
  37 #include "data-streamer.h"
  38
  39
  40 /* Check whether two set of operations have same effects.  */
  41 static bool
  42 expr_eval_ops_equal_p (expr_eval_ops ops1, expr_eval_ops ops2)
  43 {
  44   if (ops1)
  45     {
  46       if (!ops2 || ops1->length () != ops2->length ())
  47         return false;
  48
  49       for (unsigned i = 0; i < ops1->length (); i++)
  50         {
  51           expr_eval_op &op1 = (*ops1)[i];
  52           expr_eval_op &op2 = (*ops2)[i];
  53
  54           if (op1.code != op2.code
  55               || op1.index != op2.index
  56               || !vrp_operand_equal_p (op1.val[0], op2.val[0])
  57               || !vrp_operand_equal_p (op1.val[1], op2.val[1])
  58               || !types_compatible_p (op1.type, op2.type))
  59             return false;
  60         }
  61       return true;
  62     }
  63   return !ops2;
  64 }
  65
  66 /* Add clause CLAUSE into the predicate P.
  67    When CONDITIONS is NULL do not perform checking whether NEW_CLAUSE
  68    is obviously true.  This is useful only when NEW_CLAUSE is known to be
  69    sane.  */
  70
  71 void
  72 ipa_predicate::add_clause (conditions conditions, clause_t new_clause)
  73 {
  74   int i;
  75   int i2;
  76   int insert_here = -1;
  77   int c1, c2;
  78
  79   /* True clause.  */
  80   if (!new_clause)
  81     return;
  82
  83   /* False clause makes the whole predicate false.  Kill the other variants.  */
  84   if (new_clause == (1 << ipa_predicate::false_condition))
  85     {
  86       *this = false;
  87       return;
  88     }
  89   if (*this == false)
  90     return;
  91
  92   /* No one should be silly enough to add false into nontrivial clauses.  */
  93   gcc_checking_assert (!(new_clause & (1 << ipa_predicate::false_condition)));
  94
  95   /* Look where to insert the new_clause.  At the same time prune out
  96      new_clauses of P that are implied by the new new_clause and thus
  97      redundant.  */
  98   for (i = 0, i2 = 0; i <= max_clauses; i++)
  99     {
 100       m_clause[i2] = m_clause[i];
 101
 102       if (!m_clause[i])
 103         break;
 104
 105       /* If m_clause[i] implies new_clause, there is nothing to add.  */
 106       if ((m_clause[i] & new_clause) == m_clause[i])
 107         {
 108           /* We had nothing to add, none of clauses should've become
 109              redundant.  */
 110           gcc_checking_assert (i == i2);
 111           return;
 112         }
 113
 114       if (m_clause[i] < new_clause && insert_here < 0)
 115         insert_here = i2;
 116
 117       /* If new_clause implies clause[i], then clause[i] becomes redundant.
 118          Otherwise the clause[i] has to stay.  */
 119       if ((m_clause[i] & new_clause) != new_clause)
 120         i2++;
 121     }
 122
 123   /* Look for clauses that are obviously true.  I.e.
 124      op0 == 5 || op0 != 5.  */
 125   if (conditions)
 126     for (c1 = ipa_predicate::first_dynamic_condition;
 127          c1 < num_conditions; c1++)
 128       {
 129         condition *cc1;
 130         if (!(new_clause & (1 << c1)))
 131           continue;
 132         cc1 = &(*conditions)[c1 - ipa_predicate::first_dynamic_condition];
 133         /* We have no way to represent !changed and !is_not_constant
 134            and thus there is no point for looking for them.  */
 135         if (cc1->code == changed || cc1->code == is_not_constant || cc1->code == not_sra_candidate)
 136           continue;
 137         for (c2 = c1 + 1; c2 < num_conditions; c2++)
 138           if (new_clause & (1 << c2))
 139             {
 140               condition *cc2 =
 141                 &(*conditions)[c2 - ipa_predicate::first_dynamic_condition];
 142               if (cc1->operand_num == cc2->operand_num
 143                   && vrp_operand_equal_p (cc1->val, cc2->val)
 144                   && cc2->code != is_not_constant
 145                   && cc2->code != not_sra_candidate
 146                   && cc2->code != changed
 147                   && expr_eval_ops_equal_p (cc1->param_ops, cc2->param_ops)
 148                   && cc2->agg_contents == cc1->agg_contents
 149                   && cc2->by_ref == cc1->by_ref
 150                   && types_compatible_p (cc2->type, cc1->type)
 151                   && cc1->code == invert_tree_comparison (cc2->code,
 152                                                           HONOR_NANS (cc1->val)))
 153                 return;
 154             }
 155       }
 156
 157
 158   /* We run out of variants.  Be conservative in positive direction.  */
 159   if (i2 == max_clauses)
 160     return;
 161   /* Keep clauses in decreasing order. This makes equivalence testing easy.  */
 162   m_clause[i2 + 1] = 0;
 163   if (insert_here >= 0)
 164     for (; i2 > insert_here; i2--)
 165       m_clause[i2] = m_clause[i2 - 1];
 166   else
 167     insert_here = i2;
 168   m_clause[insert_here] = new_clause;
 169 }
 170
 171
 172 /* Do THIS &= P.  */
 173
 174 ipa_predicate &
 175 ipa_predicate::operator &= (const ipa_predicate &p)
 176 {
 177   /* Avoid busy work.  */
 178   if (p == false || *this == true)
 179     {
 180       *this = p;
 181       return *this;
 182     }
 183   if (*this == false || p == true || this == &p)
 184     return *this;
 185
 186   int i;
 187
 188   /* See how far ipa_predicates match.  */
 189   for (i = 0; m_clause[i] && m_clause[i] == p.m_clause[i]; i++)
 190     {
 191       gcc_checking_assert (i < max_clauses);
 192     }
 193
 194   /* Combine the ipa_predicates rest.  */
 195   for (; p.m_clause[i]; i++)
 196     {
 197       gcc_checking_assert (i < max_clauses);
 198       add_clause (NULL, p.m_clause[i]);
 199     }
 200   return *this;
 201 }
 202
 203
 204
 205 /* Return THIS | P2.  */
 206
 207 ipa_predicate
 208 ipa_predicate::or_with (conditions conditions,
 209                         const ipa_predicate &p) const
 210 {
 211   /* Avoid busy work.  */
 212   if (p == false || *this == true || *this == p)
 213     return *this;
 214   if (*this == false || p == true)
 215     return p;
 216
 217   /* OK, combine the predicates.  */
 218   ipa_predicate out = true;
 219
 220   for (int i = 0; m_clause[i]; i++)
 221     for (int j = 0; p.m_clause[j]; j++)
 222       {
 223         gcc_checking_assert (i < max_clauses && j < max_clauses);
 224         out.add_clause (conditions, m_clause[i] | p.m_clause[j]);
 225       }
 226   return out;
 227 }
 228
 229
 230 /* Having partial truth assignment in POSSIBLE_TRUTHS, return false
 231    if predicate P is known to be false.  */
 232
 233 bool
 234 ipa_predicate::evaluate (clause_t possible_truths) const
 235 {
 236   int i;
 237
 238   /* True remains true.  */
 239   if (*this == true)
 240     return true;
 241
 242   gcc_assert (!(possible_truths & (1 << ipa_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 false;
 250     }
 251   return true;
 252 }
 253
 254 /* Return the probability in range 0...REG_BR_PROB_BASE that the predicated
 255    instruction will be recomputed per invocation of the inlined call.  */
 256
 257 int
 258 ipa_predicate::probability (conditions conds,
 259                         clause_t possible_truths,
 260                         vec<inline_param_summary> inline_param_summary) const
 261 {
 262   int i;
 263   int combined_prob = REG_BR_PROB_BASE;
 264
 265   /* True remains true.  */
 266   if (*this == true)
 267     return REG_BR_PROB_BASE;
 268
 269   if (*this == false)
 270     return 0;
 271
 272   gcc_assert (!(possible_truths & (1 << ipa_predicate::false_condition)));
 273
 274   /* See if we can find clause we can disprove.  */
 275   for (i = 0; m_clause[i]; i++)
 276     {
 277       gcc_checking_assert (i < max_clauses);
 278       if (!(m_clause[i] & possible_truths))
 279         return 0;
 280       else
 281         {
 282           int this_prob = 0;
 283           int i2;
 284           if (!inline_param_summary.exists ())
 285             return REG_BR_PROB_BASE;
 286           for (i2 = 0; i2 < num_conditions; i2++)
 287             if ((m_clause[i] & possible_truths) & (1 << i2))
 288               {
 289                 if (i2 >= ipa_predicate::first_dynamic_condition)
 290                   {
 291                     condition *c =
 292                       &(*conds)[i2 - ipa_predicate::first_dynamic_condition];
 293                     if (c->code == ipa_predicate::changed
 294                         && (c->operand_num <
 295                             (int) inline_param_summary.length ()))
 296                       {
 297                         int iprob =
 298                           inline_param_summary[c->operand_num].change_prob;
 299                         this_prob = MAX (this_prob, iprob);
 300                       }
 301                     else
 302                       this_prob = REG_BR_PROB_BASE;
 303                   }
 304                 else
 305                   this_prob = REG_BR_PROB_BASE;
 306               }
 307           combined_prob = MIN (this_prob, combined_prob);
 308           if (!combined_prob)
 309             return 0;
 310         }
 311     }
 312   return combined_prob;
 313 }
 314
 315
 316 /* Dump conditional COND.  */
 317
 318 void
 319 dump_condition (FILE *f, conditions conditions, int cond)
 320 {
 321   condition *c;
 322   if (cond == ipa_predicate::false_condition)
 323     fprintf (f, "false");
 324   else if (cond == ipa_predicate::not_inlined_condition)
 325     fprintf (f, "not inlined");
 326   else
 327     {
 328       c = &(*conditions)[cond - ipa_predicate::first_dynamic_condition];
 329       fprintf (f, "op%i", c->operand_num);
 330       if (c->agg_contents)
 331         fprintf (f, "[%soffset: " HOST_WIDE_INT_PRINT_DEC "]",
 332                  c->by_ref ? "ref " : "", c->offset);
 333
 334       for (unsigned i = 0; i < vec_safe_length (c->param_ops); i++)
 335         {
 336           expr_eval_op &op = (*(c->param_ops))[i];
 337           const char *op_name = op_symbol_code (op.code);
 338
 339           if (op_name == op_symbol_code (ERROR_MARK))
 340             op_name = get_tree_code_name (op.code);
 341
 342           fprintf (f, ",(");
 343
 344           if (!op.val[0])
 345             {
 346               switch (op.code)
 347                 {
 348                 case FLOAT_EXPR:
 349                 case FIX_TRUNC_EXPR:
 350                 case FIXED_CONVERT_EXPR:
 351                 case VIEW_CONVERT_EXPR:
 352                 CASE_CONVERT:
 353                   if (op.code == VIEW_CONVERT_EXPR)
 354                     fprintf (f, "VCE");
 355                   fprintf (f, "(");
 356                   print_generic_expr (f, op.type);
 357                   fprintf (f, ")" );
 358                   break;
 359
 360                 default:
 361                   fprintf (f, "%s", op_name);
 362                 }
 363               fprintf (f, " #");
 364             }
 365           else if (!op.val[1])
 366             {
 367               if (op.index)
 368                 {
 369                   print_generic_expr (f, op.val[0]);
 370                   fprintf (f, " %s #", op_name);
 371                 }
 372               else
 373                 {
 374                   fprintf (f, "# %s ", op_name);
 375                   print_generic_expr (f, op.val[0]);
 376                 }
 377             }
 378           else
 379             {
 380               fprintf (f, "%s ", op_name);
 381               switch (op.index)
 382                 {
 383                 case 0:
 384                   fprintf (f, "#, ");
 385                   print_generic_expr (f, op.val[0]);
 386                   fprintf (f, ", ");
 387                   print_generic_expr (f, op.val[1]);
 388                   break;
 389
 390                 case 1:
 391                   print_generic_expr (f, op.val[0]);
 392                   fprintf (f, ", #, ");
 393                   print_generic_expr (f, op.val[1]);
 394                   break;
 395
 396                 case 2:
 397                   print_generic_expr (f, op.val[0]);
 398                   fprintf (f, ", ");
 399                   print_generic_expr (f, op.val[1]);
 400                   fprintf (f, ", #");
 401                   break;
 402
 403                 default:
 404                   fprintf (f, "*, *, *");
 405                 }
 406             }
 407           fprintf (f, ")");
 408         }
 409
 410       if (c->code == ipa_predicate::is_not_constant)
 411         {
 412           fprintf (f, " not constant");
 413           return;
 414         }
 415       if (c->code == ipa_predicate::changed)
 416         {
 417           fprintf (f, " changed");
 418           return;
 419         }
 420       if (c->code == ipa_predicate::not_sra_candidate)
 421         {
 422           fprintf (f, " not sra candidate");
 423           return;
 424         }
 425       fprintf (f, " %s ", op_symbol_code (c->code));
 426       print_generic_expr (f, c->val);
 427     }
 428 }
 429
 430
 431 /* Dump clause CLAUSE.  */
 432
 433 static void
 434 dump_clause (FILE *f, conditions conds, clause_t clause)
 435 {
 436   int i;
 437   bool found = false;
 438   fprintf (f, "(");
 439   if (!clause)
 440     fprintf (f, "true");
 441   for (i = 0; i < ipa_predicate::num_conditions; i++)
 442     if (clause & (1 << i))
 443       {
 444         if (found)
 445           fprintf (f, " || ");
 446         found = true;
 447         dump_condition (f, conds, i);
 448       }
 449   fprintf (f, ")");
 450 }
 451
 452
 453 /* Dump THIS to F.  CONDS a vector of conditions used when evaluating
 454    ipa_predicates.  When NL is true new line is output at the end of dump.  */
 455
 456 void
 457 ipa_predicate::dump (FILE *f, conditions conds, bool nl) const
 458 {
 459   int i;
 460   if (*this == true)
 461     dump_clause (f, conds, 0);
 462   else
 463     for (i = 0; m_clause[i]; i++)
 464       {
 465         if (i)
 466           fprintf (f, " && ");
 467         dump_clause (f, conds, m_clause[i]);
 468       }
 469   if (nl)
 470     fprintf (f, "\n");
 471 }
 472
 473
 474 void
 475 ipa_predicate::debug (conditions conds) const
 476 {
 477   dump (stderr, conds);
 478 }
 479
 480
 481 /* Remap predicate THIS of former function to be predicate of duplicated function.
 482    POSSIBLE_TRUTHS is clause of possible truths in the duplicated node,
 483    INFO is inline summary of the duplicated node.  */
 484
 485 ipa_predicate
 486 ipa_predicate::remap_after_duplication (clause_t possible_truths)
 487 {
 488   int j;
 489   ipa_predicate out = true;
 490   for (j = 0; m_clause[j]; j++)
 491     if (!(possible_truths & m_clause[j]))
 492       return false;
 493     else
 494       out.add_clause (NULL, possible_truths & m_clause[j]);
 495   return out;
 496 }
 497
 498
 499 /* Translate all conditions from callee representation into caller
 500    representation and symbolically evaluate predicate THIS into new predicate.
 501
 502    INFO is ipa_fn_summary of function we are adding predicate into, CALLEE_INFO
 503    is summary of function predicate P is from. OPERAND_MAP is array giving
 504    callee formal IDs the caller formal IDs. POSSSIBLE_TRUTHS is clause of all
 505    callee conditions that may be true in caller context.  TOPLEV_PREDICATE is
 506    predicate under which callee is executed.  OFFSET_MAP is an array of
 507    offsets that need to be added to conditions, negative offset means that
 508    conditions relying on values passed by reference have to be discarded
 509    because they might not be preserved (and should be considered offset zero
 510    for other purposes).  */
 511
 512 ipa_predicate
 513 ipa_predicate::remap_after_inlining (class ipa_fn_summary *info,
 514                                  class ipa_node_params *params_summary,
 515                                  class ipa_fn_summary *callee_info,
 516                                  const vec<int> &operand_map,
 517                                  const vec<HOST_WIDE_INT> &offset_map,
 518                                  clause_t possible_truths,
 519                                  const ipa_predicate &toplev_predicate)
 520 {
 521   int i;
 522   ipa_predicate out = true;
 523
 524   /* True ipa_predicate is easy.  */
 525   if (*this == true)
 526     return toplev_predicate;
 527   for (i = 0; m_clause[i]; i++)
 528     {
 529       clause_t clause = m_clause[i];
 530       int cond;
 531       ipa_predicate clause_predicate = false;
 532
 533       gcc_assert (i < max_clauses);
 534
 535       for (cond = 0; cond < num_conditions; cond++)
 536         /* Do we have condition we can't disprove?   */
 537         if (clause & possible_truths & (1 << cond))
 538           {
 539             ipa_predicate cond_predicate;
 540             /* Work out if the condition can translate to predicate in the
 541                inlined function.  */
 542             if (cond >= ipa_predicate::first_dynamic_condition)
 543               {
 544                 struct condition *c;
 545
 546                 int index = cond - ipa_predicate::first_dynamic_condition;
 547                 c = &(*callee_info->conds)[index];
 548                 /* See if we can remap condition operand to caller's operand.
 549                    Otherwise give up.  */
 550                 if (!operand_map.exists ()
 551                     || (int) operand_map.length () <= c->operand_num
 552                     || operand_map[c->operand_num] == -1
 553                     /* TODO: For non-aggregate conditions, adding an offset is
 554                        basically an arithmetic jump function processing which
 555                        we should support in future.  */
 556                     || ((!c->agg_contents || !c->by_ref)
 557                         && offset_map[c->operand_num] > 0)
 558                     || (c->agg_contents && c->by_ref
 559                         && offset_map[c->operand_num] < 0))
 560                   cond_predicate = true;
 561                 else
 562                   {
 563                     struct agg_position_info ap;
 564                     HOST_WIDE_INT offset_delta = offset_map[c->operand_num];
 565                     if (offset_delta < 0)
 566                       {
 567                         gcc_checking_assert (!c->agg_contents || !c->by_ref);
 568                         offset_delta = 0;
 569                       }
 570                     gcc_assert (!c->agg_contents
 571                                 || c->by_ref || offset_delta == 0);
 572                     ap.offset = c->offset + offset_delta;
 573                     ap.agg_contents = c->agg_contents;
 574                     ap.by_ref = c->by_ref;
 575                     cond_predicate = add_condition (info, params_summary,
 576                                                     operand_map[c->operand_num],
 577                                                     c->type, &ap, c->code,
 578                                                     c->val, c->param_ops);
 579                   }
 580               }
 581             /* Fixed conditions remains same, construct single
 582                condition predicate.  */
 583             else
 584               cond_predicate = ipa_predicate::predicate_testing_cond (cond);
 585             clause_predicate = clause_predicate.or_with (info->conds,
 586                                                          cond_predicate);
 587           }
 588       out &= clause_predicate;
 589     }
 590   out &= toplev_predicate;
 591   return out;
 592 }
 593
 594
 595 /* Read predicate from IB.  */
 596
 597 void
 598 ipa_predicate::stream_in (class lto_input_block *ib)
 599 {
 600   clause_t clause;
 601   int k = 0;
 602
 603   do
 604     {
 605       gcc_assert (k <= max_clauses);
 606       clause = m_clause[k++] = streamer_read_uhwi (ib);
 607     }
 608   while (clause);
 609
 610   /* Zero-initialize the remaining clauses in OUT.  */
 611   while (k <= max_clauses)
 612     m_clause[k++] = 0;
 613 }
 614
 615
 616 /* Write predicate P to OB.  */
 617
 618 void
 619 ipa_predicate::stream_out (struct output_block *ob)
 620 {
 621   int j;
 622   for (j = 0; m_clause[j]; j++)
 623     {
 624       gcc_assert (j < max_clauses);
 625       streamer_write_uhwi (ob, m_clause[j]);
 626     }
 627   streamer_write_uhwi (ob, 0);
 628 }
 629
 630
 631 /* Add condition to condition list SUMMARY.  OPERAND_NUM, TYPE, CODE, VAL and
 632    PARAM_OPS correspond to fields of condition structure.  AGGPOS describes
 633    whether the used operand is loaded from an aggregate and where in the
 634    aggregate it is.  It can be NULL, which means this not a load from an
 635    aggregate.  */
 636
 637 ipa_predicate
 638 add_condition (class ipa_fn_summary *summary,
 639                class ipa_node_params *params_summary,
 640                int operand_num,
 641                tree type, struct agg_position_info *aggpos,
 642                enum tree_code code, tree val, expr_eval_ops param_ops)
 643 {
 644   int i, j;
 645   struct condition *c;
 646   struct condition new_cond;
 647   HOST_WIDE_INT offset;
 648   bool agg_contents, by_ref;
 649   expr_eval_op *op;
 650
 651   if (params_summary)
 652     ipa_set_param_used_by_ipa_predicates (params_summary, operand_num, true);
 653
 654   if (aggpos)
 655     {
 656       offset = aggpos->offset;
 657       agg_contents = aggpos->agg_contents;
 658       by_ref = aggpos->by_ref;
 659     }
 660   else
 661     {
 662       offset = 0;
 663       agg_contents = false;
 664       by_ref = false;
 665     }
 666
 667   gcc_checking_assert (operand_num >= 0);
 668   for (i = 0; vec_safe_iterate (summary->conds, i, &c); i++)
 669     {
 670       if (c->operand_num == operand_num
 671           && c->code == code
 672           && types_compatible_p (c->type, type)
 673           && vrp_operand_equal_p (c->val, val)
 674           && c->agg_contents == agg_contents
 675           && expr_eval_ops_equal_p (c->param_ops, param_ops)
 676           && (!agg_contents || (c->offset == offset && c->by_ref == by_ref)))
 677         return ipa_predicate::predicate_testing_cond (i);
 678     }
 679   /* Too many conditions.  Give up and return constant true.  */
 680   if (i == ipa_predicate::num_conditions - ipa_predicate::first_dynamic_condition)
 681     return true;
 682
 683   new_cond.operand_num = operand_num;
 684   new_cond.code = code;
 685   new_cond.type = unshare_expr_without_location (type);
 686   new_cond.val = val ? unshare_expr_without_location (val) : val;
 687   new_cond.agg_contents = agg_contents;
 688   new_cond.by_ref = by_ref;
 689   new_cond.offset = offset;
 690   new_cond.param_ops = vec_safe_copy (param_ops);
 691
 692   for (j = 0; vec_safe_iterate (new_cond.param_ops, j, &op); j++)
 693     {
 694       if (op->val[0])
 695         op->val[0] = unshare_expr_without_location (op->val[0]);
 696       if (op->val[1])
 697         op->val[1] = unshare_expr_without_location (op->val[1]);
 698     }
 699
 700   vec_safe_push (summary->conds, new_cond);
 701
 702   return ipa_predicate::predicate_testing_cond (i);
 703 }