[ARM][ParallelDSP] Change the search for smlads

[samparker]

Summary

Two functional changes have been made here:

1. Now search up from any add instruction to find the chains of operations that we may turn into a smlad. This allows the generation of a smlad which doesn't accumulate into a phi.
2. The search function has been corrected to stop it falsely searching up through an invalid path.

The bulk of the changes have been making the Reduction struct a class and making it more C++y with getters and setters.

[SjoerdMeijer]

A first pass, see inlined nits.

lib/Target/ARM/ARMParallelDSP.cpp

98–161

if we use doxygen style comments for the methods of this class, should we provide a general description here too?

102

nit: indentation

110

nit: apart?

113

same here?

121

nit: perhaps this can also be a setter method, as that's the only thing it does essentially.

I am now curious about the false case. I.e., perhaps also briefly comment on what is supported (1 or more accumulators in 1 loop), and what happens in the false case.

139

another nit: the getter and setter methods are not capitalised, while the other methods are. Not sure they should be though....perhaps they are an exception.

459

Comment out of date? Don't think we look at PHIs anymore, but just at any add?

489

nit: newline

497

Perhaps good to spend a few words here on which non-instructions that might be?

[samparker]

Added and modified comments.

[SjoerdMeijer]

Thanks. This looks very reasonable to me.

lib/Target/ARM/ARMParallelDSP.cpp

 
 static cl::opt<bool>
 DisableParallelDSP("disable-arm-parallel-dsp", cl::Hidden, cl::init(false),
                    cl::desc("Disable the ARM Parallel DSP pass"));
 
 namespace {
   struct OpChain;
   struct BinOpChain;
-  struct Reduction;
+  class Reduction;
 
   using OpChainList     = SmallVector<std::unique_ptr<OpChain>, 8>;
   using ReductionList   = SmallVector<Reduction, 8>;
   using ValueList       = SmallVector<Value*, 8>;
   using MemInstList     = SmallVector<LoadInst*, 8>;
   using PMACPair        = std::pair<BinOpChain*,BinOpChain*>;
   using PMACPairList    = SmallVector<PMACPair, 8>;
   using Instructions    = SmallVector<Instruction*,16>;
void PopulateLoads() {
         if (auto *Ld = dyn_cast<LoadInst>(V))
           Loads.push_back(Ld);
       }
     }
 
     unsigned size() const { return AllValues.size(); }
   };
 
-  // 'BinOpChain' and 'Reduction' are just some bookkeeping data structures.
-  // 'Reduction' contains the phi-node and accumulator statement from where we
-  // start pattern matching, and 'BinOpChain' the multiplication
-  // instructions that are candidates for parallel execution.
+  // 'BinOpChain' holds the multiplication instructions that are candidates
+  // for parallel execution.
   struct BinOpChain : public OpChain {
     ValueList     LHS;      // List of all (narrow) left hand operands.
     ValueList     RHS;      // List of all (narrow) right hand operands.
     bool Exchange = false;
 
     BinOpChain(Instruction *I, ValueList &lhs, ValueList &rhs) :
       OpChain(I, lhs), LHS(lhs), RHS(rhs) {
         for (auto *V : RHS)
           AllValues.push_back(V);
       }
 
     bool AreSymmetrical(BinOpChain *Other);
   };
 
