[ARM][NFC] ParallelDSP tweaks

[samparker]

Summary

Convert the ParallelMAC struct to something more generic, it has become 'BinOpSequence' and the ValueList 'VL' is now two: LHS and RHS. This makes iterating and comparing the instructions cleaner.

Also changed some functions to accept reference arguments instead of copying the data out.

[SjoerdMeijer]

lib/Target/ARM/ARMParallelDSP.cpp

42

Bikeshedding names: was thinking if e.g. BinOpChain is capturing it better?

459

Should we then also rename argument 'MACCandidates' in to e.g. just Candidates to also make that generic?

490

Same here?

[samparker]

Renamed BinOpSequence to BinOpChain and replaced MACCandidates with Candidates in the Alias functions.

[SjoerdMeijer]

LGTM, cheers!

[samparker]

Merging changes into D49020 since it was easier to do with a rebase.

lib/Target/ARM/ARMParallelDSP.cpp

 #include "ARMSubtarget.h"
 
 using namespace llvm;
 using namespace PatternMatch;
 
 #define DEBUG_TYPE "parallel-dsp"
 
 namespace {
-  struct ParallelMAC;
+  struct BinOpChain;
   struct Reduction;
 
-  using ParallelMACList = SmallVector<ParallelMAC, 8>;
+  using BinOpChainList = SmallVector<BinOpChain, 8>;
   using ReductionList   = SmallVector<Reduction, 8>;
   using ValueList       = SmallVector<Value*, 8>;
   using MemInstList     = SmallVector<Instruction*, 8>;
-  using PMACPair        = std::pair<ParallelMAC*,ParallelMAC*>;
+  using PMACPair        = std::pair<BinOpChain*,BinOpChain*>;
   using PMACPairList    = SmallVector<PMACPair, 8>;
   using Instructions    = SmallVector<Instruction*,16>;
   using MemLocList      = SmallVector<MemoryLocation, 4>;
 
-  // 'ParallelMAC' and 'Reduction' are just some bookkeeping data structures.
+  // 'BinOpChain' and 'Reduction' are just some bookkeeping data structures.
   // 'Reduction' contains the phi-node and accumulator statement from where we
-  // start pattern matching, and 'ParallelMAC' the multiplication
+  // start pattern matching, and 'BinOpChain' the multiplication
   // instructions that are candidates for parallel execution.
-  struct ParallelMAC {
-    Instruction *Mul;
-    ValueList    VL;        // List of all (narrow) operands of this Mul
-    MemInstList  VecLd;     // List of all load instructions of this Mul
-    MemLocList   MemLocs;   // All memory locations read by this Mul
-
-    ParallelMAC(Instruction *I, ValueList &V) : Mul(I), VL(V) {};
+  struct BinOpChain {
+    Instruction   *Root;
+    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) {};
   };
 
   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(ParallelMACList &Candidates);
+    PMACPairList CreateParallelMACPairs(BinOpChainList &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.

     LLVM_DEBUG(dbgs() << "No, load has more than one use.\n");
     return false;
   }
 
   return AreSequentialAccesses<LoadInst>(Ld0, Ld1, VecMem, *DL, *SE);
 }
 
 PMACPairList
