[Hexagon][NewPM] Port -hexagon-loop-idiom and add to pipeline

[aeubanks]

Summary

Fixes pmpy-mod.ll under NPM

[kparzysz]

LGTM. Thanks!

llvm/lib/Target/Hexagon/HexagonLoopIdiomRecognition.h

+//===- HexagonLoopIdiomRecognition.h --------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIB_TARGET_HEXAGON_HEXAGONLOOPIDIOMRECOGNITION_H
+#define LLVM_LIB_TARGET_HEXAGON_HEXAGONLOOPIDIOMRECOGNITION_H
+
+#include "llvm/IR/PassManager.h"
+#include "llvm/Transforms/Scalar/LoopPassManager.h"
+
+namespace llvm {
+
+struct HexagonLoopIdiomRecognitionPass
+    : PassInfoMixin<HexagonLoopIdiomRecognitionPass> {
+  PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,
+                        LoopStandardAnalysisResults &AR, LPMUpdater &U);
+};
+} // namespace llvm
+
+#endif // LLVM_LIB_TARGET_HEXAGON_HEXAGONLOOPIDIOMRECOGNITION_H

llvm/lib/Target/Hexagon/HexagonLoopIdiomRecognition.cpp

 //===- HexagonLoopIdiomRecognition.cpp ------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
+#include "HexagonLoopIdiomRecognition.h"
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/Triple.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/InstructionSimplify.h"
+#include "llvm/Analysis/LoopAnalysisManager.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/MemoryLocation.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DebugLoc.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/IntrinsicsHexagon.h"
 #include "llvm/IR/Module.h"
+#include "llvm/IR/PassManager.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/User.h"
 #include "llvm/IR/Value.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
