contrib/llvm/lib/Transforms/Utils/PredicateInfo.cpp

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