-ARMParallelDSP::CreateParallelMACPairs(ParallelMACList &Candidates) {
+ARMParallelDSP::CreateParallelMACPairs(BinOpChainList &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) {
-    ParallelMAC &PMul0 = Candidates[i];
-    ParallelMAC &PMul1 = Candidates[i+1];
-    const Instruction *Mul0 = PMul0.Mul;
-    const Instruction *Mul1 = PMul1.Mul;
+    BinOpChain &PMul0 = Candidates[i];
+    BinOpChain &PMul1 = 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 &VL0 = PMul0.VL;
-    const ValueList &VL1 = PMul1.VL;
+    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(VL0, VL1))
+    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 < VL0.size(); x += 4) {
-      auto *Ld0 = dyn_cast<LoadInst>(VL0[x]);
-      auto *Ld1 = dyn_cast<LoadInst>(VL1[x]);
-      auto *Ld2 = dyn_cast<LoadInst>(VL0[x+2]);
-      auto *Ld3 = dyn_cast<LoadInst>(VL1[x+2]);
+    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: "; VL0[x]->dump();
-                 dbgs() << "\t mul2: "; VL1[x]->dump();
+                 dbgs() << "\t mul1: "; Mul0_LHS[x]->dump();
+                 dbgs() << "\t mul2: "; Mul1_LHS[x]->dump();
                  dbgs() << "and operands " << x + 2 << ":\n";
-                 dbgs() << "\t mul1: "; VL0[x+2]->dump();
-                 dbgs() << "\t mul2: "; VL1[x+2]->dump());
+                 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)) {
         LLVM_DEBUG(dbgs() << "OK: found two pairs of parallel loads!\n");
         PMACPairs.push_back(std::make_pair(&PMul0, &PMul1));
       }
     }
   }
   return PMACPairs;
 }
 
 bool ARMParallelDSP::InsertParallelMACs(Reduction &Reduction,
                                         PMACPairList &PMACPairs) {
   Instruction *Acc = Reduction.Phi;
   Instruction *InsertAfter = Reduction.AccIntAdd;
 
   for (auto &Pair : PMACPairs) {
     LLVM_DEBUG(dbgs() << "Found parallel MACs!!\n";
-               dbgs() << "- "; Pair.first->Mul->dump();
-               dbgs() << "- "; Pair.second->Mul->dump());
+               dbgs() << "- "; Pair.first->Root->dump();
+               dbgs() << "- "; Pair.second->Root->dump());
     auto *VecLd0 = cast<LoadInst>(Pair.first->VecLd[0]);
     auto *VecLd1 = cast<LoadInst>(Pair.second->VecLd[0]);
     Acc = CreateSMLADCall(VecLd0, VecLd1, Acc, InsertAfter);
     InsertAfter = Acc;
   }
 
   if (Acc != Reduction.Phi) {
     LLVM_DEBUG(dbgs() << "Replace Accumulate: "; Acc->dump());
     Reduction.AccIntAdd->replaceAllUsesWith(Acc);
     return true;
   }
   return false;
 }
 
