From f2cfef35966a24265b9e3c1b5ef8e64dcd5f431a Mon Sep 17 00:00:00 2001 From: Philip Reames Date: Fri, 26 Feb 2021 11:17:47 -0800 Subject: [PATCH] Be more mathematicly precise about definition of recurrence [NFC] This clarifies the interface of the matchSimpleRecurrence helper introduced in 8020be0b8 for non-commutative operators. After ebd3aeba, I realized the original way I framed the routine was inconsistent. For shifts, we only matched the the LHS form, but for sub we matched both and the caller wanted that information. So, instead, we now consistently match both forms for non-commutative operators and the caller becomes responsible for filtering if needed. I tried to put a clear warning in the header because I suspect the RHS form of e.g. a sub recurrence is non-obvious for most folks. (It was for me.) --- llvm/include/llvm/Analysis/ValueTracking.h | 12 +++++++++--- llvm/lib/Analysis/ValueTracking.cpp | 28 ++++++++++------------------ 2 files changed, 19 insertions(+), 21 deletions(-) diff --git a/llvm/include/llvm/Analysis/ValueTracking.h b/llvm/include/llvm/Analysis/ValueTracking.h index 10b65a2..584afc3 100644 --- a/llvm/include/llvm/Analysis/ValueTracking.h +++ b/llvm/include/llvm/Analysis/ValueTracking.h @@ -748,11 +748,17 @@ constexpr unsigned MaxAnalysisRecursionDepth = 6; std::pair canConvertToMinOrMaxIntrinsic(ArrayRef VL); - /// Attempt to match a simple recurrence cycle of the form: - /// (using SCEV's notation) - /// In IR, this might look like: + /// Attempt to match a simple first order recurrence cycle 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 + /// + /// 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. + /// /// 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, diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp index 07084c0..c62cfaf 100644 --- a/llvm/lib/Analysis/ValueTracking.cpp +++ b/llvm/lib/Analysis/ValueTracking.cpp @@ -1382,9 +1382,9 @@ static void computeKnownBitsFromOperator(const Operator *I, // If this is a 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) { + if ((Opcode == Instruction::LShr || Opcode == Instruction::AShr || + Opcode == Instruction::Shl) && + BO->getOperand(0) == I) { // We have matched a recurrence of the form: // %iv = [R, %entry], [%iv.next, %backedge] @@ -6051,21 +6051,10 @@ bool llvm::matchSimpleRecurrence(const PHINode *P, BinaryOperator *&BO, switch (Opcode) { default: continue; + // TODO: Expand list -- xor, div, gep, uaddo, etc.. case Instruction::LShr: case Instruction::AShr: - case Instruction::Shl: { - Value *LL = LU->getOperand(0); - Value *LR = LU->getOperand(1); - // Find a recurrence. - if (LL == P) - L = LR; - else - continue; // Check for recurrence with L and R flipped. - - break; // Match! - } - - // TODO: Expand list -- xor, mul, div, gep, uaddo, etc.. + case Instruction::Shl: case Instruction::Add: case Instruction::Sub: case Instruction::And: @@ -6086,8 +6075,11 @@ bool llvm::matchSimpleRecurrence(const PHINode *P, BinaryOperator *&BO, }; // We have matched a recurrence of the form: - // %iv = [R, %entry], [%iv.next, %backedge] - // %iv.next = binop %iv, L + // %iv = [R, %entry], [%iv.next, %backedge] + // %iv.next = binop %iv, L + // OR + // %iv = [R, %entry], [%iv.next, %backedge] + // %iv.next = binop L, %iv BO = cast(LU); Start = R; Step = L; -- 2.7.4