static cl::opt<unsigned> SimplifyLimit("hlir-simplify-limit", cl::init(10000),
   cl::Hidden, cl::desc("Maximum number of simplification steps in HLIR"));
 
 static const char *HexagonVolatileMemcpyName
   = "hexagon_memcpy_forward_vp4cp4n2";
 
 
 namespace llvm {
 
-  void initializeHexagonLoopIdiomRecognizePass(PassRegistry&);
-  Pass *createHexagonLoopIdiomPass();
+void initializeHexagonLoopIdiomRecognizeLegacyPassPass(PassRegistry &);
 
 } // end namespace llvm
 
 namespace {
 
-  class HexagonLoopIdiomRecognize : public LoopPass {
-  public:
-    static char ID;
+class HexagonLoopIdiomRecognize {
+public:
+  explicit HexagonLoopIdiomRecognize(AliasAnalysis *AA, DominatorTree *DT,
+                                     LoopInfo *LF, const TargetLibraryInfo *TLI,
+                                     ScalarEvolution *SE)
+      : AA(AA), DT(DT), LF(LF), TLI(TLI), SE(SE) {}
+
+  bool run(Loop *L);
+
+private:
+  int getSCEVStride(const SCEVAddRecExpr *StoreEv);
+  bool isLegalStore(Loop *CurLoop, StoreInst *SI);
+  void collectStores(Loop *CurLoop, BasicBlock *BB,
+                     SmallVectorImpl<StoreInst *> &Stores);
+  bool processCopyingStore(Loop *CurLoop, StoreInst *SI, const SCEV *BECount);
+  bool coverLoop(Loop *L, SmallVectorImpl<Instruction *> &Insts) const;
+  bool runOnLoopBlock(Loop *CurLoop, BasicBlock *BB, const SCEV *BECount,
+                      SmallVectorImpl<BasicBlock *> &ExitBlocks);
+  bool runOnCountableLoop(Loop *L);
+
+  AliasAnalysis *AA;
+  const DataLayout *DL;
+  DominatorTree *DT;
+  LoopInfo *LF;
+  const TargetLibraryInfo *TLI;
+  ScalarEvolution *SE;
+  bool HasMemcpy, HasMemmove;
+};
+
+class HexagonLoopIdiomRecognizeLegacyPass : public LoopPass {
 
-    explicit HexagonLoopIdiomRecognize() : LoopPass(ID) {
-      initializeHexagonLoopIdiomRecognizePass(*PassRegistry::getPassRegistry());
-    }
+  explicit HexagonLoopIdiomRecognizeLegacyPass() : LoopPass(ID) {
+    initializeHexagonLoopIdiomRecognizeLegacyPassPass(
+        *PassRegistry::getPassRegistry());
 
-    StringRef getPassName() const override {
-      return "Recognize Hexagon-specific loop idioms";
-    }
 
-   void getAnalysisUsage(AnalysisUsage &AU) const override {
-      AU.addRequired<LoopInfoWrapperPass>();
-      AU.addRequiredID(LoopSimplifyID);
-      AU.addRequiredID(LCSSAID);
-      AU.addRequired<AAResultsWrapperPass>();
-      AU.addPreserved<AAResultsWrapperPass>();
-      AU.addRequired<ScalarEvolutionWrapperPass>();
-      AU.addRequired<DominatorTreeWrapperPass>();
-      AU.addRequired<TargetLibraryInfoWrapperPass>();
-      AU.addPreserved<TargetLibraryInfoWrapperPass>();
-    }
 
-    bool runOnLoop(Loop *L, LPPassManager &LPM) override;
-
-  private:
-    int getSCEVStride(const SCEVAddRecExpr *StoreEv);
-    bool isLegalStore(Loop *CurLoop, StoreInst *SI);
-    void collectStores(Loop *CurLoop, BasicBlock *BB,
-        SmallVectorImpl<StoreInst*> &Stores);
-    bool processCopyingStore(Loop *CurLoop, StoreInst *SI, const SCEV *BECount);
-    bool coverLoop(Loop *L, SmallVectorImpl<Instruction*> &Insts) const;
-    bool runOnLoopBlock(Loop *CurLoop, BasicBlock *BB, const SCEV *BECount,
-        SmallVectorImpl<BasicBlock*> &ExitBlocks);
-    bool runOnCountableLoop(Loop *L);
-
-    AliasAnalysis *AA;
-    const DataLayout *DL;
-    DominatorTree *DT;
-    LoopInfo *LF;
-    const TargetLibraryInfo *TLI;
-    ScalarEvolution *SE;
-    bool HasMemcpy, HasMemmove;
-  };
 
-  struct Simplifier {
-    struct Rule {
-      using FuncType = std::function<Value* (Instruction*, LLVMContext&)>;
-      Rule(StringRef N, FuncType F) : Name(N), Fn(F) {}
-      StringRef Name;   // For debugging.
-      FuncType Fn;
-    };
+    using FuncType = std::function<Value *(Instruction *, LLVMContext &)>;
+    StringRef Name; // For debugging.
 
-    void addRule(StringRef N, const Rule::FuncType &F) {
-      Rules.push_back(Rule(N, F));
-    }
 
-  private:
-    struct WorkListType {
-      WorkListType() = default;
 
-      void push_back(Value* V) {
-        // Do not push back duplicates.
-        if (!S.count(V)) { Q.push_back(V); S.insert(V); }
-      }
+    void push_back(Value *V) {
+      if (!S.count(V)) {
+        Q.push_back(V);
+        S.insert(V);
+      }
 
-      Value *pop_front_val() {
-        Value *V = Q.front(); Q.pop_front(); S.erase(V);
-        return V;
-      }
+      Value *V = Q.front();
+      Q.pop_front();
+      S.erase(V);
 
-      bool empty() const { return Q.empty(); }
 
-    private:
-      std::deque<Value*> Q;
-      std::set<Value*> S;
-    };
+    std::deque<Value *> Q;
+    std::set<Value *> S;
 
-    using ValueSetType = std::set<Value *>;
 
-    std::vector<Rule> Rules;
 
-  public:
-    struct Context {
-      using ValueMapType = DenseMap<Value *, Value *>;
 
-      Value *Root;
-      ValueSetType Used;    // The set of all cloned values used by Root.
-      ValueSetType Clones;  // The set of all cloned values.
-      LLVMContext &Ctx;
+    ValueSetType Used;   // The set of all cloned values used by Root.
+    ValueSetType Clones; // The set of all cloned values.
 
-      Context(Instruction *Exp)
         : Ctx(Exp->getParent()->getParent()->getContext()) {
-        initialize(Exp);
-      }
 
-      ~Context() { cleanup(); }
 
-      void print(raw_ostream &OS, const Value *V) const;
-      Value *materialize(BasicBlock *B, BasicBlock::iterator At);
 
-    private:
-      friend struct Simplifier;
 
-      void initialize(Instruction *Exp);
-      void cleanup();
 
-      template <typename FuncT> void traverse(Value *V, FuncT F);
-      void record(Value *V);
-      void use(Value *V);
-      void unuse(Value *V);
 
-      bool equal(const Instruction *I, const Instruction *J) const;
-      Value *find(Value *Tree, Value *Sub) const;
-      Value *subst(Value *Tree, Value *OldV, Value *NewV);
-      void replace(Value *OldV, Value *NewV);
-      void link(Instruction *I, BasicBlock *B, BasicBlock::iterator At);
-    };
 
-    Value *simplify(Context &C);
-  };
 
   struct PE {
     PE(const Simplifier::Context &c, Value *v = nullptr) : C(c), V(v) {}
 
     const Simplifier::Context &C;
     const Value *V;
   };
 
   LLVM_ATTRIBUTE_USED
   raw_ostream &operator<<(raw_ostream &OS, const PE &P) {
     P.C.print(OS, P.V ? P.V : P.C.Root);
     return OS;
   }
 
 } // end anonymous namespace
 
-char HexagonLoopIdiomRecognize::ID = 0;
+char HexagonLoopIdiomRecognizeLegacyPass::ID = 0;
 
-INITIALIZE_PASS_BEGIN(HexagonLoopIdiomRecognize, "hexagon-loop-idiom",
+INITIALIZE_PASS_BEGIN(HexagonLoopIdiomRecognizeLegacyPass, "hexagon-loop-idiom",
                       "Recognize Hexagon-specific loop idioms", false, false)
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
 INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
-INITIALIZE_PASS_END(HexagonLoopIdiomRecognize, "hexagon-loop-idiom",
+INITIALIZE_PASS_END(HexagonLoopIdiomRecognizeLegacyPass, "hexagon-loop-idiom",
                     "Recognize Hexagon-specific loop idioms", false, false)
 
 template <typename FuncT>
 void Simplifier::Context::traverse(Value *V, FuncT F) {
   WorkListType Q;
   Q.push_back(V);
 
   while (!Q.empty()) {
     Instruction *U = dyn_cast<Instruction>(Q.pop_front_val());
for (auto *BB : L->getBlocks()) {
     if (LF->getLoopFor(BB) != L)
       continue;
     Changed |= runOnLoopBlock(L, BB, BECount, ExitBlocks);
   }
 
   return Changed;
 }
 
-bool HexagonLoopIdiomRecognize::runOnLoop(Loop *L, LPPassManager &LPM) {
+bool HexagonLoopIdiomRecognize::run(Loop *L) {
   const Module &M = *L->getHeader()->getParent()->getParent();
   if (Triple(M.getTargetTriple()).getArch() != Triple::hexagon)
     return false;
 
-  if (skipLoop(L))
-    return false;
-
   // If the loop could not be converted to canonical form, it must have an
   // indirectbr in it, just give up.
   if (!L->getLoopPreheader())
     return false;
 
   // Disable loop idiom recognition if the function's name is a common idiom.
   StringRef Name = L->getHeader()->getParent()->getName();
   if (Name == "memset" || Name == "memcpy" || Name == "memmove")
     return false;
 
-  AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
   DL = &L->getHeader()->getModule()->getDataLayout();
-  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
-  LF = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
-  TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
-      *L->getHeader()->getParent());
-  SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
 
   HasMemcpy = TLI->has(LibFunc_memcpy);
   HasMemmove = TLI->has(LibFunc_memmove);
 
   if (SE->hasLoopInvariantBackedgeTakenCount(L))
     return runOnCountableLoop(L);
   return false;
 }
 
+bool HexagonLoopIdiomRecognizeLegacyPass::runOnLoop(Loop *L,
+                                                    LPPassManager &LPM) {
+  if (skipLoop(L))
+    return false;
+
+  auto *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
+  auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+  auto *LF = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
+  auto *TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
+      *L->getHeader()->getParent());
+  auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
+  return HexagonLoopIdiomRecognize(AA, DT, LF, TLI, SE).run(L);
+}
+
 Pass *llvm::createHexagonLoopIdiomPass() {
-  return new HexagonLoopIdiomRecognize();
+  return new HexagonLoopIdiomRecognizeLegacyPass();
+}
+
+PreservedAnalyses
+HexagonLoopIdiomRecognitionPass::run(Loop &L, LoopAnalysisManager &AM,
+                                     LoopStandardAnalysisResults &AR,
+                                     LPMUpdater &U) {
+  return HexagonLoopIdiomRecognize(&AR.AA, &AR.DT, &AR.LI, &AR.TLI, &AR.SE)
+                 .run(&L)
+             ? getLoopPassPreservedAnalyses()
+             : PreservedAnalyses::all();
 }

llvm/lib/Target/Hexagon/HexagonTargetMachine.cpp

 //===-- HexagonTargetMachine.cpp - Define TargetMachine for Hexagon -------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
 // Implements the info about Hexagon target spec.
 //
 //===----------------------------------------------------------------------===//
 
 #include "HexagonTargetMachine.h"
 #include "Hexagon.h"
 #include "HexagonISelLowering.h"
+#include "HexagonLoopIdiomRecognition.h"
 #include "HexagonMachineScheduler.h"
 #include "HexagonTargetObjectFile.h"
 #include "HexagonTargetTransformInfo.h"
 #include "HexagonVectorLoopCarriedReuse.h"
 #include "TargetInfo/HexagonTargetInfo.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/CodeGen/TargetPassConfig.h"
 #include "llvm/IR/LegacyPassManager.h"
namespace llvm {
   extern char &HexagonExpandCondsetsID;
   void initializeHexagonBitSimplifyPass(PassRegistry&);
   void initializeHexagonConstExtendersPass(PassRegistry&);
   void initializeHexagonConstPropagationPass(PassRegistry&);
   void initializeHexagonEarlyIfConversionPass(PassRegistry&);
   void initializeHexagonExpandCondsetsPass(PassRegistry&);
   void initializeHexagonGenMuxPass(PassRegistry&);
   void initializeHexagonHardwareLoopsPass(PassRegistry&);
-  void initializeHexagonLoopIdiomRecognizePass(PassRegistry&);
+  void initializeHexagonLoopIdiomRecognizeLegacyPassPass(PassRegistry &);
   void initializeHexagonVectorLoopCarriedReuseLegacyPassPass(PassRegistry &);
   void initializeHexagonNewValueJumpPass(PassRegistry&);
   void initializeHexagonOptAddrModePass(PassRegistry&);
   void initializeHexagonPacketizerPass(PassRegistry&);
   void initializeHexagonRDFOptPass(PassRegistry&);
   void initializeHexagonSplitDoubleRegsPass(PassRegistry&);
   void initializeHexagonVExtractPass(PassRegistry&);
   Pass *createHexagonLoopIdiomPass();
extern "C" LLVM_EXTERNAL_VISIBILITY void LLVMInitializeHexagonTarget() {
 
   PassRegistry &PR = *PassRegistry::getPassRegistry();
   initializeHexagonBitSimplifyPass(PR);
   initializeHexagonConstExtendersPass(PR);
   initializeHexagonConstPropagationPass(PR);
   initializeHexagonEarlyIfConversionPass(PR);
   initializeHexagonGenMuxPass(PR);
   initializeHexagonHardwareLoopsPass(PR);
-  initializeHexagonLoopIdiomRecognizePass(PR);
+  initializeHexagonLoopIdiomRecognizeLegacyPassPass(PR);
   initializeHexagonVectorLoopCarriedReuseLegacyPassPass(PR);
   initializeHexagonNewValueJumpPass(PR);
   initializeHexagonOptAddrModePass(PR);
   initializeHexagonPacketizerPass(PR);
   initializeHexagonRDFOptPass(PR);
   initializeHexagonSplitDoubleRegsPass(PR);
   initializeHexagonVExtractPass(PR);
 }
PMB.addExtension(
       PassManagerBuilder::EP_LoopOptimizerEnd,
       [&](const PassManagerBuilder &, legacy::PassManagerBase &PM) {
         PM.add(createHexagonVectorLoopCarriedReuseLegacyPass());
       });
 }
 
 void HexagonTargetMachine::registerPassBuilderCallbacks(PassBuilder &PB,
                                                         bool DebugPassManager) {
+  PB.registerLateLoopOptimizationsEPCallback(
+      [=](LoopPassManager &LPM, PassBuilder::OptimizationLevel Level) {
+        LPM.addPass(HexagonLoopIdiomRecognitionPass());
+      });
   PB.registerOptimizerLastEPCallback(
       [=](ModulePassManager &MPM, PassBuilder::OptimizationLevel Level) {
         LoopPassManager LPM(DebugPassManager);
         FunctionPassManager FPM(DebugPassManager);
         LPM.addPass(HexagonVectorLoopCarriedReusePass());
         FPM.addPass(createFunctionToLoopPassAdaptor(std::move(LPM)));
         MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
       });

llvm/test/CodeGen/Hexagon/loop-idiom/pmpy-mod.ll

 ; Run -O2 to make sure that all the usual optimizations do happen before
 ; the Hexagon loop idiom recognition runs. This is to check that we still
 ; get this opportunity regardless of what happens before.
 
 ; RUN: opt -O2 -march=hexagon -S < %s | FileCheck %s
+; RUN: opt -aa-pipeline=default -passes='default<O2>' -march=hexagon -S < %s | FileCheck %s
 
 target triple = "hexagon"
 target datalayout = "e-m:e-p:32:32:32-a:0-n16:32-i64:64:64-i32:32:32-i16:16:16-i1:8:8-f32:32:32-f64:64:64-v32:32:32-v64:64:64-v512:512:512-v1024:1024:1024-v2048:2048:2048"
 
 ; CHECK-LABEL: define zeroext i16 @pmpy_mod_lsr
 ; There need to be two pmpy instructions.
 ; CHECK: call i64 @llvm.hexagon.M4.pmpyw
 ; CHECK: call i64 @llvm.hexagon.M4.pmpyw