1 //===-- PredicateInfo.cpp - PredicateInfo Builder--------------------===//
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
7 //===----------------------------------------------------------------===//
9 // This file implements the PredicateInfo class.
11 //===----------------------------------------------------------------===//
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"
38 #define DEBUG_TYPE "predicateinfo"
40 using namespace PatternMatch;
41 using namespace llvm::PredicateInfoClasses;
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");
56 // Given a predicate info that is a type of branching terminator, get the
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;
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();
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);
85 namespace PredicateInfoClasses {
87 // Operations that must appear first in the block.
89 // Operations that are somewhere in the middle of the block, and are sorted on
92 // Operations that must appear last in a block, like successor phi node uses.
96 // Associate global and local DFS info with defs and uses, so we can sort them
97 // into a global domination ordering.
101 unsigned int LocalNum = LN_Middle;
102 // Only one of Def or Use will be set.
103 Value *Def = nullptr;
105 // Neither PInfo nor EdgeOnly participate in the ordering
106 PredicateBase *PInfo = nullptr;
107 bool EdgeOnly = false;
110 // Perform a strict weak ordering on instructions and arguments.
111 static bool valueComesBefore(OrderedInstructions &OI, const Value *A,
113 auto *ArgA = dyn_cast_or_null<Argument>(A);
114 auto *ArgB = dyn_cast_or_null<Argument>(B);
120 return ArgA->getArgNo() < ArgB->getArgNo();
121 return OI.dfsBefore(cast<Instruction>(A), cast<Instruction>(B));
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 OrderedInstructions &OI;
129 ValueDFS_Compare(OrderedInstructions &OI) : OI(OI) {}
131 bool operator()(const ValueDFS &A, const ValueDFS &B) const {
134 // The only case we can't directly compare them is when they in the same
135 // block, and both have localnum == middle. In that case, we have to use
136 // comesbefore to see what the real ordering is, because they are in the
139 bool SameBlock = std::tie(A.DFSIn, A.DFSOut) == std::tie(B.DFSIn, B.DFSOut);
141 // We want to put the def that will get used for a given set of phi uses,
142 // before those phi uses.
143 // So we sort by edge, then by def.
144 // Note that only phi nodes uses and defs can come last.
145 if (SameBlock && A.LocalNum == LN_Last && B.LocalNum == LN_Last)
146 return comparePHIRelated(A, B);
148 if (!SameBlock || A.LocalNum != LN_Middle || B.LocalNum != LN_Middle)
149 return std::tie(A.DFSIn, A.DFSOut, A.LocalNum, A.Def, A.U) <
150 std::tie(B.DFSIn, B.DFSOut, B.LocalNum, B.Def, B.U);
151 return localComesBefore(A, B);
154 // For a phi use, or a non-materialized def, return the edge it represents.
155 const std::pair<BasicBlock *, BasicBlock *>
156 getBlockEdge(const ValueDFS &VD) const {
157 if (!VD.Def && VD.U) {
158 auto *PHI = cast<PHINode>(VD.U->getUser());
159 return std::make_pair(PHI->getIncomingBlock(*VD.U), PHI->getParent());
161 // This is really a non-materialized def.
162 return ::getBlockEdge(VD.PInfo);
165 // For two phi related values, return the ordering.
166 bool comparePHIRelated(const ValueDFS &A, const ValueDFS &B) const {
167 auto &ABlockEdge = getBlockEdge(A);
168 auto &BBlockEdge = getBlockEdge(B);
169 // Now sort by block edge and then defs before uses.
170 return std::tie(ABlockEdge, A.Def, A.U) < std::tie(BBlockEdge, B.Def, B.U);
173 // Get the definition of an instruction that occurs in the middle of a block.
174 Value *getMiddleDef(const ValueDFS &VD) const {
177 // It's possible for the defs and uses to be null. For branches, the local
178 // numbering will say the placed predicaeinfos should go first (IE
179 // LN_beginning), so we won't be in this function. For assumes, we will end
180 // up here, beause we need to order the def we will place relative to the
181 // assume. So for the purpose of ordering, we pretend the def is the assume
182 // because that is where we will insert the info.
185 "No def, no use, and no predicateinfo should not occur");
186 assert(isa<PredicateAssume>(VD.PInfo) &&
187 "Middle of block should only occur for assumes");
188 return cast<PredicateAssume>(VD.PInfo)->AssumeInst;
193 // Return either the Def, if it's not null, or the user of the Use, if the def
195 const Instruction *getDefOrUser(const Value *Def, const Use *U) const {
197 return cast<Instruction>(Def);
198 return cast<Instruction>(U->getUser());
201 // This performs the necessary local basic block ordering checks to tell
202 // whether A comes before B, where both are in the same basic block.
203 bool localComesBefore(const ValueDFS &A, const ValueDFS &B) const {
204 auto *ADef = getMiddleDef(A);
205 auto *BDef = getMiddleDef(B);
207 // See if we have real values or uses. If we have real values, we are
208 // guaranteed they are instructions or arguments. No matter what, we are
209 // guaranteed they are in the same block if they are instructions.
210 auto *ArgA = dyn_cast_or_null<Argument>(ADef);
211 auto *ArgB = dyn_cast_or_null<Argument>(BDef);
214 return valueComesBefore(OI, ArgA, ArgB);
216 auto *AInst = getDefOrUser(ADef, A.U);
217 auto *BInst = getDefOrUser(BDef, B.U);
218 return valueComesBefore(OI, AInst, BInst);
222 } // namespace PredicateInfoClasses
224 bool PredicateInfo::stackIsInScope(const ValueDFSStack &Stack,
225 const ValueDFS &VDUse) const {
228 // If it's a phi only use, make sure it's for this phi node edge, and that the
229 // use is in a phi node. If it's anything else, and the top of the stack is
230 // EdgeOnly, we need to pop the stack. We deliberately sort phi uses next to
231 // the defs they must go with so that we can know it's time to pop the stack
232 // when we hit the end of the phi uses for a given def.
233 if (Stack.back().EdgeOnly) {
236 auto *PHI = dyn_cast<PHINode>(VDUse.U->getUser());
240 BasicBlock *EdgePred = PHI->getIncomingBlock(*VDUse.U);
241 if (EdgePred != getBranchBlock(Stack.back().PInfo))
244 // Use dominates, which knows how to handle edge dominance.
245 return DT.dominates(getBlockEdge(Stack.back().PInfo), *VDUse.U);
248 return (VDUse.DFSIn >= Stack.back().DFSIn &&
249 VDUse.DFSOut <= Stack.back().DFSOut);
252 void PredicateInfo::popStackUntilDFSScope(ValueDFSStack &Stack,
253 const ValueDFS &VD) {
254 while (!Stack.empty() && !stackIsInScope(Stack, VD))
258 // Convert the uses of Op into a vector of uses, associating global and local
259 // DFS info with each one.
260 void PredicateInfo::convertUsesToDFSOrdered(
261 Value *Op, SmallVectorImpl<ValueDFS> &DFSOrderedSet) {
262 for (auto &U : Op->uses()) {
263 if (auto *I = dyn_cast<Instruction>(U.getUser())) {
265 // Put the phi node uses in the incoming block.
267 if (auto *PN = dyn_cast<PHINode>(I)) {
268 IBlock = PN->getIncomingBlock(U);
269 // Make phi node users appear last in the incoming block
271 VD.LocalNum = LN_Last;
273 // If it's not a phi node use, it is somewhere in the middle of the
275 IBlock = I->getParent();
276 VD.LocalNum = LN_Middle;
278 DomTreeNode *DomNode = DT.getNode(IBlock);
279 // It's possible our use is in an unreachable block. Skip it if so.
282 VD.DFSIn = DomNode->getDFSNumIn();
283 VD.DFSOut = DomNode->getDFSNumOut();
285 DFSOrderedSet.push_back(VD);
290 // Collect relevant operations from Comparison that we may want to insert copies
292 void collectCmpOps(CmpInst *Comparison, SmallVectorImpl<Value *> &CmpOperands) {
293 auto *Op0 = Comparison->getOperand(0);
294 auto *Op1 = Comparison->getOperand(1);
297 CmpOperands.push_back(Comparison);
298 // Only want real values, not constants. Additionally, operands with one use
299 // are only being used in the comparison, which means they will not be useful
300 // for us to consider for predicateinfo.
302 if ((isa<Instruction>(Op0) || isa<Argument>(Op0)) && !Op0->hasOneUse())
303 CmpOperands.push_back(Op0);
304 if ((isa<Instruction>(Op1) || isa<Argument>(Op1)) && !Op1->hasOneUse())
305 CmpOperands.push_back(Op1);
308 // Add Op, PB to the list of value infos for Op, and mark Op to be renamed.
309 void PredicateInfo::addInfoFor(SmallPtrSetImpl<Value *> &OpsToRename, Value *Op,
311 OpsToRename.insert(Op);
312 auto &OperandInfo = getOrCreateValueInfo(Op);
313 AllInfos.push_back(PB);
314 OperandInfo.Infos.push_back(PB);
317 // Process an assume instruction and place relevant operations we want to rename
319 void PredicateInfo::processAssume(IntrinsicInst *II, BasicBlock *AssumeBB,
320 SmallPtrSetImpl<Value *> &OpsToRename) {
321 // See if we have a comparison we support
322 SmallVector<Value *, 8> CmpOperands;
323 SmallVector<Value *, 2> ConditionsToProcess;
324 CmpInst::Predicate Pred;
325 Value *Operand = II->getOperand(0);
326 if (m_c_And(m_Cmp(Pred, m_Value(), m_Value()),
327 m_Cmp(Pred, m_Value(), m_Value()))
328 .match(II->getOperand(0))) {
329 ConditionsToProcess.push_back(cast<BinaryOperator>(Operand)->getOperand(0));
330 ConditionsToProcess.push_back(cast<BinaryOperator>(Operand)->getOperand(1));
331 ConditionsToProcess.push_back(Operand);
332 } else if (isa<CmpInst>(Operand)) {
334 ConditionsToProcess.push_back(Operand);
336 for (auto Cond : ConditionsToProcess) {
337 if (auto *Cmp = dyn_cast<CmpInst>(Cond)) {
338 collectCmpOps(Cmp, CmpOperands);
339 // Now add our copy infos for our operands
340 for (auto *Op : CmpOperands) {
341 auto *PA = new PredicateAssume(Op, II, Cmp);
342 addInfoFor(OpsToRename, Op, PA);
345 } else if (auto *BinOp = dyn_cast<BinaryOperator>(Cond)) {
346 // Otherwise, it should be an AND.
347 assert(BinOp->getOpcode() == Instruction::And &&
348 "Should have been an AND");
349 auto *PA = new PredicateAssume(BinOp, II, BinOp);
350 addInfoFor(OpsToRename, BinOp, PA);
352 llvm_unreachable("Unknown type of condition");
357 // Process a block terminating branch, and place relevant operations to be
358 // renamed into OpsToRename.
359 void PredicateInfo::processBranch(BranchInst *BI, BasicBlock *BranchBB,
360 SmallPtrSetImpl<Value *> &OpsToRename) {
361 BasicBlock *FirstBB = BI->getSuccessor(0);
362 BasicBlock *SecondBB = BI->getSuccessor(1);
363 SmallVector<BasicBlock *, 2> SuccsToProcess;
364 SuccsToProcess.push_back(FirstBB);
365 SuccsToProcess.push_back(SecondBB);
366 SmallVector<Value *, 2> ConditionsToProcess;
368 auto InsertHelper = [&](Value *Op, bool isAnd, bool isOr, Value *Cond) {
369 for (auto *Succ : SuccsToProcess) {
370 // Don't try to insert on a self-edge. This is mainly because we will
371 // eliminate during renaming anyway.
372 if (Succ == BranchBB)
374 bool TakenEdge = (Succ == FirstBB);
375 // For and, only insert on the true edge
376 // For or, only insert on the false edge
377 if ((isAnd && !TakenEdge) || (isOr && TakenEdge))
380 new PredicateBranch(Op, BranchBB, Succ, Cond, TakenEdge);
381 addInfoFor(OpsToRename, Op, PB);
382 if (!Succ->getSinglePredecessor())
383 EdgeUsesOnly.insert({BranchBB, Succ});
387 // Match combinations of conditions.
388 CmpInst::Predicate Pred;
391 SmallVector<Value *, 8> CmpOperands;
392 if (match(BI->getCondition(), m_And(m_Cmp(Pred, m_Value(), m_Value()),
393 m_Cmp(Pred, m_Value(), m_Value()))) ||
394 match(BI->getCondition(), m_Or(m_Cmp(Pred, m_Value(), m_Value()),
395 m_Cmp(Pred, m_Value(), m_Value())))) {
396 auto *BinOp = cast<BinaryOperator>(BI->getCondition());
397 if (BinOp->getOpcode() == Instruction::And)
399 else if (BinOp->getOpcode() == Instruction::Or)
401 ConditionsToProcess.push_back(BinOp->getOperand(0));
402 ConditionsToProcess.push_back(BinOp->getOperand(1));
403 ConditionsToProcess.push_back(BI->getCondition());
404 } else if (isa<CmpInst>(BI->getCondition())) {
405 ConditionsToProcess.push_back(BI->getCondition());
407 for (auto Cond : ConditionsToProcess) {
408 if (auto *Cmp = dyn_cast<CmpInst>(Cond)) {
409 collectCmpOps(Cmp, CmpOperands);
410 // Now add our copy infos for our operands
411 for (auto *Op : CmpOperands)
412 InsertHelper(Op, isAnd, isOr, Cmp);
413 } else if (auto *BinOp = dyn_cast<BinaryOperator>(Cond)) {
414 // This must be an AND or an OR.
415 assert((BinOp->getOpcode() == Instruction::And ||
416 BinOp->getOpcode() == Instruction::Or) &&
417 "Should have been an AND or an OR");
418 // The actual value of the binop is not subject to the same restrictions
419 // as the comparison. It's either true or false on the true/false branch.
420 InsertHelper(BinOp, false, false, BinOp);
422 llvm_unreachable("Unknown type of condition");
427 // Process a block terminating switch, and place relevant operations to be
428 // renamed into OpsToRename.
429 void PredicateInfo::processSwitch(SwitchInst *SI, BasicBlock *BranchBB,
430 SmallPtrSetImpl<Value *> &OpsToRename) {
431 Value *Op = SI->getCondition();
432 if ((!isa<Instruction>(Op) && !isa<Argument>(Op)) || Op->hasOneUse())
435 // Remember how many outgoing edges there are to every successor.
436 SmallDenseMap<BasicBlock *, unsigned, 16> SwitchEdges;
437 for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) {
438 BasicBlock *TargetBlock = SI->getSuccessor(i);
439 ++SwitchEdges[TargetBlock];
442 // Now propagate info for each case value
443 for (auto C : SI->cases()) {
444 BasicBlock *TargetBlock = C.getCaseSuccessor();
445 if (SwitchEdges.lookup(TargetBlock) == 1) {
446 PredicateSwitch *PS = new PredicateSwitch(
447 Op, SI->getParent(), TargetBlock, C.getCaseValue(), SI);
448 addInfoFor(OpsToRename, Op, PS);
449 if (!TargetBlock->getSinglePredecessor())
450 EdgeUsesOnly.insert({BranchBB, TargetBlock});
455 // Build predicate info for our function
456 void PredicateInfo::buildPredicateInfo() {
457 DT.updateDFSNumbers();
458 // Collect operands to rename from all conditional branch terminators, as well
459 // as assume statements.
460 SmallPtrSet<Value *, 8> OpsToRename;
461 for (auto DTN : depth_first(DT.getRootNode())) {
462 BasicBlock *BranchBB = DTN->getBlock();
463 if (auto *BI = dyn_cast<BranchInst>(BranchBB->getTerminator())) {
464 if (!BI->isConditional())
466 // Can't insert conditional information if they all go to the same place.
467 if (BI->getSuccessor(0) == BI->getSuccessor(1))
469 processBranch(BI, BranchBB, OpsToRename);
470 } else if (auto *SI = dyn_cast<SwitchInst>(BranchBB->getTerminator())) {
471 processSwitch(SI, BranchBB, OpsToRename);
474 for (auto &Assume : AC.assumptions()) {
475 if (auto *II = dyn_cast_or_null<IntrinsicInst>(Assume))
476 if (DT.isReachableFromEntry(II->getParent()))
477 processAssume(II, II->getParent(), OpsToRename);
479 // Now rename all our operations.
480 renameUses(OpsToRename);
483 // Create a ssa_copy declaration with custom mangling, because
484 // Intrinsic::getDeclaration does not handle overloaded unnamed types properly:
485 // all unnamed types get mangled to the same string. We use the pointer
486 // to the type as name here, as it guarantees unique names for different
487 // types and we remove the declarations when destroying PredicateInfo.
488 // It is a workaround for PR38117, because solving it in a fully general way is
490 static Function *getCopyDeclaration(Module *M, Type *Ty) {
491 std::string Name = "llvm.ssa.copy." + utostr((uintptr_t) Ty);
492 return cast<Function>(
493 M->getOrInsertFunction(Name,
494 getType(M->getContext(), Intrinsic::ssa_copy, Ty))
498 // Given the renaming stack, make all the operands currently on the stack real
499 // by inserting them into the IR. Return the last operation's value.
500 Value *PredicateInfo::materializeStack(unsigned int &Counter,
501 ValueDFSStack &RenameStack,
503 // Find the first thing we have to materialize
504 auto RevIter = RenameStack.rbegin();
505 for (; RevIter != RenameStack.rend(); ++RevIter)
509 size_t Start = RevIter - RenameStack.rbegin();
510 // The maximum number of things we should be trying to materialize at once
511 // right now is 4, depending on if we had an assume, a branch, and both used
512 // and of conditions.
513 for (auto RenameIter = RenameStack.end() - Start;
514 RenameIter != RenameStack.end(); ++RenameIter) {
516 RenameIter == RenameStack.begin() ? OrigOp : (RenameIter - 1)->Def;
517 ValueDFS &Result = *RenameIter;
518 auto *ValInfo = Result.PInfo;
519 // For edge predicates, we can just place the operand in the block before
520 // the terminator. For assume, we have to place it right before the assume
521 // to ensure we dominate all of our uses. Always insert right before the
522 // relevant instruction (terminator, assume), so that we insert in proper
523 // order in the case of multiple predicateinfo in the same block.
524 if (isa<PredicateWithEdge>(ValInfo)) {
525 IRBuilder<> B(getBranchTerminator(ValInfo));
526 Function *IF = getCopyDeclaration(F.getParent(), Op->getType());
527 if (empty(IF->users()))
528 CreatedDeclarations.insert(IF);
530 B.CreateCall(IF, Op, Op->getName() + "." + Twine(Counter++));
531 PredicateMap.insert({PIC, ValInfo});
534 auto *PAssume = dyn_cast<PredicateAssume>(ValInfo);
536 "Should not have gotten here without it being an assume");
537 IRBuilder<> B(PAssume->AssumeInst);
538 Function *IF = getCopyDeclaration(F.getParent(), Op->getType());
539 if (empty(IF->users()))
540 CreatedDeclarations.insert(IF);
541 CallInst *PIC = B.CreateCall(IF, Op);
542 PredicateMap.insert({PIC, ValInfo});
546 return RenameStack.back().Def;
549 // Instead of the standard SSA renaming algorithm, which is O(Number of
550 // instructions), and walks the entire dominator tree, we walk only the defs +
551 // uses. The standard SSA renaming algorithm does not really rely on the
552 // dominator tree except to order the stack push/pops of the renaming stacks, so
553 // that defs end up getting pushed before hitting the correct uses. This does
554 // not require the dominator tree, only the *order* of the dominator tree. The
555 // complete and correct ordering of the defs and uses, in dominator tree is
556 // contained in the DFS numbering of the dominator tree. So we sort the defs and
557 // uses into the DFS ordering, and then just use the renaming stack as per
558 // normal, pushing when we hit a def (which is a predicateinfo instruction),
559 // popping when we are out of the dfs scope for that def, and replacing any uses
560 // with top of stack if it exists. In order to handle liveness without
561 // propagating liveness info, we don't actually insert the predicateinfo
562 // instruction def until we see a use that it would dominate. Once we see such
563 // a use, we materialize the predicateinfo instruction in the right place and
566 // TODO: Use this algorithm to perform fast single-variable renaming in
567 // promotememtoreg and memoryssa.
568 void PredicateInfo::renameUses(SmallPtrSetImpl<Value *> &OpSet) {
569 // Sort OpsToRename since we are going to iterate it.
570 SmallVector<Value *, 8> OpsToRename(OpSet.begin(), OpSet.end());
571 auto Comparator = [&](const Value *A, const Value *B) {
572 return valueComesBefore(OI, A, B);
574 llvm::sort(OpsToRename, Comparator);
575 ValueDFS_Compare Compare(OI);
576 // Compute liveness, and rename in O(uses) per Op.
577 for (auto *Op : OpsToRename) {
578 LLVM_DEBUG(dbgs() << "Visiting " << *Op << "\n");
579 unsigned Counter = 0;
580 SmallVector<ValueDFS, 16> OrderedUses;
581 const auto &ValueInfo = getValueInfo(Op);
582 // Insert the possible copies into the def/use list.
583 // They will become real copies if we find a real use for them, and never
584 // created otherwise.
585 for (auto &PossibleCopy : ValueInfo.Infos) {
587 // Determine where we are going to place the copy by the copy type.
588 // The predicate info for branches always come first, they will get
589 // materialized in the split block at the top of the block.
590 // The predicate info for assumes will be somewhere in the middle,
591 // it will get materialized in front of the assume.
592 if (const auto *PAssume = dyn_cast<PredicateAssume>(PossibleCopy)) {
593 VD.LocalNum = LN_Middle;
594 DomTreeNode *DomNode = DT.getNode(PAssume->AssumeInst->getParent());
597 VD.DFSIn = DomNode->getDFSNumIn();
598 VD.DFSOut = DomNode->getDFSNumOut();
599 VD.PInfo = PossibleCopy;
600 OrderedUses.push_back(VD);
601 } else if (isa<PredicateWithEdge>(PossibleCopy)) {
602 // If we can only do phi uses, we treat it like it's in the branch
603 // block, and handle it specially. We know that it goes last, and only
604 // dominate phi uses.
605 auto BlockEdge = getBlockEdge(PossibleCopy);
606 if (EdgeUsesOnly.count(BlockEdge)) {
607 VD.LocalNum = LN_Last;
608 auto *DomNode = DT.getNode(BlockEdge.first);
610 VD.DFSIn = DomNode->getDFSNumIn();
611 VD.DFSOut = DomNode->getDFSNumOut();
612 VD.PInfo = PossibleCopy;
614 OrderedUses.push_back(VD);
617 // Otherwise, we are in the split block (even though we perform
618 // insertion in the branch block).
619 // Insert a possible copy at the split block and before the branch.
620 VD.LocalNum = LN_First;
621 auto *DomNode = DT.getNode(BlockEdge.second);
623 VD.DFSIn = DomNode->getDFSNumIn();
624 VD.DFSOut = DomNode->getDFSNumOut();
625 VD.PInfo = PossibleCopy;
626 OrderedUses.push_back(VD);
632 convertUsesToDFSOrdered(Op, OrderedUses);
633 // Here we require a stable sort because we do not bother to try to
634 // assign an order to the operands the uses represent. Thus, two
635 // uses in the same instruction do not have a strict sort order
636 // currently and will be considered equal. We could get rid of the
637 // stable sort by creating one if we wanted.
638 llvm::stable_sort(OrderedUses, Compare);
639 SmallVector<ValueDFS, 8> RenameStack;
640 // For each use, sorted into dfs order, push values and replaces uses with
641 // top of stack, which will represent the reaching def.
642 for (auto &VD : OrderedUses) {
643 // We currently do not materialize copy over copy, but we should decide if
645 bool PossibleCopy = VD.PInfo != nullptr;
646 if (RenameStack.empty()) {
647 LLVM_DEBUG(dbgs() << "Rename Stack is empty\n");
649 LLVM_DEBUG(dbgs() << "Rename Stack Top DFS numbers are ("
650 << RenameStack.back().DFSIn << ","
651 << RenameStack.back().DFSOut << ")\n");
654 LLVM_DEBUG(dbgs() << "Current DFS numbers are (" << VD.DFSIn << ","
655 << VD.DFSOut << ")\n");
657 bool ShouldPush = (VD.Def || PossibleCopy);
658 bool OutOfScope = !stackIsInScope(RenameStack, VD);
659 if (OutOfScope || ShouldPush) {
660 // Sync to our current scope.
661 popStackUntilDFSScope(RenameStack, VD);
663 RenameStack.push_back(VD);
666 // If we get to this point, and the stack is empty we must have a use
667 // with no renaming needed, just skip it.
668 if (RenameStack.empty())
670 // Skip values, only want to rename the uses
671 if (VD.Def || PossibleCopy)
673 if (!DebugCounter::shouldExecute(RenameCounter)) {
674 LLVM_DEBUG(dbgs() << "Skipping execution due to debug counter\n");
677 ValueDFS &Result = RenameStack.back();
679 // If the possible copy dominates something, materialize our stack up to
680 // this point. This ensures every comparison that affects our operation
681 // ends up with predicateinfo.
683 Result.Def = materializeStack(Counter, RenameStack, Op);
685 LLVM_DEBUG(dbgs() << "Found replacement " << *Result.Def << " for "
686 << *VD.U->get() << " in " << *(VD.U->getUser())
688 assert(DT.dominates(cast<Instruction>(Result.Def), *VD.U) &&
689 "Predicateinfo def should have dominated this use");
690 VD.U->set(Result.Def);
695 PredicateInfo::ValueInfo &PredicateInfo::getOrCreateValueInfo(Value *Operand) {
696 auto OIN = ValueInfoNums.find(Operand);
697 if (OIN == ValueInfoNums.end()) {
699 ValueInfos.resize(ValueInfos.size() + 1);
700 // This will use the new size and give us a 0 based number of the info
701 auto InsertResult = ValueInfoNums.insert({Operand, ValueInfos.size() - 1});
702 assert(InsertResult.second && "Value info number already existed?");
703 return ValueInfos[InsertResult.first->second];
705 return ValueInfos[OIN->second];
708 const PredicateInfo::ValueInfo &
709 PredicateInfo::getValueInfo(Value *Operand) const {
710 auto OINI = ValueInfoNums.lookup(Operand);
711 assert(OINI != 0 && "Operand was not really in the Value Info Numbers");
712 assert(OINI < ValueInfos.size() &&
713 "Value Info Number greater than size of Value Info Table");
714 return ValueInfos[OINI];
717 PredicateInfo::PredicateInfo(Function &F, DominatorTree &DT,
719 : F(F), DT(DT), AC(AC), OI(&DT) {
720 // Push an empty operand info so that we can detect 0 as not finding one
721 ValueInfos.resize(1);
722 buildPredicateInfo();
725 // Remove all declarations we created . The PredicateInfo consumers are
726 // responsible for remove the ssa_copy calls created.
727 PredicateInfo::~PredicateInfo() {
728 // Collect function pointers in set first, as SmallSet uses a SmallVector
729 // internally and we have to remove the asserting value handles first.
730 SmallPtrSet<Function *, 20> FunctionPtrs;
731 for (auto &F : CreatedDeclarations)
732 FunctionPtrs.insert(&*F);
733 CreatedDeclarations.clear();
735 for (Function *F : FunctionPtrs) {
736 assert(F->user_begin() == F->user_end() &&
737 "PredicateInfo consumer did not remove all SSA copies.");
738 F->eraseFromParent();
742 void PredicateInfo::verifyPredicateInfo() const {}
744 char PredicateInfoPrinterLegacyPass::ID = 0;
746 PredicateInfoPrinterLegacyPass::PredicateInfoPrinterLegacyPass()
748 initializePredicateInfoPrinterLegacyPassPass(
749 *PassRegistry::getPassRegistry());
752 void PredicateInfoPrinterLegacyPass::getAnalysisUsage(AnalysisUsage &AU) const {
753 AU.setPreservesAll();
754 AU.addRequiredTransitive<DominatorTreeWrapperPass>();
755 AU.addRequired<AssumptionCacheTracker>();
758 // Replace ssa_copy calls created by PredicateInfo with their operand.
759 static void replaceCreatedSSACopys(PredicateInfo &PredInfo, Function &F) {
760 for (auto I = inst_begin(F), E = inst_end(F); I != E;) {
761 Instruction *Inst = &*I++;
762 const auto *PI = PredInfo.getPredicateInfoFor(Inst);
763 auto *II = dyn_cast<IntrinsicInst>(Inst);
764 if (!PI || !II || II->getIntrinsicID() != Intrinsic::ssa_copy)
767 Inst->replaceAllUsesWith(II->getOperand(0));
768 Inst->eraseFromParent();
772 bool PredicateInfoPrinterLegacyPass::runOnFunction(Function &F) {
773 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
774 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
775 auto PredInfo = make_unique<PredicateInfo>(F, DT, AC);
776 PredInfo->print(dbgs());
777 if (VerifyPredicateInfo)
778 PredInfo->verifyPredicateInfo();
780 replaceCreatedSSACopys(*PredInfo, F);
784 PreservedAnalyses PredicateInfoPrinterPass::run(Function &F,
785 FunctionAnalysisManager &AM) {
786 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
787 auto &AC = AM.getResult<AssumptionAnalysis>(F);
788 OS << "PredicateInfo for function: " << F.getName() << "\n";
789 auto PredInfo = make_unique<PredicateInfo>(F, DT, AC);
792 replaceCreatedSSACopys(*PredInfo, F);
793 return PreservedAnalyses::all();
796 /// An assembly annotator class to print PredicateInfo information in
798 class PredicateInfoAnnotatedWriter : public AssemblyAnnotationWriter {
799 friend class PredicateInfo;
800 const PredicateInfo *PredInfo;
803 PredicateInfoAnnotatedWriter(const PredicateInfo *M) : PredInfo(M) {}
805 virtual void emitBasicBlockStartAnnot(const BasicBlock *BB,
806 formatted_raw_ostream &OS) {}
808 virtual void emitInstructionAnnot(const Instruction *I,
809 formatted_raw_ostream &OS) {
810 if (const auto *PI = PredInfo->getPredicateInfoFor(I)) {
811 OS << "; Has predicate info\n";
812 if (const auto *PB = dyn_cast<PredicateBranch>(PI)) {
813 OS << "; branch predicate info { TrueEdge: " << PB->TrueEdge
814 << " Comparison:" << *PB->Condition << " Edge: [";
815 PB->From->printAsOperand(OS);
817 PB->To->printAsOperand(OS);
819 } else if (const auto *PS = dyn_cast<PredicateSwitch>(PI)) {
820 OS << "; switch predicate info { CaseValue: " << *PS->CaseValue
821 << " Switch:" << *PS->Switch << " Edge: [";
822 PS->From->printAsOperand(OS);
824 PS->To->printAsOperand(OS);
826 } else if (const auto *PA = dyn_cast<PredicateAssume>(PI)) {
827 OS << "; assume predicate info {"
828 << " Comparison:" << *PA->Condition << " }\n";
834 void PredicateInfo::print(raw_ostream &OS) const {
835 PredicateInfoAnnotatedWriter Writer(this);
836 F.print(OS, &Writer);
839 void PredicateInfo::dump() const {
840 PredicateInfoAnnotatedWriter Writer(this);
841 F.print(dbgs(), &Writer);
844 PreservedAnalyses PredicateInfoVerifierPass::run(Function &F,
845 FunctionAnalysisManager &AM) {
846 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
847 auto &AC = AM.getResult<AssumptionAnalysis>(F);
848 make_unique<PredicateInfo>(F, DT, AC)->verifyPredicateInfo();
850 return PreservedAnalyses::all();