Index: llvm/trunk/lib/Transforms/Scalar/NewGVN.cpp =================================================================== --- llvm/trunk/lib/Transforms/Scalar/NewGVN.cpp +++ llvm/trunk/lib/Transforms/Scalar/NewGVN.cpp @@ -81,13 +81,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"); @@ -209,6 +209,7 @@ AliasAnalysis *AA; MemorySSA *MSSA; MemorySSAWalker *MSSAWalker; + std::unique_ptr PredInfo; BumpPtrAllocator ExpressionAllocator; ArrayRecycler ArgRecycler; @@ -229,6 +230,12 @@ DenseMap ValueToClass; DenseMap ValueToExpression; + // Mapping from predicate info we used to the instructions we used it with. + // In order to correctly ensure propagation, we must keep track of what + // comparisons we used, so that when the values of the comparisons change, we + // propagate the information to the places we used the comparison. + DenseMap> PredicateToUsers; + // A table storing which memorydefs/phis represent a memory state provably // equivalent to another memory state. // We could use the congruence class machinery, but the MemoryAccess's are @@ -297,7 +304,6 @@ AU.addRequired(); AU.addRequired(); AU.addRequired(); - AU.addPreserved(); AU.addPreserved(); } @@ -308,6 +314,7 @@ PHIExpression *createPHIExpression(Instruction *); const VariableExpression *createVariableExpression(Value *); const ConstantExpression *createConstantExpression(Constant *); + const Expression *createVariableOrConstant(Value *V); const UnknownExpression *createUnknownExpression(Instruction *); const StoreExpression *createStoreExpression(StoreInst *, MemoryAccess *); LoadExpression *createLoadExpression(Type *, Value *, LoadInst *, @@ -345,6 +352,7 @@ const Expression *performSymbolicPHIEvaluation(Instruction *); const Expression *performSymbolicAggrValueEvaluation(Instruction *); const Expression *performSymbolicCmpEvaluation(Instruction *); + const Expression *performSymbolicPredicateInfoEvaluation(Instruction *); // Congruence finding. Value *lookupOperandLeader(Value *) const; @@ -382,13 +390,16 @@ // Various instruction touch utilities void markUsersTouched(Value *); void markMemoryUsersTouched(MemoryAccess *); + void markPredicateUsersTouched(Instruction *); void markLeaderChangeTouched(CongruenceClass *CC); + void addPredicateUsers(const PredicateBase *, Instruction *); // Utilities. void cleanupTables(); std::pair assignDFSNumbers(BasicBlock *, unsigned); void updateProcessedCount(Value *V); void verifyMemoryCongruency() const; + void verifyComparisons(Function &F); bool singleReachablePHIPath(const MemoryAccess *, const MemoryAccess *) const; }; } // end anonymous namespace @@ -669,6 +680,12 @@ return E; } +const Expression *NewGVN::createVariableOrConstant(Value *V) { + if (auto *C = dyn_cast(V)) + return createConstantExpression(C); + return createVariableExpression(V); +} + const ConstantExpression *NewGVN::createConstantExpression(Constant *C) { auto *E = new (ExpressionAllocator) ConstantExpression(C); E->setOpcode(C->getValueID()); @@ -831,12 +848,103 @@ 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"); + auto *CopyOf = I->getOperand(0); + auto *Cond = dyn_cast(PI->Condition); + if (!Cond) + return nullptr; + + // If this a copy of the condition, it must be either true or false depending + // on the predicate info type and edge + if (CopyOf == Cond) { + addPredicateUsers(PI, I); + if (isa(PI)) + return createConstantExpression(ConstantInt::getTrue(Cond->getType())); + if (auto *PBranch = dyn_cast(PI)) { + if (PBranch->TrueEdge) + return createConstantExpression(ConstantInt::getTrue(Cond->getType())); + return createConstantExpression(ConstantInt::getFalse(Cond->getType())); + } + } + // Not a copy of the condition, so see what the predicates tell us about this + // value. + // Not a copy of the condition, so see what the predicates tell us about this + // value. First, though, we check to make sure the value is actually a copy + // of one of the condition operands. It's possible, in certain cases, for it + // to be a copy of a predicateinfo copy. In particular, if two branch + // operations use the same condition, and one branch dominates the other, we + // will end up with a copy of a copy. This is currently a small deficiency in + // predicateinfo. What will end up happening here is that we will value + // number both copies the same anyway. + if (CopyOf != Cond->getOperand(0) && CopyOf != Cond->getOperand(1)) { + DEBUG(dbgs() << "Copy is not of any condition operands!"); + return nullptr; + } + Value *FirstOp = lookupOperandLeader(Cond->getOperand(0)); + Value *SecondOp = lookupOperandLeader(Cond->getOperand(1)); + bool SwappedOps = false; + // Sort the ops + if (shouldSwapOperands(FirstOp, SecondOp)) { + std::swap(FirstOp, SecondOp); + SwappedOps = true; + } + + // Everything below relies on the condition being a comparison. + auto *Cmp = dyn_cast(Cond); + CmpInst::Predicate Predicate = + SwappedOps ? Cmp->getSwappedPredicate() : Cmp->getPredicate(); + + 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)) { + addPredicateUsers(PI, I); + return createVariableOrConstant(FirstOp); + } + } + if (const auto *PBranch = dyn_cast(PI)) { + // 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. In particular, if the comparison is true/false when the + // operands are equal, and we are on the right edge, we know this operation + // is equal to something. + if ((PBranch->TrueEdge && Predicate == CmpInst::ICMP_EQ) || + (!PBranch->TrueEdge && Predicate == CmpInst::ICMP_NE)) { + addPredicateUsers(PI, I); + return createVariableOrConstant(FirstOp); + } + // Handle the special case of floating point. + if (((PBranch->TrueEdge && Predicate == CmpInst::FCMP_OEQ) || + (!PBranch->TrueEdge && Predicate == CmpInst::FCMP_UNE)) && + isa(FirstOp) && !cast(FirstOp)->isZero()) { + addPredicateUsers(PI, I); + 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)) { + // Instrinsics with the returned attribute are copies of arguments. + if (auto *ReturnedValue = II->getReturnedArgOperand()) { + if (II->getIntrinsicID() == Intrinsic::ssa_copy) + if (const auto *Result = performSymbolicPredicateInfoEvaluation(I)) + return Result; + return createVariableOrConstant(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)); } @@ -930,9 +1038,7 @@ << "\n"); E->deallocateOperands(ArgRecycler); ExpressionAllocator.Deallocate(E); - if (auto *C = dyn_cast(AllSameValue)) - return createConstantExpression(C); - return createVariableExpression(AllSameValue); + return createVariableOrConstant(AllSameValue); } return E; } @@ -976,16 +1082,117 @@ 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 OurPredicate = CI->getPredicate(); + if (shouldSwapOperands(Op1, Op0)) { + std::swap(Op0, Op1); + OurPredicate = CI->getSwappedPredicate(); + } + + // 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())); + if (Op0 == Op1) { + // This condition does not depend on predicates, no need to add users if (CI->isTrueWhenEqual()) return createConstantExpression(ConstantInt::getTrue(CI->getType())); else if (CI->isFalseWhenEqual()) return createConstantExpression(ConstantInt::getFalse(CI->getType())); } + + // NOTE: Because we are comparing both operands here and below, and using + // previous comparisons, we rely on fact that predicateinfo knows to mark + // comparisons that use renamed operands as users of the earlier comparisons. + // It is *not* enough to just mark predicateinfo renamed operands as users of + // the earlier comparisons, because the *other* operand may have changed in a + // previous iteration. + // Example: + // icmp slt %a, %b + // %b.0 = ssa.copy(%b) + // false branch: + // icmp slt %c, %b.0 + + // %c and %a may start out equal, and thus, the code below will say the second + // %icmp is false. c may become equal to something else, and in that case the + // %second icmp *must* be reexamined, but would not if only the renamed + // %operands are considered users of the icmp. + + // *Currently* we only check one level of comparisons back, and only mark one + // level back as touched when changes appen . If you modify this code to look + // back farther through comparisons, you *must* mark the appropriate + // comparisons as users in PredicateInfo.cpp, or you will cause bugs. See if + // we know something just from the operands themselves + + // 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. + // TODO: We only handle actual comparison conditions below, not and/or. + auto *BranchCond = dyn_cast(PBranch->Condition); + if (!BranchCond) + continue; + auto *BranchOp0 = lookupOperandLeader(BranchCond->getOperand(0)); + auto *BranchOp1 = lookupOperandLeader(BranchCond->getOperand(1)); + auto BranchPredicate = BranchCond->getPredicate(); + if (shouldSwapOperands(BranchOp1, BranchOp0)) { + std::swap(BranchOp0, BranchOp1); + BranchPredicate = BranchCond->getSwappedPredicate(); + } + if (BranchOp0 == Op0 && BranchOp1 == 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 (CmpInst::isImpliedTrueByMatchingCmp(OurPredicate, + BranchPredicate)) { + addPredicateUsers(PI, I); + return createConstantExpression( + ConstantInt::getTrue(CI->getType())); + } + + if (CmpInst::isImpliedFalseByMatchingCmp(OurPredicate, + BranchPredicate)) { + addPredicateUsers(PI, I); + 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 (BranchPredicate == OurPredicate) { + addPredicateUsers(PI, I); + // Same predicate, same ops,we know it was false, so this is false. + return createConstantExpression( + ConstantInt::getFalse(CI->getType())); + } else if (BranchPredicate == + CmpInst::getInversePredicate(OurPredicate)) { + addPredicateUsers(PI, I); + // 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); } @@ -1085,6 +1292,22 @@ } } +// Add I to the set of users of a given predicate. +void NewGVN::addPredicateUsers(const PredicateBase *PB, Instruction *I) { + if (auto *PBranch = dyn_cast(PB)) + PredicateToUsers[PBranch->Condition].insert(I); + else if (auto *PAssume = dyn_cast(PB)) + PredicateToUsers[PAssume->Condition].insert(I); +} + +// Touch all the predicates that depend on this instruction. +void NewGVN::markPredicateUsersTouched(Instruction *I) { + const auto Result = PredicateToUsers.find(I); + if (Result != PredicateToUsers.end()) + for (auto *User : Result->second) + TouchedInstructions.set(InstrDFS.lookup(User)); +} + // Touch the instructions that need to be updated after a congruence class has a // leader change, and mark changed values. void NewGVN::markLeaderChangeTouched(CongruenceClass *CC) { @@ -1286,6 +1509,8 @@ markUsersTouched(I); if (MemoryAccess *MA = MSSA->getMemoryAccess(I)) markMemoryUsersTouched(MA); + if (auto *CI = dyn_cast(I)) + markPredicateUsersTouched(CI); } } @@ -1481,6 +1706,7 @@ TouchedInstructions.clear(); DominatedInstRange.clear(); MemoryAccessToClass.clear(); + PredicateToUsers.clear(); } std::pair NewGVN::assignDFSNumbers(BasicBlock *B, @@ -1681,6 +1907,27 @@ } } +// Re-evaluate all the comparisons after value numbering and ensure they don't +// change. If they changed, we didn't mark them touched properly. +void NewGVN::verifyComparisons(Function &F) { +#ifndef NDEBUG + for (auto &BB : F) { + if (!ReachableBlocks.count(&BB)) + continue; + for (auto &I : BB) { + if (InstructionsToErase.count(&I)) + continue; + if (isa(&I)) { + auto *CurrentVal = ValueToClass.lookup(&I); + valueNumberInstruction(&I); + assert(CurrentVal == ValueToClass.lookup(&I) && + "Re-evaluating comparison changed value"); + } + } + } +#endif +} + // This is the main transformation entry point. bool NewGVN::runGVN(Function &F, DominatorTree *_DT, AssumptionCache *_AC, TargetLibraryInfo *_TLI, AliasAnalysis *_AA, @@ -1692,6 +1939,7 @@ TLI = _TLI; AA = _AA; MSSA = _MSSA; + PredInfo = make_unique(F, *DT, *AC); DL = &F.getParent()->getDataLayout(); MSSAWalker = MSSA->getWalker(); @@ -1700,9 +1948,9 @@ unsigned ICount = 1; // Add an empty instruction to account for the fact that we start at 1 DFSToInstr.emplace_back(nullptr); - // Note: We want RPO traversal of the blocks, which is not quite the same as - // dominator tree order, particularly with regard whether backedges get - // visited first or second, given a block with multiple successors. + // Note: We want ideal RPO traversal of the blocks, which is not quite the + // same as dominator tree order, particularly with regard whether backedges + // get visited first or second, given a block with multiple successors. // If we visit in the wrong order, we will end up performing N times as many // iterations. // The dominator tree does guarantee that, for a given dom tree node, it's @@ -1766,6 +2014,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)) { @@ -1820,7 +2071,9 @@ NumGVNMaxIterations = std::max(NumGVNMaxIterations.getValue(), Iterations); #ifndef NDEBUG verifyMemoryCongruency(); + verifyComparisons(F); #endif + Changed |= eliminateInstructions(F); // Delete all instructions marked for deletion. @@ -2295,15 +2548,14 @@ // start using, we also push. // Otherwise, we walk along, processing members who are // dominated by this scope, and eliminate them. - bool ShouldPush = - Member && (EliminationStack.empty() || isa(Member)); + bool ShouldPush = Member && EliminationStack.empty(); bool OutOfScope = !EliminationStack.isInScope(MemberDFSIn, MemberDFSOut); if (OutOfScope || ShouldPush) { // Sync to our current scope. EliminationStack.popUntilDFSScope(MemberDFSIn, MemberDFSOut); - ShouldPush |= Member && EliminationStack.empty(); + bool ShouldPush = Member && EliminationStack.empty(); if (ShouldPush) { EliminationStack.push_back(Member, MemberDFSIn, MemberDFSOut); } @@ -2329,8 +2581,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 its 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); @@ -2425,5 +2682,5 @@ // Because we only care about a total ordering, and don't rewrite expressions // in this order, we order by rank, which will give a strict weak ordering to // everything but constants, and then we order by pointer address. - return std::make_pair(getRank(A), A) > std::make_pair(getRank(B), B); + return std::make_pair(getRank(A), A) > std::make_pair(getRank(B), B); } Index: llvm/trunk/test/Transforms/NewGVN/condprop.ll =================================================================== --- llvm/trunk/test/Transforms/NewGVN/condprop.ll +++ llvm/trunk/test/Transforms/NewGVN/condprop.ll @@ -1,59 +1,5 @@ -; XFAIL: * ; RUN: opt < %s -basicaa -newgvn -S | FileCheck %s -@a = external global i32 ; [#uses=7] - -; CHECK-LABEL: @test1( -define i32 @test1() nounwind { -entry: - %0 = load i32, i32* @a, align 4 - %1 = icmp eq i32 %0, 4 - br i1 %1, label %bb, label %bb1 - -bb: ; preds = %entry - br label %bb8 - -bb1: ; preds = %entry - %2 = load i32, i32* @a, align 4 - %3 = icmp eq i32 %2, 5 - br i1 %3, label %bb2, label %bb3 - -bb2: ; preds = %bb1 - br label %bb8 - -bb3: ; preds = %bb1 - %4 = load i32, i32* @a, align 4 - %5 = icmp eq i32 %4, 4 -; CHECK: br i1 false, label %bb4, label %bb5 - br i1 %5, label %bb4, label %bb5 - -bb4: ; preds = %bb3 - %6 = load i32, i32* @a, align 4 - %7 = add i32 %6, 5 - br label %bb8 - -bb5: ; preds = %bb3 - %8 = load i32, i32* @a, align 4 - %9 = icmp eq i32 %8, 5 -; CHECK: br i1 false, label %bb6, label %bb7 - br i1 %9, label %bb6, label %bb7 - -bb6: ; preds = %bb5 - %10 = load i32, i32* @a, align 4 - %11 = add i32 %10, 4 - br label %bb8 - -bb7: ; preds = %bb5 - %12 = load i32, i32* @a, align 4 - br label %bb8 - -bb8: ; preds = %bb7, %bb6, %bb4, %bb2, %bb - %.0 = phi i32 [ %12, %bb7 ], [ %11, %bb6 ], [ %7, %bb4 ], [ 4, %bb2 ], [ 5, %bb ] - br label %return - -return: ; preds = %bb8 - ret i32 %.0 -} declare void @foo(i1) declare void @bar(i32) @@ -80,39 +26,6 @@ ret void } -; CHECK-LABEL: @test4( -define void @test4(i1 %b, i32 %x) { - br i1 %b, label %sw, label %case3 -sw: - switch i32 %x, label %default [ - i32 0, label %case0 - i32 1, label %case1 - i32 2, label %case0 - i32 3, label %case3 - i32 4, label %default - ] -default: -; CHECK: default: - call void @bar(i32 %x) -; CHECK: call void @bar(i32 %x) - ret void -case0: -; CHECK: case0: - call void @bar(i32 %x) -; CHECK: call void @bar(i32 %x) - ret void -case1: -; CHECK: case1: - call void @bar(i32 %x) -; CHECK: call void @bar(i32 1) - ret void -case3: -; CHECK: case3: - call void @bar(i32 %x) -; CHECK: call void @bar(i32 %x) - ret void -} - ; CHECK-LABEL: @test5( define i1 @test5(i32 %x, i32 %y) { %cmp = icmp eq i32 %x, %y @@ -129,37 +42,6 @@ ret i1 %cmp3 } -; CHECK-LABEL: @test6( -define i1 @test6(i32 %x, i32 %y) { - %cmp2 = icmp ne i32 %x, %y - %cmp = icmp eq i32 %x, %y - %cmp3 = icmp eq i32 %x, %y - br i1 %cmp, label %same, label %different - -same: -; CHECK: ret i1 false - ret i1 %cmp2 - -different: -; CHECK: ret i1 false - ret i1 %cmp3 -} - -; CHECK-LABEL: @test6_fp( -define i1 @test6_fp(float %x, float %y) { - %cmp2 = fcmp une float %x, %y - %cmp = fcmp oeq float %x, %y - %cmp3 = fcmp oeq float %x, %y - br i1 %cmp, label %same, label %different - -same: -; CHECK: ret i1 false - ret i1 %cmp2 - -different: -; CHECK: ret i1 false - ret i1 %cmp3 -} ; CHECK-LABEL: @test7( define i1 @test7(i32 %x, i32 %y) { @@ -193,38 +75,6 @@ ret i1 %cmp3 } -; CHECK-LABEL: @test8( -define i1 @test8(i32 %x, i32 %y) { - %cmp2 = icmp sle i32 %x, %y - %cmp = icmp sgt i32 %x, %y - %cmp3 = icmp sgt i32 %x, %y - br i1 %cmp, label %same, label %different - -same: -; CHECK: ret i1 false - ret i1 %cmp2 - -different: -; CHECK: ret i1 false - ret i1 %cmp3 -} - -; CHECK-LABEL: @test8_fp( -define i1 @test8_fp(float %x, float %y) { - %cmp2 = fcmp ule float %x, %y - %cmp = fcmp ogt float %x, %y - %cmp3 = fcmp ogt float %x, %y - br i1 %cmp, label %same, label %different - -same: -; CHECK: ret i1 false - ret i1 %cmp2 - -different: -; CHECK: ret i1 false - ret i1 %cmp3 -} - ; PR1768 ; CHECK-LABEL: @test9( define i32 @test9(i32 %i, i32 %j) { Index: llvm/trunk/test/Transforms/NewGVN/predicates.ll =================================================================== --- llvm/trunk/test/Transforms/NewGVN/predicates.ll +++ llvm/trunk/test/Transforms/NewGVN/predicates.ll @@ -0,0 +1,111 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -basicaa -newgvn -S < %s | FileCheck %s + +; Function Attrs: noinline norecurse nounwind readonly ssp uwtable +define i32 @mp_unsgn_cmp(i32 %n, i32* nocapture readonly %in1, i32* nocapture readonly %in2) local_unnamed_addr { +; CHECK-LABEL: @mp_unsgn_cmp( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[CMP11:%.*]] = icmp sgt i32 [[N:%.*]], -1 +; CHECK-NEXT: br i1 [[CMP11]], label [[FOR_INC_PREHEADER:%.*]], label [[IF_ELSE:%.*]] +; CHECK: for.inc.preheader: +; CHECK-NEXT: br label [[FOR_INC:%.*]] +; CHECK: for.inc: +; CHECK-NEXT: [[STOREMERGE2:%.*]] = phi i32 [ [[INC:%.*]], [[FOR_INC]] ], [ 0, [[FOR_INC_PREHEADER]] ] +; CHECK-NEXT: [[IDXPROM:%.*]] = sext i32 [[STOREMERGE2]] to i64 +; CHECK-NEXT: [[ARRAYIDX:%.*]] = getelementptr inbounds i32, i32* [[IN1:%.*]], i64 [[IDXPROM]] +; CHECK-NEXT: [[TMP0:%.*]] = load i32, i32* [[ARRAYIDX]], align 4 +; CHECK-NEXT: [[ARRAYIDX4:%.*]] = getelementptr inbounds i32, i32* [[IN2:%.*]], i64 [[IDXPROM]] +; CHECK-NEXT: [[TMP1:%.*]] = load i32, i32* [[ARRAYIDX4]], align 4 +; CHECK-NEXT: [[SUB:%.*]] = sub nsw i32 [[TMP0]], [[TMP1]] +; CHECK-NEXT: [[INC]] = add nsw i32 [[STOREMERGE2]], 1 +; CHECK-NEXT: [[CMP1:%.*]] = icmp slt i32 [[STOREMERGE2]], [[N]] +; CHECK-NEXT: [[CMP2:%.*]] = icmp eq i32 [[SUB]], 0 +; CHECK-NEXT: [[OR_COND:%.*]] = and i1 [[CMP2]], [[CMP1]] +; CHECK-NEXT: br i1 [[OR_COND]], label [[FOR_INC]], label [[FOR_END:%.*]] +; CHECK: for.end: +; CHECK-NEXT: [[CMP5:%.*]] = icmp sgt i32 [[SUB]], 0 +; CHECK-NEXT: br i1 [[CMP5]], label [[IF_END8:%.*]], label [[IF_ELSE]] +; CHECK: if.else: +; CHECK-NEXT: [[SUB1_LCSSA4:%.*]] = phi i32 [ [[SUB]], [[FOR_END]] ], [ 0, [[ENTRY:%.*]] ] +; CHECK-NEXT: [[CMP6:%.*]] = icmp slt i32 [[SUB1_LCSSA4]], 0 +; CHECK-NEXT: [[DOTSUB1_LCSSA:%.*]] = select i1 [[CMP6]], i32 -1, i32 [[SUB1_LCSSA4]] +; CHECK-NEXT: ret i32 [[DOTSUB1_LCSSA]] +; CHECK: if.end8: +; CHECK-NEXT: ret i32 1 +; +entry: + %cmp11 = icmp sgt i32 %n, -1 + br i1 %cmp11, label %for.inc.preheader, label %if.else + +for.inc.preheader: ; preds = %entry + br label %for.inc + +for.inc: ; preds = %for.inc.preheader, %for.inc + %storemerge2 = phi i32 [ %inc, %for.inc ], [ 0, %for.inc.preheader ] + %idxprom = sext i32 %storemerge2 to i64 + %arrayidx = getelementptr inbounds i32, i32* %in1, i64 %idxprom + %0 = load i32, i32* %arrayidx, align 4 + %arrayidx4 = getelementptr inbounds i32, i32* %in2, i64 %idxprom + %1 = load i32, i32* %arrayidx4, align 4 + %sub = sub nsw i32 %0, %1 + %inc = add nsw i32 %storemerge2, 1 + %cmp1 = icmp slt i32 %storemerge2, %n + %cmp2 = icmp eq i32 %sub, 0 + %or.cond = and i1 %cmp2, %cmp1 +;; This is a self-critical edge to for.inc. If we insert predicate info on it, we will insert +;; predicateinfo at the end of this block, and think it dominates everthing using only dfs +;; numbers, instead of proper edge dominance. We would then proceed to propagate the true value +;; of sub == 0 everywhere, making this function only ever return 0. + br i1 %or.cond, label %for.inc, label %for.end + +for.end: ; preds = %for.inc + %sub.lcssa = phi i32 [ %sub, %for.inc ] + %cmp5 = icmp sgt i32 %sub.lcssa, 0 + br i1 %cmp5, label %if.end8, label %if.else + +if.else: ; preds = %entry, %for.end + %sub1.lcssa4 = phi i32 [ %sub.lcssa, %for.end ], [ 0, %entry ] + %cmp6 = icmp slt i32 %sub1.lcssa4, 0 + %.sub1.lcssa = select i1 %cmp6, i32 -1, i32 %sub1.lcssa4 + ret i32 %.sub1.lcssa + +if.end8: ; preds = %for.end + ret i32 1 +} + + +;; This test will generate a copy of a copy of predicateinfo to the multiple uses +;; of branch conditions below. Make sure we don't try to extract operand info. +; Function Attrs: uwtable +define fastcc void @barney() { +; CHECK-LABEL: @barney( +; CHECK-NEXT: bb: +; CHECK-NEXT: br label [[BB22:%.*]] +; CHECK: bb22: +; CHECK-NEXT: br i1 undef, label [[BB29:%.*]], label [[BB35:%.*]] +; CHECK: bb29: +; CHECK-NEXT: br i1 true, label [[BB33:%.*]], label [[BB35]] +; CHECK: bb33: +; CHECK-NEXT: br i1 true, label [[BB35]], label [[BB35]] +; CHECK: bb35: +; CHECK-NEXT: unreachable +; +bb: + br label %bb22 +bb22: ; preds = %bb21 + %tmp23 = icmp eq i32 undef, 2 + br i1 %tmp23, label %bb29, label %bb35 + + +bb29: ; preds = %bb28 + br i1 %tmp23, label %bb33, label %bb35 + + +bb33: ; preds = %bb31 + br i1 %tmp23, label %bb35, label %bb35 + + +bb35: ; preds = %bb33, %bb29, %bb22 + unreachable +} + Index: llvm/trunk/test/Transforms/NewGVN/storeoverstore.ll =================================================================== --- llvm/trunk/test/Transforms/NewGVN/storeoverstore.ll +++ llvm/trunk/test/Transforms/NewGVN/storeoverstore.ll @@ -1,3 +1,4 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py ; RUN: opt -newgvn -S < %s | FileCheck %s ; RUN: opt -passes=newgvn -S -o - %s | FileCheck %s @@ -7,31 +8,35 @@ ;; stores of the same value do not change the memory state to eliminate them. define i32 @foo(i32*, i32) { -; CHECK-LABEL: @foo +; CHECK-LABEL: @foo( +; CHECK-NEXT: store i32 5, i32* [[TMP0:%.*]], align 4 +; CHECK-NEXT: [[TMP3:%.*]] = icmp ne i32 [[TMP1:%.*]], 0 +; CHECK-NEXT: br i1 [[TMP3]], label [[TMP4:%.*]], label [[TMP5:%.*]] +; CHECK: br label [[TMP5]] +; CHECK: [[DOT0:%.*]] = phi i32 [ 10, [[TMP4]] ], [ 5, [[TMP2:%.*]] ] +; CHECK-NEXT: br i1 [[TMP3]], label [[TMP6:%.*]], label [[TMP8:%.*]] +; CHECK: [[TMP7:%.*]] = add nsw i32 [[DOT0]], 5 +; CHECK-NEXT: br label [[TMP8]] +; CHECK: [[DOT1:%.*]] = phi i32 [ [[TMP7]], [[TMP6]] ], [ [[DOT0]], [[TMP5]] ] +; CHECK-NEXT: ret i32 [[DOT1]] +; store i32 5, i32* %0, align 4 %3 = icmp ne i32 %1, 0 br i1 %3, label %4, label %7 ;