contrib/llvm/lib/Target/ARM/ARMParallelDSP.cpp

   1 //===- ParallelDSP.cpp - Parallel DSP Pass --------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 /// \file
  11 /// Armv6 introduced instructions to perform 32-bit SIMD operations. The
  12 /// purpose of this pass is do some IR pattern matching to create ACLE
  13 /// DSP intrinsics, which map on these 32-bit SIMD operations.
  14 /// This pass runs only when unaligned accesses is supported/enabled.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #include "llvm/ADT/Statistic.h"
  19 #include "llvm/ADT/SmallPtrSet.h"
  20 #include "llvm/Analysis/AliasAnalysis.h"
  21 #include "llvm/Analysis/LoopAccessAnalysis.h"
  22 #include "llvm/Analysis/LoopPass.h"
  23 #include "llvm/Analysis/LoopInfo.h"
  24 #include "llvm/IR/Instructions.h"
  25 #include "llvm/IR/NoFolder.h"
  26 #include "llvm/Transforms/Scalar.h"
  27 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  28 #include "llvm/Transforms/Utils/LoopUtils.h"
  29 #include "llvm/Pass.h"
  30 #include "llvm/PassRegistry.h"
  31 #include "llvm/PassSupport.h"
  32 #include "llvm/Support/Debug.h"
  33 #include "llvm/IR/PatternMatch.h"
  34 #include "llvm/CodeGen/TargetPassConfig.h"
  35 #include "ARM.h"
  36 #include "ARMSubtarget.h"
  37
  38 using namespace llvm;
  39 using namespace PatternMatch;
  40
  41 #define DEBUG_TYPE "arm-parallel-dsp"
  42
  43 STATISTIC(NumSMLAD , "Number of smlad instructions generated");
  44
  45 namespace {
  46   struct OpChain;
  47   struct BinOpChain;
  48   struct Reduction;
  49
  50   using OpChainList     = SmallVector<std::unique_ptr<OpChain>, 8>;
  51   using ReductionList   = SmallVector<Reduction, 8>;
  52   using ValueList       = SmallVector<Value*, 8>;
  53   using MemInstList     = SmallVector<Instruction*, 8>;
  54   using PMACPair        = std::pair<BinOpChain*,BinOpChain*>;
  55   using PMACPairList    = SmallVector<PMACPair, 8>;
  56   using Instructions    = SmallVector<Instruction*,16>;
  57   using MemLocList      = SmallVector<MemoryLocation, 4>;
  58
  59   struct OpChain {
  60     Instruction   *Root;
  61     ValueList     AllValues;
  62     MemInstList   VecLd;    // List of all load instructions.
  63     MemLocList    MemLocs;  // All memory locations read by this tree.
  64     bool          ReadOnly = true;
  65
  66     OpChain(Instruction *I, ValueList &vl) : Root(I), AllValues(vl) { }
  67     virtual ~OpChain() = default;
  68
  69     void SetMemoryLocations() {
  70       const auto Size = MemoryLocation::UnknownSize;
  71       for (auto *V : AllValues) {
  72         if (auto *I = dyn_cast<Instruction>(V)) {
  73           if (I->mayWriteToMemory())
  74             ReadOnly = false;
  75           if (auto *Ld = dyn_cast<LoadInst>(V))
  76             MemLocs.push_back(MemoryLocation(Ld->getPointerOperand(), Size));
  77         }
  78       }
  79     }
  80
  81     unsigned size() const { return AllValues.size(); }
  82   };
  83
  84   // 'BinOpChain' and 'Reduction' are just some bookkeeping data structures.
  85   // 'Reduction' contains the phi-node and accumulator statement from where we
  86   // start pattern matching, and 'BinOpChain' the multiplication
  87   // instructions that are candidates for parallel execution.
  88   struct BinOpChain : public OpChain {
  89     ValueList     LHS;      // List of all (narrow) left hand operands.
  90     ValueList     RHS;      // List of all (narrow) right hand operands.
  91
  92     BinOpChain(Instruction *I, ValueList &lhs, ValueList &rhs) :
  93       OpChain(I, lhs), LHS(lhs), RHS(rhs) {
  94         for (auto *V : RHS)
  95           AllValues.push_back(V);
  96       }
  97   };
  98
  99   struct Reduction {
 100     PHINode         *Phi;             // The Phi-node from where we start
 101                                       // pattern matching.
 102     Instruction     *AccIntAdd;       // The accumulating integer add statement,
 103                                       // i.e, the reduction statement.
 104
 105     OpChainList     MACCandidates;    // The MAC candidates associated with
 106                                       // this reduction statement.
 107     Reduction (PHINode *P, Instruction *Acc) : Phi(P), AccIntAdd(Acc) { };
 108   };
 109
 110   class ARMParallelDSP : public LoopPass {
 111     ScalarEvolution   *SE;
 112     AliasAnalysis     *AA;
 113     TargetLibraryInfo *TLI;
 114     DominatorTree     *DT;
 115     LoopInfo          *LI;
 116     Loop              *L;
 117     const DataLayout  *DL;
 118     Module            *M;
 119
 120     bool InsertParallelMACs(Reduction &Reduction, PMACPairList &PMACPairs);
 121     bool AreSequentialLoads(LoadInst *Ld0, LoadInst *Ld1, MemInstList &VecMem);
 122     PMACPairList CreateParallelMACPairs(OpChainList &Candidates);
 123     Instruction *CreateSMLADCall(LoadInst *VecLd0, LoadInst *VecLd1,
 124                                  Instruction *Acc, Instruction *InsertAfter);
 125
 126     /// Try to match and generate: SMLAD, SMLADX - Signed Multiply Accumulate
 127     /// Dual performs two signed 16x16-bit multiplications. It adds the
 128     /// products to a 32-bit accumulate operand. Optionally, the instruction can
 129     /// exchange the halfwords of the second operand before performing the
 130     /// arithmetic.
 131     bool MatchSMLAD(Function &F);
 132
 133   public:
 134     static char ID;
 135
 136     ARMParallelDSP() : LoopPass(ID) { }
 137
 138     void getAnalysisUsage(AnalysisUsage &AU) const override {
 139       LoopPass::getAnalysisUsage(AU);
 140       AU.addRequired<AssumptionCacheTracker>();
 141       AU.addRequired<ScalarEvolutionWrapperPass>();
 142       AU.addRequired<AAResultsWrapperPass>();
 143       AU.addRequired<TargetLibraryInfoWrapperPass>();
 144       AU.addRequired<LoopInfoWrapperPass>();
 145       AU.addRequired<DominatorTreeWrapperPass>();
 146       AU.addRequired<TargetPassConfig>();
 147       AU.addPreserved<LoopInfoWrapperPass>();
 148       AU.setPreservesCFG();
 149     }
 150
 151     bool runOnLoop(Loop *TheLoop, LPPassManager &) override {
 152       L = TheLoop;
 153       SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
 154       AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
 155       TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
 156       DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 157       LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 158       auto &TPC = getAnalysis<TargetPassConfig>();
 159
 160       BasicBlock *Header = TheLoop->getHeader();
 161       if (!Header)
 162         return false;
 163
 164       // TODO: We assume the loop header and latch to be the same block.
 165       // This is not a fundamental restriction, but lifting this would just
 166       // require more work to do the transformation and then patch up the CFG.
 167       if (Header != TheLoop->getLoopLatch()) {
 168         LLVM_DEBUG(dbgs() << "The loop header is not the loop latch: not "
 169                              "running pass ARMParallelDSP\n");
 170         return false;
 171       }
 172
 173       Function &F = *Header->getParent();
 174       M = F.getParent();
 175       DL = &M->getDataLayout();
 176
 177       auto &TM = TPC.getTM<TargetMachine>();
 178       auto *ST = &TM.getSubtarget<ARMSubtarget>(F);
 179
 180       if (!ST->allowsUnalignedMem()) {
 181         LLVM_DEBUG(dbgs() << "Unaligned memory access not supported: not "
 182                              "running pass ARMParallelDSP\n");
 183         return false;
 184       }
 185
 186       if (!ST->hasDSP()) {
 187         LLVM_DEBUG(dbgs() << "DSP extension not enabled: not running pass "
 188                              "ARMParallelDSP\n");
 189         return false;
 190       }
 191
 192       LoopAccessInfo LAI(L, SE, TLI, AA, DT, LI);
 193       bool Changes = false;
 194
 195       LLVM_DEBUG(dbgs() << "\n== Parallel DSP pass ==\n\n");
 196       Changes = MatchSMLAD(F);
 197       return Changes;
 198     }
 199   };
 200 }
 201
 202 // MaxBitwidth: the maximum supported bitwidth of the elements in the DSP
 203 // instructions, which is set to 16. So here we should collect all i8 and i16
 204 // narrow operations.
 205 // TODO: we currently only collect i16, and will support i8 later, so that's
 206 // why we check that types are equal to MaxBitWidth, and not <= MaxBitWidth.
 207 template<unsigned MaxBitWidth>
 208 static bool IsNarrowSequence(Value *V, ValueList &VL) {
 209   LLVM_DEBUG(dbgs() << "Is narrow sequence? "; V->dump());
 210   ConstantInt *CInt;
 211
 212   if (match(V, m_ConstantInt(CInt))) {
 213     // TODO: if a constant is used, it needs to fit within the bit width.
 214     return false;
 215   }
 216
 217   auto *I = dyn_cast<Instruction>(V);
 218   if (!I)
 219    return false;
 220
 221   Value *Val, *LHS, *RHS;
 222   if (match(V, m_Trunc(m_Value(Val)))) {
 223     if (cast<TruncInst>(I)->getDestTy()->getIntegerBitWidth() == MaxBitWidth)
 224       return IsNarrowSequence<MaxBitWidth>(Val, VL);
 225   } else if (match(V, m_Add(m_Value(LHS), m_Value(RHS)))) {
 226     // TODO: we need to implement sadd16/sadd8 for this, which enables to
 227     // also do the rewrite for smlad8.ll, but it is unsupported for now.
 228     LLVM_DEBUG(dbgs() << "No, unsupported Op:\t"; I->dump());
 229     return false;
 230   } else if (match(V, m_ZExtOrSExt(m_Value(Val)))) {
 231     if (cast<CastInst>(I)->getSrcTy()->getIntegerBitWidth() != MaxBitWidth) {
 232       LLVM_DEBUG(dbgs() << "No, wrong SrcTy size: " <<
 233         cast<CastInst>(I)->getSrcTy()->getIntegerBitWidth() << "\n");
 234       return false;
 235     }
 236
 237     if (match(Val, m_Load(m_Value()))) {
 238       LLVM_DEBUG(dbgs() << "Yes, found narrow Load:\t"; Val->dump());
 239       VL.push_back(Val);
 240       VL.push_back(I);
 241       return true;
 242     }
 243   }
 244   LLVM_DEBUG(dbgs() << "No, unsupported Op:\t"; I->dump());
 245   return false;
 246 }
 247
 248 // Element-by-element comparison of Value lists returning true if they are
 249 // instructions with the same opcode or constants with the same value.
 250 static bool AreSymmetrical(const ValueList &VL0,
 251                            const ValueList &VL1) {
 252   if (VL0.size() != VL1.size()) {
 253     LLVM_DEBUG(dbgs() << "Muls are mismatching operand list lengths: "
 254                       << VL0.size() << " != " << VL1.size() << "\n");
 255     return false;
 256   }
 257
 258   const unsigned Pairs = VL0.size();
 259   LLVM_DEBUG(dbgs() << "Number of operand pairs: " << Pairs << "\n");
 260
 261   for (unsigned i = 0; i < Pairs; ++i) {
 262     const Value *V0 = VL0[i];
 263     const Value *V1 = VL1[i];
 264     const auto *Inst0 = dyn_cast<Instruction>(V0);
 265     const auto *Inst1 = dyn_cast<Instruction>(V1);
 266
 267     LLVM_DEBUG(dbgs() << "Pair " << i << ":\n";
 268                dbgs() << "mul1: "; V0->dump();
 269                dbgs() << "mul2: "; V1->dump());
 270
 271     if (!Inst0 || !Inst1)
 272       return false;
 273
 274     if (Inst0->isSameOperationAs(Inst1)) {
 275       LLVM_DEBUG(dbgs() << "OK: same operation found!\n");
 276       continue;
 277     }
 278
 279     const APInt *C0, *C1;
 280     if (!(match(V0, m_APInt(C0)) && match(V1, m_APInt(C1)) && C0 == C1))
 281       return false;
 282   }
 283
 284   LLVM_DEBUG(dbgs() << "OK: found symmetrical operand lists.\n");
 285   return true;
 286 }
 287
 288 template<typename MemInst>
 289 static bool AreSequentialAccesses(MemInst *MemOp0, MemInst *MemOp1,
 290                                   MemInstList &VecMem, const DataLayout &DL,
 291                                   ScalarEvolution &SE) {
 292   if (!MemOp0->isSimple() || !MemOp1->isSimple()) {
 293     LLVM_DEBUG(dbgs() << "No, not touching volatile access\n");
 294     return false;
 295   }
 296   if (isConsecutiveAccess(MemOp0, MemOp1, DL, SE)) {
 297     VecMem.push_back(MemOp0);
 298     VecMem.push_back(MemOp1);
 299     LLVM_DEBUG(dbgs() << "OK: accesses are consecutive.\n");
 300     return true;
 301   }
 302   LLVM_DEBUG(dbgs() << "No, accesses aren't consecutive.\n");
 303   return false;
 304 }
 305
 306 bool ARMParallelDSP::AreSequentialLoads(LoadInst *Ld0, LoadInst *Ld1,
 307                                         MemInstList &VecMem) {
 308   if (!Ld0 || !Ld1)
 309     return false;
 310
 311   LLVM_DEBUG(dbgs() << "Are consecutive loads:\n";
 312     dbgs() << "Ld0:"; Ld0->dump();
 313     dbgs() << "Ld1:"; Ld1->dump();
 314   );
 315
 316   if (!Ld0->hasOneUse() || !Ld1->hasOneUse()) {
 317     LLVM_DEBUG(dbgs() << "No, load has more than one use.\n");
 318     return false;
 319   }
 320
 321   return AreSequentialAccesses<LoadInst>(Ld0, Ld1, VecMem, *DL, *SE);
 322 }
 323
 324 PMACPairList
 325 ARMParallelDSP::CreateParallelMACPairs(OpChainList &Candidates) {
 326   const unsigned Elems = Candidates.size();
 327   PMACPairList PMACPairs;
 328
 329   if (Elems < 2)
 330     return PMACPairs;
 331
 332   // TODO: for now we simply try to match consecutive pairs i and i+1.
 333   // We can compare all elements, but then we need to compare and evaluate
 334   // different solutions.
 335   for(unsigned i=0; i<Elems-1; i+=2) {
 336     BinOpChain *PMul0 = static_cast<BinOpChain*>(Candidates[i].get());
 337     BinOpChain *PMul1 = static_cast<BinOpChain*>(Candidates[i+1].get());
 338     const Instruction *Mul0 = PMul0->Root;
 339     const Instruction *Mul1 = PMul1->Root;
 340
 341     if (Mul0 == Mul1)
 342       continue;
 343
 344     LLVM_DEBUG(dbgs() << "\nCheck parallel muls:\n";
 345                dbgs() << "- "; Mul0->dump();
 346                dbgs() << "- "; Mul1->dump());
 347
 348     const ValueList &Mul0_LHS = PMul0->LHS;
 349     const ValueList &Mul0_RHS = PMul0->RHS;
 350     const ValueList &Mul1_LHS = PMul1->LHS;
 351     const ValueList &Mul1_RHS = PMul1->RHS;
 352
 353     if (!AreSymmetrical(Mul0_LHS, Mul1_LHS) ||
 354         !AreSymmetrical(Mul0_RHS, Mul1_RHS))
 355       continue;
 356
 357     LLVM_DEBUG(dbgs() << "OK: mul operands list match:\n");
 358     // The first elements of each vector should be loads with sexts. If we find
 359     // that its two pairs of consecutive loads, then these can be transformed
 360     // into two wider loads and the users can be replaced with DSP
 361     // intrinsics.
 362     for (unsigned x = 0; x < Mul0_LHS.size(); x += 2) {
 363       auto *Ld0 = dyn_cast<LoadInst>(Mul0_LHS[x]);
 364       auto *Ld1 = dyn_cast<LoadInst>(Mul1_LHS[x]);
 365       auto *Ld2 = dyn_cast<LoadInst>(Mul0_RHS[x]);
 366       auto *Ld3 = dyn_cast<LoadInst>(Mul1_RHS[x]);
 367
 368       LLVM_DEBUG(dbgs() << "Looking at operands " << x << ":\n";
 369                  dbgs() << "\t mul1: "; Mul0_LHS[x]->dump();
 370                  dbgs() << "\t mul2: "; Mul1_LHS[x]->dump();
 371                  dbgs() << "and operands " << x + 2 << ":\n";
 372                  dbgs() << "\t mul1: "; Mul0_RHS[x]->dump();
 373                  dbgs() << "\t mul2: "; Mul1_RHS[x]->dump());
 374
 375       if (AreSequentialLoads(Ld0, Ld1, PMul0->VecLd) &&
 376           AreSequentialLoads(Ld2, Ld3, PMul1->VecLd)) {
 377         LLVM_DEBUG(dbgs() << "OK: found two pairs of parallel loads!\n");
 378         PMACPairs.push_back(std::make_pair(PMul0, PMul1));
 379       }
 380     }
 381   }
 382   return PMACPairs;
 383 }
 384
 385 bool ARMParallelDSP::InsertParallelMACs(Reduction &Reduction,
 386                                         PMACPairList &PMACPairs) {
 387   Instruction *Acc = Reduction.Phi;
 388   Instruction *InsertAfter = Reduction.AccIntAdd;
 389
 390   for (auto &Pair : PMACPairs) {
 391     LLVM_DEBUG(dbgs() << "Found parallel MACs!!\n";
 392                dbgs() << "- "; Pair.first->Root->dump();
 393                dbgs() << "- "; Pair.second->Root->dump());
 394     auto *VecLd0 = cast<LoadInst>(Pair.first->VecLd[0]);
 395     auto *VecLd1 = cast<LoadInst>(Pair.second->VecLd[0]);
 396     Acc = CreateSMLADCall(VecLd0, VecLd1, Acc, InsertAfter);
 397     InsertAfter = Acc;
 398   }
 399
 400   if (Acc != Reduction.Phi) {
 401     LLVM_DEBUG(dbgs() << "Replace Accumulate: "; Acc->dump());
 402     Reduction.AccIntAdd->replaceAllUsesWith(Acc);
 403     return true;
 404   }
 405   return false;
 406 }
 407
 408 static void MatchReductions(Function &F, Loop *TheLoop, BasicBlock *Header,
 409                             ReductionList &Reductions) {
 410   RecurrenceDescriptor RecDesc;
 411   const bool HasFnNoNaNAttr =
 412     F.getFnAttribute("no-nans-fp-math").getValueAsString() == "true";
 413   const BasicBlock *Latch = TheLoop->getLoopLatch();
 414
 415   // We need a preheader as getIncomingValueForBlock assumes there is one.
 416   if (!TheLoop->getLoopPreheader()) {
 417     LLVM_DEBUG(dbgs() << "No preheader found, bailing out\n");
 418     return;
 419   }
 420
 421   for (PHINode &Phi : Header->phis()) {
 422     const auto *Ty = Phi.getType();
 423     if (!Ty->isIntegerTy(32))
 424       continue;
 425
 426     const bool IsReduction =
 427       RecurrenceDescriptor::AddReductionVar(&Phi,
 428                                             RecurrenceDescriptor::RK_IntegerAdd,
 429                                             TheLoop, HasFnNoNaNAttr, RecDesc);
 430     if (!IsReduction)
 431       continue;
 432
 433     Instruction *Acc = dyn_cast<Instruction>(Phi.getIncomingValueForBlock(Latch));
 434     if (!Acc)
 435       continue;
 436
 437     Reductions.push_back(Reduction(&Phi, Acc));
 438   }
 439
 440   LLVM_DEBUG(
 441     dbgs() << "\nAccumulating integer additions (reductions) found:\n";
 442     for (auto &R : Reductions) {
 443       dbgs() << "-  "; R.Phi->dump();
 444       dbgs() << "-> "; R.AccIntAdd->dump();
 445     }
 446   );
 447 }
 448
 449 static void AddMACCandidate(OpChainList &Candidates,
 450                             const Instruction *Acc,
 451                             Value *MulOp0, Value *MulOp1, int MulOpNum) {
 452   Instruction *Mul = dyn_cast<Instruction>(Acc->getOperand(MulOpNum));
 453   LLVM_DEBUG(dbgs() << "OK, found acc mul:\t"; Mul->dump());
 454   ValueList LHS;
 455   ValueList RHS;
 456   if (IsNarrowSequence<16>(MulOp0, LHS) &&
 457       IsNarrowSequence<16>(MulOp1, RHS)) {
 458     LLVM_DEBUG(dbgs() << "OK, found narrow mul: "; Mul->dump());
 459     Candidates.push_back(make_unique<BinOpChain>(Mul, LHS, RHS));
 460   }
 461 }
 462
 463 static void MatchParallelMACSequences(Reduction &R,
 464                                       OpChainList &Candidates) {
 465   const Instruction *Acc = R.AccIntAdd;
 466   Value *A, *MulOp0, *MulOp1;
 467   LLVM_DEBUG(dbgs() << "\n- Analysing:\t"; Acc->dump());
 468
 469   // Pattern 1: the accumulator is the RHS of the mul.
 470   while(match(Acc, m_Add(m_Mul(m_Value(MulOp0), m_Value(MulOp1)),
 471                          m_Value(A)))){
 472     AddMACCandidate(Candidates, Acc, MulOp0, MulOp1, 0);
 473     Acc = dyn_cast<Instruction>(A);
 474   }
 475   // Pattern 2: the accumulator is the LHS of the mul.
 476   while(match(Acc, m_Add(m_Value(A),
 477                          m_Mul(m_Value(MulOp0), m_Value(MulOp1))))) {
 478     AddMACCandidate(Candidates, Acc, MulOp0, MulOp1, 1);
 479     Acc = dyn_cast<Instruction>(A);
 480   }
 481
 482   // The last mul in the chain has a slightly different pattern:
 483   // the mul is the first operand
 484   if (match(Acc, m_Add(m_Mul(m_Value(MulOp0), m_Value(MulOp1)), m_Value(A))))
 485     AddMACCandidate(Candidates, Acc, MulOp0, MulOp1, 0);
 486
 487   // Because we start at the bottom of the chain, and we work our way up,
 488   // the muls are added in reverse program order to the list.
 489   std::reverse(Candidates.begin(), Candidates.end());
 490 }
 491
 492 // Collects all instructions that are not part of the MAC chains, which is the
 493 // set of instructions that can potentially alias with the MAC operands.
 494 static void AliasCandidates(BasicBlock *Header, Instructions &Reads,
 495                             Instructions &Writes) {
 496   for (auto &I : *Header) {
 497     if (I.mayReadFromMemory())
 498       Reads.push_back(&I);
 499     if (I.mayWriteToMemory())
 500       Writes.push_back(&I);
 501   }
 502 }
 503
 504 // Check whether statements in the basic block that write to memory alias with
 505 // the memory locations accessed by the MAC-chains.
 506 // TODO: we need the read statements when we accept more complicated chains.
 507 static bool AreAliased(AliasAnalysis *AA, Instructions &Reads,
 508                        Instructions &Writes, OpChainList &MACCandidates) {
 509   LLVM_DEBUG(dbgs() << "Alias checks:\n");
 510   for (auto &MAC : MACCandidates) {
 511     LLVM_DEBUG(dbgs() << "mul: "; MAC->Root->dump());
 512
 513     // At the moment, we allow only simple chains that only consist of reads,
 514     // accumulate their result with an integer add, and thus that don't write
 515     // memory, and simply bail if they do.
 516     if (!MAC->ReadOnly)
 517       return true;
 518
 519     // Now for all writes in the basic block, check that they don't alias with
 520     // the memory locations accessed by our MAC-chain:
 521     for (auto *I : Writes) {
 522       LLVM_DEBUG(dbgs() << "- "; I->dump());
 523       assert(MAC->MemLocs.size() >= 2 && "expecting at least 2 memlocs");
 524       for (auto &MemLoc : MAC->MemLocs) {
 525         if (isModOrRefSet(intersectModRef(AA->getModRefInfo(I, MemLoc),
 526                                           ModRefInfo::ModRef))) {
 527           LLVM_DEBUG(dbgs() << "Yes, aliases found\n");
 528           return true;
 529         }
 530       }
 531     }
 532   }
 533
 534   LLVM_DEBUG(dbgs() << "OK: no aliases found!\n");
 535   return false;
 536 }
 537
 538 static bool CheckMACMemory(OpChainList &Candidates) {
 539   for (auto &C : Candidates) {
 540     // A mul has 2 operands, and a narrow op consist of sext and a load; thus
 541     // we expect at least 4 items in this operand value list.
 542     if (C->size() < 4) {
 543       LLVM_DEBUG(dbgs() << "Operand list too short.\n");
 544       return false;
 545     }
 546     C->SetMemoryLocations();
 547     ValueList &LHS = static_cast<BinOpChain*>(C.get())->LHS;
 548     ValueList &RHS = static_cast<BinOpChain*>(C.get())->RHS;
 549
 550     // Use +=2 to skip over the expected extend instructions.
 551     for (unsigned i = 0, e = LHS.size(); i < e; i += 2) {
 552       if (!isa<LoadInst>(LHS[i]) || !isa<LoadInst>(RHS[i]))
 553         return false;
 554     }
 555   }
 556   return true;
 557 }
 558
 559 // Loop Pass that needs to identify integer add/sub reductions of 16-bit vector
 560 // multiplications.
 561 // To use SMLAD:
 562 // 1) we first need to find integer add reduction PHIs,
 563 // 2) then from the PHI, look for this pattern:
 564 //
 565 // acc0 = phi i32 [0, %entry], [%acc1, %loop.body]
 566 // ld0 = load i16
 567 // sext0 = sext i16 %ld0 to i32
 568 // ld1 = load i16
 569 // sext1 = sext i16 %ld1 to i32
 570 // mul0 = mul %sext0, %sext1
 571 // ld2 = load i16
 572 // sext2 = sext i16 %ld2 to i32
 573 // ld3 = load i16
 574 // sext3 = sext i16 %ld3 to i32
 575 // mul1 = mul i32 %sext2, %sext3
 576 // add0 = add i32 %mul0, %acc0
 577 // acc1 = add i32 %add0, %mul1
 578 //
 579 // Which can be selected to:
 580 //
 581 // ldr.h r0
 582 // ldr.h r1
 583 // smlad r2, r0, r1, r2
 584 //
 585 // If constants are used instead of loads, these will need to be hoisted
 586 // out and into a register.
 587 //
 588 // If loop invariants are used instead of loads, these need to be packed
 589 // before the loop begins.
 590 //
 591 bool ARMParallelDSP::MatchSMLAD(Function &F) {
 592   BasicBlock *Header = L->getHeader();
 593   LLVM_DEBUG(dbgs() << "= Matching SMLAD =\n";
 594              dbgs() << "Header block:\n"; Header->dump();
 595              dbgs() << "Loop info:\n\n"; L->dump());
 596
 597   bool Changed = false;
 598   ReductionList Reductions;
 599   MatchReductions(F, L, Header, Reductions);
 600
 601   for (auto &R : Reductions) {
 602     OpChainList MACCandidates;
 603     MatchParallelMACSequences(R, MACCandidates);
 604     if (!CheckMACMemory(MACCandidates))
 605       continue;
 606
 607     R.MACCandidates = std::move(MACCandidates);
 608
 609     LLVM_DEBUG(dbgs() << "MAC candidates:\n";
 610       for (auto &M : R.MACCandidates)
 611         M->Root->dump();
 612       dbgs() << "\n";);
 613   }
 614
 615   // Collect all instructions that may read or write memory. Our alias
 616   // analysis checks bail out if any of these instructions aliases with an
 617   // instruction from the MAC-chain.
 618   Instructions Reads, Writes;
 619   AliasCandidates(Header, Reads, Writes);
 620
 621   for (auto &R : Reductions) {
 622     if (AreAliased(AA, Reads, Writes, R.MACCandidates))
 623       return false;
 624     PMACPairList PMACPairs = CreateParallelMACPairs(R.MACCandidates);
 625     Changed |= InsertParallelMACs(R, PMACPairs);
 626   }
 627
 628   LLVM_DEBUG(if (Changed) dbgs() << "Header block:\n"; Header->dump(););
 629   return Changed;
 630 }
 631
 632 static void CreateLoadIns(IRBuilder<NoFolder> &IRB, Instruction *Acc,
 633                           LoadInst **VecLd) {
 634   const Type *AccTy = Acc->getType();
 635   const unsigned AddrSpace = (*VecLd)->getPointerAddressSpace();
 636
 637   Value *VecPtr = IRB.CreateBitCast((*VecLd)->getPointerOperand(),
 638                                     AccTy->getPointerTo(AddrSpace));
 639   *VecLd = IRB.CreateAlignedLoad(VecPtr, (*VecLd)->getAlignment());
 640 }
 641
 642 Instruction *ARMParallelDSP::CreateSMLADCall(LoadInst *VecLd0, LoadInst *VecLd1,
 643                                              Instruction *Acc,
 644                                              Instruction *InsertAfter) {
 645   LLVM_DEBUG(dbgs() << "Create SMLAD intrinsic using:\n";
 646              dbgs() << "- "; VecLd0->dump();
 647              dbgs() << "- "; VecLd1->dump();
 648              dbgs() << "- "; Acc->dump());
 649
 650   IRBuilder<NoFolder> Builder(InsertAfter->getParent(),
 651                               ++BasicBlock::iterator(InsertAfter));
 652
 653   // Replace the reduction chain with an intrinsic call
 654   CreateLoadIns(Builder, Acc, &VecLd0);
 655   CreateLoadIns(Builder, Acc, &VecLd1);
 656   Value* Args[] = { VecLd0, VecLd1, Acc };
 657   Function *SMLAD = Intrinsic::getDeclaration(M, Intrinsic::arm_smlad);
 658   CallInst *Call = Builder.CreateCall(SMLAD, Args);
 659   NumSMLAD++;
 660   return Call;
 661 }
 662
 663 Pass *llvm::createARMParallelDSPPass() {
 664   return new ARMParallelDSP();
 665 }
 666
 667 char ARMParallelDSP::ID = 0;
 668
 669 INITIALIZE_PASS_BEGIN(ARMParallelDSP, "arm-parallel-dsp",
 670                 "Transform loops to use DSP intrinsics", false, false)
 671 INITIALIZE_PASS_END(ARMParallelDSP, "arm-parallel-dsp",
 672                 "Transform loops to use DSP intrinsics", false, false)