[ARM][ParallelDSP] Convert to function pass

[samparker]

Summary

Run across a whole function, visiting each basic block one at a time.

[efriedma]

lib/Target/ARM/ARMParallelDSP.cpp

222

Missing call to skipFunction?

[samparker]

Thanks. Added skipFunction and rebased.

[efriedma]

LGTM

lib/Target/ARM/ARMParallelDSP.cpp

212

Missing call to AU.addPreserved<ScalarEvolutionWrapperPass>(). Missing call to AU.addPreserved<GlobalsAAWrapperPass>(). But that's orthogonal, I guess; fine to address that in a followup.

[samparker]

@efriedma Thanks, added Preserved before committing.

[thakis]

Heads-up, we've bisected a webrtc test failure down to this revision: https://bugs.chromium.org/p/webrtc/issues/detail?id=10887

(But we're still analyzing things.)

lib/Target/ARM/ARMParallelDSP.cpp

-//===- ParallelDSP.cpp - Parallel DSP Pass --------------------------------===//
+//===- ARMParallelDSP.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"
WidenedLoad(SmallVectorImpl<LoadInst*> &Lds, LoadInst *Wide)
       for (auto *I : Lds)
         Loads.push_back(I);
     }
     LoadInst *getLoad() {
       return NewLd;
     }
   };
 
-  class ARMParallelDSP : public LoopPass {
+  class ARMParallelDSP : public FunctionPass {
     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);
+    bool MatchSMLAD(Function &F);
 
   public:
     static char ID;
 
-    ARMParallelDSP() : LoopPass(ID) { }
-
-    bool doInitialization(Loop *L, LPPassManager &LPM) override {
-      LoadPairs.clear();
-      WideLoads.clear();
-      return true;
-    }
+    ARMParallelDSP() : FunctionPass(ID) { }
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
-      LoopPass::getAnalysisUsage(AU);
+      FunctionPass::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 {
+    bool runOnFunction(Function &F) override {
       if (DisableParallelDSP)
         return false;
-      if (skipLoop(TheLoop))
-        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);
+      bool Changes = MatchSMLAD(F);
       return Changes;
     }
   };
 }
 
 template<typename MemInst>
 static bool AreSequentialAccesses(MemInst *MemOp0, MemInst *MemOp1,
                                   const DataLayout &DL, ScalarEvolution &SE) {
bool ARMParallelDSP::IsNarrowSequence(Value *V, ValueList &VL) {
   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;
+  LoadPairs.clear();
+  WideLoads.clear();
 
   // 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);
LLVM_DEBUG(if (!LoadPairs.empty()) {
                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
+// The 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

 //
 // 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) {
+bool ARMParallelDSP::MatchSMLAD(Function &F) {
   // 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 {
+  std::function<bool(Value*, BasicBlock *BB, Reduction&)> Search = [&]
+    (Value *V, BasicBlock *BB, 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);
 
+    if (I->getParent() != BB)
+      return false;
+
     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);
+      bool ValidLHS = Search(I->getOperand(0), BB, R);
+      bool ValidRHS = Search(I->getOperand(1), BB, 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: {
             IsNarrowSequence<16>(MulOp1, RHS)) {
           R.InsertMul(I, LHS, RHS);
           return true;
         }
       }
       return false;
     }
     case Instruction::SExt:
-      return Search(I->getOperand(0), R);
+      return Search(I->getOperand(0), BB, R);
     }
     return false;
   };
 
   bool Changed = false;
-  SmallPtrSet<Instruction*, 4> AllAdds;
-  BasicBlock *Latch = L->getLoopLatch();
 
-  for (Instruction &I : reverse(*Latch)) {
+  for (auto &BB : F) {
+    SmallPtrSet<Instruction*, 4> AllAdds;
+    if (!RecordMemoryOps(&BB)) {
+      LLVM_DEBUG(dbgs() << " - No sequential loads found.\n");
+      continue;
+    }
+    for (Instruction &I : reverse(BB)) {
       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))
+      if (!Search(&I, &BB, 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)

 
 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)
+                "Transform functions to use DSP intrinsics", false, false)
 INITIALIZE_PASS_END(ARMParallelDSP, "arm-parallel-dsp",
-                "Transform loops to use DSP intrinsics", false, false)
+                "Transform functions to use DSP intrinsics", false, false)

test/CodeGen/ARM/O3-pipeline.ll

 ; CHECK-NEXT:      Instrument function entry/exit with calls to e.g. mcount() (post inlining)
 ; CHECK-NEXT:      Scalarize Masked Memory Intrinsics
 ; CHECK-NEXT:      Expand reduction intrinsics
 ; CHECK-NEXT:      Dominator Tree Construction
 ; CHECK-NEXT:      Natural Loop Information
 ; CHECK-NEXT:      Scalar Evolution Analysis
 ; CHECK-NEXT:      Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:      Function Alias Analysis Results
-; CHECK-NEXT:      Loop Pass Manager
-; CHECK-NEXT:        Transform loops to use DSP intrinsics
+; CHECK-NEXT:      Transform functions to use DSP intrinsics
 ; CHECK-NEXT:      Interleaved Access Pass
 ; CHECK-NEXT:      ARM IR optimizations
 ; CHECK-NEXT:      Dominator Tree Construction
 ; CHECK-NEXT:      Natural Loop Information
 ; CHECK-NEXT:      CodeGen Prepare
 ; CHECK-NEXT:    Rewrite Symbols
 ; CHECK-NEXT:    FunctionPass Manager
 ; CHECK-NEXT:      Dominator Tree Construction

