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