gcc/ipa-predicate.c

   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 }