Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/ARM/ARMParallelDSP.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- ParallelDSP.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 "llvm/ADT/Statistic.h"
18
#include "llvm/ADT/SmallPtrSet.h"
19
#include "llvm/Analysis/AliasAnalysis.h"
20
#include "llvm/Analysis/LoopAccessAnalysis.h"
21
#include "llvm/Analysis/LoopPass.h"
22
#include "llvm/Analysis/LoopInfo.h"
23
#include "llvm/IR/Instructions.h"
24
#include "llvm/IR/NoFolder.h"
25
#include "llvm/Transforms/Scalar.h"
26
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
27
#include "llvm/Transforms/Utils/LoopUtils.h"
28
#include "llvm/Pass.h"
29
#include "llvm/PassRegistry.h"
30
#include "llvm/PassSupport.h"
31
#include "llvm/Support/Debug.h"
32
#include "llvm/IR/PatternMatch.h"
33
#include "llvm/CodeGen/TargetPassConfig.h"
34
#include "ARM.h"
35
#include "ARMSubtarget.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
namespace {
49
  struct OpChain;
50
  struct BinOpChain;
51
  class Reduction;
52
53
  using OpChainList     = SmallVector<std::unique_ptr<OpChain>, 8>;
54
  using ReductionList   = SmallVector<Reduction, 8>;
55
  using ValueList       = SmallVector<Value*, 8>;
56
  using MemInstList     = SmallVector<LoadInst*, 8>;
57
  using PMACPair        = std::pair<BinOpChain*,BinOpChain*>;
58
  using PMACPairList    = SmallVector<PMACPair, 8>;
59
  using Instructions    = SmallVector<Instruction*,16>;
60
  using MemLocList      = SmallVector<MemoryLocation, 4>;
61
62
  struct OpChain {
63
    Instruction   *Root;
64
    ValueList     AllValues;
65
    MemInstList   VecLd;    // List of all load instructions.
66
    MemInstList   Loads;
67
    bool          ReadOnly = true;
68
69
153
    OpChain(Instruction *I, ValueList &vl) : Root(I), AllValues(vl) { }
70
153
    virtual ~OpChain() = default;
71
72
123
    void PopulateLoads() {
73
492
      for (auto *V : AllValues) {
74
492
        if (auto *Ld = dyn_cast<LoadInst>(V))
75
246
          Loads.push_back(Ld);
76
492
      }
77
123
    }
78
79
123
    unsigned size() const { return AllValues.size(); }
80
  };
81
82
  // 'BinOpChain' holds the multiplication instructions that are candidates
83
  // for parallel execution.
84
  struct BinOpChain : public OpChain {
85
    ValueList     LHS;      // List of all (narrow) left hand operands.
86
    ValueList     RHS;      // List of all (narrow) right hand operands.
87
    bool Exchange = false;
88
89
    BinOpChain(Instruction *I, ValueList &lhs, ValueList &rhs) :
90
153
      OpChain(I, lhs), LHS(lhs), RHS(rhs) {
91
153
        for (auto *V : RHS)
92
306
          AllValues.push_back(V);
93
153
      }
94
95
    bool AreSymmetrical(BinOpChain *Other);
96
  };
97
98
  /// Represent a sequence of multiply-accumulate operations with the aim to
99
  /// perform the multiplications in parallel.
100
  class Reduction {
101
    Instruction     *Root = nullptr;
102
    Value           *Acc = nullptr;
103
    OpChainList     Muls;
104
    PMACPairList        MulPairs;
105
    SmallPtrSet<Instruction*, 4> Adds;
106
107
  public:
108
    Reduction() = delete;
109
110
138
    Reduction (Instruction *Add) : Root(Add) { }
111
112
    /// Record an Add instruction that is a part of the this reduction.
113
196
    void InsertAdd(Instruction *I) { Adds.insert(I); }
114
115
    /// Record a BinOpChain, rooted at a Mul instruction, that is a part of
116
    /// this reduction.
117
153
    void InsertMul(Instruction *I, ValueList &LHS, ValueList &RHS) {
118
153
      Muls.push_back(make_unique<BinOpChain>(I, LHS, RHS));
119
153
    }
120
121
    /// Add the incoming accumulator value, returns true if a value had not
122
    /// already been added. Returning false signals to the user that this
123
    /// reduction already has a value to initialise the accumulator.
124
235
    bool InsertAcc(Value *V) {
125
235
      if (Acc)
126
100
        return false;
127
135
      Acc = V;
128
135
      return true;
129
135
    }
130
131
    /// Set two BinOpChains, rooted at muls, that can be executed as a single
132
    /// parallel operation.
133
46
    void AddMulPair(BinOpChain *Mul0, BinOpChain *Mul1) {
134
46
      MulPairs.push_back(std::make_pair(Mul0, Mul1));
135
46
    }
136
137
    /// Return true if enough mul operations are found that can be executed in
138
    /// parallel.
139
    bool CreateParallelPairs();
140
141
    /// Return the add instruction which is the root of the reduction.
142
34
    Instruction *getRoot() { return Root; }
143
144
    /// Return the incoming value to be accumulated. This maybe null.
145
34
    Value *getAccumulator() { return Acc; }
146
147
    /// Return the set of adds that comprise the reduction.
148
68
    SmallPtrSetImpl<Instruction*> &getAdds() { return Adds; }
149
150
    /// Return the BinOpChain, rooted at mul instruction, that comprise the
151
    /// the reduction.
152
144
    OpChainList &getMuls() { return Muls; }
153
154
    /// Return the BinOpChain, rooted at mul instructions, that have been
155
    /// paired for parallel execution.
156
80
    PMACPairList &getMulPairs() { return MulPairs; }
157
158
    /// To finalise, replace the uses of the root with the intrinsic call.
159
34
    void UpdateRoot(Instruction *SMLAD) {
160
34
      Root->replaceAllUsesWith(SMLAD);
161
34
    }
162
  };
163
164
  class WidenedLoad {
165
    LoadInst *NewLd = nullptr;
166
    SmallVector<LoadInst*, 4> Loads;
167
168
  public:
169
    WidenedLoad(SmallVectorImpl<LoadInst*> &Lds, LoadInst *Wide)
170
92
      : NewLd(Wide) {
171
92
      for (auto *I : Lds)
172
184
        Loads.push_back(I);
173
92
    }
174
0
    LoadInst *getLoad() {
175
0
      return NewLd;
176
0
    }
177
  };
178
179
  class ARMParallelDSP : public LoopPass {
180
    ScalarEvolution   *SE;
181
    AliasAnalysis     *AA;
182
    TargetLibraryInfo *TLI;
183
    DominatorTree     *DT;
184
    LoopInfo          *LI;
185
    Loop              *L;
186
    const DataLayout  *DL;
187
    Module            *M;
188
    std::map<LoadInst*, LoadInst*> LoadPairs;
189
    SmallPtrSet<LoadInst*, 4> OffsetLoads;
190
    std::map<LoadInst*, std::unique_ptr<WidenedLoad>> WideLoads;
191
192
    template<unsigned>
193
    bool IsNarrowSequence(Value *V, ValueList &VL);
194
195
    bool RecordMemoryOps(BasicBlock *BB);
196
    void InsertParallelMACs(Reduction &Reduction);
197
    bool AreSequentialLoads(LoadInst *Ld0, LoadInst *Ld1, MemInstList &VecMem);
198
    LoadInst* CreateWideLoad(SmallVectorImpl<LoadInst*> &Loads,
199
                             IntegerType *LoadTy);
200
    bool CreateParallelPairs(Reduction &R);
201
202
    /// Try to match and generate: SMLAD, SMLADX - Signed Multiply Accumulate
203
    /// Dual performs two signed 16x16-bit multiplications. It adds the
204
    /// products to a 32-bit accumulate operand. Optionally, the instruction can
205
    /// exchange the halfwords of the second operand before performing the
206
    /// arithmetic.
207
    bool MatchSMLAD(Loop *L);
208
209
  public:
210
    static char ID;
211
212
1.29k
    ARMParallelDSP() : LoopPass(ID) { }
213
214
3.78k
    bool doInitialization(Loop *L, LPPassManager &LPM) override {
215
3.78k
      LoadPairs.clear();
216
3.78k
      WideLoads.clear();
217
3.78k
      return true;
218
3.78k
    }
219
220
1.29k
    void getAnalysisUsage(AnalysisUsage &AU) const override {
221
1.29k
      LoopPass::getAnalysisUsage(AU);
222
1.29k
      AU.addRequired<AssumptionCacheTracker>();
223
1.29k
      AU.addRequired<ScalarEvolutionWrapperPass>();
224
1.29k
      AU.addRequired<AAResultsWrapperPass>();
225
1.29k
      AU.addRequired<TargetLibraryInfoWrapperPass>();
226
1.29k
      AU.addRequired<LoopInfoWrapperPass>();
227
1.29k
      AU.addRequired<DominatorTreeWrapperPass>();
228
1.29k
      AU.addRequired<TargetPassConfig>();
229
1.29k
      AU.addPreserved<LoopInfoWrapperPass>();
230
1.29k
      AU.setPreservesCFG();
231
1.29k
    }
232
233
3.78k
    bool runOnLoop(Loop *TheLoop, LPPassManager &) override {
234
3.78k
      if (DisableParallelDSP)
235
0
        return false;
236
3.78k
      if (skipLoop(TheLoop))
237
0
        return false;
238
3.78k
239
3.78k
      L = TheLoop;
240
3.78k
      SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
241
3.78k
      AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
242
3.78k
      TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
243
3.78k
      DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
244
3.78k
      LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
245
3.78k
      auto &TPC = getAnalysis<TargetPassConfig>();
246
3.78k
247
3.78k
      BasicBlock *Header = TheLoop->getHeader();
248
3.78k
      if (!Header)
249
0
        return false;
250
3.78k
251
3.78k
      // TODO: We assume the loop header and latch to be the same block.
252
3.78k
      // This is not a fundamental restriction, but lifting this would just
253
3.78k
      // require more work to do the transformation and then patch up the CFG.
254
3.78k
      if (Header != TheLoop->getLoopLatch()) {
255
2.06k
        LLVM_DEBUG(dbgs() << "The loop header is not the loop latch: not "
256
2.06k
                             "running pass ARMParallelDSP\n");
257
2.06k
        return false;
258
2.06k
      }
259
1.71k
260
1.71k
      if (!TheLoop->getLoopPreheader())
261
12
        InsertPreheaderForLoop(L, DT, LI, nullptr, true);
262
1.71k
263
1.71k
      Function &F = *Header->getParent();
264
1.71k
      M = F.getParent();
265
1.71k
      DL = &M->getDataLayout();
266
1.71k
267
1.71k
      auto &TM = TPC.getTM<TargetMachine>();
268
1.71k
      auto *ST = &TM.getSubtarget<ARMSubtarget>(F);
269
1.71k
270
1.71k
      if (!ST->allowsUnalignedMem()) {
271
69
        LLVM_DEBUG(dbgs() << "Unaligned memory access not supported: not "
272
69
                             "running pass ARMParallelDSP\n");
273
69
        return false;
274
69
      }
275
1.65k
276
1.65k
      if (!ST->hasDSP()) {
277
24
        LLVM_DEBUG(dbgs() << "DSP extension not enabled: not running pass "
278
24
                             "ARMParallelDSP\n");
279
24
        return false;
280
24
      }
281
1.62k
282
1.62k
      if (!ST->isLittle()) {
283
13
        LLVM_DEBUG(dbgs() << "Only supporting little endian: not running pass "
284
13
                          << "ARMParallelDSP\n");
285
13
        return false;
286
13
      }
287
1.61k
288
1.61k
      LoopAccessInfo LAI(L, SE, TLI, AA, DT, LI);
289
1.61k
290
1.61k
      LLVM_DEBUG(dbgs() << "\n== Parallel DSP pass ==\n");
291
1.61k
      LLVM_DEBUG(dbgs() << " - " << F.getName() << "\n\n");
292
1.61k
293
1.61k
      if (!RecordMemoryOps(Header)) {
294
1.56k
        LLVM_DEBUG(dbgs() << " - No sequential loads found.\n");
295
1.56k
        return false;
296
1.56k
      }
297
45
298
45
      bool Changes = MatchSMLAD(L);
299
45
      return Changes;
300
45
    }
301
  };
302
}
303
304
template<typename MemInst>
305
static bool AreSequentialAccesses(MemInst *MemOp0, MemInst *MemOp1,
306
2.52k
                                  const DataLayout &DL, ScalarEvolution &SE) {
307
2.52k
  if (isConsecutiveAccess(MemOp0, MemOp1, DL, SE))
308
245
    return true;
309
2.28k
  return false;
310
2.28k
}
311
312
bool ARMParallelDSP::AreSequentialLoads(LoadInst *Ld0, LoadInst *Ld1,
313
308
                                        MemInstList &VecMem) {
314
308
  if (!Ld0 || !Ld1)
315
0
    return false;
316
308
317
308
  if (!LoadPairs.count(Ld0) || 
LoadPairs[Ld0] != Ld1248
)
318
190
    return false;
319
118
320
118
  LLVM_DEBUG(dbgs() << "Loads are sequential and valid:\n";
321
118
    dbgs() << "Ld0:"; Ld0->dump();
322
118
    dbgs() << "Ld1:"; Ld1->dump();
323
118
  );
324
118
325
118
  VecMem.clear();
326
118
  VecMem.push_back(Ld0);
327
118
  VecMem.push_back(Ld1);
328
118
  return true;
329
118
}
330
331
// MaxBitwidth: the maximum supported bitwidth of the elements in the DSP
332
// instructions, which is set to 16. So here we should collect all i8 and i16
333
// narrow operations.
334
// TODO: we currently only collect i16, and will support i8 later, so that's
335
// why we check that types are equal to MaxBitWidth, and not <= MaxBitWidth.
336
template<unsigned MaxBitWidth>
337
385
bool ARMParallelDSP::IsNarrowSequence(Value *V, ValueList &VL) {
338
385
  ConstantInt *CInt;
339
385
340
385
  if (match(V, m_ConstantInt(CInt))) {
341
0
    // TODO: if a constant is used, it needs to fit within the bit width.
342
0
    return false;
343
0
  }
344
385
345
385
  auto *I = dyn_cast<Instruction>(V);
346
385
  if (!I)
347
0
    return false;
348
385
349
385
  Value *Val, *LHS, *RHS;
350
385
  if (match(V, m_Trunc(m_Value(Val)))) {
351
0
    if (cast<TruncInst>(I)->getDestTy()->getIntegerBitWidth() == MaxBitWidth)
352
0
      return IsNarrowSequence<MaxBitWidth>(Val, VL);
353
385
  } else if (match(V, m_Add(m_Value(LHS), m_Value(RHS)))) {
354
0
    // TODO: we need to implement sadd16/sadd8 for this, which enables to
355
0
    // also do the rewrite for smlad8.ll, but it is unsupported for now.
356
0
    return false;
357
385
  } else if (match(V, m_ZExtOrSExt(m_Value(Val)))) {
358
385
    if (cast<CastInst>(I)->getSrcTy()->getIntegerBitWidth() != MaxBitWidth)
359
6
      return false;
360
379
361
379
    if (match(Val, m_Load(m_Value()))) {
362
379
      auto *Ld = cast<LoadInst>(Val);
363
379
364
379
      // Check that these load could be paired.
365
379
      if (!LoadPairs.count(Ld) && 
!OffsetLoads.count(Ld)110
)
366
43
        return false;
367
336
368
336
      VL.push_back(Val);
369
336
      VL.push_back(I);
370
336
      return true;
371
336
    }
372
379
  }
373
0
  return false;
374
0
}
375
376
/// Iterate through the block and record base, offset pairs of loads which can
377
/// be widened into a single load.
378
1.61k
bool ARMParallelDSP::RecordMemoryOps(BasicBlock *BB) {
379
1.61k
  SmallVector<LoadInst*, 8> Loads;
380
1.61k
  SmallVector<Instruction*, 8> Writes;
381
1.61k
382
1.61k
  // Collect loads and instruction that may write to memory. For now we only
383
1.61k
  // record loads which are simple, sign-extended and have a single user.
384
1.61k
  // TODO: Allow zero-extended loads.
385
16.6k
  for (auto &I : *BB) {
386
16.6k
    if (I.mayWriteToMemory())
387
2.12k
      Writes.push_back(&I);
388
16.6k
    auto *Ld = dyn_cast<LoadInst>(&I);
389
16.6k
    if (!Ld || 
!Ld->isSimple()1.71k
||
390
16.6k
        
!Ld->hasOneUse()1.69k
||
!isa<SExtInst>(Ld->user_back())1.56k
)
391
16.1k
      continue;
392
461
    Loads.push_back(Ld);
393
461
  }
394
1.61k
395
1.61k
  using InstSet = std::set<Instruction*>;
396
1.61k
  using DepMap = std::map<Instruction*, InstSet>;
397
1.61k
  DepMap RAWDeps;
398
1.61k
399
1.61k
  // Record any writes that may alias a load.
400
1.61k
  const auto Size = LocationSize::unknown();
401
1.61k
  for (auto Read : Loads) {
402
461
    for (auto Write : Writes) {
403
274
      MemoryLocation ReadLoc =
404
274
        MemoryLocation(Read->getPointerOperand(), Size);
405
274
406
274
      if (!isModOrRefSet(intersectModRef(AA->getModRefInfo(Write, ReadLoc),
407
274
          ModRefInfo::ModRef)))
408
30
        continue;
409
244
      if (DT->dominates(Write, Read))
410
87
        RAWDeps[Read].insert(Write);
411
244
    }
412
461
  }
413
1.61k
414
1.61k
  // Check whether there's not a write between the two loads which would
415
1.61k
  // prevent them from being safely merged.
416
1.61k
  auto SafeToPair = [&](LoadInst *Base, LoadInst *Offset) {
417
245
    LoadInst *Dominator = DT->dominates(Base, Offset) ? 
Base227
:
Offset18
;
418
245
    LoadInst *Dominated = DT->dominates(Base, Offset) ? 
Offset227
:
Base18
;
419
245
420
245
    if (RAWDeps.count(Dominated)) {
421
48
      InstSet &WritesBefore = RAWDeps[Dominated];
422
48
423
69
      for (auto Before : WritesBefore) {
424
69
425
69
        // We can't move the second load backward, past a write, to merge
426
69
        // with the first load.
427
69
        if (DT->dominates(Dominator, Before))
428
43
          return false;
429
69
      }
430
48
    }
431
245
    
return true202
;
432
245
  };
433
1.61k
434
1.61k
  // Record base, offset load pairs.
435
1.61k
  for (auto *Base : Loads) {
436
2.96k
    for (auto *Offset : Loads) {
437
2.96k
      if (Base == Offset)
438
443
        continue;
439
2.52k
440
2.52k
      if (AreSequentialAccesses<LoadInst>(Base, Offset, *DL, *SE) &&
441
2.52k
          
SafeToPair(Base, Offset)245
) {
442
202
        LoadPairs[Base] = Offset;
443
202
        OffsetLoads.insert(Offset);
444
202
        break;
445
202
      }
446
2.52k
    }
447
461
  }
448
1.61k
449
1.61k
  LLVM_DEBUG(if (!LoadPairs.empty()) {
450
1.61k
               dbgs() << "Consecutive load pairs:\n";
451
1.61k
               for (auto &MapIt : LoadPairs) {
452
1.61k
                 LLVM_DEBUG(dbgs() << *MapIt.first << ", "
453
1.61k
                            << *MapIt.second << "\n");
454
1.61k
               }
455
1.61k
             });
456
1.61k
  return LoadPairs.size() > 1;
457
1.61k
}
458
459
// Loop Pass that needs to identify integer add/sub reductions of 16-bit vector
460
// multiplications.
461
// To use SMLAD:
462
// 1) we first need to find integer add then look for this pattern:
463
//
464
// acc0 = ...
465
// ld0 = load i16
466
// sext0 = sext i16 %ld0 to i32
467
// ld1 = load i16
468
// sext1 = sext i16 %ld1 to i32
469
// mul0 = mul %sext0, %sext1
470
// ld2 = load i16
471
// sext2 = sext i16 %ld2 to i32
472
// ld3 = load i16
473
// sext3 = sext i16 %ld3 to i32
474
// mul1 = mul i32 %sext2, %sext3
475
// add0 = add i32 %mul0, %acc0
476
// acc1 = add i32 %add0, %mul1
477
//
478
// Which can be selected to:
479
//
480
// ldr r0
481
// ldr r1
482
// smlad r2, r0, r1, r2
483
//
484
// If constants are used instead of loads, these will need to be hoisted
485
// out and into a register.
486
//
487
// If loop invariants are used instead of loads, these need to be packed
488
// before the loop begins.
489
//
490
45
bool ARMParallelDSP::MatchSMLAD(Loop *L) {
491
45
  // Search recursively back through the operands to find a tree of values that
492
45
  // form a multiply-accumulate chain. The search records the Add and Mul
493
45
  // instructions that form the reduction and allows us to find a single value
494
45
  // to be used as the initial input to the accumlator.
495
45
  std::function<bool(Value*, Reduction&)> Search = [&]
496
683
    (Value *V, Reduction &R) -> bool {
497
683
498
683
    // If we find a non-instruction, try to use it as the initial accumulator
499
683
    // value. This may have already been found during the search in which case
500
683
    // this function will return false, signaling a search fail.
501
683
    auto *I = dyn_cast<Instruction>(V);
502
683
    if (!I)
503
50
      return R.InsertAcc(V);
504
633
505
633
    switch (I->getOpcode()) {
506
633
    default:
507
9
      break;
508
633
    case Instruction::PHI:
509
134
      // Could be the accumulator value.
510
134
      return R.InsertAcc(V);
511
633
    case Instruction::Add: {
512
260
      // Adds should be adding together two muls, or another add and a mul to
513
260
      // be within the mac chain. One of the operands may also be the
514
260
      // accumulator value at which point we should stop searching.
515
260
      bool ValidLHS = Search(I->getOperand(0), R);
516
260
      bool ValidRHS = Search(I->getOperand(1), R);
517
260
      if (!ValidLHS && 
!ValidLHS64
)
518
64
        return false;
519
196
      else if (ValidLHS && ValidRHS) {
520
145
        R.InsertAdd(I);
521
145
        return true;
522
145
      } else {
523
51
        R.InsertAdd(I);
524
51
        return R.InsertAcc(I);
525
51
      }
526
0
    }
527
205
    case Instruction::Mul: {
528
205
      Value *MulOp0 = I->getOperand(0);
529
205
      Value *MulOp1 = I->getOperand(1);
530
205
      if (isa<SExtInst>(MulOp0) && 
isa<SExtInst>(MulOp1)202
) {
531
202
        ValueList LHS;
532
202
        ValueList RHS;
533
202
        if (IsNarrowSequence<16>(MulOp0, LHS) &&
534
202
            
IsNarrowSequence<16>(MulOp1, RHS)183
) {
535
153
          R.InsertMul(I, LHS, RHS);
536
153
          return true;
537
153
        }
538
52
      }
539
52
      return false;
540
52
    }
541
52
    case Instruction::SExt:
542
25
      return Search(I->getOperand(0), R);
543
9
    }
544
9
    return false;
545
9
  };
546
45
547
45
  bool Changed = false;
548
45
  SmallPtrSet<Instruction*, 4> AllAdds;
549
45
  BasicBlock *Latch = L->getLoopLatch();
550
45
551
2.10k
  for (Instruction &I : reverse(*Latch)) {
552
2.10k
    if (I.getOpcode() != Instruction::Add)
553
1.91k
      continue;
554
196
555
196
    if (AllAdds.count(&I))
556
58
      continue;
557
138
558
138
    const auto *Ty = I.getType();
559
138
    if (!Ty->isIntegerTy(32) && 
!Ty->isIntegerTy(64)17
)
560
0
      continue;
561
138
562
138
    Reduction R(&I);
563
138
    if (!Search(&I, R))
564
86
      continue;
565
52
566
52
    if (!CreateParallelPairs(R))
567
18
      continue;
568
34
569
34
    InsertParallelMACs(R);
570
34
    Changed = true;
571
34
    AllAdds.insert(R.getAdds().begin(), R.getAdds().end());
572
34
  }
573
45
574
45
  return Changed;
575
45
}
576
577
52
bool ARMParallelDSP::CreateParallelPairs(Reduction &R) {
578
52
579
52
  // Not enough mul operations to make a pair.
580
52
  if (R.getMuls().size() < 2)
581
6
    return false;
582
46
583
46
  // Check that the muls operate directly upon sign extended loads.
584
123
  
for (auto &MulChain : R.getMuls())46
{
585
123
    // A mul has 2 operands, and a narrow op consist of sext and a load; thus
586
123
    // we expect at least 4 items in this operand value list.
587
123
    if (MulChain->size() < 4) {
588
0
      LLVM_DEBUG(dbgs() << "Operand list too short.\n");
589
0
      return false;
590
0
    }
591
123
    MulChain->PopulateLoads();
592
123
    ValueList &LHS = static_cast<BinOpChain*>(MulChain.get())->LHS;
593
123
    ValueList &RHS = static_cast<BinOpChain*>(MulChain.get())->RHS;
594
123
595
123
    // Use +=2 to skip over the expected extend instructions.
596
246
    for (unsigned i = 0, e = LHS.size(); i < e; 
i += 2123
) {
597
123
      if (!isa<LoadInst>(LHS[i]) || !isa<LoadInst>(RHS[i]))
598
0
        return false;
599
123
    }
600
123
  }
601
46
602
135
  
auto CanPair = [&](Reduction &R, BinOpChain *PMul0, BinOpChain *PMul1) 46
{
603
135
    if (!PMul0->AreSymmetrical(PMul1))
604
0
      return false;
605
135
606
135
    // The first elements of each vector should be loads with sexts. If we
607
135
    // find that its two pairs of consecutive loads, then these can be
608
135
    // transformed into two wider loads and the users can be replaced with
609
135
    // DSP intrinsics.
610
224
    
for (unsigned x = 0; 135
x < PMul0->LHS.size();
x += 289
) {
611
135
      auto *Ld0 = dyn_cast<LoadInst>(PMul0->LHS[x]);
612
135
      auto *Ld1 = dyn_cast<LoadInst>(PMul1->LHS[x]);
613
135
      auto *Ld2 = dyn_cast<LoadInst>(PMul0->RHS[x]);
614
135
      auto *Ld3 = dyn_cast<LoadInst>(PMul1->RHS[x]);
615
135
616
135
      if (!Ld0 || !Ld1 || !Ld2 || !Ld3)
617
0
        return false;
618
135
619
135
      LLVM_DEBUG(dbgs() << "Loads:\n"
620
135
                 << " - " << *Ld0 << "\n"
621
135
                 << " - " << *Ld1 << "\n"
622
135
                 << " - " << *Ld2 << "\n"
623
135
                 << " - " << *Ld3 << "\n");
624
135
625
135
      if (AreSequentialLoads(Ld0, Ld1, PMul0->VecLd)) {
626
39
        if (AreSequentialLoads(Ld2, Ld3, PMul1->VecLd)) {
627
34
          LLVM_DEBUG(dbgs() << "OK: found two pairs of parallel loads!\n");
628
34
          R.AddMulPair(PMul0, PMul1);
629
34
          return true;
630
34
        } else 
if (5
AreSequentialLoads(Ld3, Ld2, PMul1->VecLd)5
) {
631
5
          LLVM_DEBUG(dbgs() << "OK: found two pairs of parallel loads!\n");
632
5
          LLVM_DEBUG(dbgs() << "    exchanging Ld2 and Ld3\n");
633
5
          PMul1->Exchange = true;
634
5
          R.AddMulPair(PMul0, PMul1);
635
5
          return true;
636
5
        }
637
96
      } else if (AreSequentialLoads(Ld1, Ld0, PMul0->VecLd) &&
638
96
                 
AreSequentialLoads(Ld2, Ld3, PMul1->VecLd)33
) {
639
7
        LLVM_DEBUG(dbgs() << "OK: found two pairs of parallel loads!\n");
640
7
        LLVM_DEBUG(dbgs() << "    exchanging Ld0 and Ld1\n");
641
7
        LLVM_DEBUG(dbgs() << "    and swapping muls\n");
642
7
        PMul0->Exchange = true;
643
7
        // Only the second operand can be exchanged, so swap the muls.
644
7
        R.AddMulPair(PMul1, PMul0);
645
7
        return true;
646
7
      }
647
135
    }
648
135
    
return false89
;
649
135
  };
650
46
651
46
  OpChainList &Muls = R.getMuls();
652
46
  const unsigned Elems = Muls.size();
653
46
  SmallPtrSet<const Instruction*, 4> Paired;
654
169
  for (unsigned i = 0; i < Elems; 
++i123
) {
655
123
    BinOpChain *PMul0 = static_cast<BinOpChain*>(Muls[i].get());
656
123
    if (Paired.count(PMul0->Root))
657
20
      continue;
658
103
659
306
    
for (unsigned j = 0; 103
j < Elems;
++j203
) {
660
249
      if (i == j)
661
77
        continue;
662
172
663
172
      BinOpChain *PMul1 = static_cast<BinOpChain*>(Muls[j].get());
664
172
      if (Paired.count(PMul1->Root))
665
37
        continue;
666
135
667
135
      const Instruction *Mul0 = PMul0->Root;
668
135
      const Instruction *Mul1 = PMul1->Root;
669
135
      if (Mul0 == Mul1)
670
0
        continue;
671
135
672
135
      assert(PMul0 != PMul1 && "expected different chains");
673
135
674
135
      if (CanPair(R, PMul0, PMul1)) {
675
46
        Paired.insert(Mul0);
676
46
        Paired.insert(Mul1);
677
46
        break;
678
46
      }
679
135
    }
680
103
  }
681
46
  return !R.getMulPairs().empty();
682
46
}
683
684
685
34
void ARMParallelDSP::InsertParallelMACs(Reduction &R) {
686
34
687
34
  auto CreateSMLADCall = [&](SmallVectorImpl<LoadInst*> &VecLd0,
688
34
                             SmallVectorImpl<LoadInst*> &VecLd1,
689
34
                             Value *Acc, bool Exchange,
690
46
                             Instruction *InsertAfter) {
691
46
    // Replace the reduction chain with an intrinsic call
692
46
    IntegerType *Ty = IntegerType::get(M->getContext(), 32);
693
46
    LoadInst *WideLd0 = WideLoads.count(VecLd0[0]) ?
694
46
      
WideLoads[VecLd0[0]]->getLoad()0
: CreateWideLoad(VecLd0, Ty);
695
46
    LoadInst *WideLd1 = WideLoads.count(VecLd1[0]) ?
696
46
      
WideLoads[VecLd1[0]]->getLoad()0
: CreateWideLoad(VecLd1, Ty);
697
46
698
46
    Value* Args[] = { WideLd0, WideLd1, Acc };
699
46
    Function *SMLAD = nullptr;
700
46
    if (Exchange)
701
12
      SMLAD = Acc->getType()->isIntegerTy(32) ?
702
4
        Intrinsic::getDeclaration(M, Intrinsic::arm_smladx) :
703
12
        
Intrinsic::getDeclaration(M, Intrinsic::arm_smlaldx)8
;
704
34
    else
705
34
      SMLAD = Acc->getType()->isIntegerTy(32) ?
706
26
        Intrinsic::getDeclaration(M, Intrinsic::arm_smlad) :
707
34
        
Intrinsic::getDeclaration(M, Intrinsic::arm_smlald)8
;
708
46
709
46
    IRBuilder<NoFolder> Builder(InsertAfter->getParent(),
710
46
                                ++BasicBlock::iterator(InsertAfter));
711
46
    Instruction *Call = Builder.CreateCall(SMLAD, Args);
712
46
    NumSMLAD++;
713
46
    return Call;
714
46
  };
715
34
716
34
  Instruction *InsertAfter = R.getRoot();
717
34
  Value *Acc = R.getAccumulator();
718
34
  if (!Acc)
719
1
    Acc = ConstantInt::get(IntegerType::get(M->getContext(), 32), 0);
720
34
721
34
  LLVM_DEBUG(dbgs() << "Root: " << *InsertAfter << "\n"
722
34
             << "Acc: " << *Acc << "\n");
723
46
  for (auto &Pair : R.getMulPairs()) {
724
46
    BinOpChain *PMul0 = Pair.first;
725
46
    BinOpChain *PMul1 = Pair.second;
726
46
    LLVM_DEBUG(dbgs() << "Muls:\n"
727
46
               << "- " << *PMul0->Root << "\n"
728
46
               << "- " << *PMul1->Root << "\n");
729
46
730
46
    Acc = CreateSMLADCall(PMul0->VecLd, PMul1->VecLd, Acc, PMul1->Exchange,
731
46
                          InsertAfter);
732
46
    InsertAfter = cast<Instruction>(Acc);
733
46
  }
734
34
  R.UpdateRoot(cast<Instruction>(Acc));
735
34
}
736
737
LoadInst* ARMParallelDSP::CreateWideLoad(SmallVectorImpl<LoadInst*> &Loads,
738
92
                                         IntegerType *LoadTy) {
739
92
  assert(Loads.size() == 2 && "currently only support widening two loads");
740
92
741
92
  LoadInst *Base = Loads[0];
742
92
  LoadInst *Offset = Loads[1];
743
92
744
92
  Instruction *BaseSExt = dyn_cast<SExtInst>(Base->user_back());
745
92
  Instruction *OffsetSExt = dyn_cast<SExtInst>(Offset->user_back());
746
92
747
92
  assert((BaseSExt && OffsetSExt)
748
92
         && "Loads should have a single, extending, user");
749
92
750
92
  std::function<void(Value*, Value*)> MoveBefore =
751
202
    [&](Value *A, Value *B) -> void {
752
202
      if (!isa<Instruction>(A) || !isa<Instruction>(B))
753
0
        return;
754
202
755
202
      auto *Source = cast<Instruction>(A);
756
202
      auto *Sink = cast<Instruction>(B);
757
202
758
202
      if (DT->dominates(Source, Sink) ||
759
202
          
Source->getParent() != Sink->getParent()9
||
760
202
          
isa<PHINode>(Source)9
||
isa<PHINode>(Sink)9
)
761
193
        return;
762
9
763
9
      Source->moveBefore(Sink);
764
9
      for (auto &U : Source->uses())
765
18
        MoveBefore(Source, U.getUser());
766
9
    };
767
92
768
92
  // Insert the load at the point of the original dominating load.
769
92
  LoadInst *DomLoad = DT->dominates(Base, Offset) ? 
Base80
:
Offset12
;
770
92
  IRBuilder<NoFolder> IRB(DomLoad->getParent(),
771
92
                          ++BasicBlock::iterator(DomLoad));
772
92
773
92
  // Bitcast the pointer to a wider type and create the wide load, while making
774
92
  // sure to maintain the original alignment as this prevents ldrd from being
775
92
  // generated when it could be illegal due to memory alignment.
776
92
  const unsigned AddrSpace = DomLoad->getPointerAddressSpace();
777
92
  Value *VecPtr = IRB.CreateBitCast(Base->getPointerOperand(),
778
92
                                    LoadTy->getPointerTo(AddrSpace));
779
92
  LoadInst *WideLoad = IRB.CreateAlignedLoad(LoadTy, VecPtr,
780
92
                                             Base->getAlignment());
781
92
782
92
  // Make sure everything is in the correct order in the basic block.
783
92
  MoveBefore(Base->getPointerOperand(), VecPtr);
784
92
  MoveBefore(VecPtr, WideLoad);
785
92
786
92
  // From the wide load, create two values that equal the original two loads.
787
92
  // Loads[0] needs trunc while Loads[1] needs a lshr and trunc.
788
92
  // TODO: Support big-endian as well.
789
92
  Value *Bottom = IRB.CreateTrunc(WideLoad, Base->getType());
790
92
  BaseSExt->setOperand(0, Bottom);
791
92
792
92
  IntegerType *OffsetTy = cast<IntegerType>(Offset->getType());
793
92
  Value *ShiftVal = ConstantInt::get(LoadTy, OffsetTy->getBitWidth());
794
92
  Value *Top = IRB.CreateLShr(WideLoad, ShiftVal);
795
92
  Value *Trunc = IRB.CreateTrunc(Top, OffsetTy);
796
92
  OffsetSExt->setOperand(0, Trunc);
797
92
798
92
  WideLoads.emplace(std::make_pair(Base,
799
92
                                   make_unique<WidenedLoad>(Loads, WideLoad)));
800
92
  return WideLoad;
801
92
}
802
803
// Compare the value lists in Other to this chain.
804
135
bool BinOpChain::AreSymmetrical(BinOpChain *Other) {
805
135
  // Element-by-element comparison of Value lists returning true if they are
806
135
  // instructions with the same opcode or constants with the same value.
807
135
  auto CompareValueList = [](const ValueList &VL0,
808
270
                             const ValueList &VL1) {
809
270
    if (VL0.size() != VL1.size()) {
810
0
      LLVM_DEBUG(dbgs() << "Muls are mismatching operand list lengths: "
811
0
                        << VL0.size() << " != " << VL1.size() << "\n");
812
0
      return false;
813
0
    }
814
270
815
270
    const unsigned Pairs = VL0.size();
816
270
817
810
    for (unsigned i = 0; i < Pairs; 
++i540
) {
818
540
      const Value *V0 = VL0[i];
819
540
      const Value *V1 = VL1[i];
820
540
      const auto *Inst0 = dyn_cast<Instruction>(V0);
821
540
      const auto *Inst1 = dyn_cast<Instruction>(V1);
822
540
823
540
      if (!Inst0 || !Inst1)
824
0
        return false;
825
540
826
540
      if (Inst0->isSameOperationAs(Inst1))
827
540
        continue;
828
0
829
0
      const APInt *C0, *C1;
830
0
      if (!(match(V0, m_APInt(C0)) && match(V1, m_APInt(C1)) && C0 == C1))
831
0
        return false;
832
0
    }
833
270
834
270
    return true;
835
270
  };
836
135
837
135
  return CompareValueList(LHS, Other->LHS) &&
838
135
         CompareValueList(RHS, Other->RHS);
839
135
}
840
841
1.26k
Pass *llvm::createARMParallelDSPPass() {
842
1.26k
  return new ARMParallelDSP();
843
1.26k
}
844
845
char ARMParallelDSP::ID = 0;
846
847
101k
INITIALIZE_PASS_BEGIN(ARMParallelDSP, "arm-parallel-dsp",
848
101k
                "Transform loops to use DSP intrinsics", false, false)
849
101k
INITIALIZE_PASS_END(ARMParallelDSP, "arm-parallel-dsp",
850
                "Transform loops to use DSP intrinsics", false, false)