[ARM] ParallelDSP reorganisation

[samparker]

Summary

In preparing to allow ARMParallelDSP pass to parallelise more than
smlads, I've restructed some elements:

- The ParallelMAC struct has been renamed to BinOpChain.
- The BinOpChain struct holds two value lists: LHS and RHS, as well
  as inheriting from the OpChain base class.
- The OpChain struct holds all the values of the represented chain
  and has had the memory locations functionality inserted into it.
- ParallelMACList becomes OpChainList and it now holds pointers instead
  of objects.

[samparker]

lib/Target/ARM/ARMParallelDSP.cpp

599–601

I'm supposed to have a loop deleting the candidates here...

[samparker]

Added loop to destroy the MACCandidates.

[samparker]

Combined changes from D48972 and performed a rebase.

[SjoerdMeijer]

LGTM

lib/Target/ARM/ARMParallelDSP.cpp

 #include "ARMSubtarget.h"
 
 using namespace llvm;
 using namespace PatternMatch;
 
 #define DEBUG_TYPE "parallel-dsp"
 
 namespace {
+  struct OpChain;
   struct BinOpChain;
   struct Reduction;
 
-  using BinOpChainList = SmallVector<BinOpChain, 8>;
+  using OpChainList     = SmallVector<OpChain*, 8>;
   using ReductionList   = SmallVector<Reduction, 8>;
-  using ValueList       = SmallVector<Value*, 8>;
+  using ValueList       = SmallSetVector<Value*, 8>;
   using MemInstList     = SmallVector<Instruction*, 8>;
   using PMACPair        = std::pair<BinOpChain*,BinOpChain*>;
   using PMACPairList    = SmallVector<PMACPair, 8>;
   using Instructions    = SmallVector<Instruction*,16>;
   using MemLocList      = SmallVector<MemoryLocation, 4>;
 
+  struct OpChain {
+    Instruction   *Root;
+    ValueList     AllValues;
+    MemInstList   VecLd;    // List of all load instructions.
+    MemLocList    MemLocs;  // All memory locations read by this tree.
+    OpChain(Instruction *I, ValueList &vl) : Root(I), AllValues(vl) { }
+
+    void SetMemoryLocations() {
+      const auto Size = MemoryLocation::UnknownSize;
+      for (auto V : AllValues)
+        if (auto *Ld = dyn_cast<LoadInst>(V))
+          MemLocs.push_back(MemoryLocation(Ld->getPointerOperand(), Size));
+    }
+
+    bool contains(Value *V) {
+      if (V == Root)
+        return true;
+      return AllValues.count(V) != 0;
+    }
+
+    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.
-  struct BinOpChain {
-    Instruction   *Root;
+  struct BinOpChain : public OpChain {
     ValueList     LHS;      // List of all (narrow) left hand operands.
     ValueList     RHS;      // List of all (narrow) right hand operands.
-    MemInstList   VecLd;    // List of all load instructions.
-    MemLocList    MemLocs;  // All memory locations read by this tree.
 
     BinOpChain(Instruction *I, ValueList &lhs, ValueList &rhs) :
-      Root(I), LHS(lhs), RHS(rhs) {};
+      OpChain(I, lhs), LHS(lhs), RHS(rhs) {
+        AllValues.insert(RHS.begin(), RHS.end());
+      }
   };
 
   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.
 
     Reduction (PHINode *P, Instruction *Acc) : Phi(P), AccIntAdd(Acc) { };
   };
 
   class ARMParallelDSP : public LoopPass {
     ScalarEvolution   *SE;
     AliasAnalysis     *AA;
     TargetLibraryInfo *TLI;
     DominatorTree     *DT;
     LoopInfo          *LI;
     Loop              *L;
     const DataLayout  *DL;
     Module            *M;
 
     bool InsertParallelMACs(Reduction &Reduction, PMACPairList &PMACPairs);
     bool AreSequentialLoads(LoadInst *Ld0, LoadInst *Ld1, MemInstList &VecMem);
-    PMACPairList CreateParallelMACPairs(BinOpChainList &Candidates);
+    PMACPairList CreateParallelMACPairs(OpChainList &Candidates);
     Instruction *CreateSMLADCall(LoadInst *VecLd0, LoadInst *VecLd1,
                                  Instruction *Acc, Instruction *InsertAfter);
 
     /// 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.
if (match(V, m_Trunc(m_Value(Val)))) {
     if (cast<CastInst>(I)->getSrcTy()->getIntegerBitWidth() != MaxBitWidth) {
       LLVM_DEBUG(dbgs() << "No, wrong SrcTy size: " <<
         cast<CastInst>(I)->getSrcTy()->getIntegerBitWidth() << "\n");
       return false;
     }
 
     if (match(Val, m_Load(m_Value()))) {
       LLVM_DEBUG(dbgs() << "Yes, found narrow Load:\t"; Val->dump());
-      VL.push_back(Val);
-      VL.push_back(I);
+      VL.insert(Val);
+      VL.insert(I);
       return true;
     }
   }
   LLVM_DEBUG(dbgs() << "No, unsupported Op:\t"; I->dump());
   return false;
 }
 
 // Element-by-element comparison of Value lists returning true if they are
if (!Ld0->hasOneUse() || !Ld1->hasOneUse()) {
     LLVM_DEBUG(dbgs() << "No, load has more than one use.\n");
     return false;
   }
 
   return AreSequentialAccesses<LoadInst>(Ld0, Ld1, VecMem, *DL, *SE);
 }
 
 PMACPairList
-ARMParallelDSP::CreateParallelMACPairs(BinOpChainList &Candidates) {
+ARMParallelDSP::CreateParallelMACPairs(OpChainList &Candidates) {
   const unsigned Elems = Candidates.size();
   PMACPairList PMACPairs;
 
   if (Elems < 2)
     return PMACPairs;
 
   // TODO: for now we simply try to match consecutive pairs i and i+1.
   // We can compare all elements, but then we need to compare and evaluate
   // different solutions.
   for(unsigned i=0; i<Elems-1; i+=2) {
-    BinOpChain &PMul0 = Candidates[i];
-    BinOpChain &PMul1 = Candidates[i+1];
-    const Instruction *Mul0 = PMul0.Root;
-    const Instruction *Mul1 = PMul1.Root;
+    BinOpChain *PMul0 = static_cast<BinOpChain*>(Candidates[i]);
+    BinOpChain *PMul1 = static_cast<BinOpChain*>(Candidates[i+1]);
+    const Instruction *Mul0 = PMul0->Root;
+    const Instruction *Mul1 = PMul1->Root;
 
     if (Mul0 == Mul1)
       continue;
 
     LLVM_DEBUG(dbgs() << "\nCheck parallel muls:\n";
                dbgs() << "- "; Mul0->dump();
                dbgs() << "- "; Mul1->dump());
 
-    const ValueList &Mul0_LHS = PMul0.LHS;
-    const ValueList &Mul0_RHS = PMul0.RHS;
-    const ValueList &Mul1_LHS = PMul1.LHS;
-    const ValueList &Mul1_RHS = PMul1.RHS;
+    const ValueList &Mul0_LHS = PMul0->LHS;
+    const ValueList &Mul0_RHS = PMul0->RHS;
+    const ValueList &Mul1_LHS = PMul1->LHS;
+    const ValueList &Mul1_RHS = PMul1->RHS;
 
     if (!AreSymmetrical(Mul0_LHS, Mul1_LHS) ||
         !AreSymmetrical(Mul0_RHS, Mul1_RHS))
       continue;
 
     LLVM_DEBUG(dbgs() << "OK: mul operands list match:\n");
     // 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 < Mul0_LHS.size(); x += 2) {
       auto *Ld0 = dyn_cast<LoadInst>(Mul0_LHS[x]);
       auto *Ld1 = dyn_cast<LoadInst>(Mul1_LHS[x]);
       auto *Ld2 = dyn_cast<LoadInst>(Mul0_RHS[x]);
       auto *Ld3 = dyn_cast<LoadInst>(Mul1_RHS[x]);
 
       LLVM_DEBUG(dbgs() << "Looking at operands " << x << ":\n";
                  dbgs() << "\t mul1: "; Mul0_LHS[x]->dump();
                  dbgs() << "\t mul2: "; Mul1_LHS[x]->dump();
                  dbgs() << "and operands " << x + 2 << ":\n";
                  dbgs() << "\t mul1: "; Mul0_RHS[x]->dump();
                  dbgs() << "\t mul2: "; Mul1_RHS[x]->dump());
 
-      if (AreSequentialLoads(Ld0, Ld1, Candidates[i].VecLd) &&
-          AreSequentialLoads(Ld2, Ld3, Candidates[i+1].VecLd)) {
+      if (AreSequentialLoads(Ld0, Ld1, PMul0->VecLd) &&
+          AreSequentialLoads(Ld2, Ld3, PMul1->VecLd)) {
         LLVM_DEBUG(dbgs() << "OK: found two pairs of parallel loads!\n");
-        PMACPairs.push_back(std::make_pair(&PMul0, &PMul1));
+        PMACPairs.push_back(std::make_pair(PMul0, PMul1));
       }
     }
   }
   return PMACPairs;
 }
 
 bool ARMParallelDSP::InsertParallelMACs(Reduction &Reduction,
                                         PMACPairList &PMACPairs) {
LLVM_DEBUG(
     dbgs() << "\nAccumulating integer additions (reductions) found:\n";
     for (auto R : Reductions) {
       dbgs() << "-  "; R.Phi->dump();
       dbgs() << "-> "; R.AccIntAdd->dump();
     }
   );
 }
 
-static void AddCandidateMAC(BinOpChainList &Candidates,
+static void AddCandidateMAC(OpChainList &Candidates,
                             const Instruction *Acc,
                             Value *MulOp0, Value *MulOp1, int MulOpNum) {
   Instruction *Mul = dyn_cast<Instruction>(Acc->getOperand(MulOpNum));
   LLVM_DEBUG(dbgs() << "OK, found acc mul:\t"; Mul->dump());
   ValueList LHS;
   ValueList RHS;
   if (IsNarrowSequence<16>(MulOp0, LHS) &&
       IsNarrowSequence<16>(MulOp1, RHS)) {
     LLVM_DEBUG(dbgs() << "OK, found narrow mul: "; Mul->dump());
-    Candidates.push_back(BinOpChain(Mul, LHS, RHS));
+    Candidates.push_back(new BinOpChain(Mul, LHS, RHS));
   }
 }
 
 static void MatchParallelMACSequences(Reduction &R,
-                                      BinOpChainList &Candidates) {
+                                      OpChainList &Candidates) {
   const Instruction *Acc = R.AccIntAdd;
   Value *A, *MulOp0, *MulOp1;
   LLVM_DEBUG(dbgs() << "\n- Analysing:\t"; Acc->dump());
 
   // Pattern 1: the accumulator is the RHS of the mul.
   while(match(Acc, m_Add(m_Mul(m_Value(MulOp0), m_Value(MulOp1)),
                          m_Value(A)))){
     AddCandidateMAC(Candidates, Acc, MulOp0, MulOp1, 0);
static void MatchParallelMACSequences(Reduction &R,
   // Because we start at the bottom of the chain, and we work our way up,
   // the muls are added in reverse program order to the list.
   std::reverse(Candidates.begin(), Candidates.end());
 }
 
 // Collects all instructions that are not part of the BinOp chains, which is
 // the set of instructions that can potentially alias with the MAC operands.
 static void AliasCandidates(BasicBlock *Header,
-                            BinOpChainList &Candidates,
+                            OpChainList &Candidates,
                             Instructions &Aliases) {
-  auto IsCandidate = [] (Instruction *I, BinOpChainList &Candidates) {
-    for (auto &C : Candidates) {
-      if (I == C.Root)
-        return true;
-      for (auto *Val : C.LHS) {
-        if (Val == I)
-          return true;
-      }
-      for (auto *Val : C.RHS) {
-        if (Val == I)
-          return true;
-      }
-    }
+  auto IsCandidate = [] (Instruction *I, OpChainList &Candidates) {
+    for (auto *C : Candidates) {
+      if (C->contains(I))
     return false;
   };
 
   std::for_each(Header->begin(), Header->end(),
                 [&Aliases, &Candidates, &IsCandidate] (Instruction &I) {
                   if (I.mayReadOrWriteMemory() &&
                       !IsCandidate(&I, Candidates))
                     Aliases.push_back(&I); });
 }
 
 // This compares all instructions from the "alias candidates" set, i.e., all
 // instructions that are not part of the MAC-chain, with all instructions in
 // the MAC candidate set, to see if instructions are aliased.
 static bool AreAliased(AliasAnalysis *AA, Instructions AliasCandidates,
-                       BinOpChainList &Candidates) {
+                       OpChainList &Candidates) {
   LLVM_DEBUG(dbgs() << "Alias checks:\n");
   for (auto *I : AliasCandidates) {
     LLVM_DEBUG(dbgs() << "- "; I->dump());
-    for (auto &C : Candidates) {
-      LLVM_DEBUG(dbgs() << "mul: "; C.Root->dump());
-      assert(C.MemLocs.size() >= 2 && "expecting at least 2 memlocs");
-      for (auto &MemLoc : C.MemLocs) {
+    for (auto *C : Candidates) {
+      LLVM_DEBUG(dbgs() << "mul: "; C->Root->dump());
+      assert(C->MemLocs.size() >= 2 && "expecting at least 2 memlocs");
+      for (auto &MemLoc : C->MemLocs) {
         if (isModOrRefSet(intersectModRef(AA->getModRefInfo(I, MemLoc),
                                           ModRefInfo::ModRef))) {
           LLVM_DEBUG(dbgs() << "Yes, aliases found\n");
           return true;
         }
       }
     }
   }
   LLVM_DEBUG(dbgs() << "OK: no aliases found!\n");
   return false;
 }
 
-static bool SetMemoryLocations(BinOpChainList &Candidates) {
-  const auto Size = MemoryLocation::UnknownSize;
-  for (auto &C : Candidates) {
+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.LHS.size() < 2 || C.LHS.size() != C.RHS.size()) {
+    if (C->size() < 4) {
       LLVM_DEBUG(dbgs() << "Operand list too short.\n");
       return false;
     }
+    C->SetMemoryLocations();
+    ValueList &LHS = static_cast<BinOpChain*>(C)->LHS;
+    ValueList &RHS = static_cast<BinOpChain*>(C)->RHS;
 
-    for (unsigned i = 0, e = C.LHS.size(); i < e; i += 2) {
-      auto *LdOp0 = dyn_cast<LoadInst>(C.LHS[i]);
-      auto *LdOp1 = dyn_cast<LoadInst>(C.RHS[i]);
-      if (!LdOp0 || !LdOp1)
+    for (unsigned i = 0, e = LHS.size(); i < e; i += 2) {
+      if (!isa<LoadInst>(LHS[i]) || !isa<LoadInst>(RHS[i]))
         return false;
-
-      C.MemLocs.push_back(MemoryLocation(LdOp0->getPointerOperand(), Size));
-      C.MemLocs.push_back(MemoryLocation(LdOp1->getPointerOperand(), Size));
     }
   }
   return true;
 }
 
 // Loop Pass that needs to identify integer add/sub reductions of 16-bit vector
 // multiplications.
 // To use SMLAD:
LLVM_DEBUG(dbgs() << "= Matching SMLAD =\n";
              dbgs() << "Header block:\n"; Header->dump();
              dbgs() << "Loop info:\n\n"; L->dump());
 
   bool Changed = false;
   ReductionList Reductions;
   MatchReductions(F, L, Header, Reductions);
 
   for (auto &R : Reductions) {
-    BinOpChainList MACCandidates;
+    OpChainList MACCandidates;
     MatchParallelMACSequences(R, MACCandidates);
-    if (!SetMemoryLocations(MACCandidates))
+    if (!CheckMACMemory(MACCandidates))
       continue;
     Instructions Aliases;
     AliasCandidates(Header, MACCandidates, Aliases);
     if (AreAliased(AA, Aliases, MACCandidates))
       continue;
     PMACPairList PMACPairs = CreateParallelMACPairs(MACCandidates);
     Changed = InsertParallelMACs(R, PMACPairs) || Changed;
+    for (auto *C : MACCandidates)
+      delete C;
   }
 
   LLVM_DEBUG(if (Changed) dbgs() << "Header block:\n"; Header->dump(););
   return Changed;
 }
 
 static void CreateLoadIns(IRBuilder<NoFolder> &IRB, Instruction *Acc,
                           LoadInst **VecLd) {