lib/Transforms/Utils/PredicateInfo.cpp

   1 //===-- PredicateInfo.cpp - PredicateInfo Builder--------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------===//
   8 //
   9 // This file implements the PredicateInfo class.
  10 //
  11 //===----------------------------------------------------------------===//
  12
  13 #include "llvm/Transforms/Utils/PredicateInfo.h"
  14 #include "llvm/ADT/DenseMap.h"
  15 #include "llvm/ADT/DepthFirstIterator.h"
  16 #include "llvm/ADT/STLExtras.h"
  17 #include "llvm/ADT/SmallPtrSet.h"
  18 #include "llvm/ADT/Statistic.h"
  19 #include "llvm/ADT/StringExtras.h"
  20 #include "llvm/Analysis/AssumptionCache.h"
  21 #include "llvm/Analysis/CFG.h"
  22 #include "llvm/IR/AssemblyAnnotationWriter.h"
  23 #include "llvm/IR/DataLayout.h"
  24 #include "llvm/IR/Dominators.h"
  25 #include "llvm/IR/GlobalVariable.h"
  26 #include "llvm/IR/IRBuilder.h"
  27 #include "llvm/IR/InstIterator.h"
  28 #include "llvm/IR/IntrinsicInst.h"
  29 #include "llvm/IR/LLVMContext.h"
  30 #include "llvm/IR/Metadata.h"
  31 #include "llvm/IR/Module.h"
  32 #include "llvm/IR/PatternMatch.h"
  33 #include "llvm/Support/Debug.h"
  34 #include "llvm/Support/DebugCounter.h"
  35 #include "llvm/Support/FormattedStream.h"
  36 #include "llvm/Transforms/Utils.h"
  37 #include <algorithm>
  38 #define DEBUG_TYPE "predicateinfo"
  39 using namespace llvm;
  40 using namespace PatternMatch;
  41 using namespace llvm::PredicateInfoClasses;
  42
  43 INITIALIZE_PASS_BEGIN(PredicateInfoPrinterLegacyPass, "print-predicateinfo",
  44                       "PredicateInfo Printer", false, false)
  45 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
  46 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
  47 INITIALIZE_PASS_END(PredicateInfoPrinterLegacyPass, "print-predicateinfo",
  48                     "PredicateInfo Printer", false, false)
  49 static cl::opt<bool> VerifyPredicateInfo(
  50     "verify-predicateinfo", cl::init(false), cl::Hidden,
  51     cl::desc("Verify PredicateInfo in legacy printer pass."));
  52 DEBUG_COUNTER(RenameCounter, "predicateinfo-rename",
  53               "Controls which variables are renamed with predicateinfo");
  54
  55 namespace {
  56 // Given a predicate info that is a type of branching terminator, get the
  57 // branching block.
  58 const BasicBlock *getBranchBlock(const PredicateBase *PB) {
  59   assert(isa<PredicateWithEdge>(PB) &&
  60          "Only branches and switches should have PHIOnly defs that "
  61          "require branch blocks.");
  62   return cast<PredicateWithEdge>(PB)->From;
  63 }
  64
  65 // Given a predicate info that is a type of branching terminator, get the
  66 // branching terminator.
  67 static Instruction *getBranchTerminator(const PredicateBase *PB) {
  68   assert(isa<PredicateWithEdge>(PB) &&
  69          "Not a predicate info type we know how to get a terminator from.");
  70   return cast<PredicateWithEdge>(PB)->From->getTerminator();
  71 }
  72
  73 // Given a predicate info that is a type of branching terminator, get the
  74 // edge this predicate info represents
  75 const std::pair<BasicBlock *, BasicBlock *>
  76 getBlockEdge(const PredicateBase *PB) {
  77   assert(isa<PredicateWithEdge>(PB) &&
  78          "Not a predicate info type we know how to get an edge from.");
  79   const auto *PEdge = cast<PredicateWithEdge>(PB);
  80   return std::make_pair(PEdge->From, PEdge->To);
  81 }
  82 }
  83
  84 namespace llvm {
  85 namespace PredicateInfoClasses {
  86 enum LocalNum {
  87   // Operations that must appear first in the block.
  88   LN_First,
  89   // Operations that are somewhere in the middle of the block, and are sorted on
  90   // demand.
  91   LN_Middle,
  92   // Operations that must appear last in a block, like successor phi node uses.
  93   LN_Last
  94 };
  95
  96 // Associate global and local DFS info with defs and uses, so we can sort them
  97 // into a global domination ordering.
  98 struct ValueDFS {
  99   int DFSIn = 0;
 100   int DFSOut = 0;
 101   unsigned int LocalNum = LN_Middle;
 102   // Only one of Def or Use will be set.
 103   Value *Def = nullptr;
 104   Use *U = nullptr;
 105   // Neither PInfo nor EdgeOnly participate in the ordering
 106   PredicateBase *PInfo = nullptr;
 107   bool EdgeOnly = false;
 108 };
 109
 110 // Perform a strict weak ordering on instructions and arguments.
 111 static bool valueComesBefore(OrderedInstructions &OI, const Value *A,
 112                              const Value *B) {
 113   auto *ArgA = dyn_cast_or_null<Argument>(A);
 114   auto *ArgB = dyn_cast_or_null<Argument>(B);
 115   if (ArgA && !ArgB)
 116     return true;
 117   if (ArgB && !ArgA)
 118     return false;
 119   if (ArgA && ArgB)
 120     return ArgA->getArgNo() < ArgB->getArgNo();
 121   return OI.dfsBefore(cast<Instruction>(A), cast<Instruction>(B));
 122 }
 123
 124 // This compares ValueDFS structures, creating OrderedBasicBlocks where
 125 // necessary to compare uses/defs in the same block.  Doing so allows us to walk
 126 // the minimum number of instructions necessary to compute our def/use ordering.
 127 struct ValueDFS_Compare {
 128   DominatorTree &DT;
 129   OrderedInstructions &OI;
 130   ValueDFS_Compare(DominatorTree &DT, OrderedInstructions &OI)
 131       : DT(DT), OI(OI) {}
 132
 133   bool operator()(const ValueDFS &A, const ValueDFS &B) const {
 134     if (&A == &B)
 135       return false;
 136     // The only case we can't directly compare them is when they in the same
 137     // block, and both have localnum == middle.  In that case, we have to use
 138     // comesbefore to see what the real ordering is, because they are in the
 139     // same basic block.
 140
 141     assert((A.DFSIn != B.DFSIn || A.DFSOut == B.DFSOut) &&
 142            "Equal DFS-in numbers imply equal out numbers");
 143     bool SameBlock = A.DFSIn == B.DFSIn;
 144
 145     // We want to put the def that will get used for a given set of phi uses,
 146     // before those phi uses.
 147     // So we sort by edge, then by def.
 148     // Note that only phi nodes uses and defs can come last.
 149     if (SameBlock && A.LocalNum == LN_Last && B.LocalNum == LN_Last)
 150       return comparePHIRelated(A, B);
 151
 152     bool isADef = A.Def;
 153     bool isBDef = B.Def;
 154     if (!SameBlock || A.LocalNum != LN_Middle || B.LocalNum != LN_Middle)
 155       return std::tie(A.DFSIn, A.LocalNum, isADef) <
 156              std::tie(B.DFSIn, B.LocalNum, isBDef);
 157     return localComesBefore(A, B);
 158   }
 159
 160   // For a phi use, or a non-materialized def, return the edge it represents.
 161   const std::pair<BasicBlock *, BasicBlock *>
 162   getBlockEdge(const ValueDFS &VD) const {
 163     if (!VD.Def && VD.U) {
 164       auto *PHI = cast<PHINode>(VD.U->getUser());
 165       return std::make_pair(PHI->getIncomingBlock(*VD.U), PHI->getParent());
 166     }
 167     // This is really a non-materialized def.
 168     return ::getBlockEdge(VD.PInfo);
 169   }
 170
 171   // For two phi related values, return the ordering.
 172   bool comparePHIRelated(const ValueDFS &A, const ValueDFS &B) const {
 173     BasicBlock *ASrc, *ADest, *BSrc, *BDest;
 174     std::tie(ASrc, ADest) = getBlockEdge(A);
 175     std::tie(BSrc, BDest) = getBlockEdge(B);
 176
 177 #ifndef NDEBUG
 178     // This function should only be used for values in the same BB, check that.
 179     DomTreeNode *DomASrc = DT.getNode(ASrc);
 180     DomTreeNode *DomBSrc = DT.getNode(BSrc);
 181     assert(DomASrc->getDFSNumIn() == (unsigned)A.DFSIn &&
 182            "DFS numbers for A should match the ones of the source block");
 183     assert(DomBSrc->getDFSNumIn() == (unsigned)B.DFSIn &&
 184            "DFS numbers for B should match the ones of the source block");
 185     assert(A.DFSIn == B.DFSIn && "Values must be in the same block");
 186 #endif
 187     (void)ASrc;
 188     (void)BSrc;
 189
 190     // Use DFS numbers to compare destination blocks, to guarantee a
 191     // deterministic order.
 192     DomTreeNode *DomADest = DT.getNode(ADest);
 193     DomTreeNode *DomBDest = DT.getNode(BDest);
 194     unsigned AIn = DomADest->getDFSNumIn();
 195     unsigned BIn = DomBDest->getDFSNumIn();
 196     bool isADef = A.Def;
 197     bool isBDef = B.Def;
 198     assert((!A.Def || !A.U) && (!B.Def || !B.U) &&
 199            "Def and U cannot be set at the same time");
 200     // Now sort by edge destination and then defs before uses.
 201     return std::tie(AIn, isADef) < std::tie(BIn, isBDef);
 202   }
 203
 204   // Get the definition of an instruction that occurs in the middle of a block.
 205   Value *getMiddleDef(const ValueDFS &VD) const {
 206     if (VD.Def)
 207       return VD.Def;
 208     // It's possible for the defs and uses to be null.  For branches, the local
 209     // numbering will say the placed predicaeinfos should go first (IE
 210     // LN_beginning), so we won't be in this function. For assumes, we will end
 211     // up here, beause we need to order the def we will place relative to the
 212     // assume.  So for the purpose of ordering, we pretend the def is the assume
 213     // because that is where we will insert the info.
 214     if (!VD.U) {
 215       assert(VD.PInfo &&
 216              "No def, no use, and no predicateinfo should not occur");
 217       assert(isa<PredicateAssume>(VD.PInfo) &&
 218              "Middle of block should only occur for assumes");
 219       return cast<PredicateAssume>(VD.PInfo)->AssumeInst;
 220     }
 221     return nullptr;
 222   }
 223
 224   // Return either the Def, if it's not null, or the user of the Use, if the def
 225   // is null.
 226   const Instruction *getDefOrUser(const Value *Def, const Use *U) const {
 227     if (Def)
 228       return cast<Instruction>(Def);
 229     return cast<Instruction>(U->getUser());
 230   }
 231
 232   // This performs the necessary local basic block ordering checks to tell
 233   // whether A comes before B, where both are in the same basic block.
 234   bool localComesBefore(const ValueDFS &A, const ValueDFS &B) const {
 235     auto *ADef = getMiddleDef(A);
 236     auto *BDef = getMiddleDef(B);
 237
 238     // See if we have real values or uses. If we have real values, we are
 239     // guaranteed they are instructions or arguments. No matter what, we are
 240     // guaranteed they are in the same block if they are instructions.
 241     auto *ArgA = dyn_cast_or_null<Argument>(ADef);
 242     auto *ArgB = dyn_cast_or_null<Argument>(BDef);
 243
 244     if (ArgA || ArgB)
 245       return valueComesBefore(OI, ArgA, ArgB);
 246
 247     auto *AInst = getDefOrUser(ADef, A.U);
 248     auto *BInst = getDefOrUser(BDef, B.U);
 249     return valueComesBefore(OI, AInst, BInst);
 250   }
 251 };
 252
 253 } // namespace PredicateInfoClasses
 254
 255 bool PredicateInfo::stackIsInScope(const ValueDFSStack &Stack,
 256                                    const ValueDFS &VDUse) const {
 257   if (Stack.empty())
 258     return false;
 259   // If it's a phi only use, make sure it's for this phi node edge, and that the
 260   // use is in a phi node.  If it's anything else, and the top of the stack is
 261   // EdgeOnly, we need to pop the stack.  We deliberately sort phi uses next to
 262   // the defs they must go with so that we can know it's time to pop the stack
 263   // when we hit the end of the phi uses for a given def.
 264   if (Stack.back().EdgeOnly) {
 265     if (!VDUse.U)
 266       return false;
 267     auto *PHI = dyn_cast<PHINode>(VDUse.U->getUser());
 268     if (!PHI)
 269       return false;
 270     // Check edge
 271     BasicBlock *EdgePred = PHI->getIncomingBlock(*VDUse.U);
 272     if (EdgePred != getBranchBlock(Stack.back().PInfo))
 273       return false;
 274
 275     // Use dominates, which knows how to handle edge dominance.
 276     return DT.dominates(getBlockEdge(Stack.back().PInfo), *VDUse.U);
 277   }
 278
 279   return (VDUse.DFSIn >= Stack.back().DFSIn &&
 280           VDUse.DFSOut <= Stack.back().DFSOut);
 281 }
 282
 283 void PredicateInfo::popStackUntilDFSScope(ValueDFSStack &Stack,
 284                                           const ValueDFS &VD) {
 285   while (!Stack.empty() && !stackIsInScope(Stack, VD))
 286     Stack.pop_back();
 287 }
 288
 289 // Convert the uses of Op into a vector of uses, associating global and local
 290 // DFS info with each one.
 291 void PredicateInfo::convertUsesToDFSOrdered(
 292     Value *Op, SmallVectorImpl<ValueDFS> &DFSOrderedSet) {
 293   for (auto &U : Op->uses()) {
 294     if (auto *I = dyn_cast<Instruction>(U.getUser())) {
 295       ValueDFS VD;
 296       // Put the phi node uses in the incoming block.
 297       BasicBlock *IBlock;
 298       if (auto *PN = dyn_cast<PHINode>(I)) {
 299         IBlock = PN->getIncomingBlock(U);
 300         // Make phi node users appear last in the incoming block
 301         // they are from.
 302         VD.LocalNum = LN_Last;
 303       } else {
 304         // If it's not a phi node use, it is somewhere in the middle of the
 305         // block.
 306         IBlock = I->getParent();
 307         VD.LocalNum = LN_Middle;
 308       }
 309       DomTreeNode *DomNode = DT.getNode(IBlock);
 310       // It's possible our use is in an unreachable block. Skip it if so.
 311       if (!DomNode)
 312         continue;
 313       VD.DFSIn = DomNode->getDFSNumIn();
 314       VD.DFSOut = DomNode->getDFSNumOut();
 315       VD.U = &U;
 316       DFSOrderedSet.push_back(VD);
 317     }
 318   }
 319 }
 320
 321 // Collect relevant operations from Comparison that we may want to insert copies
 322 // for.
 323 void collectCmpOps(CmpInst *Comparison, SmallVectorImpl<Value *> &CmpOperands) {
 324   auto *Op0 = Comparison->getOperand(0);
 325   auto *Op1 = Comparison->getOperand(1);
 326   if (Op0 == Op1)
 327     return;
 328   CmpOperands.push_back(Comparison);
 329   // Only want real values, not constants.  Additionally, operands with one use
 330   // are only being used in the comparison, which means they will not be useful
 331   // for us to consider for predicateinfo.
 332   //
 333   if ((isa<Instruction>(Op0) || isa<Argument>(Op0)) && !Op0->hasOneUse())
 334     CmpOperands.push_back(Op0);
 335   if ((isa<Instruction>(Op1) || isa<Argument>(Op1)) && !Op1->hasOneUse())
 336     CmpOperands.push_back(Op1);
 337 }
 338
 339 // Add Op, PB to the list of value infos for Op, and mark Op to be renamed.
 340 void PredicateInfo::addInfoFor(SmallVectorImpl<Value *> &OpsToRename, Value *Op,
 341                                PredicateBase *PB) {
 342   auto &OperandInfo = getOrCreateValueInfo(Op);
 343   if (OperandInfo.Infos.empty())
 344     OpsToRename.push_back(Op);
 345   AllInfos.push_back(PB);
 346   OperandInfo.Infos.push_back(PB);
 347 }
 348
 349 // Process an assume instruction and place relevant operations we want to rename
 350 // into OpsToRename.
 351 void PredicateInfo::processAssume(IntrinsicInst *II, BasicBlock *AssumeBB,
 352                                   SmallVectorImpl<Value *> &OpsToRename) {
 353   // See if we have a comparison we support
 354   SmallVector<Value *, 8> CmpOperands;
 355   SmallVector<Value *, 2> ConditionsToProcess;
 356   CmpInst::Predicate Pred;
 357   Value *Operand = II->getOperand(0);
 358   if (m_c_And(m_Cmp(Pred, m_Value(), m_Value()),
 359               m_Cmp(Pred, m_Value(), m_Value()))
 360           .match(II->getOperand(0))) {
 361     ConditionsToProcess.push_back(cast<BinaryOperator>(Operand)->getOperand(0));
 362     ConditionsToProcess.push_back(cast<BinaryOperator>(Operand)->getOperand(1));
 363     ConditionsToProcess.push_back(Operand);
 364   } else if (isa<CmpInst>(Operand)) {
 365
 366     ConditionsToProcess.push_back(Operand);
 367   }
 368   for (auto Cond : ConditionsToProcess) {
 369     if (auto *Cmp = dyn_cast<CmpInst>(Cond)) {
 370       collectCmpOps(Cmp, CmpOperands);
 371       // Now add our copy infos for our operands
 372       for (auto *Op : CmpOperands) {
 373         auto *PA = new PredicateAssume(Op, II, Cmp);
 374         addInfoFor(OpsToRename, Op, PA);
 375       }
 376       CmpOperands.clear();
 377     } else if (auto *BinOp = dyn_cast<BinaryOperator>(Cond)) {
 378       // Otherwise, it should be an AND.
 379       assert(BinOp->getOpcode() == Instruction::And &&
 380              "Should have been an AND");
 381       auto *PA = new PredicateAssume(BinOp, II, BinOp);
 382       addInfoFor(OpsToRename, BinOp, PA);
 383     } else {
 384       llvm_unreachable("Unknown type of condition");
 385     }
 386   }
 387 }
 388
 389 // Process a block terminating branch, and place relevant operations to be
 390 // renamed into OpsToRename.
 391 void PredicateInfo::processBranch(BranchInst *BI, BasicBlock *BranchBB,
 392                                   SmallVectorImpl<Value *> &OpsToRename) {
 393   BasicBlock *FirstBB = BI->getSuccessor(0);
 394   BasicBlock *SecondBB = BI->getSuccessor(1);
 395   SmallVector<BasicBlock *, 2> SuccsToProcess;
 396   SuccsToProcess.push_back(FirstBB);
 397   SuccsToProcess.push_back(SecondBB);
 398   SmallVector<Value *, 2> ConditionsToProcess;
 399
 400   auto InsertHelper = [&](Value *Op, bool isAnd, bool isOr, Value *Cond) {
 401     for (auto *Succ : SuccsToProcess) {
 402       // Don't try to insert on a self-edge. This is mainly because we will
 403       // eliminate during renaming anyway.
 404       if (Succ == BranchBB)
 405         continue;
 406       bool TakenEdge = (Succ == FirstBB);
 407       // For and, only insert on the true edge
 408       // For or, only insert on the false edge
 409       if ((isAnd && !TakenEdge) || (isOr && TakenEdge))
 410         continue;
 411       PredicateBase *PB =
 412           new PredicateBranch(Op, BranchBB, Succ, Cond, TakenEdge);
 413       addInfoFor(OpsToRename, Op, PB);
 414       if (!Succ->getSinglePredecessor())
 415         EdgeUsesOnly.insert({BranchBB, Succ});
 416     }
 417   };
 418
 419   // Match combinations of conditions.
 420   CmpInst::Predicate Pred;
 421   bool isAnd = false;
 422   bool isOr = false;
 423   SmallVector<Value *, 8> CmpOperands;
 424   if (match(BI->getCondition(), m_And(m_Cmp(Pred, m_Value(), m_Value()),
 425                                       m_Cmp(Pred, m_Value(), m_Value()))) ||
 426       match(BI->getCondition(), m_Or(m_Cmp(Pred, m_Value(), m_Value()),
 427                                      m_Cmp(Pred, m_Value(), m_Value())))) {
 428     auto *BinOp = cast<BinaryOperator>(BI->getCondition());
 429     if (BinOp->getOpcode() == Instruction::And)
 430       isAnd = true;
 431     else if (BinOp->getOpcode() == Instruction::Or)
 432       isOr = true;
 433     ConditionsToProcess.push_back(BinOp->getOperand(0));
 434     ConditionsToProcess.push_back(BinOp->getOperand(1));
 435     ConditionsToProcess.push_back(BI->getCondition());
 436   } else if (isa<CmpInst>(BI->getCondition())) {
 437     ConditionsToProcess.push_back(BI->getCondition());
 438   }
 439   for (auto Cond : ConditionsToProcess) {
 440     if (auto *Cmp = dyn_cast<CmpInst>(Cond)) {
 441       collectCmpOps(Cmp, CmpOperands);
 442       // Now add our copy infos for our operands
 443       for (auto *Op : CmpOperands)
 444         InsertHelper(Op, isAnd, isOr, Cmp);
 445     } else if (auto *BinOp = dyn_cast<BinaryOperator>(Cond)) {
 446       // This must be an AND or an OR.
 447       assert((BinOp->getOpcode() == Instruction::And ||
 448               BinOp->getOpcode() == Instruction::Or) &&
 449              "Should have been an AND or an OR");
 450       // The actual value of the binop is not subject to the same restrictions
 451       // as the comparison. It's either true or false on the true/false branch.
 452       InsertHelper(BinOp, false, false, BinOp);
 453     } else {
 454       llvm_unreachable("Unknown type of condition");
 455     }
 456     CmpOperands.clear();
 457   }
 458 }
 459 // Process a block terminating switch, and place relevant operations to be
 460 // renamed into OpsToRename.
 461 void PredicateInfo::processSwitch(SwitchInst *SI, BasicBlock *BranchBB,
 462                                   SmallVectorImpl<Value *> &OpsToRename) {
 463   Value *Op = SI->getCondition();
 464   if ((!isa<Instruction>(Op) && !isa<Argument>(Op)) || Op->hasOneUse())
 465     return;
 466
 467   // Remember how many outgoing edges there are to every successor.
 468   SmallDenseMap<BasicBlock *, unsigned, 16> SwitchEdges;
 469   for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) {
 470     BasicBlock *TargetBlock = SI->getSuccessor(i);
 471     ++SwitchEdges[TargetBlock];
 472   }
 473
 474   // Now propagate info for each case value
 475   for (auto C : SI->cases()) {
 476     BasicBlock *TargetBlock = C.getCaseSuccessor();
 477     if (SwitchEdges.lookup(TargetBlock) == 1) {
 478       PredicateSwitch *PS = new PredicateSwitch(
 479           Op, SI->getParent(), TargetBlock, C.getCaseValue(), SI);
 480       addInfoFor(OpsToRename, Op, PS);
 481       if (!TargetBlock->getSinglePredecessor())
 482         EdgeUsesOnly.insert({BranchBB, TargetBlock});
 483     }
 484   }
 485 }
 486
 487 // Build predicate info for our function
 488 void PredicateInfo::buildPredicateInfo() {
 489   DT.updateDFSNumbers();
 490   // Collect operands to rename from all conditional branch terminators, as well
 491   // as assume statements.
 492   SmallVector<Value *, 8> OpsToRename;
 493   for (auto DTN : depth_first(DT.getRootNode())) {
 494     BasicBlock *BranchBB = DTN->getBlock();
 495     if (auto *BI = dyn_cast<BranchInst>(BranchBB->getTerminator())) {
 496       if (!BI->isConditional())
 497         continue;
 498       // Can't insert conditional information if they all go to the same place.
 499       if (BI->getSuccessor(0) == BI->getSuccessor(1))
 500         continue;
 501       processBranch(BI, BranchBB, OpsToRename);
 502     } else if (auto *SI = dyn_cast<SwitchInst>(BranchBB->getTerminator())) {
 503       processSwitch(SI, BranchBB, OpsToRename);
 504     }
 505   }
 506   for (auto &Assume : AC.assumptions()) {
 507     if (auto *II = dyn_cast_or_null<IntrinsicInst>(Assume))
 508       if (DT.isReachableFromEntry(II->getParent()))
 509         processAssume(II, II->getParent(), OpsToRename);
 510   }
 511   // Now rename all our operations.
 512   renameUses(OpsToRename);
 513 }
 514
 515 // Create a ssa_copy declaration with custom mangling, because
 516 // Intrinsic::getDeclaration does not handle overloaded unnamed types properly:
 517 // all unnamed types get mangled to the same string. We use the pointer
 518 // to the type as name here, as it guarantees unique names for different
 519 // types and we remove the declarations when destroying PredicateInfo.
 520 // It is a workaround for PR38117, because solving it in a fully general way is
 521 // tricky (FIXME).
 522 static Function *getCopyDeclaration(Module *M, Type *Ty) {
 523   std::string Name = "llvm.ssa.copy." + utostr((uintptr_t) Ty);
 524   return cast<Function>(
 525       M->getOrInsertFunction(Name,
 526                              getType(M->getContext(), Intrinsic::ssa_copy, Ty))
 527           .getCallee());
 528 }
 529
 530 // Given the renaming stack, make all the operands currently on the stack real
 531 // by inserting them into the IR.  Return the last operation's value.
 532 Value *PredicateInfo::materializeStack(unsigned int &Counter,
 533                                        ValueDFSStack &RenameStack,
 534                                        Value *OrigOp) {
 535   // Find the first thing we have to materialize
 536   auto RevIter = RenameStack.rbegin();
 537   for (; RevIter != RenameStack.rend(); ++RevIter)
 538     if (RevIter->Def)
 539       break;
 540
 541   size_t Start = RevIter - RenameStack.rbegin();
 542   // The maximum number of things we should be trying to materialize at once
 543   // right now is 4, depending on if we had an assume, a branch, and both used
 544   // and of conditions.
 545   for (auto RenameIter = RenameStack.end() - Start;
 546        RenameIter != RenameStack.end(); ++RenameIter) {
 547     auto *Op =
 548         RenameIter == RenameStack.begin() ? OrigOp : (RenameIter - 1)->Def;
 549     ValueDFS &Result = *RenameIter;
 550     auto *ValInfo = Result.PInfo;
 551     // For edge predicates, we can just place the operand in the block before
 552     // the terminator.  For assume, we have to place it right before the assume
 553     // to ensure we dominate all of our uses.  Always insert right before the
 554     // relevant instruction (terminator, assume), so that we insert in proper
 555     // order in the case of multiple predicateinfo in the same block.
 556     if (isa<PredicateWithEdge>(ValInfo)) {
 557       IRBuilder<> B(getBranchTerminator(ValInfo));
 558       Function *IF = getCopyDeclaration(F.getParent(), Op->getType());
 559       if (IF->users().empty())
 560         CreatedDeclarations.insert(IF);
 561       CallInst *PIC =
 562           B.CreateCall(IF, Op, Op->getName() + "." + Twine(Counter++));
 563       PredicateMap.insert({PIC, ValInfo});
 564       Result.Def = PIC;
 565     } else {
 566       auto *PAssume = dyn_cast<PredicateAssume>(ValInfo);
 567       assert(PAssume &&
 568              "Should not have gotten here without it being an assume");
 569       IRBuilder<> B(PAssume->AssumeInst);
 570       Function *IF = getCopyDeclaration(F.getParent(), Op->getType());
 571       if (IF->users().empty())
 572         CreatedDeclarations.insert(IF);
 573       CallInst *PIC = B.CreateCall(IF, Op);
 574       PredicateMap.insert({PIC, ValInfo});
 575       Result.Def = PIC;
 576     }
 577   }
 578   return RenameStack.back().Def;
 579 }
 580
 581 // Instead of the standard SSA renaming algorithm, which is O(Number of
 582 // instructions), and walks the entire dominator tree, we walk only the defs +
 583 // uses.  The standard SSA renaming algorithm does not really rely on the
 584 // dominator tree except to order the stack push/pops of the renaming stacks, so
 585 // that defs end up getting pushed before hitting the correct uses.  This does
 586 // not require the dominator tree, only the *order* of the dominator tree. The
 587 // complete and correct ordering of the defs and uses, in dominator tree is
 588 // contained in the DFS numbering of the dominator tree. So we sort the defs and
 589 // uses into the DFS ordering, and then just use the renaming stack as per
 590 // normal, pushing when we hit a def (which is a predicateinfo instruction),
 591 // popping when we are out of the dfs scope for that def, and replacing any uses
 592 // with top of stack if it exists.  In order to handle liveness without
 593 // propagating liveness info, we don't actually insert the predicateinfo
 594 // instruction def until we see a use that it would dominate.  Once we see such
 595 // a use, we materialize the predicateinfo instruction in the right place and
 596 // use it.
 597 //
 598 // TODO: Use this algorithm to perform fast single-variable renaming in
 599 // promotememtoreg and memoryssa.
 600 void PredicateInfo::renameUses(SmallVectorImpl<Value *> &OpsToRename) {
 601   ValueDFS_Compare Compare(DT, OI);
 602   // Compute liveness, and rename in O(uses) per Op.
 603   for (auto *Op : OpsToRename) {
 604     LLVM_DEBUG(dbgs() << "Visiting " << *Op << "\n");
 605     unsigned Counter = 0;
 606     SmallVector<ValueDFS, 16> OrderedUses;
 607     const auto &ValueInfo = getValueInfo(Op);
 608     // Insert the possible copies into the def/use list.
 609     // They will become real copies if we find a real use for them, and never
 610     // created otherwise.
 611     for (auto &PossibleCopy : ValueInfo.Infos) {
 612       ValueDFS VD;
 613       // Determine where we are going to place the copy by the copy type.
 614       // The predicate info for branches always come first, they will get
 615       // materialized in the split block at the top of the block.
 616       // The predicate info for assumes will be somewhere in the middle,
 617       // it will get materialized in front of the assume.
 618       if (const auto *PAssume = dyn_cast<PredicateAssume>(PossibleCopy)) {
 619         VD.LocalNum = LN_Middle;
 620         DomTreeNode *DomNode = DT.getNode(PAssume->AssumeInst->getParent());
 621         if (!DomNode)
 622           continue;
 623         VD.DFSIn = DomNode->getDFSNumIn();
 624         VD.DFSOut = DomNode->getDFSNumOut();
 625         VD.PInfo = PossibleCopy;
 626         OrderedUses.push_back(VD);
 627       } else if (isa<PredicateWithEdge>(PossibleCopy)) {
 628         // If we can only do phi uses, we treat it like it's in the branch
 629         // block, and handle it specially. We know that it goes last, and only
 630         // dominate phi uses.
 631         auto BlockEdge = getBlockEdge(PossibleCopy);
 632         if (EdgeUsesOnly.count(BlockEdge)) {
 633           VD.LocalNum = LN_Last;
 634           auto *DomNode = DT.getNode(BlockEdge.first);
 635           if (DomNode) {
 636             VD.DFSIn = DomNode->getDFSNumIn();
 637             VD.DFSOut = DomNode->getDFSNumOut();
 638             VD.PInfo = PossibleCopy;
 639             VD.EdgeOnly = true;
 640             OrderedUses.push_back(VD);
 641           }
 642         } else {
 643           // Otherwise, we are in the split block (even though we perform
 644           // insertion in the branch block).
 645           // Insert a possible copy at the split block and before the branch.
 646           VD.LocalNum = LN_First;
 647           auto *DomNode = DT.getNode(BlockEdge.second);
 648           if (DomNode) {
 649             VD.DFSIn = DomNode->getDFSNumIn();
 650             VD.DFSOut = DomNode->getDFSNumOut();
 651             VD.PInfo = PossibleCopy;
 652             OrderedUses.push_back(VD);
 653           }
 654         }
 655       }
 656     }
 657
 658     convertUsesToDFSOrdered(Op, OrderedUses);
 659     // Here we require a stable sort because we do not bother to try to
 660     // assign an order to the operands the uses represent. Thus, two
 661     // uses in the same instruction do not have a strict sort order
 662     // currently and will be considered equal. We could get rid of the
 663     // stable sort by creating one if we wanted.
 664     llvm::stable_sort(OrderedUses, Compare);
 665     SmallVector<ValueDFS, 8> RenameStack;
 666     // For each use, sorted into dfs order, push values and replaces uses with
 667     // top of stack, which will represent the reaching def.
 668     for (auto &VD : OrderedUses) {
 669       // We currently do not materialize copy over copy, but we should decide if
 670       // we want to.
 671       bool PossibleCopy = VD.PInfo != nullptr;
 672       if (RenameStack.empty()) {
 673         LLVM_DEBUG(dbgs() << "Rename Stack is empty\n");
 674       } else {
 675         LLVM_DEBUG(dbgs() << "Rename Stack Top DFS numbers are ("
 676                           << RenameStack.back().DFSIn << ","
 677                           << RenameStack.back().DFSOut << ")\n");
 678       }
 679
 680       LLVM_DEBUG(dbgs() << "Current DFS numbers are (" << VD.DFSIn << ","
 681                         << VD.DFSOut << ")\n");
 682
 683       bool ShouldPush = (VD.Def || PossibleCopy);
 684       bool OutOfScope = !stackIsInScope(RenameStack, VD);
 685       if (OutOfScope || ShouldPush) {
 686         // Sync to our current scope.
 687         popStackUntilDFSScope(RenameStack, VD);
 688         if (ShouldPush) {
 689           RenameStack.push_back(VD);
 690         }
 691       }
 692       // If we get to this point, and the stack is empty we must have a use
 693       // with no renaming needed, just skip it.
 694       if (RenameStack.empty())
 695         continue;
 696       // Skip values, only want to rename the uses
 697       if (VD.Def || PossibleCopy)
 698         continue;
 699       if (!DebugCounter::shouldExecute(RenameCounter)) {
 700         LLVM_DEBUG(dbgs() << "Skipping execution due to debug counter\n");
 701         continue;
 702       }
 703       ValueDFS &Result = RenameStack.back();
 704
 705       // If the possible copy dominates something, materialize our stack up to
 706       // this point. This ensures every comparison that affects our operation
 707       // ends up with predicateinfo.
 708       if (!Result.Def)
 709         Result.Def = materializeStack(Counter, RenameStack, Op);
 710
 711       LLVM_DEBUG(dbgs() << "Found replacement " << *Result.Def << " for "
 712                         << *VD.U->get() << " in " << *(VD.U->getUser())
 713                         << "\n");
 714       assert(DT.dominates(cast<Instruction>(Result.Def), *VD.U) &&
 715              "Predicateinfo def should have dominated this use");
 716       VD.U->set(Result.Def);
 717     }
 718   }
 719 }
 720
 721 PredicateInfo::ValueInfo &PredicateInfo::getOrCreateValueInfo(Value *Operand) {
 722   auto OIN = ValueInfoNums.find(Operand);
 723   if (OIN == ValueInfoNums.end()) {
 724     // This will grow it
 725     ValueInfos.resize(ValueInfos.size() + 1);
 726     // This will use the new size and give us a 0 based number of the info
 727     auto InsertResult = ValueInfoNums.insert({Operand, ValueInfos.size() - 1});
 728     assert(InsertResult.second && "Value info number already existed?");
 729     return ValueInfos[InsertResult.first->second];
 730   }
 731   return ValueInfos[OIN->second];
 732 }
 733
 734 const PredicateInfo::ValueInfo &
 735 PredicateInfo::getValueInfo(Value *Operand) const {
 736   auto OINI = ValueInfoNums.lookup(Operand);
 737   assert(OINI != 0 && "Operand was not really in the Value Info Numbers");
 738   assert(OINI < ValueInfos.size() &&
 739          "Value Info Number greater than size of Value Info Table");
 740   return ValueInfos[OINI];
 741 }
 742
 743 PredicateInfo::PredicateInfo(Function &F, DominatorTree &DT,
 744                              AssumptionCache &AC)
 745     : F(F), DT(DT), AC(AC), OI(&DT) {
 746   // Push an empty operand info so that we can detect 0 as not finding one
 747   ValueInfos.resize(1);
 748   buildPredicateInfo();
 749 }
 750
 751 // Remove all declarations we created . The PredicateInfo consumers are
 752 // responsible for remove the ssa_copy calls created.
 753 PredicateInfo::~PredicateInfo() {
 754   // Collect function pointers in set first, as SmallSet uses a SmallVector
 755   // internally and we have to remove the asserting value handles first.
 756   SmallPtrSet<Function *, 20> FunctionPtrs;
 757   for (auto &F : CreatedDeclarations)
 758     FunctionPtrs.insert(&*F);
 759   CreatedDeclarations.clear();
 760
 761   for (Function *F : FunctionPtrs) {
 762     assert(F->user_begin() == F->user_end() &&
 763            "PredicateInfo consumer did not remove all SSA copies.");
 764     F->eraseFromParent();
 765   }
 766 }
 767
 768 void PredicateInfo::verifyPredicateInfo() const {}
 769
 770 char PredicateInfoPrinterLegacyPass::ID = 0;
 771
 772 PredicateInfoPrinterLegacyPass::PredicateInfoPrinterLegacyPass()
 773     : FunctionPass(ID) {
 774   initializePredicateInfoPrinterLegacyPassPass(
 775       *PassRegistry::getPassRegistry());
 776 }
 777
 778 void PredicateInfoPrinterLegacyPass::getAnalysisUsage(AnalysisUsage &AU) const {
 779   AU.setPreservesAll();
 780   AU.addRequiredTransitive<DominatorTreeWrapperPass>();
 781   AU.addRequired<AssumptionCacheTracker>();
 782 }
 783
 784 // Replace ssa_copy calls created by PredicateInfo with their operand.
 785 static void replaceCreatedSSACopys(PredicateInfo &PredInfo, Function &F) {
 786   for (auto I = inst_begin(F), E = inst_end(F); I != E;) {
 787     Instruction *Inst = &*I++;
 788     const auto *PI = PredInfo.getPredicateInfoFor(Inst);
 789     auto *II = dyn_cast<IntrinsicInst>(Inst);
 790     if (!PI || !II || II->getIntrinsicID() != Intrinsic::ssa_copy)
 791       continue;
 792
 793     Inst->replaceAllUsesWith(II->getOperand(0));
 794     Inst->eraseFromParent();
 795   }
 796 }
 797
 798 bool PredicateInfoPrinterLegacyPass::runOnFunction(Function &F) {
 799   auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 800   auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
 801   auto PredInfo = std::make_unique<PredicateInfo>(F, DT, AC);
 802   PredInfo->print(dbgs());
 803   if (VerifyPredicateInfo)
 804     PredInfo->verifyPredicateInfo();
 805
 806   replaceCreatedSSACopys(*PredInfo, F);
 807   return false;
 808 }
 809
 810 PreservedAnalyses PredicateInfoPrinterPass::run(Function &F,
 811                                                 FunctionAnalysisManager &AM) {
 812   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
 813   auto &AC = AM.getResult<AssumptionAnalysis>(F);
 814   OS << "PredicateInfo for function: " << F.getName() << "\n";
 815   auto PredInfo = std::make_unique<PredicateInfo>(F, DT, AC);
 816   PredInfo->print(OS);
 817
 818   replaceCreatedSSACopys(*PredInfo, F);
 819   return PreservedAnalyses::all();
 820 }
 821
 822 /// An assembly annotator class to print PredicateInfo information in
 823 /// comments.
 824 class PredicateInfoAnnotatedWriter : public AssemblyAnnotationWriter {
 825   friend class PredicateInfo;
 826   const PredicateInfo *PredInfo;
 827
 828 public:
 829   PredicateInfoAnnotatedWriter(const PredicateInfo *M) : PredInfo(M) {}
 830
 831   virtual void emitBasicBlockStartAnnot(const BasicBlock *BB,
 832                                         formatted_raw_ostream &OS) {}
 833
 834   virtual void emitInstructionAnnot(const Instruction *I,
 835                                     formatted_raw_ostream &OS) {
 836     if (const auto *PI = PredInfo->getPredicateInfoFor(I)) {
 837       OS << "; Has predicate info\n";
 838       if (const auto *PB = dyn_cast<PredicateBranch>(PI)) {
 839         OS << "; branch predicate info { TrueEdge: " << PB->TrueEdge
 840            << " Comparison:" << *PB->Condition << " Edge: [";
 841         PB->From->printAsOperand(OS);
 842         OS << ",";
 843         PB->To->printAsOperand(OS);
 844         OS << "] }\n";
 845       } else if (const auto *PS = dyn_cast<PredicateSwitch>(PI)) {
 846         OS << "; switch predicate info { CaseValue: " << *PS->CaseValue
 847            << " Switch:" << *PS->Switch << " Edge: [";
 848         PS->From->printAsOperand(OS);
 849         OS << ",";
 850         PS->To->printAsOperand(OS);
 851         OS << "] }\n";
 852       } else if (const auto *PA = dyn_cast<PredicateAssume>(PI)) {
 853         OS << "; assume predicate info {"
 854            << " Comparison:" << *PA->Condition << " }\n";
 855       }
 856     }
 857   }
 858 };
 859
 860 void PredicateInfo::print(raw_ostream &OS) const {
 861   PredicateInfoAnnotatedWriter Writer(this);
 862   F.print(OS, &Writer);
 863 }
 864
 865 void PredicateInfo::dump() const {
 866   PredicateInfoAnnotatedWriter Writer(this);
 867   F.print(dbgs(), &Writer);
 868 }
 869
 870 PreservedAnalyses PredicateInfoVerifierPass::run(Function &F,
 871                                                  FunctionAnalysisManager &AM) {
 872   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
 873   auto &AC = AM.getResult<AssumptionAnalysis>(F);
 874   std::make_unique<PredicateInfo>(F, DT, AC)->verifyPredicateInfo();
 875
 876   return PreservedAnalyses::all();
 877 }
 878 }