[ARM] Use matchSimpleRecurrence to simplify some code in MVEGatherScatterLowering. NFCI

[craig.topper]

Ping

[dmgreen]

Looks nice. Like a good cleanup.

What made you look into the MVEGatherScatterLowering pass, out of interest?

[craig.topper]

In D105262#2864583, @dmgreen wrote:

Looks nice. Like a good cleanup.

What made you look into the MVEGatherScatterLowering pass, out of interest?

I've been trying to apply some portions of it to RISCV vectors. So far just the code to push computations out of the loop. One interesting thing I noticed is that MVEGatherScatterLowering can't push shl by a constant splat out of a loop. That would be the canonical IR for a multiply by a constant power of 2 splat.

[dmgreen]

Oh yeah, I've seen shr come up before too. That was from gathers produced from x[i/2]. It's not one that we've got to yet. Constant factors of 2 are less common under MVE I think, because would usually use VLD2 instead.

So far just the code to push computations out of the loop.

Yesh, the other half of this might be pretty MVE specific, lowering the gathers to intrinsics. The exact forms of gathers supported in MVE is sometimes quite specific, and can require some of the optimizations here to lower them nicely.

This patch LGTM from what I can tell about matchSimpleRecurrence. Thanks for putting it together.

llvm/lib/Target/ARM/MVEGatherScatterLowering.cpp

 //===- MVEGatherScatterLowering.cpp - Gather/Scatter lowering -------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 /// This pass custom lowers llvm.gather and llvm.scatter instructions to
 /// arm.mve.gather and arm.mve.scatter intrinsics, optimising the code to
 /// produce a better final result as we go.
 //
 //===----------------------------------------------------------------------===//
 
 #include "ARM.h"
 #include "ARMBaseInstrInfo.h"
 #include "ARMSubtarget.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/Analysis/ValueTracking.h"
 #include "llvm/CodeGen/TargetLowering.h"
 #include "llvm/CodeGen/TargetPassConfig.h"
 #include "llvm/CodeGen/TargetSubtargetInfo.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/IntrinsicsARM.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/Value.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include <algorithm>
 #include <cassert>
 
 using namespace llvm;
 
if (isa<PHINode>(Offs->getOperand(0))) {
     } else if (isa<PHINode>(Offs->getOperand(1))) {
       Phi = cast<PHINode>(Offs->getOperand(1));
       OffsSecondOp = 0;
     } else {
       return false;
     }
   }
   // A phi node we want to perform this function on should be from the
-  // loop header, and shouldn't have more than 2 incoming values
-  if (Phi->getParent() != L->getHeader() ||
-      Phi->getNumIncomingValues() != 2)
+  // loop header.
+  if (Phi->getParent() != L->getHeader())
     return false;
 
-  // The phi must be an induction variable
-  int IncrementingBlock = -1;
-
-  for (int i = 0; i < 2; i++)
-    if (auto *Op = dyn_cast<Instruction>(Phi->getIncomingValue(i)))
-      if (Op->getOpcode() == Instruction::Add &&
-          (Op->getOperand(0) == Phi || Op->getOperand(1) == Phi))
-        IncrementingBlock = i;
-  if (IncrementingBlock == -1)
+  // We're looking for a simple add recurrence.
+  BinaryOperator *IncInstruction;
+  Value *Start, *IncrementPerRound;
+  if (!matchSimpleRecurrence(Phi, IncInstruction, Start, IncrementPerRound) ||
+      IncInstruction->getOpcode() != Instruction::Add)
     return false;
 
-  Instruction *IncInstruction =
-      cast<Instruction>(Phi->getIncomingValue(IncrementingBlock));
-
-  // If the phi is not used by anything else, we can just adapt it when
-  // replacing the instruction; if it is, we'll have to duplicate it
-  PHINode *NewPhi;
-  Value *IncrementPerRound = IncInstruction->getOperand(
-      (IncInstruction->getOperand(0) == Phi) ? 1 : 0);
+  int IncrementingBlock = Phi->getIncomingValue(0) == IncInstruction ? 0 : 1;
 
   // Get the value that is added to/multiplied with the phi
   Value *OffsSecondOperand = Offs->getOperand(OffsSecondOp);
 
   if (IncrementPerRound->getType() != OffsSecondOperand->getType() ||
       !L->isLoopInvariant(OffsSecondOperand))
     // Something has gone wrong, abort
     return false;
 
   // Only proceed if the increment per round is a constant or an instruction
   // which does not originate from within the loop
   if (!isa<Constant>(IncrementPerRound) &&
       !(isa<Instruction>(IncrementPerRound) &&
         !L->contains(cast<Instruction>(IncrementPerRound))))
     return false;
 
+  // If the phi is not used by anything else, we can just adapt it when
+  // replacing the instruction; if it is, we'll have to duplicate it
+  PHINode *NewPhi;
   if (Phi->getNumUses() == 2) {
     // No other users -> reuse existing phi (One user is the instruction
     // we're looking at, the other is the phi increment)
     if (IncInstruction->getNumUses() != 1) {
       // If the incrementing instruction does have more users than
       // our phi, we need to copy it
       IncInstruction = BinaryOperator::Create(
           Instruction::BinaryOps(IncInstruction->getOpcode()), Phi,