Index: include/llvm/Transforms/Utils/PredicateInfo.h =================================================================== --- include/llvm/Transforms/Utils/PredicateInfo.h +++ include/llvm/Transforms/Utils/PredicateInfo.h @@ -53,6 +53,7 @@ #define LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseSet.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/ilist.h" @@ -91,7 +92,7 @@ class raw_ostream; class OrderedBasicBlock; -enum PredicateType { PT_Branch, PT_Assume }; +enum PredicateType { PT_Branch, PT_Assume, PT_Switch }; // Base class for all predicate information we provide. // All of our predicate information has at least a comparison. @@ -102,25 +103,36 @@ // This can be use by passes, when destroying predicateinfo, to know // whether they can just drop the intrinsic, or have to merge metadata. Value *OriginalOp; - CmpInst *Comparison; PredicateBase(const PredicateBase &) = delete; PredicateBase &operator=(const PredicateBase &) = delete; PredicateBase() = delete; virtual ~PredicateBase() = default; protected: - PredicateBase(PredicateType PT, Value *Op, CmpInst *Comparison) - : Type(PT), OriginalOp(Op), Comparison(Comparison) {} + PredicateBase(PredicateType PT, Value *Op) : Type(PT), OriginalOp(Op) {} +}; + +class PredicateWithComparison : public PredicateBase { +public: + CmpInst *Comparison; + static inline bool classof(const PredicateBase *PB) { + return PB->Type == PT_Assume || PB->Type == PT_Branch; + } + +protected: + PredicateWithComparison(PredicateType PT, Value *Op, CmpInst *Comparison) + : PredicateBase(PT, Op), Comparison(Comparison) {} }; // Provides predicate information for assumes. Since assumes are always true, // we simply provide the assume instruction, so you can tell your relative // position to it. -class PredicateAssume : public PredicateBase { +class PredicateAssume : public PredicateWithComparison { public: IntrinsicInst *AssumeInst; PredicateAssume(Value *Op, IntrinsicInst *AssumeInst, CmpInst *Comparison) - : PredicateBase(PT_Assume, Op, Comparison), AssumeInst(AssumeInst) {} + : PredicateWithComparison(PT_Assume, Op, Comparison), + AssumeInst(AssumeInst) {} PredicateAssume() = delete; static inline bool classof(const PredicateBase *PB) { return PB->Type == PT_Assume; @@ -128,7 +140,7 @@ }; // Provides predicate information for branches. -class PredicateBranch : public PredicateBase { +class PredicateBranch : public PredicateWithComparison { public: // This is the block that is conditional upon the comparison. BasicBlock *BranchBB; @@ -138,7 +150,7 @@ bool TrueEdge; PredicateBranch(Value *Op, BasicBlock *BranchBB, BasicBlock *SplitBB, CmpInst *Comparison, bool TakenEdge) - : PredicateBase(PT_Branch, Op, Comparison), BranchBB(BranchBB), + : PredicateWithComparison(PT_Branch, Op, Comparison), BranchBB(BranchBB), SplitBB(SplitBB), TrueEdge(TakenEdge) {} PredicateBranch() = delete; static inline bool classof(const PredicateBase *PB) { @@ -146,6 +158,25 @@ } }; +class PredicateSwitch : public PredicateBase { +public: + // This is the block of the switch. + BasicBlock *SwitchBB; + // This is the target block of the case statement. + BasicBlock *TargetBB; + // This is the case value for the switch to that block. + Value *CaseValue; + // This is the switch instruction. + SwitchInst *Switch; + PredicateSwitch(Value *Op, BasicBlock *SwitchBB, BasicBlock *TargetBB, + Value *CaseValue, SwitchInst *SI) + : PredicateBase(PT_Switch, Op), SwitchBB(SwitchBB), TargetBB(TargetBB), + CaseValue(CaseValue), Switch(SI) {} + static inline bool classof(const PredicateBase *PB) { + return PB->Type == PT_Switch; + } +}; + // This name is used in a few places, so kick it into their own namespace namespace PredicateInfoClasses { struct ValueDFS; @@ -188,13 +219,14 @@ void buildPredicateInfo(); void processAssume(IntrinsicInst *, BasicBlock *, SmallPtrSetImpl &); void processBranch(BranchInst *, BasicBlock *, SmallPtrSetImpl &); + void processSwitch(SwitchInst *, BasicBlock *, SmallPtrSetImpl &); void renameUses(SmallPtrSetImpl &); using ValueDFS = PredicateInfoClasses::ValueDFS; typedef SmallVectorImpl ValueDFSStack; void convertUsesToDFSOrdered(Value *, SmallVectorImpl &); Value *materializeStack(unsigned int &, ValueDFSStack &, Value *); - bool stackIsInScope(const ValueDFSStack &, int DFSIn, int DFSOut) const; - void popStackUntilDFSScope(ValueDFSStack &, int DFSIn, int DFSOut); + bool stackIsInScope(const ValueDFSStack &, const ValueDFS &) const; + void popStackUntilDFSScope(ValueDFSStack &, const ValueDFS &); ValueInfo &getOrCreateValueInfo(Value *); const ValueInfo &getValueInfo(Value *) const; Function &F; @@ -214,6 +246,9 @@ DenseMap ValueInfoNums; // OrderedBasicBlocks used during sorting uses DenseMap> OBBMap; + // The set of edges along which we can only handle phi uses, due to critical + // edges. + DenseSet> PhiUsesOnly; }; // This pass does eager building and then printing of PredicateInfo. It is used Index: lib/Transforms/Scalar/NewGVN.cpp =================================================================== --- lib/Transforms/Scalar/NewGVN.cpp +++ lib/Transforms/Scalar/NewGVN.cpp @@ -64,6 +64,7 @@ #include "llvm/Analysis/MemoryBuiltins.h" #include "llvm/Analysis/MemoryLocation.h" #include "llvm/Analysis/TargetLibraryInfo.h" +#include "llvm/IR/ConstantRange.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/GlobalVariable.h" @@ -81,13 +82,13 @@ #include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Transforms/Utils/Local.h" #include "llvm/Transforms/Utils/MemorySSA.h" +#include "llvm/Transforms/Utils/PredicateInfo.h" #include #include #include using namespace llvm; using namespace PatternMatch; using namespace llvm::GVNExpression; - #define DEBUG_TYPE "newgvn" STATISTIC(NumGVNInstrDeleted, "Number of instructions deleted"); @@ -208,9 +209,13 @@ AliasAnalysis *AA; MemorySSA *MSSA; MemorySSAWalker *MSSAWalker; + PredicateInfo *PredInfo; BumpPtrAllocator ExpressionAllocator; ArrayRecycler ArgRecycler; + // Number of function arguments, used by ranking + unsigned int NumFuncArgs; + // Congruence class info. CongruenceClass *InitialClass; std::vector CongruenceClasses; @@ -288,7 +293,6 @@ AU.addRequired(); AU.addRequired(); AU.addRequired(); - AU.addPreserved(); AU.addPreserved(); } @@ -337,6 +341,7 @@ const Expression *performSymbolicPHIEvaluation(Instruction *); const Expression *performSymbolicAggrValueEvaluation(Instruction *); const Expression *performSymbolicCmpEvaluation(Instruction *); + const Expression *performSymbolicPredicateInfoEvaluation(Instruction *); // Congruence finding. Value *lookupOperandLeader(Value *) const; @@ -347,6 +352,9 @@ MemoryAccess *lookupMemoryAccessEquiv(MemoryAccess *) const; bool isMemoryAccessTop(const MemoryAccess *) const; + // Ranking + unsigned int getRank(Value *V) const; + // Reachability handling. void updateReachableEdge(BasicBlock *, BasicBlock *); void processOutgoingEdges(TerminatorInst *, BasicBlock *); @@ -573,7 +581,7 @@ // Sort the operand value numbers so xx get the same value // number. CmpInst::Predicate Predicate = CI->getPredicate(); - if (E->getOperand(0) > E->getOperand(1)) { + if (getRank(E->getOperand(0)) > getRank(E->getOperand(1))) { E->swapOperands(0, 1); Predicate = CmpInst::getSwappedPredicate(Predicate); } @@ -828,12 +836,90 @@ return E; } +const Expression * +NewGVN::performSymbolicPredicateInfoEvaluation(Instruction *I) { + auto *PI = PredInfo->getPredicateInfoFor(I); + if (!PI) + return nullptr; + DEBUG(dbgs() << "Found predicate info from instruction !\n"); + if (auto *PSwitch = dyn_cast(PI)) { + // For switch statements, we know the value of the condition, and that is + // what Op must be. + assert(I->getOperand(0) == PSwitch->Switch->getCondition() && + "Found a predicateswitch info that seems to be about a non-switch " + "condition"); + assert(isa(PSwitch->CaseValue)); + return createConstantExpression(cast(PSwitch->CaseValue)); + } + if (auto *PWC = dyn_cast(PI)) { + auto *CopyOf = I->getOperand(0); + auto *Cmp = PWC->Comparison; + // If this is an assume predicate and a copy of a comparison, it must be + // true. + if (isa(PI) && CopyOf == Cmp) + return createConstantExpression(ConstantInt::getTrue(Cmp->getType())); + + Value *FirstOp = lookupOperandLeader(Cmp->getOperand(0)); + Value *SecondOp = lookupOperandLeader(Cmp->getOperand(1)); + // Sort the ops + CmpInst::Predicate Predicate = Cmp->getPredicate(); + // FIXME: We should really be ranking them here + if (getRank(FirstOp) > getRank(SecondOp)) { + std::swap(FirstOp, SecondOp); + Predicate = CmpInst::getSwappedPredicate(Predicate); + } + if (isa(PI)) { + // If the comparison is true when the operands are equal, then we know + // the operands are equal, because assumes must always be true. + if (CmpInst::isTrueWhenEqual(Predicate)) + if (auto *C = dyn_cast(FirstOp)) + return createConstantExpression(C); + return createVariableExpression(FirstOp); + } else if (const auto *PBranch = dyn_cast(PI)) { + // If this is a copy of the comparison, it's value is determined by the + // edge. + if (CopyOf == Cmp) { + if (PBranch->TrueEdge) + return createConstantExpression(ConstantInt::getTrue(Cmp->getType())); + return createConstantExpression(ConstantInt::getFalse(Cmp->getType())); + } else if ((PBranch->TrueEdge && CmpInst::isTrueWhenEqual(Predicate)) || + (!PBranch->TrueEdge && CmpInst::isFalseWhenEqual(Predicate))) { + // If we are *not* a copy of the comparison, we may equal to the other + // operand when the predicate implies something about equality of + // operations. + if (auto *C = dyn_cast(FirstOp)) + return createConstantExpression(C); + return createVariableExpression(FirstOp); + } else if (((PBranch->TrueEdge && Predicate == CmpInst::FCMP_OEQ) || + (!PBranch->TrueEdge && Predicate == CmpInst::FCMP_UNE)) && + isa(FirstOp) && + !cast(FirstOp)->isZero()) { + return createConstantExpression(cast(FirstOp)); + } + } + } + return nullptr; +} + // Evaluate read only and pure calls, and create an expression result. const Expression *NewGVN::performSymbolicCallEvaluation(Instruction *I) { auto *CI = cast(I); - if (AA->doesNotAccessMemory(CI)) + if (auto *II = dyn_cast(I)) { + // Things with the returned attribute are copies of arguments + if (auto *ReturnedValue = II->getReturnedArgOperand()) { + if (II->getIntrinsicID() == Intrinsic::ssa_copy) { + const Expression *Result = performSymbolicPredicateInfoEvaluation(I); + if (Result) + return Result; + } + if (auto *C = dyn_cast(ReturnedValue)) + return createConstantExpression(C); + return createVariableExpression(ReturnedValue); + } + } + if (AA->doesNotAccessMemory(CI)) { return createCallExpression(CI, nullptr); - if (AA->onlyReadsMemory(CI)) { + } else if (AA->onlyReadsMemory(CI)) { MemoryAccess *DefiningAccess = MSSAWalker->getClobberingMemoryAccess(CI); return createCallExpression(CI, lookupMemoryAccessEquiv(DefiningAccess)); } @@ -964,9 +1050,8 @@ // expression. assert(II->getNumArgOperands() == 2 && "Expect two args for recognised intrinsics."); - return createBinaryExpression(Opcode, EI->getType(), - II->getArgOperand(0), - II->getArgOperand(1)); + return createBinaryExpression( + Opcode, EI->getType(), II->getArgOperand(0), II->getArgOperand(1)); } } } @@ -974,16 +1059,76 @@ return createAggregateValueExpression(I); } const Expression *NewGVN::performSymbolicCmpEvaluation(Instruction *I) { - CmpInst *CI = dyn_cast(I); - // See if our operands are equal and that implies something. + auto *CI = dyn_cast(I); + // See if our operands are equal to those of a previous predicate, and if so, + // if it implies true or false. auto Op0 = lookupOperandLeader(CI->getOperand(0)); auto Op1 = lookupOperandLeader(CI->getOperand(1)); + auto Predicate = CI->getPredicate(); + if (getRank(Op0) > getRank(Op1)) { + std::swap(Op0, Op1); + Predicate = CmpInst::getSwappedPredicate(CI->getPredicate()); + } + + // Avoid processing the same info twice + const PredicateBase *LastPredInfo = nullptr; + + // See if we know something about the comparison itself, like it is the target + // of an assume. + auto *CmpPI = PredInfo->getPredicateInfoFor(I); + if (dyn_cast_or_null(CmpPI)) + return createConstantExpression(ConstantInt::getTrue(CI->getType())); + + // See if we know something just from the operands themselves if (Op0 == Op1) { if (CI->isTrueWhenEqual()) return createConstantExpression(ConstantInt::getTrue(CI->getType())); else if (CI->isFalseWhenEqual()) return createConstantExpression(ConstantInt::getFalse(CI->getType())); } + + // See if our operands have predicate info, so that we may be able to derive + // something from a previous comparison. + for (const auto &Op : CI->operands()) { + auto *PI = PredInfo->getPredicateInfoFor(Op); + if (const auto *PBranch = dyn_cast_or_null(PI)) { + if (PI == LastPredInfo) + continue; + LastPredInfo = PI; + + // TODO: Along the false edge, we may know more things too, like icmp of + // same operands is false. + // + auto *BranchCond = PBranch->Comparison; + if (lookupOperandLeader(BranchCond->getOperand(0)) == Op0 && + lookupOperandLeader(BranchCond->getOperand(1)) == Op1) { + if (PBranch->TrueEdge) { + // If we know the previous predicate is true and we are in the true + // edge then we may be implied true or false. + if (CI->isImpliedTrueByMatchingCmp(BranchCond->getPredicate())) + return createConstantExpression( + ConstantInt::getTrue(CI->getType())); + if (CI->isImpliedFalseByMatchingCmp(BranchCond->getPredicate())) + return createConstantExpression( + ConstantInt::getFalse(CI->getType())); + } else { + // Just handle the ne and eq cases, where if we have the same + // operands, we may know something. + if (BranchCond->getPredicate() == CI->getPredicate()) { + // Same predicate, same ops,we know it was false, so this is false. + return createConstantExpression( + ConstantInt::getFalse(CI->getType())); + } else if (BranchCond->getPredicate() == CI->getInversePredicate()) { + // Inverse predicate, we know the other was false, so this is true. + // FIXME: Double check this + return createConstantExpression( + ConstantInt::getTrue(CI->getType())); + } + } + } + } + } + // Create expression will take care of simplifyCmpInst return createExpression(I); } @@ -1696,11 +1841,13 @@ TargetLibraryInfo *_TLI, AliasAnalysis *_AA, MemorySSA *_MSSA) { bool Changed = false; + NumFuncArgs = F.arg_size(); DT = _DT; AC = _AC; TLI = _TLI; AA = _AA; MSSA = _MSSA; + PredInfo = new PredicateInfo(F, *DT, *AC); DL = &F.getParent()->getDataLayout(); MSSAWalker = MSSA->getWalker(); @@ -1775,6 +1922,9 @@ while (TouchedInstructions.any()) { ++Iterations; // Walk through all the instructions in all the blocks in RPO. + // TODO: As we hit a new block, we should push and pop equalities into a + // table lookupOperandLeader can use, to catch things PredicateInfo + // might miss, like edge-only equivalences. for (int InstrNum = TouchedInstructions.find_first(); InstrNum != -1; InstrNum = TouchedInstructions.find_next(InstrNum)) { @@ -2327,8 +2477,13 @@ // If we replaced something in an instruction, handle the patching of // metadata. - if (auto *ReplacedInst = dyn_cast(MemberUse->get())) - patchReplacementInstruction(ReplacedInst, Result); + if (auto *ReplacedInst = dyn_cast(MemberUse->get())) { + // Skip this if we are replacing predicateinfo with it's original + // operand, as we already know we can just drop it. + auto *PI = PredInfo->getPredicateInfoFor(ReplacedInst); + if (!PI || Result != PI->OriginalOp) + patchReplacementInstruction(ReplacedInst, Result); + } assert(isa(MemberUse->getUser())); MemberUse->set(Result); @@ -2393,3 +2548,18 @@ return AnythingReplaced; } + +unsigned int NewGVN::getRank(Value *V) const { + if (isa(V)) + return 0; + else if (Argument *A = dyn_cast(V)) + return 1 + A->getArgNo(); + + // Need to shift the instruction DFS by number of arguments + 1 to account for + // the constant and argument ranking above. + unsigned Result = InstrDFS.lookup(V); + if (Result > 0) + return 2 + NumFuncArgs + Result; + // Unreachable or something else, just return a really large number. + return ~0; +} Index: lib/Transforms/Utils/PredicateInfo.cpp =================================================================== --- lib/Transforms/Utils/PredicateInfo.cpp +++ lib/Transforms/Utils/PredicateInfo.cpp @@ -48,6 +48,41 @@ static cl::opt VerifyPredicateInfo( "verify-predicateinfo", cl::init(false), cl::Hidden, cl::desc("Verify PredicateInfo in legacy printer pass.")); +namespace { + +// Given a predicate info that is a type of branching terminator, get the +// branching block. +const BasicBlock *getBranchBlock(PredicateBase *PB) { + if (auto *PBranch = dyn_cast(PB)) + return PBranch->BranchBB; + if (auto *PSwitch = dyn_cast(PB)) + return PSwitch->SwitchBB; + llvm_unreachable("Only branches and switches should have PHIOnly defs that " + "require branch blocks"); +} + +// Given a predicate info that is a type of branching terminator, get the +// branching terminator. +static Instruction *getBranchTerminator(PredicateBase *PB) { + if (auto *PBranch = dyn_cast(PB)) + return PBranch->BranchBB->getTerminator(); + if (auto *PSwitch = dyn_cast(PB)) + return PSwitch->SwitchBB->getTerminator(); + llvm_unreachable("Not a predicate info type we know how to handle"); +} + +// Given a predicate info that is a type of branching terminator, get the +// edge this predicate info represents +const std::pair +getBlockEdge(const PredicateBase *PB) { + if (auto *PBranch = dyn_cast(PB)) + return std::make_pair(PBranch->BranchBB, PBranch->SplitBB); + if (auto *PSwitch = dyn_cast(PB)) + return std::make_pair(PSwitch->SwitchBB, PSwitch->TargetBB); + llvm_unreachable("Unhandle predicate info type"); +} +} + namespace llvm { namespace PredicateInfoClasses { enum LocalNum { @@ -66,10 +101,12 @@ int DFSIn = 0; int DFSOut = 0; unsigned int LocalNum = LN_Middle; - PredicateBase *PInfo = nullptr; // Only one of Def or Use will be set. Value *Def = nullptr; Use *U = nullptr; + // Neither PInfo nor PhiOnly participate in the ordering + PredicateBase *PInfo = nullptr; + bool PhiOnly = false; }; // This compares ValueDFS structures, creating OrderedBasicBlocks where @@ -90,12 +127,42 @@ bool SameBlock = std::tie(A.DFSIn, A.DFSOut) == std::tie(B.DFSIn, B.DFSOut); + // We want to put the def that will get used for a given set of phi uses, + // before those phi uses. + // So we sort by edge, then by def. + // Note that only phi nodes uses and defs can come last. + if (SameBlock && A.LocalNum == LN_Last && B.LocalNum == LN_Last) + return comparePHIRelated(A, B); + if (!SameBlock || A.LocalNum != LN_Middle || B.LocalNum != LN_Middle) return std::tie(A.DFSIn, A.DFSOut, A.LocalNum, A.Def, A.U) < std::tie(B.DFSIn, B.DFSOut, B.LocalNum, B.Def, B.U); return localComesBefore(A, B); } + // For a phi use, or a non-materialized def, return the edge it represents. + const std::pair + getBlockEdge(const ValueDFS &VD) const { + if (!VD.Def && VD.U) { + auto *PHI = cast(VD.U->getUser()); + return std::make_pair(PHI->getIncomingBlock(*VD.U), PHI->getParent()); + } + // This is really a non-materialized def. + return ::getBlockEdge(VD.PInfo); + } + + // For two phi related values, return the ordering. + bool comparePHIRelated(const ValueDFS &A, const ValueDFS &B) const { + auto &ABlockEdge = getBlockEdge(A); + auto &BBlockEdge = getBlockEdge(B); + if (ABlockEdge < BBlockEdge) + return true; + if (ABlockEdge > BBlockEdge) + return false; + // Now sort defs before uses + return std::tie(A.Def, A.U) < std::tie(B.Def, B.U); + } + // Get the definition of an instruction that occurs in the middle of a block. Value *getMiddleDef(const ValueDFS &VD) const { if (VD.Def) @@ -160,16 +227,35 @@ } // namespace PredicateInfoClasses -bool PredicateInfo::stackIsInScope(const ValueDFSStack &Stack, int DFSIn, - int DFSOut) const { +bool PredicateInfo::stackIsInScope(const ValueDFSStack &Stack, + const ValueDFS &VDUse) const { if (Stack.empty()) return false; - return DFSIn >= Stack.back().DFSIn && DFSOut <= Stack.back().DFSOut; + // If it's a phi only use, make sure it's for this phi node edge, and that the + // use is in a phi node. If it's anything else, and the top of the stack is + // phionly, we need to pop the stack. We deliberately sort phi uses next to + // the defs they must go with so that we can know it's time to pop the stack + // when we hit the end of the phi uses for a given def. + if (Stack.back().PhiOnly) { + if (!VDUse.U) + return false; + auto *PHI = dyn_cast(VDUse.U->getUser()); + if (!PHI) + return false; + // The only phionly defs should be branch or switch info. + // Check that this is our edge. + BasicBlock *EdgePred = PHI->getIncomingBlock(*VDUse.U); + if (EdgePred != getBranchBlock(Stack.back().PInfo)) + return false; + } + + return (VDUse.DFSIn >= Stack.back().DFSIn && + VDUse.DFSOut <= Stack.back().DFSOut); } -void PredicateInfo::popStackUntilDFSScope(ValueDFSStack &Stack, int DFSIn, - int DFSOut) { - while (!Stack.empty() && !stackIsInScope(Stack, DFSIn, DFSOut)) +void PredicateInfo::popStackUntilDFSScope(ValueDFSStack &Stack, + const ValueDFS &VD) { + while (!Stack.empty() && !stackIsInScope(Stack, VD)) Stack.pop_back(); } @@ -271,20 +357,11 @@ SmallVector CmpOperands; BasicBlock *FirstBB = BI->getSuccessor(0); BasicBlock *SecondBB = BI->getSuccessor(1); - bool FirstSinglePred = FirstBB->getSinglePredecessor(); - bool SecondSinglePred = SecondBB->getSinglePredecessor(); SmallVector SuccsToProcess; bool isAnd = false; bool isOr = false; - // First make sure we have single preds for these successors, as we can't - // usefully propagate true/false info to them if there are multiple paths to - // them. - if (FirstSinglePred) - SuccsToProcess.push_back(FirstBB); - if (SecondSinglePred) - SuccsToProcess.push_back(SecondBB); - if (SuccsToProcess.empty()) - return; + SuccsToProcess.push_back(FirstBB); + SuccsToProcess.push_back(SecondBB); // Second, see if we have a comparison we support SmallVector ComparisonsToProcess; CmpInst::Predicate Pred; @@ -321,12 +398,44 @@ new PredicateBranch(Op, BranchBB, Succ, Cmp, TakenEdge); AllInfos.push_back(PB); OperandInfo.Infos.push_back(PB); + if (!Succ->getSinglePredecessor()) + PhiUsesOnly.insert({BranchBB, Succ}); } } CmpOperands.clear(); } } } +// Process a block terminating switch, and place relevant operations to be +// renamed into OpsToRename. +void PredicateInfo::processSwitch(SwitchInst *SI, BasicBlock *BranchBB, + SmallPtrSetImpl &OpsToRename) { + Value *Op = SI->getCondition(); + if ((!isa(Op) && !isa(Op)) || Op->hasOneUse()) + return; + + // Remember how many outgoing edges there are to every successor. + SmallDenseMap SwitchEdges; + for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) { + BasicBlock *TargetBlock = SI->getSuccessor(i); + ++SwitchEdges[TargetBlock]; + } + + // Now propagate info for each case value + for (auto i = SI->case_begin(), e = SI->case_end(); i != e; ++i) { + BasicBlock *TargetBlock = i.getCaseSuccessor(); + if (SwitchEdges.lookup(TargetBlock) == 1) { + OpsToRename.insert(Op); + auto &OperandInfo = getOrCreateValueInfo(Op); + PredicateSwitch *PS = new PredicateSwitch( + Op, SI->getParent(), TargetBlock, i.getCaseValue(), SI); + AllInfos.push_back(PS); + OperandInfo.Infos.push_back(PS); + if (!TargetBlock->getSinglePredecessor()) + PhiUsesOnly.insert({BranchBB, TargetBlock}); + } + } +} // Build predicate info for our function void PredicateInfo::buildPredicateInfo() { @@ -340,6 +449,8 @@ if (!BI->isConditional()) continue; processBranch(BI, BranchBB, OpsToRename); + } else if (auto *SI = dyn_cast(BranchBB->getTerminator())) { + processSwitch(SI, BranchBB, OpsToRename); } } for (auto &Assume : AC.assumptions()) { @@ -349,6 +460,9 @@ // Now rename all our operations. renameUses(OpsToRename); } + +// Given the renaming stack, make all the operands currently on the stack real +// by inserting them into the IR. Return the last operation's value. Value *PredicateInfo::materializeStack(unsigned int &Counter, ValueDFSStack &RenameStack, Value *OrigOp) { @@ -368,29 +482,13 @@ RenameIter == RenameStack.begin() ? OrigOp : (RenameIter - 1)->Def; ValueDFS &Result = *RenameIter; auto *ValInfo = Result.PInfo; - // For branches, we can just place the operand in the split block. For - // assume, we have to place it right before the assume to ensure we dominate - // all of our uses. - if (isa(ValInfo)) { - auto *PBranch = cast(ValInfo); - // It's possible we are trying to insert multiple predicateinfos in the - // same block at the beginning of the block. When we do this, we need to - // insert them one after the other, not one before the other. To see if we - // have already inserted predicateinfo into this block, we see if Op != - // OrigOp && Op->getParent() == PBranch->SplitBB. Op must be an - // instruction we inserted if it's not the original op. - BasicBlock::iterator InsertPt; - if (Op == OrigOp || - cast(Op)->getParent() != PBranch->SplitBB) { - InsertPt = PBranch->SplitBB->begin(); - // Insert after last phi node. - while (isa(InsertPt)) - ++InsertPt; - } else { - // Insert after op. - InsertPt = ++(cast(Op)->getIterator()); - } - IRBuilder<> B(PBranch->SplitBB, InsertPt); + // For branches, we can just place the operand in the branch block before + // the terminator. For assume, we have to place it right before the assume + // to ensure we dominate all of our uses. Always insert right before the + // relevant instruction (terminator, assume), so that we insert in proper + // order in the case of multiple predicateinfo in the same block. + if (isa(ValInfo) || isa(ValInfo)) { + IRBuilder<> B(getBranchTerminator(ValInfo)); Function *IF = Intrinsic::getDeclaration( F.getParent(), Intrinsic::ssa_copy, Op->getType()); Value *PIC = B.CreateCall(IF, Op, Op->getName() + "." + Twine(Counter++)); @@ -400,12 +498,7 @@ auto *PAssume = dyn_cast(ValInfo); assert(PAssume && "Should not have gotten here without it being an assume"); - // Unlike above, this should already insert in the right order when we - // insert multiple predicateinfos in the same block. Because we are - // always inserting right before the assume (instead of the beginning of a - // block), newer insertions will end up after older ones. - IRBuilder<> B(PAssume->AssumeInst->getParent(), - PAssume->AssumeInst->getIterator()); + IRBuilder<> B(PAssume->AssumeInst); Function *IF = Intrinsic::getDeclaration( F.getParent(), Intrinsic::ssa_copy, Op->getType()); Value *PIC = B.CreateCall(IF, Op); @@ -447,28 +540,50 @@ // created otherwise. for (auto &PossibleCopy : ValueInfo.Infos) { ValueDFS VD; - BasicBlock *CopyBB = nullptr; // Determine where we are going to place the copy by the copy type. // The predicate info for branches always come first, they will get // materialized in the split block at the top of the block. // The predicate info for assumes will be somewhere in the middle, // it will get materialized in front of the assume. - if (const auto *PBranch = dyn_cast(PossibleCopy)) { - CopyBB = PBranch->SplitBB; - VD.LocalNum = LN_First; - } else if (const auto *PAssume = - dyn_cast(PossibleCopy)) { - CopyBB = PAssume->AssumeInst->getParent(); + if (const auto *PAssume = dyn_cast(PossibleCopy)) { VD.LocalNum = LN_Middle; - } else - llvm_unreachable("Unhandled predicate info type"); - DomTreeNode *DomNode = DT.getNode(CopyBB); - if (!DomNode) - continue; - VD.DFSIn = DomNode->getDFSNumIn(); - VD.DFSOut = DomNode->getDFSNumOut(); - VD.PInfo = PossibleCopy; - OrderedUses.push_back(VD); + DomTreeNode *DomNode = DT.getNode(PAssume->AssumeInst->getParent()); + if (!DomNode) + continue; + VD.DFSIn = DomNode->getDFSNumIn(); + VD.DFSOut = DomNode->getDFSNumOut(); + VD.PInfo = PossibleCopy; + OrderedUses.push_back(VD); + } else if (isa(PossibleCopy) || + isa(PossibleCopy)) { + // If we can only do phi uses, we treat it like it's in the branch + // block, and handle it specially. We know that it goes last, and only + // dominate phi uses. + auto BlockEdge = getBlockEdge(PossibleCopy); + if (PhiUsesOnly.count(BlockEdge)) { + VD.LocalNum = LN_Last; + auto *DomNode = DT.getNode(BlockEdge.first); + if (DomNode) { + VD.DFSIn = DomNode->getDFSNumIn(); + VD.DFSOut = DomNode->getDFSNumOut(); + VD.PInfo = PossibleCopy; + VD.PhiOnly = true; + OrderedUses.push_back(VD); + } + } else { + // Otherwise, we are in the split block (even though we perform + // insertion in the branch block). + // Insert a possible copy at the split block and before the branch. + VD.LocalNum = LN_First; + auto *DomNode = DT.getNode(BlockEdge.second); + if (DomNode) { + VD.DFSIn = DomNode->getDFSNumIn(); + VD.DFSOut = DomNode->getDFSNumOut(); + VD.PInfo = PossibleCopy; + OrderedUses.push_back(VD); + } + } + } } convertUsesToDFSOrdered(Op, OrderedUses); @@ -492,10 +607,10 @@ << VD.DFSOut << ")\n"); bool ShouldPush = (VD.Def || PossibleCopy); - bool OutOfScope = !stackIsInScope(RenameStack, VD.DFSIn, VD.DFSOut); + bool OutOfScope = !stackIsInScope(RenameStack, VD); if (OutOfScope || ShouldPush) { // Sync to our current scope. - popStackUntilDFSScope(RenameStack, VD.DFSIn, VD.DFSOut); + popStackUntilDFSScope(RenameStack, VD); ShouldPush |= (VD.Def || PossibleCopy); if (ShouldPush) { RenameStack.push_back(VD); Index: test/Transforms/Util/PredicateInfo/condprop.ll =================================================================== --- test/Transforms/Util/PredicateInfo/condprop.ll +++ test/Transforms/Util/PredicateInfo/condprop.ll @@ -98,12 +98,12 @@ ; CHECK-NEXT: [[XZ:%.*]] = icmp eq i32 [[X:%.*]], 0 ; CHECK-NEXT: [[YZ:%.*]] = icmp eq i32 [[Y:%.*]], 0 ; CHECK-NEXT: [[Z:%.*]] = and i1 [[XZ]], [[YZ]] +; CHECK: [[XZ_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[XZ]]) +; CHECK: [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]]) +; CHECK: [[YZ_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[YZ]]) +; CHECK: [[Y_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[Y]]) ; CHECK-NEXT: br i1 [[Z]], label [[BOTH_ZERO:%.*]], label [[NOPE:%.*]] ; CHECK: both_zero: -; CHECK: [[Y_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[Y]]) -; CHECK: [[YZ_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[YZ]]) -; CHECK: [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]]) -; CHECK: [[XZ_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[XZ]]) ; CHECK-NEXT: call void @foo(i1 [[XZ_0]]) ; CHECK-NEXT: call void @foo(i1 [[YZ_0]]) ; CHECK-NEXT: call void @bar(i32 [[X_0]]) @@ -178,15 +178,15 @@ define i1 @test5(i32 %x, i32 %y) { ; CHECK-LABEL: @test5( ; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[X:%.*]], [[Y:%.*]] +; CHECK: [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]]) +; CHECK: [[X_1:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]]) +; CHECK: [[Y_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[Y]]) +; CHECK: [[Y_1:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[Y]]) ; CHECK-NEXT: br i1 [[CMP]], label [[SAME:%.*]], label [[DIFFERENT:%.*]] ; CHECK: same: -; CHECK: [[Y_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[Y]]) -; CHECK: [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]]) ; CHECK-NEXT: [[CMP2:%.*]] = icmp ne i32 [[X_0]], [[Y_0]] ; CHECK-NEXT: ret i1 [[CMP2]] ; CHECK: different: -; CHECK: [[Y_1:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[Y]]) -; CHECK: [[X_1:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]]) ; CHECK-NEXT: [[CMP3:%.*]] = icmp eq i32 [[X_1]], [[Y_1]] ; CHECK-NEXT: ret i1 [[CMP3]] ; @@ -251,15 +251,15 @@ define i1 @test7(i32 %x, i32 %y) { ; CHECK-LABEL: @test7( ; CHECK-NEXT: [[CMP:%.*]] = icmp sgt i32 [[X:%.*]], [[Y:%.*]] +; CHECK: [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]]) +; CHECK: [[X_1:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]]) +; CHECK: [[Y_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[Y]]) +; CHECK: [[Y_1:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[Y]]) ; CHECK-NEXT: br i1 [[CMP]], label [[SAME:%.*]], label [[DIFFERENT:%.*]] ; CHECK: same: -; CHECK: [[Y_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[Y]]) -; CHECK: [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]]) ; CHECK-NEXT: [[CMP2:%.*]] = icmp sle i32 [[X_0]], [[Y_0]] ; CHECK-NEXT: ret i1 [[CMP2]] ; CHECK: different: -; CHECK: [[Y_1:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[Y]]) -; CHECK: [[X_1:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]]) ; CHECK-NEXT: [[CMP3:%.*]] = icmp sgt i32 [[X_1]], [[Y_1]] ; CHECK-NEXT: ret i1 [[CMP3]] ; @@ -278,15 +278,15 @@ define i1 @test7_fp(float %x, float %y) { ; CHECK-LABEL: @test7_fp( ; CHECK-NEXT: [[CMP:%.*]] = fcmp ogt float [[X:%.*]], [[Y:%.*]] +; CHECK: [[X_0:%.*]] = call float @llvm.ssa.copy.f32(float [[X]]) +; CHECK: [[X_1:%.*]] = call float @llvm.ssa.copy.f32(float [[X]]) +; CHECK: [[Y_0:%.*]] = call float @llvm.ssa.copy.f32(float [[Y]]) +; CHECK: [[Y_1:%.*]] = call float @llvm.ssa.copy.f32(float [[Y]]) ; CHECK-NEXT: br i1 [[CMP]], label [[SAME:%.*]], label [[DIFFERENT:%.*]] ; CHECK: same: -; CHECK: [[Y_0:%.*]] = call float @llvm.ssa.copy.f32(float [[Y]]) -; CHECK: [[X_0:%.*]] = call float @llvm.ssa.copy.f32(float [[X]]) ; CHECK-NEXT: [[CMP2:%.*]] = fcmp ule float [[X_0]], [[Y_0]] ; CHECK-NEXT: ret i1 [[CMP2]] ; CHECK: different: -; CHECK: [[Y_1:%.*]] = call float @llvm.ssa.copy.f32(float [[Y]]) -; CHECK: [[X_1:%.*]] = call float @llvm.ssa.copy.f32(float [[X]]) ; CHECK-NEXT: [[CMP3:%.*]] = fcmp ogt float [[X_1]], [[Y_1]] ; CHECK-NEXT: ret i1 [[CMP3]] ; @@ -351,10 +351,10 @@ define i32 @test9(i32 %i, i32 %j) { ; CHECK-LABEL: @test9( ; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[I:%.*]], [[J:%.*]] +; CHECK: [[I_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[I]]) +; CHECK: [[J_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[J]]) ; CHECK-NEXT: br i1 [[CMP]], label [[COND_TRUE:%.*]], label [[RET:%.*]] ; CHECK: cond_true: -; CHECK: [[J_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[J]]) -; CHECK: [[I_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[I]]) ; CHECK-NEXT: [[DIFF:%.*]] = sub i32 [[I_0]], [[J_0]] ; CHECK-NEXT: ret i32 [[DIFF]] ; CHECK: ret: @@ -374,10 +374,10 @@ define i32 @test10(i32 %j, i32 %i) { ; CHECK-LABEL: @test10( ; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[I:%.*]], [[J:%.*]] +; CHECK: [[I_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[I]]) +; CHECK: [[J_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[J]]) ; CHECK-NEXT: br i1 [[CMP]], label [[COND_TRUE:%.*]], label [[RET:%.*]] ; CHECK: cond_true: -; CHECK: [[J_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[J]]) -; CHECK: [[I_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[I]]) ; CHECK-NEXT: [[DIFF:%.*]] = sub i32 [[I_0]], [[J_0]] ; CHECK-NEXT: ret i32 [[DIFF]] ; CHECK: ret: @@ -401,16 +401,16 @@ ; CHECK-NEXT: [[V0:%.*]] = call i32 @yogibar() ; CHECK-NEXT: [[V1:%.*]] = call i32 @yogibar() ; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[V0]], [[V1]] +; CHECK: [[V0_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[V0]]) +; CHECK: [[V1_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[V1]]) ; CHECK-NEXT: br i1 [[CMP]], label [[COND_TRUE:%.*]], label [[NEXT:%.*]] ; CHECK: cond_true: -; CHECK: [[V1_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[V1]]) ; CHECK-NEXT: ret i32 [[V1_0]] ; CHECK: next: -; CHECK: [[V0_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[V0]]) ; CHECK-NEXT: [[CMP2:%.*]] = icmp eq i32 [[X:%.*]], [[V0_0]] +; CHECK: [[V0_0_1:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[V0_0]]) ; CHECK-NEXT: br i1 [[CMP2]], label [[COND_TRUE2:%.*]], label [[NEXT2:%.*]] ; CHECK: cond_true2: -; CHECK: [[V0_0_1:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[V0_0]]) ; CHECK-NEXT: ret i32 [[V0_0_1]] ; CHECK: next2: ; CHECK-NEXT: ret i32 0 @@ -437,12 +437,12 @@ define i32 @test12(i32 %x) { ; CHECK-LABEL: @test12( ; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[X:%.*]], 0 +; CHECK: [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]]) +; CHECK: [[X_1:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]]) ; CHECK-NEXT: br i1 [[CMP]], label [[COND_TRUE:%.*]], label [[COND_FALSE:%.*]] ; CHECK: cond_true: -; CHECK: [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]]) ; CHECK-NEXT: br label [[RET:%.*]] ; CHECK: cond_false: -; CHECK: [[X_1:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]]) ; CHECK-NEXT: br label [[RET]] ; CHECK: ret: ; CHECK-NEXT: [[RES:%.*]] = phi i32 [ [[X_0]], [[COND_TRUE]] ], [ [[X_1]], [[COND_FALSE]] ] Index: test/Transforms/Util/PredicateInfo/diamond.ll =================================================================== --- /dev/null +++ test/Transforms/Util/PredicateInfo/diamond.ll @@ -0,0 +1,68 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -print-predicateinfo < %s 2>&1 | FileCheck %s +define i1 @f(i32 %x, i1 %y) { +; CHECK-LABEL: @f( +; CHECK-NEXT: br i1 [[Y:%.*]], label [[BB0:%.*]], label [[BB1:%.*]] +; CHECK: bb0: +; CHECK-NEXT: [[CMP:%.*]] = icmp sge i32 [[X:%.*]], 0 +; CHECK: [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]]) +; CHECK-NEXT: br i1 [[CMP]], label [[BB2:%.*]], label [[BB3:%.*]] +; CHECK: bb1: +; CHECK-NEXT: [[X2:%.*]] = add nuw nsw i32 [[X]], 1 +; CHECK-NEXT: [[CMP2:%.*]] = icmp sge i32 [[X2]], 2 +; CHECK: [[X2_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X2]]) +; CHECK-NEXT: br i1 [[CMP2]], label [[BB2]], label [[BB3]] +; CHECK: bb2: +; CHECK-NEXT: [[X3:%.*]] = phi i32 [ [[X_0]], [[BB0]] ], [ [[X2_0]], [[BB1]] ] +; CHECK-NEXT: br label [[BB3]] +; CHECK: bb3: +; CHECK-NEXT: ret i1 false +; + br i1 %y, label %bb0, label %bb1 + bb0: + %cmp = icmp sge i32 %x, 0 ; x > 0 + br i1 %cmp, label %bb2, label %bb3 + bb1: + %x2 = add nsw nuw i32 %x, 1 + %cmp2 = icmp sge i32 %x2, 2 ; x+1 > 2 / x > 1 + br i1 %cmp2, label %bb2, label %bb3 + bb2: + %x3 = phi i32 [ %x, %bb0 ], [ %x2, %bb1 ] + br label %bb3 + bb3: + ret i1 0 +} + +define i1 @g(i32 %x, i1 %y) { +; CHECK-LABEL: @g( +; CHECK-NEXT: br i1 [[Y:%.*]], label [[BB0:%.*]], label [[BB1:%.*]] +; CHECK: bb0: +; CHECK-NEXT: [[CMP:%.*]] = icmp sge i32 [[X:%.*]], 0 +; CHECK: [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]]) +; CHECK-NEXT: br i1 [[CMP]], label [[BB3:%.*]], label [[BB2:%.*]] +; CHECK: bb1: +; CHECK-NEXT: [[X2:%.*]] = add nuw nsw i32 [[X]], 1 +; CHECK-NEXT: [[CMP2:%.*]] = icmp sge i32 [[X2]], 2 +; CHECK: [[X2_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X2]]) +; CHECK-NEXT: br i1 [[CMP2]], label [[BB3]], label [[BB2]] +; CHECK: bb2: +; CHECK-NEXT: [[X3:%.*]] = phi i32 [ [[X_0]], [[BB0]] ], [ [[X2_0]], [[BB1]] ] +; CHECK-NEXT: br label [[BB3]] +; CHECK: bb3: +; CHECK-NEXT: ret i1 false +; + br i1 %y, label %bb0, label %bb1 + bb0: + %cmp = icmp sge i32 %x, 0 ; x > 0 + br i1 %cmp, label %bb3, label %bb2 + bb1: + %x2 = add nsw nuw i32 %x, 1 + %cmp2 = icmp sge i32 %x2, 2 ; x+1 > 2 / x > 1 + br i1 %cmp2, label %bb3, label %bb2 + bb2: + %x3 = phi i32 [ %x, %bb0 ], [ %x2, %bb1 ] + br label %bb3 + bb3: + ret i1 0 +} + Index: test/Transforms/Util/PredicateInfo/edge.ll =================================================================== --- /dev/null +++ test/Transforms/Util/PredicateInfo/edge.ll @@ -0,0 +1,242 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -print-predicateinfo -analyze < %s 2>&1 | FileCheck %s + +define i32 @f1(i32 %x) { +; CHECK-LABEL: @f1( +; CHECK-NEXT: bb0: +; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[X:%.*]], 0 +; CHECK: [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]]) +; CHECK-NEXT: br i1 [[CMP]], label [[BB2:%.*]], label [[BB1:%.*]] +; CHECK: bb1: +; CHECK-NEXT: br label [[BB2]] +; CHECK: bb2: +; CHECK-NEXT: [[COND:%.*]] = phi i32 [ [[X_0]], [[BB0:%.*]] ], [ 0, [[BB1]] ] +; CHECK-NEXT: [[FOO:%.*]] = add i32 [[COND]], [[X]] +; CHECK-NEXT: ret i32 [[FOO]] +; +bb0: + %cmp = icmp eq i32 %x, 0 + br i1 %cmp, label %bb2, label %bb1 +bb1: + br label %bb2 +bb2: + %cond = phi i32 [ %x, %bb0 ], [ 0, %bb1 ] + %foo = add i32 %cond, %x + ret i32 %foo +} + +define i32 @f2(i32 %x) { +; CHECK-LABEL: @f2( +; CHECK-NEXT: bb0: +; CHECK-NEXT: [[CMP:%.*]] = icmp ne i32 [[X:%.*]], 0 +; CHECK: [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]]) +; CHECK-NEXT: br i1 [[CMP]], label [[BB1:%.*]], label [[BB2:%.*]] +; CHECK: bb1: +; CHECK-NEXT: br label [[BB2]] +; CHECK: bb2: +; CHECK-NEXT: [[COND:%.*]] = phi i32 [ [[X_0]], [[BB0:%.*]] ], [ 0, [[BB1]] ] +; CHECK-NEXT: [[FOO:%.*]] = add i32 [[COND]], [[X]] +; CHECK-NEXT: ret i32 [[FOO]] +; +bb0: + %cmp = icmp ne i32 %x, 0 + br i1 %cmp, label %bb1, label %bb2 +bb1: + br label %bb2 +bb2: + %cond = phi i32 [ %x, %bb0 ], [ 0, %bb1 ] + %foo = add i32 %cond, %x + ret i32 %foo +} + +define i32 @f3(i32 %x) { +; CHECK-LABEL: @f3( +; CHECK-NEXT: bb0: +; CHECK: [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X:%.*]]) +; CHECK-NEXT: switch i32 [[X]], label [[BB1:%.*]] [ +; CHECK-NEXT: i32 0, label [[BB2:%.*]] +; CHECK-NEXT: ] +; CHECK: bb1: +; CHECK-NEXT: br label [[BB2]] +; CHECK: bb2: +; CHECK-NEXT: [[COND:%.*]] = phi i32 [ [[X_0]], [[BB0:%.*]] ], [ 0, [[BB1]] ] +; CHECK-NEXT: [[FOO:%.*]] = add i32 [[COND]], [[X]] +; CHECK-NEXT: ret i32 [[FOO]] +; +bb0: + switch i32 %x, label %bb1 [ i32 0, label %bb2] +bb1: + br label %bb2 +bb2: + %cond = phi i32 [ %x, %bb0 ], [ 0, %bb1 ] + %foo = add i32 %cond, %x + ret i32 %foo +} + + +define double @fcmp_oeq_not_zero(double %x, double %y) { +; CHECK-LABEL: @fcmp_oeq_not_zero( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[CMP:%.*]] = fcmp oeq double [[Y:%.*]], 2.000000e+00 +; CHECK: [[Y_0:%.*]] = call double @llvm.ssa.copy.f64(double [[Y]]) +; CHECK-NEXT: br i1 [[CMP]], label [[IF:%.*]], label [[RETURN:%.*]] +; CHECK: if: +; CHECK-NEXT: [[DIV:%.*]] = fdiv double [[X:%.*]], [[Y_0]] +; CHECK-NEXT: br label [[RETURN]] +; CHECK: return: +; CHECK-NEXT: [[RETVAL:%.*]] = phi double [ [[DIV]], [[IF]] ], [ [[X]], [[ENTRY:%.*]] ] +; CHECK-NEXT: ret double [[RETVAL]] +; +entry: + %cmp = fcmp oeq double %y, 2.0 + br i1 %cmp, label %if, label %return + +if: + %div = fdiv double %x, %y + br label %return + +return: + %retval = phi double [ %div, %if ], [ %x, %entry ] + ret double %retval + +} + +define double @fcmp_une_not_zero(double %x, double %y) { +; CHECK-LABEL: @fcmp_une_not_zero( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[CMP:%.*]] = fcmp une double [[Y:%.*]], 2.000000e+00 +; CHECK: [[Y_0:%.*]] = call double @llvm.ssa.copy.f64(double [[Y]]) +; CHECK-NEXT: br i1 [[CMP]], label [[RETURN:%.*]], label [[ELSE:%.*]] +; CHECK: else: +; CHECK-NEXT: [[DIV:%.*]] = fdiv double [[X:%.*]], [[Y_0]] +; CHECK-NEXT: br label [[RETURN]] +; CHECK: return: +; CHECK-NEXT: [[RETVAL:%.*]] = phi double [ [[DIV]], [[ELSE]] ], [ [[X]], [[ENTRY:%.*]] ] +; CHECK-NEXT: ret double [[RETVAL]] +; +entry: + %cmp = fcmp une double %y, 2.0 + br i1 %cmp, label %return, label %else + +else: + %div = fdiv double %x, %y + br label %return + +return: + %retval = phi double [ %div, %else ], [ %x, %entry ] + ret double %retval + +} + +define double @fcmp_oeq_zero(double %x, double %y) { +; CHECK-LABEL: @fcmp_oeq_zero( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[CMP:%.*]] = fcmp oeq double [[Y:%.*]], 0.000000e+00 +; CHECK: [[Y_0:%.*]] = call double @llvm.ssa.copy.f64(double [[Y]]) +; CHECK-NEXT: br i1 [[CMP]], label [[IF:%.*]], label [[RETURN:%.*]] +; CHECK: if: +; CHECK-NEXT: [[DIV:%.*]] = fdiv double [[X:%.*]], [[Y_0]] +; CHECK-NEXT: br label [[RETURN]] +; CHECK: return: +; CHECK-NEXT: [[RETVAL:%.*]] = phi double [ [[DIV]], [[IF]] ], [ [[X]], [[ENTRY:%.*]] ] +; CHECK-NEXT: ret double [[RETVAL]] +; +entry: + %cmp = fcmp oeq double %y, 0.0 + br i1 %cmp, label %if, label %return + +if: + %div = fdiv double %x, %y + br label %return + +return: + %retval = phi double [ %div, %if ], [ %x, %entry ] + ret double %retval + +} + +define double @fcmp_une_zero(double %x, double %y) { +; CHECK-LABEL: @fcmp_une_zero( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[CMP:%.*]] = fcmp une double [[Y:%.*]], -0.000000e+00 +; CHECK: [[Y_0:%.*]] = call double @llvm.ssa.copy.f64(double [[Y]]) +; CHECK-NEXT: br i1 [[CMP]], label [[RETURN:%.*]], label [[ELSE:%.*]] +; CHECK: else: +; CHECK-NEXT: [[DIV:%.*]] = fdiv double [[X:%.*]], [[Y_0]] +; CHECK-NEXT: br label [[RETURN]] +; CHECK: return: +; CHECK-NEXT: [[RETVAL:%.*]] = phi double [ [[DIV]], [[ELSE]] ], [ [[X]], [[ENTRY:%.*]] ] +; CHECK-NEXT: ret double [[RETVAL]] +; +entry: + %cmp = fcmp une double %y, -0.0 + br i1 %cmp, label %return, label %else + +else: + %div = fdiv double %x, %y + br label %return + +return: + %retval = phi double [ %div, %else ], [ %x, %entry ] + ret double %retval + +} + + +define double @fcmp_oeq_maybe_zero(double %x, double %y, double %z1, double %z2) { +; CHECK-LABEL: @fcmp_oeq_maybe_zero( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[Z:%.*]] = fadd double [[Z1:%.*]], [[Z2:%.*]] +; CHECK-NEXT: [[CMP:%.*]] = fcmp oeq double [[Y:%.*]], [[Z]] +; CHECK: [[Z_0:%.*]] = call double @llvm.ssa.copy.f64(double [[Z]]) +; CHECK-NEXT: br i1 [[CMP]], label [[IF:%.*]], label [[RETURN:%.*]] +; CHECK: if: +; CHECK-NEXT: [[DIV:%.*]] = fdiv double [[X:%.*]], [[Z_0]] +; CHECK-NEXT: br label [[RETURN]] +; CHECK: return: +; CHECK-NEXT: [[RETVAL:%.*]] = phi double [ [[DIV]], [[IF]] ], [ [[X]], [[ENTRY:%.*]] ] +; CHECK-NEXT: ret double [[RETVAL]] +; +entry: + %z = fadd double %z1, %z2 + %cmp = fcmp oeq double %y, %z + br i1 %cmp, label %if, label %return + +if: + %div = fdiv double %x, %z + br label %return + +return: + %retval = phi double [ %div, %if ], [ %x, %entry ] + ret double %retval + +} + +define double @fcmp_une_maybe_zero(double %x, double %y, double %z1, double %z2) { +; CHECK-LABEL: @fcmp_une_maybe_zero( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[Z:%.*]] = fadd double [[Z1:%.*]], [[Z2:%.*]] +; CHECK-NEXT: [[CMP:%.*]] = fcmp une double [[Y:%.*]], [[Z]] +; CHECK: [[Z_0:%.*]] = call double @llvm.ssa.copy.f64(double [[Z]]) +; CHECK-NEXT: br i1 [[CMP]], label [[RETURN:%.*]], label [[ELSE:%.*]] +; CHECK: else: +; CHECK-NEXT: [[DIV:%.*]] = fdiv double [[X:%.*]], [[Z_0]] +; CHECK-NEXT: br label [[RETURN]] +; CHECK: return: +; CHECK-NEXT: [[RETVAL:%.*]] = phi double [ [[DIV]], [[ELSE]] ], [ [[X]], [[ENTRY:%.*]] ] +; CHECK-NEXT: ret double [[RETVAL]] +; +entry: + %z = fadd double %z1, %z2 + %cmp = fcmp une double %y, %z + br i1 %cmp, label %return, label %else + +else: + %div = fdiv double %x, %z + br label %return + +return: + %retval = phi double [ %div, %else ], [ %x, %entry ] + ret double %retval + +} Index: test/Transforms/Util/PredicateInfo/testandor.ll =================================================================== --- test/Transforms/Util/PredicateInfo/testandor.ll +++ test/Transforms/Util/PredicateInfo/testandor.ll @@ -1,5 +1,5 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py -; RUN: opt -print-predicateinfo -analyze < %s 2>&1 | FileCheck %s +; RUN: opt -print-predicateinfo < %s 2>&1 | FileCheck %s declare void @foo(i1) declare void @bar(i32) @@ -10,6 +10,10 @@ ; CHECK-NEXT: [[XZ:%.*]] = icmp eq i32 [[X:%.*]], 0 ; CHECK-NEXT: [[YZ:%.*]] = icmp eq i32 [[Y:%.*]], 0 ; CHECK-NEXT: [[Z:%.*]] = or i1 [[XZ]], [[YZ]] +; CHECK: [[XZ_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[XZ]]) +; CHECK: [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]]) +; CHECK: [[YZ_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[YZ]]) +; CHECK: [[Y_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[Y]]) ; CHECK-NEXT: br i1 [[Z]], label [[ONEOF:%.*]], label [[NEITHER:%.*]] ; CHECK: oneof: ; CHECK-NEXT: call void @foo(i1 [[XZ]]) @@ -18,10 +22,6 @@ ; CHECK-NEXT: call void @bar(i32 [[Y]]) ; CHECK-NEXT: ret void ; CHECK: neither: -; CHECK: [[Y_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[Y]]) -; CHECK: [[YZ_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[YZ]]) -; CHECK: [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]]) -; CHECK: [[XZ_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[XZ]]) ; CHECK-NEXT: call void @foo(i1 [[XZ_0]]) ; CHECK-NEXT: call void @foo(i1 [[YZ_0]]) ; CHECK-NEXT: call void @bar(i32 [[X_0]]) @@ -53,12 +53,12 @@ ; CHECK-NEXT: [[XZ:%.*]] = icmp eq i32 [[X:%.*]], 0 ; CHECK-NEXT: [[YZ:%.*]] = icmp eq i32 [[Y:%.*]], 0 ; CHECK-NEXT: [[Z:%.*]] = and i1 [[XZ]], [[YZ]] +; CHECK: [[XZ_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[XZ]]) +; CHECK: [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]]) +; CHECK: [[YZ_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[YZ]]) +; CHECK: [[Y_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[Y]]) ; CHECK-NEXT: br i1 [[Z]], label [[BOTH:%.*]], label [[NOPE:%.*]] ; CHECK: both: -; CHECK: [[Y_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[Y]]) -; CHECK: [[YZ_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[YZ]]) -; CHECK: [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]]) -; CHECK: [[XZ_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[XZ]]) ; CHECK-NEXT: call void @foo(i1 [[XZ_0]]) ; CHECK-NEXT: call void @foo(i1 [[YZ_0]]) ; CHECK-NEXT: call void @bar(i32 [[X_0]]) @@ -96,12 +96,12 @@ ; CHECK-NEXT: [[XGT:%.*]] = icmp sgt i32 [[X:%.*]], 0 ; CHECK-NEXT: [[XLT:%.*]] = icmp slt i32 [[X]], 100 ; CHECK-NEXT: [[Z:%.*]] = and i1 [[XGT]], [[XLT]] -; CHECK-NEXT: br i1 [[Z]], label [[BOTH:%.*]], label [[NOPE:%.*]] -; CHECK: both: -; CHECK: [[XLT_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[XLT]]) +; CHECK: [[XGT_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[XGT]]) ; CHECK: [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]]) ; CHECK: [[X_0_1:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X_0]]) -; CHECK: [[XGT_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[XGT]]) +; CHECK: [[XLT_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[XLT]]) +; CHECK-NEXT: br i1 [[Z]], label [[BOTH:%.*]], label [[NOPE:%.*]] +; CHECK: both: ; CHECK-NEXT: call void @foo(i1 [[XGT_0]]) ; CHECK-NEXT: call void @foo(i1 [[XLT_0]]) ; CHECK-NEXT: call void @bar(i32 [[X_0_1]]) @@ -138,12 +138,12 @@ ; CHECK: [[TMP3:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[YZ]]) ; CHECK: [[TMP4:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[Y]]) ; CHECK-NEXT: call void @llvm.assume(i1 [[Z]]) +; CHECK: [[DOT0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[TMP1]]) +; CHECK: [[DOT01:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[TMP2]]) +; CHECK: [[DOT02:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[TMP3]]) +; CHECK: [[DOT03:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[TMP4]]) ; CHECK-NEXT: br i1 [[Z]], label [[BOTH:%.*]], label [[NOPE:%.*]] ; CHECK: both: -; CHECK: [[DOT03:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[TMP4]]) -; CHECK: [[DOT02:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[TMP3]]) -; CHECK: [[DOT01:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[TMP2]]) -; CHECK: [[DOT0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[TMP1]]) ; CHECK-NEXT: call void @foo(i1 [[DOT0]]) ; CHECK-NEXT: call void @foo(i1 [[DOT02]]) ; CHECK-NEXT: call void @bar(i32 [[DOT01]])