diff --git a/llvm/lib/Transforms/Scalar/NewGVN.cpp b/llvm/lib/Transforms/Scalar/NewGVN.cpp --- a/llvm/lib/Transforms/Scalar/NewGVN.cpp +++ b/llvm/lib/Transforms/Scalar/NewGVN.cpp @@ -673,24 +673,43 @@ struct ExprResult { const Expression *Expr; Value *ExtraDep; + const PredicateBase *PredDep; ~ExprResult() { assert(!ExtraDep && "unhandled ExtraDep"); } operator bool() const { return Expr; } - static ExprResult none() { return {nullptr, nullptr}; } + static ExprResult none() { return {nullptr, nullptr, nullptr}; } static ExprResult some(const Expression *Expr, Value *ExtraDep = nullptr) { - return {Expr, ExtraDep}; + return {Expr, ExtraDep, nullptr}; + } + static ExprResult some(const Expression *Expr, + const PredicateBase *PredDep) { + return {Expr, nullptr, PredDep}; + } + static ExprResult some(const Expression *Expr, Value *ExtraDep, + const PredicateBase *PredDep) { + return {Expr, ExtraDep, PredDep}; } /// Add \p User as an additional user of ExtraDep, if it is set, using \p /// AdditionalUsers. void addExtraUserTo( Instruction *User, - DenseMap> &AdditionalUsers) { + DenseMap> &AdditionalUsers, + DenseMap> + &PredicateToUsers) { if (ExtraDep && ExtraDep != User && isa(ExtraDep)) AdditionalUsers[ExtraDep].insert(User); + + if (PredDep) { + if (auto *PBranch = dyn_cast(PredDep)) + PredicateToUsers[PBranch->Condition].insert(User); + else if (auto *PAssume = dyn_cast(PredDep)) + PredicateToUsers[PAssume->Condition].insert(User); + } ExtraDep = nullptr; + PredDep = nullptr; } }; @@ -776,14 +795,14 @@ MemoryAccess *) const; const Expression *performSymbolicLoadEvaluation(Instruction *) const; const Expression *performSymbolicStoreEvaluation(Instruction *) const; - const Expression *performSymbolicCallEvaluation(Instruction *) const; + ExprResult performSymbolicCallEvaluation(Instruction *) const; void sortPHIOps(MutableArrayRef Ops) const; const Expression *performSymbolicPHIEvaluation(ArrayRef, Instruction *I, BasicBlock *PHIBlock) const; const Expression *performSymbolicAggrValueEvaluation(Instruction *) const; ExprResult performSymbolicCmpEvaluation(Instruction *) const; - const Expression *performSymbolicPredicateInfoEvaluation(Instruction *) const; + ExprResult performSymbolicPredicateInfoEvaluation(Instruction *) const; // Congruence finding. bool someEquivalentDominates(const Instruction *, const Instruction *) const; @@ -836,7 +855,6 @@ void markValueLeaderChangeTouched(CongruenceClass *CC); void markMemoryLeaderChangeTouched(CongruenceClass *CC); void markPhiOfOpsChanged(const Expression *E); - void addPredicateUsers(const PredicateBase *, Instruction *) const; void addMemoryUsers(const MemoryAccess *To, MemoryAccess *U) const; void addAdditionalUsers(Value *To, Value *User) const; @@ -1078,7 +1096,7 @@ Value *V = SimplifyBinOp(Opcode, E->getOperand(0), E->getOperand(1), SQ); if (auto Simplified = checkExprResults(E, I, V)) { - Simplified.addExtraUserTo(I, AdditionalUsers); + Simplified.addExtraUserTo(I, AdditionalUsers, PredicateToUsers); return Simplified.Expr; } return E; @@ -1539,17 +1557,17 @@ return LE; } -const Expression * +NewGVN::ExprResult NewGVN::performSymbolicPredicateInfoEvaluation(Instruction *I) const { auto *PI = PredInfo->getPredicateInfoFor(I); if (!PI) - return nullptr; + return ExprResult::none(); LLVM_DEBUG(dbgs() << "Found predicate info from instruction !\n"); const Optional &Constraint = PI->getConstraint(); if (!Constraint) - return nullptr; + return ExprResult::none(); CmpInst::Predicate Predicate = Constraint->Predicate; Value *CmpOp0 = I->getOperand(0); @@ -1566,45 +1584,43 @@ AdditionallyUsedValue = CmpOp1; } - if (Predicate == CmpInst::ICMP_EQ) { - addPredicateUsers(PI, I); - addAdditionalUsers(AdditionallyUsedValue, I); - return createVariableOrConstant(FirstOp); - } + if (Predicate == CmpInst::ICMP_EQ) + return ExprResult::some(createVariableOrConstant(FirstOp), + AdditionallyUsedValue, PI); // Handle the special case of floating point. if (Predicate == CmpInst::FCMP_OEQ && isa(FirstOp) && - !cast(FirstOp)->isZero()) { - addPredicateUsers(PI, I); - addAdditionalUsers(AdditionallyUsedValue, I); - return createConstantExpression(cast(FirstOp)); - } + !cast(FirstOp)->isZero()) + return ExprResult::some(createConstantExpression(cast(FirstOp)), + AdditionallyUsedValue, PI); - return nullptr; + return ExprResult::none(); } // Evaluate read only and pure calls, and create an expression result. -const Expression *NewGVN::performSymbolicCallEvaluation(Instruction *I) const { +NewGVN::ExprResult NewGVN::performSymbolicCallEvaluation(Instruction *I) const { auto *CI = cast(I); if (auto *II = dyn_cast(I)) { // Intrinsics 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 (auto Res = performSymbolicPredicateInfoEvaluation(I)) + return Res; + return ExprResult::some(createVariableOrConstant(ReturnedValue)); } } if (AA->doesNotAccessMemory(CI)) { - return createCallExpression(CI, TOPClass->getMemoryLeader()); + return ExprResult::some( + createCallExpression(CI, TOPClass->getMemoryLeader())); } else if (AA->onlyReadsMemory(CI)) { if (auto *MA = MSSA->getMemoryAccess(CI)) { auto *DefiningAccess = MSSAWalker->getClobberingMemoryAccess(MA); - return createCallExpression(CI, DefiningAccess); + return ExprResult::some(createCallExpression(CI, DefiningAccess)); } else // MSSA determined that CI does not access memory. - return createCallExpression(CI, TOPClass->getMemoryLeader()); + return ExprResult::some( + createCallExpression(CI, TOPClass->getMemoryLeader())); } - return nullptr; + return ExprResult::none(); } // Retrieve the memory class for a given MemoryAccess. @@ -1879,31 +1895,31 @@ // edge then we may be implied true or false. if (CmpInst::isImpliedTrueByMatchingCmp(BranchPredicate, OurPredicate)) { - addPredicateUsers(PI, I); return ExprResult::some( - createConstantExpression(ConstantInt::getTrue(CI->getType()))); + createConstantExpression(ConstantInt::getTrue(CI->getType())), + PI); } if (CmpInst::isImpliedFalseByMatchingCmp(BranchPredicate, OurPredicate)) { - addPredicateUsers(PI, I); return ExprResult::some( - createConstantExpression(ConstantInt::getFalse(CI->getType()))); + createConstantExpression(ConstantInt::getFalse(CI->getType())), + PI); } } 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 ExprResult::some( - createConstantExpression(ConstantInt::getFalse(CI->getType()))); + createConstantExpression(ConstantInt::getFalse(CI->getType())), + PI); } else if (BranchPredicate == CmpInst::getInversePredicate(OurPredicate)) { - addPredicateUsers(PI, I); // Inverse predicate, we know the other was false, so this is true. return ExprResult::some( - createConstantExpression(ConstantInt::getTrue(CI->getType()))); + createConstantExpression(ConstantInt::getTrue(CI->getType())), + PI); } } } @@ -1943,7 +1959,7 @@ E = performSymbolicPHIEvaluation(Ops, I, getBlockForValue(I)); } break; case Instruction::Call: - E = performSymbolicCallEvaluation(I); + return performSymbolicCallEvaluation(I); break; case Instruction::Store: E = performSymbolicStoreEvaluation(I); @@ -2049,18 +2065,6 @@ touchAndErase(MemoryToUsers, MA); } -// Add I to the set of users of a given predicate. -void NewGVN::addPredicateUsers(const PredicateBase *PB, Instruction *I) const { - // Don't add temporary instructions to the user lists. - if (AllTempInstructions.count(I)) - return; - - 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) { touchAndErase(PredicateToUsers, I); @@ -2434,7 +2438,7 @@ auto Res = performSymbolicEvaluation(I, Visited); if (const auto *CE = dyn_cast_or_null(Res.Expr)) { CondEvaluated = CE->getConstantValue(); - Res.addExtraUserTo(I, AdditionalUsers); + Res.addExtraUserTo(I, AdditionalUsers, PredicateToUsers); } else { // Did not use simplification result, no need to add the extra // dependency. @@ -2624,7 +2628,7 @@ auto Res = performSymbolicEvaluation(TransInst, Visited); const Expression *E = Res.Expr; - Res.addExtraUserTo(OrigInst, AdditionalUsers); + Res.addExtraUserTo(OrigInst, AdditionalUsers, PredicateToUsers); InstrDFS.erase(TransInst); AllTempInstructions.erase(TransInst); TempToBlock.erase(TransInst); @@ -3053,7 +3057,7 @@ if (DebugCounter::shouldExecute(VNCounter)) { auto Res = performSymbolicEvaluation(I, Visited); Symbolized = Res.Expr; - Res.addExtraUserTo(I, AdditionalUsers); + Res.addExtraUserTo(I, AdditionalUsers, PredicateToUsers); // Make a phi of ops if necessary if (Symbolized && !isa(Symbolized) && diff --git a/llvm/test/Transforms/NewGVN/phi-of-ops-simplification-dependencies.ll b/llvm/test/Transforms/NewGVN/phi-of-ops-simplification-dependencies.ll --- a/llvm/test/Transforms/NewGVN/phi-of-ops-simplification-dependencies.ll +++ b/llvm/test/Transforms/NewGVN/phi-of-ops-simplification-dependencies.ll @@ -116,3 +116,50 @@ exit: ret void } + +define void @pr49873_cmp_simplification_dependency(i32* %ptr, i1 %c.0) { +; CHECK-LABEL: @pr49873_cmp_simplification_dependency( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[LOOP_1:%.*]] +; CHECK: loop.1: +; CHECK-NEXT: br i1 [[C_0:%.*]], label [[LOOP_1_LATCH:%.*]], label [[LOOP_2:%.*]] +; CHECK: loop.2: +; CHECK-NEXT: [[I130:%.*]] = phi i32 [ [[I132:%.*]], [[LOOP_2]] ], [ 0, [[LOOP_1]] ] +; CHECK-NEXT: [[I132]] = add nuw i32 [[I130]], 1 +; CHECK-NEXT: [[I133:%.*]] = load i32, i32* [[PTR:%.*]], align 4 +; CHECK-NEXT: [[C_1:%.*]] = icmp ult i32 [[I132]], [[I133]] +; CHECK-NEXT: br i1 [[C_1]], label [[LOOP_2]], label [[LOOP_2_EXIT:%.*]] +; CHECK: loop.2.exit: +; CHECK-NEXT: br label [[LOOP_1_LATCH]] +; CHECK: loop.1.latch: +; CHECK-NEXT: [[DOTLCSSA:%.*]] = phi i32 [ 0, [[LOOP_1]] ], [ [[I133]], [[LOOP_2_EXIT]] ] +; CHECK-NEXT: [[C_2:%.*]] = icmp ult i32 1, [[DOTLCSSA]] +; CHECK-NEXT: br i1 [[C_2]], label [[LOOP_1]], label [[EXIT:%.*]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +entry: + br label %loop.1 + +loop.1: + %i65 = add nuw i32 0, 1 + br i1 %c.0, label %loop.1.latch, label %loop.2 + +loop.2: + %i130 = phi i32 [ %i132, %loop.2 ], [ 0, %loop.1 ] + %i132 = add nuw i32 %i130, 1 + %i133 = load i32, i32* %ptr, align 4 + %c.1 = icmp ult i32 %i132, %i133 + br i1 %c.1, label %loop.2, label %loop.2.exit + +loop.2.exit: + br label %loop.1.latch + +loop.1.latch: ; preds = %loop.2.exit, %loop.1 + %.lcssa = phi i32 [ 0, %loop.1 ], [ %i133, %loop.2.exit ] + %c.2 = icmp ult i32 %i65, %.lcssa + br i1 %c.2, label %loop.1, label %exit + +exit: + ret void +}