Index: llvm/include/llvm/Analysis/ValueTracking.h =================================================================== --- llvm/include/llvm/Analysis/ValueTracking.h +++ llvm/include/llvm/Analysis/ValueTracking.h @@ -751,13 +751,30 @@ std::pair canConvertToMinOrMaxIntrinsic(ArrayRef VL); - /// Attempt to match a simple first order recurrence cycle of the form: + /// Attempt to match a cyclic phi structure of the form: /// %iv = phi Ty [%Start, %Entry], [%Inc, %backedge] /// %inc = binop %iv, %step /// OR /// %iv = phi Ty [%Start, %Entry], [%Inc, %backedge] /// %inc = binop %step, %iv /// + /// This is *almost* a recurrence, but %step is not required to be + /// invariant with respect to the cycle. That is, we would have a + /// recurrence except that %step is a free variable in the formula. + bool matchNearRecurrence(const PHINode *P, BinaryOperator *&BO, + Value *&Start, Value *&Step); + + /// Analogous to the above, but starting from the binary operator + bool matchNearRecurrence(const BinaryOperator *I, PHINode *&P, + Value *&Start, Value *&Step); + + /// Attempt to match a simple first order recurrence cycle of the form: + /// %iv = phi Ty [%Start, %Entry], [%Inc, %backedge] + /// %inc = binop %iv, %invariant_step + /// OR + /// %iv = phi Ty [%Start, %Entry], [%Inc, %backedge] + /// %inc = binop %invariant_step, %iv + /// /// WARNING: For non-commutative operators, we will match both forms. This /// results in some odd recurrence structures. Callers may wish to filter /// out recurrences where the phi is not the LHS of the returned operator. @@ -765,11 +782,13 @@ /// NOTE: This is intentional simple. If you want the ability to analyze /// non-trivial loop conditons, see ScalarEvolution instead. bool matchSimpleRecurrence(const PHINode *P, BinaryOperator *&BO, - Value *&Start, Value *&Step); + Value *&Start, Value *&Step, + const DominatorTree &DT); /// Analogous to the above, but starting from the binary operator bool matchSimpleRecurrence(const BinaryOperator *I, PHINode *&P, - Value *&Start, Value *&Step); + Value *&Start, Value *&Step, + const DominatorTree &DT); /// Return true if RHS is known to be implied true by LHS. Return false if /// RHS is known to be implied false by LHS. Otherwise, return None if no Index: llvm/lib/Analysis/ValueTracking.cpp =================================================================== --- llvm/lib/Analysis/ValueTracking.cpp +++ llvm/lib/Analysis/ValueTracking.cpp @@ -1373,22 +1373,23 @@ const PHINode *P = cast(I); BinaryOperator *BO = nullptr; Value *R = nullptr, *L = nullptr; - if (matchSimpleRecurrence(P, BO, R, L)) { + if (matchNearRecurrence(P, BO, R, L)) { // Handle the case of a simple two-predecessor recurrence PHI. // There's a lot more that could theoretically be done here, but // this is sufficient to catch some interesting cases. unsigned Opcode = BO->getOpcode(); - // If this is a shift recurrence, we know the bits being shifted in. + // If this is a near shift recurrence, we know the bits being shifted in. // We can combine that with information about the start value of the // recurrence to conclude facts about the result. if ((Opcode == Instruction::LShr || Opcode == Instruction::AShr || Opcode == Instruction::Shl) && BO->getOperand(0) == I) { - // We have matched a recurrence of the form: + // We have matched a near recurrence of the form: // %iv = [R, %entry], [%iv.next, %backedge] // %iv.next = shift_op %iv, L + // (Note that L may not be invariant.) // Recurse with the phi context to avoid concern about whether facts // inferred hold at original context instruction. TODO: It may be @@ -6046,7 +6047,7 @@ return {Intrinsic::not_intrinsic, false}; } -bool llvm::matchSimpleRecurrence(const PHINode *P, BinaryOperator *&BO, +bool llvm::matchNearRecurrence(const PHINode *P, BinaryOperator *&BO, Value *&Start, Value *&Step) { // Handle the case of a simple two-predecessor recurrence PHI. // There's a lot more that could theoretically be done here, but @@ -6102,13 +6103,29 @@ return false; } -bool llvm::matchSimpleRecurrence(const BinaryOperator *I, PHINode *&P, - Value *&Start, Value *&Step) { +bool llvm::matchNearRecurrence(const BinaryOperator *I, PHINode *&P, + Value *&Start, Value *&Step) { BinaryOperator *BO = nullptr; P = dyn_cast(I->getOperand(0)); if (!P) P = dyn_cast(I->getOperand(1)); - return P && matchSimpleRecurrence(P, BO, Start, Step) && BO == I; + return P && matchNearRecurrence(P, BO, Start, Step) && BO == I; +} + +bool llvm::matchSimpleRecurrence(const PHINode *P, BinaryOperator *&BO, + Value *&Start, Value *&Step, + const DominatorTree &DT) { + if (!matchNearRecurrence(P, BO, Start, Step)) + return false; + return DT.dominates(Step, P); +} + +bool llvm::matchSimpleRecurrence(const BinaryOperator *I, PHINode *&P, + Value *&Start, Value *&Step, + const DominatorTree &DT) { + if (!matchNearRecurrence(I, P, Start, Step)) + return false; + return DT.dominates(Step, P); } /// Return true if "icmp Pred LHS RHS" is always true. Index: llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp =================================================================== --- llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp +++ llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp @@ -1990,7 +1990,7 @@ // An and recurrence w/loop invariant step is equivelent to (and start, step) PHINode *PN = nullptr; Value *Start = nullptr, *Step = nullptr; - if (matchSimpleRecurrence(&I, PN, Start, Step) && DT.dominates(Step, PN)) + if (matchSimpleRecurrence(&I, PN, Start, Step, DT)) return replaceInstUsesWith(I, Builder.CreateAnd(Start, Step)); return nullptr; @@ -2846,7 +2846,7 @@ // An or recurrence w/loop invariant step is equivelent to (or start, step) PHINode *PN = nullptr; Value *Start = nullptr, *Step = nullptr; - if (matchSimpleRecurrence(&I, PN, Start, Step) && DT.dominates(Step, PN)) + if (matchSimpleRecurrence(&I, PN, Start, Step, DT)) return replaceInstUsesWith(I, Builder.CreateOr(Start, Step)); return nullptr; Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp =================================================================== --- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp +++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp @@ -5576,7 +5576,7 @@ for (PHINode &PN : L->getHeader()->phis()) { BinaryOperator *BO = nullptr; Value *Start = nullptr, *Step = nullptr; - if (!matchSimpleRecurrence(&PN, BO, Start, Step)) + if (!matchSimpleRecurrence(&PN, BO, Start, Step, DT)) continue; switch (BO->getOpcode()) {