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