test/CodeGen/ARM/ParallelDSP/blocks.ll

+; RUN: opt -arm-parallel-dsp -mtriple=armv7-a -S %s -o - | FileCheck %s
+
+; CHECK-LABEL: single_block
+; CHECK: [[CAST_A:%[^ ]+]] = bitcast i16* %a to i32*
+; CHECK: [[A:%[^ ]+]] = load i32, i32* [[CAST_A]]
+; CHECK: [[CAST_B:%[^ ]+]] = bitcast i16* %b to i32*
+; CHECK: [[B:%[^ ]+]] = load i32, i32* [[CAST_B]]
+; CHECK  call i32 @llvm.arm.smlad(i32 [[A]], i32 [[B]], i32 %acc)
+define i32 @single_block(i16* %a, i16* %b, i32 %acc) {
+entry:
+  %ld.a.0 = load i16, i16* %a
+  %sext.a.0 = sext i16 %ld.a.0 to i32
+  %ld.b.0 = load i16, i16* %b
+  %sext.b.0 = sext i16 %ld.b.0 to i32
+  %mul.0 = mul i32 %sext.a.0, %sext.b.0
+  %addr.a.1 = getelementptr i16, i16* %a, i32 1
+  %addr.b.1 = getelementptr i16, i16* %b, i32 1
+  %ld.a.1 = load i16, i16* %addr.a.1
+  %sext.a.1 = sext i16 %ld.a.1 to i32
+  %ld.b.1 = load i16, i16* %addr.b.1
+  %sext.b.1 = sext i16 %ld.b.1 to i32
+  %mul.1 = mul i32 %sext.a.1, %sext.b.1
+  %add = add i32 %mul.0, %mul.1
+  %res = add i32 %add, %acc
+  ret i32 %res
+}
+
+; CHECK-LABEL: multi_block
+; CHECK: [[CAST_A:%[^ ]+]] = bitcast i16* %a to i32*
+; CHECK: [[A:%[^ ]+]] = load i32, i32* [[CAST_A]]
+; CHECK: [[CAST_B:%[^ ]+]] = bitcast i16* %b to i32*
+; CHECK: [[B:%[^ ]+]] = load i32, i32* [[CAST_B]]
+; CHECK  call i32 @llvm.arm.smlad(i32 [[A]], i32 [[B]], i32 0)
+define i32 @multi_block(i16* %a, i16* %b, i32 %acc) {
+entry:
+  %ld.a.0 = load i16, i16* %a
+  %sext.a.0 = sext i16 %ld.a.0 to i32
+  %ld.b.0 = load i16, i16* %b
+  %sext.b.0 = sext i16 %ld.b.0 to i32
+  %mul.0 = mul i32 %sext.a.0, %sext.b.0
+  %addr.a.1 = getelementptr i16, i16* %a, i32 1
+  %addr.b.1 = getelementptr i16, i16* %b, i32 1
+  %ld.a.1 = load i16, i16* %addr.a.1
+  %sext.a.1 = sext i16 %ld.a.1 to i32
+  %ld.b.1 = load i16, i16* %addr.b.1
+  %sext.b.1 = sext i16 %ld.b.1 to i32
+  %mul.1 = mul i32 %sext.a.1, %sext.b.1
+  %add = add i32 %mul.0, %mul.1
+  br label %bb.1
+
+bb.1:
+  %res = add i32 %add, %acc
+  ret i32 %res
+}
+
+; CHECK-LABEL: multi_block_1
+; CHECK-NOT: call i32 @llvm.arm.smlad
+define i32 @multi_block_1(i16* %a, i16* %b, i32 %acc) {
+entry:
+  %ld.a.0 = load i16, i16* %a
+  %sext.a.0 = sext i16 %ld.a.0 to i32
+  %ld.b.0 = load i16, i16* %b
+  %sext.b.0 = sext i16 %ld.b.0 to i32
+  %mul.0 = mul i32 %sext.a.0, %sext.b.0
+  br label %bb.1
+
+bb.1:
+  %addr.a.1 = getelementptr i16, i16* %a, i32 1
+  %addr.b.1 = getelementptr i16, i16* %b, i32 1
+  %ld.a.1 = load i16, i16* %addr.a.1
+  %sext.a.1 = sext i16 %ld.a.1 to i32
+  %ld.b.1 = load i16, i16* %addr.b.1
+  %sext.b.1 = sext i16 %ld.b.1 to i32
+  %mul.1 = mul i32 %sext.a.1, %sext.b.1
+  %add = add i32 %mul.0, %mul.1
+  %res = add i32 %add, %acc
+  ret i32 %res
+}
+

test/CodeGen/ARM/ParallelDSP/smlad12.ll

 ; RUN: opt -mtriple=arm-arm-eabi -mcpu=cortex-m33 < %s -arm-parallel-dsp -S | FileCheck %s
 ;
 ; The loop header is not the loop latch.
 ;
-; CHECK-NOT:  call i32 @llvm.arm.smlad
+; CHECK:  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