[ValueTracking] Add `matchSimpleBinaryIntrinsicRecurrence` helper

Similarly to what it is being done to match simple recurrence cycle
relations, attempt to match value-accumulating recurrences of kind:
```
  %umax.acc = phi i8 [ %umax, %backedge ], [ %a, %entry ]
  %umax = call i8 @llvm.umax.i8(i8 %umax.acc, i8 %b)
```
Preliminary work to let InstCombine avoid folding such recurrences,
so that simple loop-invariant computation may get hoisted. Minor
opportunity to refactor out code as well.

1 files changed, 52 insertions, 0 deletions

diff --git a/llvm/unittests/Analysis/ValueTrackingTest.cpp b/llvm/unittests/Analysis/ValueTrackingTest.cpp
index 6031898..dbe7228 100644
--- a/llvm/unittests/Analysis/ValueTrackingTest.cpp
+++ b/llvm/unittests/Analysis/ValueTrackingTest.cpp
@@ -1257,6 +1257,58 @@ TEST_F(ValueTrackingTest, computePtrAlignment) {
   EXPECT_EQ(getKnownAlignment(A, DL, CxtI3, &AC, &DT), Align(16));
 }
 
+TEST_F(ValueTrackingTest, MatchBinaryIntrinsicRecurrenceUMax) {
+  auto M = parseModule(R"(
+    define i8 @test(i8 %a, i8 %b) {
+    entry:
+      br label %loop
+    loop:
+      %iv = phi i8 [ %iv.next, %loop ], [ 0, %entry ]
+      %umax.acc = phi i8 [ %umax, %loop ], [ %a, %entry ]
+      %umax = call i8 @llvm.umax.i8(i8 %umax.acc, i8 %b)
+      %iv.next = add nuw i8 %iv, 1
+      %cmp = icmp ult i8 %iv.next, 10
+      br i1 %cmp, label %loop, label %exit
+    exit:
+      ret i8 %umax
+    }
+  )");
+
+  auto *F = M->getFunction("test");
+  auto *II = &cast<IntrinsicInst>(findInstructionByName(F, "umax"));
+  auto *UMaxAcc = &cast<PHINode>(findInstructionByName(F, "umax.acc"));
+  PHINode *PN;
+  Value *Init, *OtherOp;
+  EXPECT_TRUE(matchSimpleBinaryIntrinsicRecurrence(II, PN, Init, OtherOp));
+  EXPECT_EQ(UMaxAcc, PN);
+  EXPECT_EQ(F->getArg(0), Init);
+  EXPECT_EQ(F->getArg(1), OtherOp);
+}
+
+TEST_F(ValueTrackingTest, MatchBinaryIntrinsicRecurrenceNegativeFSHR) {
+  auto M = parseModule(R"(
+    define i8 @test(i8 %a, i8 %b, i8 %c) {
+    entry:
+      br label %loop
+    loop:
+      %iv = phi i8 [ %iv.next, %loop ], [ 0, %entry ]
+      %fshr.acc = phi i8 [ %fshr, %loop ], [ %a, %entry ]
+      %fshr = call i8 @llvm.fshr.i8(i8 %fshr.acc, i8 %b, i8 %c)
+      %iv.next = add nuw i8 %iv, 1
+      %cmp = icmp ult i8 %iv.next, 10
+      br i1 %cmp, label %loop, label %exit
+    exit:
+      ret i8 %fshr
+    }
+  )");
+
+  auto *F = M->getFunction("test");
+  auto *II = &cast<IntrinsicInst>(findInstructionByName(F, "fshr"));
+  PHINode *PN;
+  Value *Init, *OtherOp;
+  EXPECT_FALSE(matchSimpleBinaryIntrinsicRecurrence(II, PN, Init, OtherOp));
+}
+
 TEST_F(ComputeKnownBitsTest, ComputeKnownBits) {
   parseAssembly(
       "define i32 @test(i32 %a, i32 %b) {\n"