diff options
Diffstat (limited to 'contrib/llvm/lib/Target/ARM/ARMParallelDSP.cpp')
| -rw-r--r-- | contrib/llvm/lib/Target/ARM/ARMParallelDSP.cpp | 847 |
1 files changed, 0 insertions, 847 deletions
diff --git a/contrib/llvm/lib/Target/ARM/ARMParallelDSP.cpp b/contrib/llvm/lib/Target/ARM/ARMParallelDSP.cpp deleted file mode 100644 index 5389d09bf7d7..000000000000 --- a/contrib/llvm/lib/Target/ARM/ARMParallelDSP.cpp +++ /dev/null @@ -1,847 +0,0 @@ -//===- 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) |