summaryrefslogtreecommitdiff
path: root/contrib/llvm-project/llvm/lib/Target/ARM/ARMParallelDSP.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'contrib/llvm-project/llvm/lib/Target/ARM/ARMParallelDSP.cpp')
-rw-r--r--contrib/llvm-project/llvm/lib/Target/ARM/ARMParallelDSP.cpp847
1 files changed, 847 insertions, 0 deletions
diff --git a/contrib/llvm-project/llvm/lib/Target/ARM/ARMParallelDSP.cpp b/contrib/llvm-project/llvm/lib/Target/ARM/ARMParallelDSP.cpp
new file mode 100644
index 000000000000..5389d09bf7d7
--- /dev/null
+++ b/contrib/llvm-project/llvm/lib/Target/ARM/ARMParallelDSP.cpp
@@ -0,0 +1,847 @@
+//===- ParallelDSP.cpp - Parallel DSP Pass --------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+/// \file
+/// Armv6 introduced instructions to perform 32-bit SIMD operations. The
+/// purpose of this pass is do some IR pattern matching to create ACLE
+/// DSP intrinsics, which map on these 32-bit SIMD operations.
+/// This pass runs only when unaligned accesses is supported/enabled.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/LoopAccessAnalysis.h"
+#include "llvm/Analysis/LoopPass.h"
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/NoFolder.h"
+#include "llvm/Transforms/Scalar.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/LoopUtils.h"
+#include "llvm/Pass.h"
+#include "llvm/PassRegistry.h"
+#include "llvm/PassSupport.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/IR/PatternMatch.h"
+#include "llvm/CodeGen/TargetPassConfig.h"
+#include "ARM.h"
+#include "ARMSubtarget.h"
+
+using namespace llvm;
+using namespace PatternMatch;
+
+#define DEBUG_TYPE "arm-parallel-dsp"
+
+STATISTIC(NumSMLAD , "Number of smlad instructions generated");
+
+static cl::opt<bool>
+DisableParallelDSP("disable-arm-parallel-dsp", cl::Hidden, cl::init(false),
+ cl::desc("Disable the ARM Parallel DSP pass"));
+
+namespace {
+ struct OpChain;
+ struct BinOpChain;
+ class Reduction;
+
+ using OpChainList = SmallVector<std::unique_ptr<OpChain>, 8>;
+ using ReductionList = SmallVector<Reduction, 8>;
+ using ValueList = SmallVector<Value*, 8>;
+ using MemInstList = SmallVector<LoadInst*, 8>;
+ using PMACPair = std::pair<BinOpChain*,BinOpChain*>;
+ using PMACPairList = SmallVector<PMACPair, 8>;
+ using Instructions = SmallVector<Instruction*,16>;
+ using MemLocList = SmallVector<MemoryLocation, 4>;
+
+ struct OpChain {
+ Instruction *Root;
+ ValueList AllValues;
+ MemInstList VecLd; // List of all load instructions.
+ MemInstList Loads;
+ bool ReadOnly = true;
+
+ OpChain(Instruction *I, ValueList &vl) : Root(I), AllValues(vl) { }
+ virtual ~OpChain() = default;
+
+ void PopulateLoads() {
+ for (auto *V : AllValues) {
+ if (auto *Ld = dyn_cast<LoadInst>(V))
+ Loads.push_back(Ld);
+ }
+ }
+
+ unsigned size() const { return AllValues.size(); }
+ };
+
+ // 'BinOpChain' holds the multiplication instructions that are candidates
+ // for parallel execution.
+ struct BinOpChain : public OpChain {
+ ValueList LHS; // List of all (narrow) left hand operands.
+ ValueList RHS; // List of all (narrow) right hand operands.
+ bool Exchange = false;
+
+ BinOpChain(Instruction *I, ValueList &lhs, ValueList &rhs) :
+ OpChain(I, lhs), LHS(lhs), RHS(rhs) {
+ for (auto *V : RHS)
+ AllValues.push_back(V);
+ }
+
+ bool AreSymmetrical(BinOpChain *Other);
+ };
+
+ /// Represent a sequence of multiply-accumulate operations with the aim to
+ /// perform the multiplications in parallel.
+ class Reduction {
+ Instruction *Root = nullptr;
+ Value *Acc = nullptr;
+ OpChainList Muls;
+ PMACPairList MulPairs;
+ SmallPtrSet<Instruction*, 4> Adds;
+
+ public:
+ Reduction() = delete;
+
+ Reduction (Instruction *Add) : Root(Add) { }
+
+ /// Record an Add instruction that is a part of the this reduction.
+ void InsertAdd(Instruction *I) { Adds.insert(I); }
+
+ /// Record a BinOpChain, rooted at a Mul instruction, that is a part of
+ /// this reduction.
+ void InsertMul(Instruction *I, ValueList &LHS, ValueList &RHS) {
+ Muls.push_back(make_unique<BinOpChain>(I, LHS, RHS));
+ }
+
+ /// Add the incoming accumulator value, returns true if a value had not
+ /// already been added. Returning false signals to the user that this
+ /// reduction already has a value to initialise the accumulator.
+ bool InsertAcc(Value *V) {
+ if (Acc)
+ return false;
+ Acc = V;
+ return true;
+ }
+
+ /// Set two BinOpChains, rooted at muls, that can be executed as a single
+ /// parallel operation.
+ void AddMulPair(BinOpChain *Mul0, BinOpChain *Mul1) {
+ MulPairs.push_back(std::make_pair(Mul0, Mul1));
+ }
+
+ /// Return true if enough mul operations are found that can be executed in
+ /// parallel.
+ bool CreateParallelPairs();
+
+ /// Return the add instruction which is the root of the reduction.
+ Instruction *getRoot() { return Root; }
+
+ /// Return the incoming value to be accumulated. This maybe null.
+ Value *getAccumulator() { return Acc; }
+
+ /// Return the set of adds that comprise the reduction.
+ SmallPtrSetImpl<Instruction*> &getAdds() { return Adds; }
+
+ /// Return the BinOpChain, rooted at mul instruction, that comprise the
+ /// the reduction.
+ OpChainList &getMuls() { return Muls; }
+
+ /// Return the BinOpChain, rooted at mul instructions, that have been
+ /// paired for parallel execution.
+ PMACPairList &getMulPairs() { return MulPairs; }
+
+ /// To finalise, replace the uses of the root with the intrinsic call.
+ void UpdateRoot(Instruction *SMLAD) {
+ Root->replaceAllUsesWith(SMLAD);
+ }
+ };
+
+ class WidenedLoad {
+ LoadInst *NewLd = nullptr;
+ SmallVector<LoadInst*, 4> Loads;
+
+ public:
+ WidenedLoad(SmallVectorImpl<LoadInst*> &Lds, LoadInst *Wide)
+ : NewLd(Wide) {
+ for (auto *I : Lds)
+ Loads.push_back(I);
+ }
+ LoadInst *getLoad() {
+ return NewLd;
+ }
+ };
+
+ class ARMParallelDSP : public LoopPass {
+ ScalarEvolution *SE;
+ AliasAnalysis *AA;
+ TargetLibraryInfo *TLI;
+ DominatorTree *DT;
+ LoopInfo *LI;
+ Loop *L;
+ const DataLayout *DL;
+ Module *M;
+ std::map<LoadInst*, LoadInst*> LoadPairs;
+ SmallPtrSet<LoadInst*, 4> OffsetLoads;
+ std::map<LoadInst*, std::unique_ptr<WidenedLoad>> WideLoads;
+
+ template<unsigned>
+ bool IsNarrowSequence(Value *V, ValueList &VL);
+
+ bool RecordMemoryOps(BasicBlock *BB);
+ void InsertParallelMACs(Reduction &Reduction);
+ bool AreSequentialLoads(LoadInst *Ld0, LoadInst *Ld1, MemInstList &VecMem);
+ LoadInst* CreateWideLoad(SmallVectorImpl<LoadInst*> &Loads,
+ IntegerType *LoadTy);
+ bool CreateParallelPairs(Reduction &R);
+
+ /// Try to match and generate: SMLAD, SMLADX - Signed Multiply Accumulate
+ /// Dual performs two signed 16x16-bit multiplications. It adds the
+ /// products to a 32-bit accumulate operand. Optionally, the instruction can
+ /// exchange the halfwords of the second operand before performing the
+ /// arithmetic.
+ bool MatchSMLAD(Loop *L);
+
+ public:
+ static char ID;
+
+ ARMParallelDSP() : LoopPass(ID) { }
+
+ bool doInitialization(Loop *L, LPPassManager &LPM) override {
+ LoadPairs.clear();
+ WideLoads.clear();
+ return true;
+ }
+
+ void getAnalysisUsage(AnalysisUsage &AU) const override {
+ LoopPass::getAnalysisUsage(AU);
+ AU.addRequired<AssumptionCacheTracker>();
+ AU.addRequired<ScalarEvolutionWrapperPass>();
+ AU.addRequired<AAResultsWrapperPass>();
+ AU.addRequired<TargetLibraryInfoWrapperPass>();
+ AU.addRequired<LoopInfoWrapperPass>();
+ AU.addRequired<DominatorTreeWrapperPass>();
+ AU.addRequired<TargetPassConfig>();
+ AU.addPreserved<LoopInfoWrapperPass>();
+ AU.setPreservesCFG();
+ }
+
+ bool runOnLoop(Loop *TheLoop, LPPassManager &) override {
+ if (DisableParallelDSP)
+ return false;
+ L = TheLoop;
+ SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
+ AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
+ TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
+ DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+ LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
+ auto &TPC = getAnalysis<TargetPassConfig>();
+
+ BasicBlock *Header = TheLoop->getHeader();
+ if (!Header)
+ return false;
+
+ // TODO: We assume the loop header and latch to be the same block.
+ // This is not a fundamental restriction, but lifting this would just
+ // require more work to do the transformation and then patch up the CFG.
+ if (Header != TheLoop->getLoopLatch()) {
+ LLVM_DEBUG(dbgs() << "The loop header is not the loop latch: not "
+ "running pass ARMParallelDSP\n");
+ return false;
+ }
+
+ if (!TheLoop->getLoopPreheader())
+ InsertPreheaderForLoop(L, DT, LI, nullptr, true);
+
+ Function &F = *Header->getParent();
+ M = F.getParent();
+ DL = &M->getDataLayout();
+
+ auto &TM = TPC.getTM<TargetMachine>();
+ auto *ST = &TM.getSubtarget<ARMSubtarget>(F);
+
+ if (!ST->allowsUnalignedMem()) {
+ LLVM_DEBUG(dbgs() << "Unaligned memory access not supported: not "
+ "running pass ARMParallelDSP\n");
+ return false;
+ }
+
+ if (!ST->hasDSP()) {
+ LLVM_DEBUG(dbgs() << "DSP extension not enabled: not running pass "
+ "ARMParallelDSP\n");
+ return false;
+ }
+
+ if (!ST->isLittle()) {
+ LLVM_DEBUG(dbgs() << "Only supporting little endian: not running pass "
+ << "ARMParallelDSP\n");
+ return false;
+ }
+
+ LoopAccessInfo LAI(L, SE, TLI, AA, DT, LI);
+
+ LLVM_DEBUG(dbgs() << "\n== Parallel DSP pass ==\n");
+ LLVM_DEBUG(dbgs() << " - " << F.getName() << "\n\n");
+
+ if (!RecordMemoryOps(Header)) {
+ LLVM_DEBUG(dbgs() << " - No sequential loads found.\n");
+ return false;
+ }
+
+ bool Changes = MatchSMLAD(L);
+ return Changes;
+ }
+ };
+}
+
+template<typename MemInst>
+static bool AreSequentialAccesses(MemInst *MemOp0, MemInst *MemOp1,
+ const DataLayout &DL, ScalarEvolution &SE) {
+ if (isConsecutiveAccess(MemOp0, MemOp1, DL, SE))
+ return true;
+ return false;
+}
+
+bool ARMParallelDSP::AreSequentialLoads(LoadInst *Ld0, LoadInst *Ld1,
+ MemInstList &VecMem) {
+ if (!Ld0 || !Ld1)
+ return false;
+
+ if (!LoadPairs.count(Ld0) || LoadPairs[Ld0] != Ld1)
+ return false;
+
+ LLVM_DEBUG(dbgs() << "Loads are sequential and valid:\n";
+ dbgs() << "Ld0:"; Ld0->dump();
+ dbgs() << "Ld1:"; Ld1->dump();
+ );
+
+ VecMem.clear();
+ VecMem.push_back(Ld0);
+ VecMem.push_back(Ld1);
+ return true;
+}
+
+// MaxBitwidth: the maximum supported bitwidth of the elements in the DSP
+// instructions, which is set to 16. So here we should collect all i8 and i16
+// narrow operations.
+// TODO: we currently only collect i16, and will support i8 later, so that's
+// why we check that types are equal to MaxBitWidth, and not <= MaxBitWidth.
+template<unsigned MaxBitWidth>
+bool ARMParallelDSP::IsNarrowSequence(Value *V, ValueList &VL) {
+ ConstantInt *CInt;
+
+ if (match(V, m_ConstantInt(CInt))) {
+ // TODO: if a constant is used, it needs to fit within the bit width.
+ return false;
+ }
+
+ auto *I = dyn_cast<Instruction>(V);
+ if (!I)
+ return false;
+
+ Value *Val, *LHS, *RHS;
+ if (match(V, m_Trunc(m_Value(Val)))) {
+ if (cast<TruncInst>(I)->getDestTy()->getIntegerBitWidth() == MaxBitWidth)
+ return IsNarrowSequence<MaxBitWidth>(Val, VL);
+ } else if (match(V, m_Add(m_Value(LHS), m_Value(RHS)))) {
+ // TODO: we need to implement sadd16/sadd8 for this, which enables to
+ // also do the rewrite for smlad8.ll, but it is unsupported for now.
+ return false;
+ } else if (match(V, m_ZExtOrSExt(m_Value(Val)))) {
+ if (cast<CastInst>(I)->getSrcTy()->getIntegerBitWidth() != MaxBitWidth)
+ return false;
+
+ if (match(Val, m_Load(m_Value()))) {
+ auto *Ld = cast<LoadInst>(Val);
+
+ // Check that these load could be paired.
+ if (!LoadPairs.count(Ld) && !OffsetLoads.count(Ld))
+ return false;
+
+ VL.push_back(Val);
+ VL.push_back(I);
+ return true;
+ }
+ }
+ return false;
+}
+
+/// Iterate through the block and record base, offset pairs of loads which can
+/// be widened into a single load.
+bool ARMParallelDSP::RecordMemoryOps(BasicBlock *BB) {
+ SmallVector<LoadInst*, 8> Loads;
+ SmallVector<Instruction*, 8> Writes;
+
+ // Collect loads and instruction that may write to memory. For now we only
+ // record loads which are simple, sign-extended and have a single user.
+ // TODO: Allow zero-extended loads.
+ for (auto &I : *BB) {
+ if (I.mayWriteToMemory())
+ Writes.push_back(&I);
+ auto *Ld = dyn_cast<LoadInst>(&I);
+ if (!Ld || !Ld->isSimple() ||
+ !Ld->hasOneUse() || !isa<SExtInst>(Ld->user_back()))
+ continue;
+ Loads.push_back(Ld);
+ }
+
+ using InstSet = std::set<Instruction*>;
+ using DepMap = std::map<Instruction*, InstSet>;
+ DepMap RAWDeps;
+
+ // Record any writes that may alias a load.
+ const auto Size = LocationSize::unknown();
+ for (auto Read : Loads) {
+ for (auto Write : Writes) {
+ MemoryLocation ReadLoc =
+ MemoryLocation(Read->getPointerOperand(), Size);
+
+ if (!isModOrRefSet(intersectModRef(AA->getModRefInfo(Write, ReadLoc),
+ ModRefInfo::ModRef)))
+ continue;
+ if (DT->dominates(Write, Read))
+ RAWDeps[Read].insert(Write);
+ }
+ }
+
+ // Check whether there's not a write between the two loads which would
+ // prevent them from being safely merged.
+ auto SafeToPair = [&](LoadInst *Base, LoadInst *Offset) {
+ LoadInst *Dominator = DT->dominates(Base, Offset) ? Base : Offset;
+ LoadInst *Dominated = DT->dominates(Base, Offset) ? Offset : Base;
+
+ if (RAWDeps.count(Dominated)) {
+ InstSet &WritesBefore = RAWDeps[Dominated];
+
+ for (auto Before : WritesBefore) {
+
+ // We can't move the second load backward, past a write, to merge
+ // with the first load.
+ if (DT->dominates(Dominator, Before))
+ return false;
+ }
+ }
+ return true;
+ };
+
+ // Record base, offset load pairs.
+ for (auto *Base : Loads) {
+ for (auto *Offset : Loads) {
+ if (Base == Offset)
+ continue;
+
+ if (AreSequentialAccesses<LoadInst>(Base, Offset, *DL, *SE) &&
+ SafeToPair(Base, Offset)) {
+ LoadPairs[Base] = Offset;
+ OffsetLoads.insert(Offset);
+ break;
+ }
+ }
+ }
+
+ LLVM_DEBUG(if (!LoadPairs.empty()) {
+ dbgs() << "Consecutive load pairs:\n";
+ for (auto &MapIt : LoadPairs) {
+ LLVM_DEBUG(dbgs() << *MapIt.first << ", "
+ << *MapIt.second << "\n");
+ }
+ });
+ return LoadPairs.size() > 1;
+}
+
+// Loop Pass that needs to identify integer add/sub reductions of 16-bit vector
+// multiplications.
+// To use SMLAD:
+// 1) we first need to find integer add then look for this pattern:
+//
+// acc0 = ...
+// ld0 = load i16
+// sext0 = sext i16 %ld0 to i32
+// ld1 = load i16
+// sext1 = sext i16 %ld1 to i32
+// mul0 = mul %sext0, %sext1
+// ld2 = load i16
+// sext2 = sext i16 %ld2 to i32
+// ld3 = load i16
+// sext3 = sext i16 %ld3 to i32
+// mul1 = mul i32 %sext2, %sext3
+// add0 = add i32 %mul0, %acc0
+// acc1 = add i32 %add0, %mul1
+//
+// Which can be selected to:
+//
+// ldr r0
+// ldr r1
+// smlad r2, r0, r1, r2
+//
+// If constants are used instead of loads, these will need to be hoisted
+// out and into a register.
+//
+// If loop invariants are used instead of loads, these need to be packed
+// before the loop begins.
+//
+bool ARMParallelDSP::MatchSMLAD(Loop *L) {
+ // Search recursively back through the operands to find a tree of values that
+ // form a multiply-accumulate chain. The search records the Add and Mul
+ // instructions that form the reduction and allows us to find a single value
+ // to be used as the initial input to the accumlator.
+ std::function<bool(Value*, Reduction&)> Search = [&]
+ (Value *V, Reduction &R) -> bool {
+
+ // If we find a non-instruction, try to use it as the initial accumulator
+ // value. This may have already been found during the search in which case
+ // this function will return false, signaling a search fail.
+ auto *I = dyn_cast<Instruction>(V);
+ if (!I)
+ return R.InsertAcc(V);
+
+ switch (I->getOpcode()) {
+ default:
+ break;
+ case Instruction::PHI:
+ // Could be the accumulator value.
+ return R.InsertAcc(V);
+ case Instruction::Add: {
+ // Adds should be adding together two muls, or another add and a mul to
+ // be within the mac chain. One of the operands may also be the
+ // accumulator value at which point we should stop searching.
+ bool ValidLHS = Search(I->getOperand(0), R);
+ bool ValidRHS = Search(I->getOperand(1), R);
+ if (!ValidLHS && !ValidLHS)
+ return false;
+ else if (ValidLHS && ValidRHS) {
+ R.InsertAdd(I);
+ return true;
+ } else {
+ R.InsertAdd(I);
+ return R.InsertAcc(I);
+ }
+ }
+ case Instruction::Mul: {
+ Value *MulOp0 = I->getOperand(0);
+ Value *MulOp1 = I->getOperand(1);
+ if (isa<SExtInst>(MulOp0) && isa<SExtInst>(MulOp1)) {
+ ValueList LHS;
+ ValueList RHS;
+ if (IsNarrowSequence<16>(MulOp0, LHS) &&
+ IsNarrowSequence<16>(MulOp1, RHS)) {
+ R.InsertMul(I, LHS, RHS);
+ return true;
+ }
+ }
+ return false;
+ }
+ case Instruction::SExt:
+ return Search(I->getOperand(0), R);
+ }
+ return false;
+ };
+
+ bool Changed = false;
+ SmallPtrSet<Instruction*, 4> AllAdds;
+ BasicBlock *Latch = L->getLoopLatch();
+
+ for (Instruction &I : reverse(*Latch)) {
+ if (I.getOpcode() != Instruction::Add)
+ continue;
+
+ if (AllAdds.count(&I))
+ continue;
+
+ const auto *Ty = I.getType();
+ if (!Ty->isIntegerTy(32) && !Ty->isIntegerTy(64))
+ continue;
+
+ Reduction R(&I);
+ if (!Search(&I, R))
+ continue;
+
+ if (!CreateParallelPairs(R))
+ continue;
+
+ InsertParallelMACs(R);
+ Changed = true;
+ AllAdds.insert(R.getAdds().begin(), R.getAdds().end());
+ }
+
+ return Changed;
+}
+
+bool ARMParallelDSP::CreateParallelPairs(Reduction &R) {
+
+ // Not enough mul operations to make a pair.
+ if (R.getMuls().size() < 2)
+ return false;
+
+ // Check that the muls operate directly upon sign extended loads.
+ for (auto &MulChain : R.getMuls()) {
+ // A mul has 2 operands, and a narrow op consist of sext and a load; thus
+ // we expect at least 4 items in this operand value list.
+ if (MulChain->size() < 4) {
+ LLVM_DEBUG(dbgs() << "Operand list too short.\n");
+ return false;
+ }
+ MulChain->PopulateLoads();
+ ValueList &LHS = static_cast<BinOpChain*>(MulChain.get())->LHS;
+ ValueList &RHS = static_cast<BinOpChain*>(MulChain.get())->RHS;
+
+ // Use +=2 to skip over the expected extend instructions.
+ for (unsigned i = 0, e = LHS.size(); i < e; i += 2) {
+ if (!isa<LoadInst>(LHS[i]) || !isa<LoadInst>(RHS[i]))
+ return false;
+ }
+ }
+
+ auto CanPair = [&](Reduction &R, BinOpChain *PMul0, BinOpChain *PMul1) {
+ if (!PMul0->AreSymmetrical(PMul1))
+ return false;
+
+ // The first elements of each vector should be loads with sexts. If we
+ // find that its two pairs of consecutive loads, then these can be
+ // transformed into two wider loads and the users can be replaced with
+ // DSP intrinsics.
+ for (unsigned x = 0; x < PMul0->LHS.size(); x += 2) {
+ auto *Ld0 = dyn_cast<LoadInst>(PMul0->LHS[x]);
+ auto *Ld1 = dyn_cast<LoadInst>(PMul1->LHS[x]);
+ auto *Ld2 = dyn_cast<LoadInst>(PMul0->RHS[x]);
+ auto *Ld3 = dyn_cast<LoadInst>(PMul1->RHS[x]);
+
+ if (!Ld0 || !Ld1 || !Ld2 || !Ld3)
+ return false;
+
+ LLVM_DEBUG(dbgs() << "Loads:\n"
+ << " - " << *Ld0 << "\n"
+ << " - " << *Ld1 << "\n"
+ << " - " << *Ld2 << "\n"
+ << " - " << *Ld3 << "\n");
+
+ if (AreSequentialLoads(Ld0, Ld1, PMul0->VecLd)) {
+ if (AreSequentialLoads(Ld2, Ld3, PMul1->VecLd)) {
+ LLVM_DEBUG(dbgs() << "OK: found two pairs of parallel loads!\n");
+ R.AddMulPair(PMul0, PMul1);
+ return true;
+ } else if (AreSequentialLoads(Ld3, Ld2, PMul1->VecLd)) {
+ LLVM_DEBUG(dbgs() << "OK: found two pairs of parallel loads!\n");
+ LLVM_DEBUG(dbgs() << " exchanging Ld2 and Ld3\n");
+ PMul1->Exchange = true;
+ R.AddMulPair(PMul0, PMul1);
+ return true;
+ }
+ } else if (AreSequentialLoads(Ld1, Ld0, PMul0->VecLd) &&
+ AreSequentialLoads(Ld2, Ld3, PMul1->VecLd)) {
+ LLVM_DEBUG(dbgs() << "OK: found two pairs of parallel loads!\n");
+ LLVM_DEBUG(dbgs() << " exchanging Ld0 and Ld1\n");
+ LLVM_DEBUG(dbgs() << " and swapping muls\n");
+ PMul0->Exchange = true;
+ // Only the second operand can be exchanged, so swap the muls.
+ R.AddMulPair(PMul1, PMul0);
+ return true;
+ }
+ }
+ return false;
+ };
+
+ OpChainList &Muls = R.getMuls();
+ const unsigned Elems = Muls.size();
+ SmallPtrSet<const Instruction*, 4> Paired;
+ for (unsigned i = 0; i < Elems; ++i) {
+ BinOpChain *PMul0 = static_cast<BinOpChain*>(Muls[i].get());
+ if (Paired.count(PMul0->Root))
+ continue;
+
+ for (unsigned j = 0; j < Elems; ++j) {
+ if (i == j)
+ continue;
+
+ BinOpChain *PMul1 = static_cast<BinOpChain*>(Muls[j].get());
+ if (Paired.count(PMul1->Root))
+ continue;
+
+ const Instruction *Mul0 = PMul0->Root;
+ const Instruction *Mul1 = PMul1->Root;
+ if (Mul0 == Mul1)
+ continue;
+
+ assert(PMul0 != PMul1 && "expected different chains");
+
+ if (CanPair(R, PMul0, PMul1)) {
+ Paired.insert(Mul0);
+ Paired.insert(Mul1);
+ break;
+ }
+ }
+ }
+ return !R.getMulPairs().empty();
+}
+
+
+void ARMParallelDSP::InsertParallelMACs(Reduction &R) {
+
+ auto CreateSMLADCall = [&](SmallVectorImpl<LoadInst*> &VecLd0,
+ SmallVectorImpl<LoadInst*> &VecLd1,
+ Value *Acc, bool Exchange,
+ Instruction *InsertAfter) {
+ // Replace the reduction chain with an intrinsic call
+ IntegerType *Ty = IntegerType::get(M->getContext(), 32);
+ LoadInst *WideLd0 = WideLoads.count(VecLd0[0]) ?
+ WideLoads[VecLd0[0]]->getLoad() : CreateWideLoad(VecLd0, Ty);
+ LoadInst *WideLd1 = WideLoads.count(VecLd1[0]) ?
+ WideLoads[VecLd1[0]]->getLoad() : CreateWideLoad(VecLd1, Ty);
+
+ Value* Args[] = { WideLd0, WideLd1, Acc };
+ Function *SMLAD = nullptr;
+ if (Exchange)
+ SMLAD = Acc->getType()->isIntegerTy(32) ?
+ Intrinsic::getDeclaration(M, Intrinsic::arm_smladx) :
+ Intrinsic::getDeclaration(M, Intrinsic::arm_smlaldx);
+ else
+ SMLAD = Acc->getType()->isIntegerTy(32) ?
+ Intrinsic::getDeclaration(M, Intrinsic::arm_smlad) :
+ Intrinsic::getDeclaration(M, Intrinsic::arm_smlald);
+
+ IRBuilder<NoFolder> Builder(InsertAfter->getParent(),
+ ++BasicBlock::iterator(InsertAfter));
+ Instruction *Call = Builder.CreateCall(SMLAD, Args);
+ NumSMLAD++;
+ return Call;
+ };
+
+ Instruction *InsertAfter = R.getRoot();
+ Value *Acc = R.getAccumulator();
+ if (!Acc)
+ Acc = ConstantInt::get(IntegerType::get(M->getContext(), 32), 0);
+
+ LLVM_DEBUG(dbgs() << "Root: " << *InsertAfter << "\n"
+ << "Acc: " << *Acc << "\n");
+ for (auto &Pair : R.getMulPairs()) {
+ BinOpChain *PMul0 = Pair.first;
+ BinOpChain *PMul1 = Pair.second;
+ LLVM_DEBUG(dbgs() << "Muls:\n"
+ << "- " << *PMul0->Root << "\n"
+ << "- " << *PMul1->Root << "\n");
+
+ Acc = CreateSMLADCall(PMul0->VecLd, PMul1->VecLd, Acc, PMul1->Exchange,
+ InsertAfter);
+ InsertAfter = cast<Instruction>(Acc);
+ }
+ R.UpdateRoot(cast<Instruction>(Acc));
+}
+
+LoadInst* ARMParallelDSP::CreateWideLoad(SmallVectorImpl<LoadInst*> &Loads,
+ IntegerType *LoadTy) {
+ assert(Loads.size() == 2 && "currently only support widening two loads");
+
+ LoadInst *Base = Loads[0];
+ LoadInst *Offset = Loads[1];
+
+ Instruction *BaseSExt = dyn_cast<SExtInst>(Base->user_back());
+ Instruction *OffsetSExt = dyn_cast<SExtInst>(Offset->user_back());
+
+ assert((BaseSExt && OffsetSExt)
+ && "Loads should have a single, extending, user");
+
+ std::function<void(Value*, Value*)> MoveBefore =
+ [&](Value *A, Value *B) -> void {
+ if (!isa<Instruction>(A) || !isa<Instruction>(B))
+ return;
+
+ auto *Source = cast<Instruction>(A);
+ auto *Sink = cast<Instruction>(B);
+
+ if (DT->dominates(Source, Sink) ||
+ Source->getParent() != Sink->getParent() ||
+ isa<PHINode>(Source) || isa<PHINode>(Sink))
+ return;
+
+ Source->moveBefore(Sink);
+ for (auto &U : Source->uses())
+ MoveBefore(Source, U.getUser());
+ };
+
+ // Insert the load at the point of the original dominating load.
+ LoadInst *DomLoad = DT->dominates(Base, Offset) ? Base : Offset;
+ IRBuilder<NoFolder> IRB(DomLoad->getParent(),
+ ++BasicBlock::iterator(DomLoad));
+
+ // Bitcast the pointer to a wider type and create the wide load, while making
+ // sure to maintain the original alignment as this prevents ldrd from being
+ // generated when it could be illegal due to memory alignment.
+ const unsigned AddrSpace = DomLoad->getPointerAddressSpace();
+ Value *VecPtr = IRB.CreateBitCast(Base->getPointerOperand(),
+ LoadTy->getPointerTo(AddrSpace));
+ LoadInst *WideLoad = IRB.CreateAlignedLoad(LoadTy, VecPtr,
+ Base->getAlignment());
+
+ // Make sure everything is in the correct order in the basic block.
+ MoveBefore(Base->getPointerOperand(), VecPtr);
+ MoveBefore(VecPtr, WideLoad);
+
+ // From the wide load, create two values that equal the original two loads.
+ // Loads[0] needs trunc while Loads[1] needs a lshr and trunc.
+ // TODO: Support big-endian as well.
+ Value *Bottom = IRB.CreateTrunc(WideLoad, Base->getType());
+ BaseSExt->setOperand(0, Bottom);
+
+ IntegerType *OffsetTy = cast<IntegerType>(Offset->getType());
+ Value *ShiftVal = ConstantInt::get(LoadTy, OffsetTy->getBitWidth());
+ Value *Top = IRB.CreateLShr(WideLoad, ShiftVal);
+ Value *Trunc = IRB.CreateTrunc(Top, OffsetTy);
+ OffsetSExt->setOperand(0, Trunc);
+
+ WideLoads.emplace(std::make_pair(Base,
+ make_unique<WidenedLoad>(Loads, WideLoad)));
+ return WideLoad;
+}
+
+// Compare the value lists in Other to this chain.
+bool BinOpChain::AreSymmetrical(BinOpChain *Other) {
+ // Element-by-element comparison of Value lists returning true if they are
+ // instructions with the same opcode or constants with the same value.
+ auto CompareValueList = [](const ValueList &VL0,
+ const ValueList &VL1) {
+ if (VL0.size() != VL1.size()) {
+ LLVM_DEBUG(dbgs() << "Muls are mismatching operand list lengths: "
+ << VL0.size() << " != " << VL1.size() << "\n");
+ return false;
+ }
+
+ const unsigned Pairs = VL0.size();
+
+ for (unsigned i = 0; i < Pairs; ++i) {
+ const Value *V0 = VL0[i];
+ const Value *V1 = VL1[i];
+ const auto *Inst0 = dyn_cast<Instruction>(V0);
+ const auto *Inst1 = dyn_cast<Instruction>(V1);
+
+ if (!Inst0 || !Inst1)
+ return false;
+
+ if (Inst0->isSameOperationAs(Inst1))
+ continue;
+
+ const APInt *C0, *C1;
+ if (!(match(V0, m_APInt(C0)) && match(V1, m_APInt(C1)) && C0 == C1))
+ return false;
+ }
+
+ return true;
+ };
+
+ return CompareValueList(LHS, Other->LHS) &&
+ CompareValueList(RHS, Other->RHS);
+}
+
+Pass *llvm::createARMParallelDSPPass() {
+ return new ARMParallelDSP();
+}
+
+char ARMParallelDSP::ID = 0;
+
+INITIALIZE_PASS_BEGIN(ARMParallelDSP, "arm-parallel-dsp",
+ "Transform loops to use DSP intrinsics", false, false)
+INITIALIZE_PASS_END(ARMParallelDSP, "arm-parallel-dsp",
+ "Transform loops to use DSP intrinsics", false, false)
generated by cgit v1.2.3 (git 2.25.1) at 2025-12-08 23:29:24 +0000