-  struct Reduction {
-    PHINode         *Phi;             // The Phi-node from where we start
-                                      // pattern matching.
-    Instruction     *AccIntAdd;       // The accumulating integer add statement,
-                                      // i.e, the reduction statement.
-    OpChainList     MACCandidates;    // The MAC candidates associated with
-                                      // this reduction statement.
-    PMACPairList    PMACPairs;
-    Reduction (PHINode *P, Instruction *Acc) : Phi(P), AccIntAdd(Acc) { };
+  /// Represent a sequence of multiply-accumulate operations with the aim to
+  /// perform the multiplications in parallel.
+  class Reduction {
+    Instruction     *Root = nullptr;
+    Value           *Acc = nullptr;
+    OpChainList     Muls;
+    PMACPairList        MulPairs;
+    SmallPtrSet<Instruction*, 4> Adds;
+
+  public:
+    Reduction() = delete;
+
+    Reduction (Instruction *Add) : Root(Add) { }
+
+    /// Record an Add instruction that is a part of the this reduction.
+    void InsertAdd(Instruction *I) { Adds.insert(I); }
+
+    /// Record a BinOpChain, rooted at a Mul instruction, that is a part of
+    /// this reduction.
+    void InsertMul(Instruction *I, ValueList &LHS, ValueList &RHS) {
+      Muls.push_back(make_unique<BinOpChain>(I, LHS, RHS));
+    }
+
+    /// Add the incoming accumulator value, returns true if a value had not
+    /// already been added. Returning false signals to the user that this
+    /// reduction already has a value to initialise the accumulator.
+    bool InsertAcc(Value *V) {
+      if (Acc)
+        return false;
+      Acc = V;
+      return true;
+    }
+
+    /// Set two BinOpChains, rooted at muls, that can be executed as a single
+    /// parallel operation.
+    void AddMulPair(BinOpChain *Mul0, BinOpChain *Mul1) {
+      MulPairs.push_back(std::make_pair(Mul0, Mul1));
+    }
+
+    /// Return true if enough mul operations are found that can be executed in
+    /// parallel.
+    bool CreateParallelPairs();
+
+    /// Return the add instruction which is the root of the reduction.
+    Instruction *getRoot() { return Root; }
+
+    /// Return the incoming value to be accumulated. This maybe null.
+    Value *getAccumulator() { return Acc; }
+
+    /// Return the set of adds that comprise the reduction.
+    SmallPtrSetImpl<Instruction*> &getAdds() { return Adds; }
+
+    /// Return the BinOpChain, rooted at mul instruction, that comprise the
+    /// the reduction.
+    OpChainList &getMuls() { return Muls; }
+
+    /// Return the BinOpChain, rooted at mul instructions, that have been
+    /// paired for parallel execution.
+    PMACPairList &getMulPairs() { return MulPairs; }
+
+    /// To finalise, replace the uses of the root with the intrinsic call.
+    void UpdateRoot(Instruction *SMLAD) {
+      Root->replaceAllUsesWith(SMLAD);
+    }
   };
 
   class WidenedLoad {
     LoadInst *NewLd = nullptr;
     SmallVector<LoadInst*, 4> Loads;
 
   public:
     WidenedLoad(SmallVectorImpl<LoadInst*> &Lds, LoadInst *Wide)
class ARMParallelDSP : public LoopPass {
     AliasAnalysis     *AA;
     TargetLibraryInfo *TLI;
     DominatorTree     *DT;
     LoopInfo          *LI;
     Loop              *L;
     const DataLayout  *DL;
     Module            *M;
     std::map<LoadInst*, LoadInst*> LoadPairs;
+    SmallPtrSet<LoadInst*, 4> OffsetLoads;
     std::map<LoadInst*, std::unique_ptr<WidenedLoad>> WideLoads;
 
+    template<unsigned>
+    bool IsNarrowSequence(Value *V, ValueList &VL);
+
     bool RecordMemoryOps(BasicBlock *BB);
-    bool InsertParallelMACs(Reduction &Reduction);
+    void InsertParallelMACs(Reduction &Reduction);
     bool AreSequentialLoads(LoadInst *Ld0, LoadInst *Ld1, MemInstList &VecMem);
     LoadInst* CreateWideLoad(SmallVectorImpl<LoadInst*> &Loads,
                              IntegerType *LoadTy);
-    void CreateParallelMACPairs(Reduction &R);
-    Instruction *CreateSMLADCall(SmallVectorImpl<LoadInst*> &VecLd0,
-                                 SmallVectorImpl<LoadInst*> &VecLd1,
-                                 Instruction *Acc, bool Exchange,
-                                 Instruction *InsertAfter);
+    bool CreateParallelPairs(Reduction &R);
 
     /// Try to match and generate: SMLAD, SMLADX - Signed Multiply Accumulate
     /// Dual performs two signed 16x16-bit multiplications. It adds the
     /// products to a 32-bit accumulate operand. Optionally, the instruction can
     /// exchange the halfwords of the second operand before performing the
     /// arithmetic.
-    bool MatchSMLAD(Function &F);
+    bool MatchSMLAD(Loop *L);
 
   public:
     static char ID;
 
     ARMParallelDSP() : LoopPass(ID) { }
 
     bool doInitialization(Loop *L, LPPassManager &LPM) override {
       LoadPairs.clear();
bool runOnLoop(Loop *TheLoop, LPPassManager &) override {
       // This is not a fundamental restriction, but lifting this would just
       // require more work to do the transformation and then patch up the CFG.
       if (Header != TheLoop->getLoopLatch()) {
         LLVM_DEBUG(dbgs() << "The loop header is not the loop latch: not "
                              "running pass ARMParallelDSP\n");
         return false;
       }
 
-      // We need a preheader as getIncomingValueForBlock assumes there is one.
-      if (!TheLoop->getLoopPreheader()) {
-        LLVM_DEBUG(dbgs() << "No preheader found, bailing out\n");
-        return false;
-      }
+      if (!TheLoop->getLoopPreheader())
+        InsertPreheaderForLoop(L, DT, LI, nullptr, true);
 
       Function &F = *Header->getParent();
       M = F.getParent();
       DL = &M->getDataLayout();
 
       auto &TM = TPC.getTM<TargetMachine>();
       auto *ST = &TM.getSubtarget<ARMSubtarget>(F);
 
bool runOnLoop(Loop *TheLoop, LPPassManager &) override {
       LLVM_DEBUG(dbgs() << "\n== Parallel DSP pass ==\n");
       LLVM_DEBUG(dbgs() << " - " << F.getName() << "\n\n");
 
       if (!RecordMemoryOps(Header)) {
         LLVM_DEBUG(dbgs() << " - No sequential loads found.\n");
         return false;
       }
 
-      bool Changes = MatchSMLAD(F);
+      bool Changes = MatchSMLAD(L);
       return Changes;
     }
   };
 }
 
 template<typename MemInst>
 static bool AreSequentialAccesses(MemInst *MemOp0, MemInst *MemOp1,
                                   const DataLayout &DL, ScalarEvolution &SE) {
bool ARMParallelDSP::AreSequentialLoads(LoadInst *Ld0, LoadInst *Ld1,
   );
 
   VecMem.clear();
   VecMem.push_back(Ld0);
   VecMem.push_back(Ld1);
   return true;
 }
 
+// MaxBitwidth: the maximum supported bitwidth of the elements in the DSP
+// instructions, which is set to 16. So here we should collect all i8 and i16
+// narrow operations.
+// TODO: we currently only collect i16, and will support i8 later, so that's
+// why we check that types are equal to MaxBitWidth, and not <= MaxBitWidth.
+template<unsigned MaxBitWidth>
+bool ARMParallelDSP::IsNarrowSequence(Value *V, ValueList &VL) {
+  ConstantInt *CInt;
+
+  if (match(V, m_ConstantInt(CInt))) {
+    // TODO: if a constant is used, it needs to fit within the bit width.
+    return false;
+  }
+
+  auto *I = dyn_cast<Instruction>(V);
+  if (!I)
+    return false;
+
+  Value *Val, *LHS, *RHS;
+  if (match(V, m_Trunc(m_Value(Val)))) {
+    if (cast<TruncInst>(I)->getDestTy()->getIntegerBitWidth() == MaxBitWidth)
+      return IsNarrowSequence<MaxBitWidth>(Val, VL);
+  } else if (match(V, m_Add(m_Value(LHS), m_Value(RHS)))) {
+    // TODO: we need to implement sadd16/sadd8 for this, which enables to
+    // also do the rewrite for smlad8.ll, but it is unsupported for now.
+    return false;
+  } else if (match(V, m_ZExtOrSExt(m_Value(Val)))) {
+    if (cast<CastInst>(I)->getSrcTy()->getIntegerBitWidth() != MaxBitWidth)
+      return false;
+
+    if (match(Val, m_Load(m_Value()))) {
+      auto *Ld = cast<LoadInst>(Val);
+
+      // Check that these load could be paired.
+      if (!LoadPairs.count(Ld) && !OffsetLoads.count(Ld))
+        return false;
+
+      VL.push_back(Val);
+      VL.push_back(I);
+      return true;
+    }
+  }
+  return false;
+}
+
 /// Iterate through the block and record base, offset pairs of loads which can
 /// be widened into a single load.
 bool ARMParallelDSP::RecordMemoryOps(BasicBlock *BB) {
   SmallVector<LoadInst*, 8> Loads;
   SmallVector<Instruction*, 8> Writes;
 
   // Collect loads and instruction that may write to memory. For now we only
   // record loads which are simple, sign-extended and have a single user.
bool ARMParallelDSP::RecordMemoryOps(BasicBlock *BB) {
   for (auto *Base : Loads) {
     for (auto *Offset : Loads) {
       if (Base == Offset)
         continue;
 
       if (AreSequentialAccesses<LoadInst>(Base, Offset, *DL, *SE) &&
           SafeToPair(Base, Offset)) {
         LoadPairs[Base] = Offset;
+        OffsetLoads.insert(Offset);
         break;
       }
     }
   }
 
   LLVM_DEBUG(if (!LoadPairs.empty()) {
                dbgs() << "Consecutive load pairs:\n";
                for (auto &MapIt : LoadPairs) {
                  LLVM_DEBUG(dbgs() << *MapIt.first << ", "
                             << *MapIt.second << "\n");
                }
              });
   return LoadPairs.size() > 1;
 }
 
-void ARMParallelDSP::CreateParallelMACPairs(Reduction &R) {
-  OpChainList &Candidates = R.MACCandidates;
-  PMACPairList &PMACPairs = R.PMACPairs;
-  const unsigned Elems = Candidates.size();
+// Loop Pass that needs to identify integer add/sub reductions of 16-bit vector
+// multiplications.
+// To use SMLAD:
+// 1) we first need to find integer add then look for this pattern:
+//
+// acc0 = ...
+// ld0 = load i16
+// sext0 = sext i16 %ld0 to i32
+// ld1 = load i16
+// sext1 = sext i16 %ld1 to i32
+// mul0 = mul %sext0, %sext1
+// ld2 = load i16
+// sext2 = sext i16 %ld2 to i32
+// ld3 = load i16
+// sext3 = sext i16 %ld3 to i32
+// mul1 = mul i32 %sext2, %sext3
+// add0 = add i32 %mul0, %acc0
+// acc1 = add i32 %add0, %mul1
+//
+// Which can be selected to:
+//
+// ldr r0
+// ldr r1
+// smlad r2, r0, r1, r2
+//
+// If constants are used instead of loads, these will need to be hoisted
+// out and into a register.
+//
+// If loop invariants are used instead of loads, these need to be packed
+// before the loop begins.
+//
+bool ARMParallelDSP::MatchSMLAD(Loop *L) {
+  // Search recursively back through the operands to find a tree of values that
+  // form a multiply-accumulate chain. The search records the Add and Mul
+  // instructions that form the reduction and allows us to find a single value
+  // to be used as the initial input to the accumlator.
+  std::function<bool(Value*, Reduction&)> Search = [&]
+    (Value *V, Reduction &R) -> bool {
+
+    // If we find a non-instruction, try to use it as the initial accumulator
+    // value. This may have already been found during the search in which case
+    // this function will return false, signaling a search fail.
+    auto *I = dyn_cast<Instruction>(V);
+    if (!I)
+      return R.InsertAcc(V);
 
-  if (Elems < 2)
-    return;
+    switch (I->getOpcode()) {
+    default:
+      break;
+    case Instruction::PHI:
+      // Could be the accumulator value.
+      return R.InsertAcc(V);
+    case Instruction::Add: {
+      // Adds should be adding together two muls, or another add and a mul to
+      // be within the mac chain. One of the operands may also be the
+      // accumulator value at which point we should stop searching.
+      bool ValidLHS = Search(I->getOperand(0), R);
+      bool ValidRHS = Search(I->getOperand(1), R);
+      if (!ValidLHS && !ValidLHS)
+        return false;
+      else if (ValidLHS && ValidRHS) {
+        R.InsertAdd(I);
+        return true;
+      } else {
+        R.InsertAdd(I);
+        return R.InsertAcc(I);
+      }
+    }
+    case Instruction::Mul: {
+      Value *MulOp0 = I->getOperand(0);
+      Value *MulOp1 = I->getOperand(1);
+      if (isa<SExtInst>(MulOp0) && isa<SExtInst>(MulOp1)) {
+        ValueList LHS;
+        ValueList RHS;
+        if (IsNarrowSequence<16>(MulOp0, LHS) &&
+            IsNarrowSequence<16>(MulOp1, RHS)) {
+          R.InsertMul(I, LHS, RHS);
+          return true;
+        }
+      }
+      return false;
+    }
+    case Instruction::SExt:
+      return Search(I->getOperand(0), R);
+    }
+    return false;
+  };
 
-  auto CanPair = [&](BinOpChain *PMul0, BinOpChain *PMul1) {
+  bool Changed = false;
+  SmallPtrSet<Instruction*, 4> AllAdds;
+  BasicBlock *Latch = L->getLoopLatch();
+
+  for (Instruction &I : reverse(*Latch)) {
+    if (I.getOpcode() != Instruction::Add)
+      continue;
+
+    if (AllAdds.count(&I))
+      continue;
+
+    const auto *Ty = I.getType();
+    if (!Ty->isIntegerTy(32) && !Ty->isIntegerTy(64))
+      continue;
+
+    Reduction R(&I);
+    if (!Search(&I, R))
+      continue;
+
+    if (!CreateParallelPairs(R))
+      continue;
+
+    InsertParallelMACs(R);
+    Changed = true;
+    AllAdds.insert(R.getAdds().begin(), R.getAdds().end());
+  }
+
+  return Changed;
+}
+
+bool ARMParallelDSP::CreateParallelPairs(Reduction &R) {
+
+  // Not enough mul operations to make a pair.
+  if (R.getMuls().size() < 2)
+    return false;
+
+  // Check that the muls operate directly upon sign extended loads.
+  for (auto &MulChain : R.getMuls()) {
+    // A mul has 2 operands, and a narrow op consist of sext and a load; thus
+    // we expect at least 4 items in this operand value list.
+    if (MulChain->size() < 4) {
+      LLVM_DEBUG(dbgs() << "Operand list too short.\n");
+      return false;
+    }
+    MulChain->PopulateLoads();
+    ValueList &LHS = static_cast<BinOpChain*>(MulChain.get())->LHS;
+    ValueList &RHS = static_cast<BinOpChain*>(MulChain.get())->RHS;
+
+    // Use +=2 to skip over the expected extend instructions.
+    for (unsigned i = 0, e = LHS.size(); i < e; i += 2) {
+      if (!isa<LoadInst>(LHS[i]) || !isa<LoadInst>(RHS[i]))
+        return false;
+    }
+  }
+
+  auto CanPair = [&](Reduction &R, BinOpChain *PMul0, BinOpChain *PMul1) {
     if (!PMul0->AreSymmetrical(PMul1))
       return false;
 
     // The first elements of each vector should be loads with sexts. If we
     // find that its two pairs of consecutive loads, then these can be
     // transformed into two wider loads and the users can be replaced with
     // DSP intrinsics.
     for (unsigned x = 0; x < PMul0->LHS.size(); x += 2) {
for (unsigned x = 0; x < PMul0->LHS.size(); x += 2) {
                  << " - " << *Ld0 << "\n"
                  << " - " << *Ld1 << "\n"
                  << " - " << *Ld2 << "\n"
                  << " - " << *Ld3 << "\n");
 
       if (AreSequentialLoads(Ld0, Ld1, PMul0->VecLd)) {
         if (AreSequentialLoads(Ld2, Ld3, PMul1->VecLd)) {
           LLVM_DEBUG(dbgs() << "OK: found two pairs of parallel loads!\n");
-          PMACPairs.push_back(std::make_pair(PMul0, PMul1));
+          R.AddMulPair(PMul0, PMul1);
           return true;
         } else if (AreSequentialLoads(Ld3, Ld2, PMul1->VecLd)) {
           LLVM_DEBUG(dbgs() << "OK: found two pairs of parallel loads!\n");
           LLVM_DEBUG(dbgs() << "    exchanging Ld2 and Ld3\n");
           PMul1->Exchange = true;
-          PMACPairs.push_back(std::make_pair(PMul0, PMul1));
+          R.AddMulPair(PMul0, PMul1);
           return true;
         }
       } else if (AreSequentialLoads(Ld1, Ld0, PMul0->VecLd) &&
                  AreSequentialLoads(Ld2, Ld3, PMul1->VecLd)) {
         LLVM_DEBUG(dbgs() << "OK: found two pairs of parallel loads!\n");
         LLVM_DEBUG(dbgs() << "    exchanging Ld0 and Ld1\n");
         LLVM_DEBUG(dbgs() << "    and swapping muls\n");
         PMul0->Exchange = true;
         // Only the second operand can be exchanged, so swap the muls.
-        PMACPairs.push_back(std::make_pair(PMul1, PMul0));
+        R.AddMulPair(PMul1, PMul0);
         return true;
       }
     }
     return false;
   };
 
+  OpChainList &Muls = R.getMuls();
+  const unsigned Elems = Muls.size();
   SmallPtrSet<const Instruction*, 4> Paired;
   for (unsigned i = 0; i < Elems; ++i) {
-    BinOpChain *PMul0 = static_cast<BinOpChain*>(Candidates[i].get());
+    BinOpChain *PMul0 = static_cast<BinOpChain*>(Muls[i].get());
     if (Paired.count(PMul0->Root))
       continue;
 
     for (unsigned j = 0; j < Elems; ++j) {
       if (i == j)
         continue;
 
-      BinOpChain *PMul1 = static_cast<BinOpChain*>(Candidates[j].get());
+      BinOpChain *PMul1 = static_cast<BinOpChain*>(Muls[j].get());
       if (Paired.count(PMul1->Root))
         continue;
 
       const Instruction *Mul0 = PMul0->Root;
       const Instruction *Mul1 = PMul1->Root;
       if (Mul0 == Mul1)
         continue;
 
       assert(PMul0 != PMul1 && "expected different chains");
 
-      if (CanPair(PMul0, PMul1)) {
+      if (CanPair(R, PMul0, PMul1)) {
         Paired.insert(Mul0);
         Paired.insert(Mul1);
         break;
       }
     }
   }
+  return !R.getMulPairs().empty();
 }
 
-bool ARMParallelDSP::InsertParallelMACs(Reduction &Reduction) {
-  Instruction *Acc = Reduction.Phi;
-  Instruction *InsertAfter = Reduction.AccIntAdd;
-
-  for (auto &Pair : Reduction.PMACPairs) {
-    BinOpChain *PMul0 = Pair.first;
-    BinOpChain *PMul1 = Pair.second;
-    LLVM_DEBUG(dbgs() << "Found parallel MACs:\n"
-               << "- " << *PMul0->Root << "\n"
-               << "- " << *PMul1->Root << "\n");
-
-    Acc = CreateSMLADCall(PMul0->VecLd, PMul1->VecLd, Acc, PMul1->Exchange,
-                          InsertAfter);
-    InsertAfter = Acc;
-  }
-
-  if (Acc != Reduction.Phi) {
-    LLVM_DEBUG(dbgs() << "Replace Accumulate: "; Acc->dump());
-    Reduction.AccIntAdd->replaceAllUsesWith(Acc);
-    return true;
-  }
-  return false;
-}
-
-template<typename InstType, unsigned BitWidth>
-bool IsExtendingLoad(Value *V) {
-  auto *I = dyn_cast<InstType>(V);
-  if (!I)
-    return false;
-
-  if (I->getSrcTy()->getIntegerBitWidth() != BitWidth)
-    return false;
-
-  return isa<LoadInst>(I->getOperand(0));
-}
 
-static void MatchParallelMACSequences(Reduction &R,
-                                      OpChainList &Candidates) {
-  Instruction *Acc = R.AccIntAdd;
-  LLVM_DEBUG(dbgs() << "\n- Analysing:\t" << *Acc << "\n");
+void ARMParallelDSP::InsertParallelMACs(Reduction &R) {
 
-  // Returns false to signal the search should be stopped.
-  std::function<bool(Value*)> Match =
-    [&Candidates, &Match](Value *V) -> bool {
+  auto CreateSMLADCall = [&](SmallVectorImpl<LoadInst*> &VecLd0,
+                             SmallVectorImpl<LoadInst*> &VecLd1,
+                             Value *Acc, bool Exchange,
+                             Instruction *InsertAfter) {
+    // Replace the reduction chain with an intrinsic call
+    IntegerType *Ty = IntegerType::get(M->getContext(), 32);
+    LoadInst *WideLd0 = WideLoads.count(VecLd0[0]) ?
+      WideLoads[VecLd0[0]]->getLoad() : CreateWideLoad(VecLd0, Ty);
+    LoadInst *WideLd1 = WideLoads.count(VecLd1[0]) ?
+      WideLoads[VecLd1[0]]->getLoad() : CreateWideLoad(VecLd1, Ty);
 
-    auto *I = dyn_cast<Instruction>(V);
-    if (!I)
-      return false;
+    Value* Args[] = { WideLd0, WideLd1, Acc };
+    Function *SMLAD = nullptr;
+    if (Exchange)
+      SMLAD = Acc->getType()->isIntegerTy(32) ?
+        Intrinsic::getDeclaration(M, Intrinsic::arm_smladx) :
+        Intrinsic::getDeclaration(M, Intrinsic::arm_smlaldx);
+    else
+      SMLAD = Acc->getType()->isIntegerTy(32) ?
+        Intrinsic::getDeclaration(M, Intrinsic::arm_smlad) :
+        Intrinsic::getDeclaration(M, Intrinsic::arm_smlald);
 
-    switch (I->getOpcode()) {
-    case Instruction::Add:
-      if (Match(I->getOperand(0)) || (Match(I->getOperand(1))))
-        return true;
-      break;
-    case Instruction::Mul: {
-      Value *Op0 = I->getOperand(0);
-      Value *Op1 = I->getOperand(1);
-      if (IsExtendingLoad<SExtInst, 16>(Op0) &&
-          IsExtendingLoad<SExtInst, 16>(Op1)) {
-        ValueList LHS = { cast<SExtInst>(Op0)->getOperand(0), Op0 };
-        ValueList RHS = { cast<SExtInst>(Op1)->getOperand(0), Op1 };
-        Candidates.push_back(make_unique<BinOpChain>(I, LHS, RHS));
-      }
-      return false;
-    }
-    case Instruction::SExt:
-      return Match(I->getOperand(0));
-    }
-    return false;
+    IRBuilder<NoFolder> Builder(InsertAfter->getParent(),
+                                ++BasicBlock::iterator(InsertAfter));
+    Instruction *Call = Builder.CreateCall(SMLAD, Args);
+    NumSMLAD++;
+    return Call;
   };
 
-  while (Match (Acc));
-  LLVM_DEBUG(dbgs() << "Finished matching MAC sequences, found "
-             << Candidates.size() << " candidates.\n");
-}
-
-static bool CheckMACMemory(OpChainList &Candidates) {
-  for (auto &C : Candidates) {
-    // A mul has 2 operands, and a narrow op consist of sext and a load; thus
-    // we expect at least 4 items in this operand value list.
-    if (C->size() < 4) {
-      LLVM_DEBUG(dbgs() << "Operand list too short.\n");
-      return false;
-    }
-    C->PopulateLoads();
-    ValueList &LHS = static_cast<BinOpChain*>(C.get())->LHS;
-    ValueList &RHS = static_cast<BinOpChain*>(C.get())->RHS;
-
-    // Use +=2 to skip over the expected extend instructions.
-    for (unsigned i = 0, e = LHS.size(); i < e; i += 2) {
-      if (!isa<LoadInst>(LHS[i]) || !isa<LoadInst>(RHS[i]))
-        return false;
-    }
-  }
-  return true;
-}
-
-// Loop Pass that needs to identify integer add/sub reductions of 16-bit vector
-// multiplications.
-// To use SMLAD:
-// 1) we first need to find integer add reduction PHIs,
-// 2) then from the PHI, look for this pattern:
-//
-// acc0 = phi i32 [0, %entry], [%acc1, %loop.body]
-// ld0 = load i16
-// sext0 = sext i16 %ld0 to i32
-// ld1 = load i16
-// sext1 = sext i16 %ld1 to i32
-// mul0 = mul %sext0, %sext1
-// ld2 = load i16
-// sext2 = sext i16 %ld2 to i32
-// ld3 = load i16
-// sext3 = sext i16 %ld3 to i32
-// mul1 = mul i32 %sext2, %sext3
-// add0 = add i32 %mul0, %acc0
-// acc1 = add i32 %add0, %mul1
-//
-// Which can be selected to:
-//
-// ldr.h r0
-// ldr.h r1
-// smlad r2, r0, r1, r2
-//
-// If constants are used instead of loads, these will need to be hoisted
-// out and into a register.
-//
-// If loop invariants are used instead of loads, these need to be packed
-// before the loop begins.
-//
-bool ARMParallelDSP::MatchSMLAD(Function &F) {
-
-  auto FindReductions = [&](ReductionList &Reductions) {
-    RecurrenceDescriptor RecDesc;
-    const bool HasFnNoNaNAttr =
-      F.getFnAttribute("no-nans-fp-math").getValueAsString() == "true";
-    BasicBlock *Latch = L->getLoopLatch();
-
-    for (PHINode &Phi : Latch->phis()) {
-      const auto *Ty = Phi.getType();
-      if (!Ty->isIntegerTy(32) && !Ty->isIntegerTy(64))
-        continue;
-
-      const bool IsReduction = RecurrenceDescriptor::AddReductionVar(
-        &Phi, RecurrenceDescriptor::RK_IntegerAdd, L, HasFnNoNaNAttr, RecDesc);
-
-      if (!IsReduction)
-        continue;
-
-      Instruction *Acc = dyn_cast<Instruction>(Phi.getIncomingValueForBlock(Latch));
-      if (!Acc)
-        continue;
-
-      Reductions.push_back(Reduction(&Phi, Acc));
-    }
-    return !Reductions.empty();
-  };
+  Instruction *InsertAfter = R.getRoot();
+  Value *Acc = R.getAccumulator();
+    Acc = ConstantInt::get(IntegerType::get(M->getContext(), 32), 0);
 
-  ReductionList Reductions;
-  if (!FindReductions(Reductions))
-    return false;
-
-  for (auto &R : Reductions) {
-    OpChainList MACCandidates;
-    MatchParallelMACSequences(R, MACCandidates);
-    if (!CheckMACMemory(MACCandidates))
-      continue;
-
-    R.MACCandidates = std::move(MACCandidates);
-
-    LLVM_DEBUG(dbgs() << "MAC candidates:\n";
-      for (auto &M : R.MACCandidates)
-        M->Root->dump();
-      dbgs() << "\n";);
-  }
+  LLVM_DEBUG(dbgs() << "Root: " << *InsertAfter << "\n"
+             << "Acc: " << *Acc << "\n");
+  for (auto &Pair : R.getMulPairs()) {
+    BinOpChain *PMul0 = Pair.first;
+    BinOpChain *PMul1 = Pair.second;
+    LLVM_DEBUG(dbgs() << "Muls:\n"
+               << "- " << *PMul0->Root << "\n"
+               << "- " << *PMul1->Root << "\n");
 
-  bool Changed = false;
-  // Check whether statements in the basic block that write to memory alias
-  // with the memory locations accessed by the MAC-chains.
-  for (auto &R : Reductions) {
-    CreateParallelMACPairs(R);
-    Changed |= InsertParallelMACs(R);
+    Acc = CreateSMLADCall(PMul0->VecLd, PMul1->VecLd, Acc, PMul1->Exchange,
+                          InsertAfter);
+    InsertAfter = cast<Instruction>(Acc);
   }
-
-  return Changed;
+  R.UpdateRoot(cast<Instruction>(Acc));
 }
 
 LoadInst* ARMParallelDSP::CreateWideLoad(SmallVectorImpl<LoadInst*> &Loads,
                                          IntegerType *LoadTy) {
   assert(Loads.size() == 2 && "currently only support widening two loads");
 
   LoadInst *Base = Loads[0];
   LoadInst *Offset = Loads[1];
LoadInst* ARMParallelDSP::CreateWideLoad(SmallVectorImpl<LoadInst*> &Loads,
   Value *Trunc = IRB.CreateTrunc(Top, OffsetTy);
   OffsetSExt->setOperand(0, Trunc);
 
   WideLoads.emplace(std::make_pair(Base,
                                    make_unique<WidenedLoad>(Loads, WideLoad)));
   return WideLoad;
 }
 
-Instruction *ARMParallelDSP::CreateSMLADCall(SmallVectorImpl<LoadInst*> &VecLd0,
-                                             SmallVectorImpl<LoadInst*> &VecLd1,
-                                             Instruction *Acc, bool Exchange,
-                                             Instruction *InsertAfter) {
-  LLVM_DEBUG(dbgs() << "Create SMLAD intrinsic using:\n"
-             << "- " << *VecLd0[0] << "\n"
-             << "- " << *VecLd0[1] << "\n"
-             << "- " << *VecLd1[0] << "\n"
-             << "- " << *VecLd1[1] << "\n"
-             << "- " << *Acc << "\n"
-             << "- Exchange: " << Exchange << "\n");
-
-  // Replace the reduction chain with an intrinsic call
-  IntegerType *Ty = IntegerType::get(M->getContext(), 32);
-  LoadInst *WideLd0 = WideLoads.count(VecLd0[0]) ?
-    WideLoads[VecLd0[0]]->getLoad() : CreateWideLoad(VecLd0, Ty);
-  LoadInst *WideLd1 = WideLoads.count(VecLd1[0]) ?
-    WideLoads[VecLd1[0]]->getLoad() : CreateWideLoad(VecLd1, Ty);
-
-  Value* Args[] = { WideLd0, WideLd1, Acc };
-  Function *SMLAD = nullptr;
-  if (Exchange)
-    SMLAD = Acc->getType()->isIntegerTy(32) ?
-      Intrinsic::getDeclaration(M, Intrinsic::arm_smladx) :
-      Intrinsic::getDeclaration(M, Intrinsic::arm_smlaldx);
-  else
-    SMLAD = Acc->getType()->isIntegerTy(32) ?
-      Intrinsic::getDeclaration(M, Intrinsic::arm_smlad) :
-      Intrinsic::getDeclaration(M, Intrinsic::arm_smlald);
-
-  IRBuilder<NoFolder> Builder(InsertAfter->getParent(),
-                              ++BasicBlock::iterator(InsertAfter));
-  CallInst *Call = Builder.CreateCall(SMLAD, Args);
-  NumSMLAD++;
-  return Call;
-}
-
 // Compare the value lists in Other to this chain.
 bool BinOpChain::AreSymmetrical(BinOpChain *Other) {
   // Element-by-element comparison of Value lists returning true if they are
   // instructions with the same opcode or constants with the same value.
   auto CompareValueList = [](const ValueList &VL0,
                              const ValueList &VL1) {
     if (VL0.size() != VL1.size()) {
       LLVM_DEBUG(dbgs() << "Muls are mismatching operand list lengths: "

test/CodeGen/ARM/ParallelDSP/aliasing.ll

for.body:
   %conv8 = sext i16 %1 to i32
   %mul9 = mul nsw i32 %conv7, %conv8
   %add10 = add i32 %mul, %mac1.026
   %add11 = add i32 %mul9, %add10
   %exitcond = icmp ne i32 %add, %arg
   br i1 %exitcond, label %for.body, label %for.cond.cleanup
 }
 
+; TODO: I think we should be able to generate one smlad here. The search fails
+; when it finds the alias.
 ; CHECK-LABEL: one_pair_alias
-; FIXME: This tests shows we have a bug with smlad insertion
+; CHECK-NOT: call i32 @llvm.arm.smlad
 define i32 @one_pair_alias(i16* noalias nocapture readonly %b, i16* noalias nocapture readonly %c) {
 entry:
   br label %for.body
 
 for.cond.cleanup:                                 ; preds = %for.body
   ret i32 %add26
 
 for.body:                                         ; preds = %for.body, %entry

test/CodeGen/ARM/ParallelDSP/inner-full-unroll.ll

+; RUN: opt -mtriple=thumbv7em -arm-parallel-dsp -dce -S %s -o - | FileCheck %s
+
+; CHECK-LABEL: full_unroll
+; CHECK: [[IV:%[^ ]+]] = phi i32
+; CHECK: [[AI:%[^ ]+]] = getelementptr inbounds i32, i32* %a, i32 [[IV]]
+; CHECK: [[BI:%[^ ]+]] = getelementptr inbounds i16*, i16** %b, i32 [[IV]]
+; CHECK: [[BIJ:%[^ ]+]] = load i16*, i16** %arrayidx5, align 4
+; CHECK: [[CI:%[^ ]+]] = getelementptr inbounds i16*, i16** %c, i32 [[IV]]
+; CHECK: [[CIJ:%[^ ]+]] = load i16*, i16** [[CI]], align 4
+; CHECK: [[BIJ_CAST:%[^ ]+]] = bitcast i16* [[BIJ]] to i32*
+; CHECK: [[BIJ_LD:%[^ ]+]] = load i32, i32* [[BIJ_CAST]], align 2
+; CHECK: [[CIJ_CAST:%[^ ]+]] = bitcast i16* [[CIJ]] to i32*
+; CHECK: [[CIJ_LD:%[^ ]+]] = load i32, i32* [[CIJ_CAST]], align 2
+; CHECK: [[BIJ_2:%[^ ]+]] = getelementptr inbounds i16, i16* [[BIJ]], i32 2
+; CHECK: [[BIJ_2_CAST:%[^ ]+]] = bitcast i16* [[BIJ_2]] to i32*
+; CHECK: [[BIJ_2_LD:%[^ ]+]] = load i32, i32* [[BIJ_2_CAST]], align 2
+; CHECK: [[CIJ_2:%[^ ]+]] = getelementptr inbounds i16, i16* [[CIJ]], i32 2
+; CHECK: [[CIJ_2_CAST:%[^ ]+]] = bitcast i16* [[CIJ_2]] to i32*
+; CHECK: [[CIJ_2_LD:%[^ ]+]] = load i32, i32* [[CIJ_2_CAST]], align 2
+; CHECK: [[SMLAD0:%[^ ]+]] = call i32 @llvm.arm.smlad(i32 [[CIJ_2_LD]], i32 [[BIJ_2_LD]], i32 0)
+; CHECK: [[SMLAD1:%[^ ]+]] = call i32 @llvm.arm.smlad(i32 [[CIJ_LD]], i32 [[BIJ_LD]], i32 [[SMLAD0]])
+; CHECK: store i32 [[SMLAD1]], i32* %arrayidx, align 4
+
+define void @full_unroll(i32* noalias nocapture %a, i16** noalias nocapture readonly %b, i16** noalias nocapture readonly %c, i32 %N) {
+entry:
+  %cmp29 = icmp eq i32 %N, 0
+  br i1 %cmp29, label %for.cond.cleanup, label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body, %entry
+  ret void
+
+for.body:                                         ; preds = %entry, %for.body
+  %i.030 = phi i32 [ %inc12, %for.body ], [ 0, %entry ]
+  %arrayidx = getelementptr inbounds i32, i32* %a, i32 %i.030
+  %arrayidx5 = getelementptr inbounds i16*, i16** %b, i32 %i.030
+  %0 = load i16*, i16** %arrayidx5, align 4
+  %arrayidx7 = getelementptr inbounds i16*, i16** %c, i32 %i.030
+  %1 = load i16*, i16** %arrayidx7, align 4
+  %2 = load i16, i16* %0, align 2
+  %conv = sext i16 %2 to i32
+  %3 = load i16, i16* %1, align 2
+  %conv9 = sext i16 %3 to i32
+  %mul = mul nsw i32 %conv9, %conv
+  %arrayidx6.1 = getelementptr inbounds i16, i16* %0, i32 1
+  %4 = load i16, i16* %arrayidx6.1, align 2
+  %conv.1 = sext i16 %4 to i32
+  %arrayidx8.1 = getelementptr inbounds i16, i16* %1, i32 1
+  %5 = load i16, i16* %arrayidx8.1, align 2
+  %conv9.1 = sext i16 %5 to i32
+  %mul.1 = mul nsw i32 %conv9.1, %conv.1
+  %add.1 = add nsw i32 %mul.1, %mul
+  %arrayidx6.2 = getelementptr inbounds i16, i16* %0, i32 2
+  %6 = load i16, i16* %arrayidx6.2, align 2
+  %conv.2 = sext i16 %6 to i32
+  %arrayidx8.2 = getelementptr inbounds i16, i16* %1, i32 2
+  %7 = load i16, i16* %arrayidx8.2, align 2
+  %conv9.2 = sext i16 %7 to i32
+  %mul.2 = mul nsw i32 %conv9.2, %conv.2
+  %add.2 = add nsw i32 %mul.2, %add.1
+  %arrayidx6.3 = getelementptr inbounds i16, i16* %0, i32 3
+  %8 = load i16, i16* %arrayidx6.3, align 2
+  %conv.3 = sext i16 %8 to i32
+  %arrayidx8.3 = getelementptr inbounds i16, i16* %1, i32 3
+  %9 = load i16, i16* %arrayidx8.3, align 2
+  %conv9.3 = sext i16 %9 to i32
+  %mul.3 = mul nsw i32 %conv9.3, %conv.3
+  %add.3 = add nsw i32 %mul.3, %add.2
+  store i32 %add.3, i32* %arrayidx, align 4
+  %inc12 = add nuw i32 %i.030, 1
+  %exitcond = icmp eq i32 %inc12, %N
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+}
+
+; CHECK-LABEL: full_unroll_sub
+; CHEC: [[IV:%[^ ]+]] = phi i32
+; CHECK: [[AI:%[^ ]+]] = getelementptr inbounds i32, i32* %a, i32 [[IV]]
+; CHECK: [[BI:%[^ ]+]] = getelementptr inbounds i16*, i16** %b, i32 [[IV]]
+; CHECK: [[BIJ:%[^ ]+]] = load i16*, i16** [[BI]], align 4
+; CHECK: [[CI:%[^ ]+]] = getelementptr inbounds i16*, i16** %c, i32 [[IV]]
+; CHECK: [[CIJ:%[^ ]+]] = load i16*, i16** [[CI]], align 4
+; CHECK: [[BIJ_LD:%[^ ]+]] = load i16, i16* [[BIJ]], align 2
+; CHECK: [[BIJ_LD_SXT:%[^ ]+]] = sext i16 [[BIJ_LD]] to i32
+; CHECK: [[CIJ_LD:%[^ ]+]] = load i16, i16* [[CIJ]], align 2
+; CHECK: [[CIJ_LD_SXT:%[^ ]+]] = sext i16 [[CIJ_LD]] to i32
+; CHECK: [[SUB:%[^ ]+]] = sub nsw i32 [[CIJ_LD_SXT]], [[BIJ_LD_SXT]]
+; CHECK: [[BIJ_1:%[^ ]+]] = getelementptr inbounds i16, i16* [[BIJ]], i32 1
+; CHECK: [[BIJ_1_LD:%[^ ]+]] = load i16, i16* [[BIJ_1]], align 2
+; CHECK: [[BIJ_1_LD_SXT:%[^ ]+]] = sext i16 [[BIJ_1_LD]] to i32
+; CHECK: [[CIJ_1:%[^ ]+]] = getelementptr inbounds i16, i16* [[CIJ]], i32 1
+; CHECK: [[CIJ_1_LD:%[^ ]+]] = load i16, i16* [[CIJ_1]], align 2
+; CHECK: [[CIJ_1_LD_SXT:%[^ ]+]] = sext i16 [[CIJ_1_LD]] to i32
+; CHECK: [[MUL:%[^ ]+]] = mul nsw i32 [[CIJ_1_LD_SXT]], [[BIJ_1_LD_SXT]]
+; CHECK: [[ACC:%[^ ]+]] = add nsw i32 [[MUL]], [[SUB]]
+; CHECK: [[BIJ_2:%[^ ]+]] = getelementptr inbounds i16, i16* [[BIJ]], i32 2
+; CHECK: [[BIJ_2_CAST:%[^ ]+]] = bitcast i16* [[BIJ_2]] to i32*
+; CHECK: [[BIJ_2_LD:%[^ ]+]] = load i32, i32* [[BIJ_2_CAST]], align 2
+; CHECK: [[CIJ_2:%[^ ]+]] = getelementptr inbounds i16, i16* [[CIJ]], i32 2
+; CHECK: [[CIJ_2_CAST:%[^ ]+]] = bitcast i16* [[CIJ_2]] to i32*
+; CHECK: [[CIJ_2_LD:%[^ ]+]] = load i32, i32* [[CIJ_2_CAST]], align 2
+; CHECK: [[SMLAD0:%[^ ]+]] = call i32 @llvm.arm.smlad(i32 [[CIJ_2_LD]], i32 [[BIJ_2_LD]], i32 [[ACC]])
+; CHECK: store i32 [[SMLAD0]], i32* %arrayidx, align 4
+
+define void @full_unroll_sub(i32* noalias nocapture %a, i16** noalias nocapture readonly %b, i16** noalias nocapture readonly %c, i32 %N) {
+entry:
+  %cmp29 = icmp eq i32 %N, 0
+  br i1 %cmp29, label %for.cond.cleanup, label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body, %entry
+  ret void
+
+for.body:                                         ; preds = %entry, %for.body
+  %i.030 = phi i32 [ %inc12, %for.body ], [ 0, %entry ]
+  %arrayidx = getelementptr inbounds i32, i32* %a, i32 %i.030
+  %arrayidx5 = getelementptr inbounds i16*, i16** %b, i32 %i.030
+  %0 = load i16*, i16** %arrayidx5, align 4
+  %arrayidx7 = getelementptr inbounds i16*, i16** %c, i32 %i.030
+  %1 = load i16*, i16** %arrayidx7, align 4
+  %2 = load i16, i16* %0, align 2
+  %conv = sext i16 %2 to i32
+  %3 = load i16, i16* %1, align 2
+  %conv9 = sext i16 %3 to i32
+  %sub = sub nsw i32 %conv9, %conv
+  %arrayidx6.1 = getelementptr inbounds i16, i16* %0, i32 1
+  %4 = load i16, i16* %arrayidx6.1, align 2
+  %conv.1 = sext i16 %4 to i32
+  %arrayidx8.1 = getelementptr inbounds i16, i16* %1, i32 1
+  %5 = load i16, i16* %arrayidx8.1, align 2
+  %conv9.1 = sext i16 %5 to i32
+  %mul.1 = mul nsw i32 %conv9.1, %conv.1
+  %add.1 = add nsw i32 %mul.1, %sub
+  %arrayidx6.2 = getelementptr inbounds i16, i16* %0, i32 2
+  %6 = load i16, i16* %arrayidx6.2, align 2
+  %conv.2 = sext i16 %6 to i32
+  %arrayidx8.2 = getelementptr inbounds i16, i16* %1, i32 2
+  %7 = load i16, i16* %arrayidx8.2, align 2
+  %conv9.2 = sext i16 %7 to i32
+  %mul.2 = mul nsw i32 %conv9.2, %conv.2
+  %add.2 = add nsw i32 %mul.2, %add.1
+  %arrayidx6.3 = getelementptr inbounds i16, i16* %0, i32 3
+  %8 = load i16, i16* %arrayidx6.3, align 2
+  %conv.3 = sext i16 %8 to i32
+  %arrayidx8.3 = getelementptr inbounds i16, i16* %1, i32 3
+  %9 = load i16, i16* %arrayidx8.3, align 2
+  %conv9.3 = sext i16 %9 to i32
+  %mul.3 = mul nsw i32 %conv9.3, %conv.3
+  %add.3 = add nsw i32 %mul.3, %add.2
+  store i32 %add.3, i32* %arrayidx, align 4
+  %inc12 = add nuw i32 %i.030, 1
+  %exitcond = icmp eq i32 %inc12, %N
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+}