Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -221,6 +221,7 @@ void initializeLoopPassPass(PassRegistry&); void initializeLoopPredicationLegacyPassPass(PassRegistry&); void initializeLoopRerollPass(PassRegistry&); +void initializeParallelDSPLegacyPassPass(PassRegistry&); void initializeLoopRotateLegacyPassPass(PassRegistry&); void initializeLoopSimplifyCFGLegacyPassPass(PassRegistry&); void initializeLoopSimplifyPass(PassRegistry&); @@ -322,6 +323,7 @@ void initializeRegAllocFastPass(PassRegistry&); void initializeRAGreedyPass(PassRegistry&); void initializeReassociateLegacyPassPass(PassRegistry&); +void initializeParallelDSPPass(PassRegistry&); void initializeRegBankSelectPass(PassRegistry&); void initializeReachingDefAnalysisPass(PassRegistry&); void initializeRegToMemPass(PassRegistry&); Index: include/llvm/Transforms/Scalar.h =================================================================== --- include/llvm/Transforms/Scalar.h +++ include/llvm/Transforms/Scalar.h @@ -485,6 +485,8 @@ // primarily to help other loop passes. // Pass *createLoopSimplifyCFGPass(); + +Pass *createParallelDSPPass(); } // End llvm namespace #endif Index: lib/Target/ARM/ARMTargetMachine.cpp =================================================================== --- lib/Target/ARM/ARMTargetMachine.cpp +++ lib/Target/ARM/ARMTargetMachine.cpp @@ -398,6 +398,9 @@ TargetPassConfig::addIRPasses(); + if (getOptLevel() != CodeGenOpt::None) + addPass(createParallelDSPPass()); + // Match interleaved memory accesses to ldN/stN intrinsics. if (TM->getOptLevel() != CodeGenOpt::None) addPass(createInterleavedAccessPass()); Index: lib/Transforms/IPO/PassManagerBuilder.cpp =================================================================== --- lib/Transforms/IPO/PassManagerBuilder.cpp +++ lib/Transforms/IPO/PassManagerBuilder.cpp @@ -367,8 +367,10 @@ MPM.add(createLoopInterchangePass()); // Interchange loops MPM.add(createCFGSimplificationPass()); } - if (!DisableUnrollLoops) + if (!DisableUnrollLoops) { MPM.add(createSimpleLoopUnrollPass(OptLevel)); // Unroll small loops + MPM.add(createParallelDSPPass()); + } addExtensionsToPM(EP_LoopOptimizerEnd, MPM); // This ends the loop pass pipelines. @@ -669,6 +671,7 @@ if (!DisableUnrollLoops) { MPM.add(createLoopUnrollPass(OptLevel)); // Unroll small loops + MPM.add(createParallelDSPPass()); // LoopUnroll may generate some redundency to cleanup. addInstructionCombiningPass(MPM); @@ -835,12 +838,16 @@ if (EnableLoopInterchange) PM.add(createLoopInterchangePass()); - if (!DisableUnrollLoops) + if (!DisableUnrollLoops) { PM.add(createSimpleLoopUnrollPass(OptLevel)); // Unroll small loops + PM.add(createParallelDSPPass()); + } PM.add(createLoopVectorizePass(true, LoopVectorize)); // The vectorizer may have significantly shortened a loop body; unroll again. - if (!DisableUnrollLoops) + if (!DisableUnrollLoops) { PM.add(createLoopUnrollPass(OptLevel)); + PM.add(createParallelDSPPass()); + } // Now that we've optimized loops (in particular loop induction variables), // we may have exposed more scalar opportunities. Run parts of the scalar Index: lib/Transforms/Scalar/CMakeLists.txt =================================================================== --- lib/Transforms/Scalar/CMakeLists.txt +++ lib/Transforms/Scalar/CMakeLists.txt @@ -51,6 +51,7 @@ PartiallyInlineLibCalls.cpp PlaceSafepoints.cpp Reassociate.cpp + ParallelDSP.cpp Reg2Mem.cpp RewriteStatepointsForGC.cpp SCCP.cpp Index: lib/Transforms/Scalar/ParallelDSP.cpp =================================================================== --- /dev/null +++ lib/Transforms/Scalar/ParallelDSP.cpp @@ -0,0 +1,540 @@ +//===- ParallelDSP.cpp - Parallel DSP Pass --------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +/// \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. +// +//===----------------------------------------------------------------------===// + +#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" + +using namespace llvm; +using namespace PatternMatch; + +#define DEBUG_TYPE "parallel-dsp" + +namespace { + struct ParallelMAC; + struct Reduction; + + using ParallelMACList = std::vector; + using ReductionList = std::vector; + using ValueList = std::vector; + using LoadInstList = std::vector; + using PMACPair = std::pair; + using PMACPairList = std::vector; + + // 'ParallelMAC' and 'Reduction' are just some bookkeeping data structures. + // 'Reduction' contains the phi-node and accumulator statement from where we + // start pattern matching, and 'ParallelMAC' the multiplication + // instructions that are candidates for parallel execution. + struct ParallelMAC { + Instruction *Mul; + ValueList VL; // List of all (narrow) operands of this Mul + LoadInstList VecLd; // List of all load instructions of this Mul + + ParallelMAC(Instruction *I, ValueList &V) : Mul(I), VL(V) {}; + }; + + struct Reduction { + PHINode *Phi; // The Phi-node from where we start + // pattern matching. + Instruction *AccIntAdd; // The accumulating integer add statement, + // i.e, the reduction statement. + ParallelMACList Candidates; // List of all candidate parallel mul + // statements. + std::vector PMACPairs; // Pairs of parallel MAC statements + + Reduction (PHINode *P, Instruction *Acc) : Phi(P), AccIntAdd(Acc) { }; + }; + + class ParallelDSPLegacyPass : public LoopPass { + ScalarEvolution *SE; + AliasAnalysis *AA; + TargetLibraryInfo *TLI; + DominatorTree *DT; + LoopInfo *LI; + Loop *L; + const DataLayout *DL; + Module *M; + + bool CreateParallelMACs(ReductionList &Reductions); + bool AreSequentialLoads(LoadInst *Ld0, LoadInst *Ld1, LoadInstList &VecLd); + bool CreateParallelMACPairs(Reduction &R); + Instruction *CreateSMLADCall(LoadInst *VecLd0, LoadInst *VecLd1, + Instruction *Acc, Instruction *InsertAfter); + + /// 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. + void MatchSMLAD(Function &F); + + public: + static char ID; + + ParallelDSPLegacyPass() : LoopPass(ID) { + initializeParallelDSPLegacyPassPass(*PassRegistry::getPassRegistry()); + } + + void getAnalysisUsage(AnalysisUsage &AU) const override { + LoopPass::getAnalysisUsage(AU); + AU.addRequired(); + AU.addRequired(); + AU.addRequired(); + AU.addRequired(); + AU.addRequired(); + AU.addRequired(); + AU.addPreserved(); + AU.setPreservesCFG(); + } + + bool runOnLoop(Loop *TheLoop, LPPassManager &) override { + L = TheLoop; + SE = &getAnalysis().getSE(); + AA = &getAnalysis().getAAResults(); + TLI = &getAnalysis().getTLI(); + DT = &getAnalysis().getDomTree(); + LI = &getAnalysis().getLoopInfo(); + + LoopAccessInfo LAI(L, SE, TLI, AA, DT, LI); + + BasicBlock *Header = TheLoop->getHeader(); + Function &F = *Header->getParent(); + M = F.getParent(); + DL = &M->getDataLayout(); + + LLVM_DEBUG(dbgs() << "\n== Parallel DSP pass ==\n\n"); + MatchSMLAD(F); + return true; + } + }; +} + +template +static bool IsNarrowSequence(Value *V, ValueList &VL) { + LLVM_DEBUG(dbgs() << "Is narrow sequence: "; V->dump()); + ConstantInt *CInt; + + if (match(V, m_ConstantInt(CInt))) { + // If a constant is used, it needs to fit within the bit width. + if (CInt->getUniqueInteger().getBitWidth() <= BitWidth) { + LLVM_DEBUG(dbgs() << "OK: found narrow constant.\n"); + VL.push_back(CInt); + return true; + } + LLVM_DEBUG(dbgs() << "Found wide constant:\t"; CInt->dump()); + return false; + } + + auto *I = dyn_cast(V); + if (!I) + return false; + + Value *Val, *LHS, *RHS; + bool isNarrow = false; + + if (match(V, m_Trunc(m_Value(Val)))) { + if (cast(I)->getDestTy()->getIntegerBitWidth() == BitWidth) + isNarrow = IsNarrowSequence(Val, VL); + } else if (match(V, m_Add(m_Value(LHS), m_Value(RHS)))) { + if (IsNarrowSequence(LHS, VL) && + IsNarrowSequence(RHS, VL)) + isNarrow = true; + } else if (match(V, m_ZExtOrSExt(m_Value(Val)))) { + if (cast(I)->getSrcTy()->getIntegerBitWidth() == BitWidth) + isNarrow = true; + else + LLVM_DEBUG(dbgs() << "Wrong SrcTy size of CastInst: " << + cast(I)->getSrcTy()->getIntegerBitWidth()); + + if (match(Val, m_Load(m_Value(Val)))) { + auto *Ld = dyn_cast(I->getOperand(0)); + LLVM_DEBUG(dbgs() << "Found narrow Load:\t"; Ld->dump()); + VL.push_back(Ld); + isNarrow = true; + } else if (!isa(I->getOperand(0))) + VL.push_back(I->getOperand(0)); + } + + if (isNarrow) { + LLVM_DEBUG(dbgs() << "Found narrow Op:\t"; I->dump()); + VL.push_back(I); + } else + LLVM_DEBUG(dbgs() << "Found unsupported Op:\t"; I->dump()); + + return isNarrow; +} + +// Element-by-element comparison of Value lists returning true if they are +// instructions with the same opcode or constants with the same value. +static bool AreSymmetrical(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(); + LLVM_DEBUG(dbgs() << "Number of operand pairs: " << Pairs << "\n"); + + for (unsigned i = 0; i < Pairs; ++i) { + const Value *V0 = VL0[i]; + const Value *V1 = VL1[i]; + const auto *Inst0 = dyn_cast(V0); + const auto *Inst1 = dyn_cast(V1); + + LLVM_DEBUG(dbgs() << "Pair " << i << ":\n"; + dbgs() << "mul1: "; V0->dump(); + dbgs() << "mul2: "; V1->dump()); + + if (!Inst0 || !Inst1) + return false; + + if (Inst0->getOpcode() == Inst1->getOpcode()) { + LLVM_DEBUG(dbgs() << "OK: opcodes match!\n"); + continue; + } + + const APInt *C0, *C1; + if (match(V0, m_APInt(C0)) && match(V1, m_APInt(C1))) { + if (C0 != C1) + return false; + } else + return false; + } + + LLVM_DEBUG(dbgs() << "OK: found symmetrical operand lists.\n"); + return true; +} + +bool ParallelDSPLegacyPass::AreSequentialLoads(LoadInst *Ld0, LoadInst *Ld1, + LoadInstList &VecLd) { + if (!Ld0 || !Ld1) + return false; + + LLVM_DEBUG(dbgs() << "Check for consecutive loads:\n"; + dbgs() << "Ld0:"; Ld0->dump(); + dbgs() << "Ld1:"; Ld1->dump(); + ); + + if (!Ld0->hasOneUse() || !Ld1->hasOneUse()) { + LLVM_DEBUG(dbgs() << "Load has more than one use.\n"); + return false; + } + + if (Ld0 == Ld1) { + LLVM_DEBUG(dbgs() << "OK: loads are the same.\n"); + VecLd.push_back(Ld0); + VecLd.push_back(Ld1); + return true; + } + + // In case Ld0/Ld1 are volatile loads, this will return false. + if (isConsecutiveAccess(Ld0, Ld1, *DL, *SE)) { + VecLd.push_back(Ld0); + VecLd.push_back(Ld1); + LLVM_DEBUG(dbgs() << "OK: loads are consecutive.\n"); + return true; + } + + LLVM_DEBUG(dbgs() << "Ld0 and Ld1 aren't consecutive.\n"); + return false; +} + +bool ParallelDSPLegacyPass::CreateParallelMACPairs(Reduction &R) { + const unsigned Elems = R.Candidates.size(); + + for(unsigned i=0; idump(); + dbgs() << "- "; Mul1->dump()); + + const ValueList &VL0 = PMul0.VL; + const ValueList &VL1 = PMul1.VL; + + // A mul has 2 operands, and a narrow op consist of sext and a load; thus + // we expect at least 4 items in this list. + if (VL0.size() < 4) { + LLVM_DEBUG(dbgs() << "Operand list too short.\n"); + continue; + } + + if (!AreSymmetrical(VL0, VL1)) + return false; + + LLVM_DEBUG(dbgs() << "OK: mul operands list match:\n"); + + // 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 < VL0.size(); x += 4) { + auto *Ld0 = dyn_cast(VL0[x]); + auto *Ld1 = dyn_cast(VL1[x]); + auto *Ld2 = dyn_cast(VL0[x+2]); + auto *Ld3 = dyn_cast(VL1[x+2]); + + LLVM_DEBUG(dbgs() << "Looking at operands " << x << ":\n"; + dbgs() << "\t mul1: "; VL0[x]->dump(); + dbgs() << "\t mul2: "; VL1[x]->dump(); + dbgs() << "and operands " << x + 2 << ":\n"; + dbgs() << "\t mul1: "; VL0[x+2]->dump(); + dbgs() << "\t mul2: "; VL1[x+2]->dump()); + + if (AreSequentialLoads(Ld0, Ld1, R.Candidates[i].VecLd) && + AreSequentialLoads(Ld2, Ld3, R.Candidates[j].VecLd)) { + LLVM_DEBUG(dbgs() << "OK: found two pairs of parallel loads!\n"); + PMACPair P = std::make_pair(&PMul0, &PMul1); + R.PMACPairs.push_back(P); + return true; + } + } + } + } + LLVM_DEBUG(dbgs() << "Did not find any parallel loads\n"); + return false; +} + +bool ParallelDSPLegacyPass::CreateParallelMACs(ReductionList &Reductions) { + for (auto &Reduction : Reductions) { + Instruction *Acc = Reduction.Phi; + Instruction *InsertAfter = Reduction.AccIntAdd; + + CreateParallelMACPairs(Reduction); + + for (auto &Pair : Reduction.PMACPairs) { + LLVM_DEBUG(dbgs() << "Found parallel MACs!!\n"; + dbgs() << "- "; Pair.first->Mul->dump(); + dbgs() << "- "; Pair.second->Mul->dump()); + + Acc = CreateSMLADCall(Pair.first->VecLd[0], Pair.second->VecLd[0], Acc, + InsertAfter); + InsertAfter = Acc; + if (Acc == Reduction.Phi) + continue; + + LLVM_DEBUG(dbgs() << "Replace Accumulate: "; Acc->dump()); + Reduction.AccIntAdd->replaceAllUsesWith(Acc); + } + } + return true; +} + +static bool MatchReductions(Function &F, Loop *TheLoop, BasicBlock *Header, + ReductionList &Reductions) { + RecurrenceDescriptor RecDesc; + const bool HasFnNoNaNAttr = + F.getFnAttribute("no-nans-fp-math").getValueAsString() == "true"; + + for (PHINode &Phi : Header->phis()) { + if (!Phi.getType()->isIntegerTy()) + continue; + + const bool IsReduction = + RecurrenceDescriptor::AddReductionVar(&Phi, + RecurrenceDescriptor::RK_IntegerAdd, + TheLoop, HasFnNoNaNAttr, RecDesc); + if (!IsReduction) + continue; + + // TODO: should we handle multiple latch blocks? + BasicBlock *Latch = TheLoop->getLoopLatch(); + if (!Latch) + continue; + + Instruction *Acc = dyn_cast(Phi.getIncomingValueForBlock(Latch)); + if (!Acc) + return false; + + Reductions.push_back(Reduction(&Phi, Acc)); + } + + LLVM_DEBUG( + dbgs() << "\nAccumulating integer additions (reductions) found:\n"; + for (auto R : Reductions) { + dbgs() << "- "; R.Phi->dump(); + dbgs() << "-> "; R.AccIntAdd->dump(); + } + ); + return true; +} + +static void AddCandidateMAC(Reduction &R, const Instruction *Acc, + Value *MulOp0, Value *MulOp1, int MulOpNum) { + Instruction *Mul = dyn_cast(Acc->getOperand(MulOpNum)); + LLVM_DEBUG(dbgs() << "found acc mul:\t"; Mul->dump()); + ValueList VL; + if (IsNarrowSequence<16>(MulOp0, VL) && + IsNarrowSequence<16>(MulOp1, VL)) { + LLVM_DEBUG(dbgs() << "OK: found narrow mul: "; Mul->dump()); + R.Candidates.push_back(ParallelMAC(Mul, VL)); + } +} + +static void MatchParallelMACs(ReductionList &Reductions) { + LLVM_DEBUG(dbgs() << "\nNumber of reductions to analyze: "; + dbgs() << Reductions.size() << "\n"); + + for (auto &R : Reductions) { + const Instruction *Acc = R.AccIntAdd; + LLVM_DEBUG(dbgs() << "- Analysing:\t"; Acc->dump()); + + Value *A, *MulOp0, *MulOp1; + + // Pattern 1: + // %add11 = add i32 %mul, %mac1.037 + // %add16 = add i32 %mul10, %add11 + // %add17 = add i32 %mul15, %add16 + while(match(Acc, m_Add(m_Mul(m_Value(MulOp0), m_Value(MulOp1)), + m_Value(A)))){ + AddCandidateMAC(R, Acc, MulOp0, MulOp1, 0); + Acc = dyn_cast(A); + } + // Pattern 2: + // %add11 = add i32 %mul, %mac1.037 + // %add16 = add i32 %add11, %mul10 + // %add17 = add i32 %add16, %mul15 + while(match(Acc, m_Add(m_Value(A), + m_Mul(m_Value(MulOp0), m_Value(MulOp1))))) { + AddCandidateMAC(R, Acc, MulOp0, MulOp1, 1); + Acc = dyn_cast(A); + } + + // The last mul in the chain has a slightly different pattern: + // the mul is the first operand + if (match(Acc, m_Add(m_Mul(m_Value(MulOp0), m_Value(MulOp1)), m_Value(A)))) + AddCandidateMAC(R, Acc, MulOp0, MulOp1, 0); + + // Because we start at the bottom of the chain, and we work our way up, + // the muls are added in reverse program order to the list. + std::reverse(R.Candidates.begin(), R.Candidates.end()); + } +} + +// 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 reduction PHIs, +// 2) then from the PHI, look for this pattern: +// +// acc0 = phi i32 [0, %entry], [%acc1, %loop.body] +// 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.h r0 +// ldr.h 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. +// +// Can only be enabled for cores which support unaligned accesses. +// +void ParallelDSPLegacyPass::MatchSMLAD(Function &F) { + BasicBlock *Header = L->getHeader(); + + LLVM_DEBUG(dbgs() << "= Matching SMLAD =\n"; + dbgs() << "Header block:\n"; Header->dump(); + dbgs() << "Loop info:\n\n"; L->dump()); + + ReductionList Reductions; + ParallelMACList ParallelMACs; + + if (MatchReductions(F, L, Header, Reductions)) { + MatchParallelMACs(Reductions); + CreateParallelMACs(Reductions); + } +} + +Instruction *ParallelDSPLegacyPass::CreateSMLADCall(LoadInst *VecLd0, + LoadInst *VecLd1, + Instruction *Acc, + Instruction *InsertAfter) { + LLVM_DEBUG(dbgs() << "Create SMLAD intrinsic using:\n"; + dbgs() << "- "; VecLd0->dump(); + dbgs() << "- "; VecLd1->dump(); + dbgs() << "- "; Acc->dump()); + + IRBuilder Builder(InsertAfter->getParent(), + ++BasicBlock::iterator(InsertAfter)); + + // Replace the reduction chain with an intrinsic call + Type *AccTy = Acc->getType(); + unsigned AddrSpace = VecLd0->getPointerAddressSpace(); + Value *VecPtr = Builder.CreateBitCast(VecLd0->getPointerOperand(), + AccTy->getPointerTo(AddrSpace)); + VecLd0 = Builder.CreateLoad(Acc->getType(), VecPtr); + + AddrSpace = VecLd1->getPointerAddressSpace(); + VecPtr = Builder.CreateBitCast(VecLd1->getPointerOperand(), + AccTy->getPointerTo(AddrSpace)); + VecLd1 = Builder.CreateLoad(Acc->getType(), VecPtr); + + Value* Args[] = { VecLd0, VecLd1, Acc }; + Function *SMLAD = Intrinsic::getDeclaration(M, Intrinsic::arm_smlad); + + CallInst *Call = Builder.CreateCall(SMLAD, Args); + return Call; +} + +Pass *llvm::createParallelDSPPass() { + return new ParallelDSPLegacyPass(); +} + +char ParallelDSPLegacyPass::ID = 0; + +INITIALIZE_PASS_BEGIN(ParallelDSPLegacyPass, "parallel-dsp", + "Transform loops to use reducing intrinsics", false, + false); +INITIALIZE_PASS_END(ParallelDSPLegacyPass, "parallel-dsp", + "Transform loops to use reducing intrinsics", false, + false); Index: lib/Transforms/Scalar/Scalar.cpp =================================================================== --- lib/Transforms/Scalar/Scalar.cpp +++ lib/Transforms/Scalar/Scalar.cpp @@ -65,6 +65,7 @@ initializeLoopInstSimplifyLegacyPassPass(Registry); initializeLoopInterchangePass(Registry); initializeLoopPredicationLegacyPassPass(Registry); + initializeParallelDSPLegacyPassPass(Registry); initializeLoopRotateLegacyPassPass(Registry); initializeLoopStrengthReducePass(Registry); initializeLoopRerollPass(Registry); Index: test/Transforms/ParallelDSP/smlad0.ll =================================================================== --- /dev/null +++ test/Transforms/ParallelDSP/smlad0.ll @@ -0,0 +1,50 @@ +; RUN: opt < %s -parallel-dsp -S | FileCheck %s + +; CHECK: %mac1{{\.}}026 = phi i32 [ [[V8:%[0-9]+]], %for.body ], [ 0, %for.body.preheader ] +; CHECK: [[V4:%[0-9]+]] = bitcast i16* %arrayidx3 to i32* +; CHECK: [[V5:%[0-9]+]] = load i32, i32* [[V4]] +; CHECK: [[V6:%[0-9]+]] = bitcast i16* %arrayidx to i32* +; CHECK: [[V7:%[0-9]+]] = load i32, i32* [[V6]] +; CHECK: [[V8]] = call i32 @llvm.arm.smlad(i32 [[V5]], i32 [[V7]], i32 %mac1{{\.}}026) + +define dso_local i32 @test(i32 %arg, i32* nocapture readnone %arg1, i16* nocapture readonly %arg2, i16* nocapture readonly %arg3) { +entry: + %cmp24 = icmp sgt i32 %arg, 0 + br i1 %cmp24, label %for.body.preheader, label %for.cond.cleanup + +for.body.preheader: + %.pre = load i16, i16* %arg3, align 2 + %.pre27 = load i16, i16* %arg2, align 2 + br label %for.body + +for.cond.cleanup: + %mac1.0.lcssa = phi i32 [ 0, %entry ], [ %add11, %for.body ] + ret i32 %mac1.0.lcssa + +for.body: + %mac1.026 = phi i32 [ %add11, %for.body ], [ 0, %for.body.preheader ] + %i.025 = phi i32 [ %add, %for.body ], [ 0, %for.body.preheader ] + %arrayidx = getelementptr inbounds i16, i16* %arg3, i32 %i.025 + %0 = load i16, i16* %arrayidx, align 2 + %add = add nuw nsw i32 %i.025, 1 + %arrayidx1 = getelementptr inbounds i16, i16* %arg3, i32 %add + %1 = load i16, i16* %arrayidx1, align 2 + %arrayidx3 = getelementptr inbounds i16, i16* %arg2, i32 %i.025 + %2 = load i16, i16* %arrayidx3, align 2 + %conv = sext i16 %2 to i32 + %conv4 = sext i16 %0 to i32 + %mul = mul nsw i32 %conv, %conv4 + %arrayidx6 = getelementptr inbounds i16, i16* %arg2, i32 %add + %3 = load i16, i16* %arrayidx6, align 2 + %conv7 = sext i16 %3 to i32 + %conv8 = sext i16 %1 to i32 + %mul9 = mul nsw i32 %conv7, %conv8 + %add10 = add i32 %mul, %mac1.026 + +; Here the Mul is the LHS, and the Add the RHS. + %add11 = add i32 %mul9, %add10 + + %exitcond = icmp ne i32 %add, %arg + br i1 %exitcond, label %for.body, label %for.cond.cleanup +} + Index: test/Transforms/ParallelDSP/smlad1.ll =================================================================== --- /dev/null +++ test/Transforms/ParallelDSP/smlad1.ll @@ -0,0 +1,50 @@ +; RUN: opt < %s -parallel-dsp -S | FileCheck %s + +; CHECK: %mac1{{\.}}026 = phi i32 [ [[V8:%[0-9]+]], %for.body ], [ 0, %for.body.preheader ] +; CHECK: [[V4:%[0-9]+]] = bitcast i16* %arrayidx3 to i32* +; CHECK: [[V5:%[0-9]+]] = load i32, i32* [[V4]] +; CHECK: [[V6:%[0-9]+]] = bitcast i16* %arrayidx to i32* +; CHECK: [[V7:%[0-9]+]] = load i32, i32* [[V6]] +; CHECK: [[V8]] = call i32 @llvm.arm.smlad(i32 [[V5]], i32 [[V7]], i32 %mac1{{\.}}026) + +define dso_local i32 @test(i32 %arg, i32* nocapture readnone %arg1, i16* nocapture readonly %arg2, i16* nocapture readonly %arg3) { +entry: + %cmp24 = icmp sgt i32 %arg, 0 + br i1 %cmp24, label %for.body.preheader, label %for.cond.cleanup + +for.body.preheader: + %.pre = load i16, i16* %arg3, align 2 + %.pre27 = load i16, i16* %arg2, align 2 + br label %for.body + +for.cond.cleanup: + %mac1.0.lcssa = phi i32 [ 0, %entry ], [ %add11, %for.body ] + ret i32 %mac1.0.lcssa + +for.body: + %mac1.026 = phi i32 [ %add11, %for.body ], [ 0, %for.body.preheader ] + %i.025 = phi i32 [ %add, %for.body ], [ 0, %for.body.preheader ] + %arrayidx = getelementptr inbounds i16, i16* %arg3, i32 %i.025 + %0 = load i16, i16* %arrayidx, align 2 + %add = add nuw nsw i32 %i.025, 1 + %arrayidx1 = getelementptr inbounds i16, i16* %arg3, i32 %add + %1 = load i16, i16* %arrayidx1, align 2 + %arrayidx3 = getelementptr inbounds i16, i16* %arg2, i32 %i.025 + %2 = load i16, i16* %arrayidx3, align 2 + %conv = sext i16 %2 to i32 + %conv4 = sext i16 %0 to i32 + %mul = mul nsw i32 %conv, %conv4 + %arrayidx6 = getelementptr inbounds i16, i16* %arg2, i32 %add + %3 = load i16, i16* %arrayidx6, align 2 + %conv7 = sext i16 %3 to i32 + %conv8 = sext i16 %1 to i32 + %mul9 = mul nsw i32 %conv7, %conv8 + %add10 = add i32 %mul, %mac1.026 + +; And here the Add is the LHS, the Mul the RHS + %add11 = add i32 %add10, %mul9 + + %exitcond = icmp ne i32 %add, %arg + br i1 %exitcond, label %for.body, label %for.cond.cleanup +} + Index: test/Transforms/ParallelDSP/smlad2.ll =================================================================== --- /dev/null +++ test/Transforms/ParallelDSP/smlad2.ll @@ -0,0 +1,52 @@ +; RUN: opt < %s -parallel-dsp -S | FileCheck %s +; +; Check that we don't generate the smlad instruction here as the operands of +; both muls are not symmetrical (see also comments inlined below). +; +; CHECK-NOT: call i32 @llvm.arm.smlad +; +define dso_local i32 @test(i32 %arg, i32* nocapture readnone %arg1, i16* nocapture readonly %arg2, i16* nocapture readonly %arg3) { +entry: + %cmp24 = icmp sgt i32 %arg, 0 + br i1 %cmp24, label %for.body.preheader, label %for.cond.cleanup + +for.body.preheader: + %.pre = load i16, i16* %arg3, align 2 + %.pre27 = load i16, i16* %arg2, align 2 + br label %for.body + +for.cond.cleanup: + %mac1.0.lcssa = phi i32 [ 0, %entry ], [ %add11, %for.body ] + ret i32 %mac1.0.lcssa + +for.body: + %mac1.026 = phi i32 [ %add11, %for.body ], [ 0, %for.body.preheader ] + %i.025 = phi i32 [ %add, %for.body ], [ 0, %for.body.preheader ] + %arrayidx = getelementptr inbounds i16, i16* %arg3, i32 %i.025 + %0 = load i16, i16* %arrayidx, align 2 + %add = add nuw nsw i32 %i.025, 1 + %arrayidx1 = getelementptr inbounds i16, i16* %arg3, i32 %add + %1 = load i16, i16* %arrayidx1, align 2 + %arrayidx3 = getelementptr inbounds i16, i16* %arg2, i32 %i.025 + %2 = load i16, i16* %arrayidx3, align 2 + %conv = sext i16 %2 to i32 + +; This zero-extends the 2nd operand of %mul: + %conv4 = zext i16 %0 to i32 + + %mul = mul nsw i32 %conv, %conv4 + %arrayidx6 = getelementptr inbounds i16, i16* %arg2, i32 %add + %3 = load i16, i16* %arrayidx6, align 2 + +; And here we only have sign-extensions. Thus, the operands of +; %mul and %mul9 are not symmetrical: + %conv7 = sext i16 %3 to i32 + %conv8 = sext i16 %1 to i32 + + %mul9 = mul nsw i32 %conv7, %conv8 + %add10 = add i32 %mul, %mac1.026 + %add11 = add i32 %add10, %mul9 + %exitcond = icmp ne i32 %add, %arg + br i1 %exitcond, label %for.body, label %for.cond.cleanup +} + Index: test/Transforms/ParallelDSP/smlad3.ll =================================================================== --- /dev/null +++ test/Transforms/ParallelDSP/smlad3.ll @@ -0,0 +1,51 @@ +; RUN: opt < %s -parallel-dsp -S | FileCheck %s +; +; Check that we don't generate the smlad instruction here as the loads +; are not consecutive (see also comments inlined below). +; +; CHECK-NOT: call i32 @llvm.arm.smlad +; +define dso_local i32 @test(i32 %arg, i32* nocapture readnone %arg1, i16* nocapture readonly %arg2, i16* nocapture readonly %arg3) { +entry: + %cmp24 = icmp sgt i32 %arg, 0 + br i1 %cmp24, label %for.body.preheader, label %for.cond.cleanup + +for.body.preheader: + %.pre = load i16, i16* %arg3, align 2 + %.pre27 = load i16, i16* %arg2, align 2 + br label %for.body + +for.cond.cleanup: + %mac1.0.lcssa = phi i32 [ 0, %entry ], [ %add11, %for.body ] + ret i32 %mac1.0.lcssa + +for.body: + %mac1.026 = phi i32 [ %add11, %for.body ], [ 0, %for.body.preheader ] + %i.025 = phi i32 [ %add, %for.body ], [ 0, %for.body.preheader ] + %arrayidx = getelementptr inbounds i16, i16* %arg3, i32 %i.025 + %0 = load i16, i16* %arrayidx, align 2 + %add = add nuw nsw i32 %i.025, 1 + %arrayidx1 = getelementptr inbounds i16, i16* %arg3, i32 %add + %1 = load i16, i16* %arrayidx1, align 2 + %arrayidx3 = getelementptr inbounds i16, i16* %arg2, i32 %i.025 + %2 = load i16, i16* %arrayidx3, align 2 + %conv = sext i16 %2 to i32 + %conv4 = sext i16 %0 to i32 + %mul = mul nsw i32 %conv, %conv4 + +; Here we add another constants offset of 2, to make sure the +; loads to %3 and %2 are not consecutive: + + %add5 = add nuw nsw i32 %i.025, 2 + %arrayidx6 = getelementptr inbounds i16, i16* %arg2, i32 %add5 + %3 = load i16, i16* %arrayidx6, align 2 + + %conv7 = sext i16 %3 to i32 + %conv8 = sext i16 %1 to i32 + %mul9 = mul nsw i32 %conv7, %conv8 + %add10 = add i32 %mul, %mac1.026 + %add11 = add i32 %add10, %mul9 + %exitcond = icmp ne i32 %add, %arg + br i1 %exitcond, label %for.body, label %for.cond.cleanup +} + Index: test/Transforms/ParallelDSP/smlad4.ll =================================================================== --- /dev/null +++ test/Transforms/ParallelDSP/smlad4.ll @@ -0,0 +1,51 @@ +; RUN: opt < %s -parallel-dsp -S | FileCheck %s +; +; Check that we don't generate the smlad instruction here as the loads +; are not not narrow loads (see also comments inlined below). +; +; CHECK-NOT: call i32 @llvm.arm.smlad +; +; Arg2 is now an i32, while Arg3 is still and i16: +; +define dso_local i32 @test(i32 %arg, i32* nocapture readnone %arg1, i32* nocapture readonly %arg2, i16* nocapture readonly %arg3) { +entry: + %cmp22 = icmp sgt i32 %arg, 0 + br i1 %cmp22, label %for.body.preheader, label %for.cond.cleanup + +for.body.preheader: + %.pre = load i16, i16* %arg3, align 2 + br label %for.body + +for.cond.cleanup: + %mac1.0.lcssa = phi i32 [ 0, %entry ], [ %add9, %for.body ] + ret i32 %mac1.0.lcssa + +for.body: + %0 = phi i16 [ %1, %for.body ], [ %.pre, %for.body.preheader ] + %mac1.024 = phi i32 [ %add9, %for.body ], [ 0, %for.body.preheader ] + %i.023 = phi i32 [ %add, %for.body ], [ 0, %for.body.preheader ] + %add = add nuw nsw i32 %i.023, 1 + %arrayidx1 = getelementptr inbounds i16, i16* %arg3, i32 %add + %1 = load i16, i16* %arrayidx1, align 2 + %conv = sext i16 %0 to i32 + +; This is now a 'normal' i32 load to %2: + + %arrayidx3 = getelementptr inbounds i32, i32* %arg2, i32 %i.023 + %2 = load i32, i32* %arrayidx3, align 4 + +; This mul has now 1 operand which is a narrow load, and the other a normal +; i32 load: + + %mul = mul nsw i32 %2, %conv + + %add4 = add nuw nsw i32 %i.023, 2 + %arrayidx5 = getelementptr inbounds i32, i32* %arg2, i32 %add4 + %3 = load i32, i32* %arrayidx5, align 4 + %conv6 = sext i16 %1 to i32 + %mul7 = mul nsw i32 %3, %conv6 + %add8 = add i32 %mul, %mac1.024 + %add9 = add i32 %add8, %mul7 + %exitcond = icmp eq i32 %add, %arg + br i1 %exitcond, label %for.cond.cleanup, label %for.body +} Index: test/Transforms/ParallelDSP/smlad5.ll =================================================================== --- /dev/null +++ test/Transforms/ParallelDSP/smlad5.ll @@ -0,0 +1,45 @@ +; RUN: opt < %s -parallel-dsp -S | FileCheck %s +; +; Check that we don't generate the smlad instruction when the loads +; are volatile loads. +; +; CHECK-NOT: call i32 @llvm.arm.smlad +; +define dso_local i32 @test(i32 %arg, i32* nocapture readnone %arg1, i16* nocapture readonly %arg2, i16* nocapture readonly %arg3) { +entry: + %cmp24 = icmp sgt i32 %arg, 0 + br i1 %cmp24, label %for.body.preheader, label %for.cond.cleanup + +for.body.preheader: + %.pre = load i16, i16* %arg3, align 2 + %.pre27 = load i16, i16* %arg2, align 2 + br label %for.body + +for.cond.cleanup: + %mac1.0.lcssa = phi i32 [ 0, %entry ], [ %add11, %for.body ] + ret i32 %mac1.0.lcssa + +for.body: + %mac1.026 = phi i32 [ %add11, %for.body ], [ 0, %for.body.preheader ] + %i.025 = phi i32 [ %add, %for.body ], [ 0, %for.body.preheader ] + %arrayidx = getelementptr inbounds i16, i16* %arg3, i32 %i.025 + %0 = load volatile i16, i16* %arrayidx, align 2 + %add = add nuw nsw i32 %i.025, 1 + %arrayidx1 = getelementptr inbounds i16, i16* %arg3, i32 %add + %1 = load volatile i16, i16* %arrayidx1, align 2 + %arrayidx3 = getelementptr inbounds i16, i16* %arg2, i32 %i.025 + %2 = load volatile i16, i16* %arrayidx3, align 2 + %conv = sext i16 %2 to i32 + %conv4 = sext i16 %0 to i32 + %mul = mul nsw i32 %conv, %conv4 + %arrayidx6 = getelementptr inbounds i16, i16* %arg2, i32 %add + %3 = load volatile i16, i16* %arrayidx6, align 2 + %conv7 = sext i16 %3 to i32 + %conv8 = sext i16 %1 to i32 + %mul9 = mul nsw i32 %conv7, %conv8 + %add10 = add i32 %mul, %mac1.026 + %add11 = add i32 %add10, %mul9 + %exitcond = icmp ne i32 %add, %arg + br i1 %exitcond, label %for.body, label %for.cond.cleanup +} +