llvm/lib/Target/ARM/ARMParallelDSP.cpp

   1 //===- ARMParallelDSP.cpp - Parallel DSP Pass -----------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 /// \file
  10 /// Armv6 introduced instructions to perform 32-bit SIMD operations. The
  11 /// purpose of this pass is do some IR pattern matching to create ACLE
  12 /// DSP intrinsics, which map on these 32-bit SIMD operations.
  13 /// This pass runs only when unaligned accesses is supported/enabled.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "ARM.h"
  18 #include "ARMSubtarget.h"
  19 #include "llvm/ADT/SmallPtrSet.h"
  20 #include "llvm/ADT/Statistic.h"
  21 #include "llvm/Analysis/AliasAnalysis.h"
  22 #include "llvm/Analysis/AssumptionCache.h"
  23 #include "llvm/Analysis/GlobalsModRef.h"
  24 #include "llvm/Analysis/LoopAccessAnalysis.h"
  25 #include "llvm/Analysis/TargetLibraryInfo.h"
  26 #include "llvm/CodeGen/TargetPassConfig.h"
  27 #include "llvm/IR/IRBuilder.h"
  28 #include "llvm/IR/Instructions.h"
  29 #include "llvm/IR/IntrinsicsARM.h"
  30 #include "llvm/IR/Module.h"
  31 #include "llvm/IR/NoFolder.h"
  32 #include "llvm/IR/PatternMatch.h"
  33 #include "llvm/Pass.h"
  34 #include "llvm/Support/Debug.h"
  35 #include "llvm/Transforms/Scalar.h"
  36 #include "llvm/Transforms/Utils/BasicBlockUtils.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 static cl::opt<bool>
  46 DisableParallelDSP("disable-arm-parallel-dsp", cl::Hidden, cl::init(false),
  47                    cl::desc("Disable the ARM Parallel DSP pass"));
  48
  49 static cl::opt<unsigned>
  50 NumLoadLimit("arm-parallel-dsp-load-limit", cl::Hidden, cl::init(16),
  51              cl::desc("Limit the number of loads analysed"));
  52
  53 namespace {
  54   struct MulCandidate;
  55   class Reduction;
  56
  57   using MulCandList = SmallVector<std::unique_ptr<MulCandidate>, 8>;
  58   using MemInstList = SmallVectorImpl<LoadInst*>;
  59   using MulPairList = SmallVector<std::pair<MulCandidate*, MulCandidate*>, 8>;
  60
  61   // 'MulCandidate' holds the multiplication instructions that are candidates
  62   // for parallel execution.
  63   struct MulCandidate {
  64     Instruction   *Root;
  65     Value*        LHS;
  66     Value*        RHS;
  67     bool          Exchange = false;
  68     bool          Paired = false;
  69     SmallVector<LoadInst*, 2> VecLd;    // Container for loads to widen.
  70
  71     MulCandidate(Instruction *I, Value *lhs, Value *rhs) :
  72       Root(I), LHS(lhs), RHS(rhs) { }
  73
  74     bool HasTwoLoadInputs() const {
  75       return isa<LoadInst>(LHS) && isa<LoadInst>(RHS);
  76     }
  77
  78     LoadInst *getBaseLoad() const {
  79       return VecLd.front();
  80     }
  81   };
  82
  83   /// Represent a sequence of multiply-accumulate operations with the aim to
  84   /// perform the multiplications in parallel.
  85   class Reduction {
  86     Instruction     *Root = nullptr;
  87     Value           *Acc = nullptr;
  88     MulCandList     Muls;
  89     MulPairList        MulPairs;
  90     SetVector<Instruction*> Adds;
  91
  92   public:
  93     Reduction() = delete;
  94
  95     Reduction (Instruction *Add) : Root(Add) { }
  96
  97     /// Record an Add instruction that is a part of the this reduction.
  98     void InsertAdd(Instruction *I) { Adds.insert(I); }
  99
 100     /// Create MulCandidates, each rooted at a Mul instruction, that is a part
 101     /// of this reduction.
 102     void InsertMuls() {
 103       auto GetMulOperand = [](Value *V) -> Instruction* {
 104         if (auto *SExt = dyn_cast<SExtInst>(V)) {
 105           if (auto *I = dyn_cast<Instruction>(SExt->getOperand(0)))
 106             if (I->getOpcode() == Instruction::Mul)
 107               return I;
 108         } else if (auto *I = dyn_cast<Instruction>(V)) {
 109           if (I->getOpcode() == Instruction::Mul)
 110             return I;
 111         }
 112         return nullptr;
 113       };
 114
 115       auto InsertMul = [this](Instruction *I) {
 116         Value *LHS = cast<Instruction>(I->getOperand(0))->getOperand(0);
 117         Value *RHS = cast<Instruction>(I->getOperand(1))->getOperand(0);
 118         Muls.push_back(std::make_unique<MulCandidate>(I, LHS, RHS));
 119       };
 120
 121       for (auto *Add : Adds) {
 122         if (Add == Acc)
 123           continue;
 124         if (auto *Mul = GetMulOperand(Add->getOperand(0)))
 125           InsertMul(Mul);
 126         if (auto *Mul = GetMulOperand(Add->getOperand(1)))
 127           InsertMul(Mul);
 128       }
 129     }
 130
 131     /// Add the incoming accumulator value, returns true if a value had not
 132     /// already been added. Returning false signals to the user that this
 133     /// reduction already has a value to initialise the accumulator.
 134     bool InsertAcc(Value *V) {
 135       if (Acc)
 136         return false;
 137       Acc = V;
 138       return true;
 139     }
 140
 141     /// Set two MulCandidates, rooted at muls, that can be executed as a single
 142     /// parallel operation.
 143     void AddMulPair(MulCandidate *Mul0, MulCandidate *Mul1,
 144                     bool Exchange = false) {
 145       LLVM_DEBUG(dbgs() << "Pairing:\n"
 146                  << *Mul0->Root << "\n"
 147                  << *Mul1->Root << "\n");
 148       Mul0->Paired = true;
 149       Mul1->Paired = true;
 150       if (Exchange)
 151         Mul1->Exchange = true;
 152       MulPairs.push_back(std::make_pair(Mul0, Mul1));
 153     }
 154
 155     /// Return the add instruction which is the root of the reduction.
 156     Instruction *getRoot() { return Root; }
 157
 158     bool is64Bit() const { return Root->getType()->isIntegerTy(64); }
 159
 160     Type *getType() const { return Root->getType(); }
 161
 162     /// Return the incoming value to be accumulated. This maybe null.
 163     Value *getAccumulator() { return Acc; }
 164
 165     /// Return the set of adds that comprise the reduction.
 166     SetVector<Instruction*> &getAdds() { return Adds; }
 167
 168     /// Return the MulCandidate, rooted at mul instruction, that comprise the
 169     /// the reduction.
 170     MulCandList &getMuls() { return Muls; }
 171
 172     /// Return the MulCandidate, rooted at mul instructions, that have been
 173     /// paired for parallel execution.
 174     MulPairList &getMulPairs() { return MulPairs; }
 175
 176     /// To finalise, replace the uses of the root with the intrinsic call.
 177     void UpdateRoot(Instruction *SMLAD) {
 178       Root->replaceAllUsesWith(SMLAD);
 179     }
 180
 181     void dump() {
 182       LLVM_DEBUG(dbgs() << "Reduction:\n";
 183         for (auto *Add : Adds)
 184           LLVM_DEBUG(dbgs() << *Add << "\n");
 185         for (auto &Mul : Muls)
 186           LLVM_DEBUG(dbgs() << *Mul->Root << "\n"
 187                      << "  " << *Mul->LHS << "\n"
 188                      << "  " << *Mul->RHS << "\n");
 189         LLVM_DEBUG(if (Acc) dbgs() << "Acc in: " << *Acc << "\n")
 190       );
 191     }
 192   };
 193
 194   class WidenedLoad {
 195     LoadInst *NewLd = nullptr;
 196     SmallVector<LoadInst*, 4> Loads;
 197
 198   public:
 199     WidenedLoad(SmallVectorImpl<LoadInst*> &Lds, LoadInst *Wide)
 200       : NewLd(Wide) {
 201       append_range(Loads, Lds);
 202     }
 203     LoadInst *getLoad() {
 204       return NewLd;
 205     }
 206   };
 207
 208   class ARMParallelDSP : public FunctionPass {
 209     ScalarEvolution   *SE;
 210     AliasAnalysis     *AA;
 211     TargetLibraryInfo *TLI;
 212     DominatorTree     *DT;
 213     const DataLayout  *DL;
 214     Module            *M;
 215     std::map<LoadInst*, LoadInst*> LoadPairs;
 216     SmallPtrSet<LoadInst*, 4> OffsetLoads;
 217     std::map<LoadInst*, std::unique_ptr<WidenedLoad>> WideLoads;
 218
 219     template<unsigned>
 220     bool IsNarrowSequence(Value *V);
 221     bool Search(Value *V, BasicBlock *BB, Reduction &R);
 222     bool RecordMemoryOps(BasicBlock *BB);
 223     void InsertParallelMACs(Reduction &Reduction);
 224     bool AreSequentialLoads(LoadInst *Ld0, LoadInst *Ld1, MemInstList &VecMem);
 225     LoadInst* CreateWideLoad(MemInstList &Loads, IntegerType *LoadTy);
 226     bool CreateParallelPairs(Reduction &R);
 227
 228     /// Try to match and generate: SMLAD, SMLADX - Signed Multiply Accumulate
 229     /// Dual performs two signed 16x16-bit multiplications. It adds the
 230     /// products to a 32-bit accumulate operand. Optionally, the instruction can
 231     /// exchange the halfwords of the second operand before performing the
 232     /// arithmetic.
 233     bool MatchSMLAD(Function &F);
 234
 235   public:
 236     static char ID;
 237
 238     ARMParallelDSP() : FunctionPass(ID) { }
 239
 240     void getAnalysisUsage(AnalysisUsage &AU) const override {
 241       FunctionPass::getAnalysisUsage(AU);
 242       AU.addRequired<AssumptionCacheTracker>();
 243       AU.addRequired<ScalarEvolutionWrapperPass>();
 244       AU.addRequired<AAResultsWrapperPass>();
 245       AU.addRequired<TargetLibraryInfoWrapperPass>();
 246       AU.addRequired<DominatorTreeWrapperPass>();
 247       AU.addRequired<TargetPassConfig>();
 248       AU.addPreserved<ScalarEvolutionWrapperPass>();
 249       AU.addPreserved<GlobalsAAWrapperPass>();
 250       AU.setPreservesCFG();
 251     }
 252
 253     bool runOnFunction(Function &F) override {
 254       if (DisableParallelDSP)
 255         return false;
 256       if (skipFunction(F))
 257         return false;
 258
 259       SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
 260       AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
 261       TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
 262       DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 263       auto &TPC = getAnalysis<TargetPassConfig>();
 264
 265       M = F.getParent();
 266       DL = &M->getDataLayout();
 267
 268       auto &TM = TPC.getTM<TargetMachine>();
 269       auto *ST = &TM.getSubtarget<ARMSubtarget>(F);
 270
 271       if (!ST->allowsUnalignedMem()) {
 272         LLVM_DEBUG(dbgs() << "Unaligned memory access not supported: not "
 273                              "running pass ARMParallelDSP\n");
 274         return false;
 275       }
 276
 277       if (!ST->hasDSP()) {
 278         LLVM_DEBUG(dbgs() << "DSP extension not enabled: not running pass "
 279                              "ARMParallelDSP\n");
 280         return false;
 281       }
 282
 283       if (!ST->isLittle()) {
 284         LLVM_DEBUG(dbgs() << "Only supporting little endian: not running pass "
 285                           << "ARMParallelDSP\n");
 286         return false;
 287       }
 288
 289       LLVM_DEBUG(dbgs() << "\n== Parallel DSP pass ==\n");
 290       LLVM_DEBUG(dbgs() << " - " << F.getName() << "\n\n");
 291
 292       bool Changes = MatchSMLAD(F);
 293       return Changes;
 294     }
 295   };
 296 }
 297
 298 bool ARMParallelDSP::AreSequentialLoads(LoadInst *Ld0, LoadInst *Ld1,
 299                                         MemInstList &VecMem) {
 300   if (!Ld0 || !Ld1)
 301     return false;
 302
 303   if (!LoadPairs.count(Ld0) || LoadPairs[Ld0] != Ld1)
 304     return false;
 305
 306   LLVM_DEBUG(dbgs() << "Loads are sequential and valid:\n";
 307     dbgs() << "Ld0:"; Ld0->dump();
 308     dbgs() << "Ld1:"; Ld1->dump();
 309   );
 310
 311   VecMem.clear();
 312   VecMem.push_back(Ld0);
 313   VecMem.push_back(Ld1);
 314   return true;
 315 }
 316
 317 // MaxBitwidth: the maximum supported bitwidth of the elements in the DSP
 318 // instructions, which is set to 16. So here we should collect all i8 and i16
 319 // narrow operations.
 320 // TODO: we currently only collect i16, and will support i8 later, so that's
 321 // why we check that types are equal to MaxBitWidth, and not <= MaxBitWidth.
 322 template<unsigned MaxBitWidth>
 323 bool ARMParallelDSP::IsNarrowSequence(Value *V) {
 324   if (auto *SExt = dyn_cast<SExtInst>(V)) {
 325     if (SExt->getSrcTy()->getIntegerBitWidth() != MaxBitWidth)
 326       return false;
 327
 328     if (auto *Ld = dyn_cast<LoadInst>(SExt->getOperand(0))) {
 329       // Check that this load could be paired.
 330       return LoadPairs.count(Ld) || OffsetLoads.count(Ld);
 331     }
 332   }
 333   return false;
 334 }
 335
 336 /// Iterate through the block and record base, offset pairs of loads which can
 337 /// be widened into a single load.
 338 bool ARMParallelDSP::RecordMemoryOps(BasicBlock *BB) {
 339   SmallVector<LoadInst*, 8> Loads;
 340   SmallVector<Instruction*, 8> Writes;
 341   LoadPairs.clear();
 342   WideLoads.clear();
 343
 344   // Collect loads and instruction that may write to memory. For now we only
 345   // record loads which are simple, sign-extended and have a single user.
 346   // TODO: Allow zero-extended loads.
 347   for (auto &I : *BB) {
 348     if (I.mayWriteToMemory())
 349       Writes.push_back(&I);
 350     auto *Ld = dyn_cast<LoadInst>(&I);
 351     if (!Ld || !Ld->isSimple() ||
 352         !Ld->hasOneUse() || !isa<SExtInst>(Ld->user_back()))
 353       continue;
 354     Loads.push_back(Ld);
 355   }
 356
 357   if (Loads.empty() || Loads.size() > NumLoadLimit)
 358     return false;
 359
 360   using InstSet = std::set<Instruction*>;
 361   using DepMap = std::map<Instruction*, InstSet>;
 362   DepMap RAWDeps;
 363
 364   // Record any writes that may alias a load.
 365   const auto Size = LocationSize::beforeOrAfterPointer();
 366   for (auto *Write : Writes) {
 367     for (auto *Read : Loads) {
 368       MemoryLocation ReadLoc =
 369         MemoryLocation(Read->getPointerOperand(), Size);
 370
 371       if (!isModOrRefSet(AA->getModRefInfo(Write, ReadLoc)))
 372         continue;
 373       if (Write->comesBefore(Read))
 374         RAWDeps[Read].insert(Write);
 375     }
 376   }
 377
 378   // Check whether there's not a write between the two loads which would
 379   // prevent them from being safely merged.
 380   auto SafeToPair = [&](LoadInst *Base, LoadInst *Offset) {
 381     bool BaseFirst = Base->comesBefore(Offset);
 382     LoadInst *Dominator = BaseFirst ? Base : Offset;
 383     LoadInst *Dominated = BaseFirst ? Offset : Base;
 384
 385     if (RAWDeps.count(Dominated)) {
 386       InstSet &WritesBefore = RAWDeps[Dominated];
 387
 388       for (auto *Before : WritesBefore) {
 389         // We can't move the second load backward, past a write, to merge
 390         // with the first load.
 391         if (Dominator->comesBefore(Before))
 392           return false;
 393       }
 394     }
 395     return true;
 396   };
 397
 398   // Record base, offset load pairs.
 399   for (auto *Base : Loads) {
 400     for (auto *Offset : Loads) {
 401       if (Base == Offset || OffsetLoads.count(Offset))
 402         continue;
 403
 404       if (isConsecutiveAccess(Base, Offset, *DL, *SE) &&
 405           SafeToPair(Base, Offset)) {
 406         LoadPairs[Base] = Offset;
 407         OffsetLoads.insert(Offset);
 408         break;
 409       }
 410     }
 411   }
 412
 413   LLVM_DEBUG(if (!LoadPairs.empty()) {
 414                dbgs() << "Consecutive load pairs:\n";
 415                for (auto &MapIt : LoadPairs) {
 416                  LLVM_DEBUG(dbgs() << *MapIt.first << ", "
 417                             << *MapIt.second << "\n");
 418                }
 419              });
 420   return LoadPairs.size() > 1;
 421 }
 422
 423 // Search recursively back through the operands to find a tree of values that
 424 // form a multiply-accumulate chain. The search records the Add and Mul
 425 // instructions that form the reduction and allows us to find a single value
 426 // to be used as the initial input to the accumlator.
 427 bool ARMParallelDSP::Search(Value *V, BasicBlock *BB, Reduction &R) {
 428   // If we find a non-instruction, try to use it as the initial accumulator
 429   // value. This may have already been found during the search in which case
 430   // this function will return false, signaling a search fail.
 431   auto *I = dyn_cast<Instruction>(V);
 432   if (!I)
 433     return R.InsertAcc(V);
 434
 435   if (I->getParent() != BB)
 436     return false;
 437
 438   switch (I->getOpcode()) {
 439   default:
 440     break;
 441   case Instruction::PHI:
 442     // Could be the accumulator value.
 443     return R.InsertAcc(V);
 444   case Instruction::Add: {
 445     // Adds should be adding together two muls, or another add and a mul to
 446     // be within the mac chain. One of the operands may also be the
 447     // accumulator value at which point we should stop searching.
 448     R.InsertAdd(I);
 449     Value *LHS = I->getOperand(0);
 450     Value *RHS = I->getOperand(1);
 451     bool ValidLHS = Search(LHS, BB, R);
 452     bool ValidRHS = Search(RHS, BB, R);
 453
 454     if (ValidLHS && ValidRHS)
 455       return true;
 456
 457     // Ensure we don't add the root as the incoming accumulator.
 458     if (R.getRoot() == I)
 459       return false;
 460
 461     return R.InsertAcc(I);
 462   }
 463   case Instruction::Mul: {
 464     Value *MulOp0 = I->getOperand(0);
 465     Value *MulOp1 = I->getOperand(1);
 466     return IsNarrowSequence<16>(MulOp0) && IsNarrowSequence<16>(MulOp1);
 467   }
 468   case Instruction::SExt:
 469     return Search(I->getOperand(0), BB, R);
 470   }
 471   return false;
 472 }
 473
 474 // The pass needs to identify integer add/sub reductions of 16-bit vector
 475 // multiplications.
 476 // To use SMLAD:
 477 // 1) we first need to find integer add then look for this pattern:
 478 //
 479 // acc0 = ...
 480 // ld0 = load i16
 481 // sext0 = sext i16 %ld0 to i32
 482 // ld1 = load i16
 483 // sext1 = sext i16 %ld1 to i32
 484 // mul0 = mul %sext0, %sext1
 485 // ld2 = load i16
 486 // sext2 = sext i16 %ld2 to i32
 487 // ld3 = load i16
 488 // sext3 = sext i16 %ld3 to i32
 489 // mul1 = mul i32 %sext2, %sext3
 490 // add0 = add i32 %mul0, %acc0
 491 // acc1 = add i32 %add0, %mul1
 492 //
 493 // Which can be selected to:
 494 //
 495 // ldr r0
 496 // ldr r1
 497 // smlad r2, r0, r1, r2
 498 //
 499 // If constants are used instead of loads, these will need to be hoisted
 500 // out and into a register.
 501 //
 502 // If loop invariants are used instead of loads, these need to be packed
 503 // before the loop begins.
 504 //
 505 bool ARMParallelDSP::MatchSMLAD(Function &F) {
 506   bool Changed = false;
 507
 508   for (auto &BB : F) {
 509     SmallPtrSet<Instruction*, 4> AllAdds;
 510     if (!RecordMemoryOps(&BB))
 511       continue;
 512
 513     for (Instruction &I : reverse(BB)) {
 514       if (I.getOpcode() != Instruction::Add)
 515         continue;
 516
 517       if (AllAdds.count(&I))
 518         continue;
 519
 520       const auto *Ty = I.getType();
 521       if (!Ty->isIntegerTy(32) && !Ty->isIntegerTy(64))
 522         continue;
 523
 524       Reduction R(&I);
 525       if (!Search(&I, &BB, R))
 526         continue;
 527
 528       R.InsertMuls();
 529       LLVM_DEBUG(dbgs() << "After search, Reduction:\n"; R.dump());
 530
 531       if (!CreateParallelPairs(R))
 532         continue;
 533
 534       InsertParallelMACs(R);
 535       Changed = true;
 536       AllAdds.insert(R.getAdds().begin(), R.getAdds().end());
 537       LLVM_DEBUG(dbgs() << "BB after inserting parallel MACs:\n" << BB);
 538     }
 539   }
 540
 541   return Changed;
 542 }
 543
 544 bool ARMParallelDSP::CreateParallelPairs(Reduction &R) {
 545
 546   // Not enough mul operations to make a pair.
 547   if (R.getMuls().size() < 2)
 548     return false;
 549
 550   // Check that the muls operate directly upon sign extended loads.
 551   for (auto &MulCand : R.getMuls()) {
 552     if (!MulCand->HasTwoLoadInputs())
 553       return false;
 554   }
 555
 556   auto CanPair = [&](Reduction &R, MulCandidate *PMul0, MulCandidate *PMul1) {
 557     // The first elements of each vector should be loads with sexts. If we
 558     // find that its two pairs of consecutive loads, then these can be
 559     // transformed into two wider loads and the users can be replaced with
 560     // DSP intrinsics.
 561     auto Ld0 = static_cast<LoadInst*>(PMul0->LHS);
 562     auto Ld1 = static_cast<LoadInst*>(PMul1->LHS);
 563     auto Ld2 = static_cast<LoadInst*>(PMul0->RHS);
 564     auto Ld3 = static_cast<LoadInst*>(PMul1->RHS);
 565
 566     // Check that each mul is operating on two different loads.
 567     if (Ld0 == Ld2 || Ld1 == Ld3)
 568       return false;
 569
 570     if (AreSequentialLoads(Ld0, Ld1, PMul0->VecLd)) {
 571       if (AreSequentialLoads(Ld2, Ld3, PMul1->VecLd)) {
 572         LLVM_DEBUG(dbgs() << "OK: found two pairs of parallel loads!\n");
 573         R.AddMulPair(PMul0, PMul1);
 574         return true;
 575       } else if (AreSequentialLoads(Ld3, Ld2, PMul1->VecLd)) {
 576         LLVM_DEBUG(dbgs() << "OK: found two pairs of parallel loads!\n");
 577         LLVM_DEBUG(dbgs() << "    exchanging Ld2 and Ld3\n");
 578         R.AddMulPair(PMul0, PMul1, true);
 579         return true;
 580       }
 581     } else if (AreSequentialLoads(Ld1, Ld0, PMul0->VecLd) &&
 582                AreSequentialLoads(Ld2, Ld3, PMul1->VecLd)) {
 583       LLVM_DEBUG(dbgs() << "OK: found two pairs of parallel loads!\n");
 584       LLVM_DEBUG(dbgs() << "    exchanging Ld0 and Ld1\n");
 585       LLVM_DEBUG(dbgs() << "    and swapping muls\n");
 586       // Only the second operand can be exchanged, so swap the muls.
 587       R.AddMulPair(PMul1, PMul0, true);
 588       return true;
 589     }
 590     return false;
 591   };
 592
 593   MulCandList &Muls = R.getMuls();
 594   const unsigned Elems = Muls.size();
 595   for (unsigned i = 0; i < Elems; ++i) {
 596     MulCandidate *PMul0 = static_cast<MulCandidate*>(Muls[i].get());
 597     if (PMul0->Paired)
 598       continue;
 599
 600     for (unsigned j = 0; j < Elems; ++j) {
 601       if (i == j)
 602         continue;
 603
 604       MulCandidate *PMul1 = static_cast<MulCandidate*>(Muls[j].get());
 605       if (PMul1->Paired)
 606         continue;
 607
 608       const Instruction *Mul0 = PMul0->Root;
 609       const Instruction *Mul1 = PMul1->Root;
 610       if (Mul0 == Mul1)
 611         continue;
 612
 613       assert(PMul0 != PMul1 && "expected different chains");
 614
 615       if (CanPair(R, PMul0, PMul1))
 616         break;
 617     }
 618   }
 619   return !R.getMulPairs().empty();
 620 }
 621
 622 void ARMParallelDSP::InsertParallelMACs(Reduction &R) {
 623
 624   auto CreateSMLAD = [&](LoadInst* WideLd0, LoadInst *WideLd1,
 625                          Value *Acc, bool Exchange,
 626                          Instruction *InsertAfter) {
 627     // Replace the reduction chain with an intrinsic call
 628
 629     Value* Args[] = { WideLd0, WideLd1, Acc };
 630     Function *SMLAD = nullptr;
 631     if (Exchange)
 632       SMLAD =
 633           Acc->getType()->isIntegerTy(32)
 634               ? Intrinsic::getOrInsertDeclaration(M, Intrinsic::arm_smladx)
 635               : Intrinsic::getOrInsertDeclaration(M, Intrinsic::arm_smlaldx);
 636     else
 637       SMLAD = Acc->getType()->isIntegerTy(32)
 638                   ? Intrinsic::getOrInsertDeclaration(M, Intrinsic::arm_smlad)
 639                   : Intrinsic::getOrInsertDeclaration(M, Intrinsic::arm_smlald);
 640
 641     IRBuilder<NoFolder> Builder(InsertAfter->getParent(),
 642                                 BasicBlock::iterator(InsertAfter));
 643     Instruction *Call = Builder.CreateCall(SMLAD, Args);
 644     NumSMLAD++;
 645     return Call;
 646   };
 647
 648   // Return the instruction after the dominated instruction.
 649   auto GetInsertPoint = [this](Value *A, Value *B) {
 650     assert((isa<Instruction>(A) || isa<Instruction>(B)) &&
 651            "expected at least one instruction");
 652
 653     Value *V = nullptr;
 654     if (!isa<Instruction>(A))
 655       V = B;
 656     else if (!isa<Instruction>(B))
 657       V = A;
 658     else
 659       V = DT->dominates(cast<Instruction>(A), cast<Instruction>(B)) ? B : A;
 660
 661     return &*++BasicBlock::iterator(cast<Instruction>(V));
 662   };
 663
 664   Value *Acc = R.getAccumulator();
 665
 666   // For any muls that were discovered but not paired, accumulate their values
 667   // as before.
 668   IRBuilder<NoFolder> Builder(R.getRoot()->getParent());
 669   MulCandList &MulCands = R.getMuls();
 670   for (auto &MulCand : MulCands) {
 671     if (MulCand->Paired)
 672       continue;
 673
 674     Instruction *Mul = cast<Instruction>(MulCand->Root);
 675     LLVM_DEBUG(dbgs() << "Accumulating unpaired mul: " << *Mul << "\n");
 676
 677     if (R.getType() != Mul->getType()) {
 678       assert(R.is64Bit() && "expected 64-bit result");
 679       Builder.SetInsertPoint(&*++BasicBlock::iterator(Mul));
 680       Mul = cast<Instruction>(Builder.CreateSExt(Mul, R.getRoot()->getType()));
 681     }
 682
 683     if (!Acc) {
 684       Acc = Mul;
 685       continue;
 686     }
 687
 688     // If Acc is the original incoming value to the reduction, it could be a
 689     // phi. But the phi will dominate Mul, meaning that Mul will be the
 690     // insertion point.
 691     Builder.SetInsertPoint(GetInsertPoint(Mul, Acc));
 692     Acc = Builder.CreateAdd(Mul, Acc);
 693   }
 694
 695   if (!Acc) {
 696     Acc = R.is64Bit() ?
 697       ConstantInt::get(IntegerType::get(M->getContext(), 64), 0) :
 698       ConstantInt::get(IntegerType::get(M->getContext(), 32), 0);
 699   } else if (Acc->getType() != R.getType()) {
 700     Builder.SetInsertPoint(R.getRoot());
 701     Acc = Builder.CreateSExt(Acc, R.getType());
 702   }
 703
 704   // Roughly sort the mul pairs in their program order.
 705   llvm::sort(R.getMulPairs(), [](auto &PairA, auto &PairB) {
 706     const Instruction *A = PairA.first->Root;
 707     const Instruction *B = PairB.first->Root;
 708     return A->comesBefore(B);
 709   });
 710
 711   IntegerType *Ty = IntegerType::get(M->getContext(), 32);
 712   for (auto &Pair : R.getMulPairs()) {
 713     MulCandidate *LHSMul = Pair.first;
 714     MulCandidate *RHSMul = Pair.second;
 715     LoadInst *BaseLHS = LHSMul->getBaseLoad();
 716     LoadInst *BaseRHS = RHSMul->getBaseLoad();
 717     LoadInst *WideLHS = WideLoads.count(BaseLHS) ?
 718       WideLoads[BaseLHS]->getLoad() : CreateWideLoad(LHSMul->VecLd, Ty);
 719     LoadInst *WideRHS = WideLoads.count(BaseRHS) ?
 720       WideLoads[BaseRHS]->getLoad() : CreateWideLoad(RHSMul->VecLd, Ty);
 721
 722     Instruction *InsertAfter = GetInsertPoint(WideLHS, WideRHS);
 723     InsertAfter = GetInsertPoint(InsertAfter, Acc);
 724     Acc = CreateSMLAD(WideLHS, WideRHS, Acc, RHSMul->Exchange, InsertAfter);
 725   }
 726   R.UpdateRoot(cast<Instruction>(Acc));
 727 }
 728
 729 LoadInst* ARMParallelDSP::CreateWideLoad(MemInstList &Loads,
 730                                          IntegerType *LoadTy) {
 731   assert(Loads.size() == 2 && "currently only support widening two loads");
 732
 733   LoadInst *Base = Loads[0];
 734   LoadInst *Offset = Loads[1];
 735
 736   Instruction *BaseSExt = dyn_cast<SExtInst>(Base->user_back());
 737   Instruction *OffsetSExt = dyn_cast<SExtInst>(Offset->user_back());
 738
 739   assert((BaseSExt && OffsetSExt)
 740          && "Loads should have a single, extending, user");
 741
 742   std::function<void(Value*, Value*)> MoveBefore =
 743     [&](Value *A, Value *B) -> void {
 744       if (!isa<Instruction>(A) || !isa<Instruction>(B))
 745         return;
 746
 747       auto *Source = cast<Instruction>(A);
 748       auto *Sink = cast<Instruction>(B);
 749
 750       if (DT->dominates(Source, Sink) ||
 751           Source->getParent() != Sink->getParent() ||
 752           isa<PHINode>(Source) || isa<PHINode>(Sink))
 753         return;
 754
 755       Source->moveBefore(Sink);
 756       for (auto &Op : Source->operands())
 757         MoveBefore(Op, Source);
 758     };
 759
 760   // Insert the load at the point of the original dominating load.
 761   LoadInst *DomLoad = DT->dominates(Base, Offset) ? Base : Offset;
 762   IRBuilder<NoFolder> IRB(DomLoad->getParent(),
 763                           ++BasicBlock::iterator(DomLoad));
 764
 765   // Create the wide load, while making sure to maintain the original alignment
 766   // as this prevents ldrd from being generated when it could be illegal due to
 767   // memory alignment.
 768   Value *VecPtr = Base->getPointerOperand();
 769   LoadInst *WideLoad = IRB.CreateAlignedLoad(LoadTy, VecPtr, Base->getAlign());
 770
 771   // Make sure everything is in the correct order in the basic block.
 772   MoveBefore(Base->getPointerOperand(), VecPtr);
 773   MoveBefore(VecPtr, WideLoad);
 774
 775   // From the wide load, create two values that equal the original two loads.
 776   // Loads[0] needs trunc while Loads[1] needs a lshr and trunc.
 777   // TODO: Support big-endian as well.
 778   Value *Bottom = IRB.CreateTrunc(WideLoad, Base->getType());
 779   Value *NewBaseSExt = IRB.CreateSExt(Bottom, BaseSExt->getType());
 780   BaseSExt->replaceAllUsesWith(NewBaseSExt);
 781
 782   IntegerType *OffsetTy = cast<IntegerType>(Offset->getType());
 783   Value *ShiftVal = ConstantInt::get(LoadTy, OffsetTy->getBitWidth());
 784   Value *Top = IRB.CreateLShr(WideLoad, ShiftVal);
 785   Value *Trunc = IRB.CreateTrunc(Top, OffsetTy);
 786   Value *NewOffsetSExt = IRB.CreateSExt(Trunc, OffsetSExt->getType());
 787   OffsetSExt->replaceAllUsesWith(NewOffsetSExt);
 788
 789   LLVM_DEBUG(dbgs() << "From Base and Offset:\n"
 790              << *Base << "\n" << *Offset << "\n"
 791              << "Created Wide Load:\n"
 792              << *WideLoad << "\n"
 793              << *Bottom << "\n"
 794              << *NewBaseSExt << "\n"
 795              << *Top << "\n"
 796              << *Trunc << "\n"
 797              << *NewOffsetSExt << "\n");
 798   WideLoads.emplace(std::make_pair(Base,
 799                                    std::make_unique<WidenedLoad>(Loads, WideLoad)));
 800   return WideLoad;
 801 }
 802
 803 Pass *llvm::createARMParallelDSPPass() {
 804   return new ARMParallelDSP();
 805 }
 806
 807 char ARMParallelDSP::ID = 0;
 808
 809 INITIALIZE_PASS_BEGIN(ARMParallelDSP, "arm-parallel-dsp",
 810                 "Transform functions to use DSP intrinsics", false, false)
 811 INITIALIZE_PASS_END(ARMParallelDSP, "arm-parallel-dsp",
 812                 "Transform functions to use DSP intrinsics", false, false)