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 } 879