-static ReductionList MatchReductions(Function &F, Loop *TheLoop,
-                                     BasicBlock *Header) {
-  ReductionList Reductions;
+static void MatchReductions(Function &F, Loop *TheLoop, BasicBlock *Header,
+                            ReductionList &Reductions) {
   RecurrenceDescriptor RecDesc;
   const bool HasFnNoNaNAttr =
     F.getFnAttribute("no-nans-fp-math").getValueAsString() == "true";
   const BasicBlock *Latch = TheLoop->getLoopLatch();
 
   // We need a preheader as getIncomingValueForBlock assumes there is one.
   if (!TheLoop->getLoopPreheader())
-    return Reductions;
+    return;
 
   for (PHINode &Phi : Header->phis()) {
     const auto *Ty = Phi.getType();
     if (!Ty->isIntegerTy(32))
       continue;
 
     const bool IsReduction =
       RecurrenceDescriptor::AddReductionVar(&Phi,

 
   LLVM_DEBUG(
     dbgs() << "\nAccumulating integer additions (reductions) found:\n";
     for (auto R : Reductions) {
       dbgs() << "-  "; R.Phi->dump();
       dbgs() << "-> "; R.AccIntAdd->dump();
     }
   );
-  return Reductions;
 }
 
-static void AddCandidateMAC(ParallelMACList &Candidates, const Instruction *Acc,
+static void AddCandidateMAC(BinOpChainList &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 VL;
-  if (IsNarrowSequence<16>(MulOp0, VL) &&
-      IsNarrowSequence<16>(MulOp1, VL)) {
+  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(ParallelMAC(Mul, VL));
+    Candidates.push_back(BinOpChain(Mul, LHS, RHS));
   }
 }
 
-static ParallelMACList MatchParallelMACs(Reduction &R) {
-  ParallelMACList Candidates;
+static void MatchParallelMACSequences(Reduction &R,
+                                      BinOpChainList &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);

   // The last mul in the chain has a slightly different pattern:
   // the mul is the first operand
   if (match(Acc, m_Add(m_Mul(m_Value(MulOp0), m_Value(MulOp1)), m_Value(A))))
     AddCandidateMAC(Candidates, Acc, MulOp0, MulOp1, 0);
 
   // 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());
-  return Candidates;
 }
 
-// Collects all instructions that are not part of the MAC chains, which is the
-// set of instructions that can potentially alias with the MAC operands.
-static Instructions AliasCandidates(BasicBlock *Header,
-                                    ParallelMACList &MACCandidates) {
-  Instructions Aliases;
-  auto IsMACCandidate = [] (Instruction *I, ParallelMACList &MACCandidates) {
-    for (auto &MAC : MACCandidates)
-      for (auto *Val : MAC.VL)
-        if (I == MAC.Mul || Val == I)
+// 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,
+                            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;
-   return false;
+      }
+      for (auto *Val : C.RHS) {
+        if (Val == I)
+          return true;
+      }
+    }
+    return false;
   };
 
   std::for_each(Header->begin(), Header->end(),
-                [&Aliases, &MACCandidates, &IsMACCandidate] (Instruction &I) {
+                [&Aliases, &Candidates, &IsCandidate] (Instruction &I) {
                   if (I.mayReadOrWriteMemory() &&
-                      !IsMACCandidate(&I, MACCandidates))
+                      !IsCandidate(&I, Candidates))
                     Aliases.push_back(&I); });
-  return Aliases;
 }
 
 // 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,
-                       ParallelMACList &MACCandidates) {
+                       BinOpChainList &Candidates) {
   LLVM_DEBUG(dbgs() << "Alias checks:\n");
   for (auto *I : AliasCandidates) {
     LLVM_DEBUG(dbgs() << "- "; I->dump());
-    for (auto &MAC : MACCandidates) {
-      LLVM_DEBUG(dbgs() << "mul: "; MAC.Mul->dump());
-      assert(MAC.MemLocs.size() >= 2 && "expecting at least 2 memlocs");
-      for (auto &MemLoc : MAC.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(ParallelMACList &Candidates) {
+static bool SetMemoryLocations(BinOpChainList &Candidates) {
   const auto Size = MemoryLocation::UnknownSize;
   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.VL.size() < 4) {
+    if (C.LHS.size() < 2 || C.LHS.size() != C.RHS.size()) {
       LLVM_DEBUG(dbgs() << "Operand list too short.\n");
       return false;
     }
 
-    for (unsigned i = 0; i < C.VL.size(); i += 4) {
-      auto *LdOp0 = dyn_cast<LoadInst>(C.VL[i]);
-      auto *LdOp1 = dyn_cast<LoadInst>(C.VL[i+2]);
+    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)
         return false;
 
       C.MemLocs.push_back(MemoryLocation(LdOp0->getPointerOperand(), Size));
       C.MemLocs.push_back(MemoryLocation(LdOp1->getPointerOperand(), Size));
     }
   }
   return true;

 //
 bool ARMParallelDSP::MatchSMLAD(Function &F) {
   BasicBlock *Header = L->getHeader();
   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);
+  ReductionList Reductions;
+  MatchReductions(F, L, Header, Reductions);
 
   for (auto &R : Reductions) {
-    ParallelMACList MACCandidates = MatchParallelMACs(R);
+    BinOpChainList MACCandidates;
+    MatchParallelMACSequences(R, MACCandidates);
     if (!SetMemoryLocations(MACCandidates))
       continue;
-    Instructions Aliases = AliasCandidates(Header, MACCandidates);
+    Instructions Aliases;
+    AliasCandidates(Header, MACCandidates, Aliases);
     if (AreAliased(AA, Aliases, MACCandidates))
       continue;
     PMACPairList PMACPairs = CreateParallelMACPairs(MACCandidates);
     Changed = InsertParallelMACs(R, PMACPairs) || Changed;
   }
 
   LLVM_DEBUG(if (Changed) dbgs() << "Header block:\n"; Header->dump(););
   return Changed;