RFC: Target-specific loop idiom recognition

[kparzysz]

Summary

Hexagon has certain library functions and intrinsics that are specific to that target, and that are equivalent to a code written using loops. To fully exploit these features, the loop-idiom recognition pass would be the best candidate to handle these opportunities, but since it is a target-independent pass, polluting it with target-specific code does not seem like a good idea.

I'm guessing that Hexagon is likely not the only platform with these properties, and certainly there is nothing in the way for any other target to provide their own implementation of some common loop idioms (via hand-optimized library functions, for example).

This is an attempt to create a target-independent interface by which individual targets can provide their own functions to recognize loop idioms. Also, included is a do-nothing demo of how a Hexagon's pass could be hooked up using this interface.

[kparzysz]

You have made significant contributions to either the loop idiom recognition or the target transform info. Could you let me know what you think about this?

[hfinkel]

Is there any aspect of this that is (or will be) specific to loop idiom recognition, or is this just a way for a target to insert a pass at some point early in the pipeline?

[kparzysz]

The target-provided function is invoked in the loop idiom recognition pass, so that's the connection here. It does not have to be that way, and inserting a target-specific pass into the pipeline would also work, but there is no way to accomplish this at the moment.

[jmolloy]

Hi,

I agree with Hal's comment here. I don't see the value-add for other targets from this approach.

What's the value of calling this from LIR? Your hook isn't leveraging off of any of LIR's infrastructure, and that is the usual goal. "Take out what is target independent, and keep what is not" - There's no target independent stuff being hoisted here, you're just running a pass on a loop. You can do that without LIR.

I think you'd have to describe some functionality being shared here before I'll be fully convinced.

Cheers,

James

[hfinkel]

See also my comments here: http://lists.llvm.org/pipermail/llvm-dev/2015-August/089190.html

-Hal

• Original Message -----

From: "James Molloy" <[e-mail]>
To: [e-mail], [e-mail], "benny kra" <[e-mail]>, [e-mail],
[e-mail], [e-mail], [e-mail]
Cc: "james molloy" <[e-mail]>, "ted woodward" <[e-mail]>, [e-mail]
Sent: Thursday, August 13, 2015 2:54:43 AM
Subject: Re: [PATCH] D11782: RFC: Target-specific loop idiom recognition

jmolloy added a subscriber: jmolloy.
jmolloy added a comment.

Hi,

I agree with Hal's comment here. I don't see the value-add for other
targets from this approach.

What's the value of calling this from LIR? Your hook isn't leveraging
off of any of LIR's infrastructure, and that is the usual goal.
"Take out what is target independent, and keep what is not" -
There's no target independent stuff being hoisted here, you're just
running a pass on a loop. You can do that without LIR.

I think you'd have to describe some functionality being shared here
before I'll be fully convinced.

Cheers,

James

Repository:

rL LLVM

http://reviews.llvm.org/D11782

[kparzysz]

In D11782#223545, @jmolloy wrote:

What's the value of calling this from LIR?

As per my previous reply---the value is that the target-specific hook runs at the same time as the regular LIR. This is important not because there is anything shared between the two, but because the loops are "in the right shape" for doing such transformation. Also, as I said earlier, inserting a target-specific pass into the optimization sequence at that point would work, but there is no way of doing it right now: there is no extension point at where LIR runs right now. If the approach described in the email that Hal added in his comment was implemented (including an extension point for LIR), this would work for me just fine.

[sanjoy]

You have made significant contributions to either the loop idiom recognition or the target transform info.

No I haven't. :)

include/llvm/Analysis/TargetTransformInfo.h

   Value *PtrVal;
 };
 
+/// \brief This class provides a function that implements target-specific
+/// loop idiom recognition. Targets that want to handle specific loop idioms
+/// should implement this class and return a pointer to it from their
+/// respective TTI implementations.
+/// See \c TargetTransformInfo::getTargetLoopIdiomRecognize below.
+class TargetLoopIdiomRecognize {
+public:
+  virtual bool run(Pass *P, Loop *L) = 0;
+  virtual ~TargetLoopIdiomRecognize() {}
+};
+
 /// \brief This pass provides access to the codegen interfaces that are needed
 /// for IR-level transformations.
 class TargetTransformInfo {

                     Type *Ty) const;
   int getIntImmCost(Intrinsic::ID IID, unsigned Idx, const APInt &Imm,
                     Type *Ty) const;
+
+  /// \brief Get a class implementing target-specific loop idiom recognition,
+  /// or nullptr if the target does not require handling of specific loop
+  /// idioms.
+  TargetLoopIdiomRecognize *getTargetLoopIdiomRecognize() const;
+
   /// @}
 
   /// \name Vector Target Information

                             Type *Ty) = 0;
   virtual int getIntImmCost(Intrinsic::ID IID, unsigned Idx, const APInt &Imm,
                             Type *Ty) = 0;
+  virtual TargetLoopIdiomRecognize *getTargetLoopIdiomRecognize() = 0;
   virtual unsigned getNumberOfRegisters(bool Vector) = 0;
   virtual unsigned getRegisterBitWidth(bool Vector) = 0;
   virtual unsigned getMaxInterleaveFactor(unsigned VF) = 0;

                     Type *Ty) override {
     return Impl.getIntImmCost(IID, Idx, Imm, Ty);
   }
+  TargetLoopIdiomRecognize *getTargetLoopIdiomRecognize() override {
+    return Impl.getTargetLoopIdiomRecognize();
+  }
   unsigned getNumberOfRegisters(bool Vector) override {
     return Impl.getNumberOfRegisters(Vector);
   }

include/llvm/Analysis/TargetTransformInfoImpl.h

     return TTI::TCC_Free;
   }
 
+  TargetLoopIdiomRecognize *getTargetLoopIdiomRecognize() { return nullptr; }
+
   unsigned getNumberOfRegisters(bool Vector) { return 8; }
 
   unsigned getRegisterBitWidth(bool Vector) { return 32; }

lib/Analysis/TargetTransformInfo.cpp

   return Cost;
 }
 
+TargetLoopIdiomRecognize *TargetTransformInfo::getTargetLoopIdiomRecognize()
+      const {
+  return TTIImpl->getTargetLoopIdiomRecognize();
+}
+
 unsigned TargetTransformInfo::getNumberOfRegisters(bool Vector) const {
   return TTIImpl->getNumberOfRegisters(Vector);
 }

lib/Target/Hexagon/CMakeLists.txt

   HexagonInstrInfo.cpp
   HexagonISelDAGToDAG.cpp
   HexagonISelLowering.cpp
+  HexagonLoopIdiomRecognize.cpp
   HexagonMachineFunctionInfo.cpp
   HexagonMachineScheduler.cpp
   HexagonMCInstLower.cpp

lib/Target/Hexagon/HexagonLoopIdiomRecognize.h

+#include "llvm/Analysis/LoopPass.h"
+#include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/Pass.h"
+
+using namespace llvm;
+
+namespace llvm {
+  class HexagonLoopIdiomRecognize : public TargetLoopIdiomRecognize {
+  public:
+    bool run(Pass *P, Loop *L) override;
+  };
+}

lib/Target/Hexagon/HexagonLoopIdiomRecognize.cpp

+#define DEBUG_TYPE "hexidiom"
+
+#include "HexagonLoopIdiomRecognize.h"
+#include "llvm/ADT/SetVector.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Analysis/InstructionSimplify.h"
+#include "llvm/Analysis/ScalarEvolution.h"
+#include "llvm/Analysis/ScalarEvolutionExpressions.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
+#include "llvm/Analysis/ValueTracking.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/PatternMatch.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/Utils/Local.h"
+
+using namespace llvm;
+
+bool llvm::HexagonLoopIdiomRecognize::run(Pass *P, Loop *L) {
+  BasicBlock *Header = L->getHeader();
+  if (!Header)
+    return false;
+
+  auto *DL = &Header->getParent()->getParent()->getDataLayout();
+  auto *DTW = P->getAnalysisIfAvailable<DominatorTreeWrapperPass>();
+  auto *TLIW = P->getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
+  auto *SE = P->getAnalysisIfAvailable<ScalarEvolution>();
+
+  (void)DL;
+  if (!DTW || !TLIW || !SE)
+    return false;
+
+  dbgs() << "Hello, all is in order\n";
+  return false;
+}
+

lib/Target/Hexagon/HexagonTargetMachine.cpp

   return I.get();
 }
 
+static HexagonLoopIdiomRecognize HLIR;
+
 TargetIRAnalysis HexagonTargetMachine::getTargetIRAnalysis() {
   return TargetIRAnalysis([this](Function &F) {
-    return TargetTransformInfo(HexagonTTIImpl(this, F));
+    return TargetTransformInfo(HexagonTTIImpl(this, F, &HLIR));
   });
 }
 

lib/Target/Hexagon/HexagonTargetTransformInfo.h

 
 #include "Hexagon.h"
 #include "HexagonTargetMachine.h"
+#include "HexagonLoopIdiomRecognize.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/CodeGen/BasicTTIImpl.h"
 #include "llvm/Target/TargetLowering.h"

 
   const HexagonSubtarget *ST;
   const HexagonTargetLowering *TLI;
+  HexagonLoopIdiomRecognize *HLIR;
 
   const HexagonSubtarget *getST() const { return ST; }
   const HexagonTargetLowering *getTLI() const { return TLI; }
 
 public:
-  explicit HexagonTTIImpl(const HexagonTargetMachine *TM, Function &F)
+  explicit HexagonTTIImpl(const HexagonTargetMachine *TM, Function &F,
+                          HexagonLoopIdiomRecognize *LIR)
       : BaseT(TM, F.getParent()->getDataLayout()), ST(TM->getSubtargetImpl(F)),
-        TLI(ST->getTargetLowering()) {}
+        TLI(ST->getTargetLowering()), HLIR(LIR) {}
 
   // Provide value semantics. MSVC requires that we spell all of these out.
   HexagonTTIImpl(const HexagonTTIImpl &Arg)
-      : BaseT(static_cast<const BaseT &>(Arg)), ST(Arg.ST), TLI(Arg.TLI) {}
+      : BaseT(static_cast<const BaseT &>(Arg)), ST(Arg.ST), TLI(Arg.TLI),
+        HLIR(Arg.HLIR) {}
   HexagonTTIImpl(HexagonTTIImpl &&Arg)
       : BaseT(std::move(static_cast<BaseT &>(Arg))), ST(std::move(Arg.ST)),
-        TLI(std::move(Arg.TLI)) {}
+        TLI(std::move(Arg.TLI)), HLIR(std::move(Arg.HLIR)) {}
 
   /// \name Scalar TTI Implementations
   /// @{

   // The Hexagon target can unroll loops with run-time trip counts.
   void getUnrollingPreferences(Loop *L, TTI::UnrollingPreferences &UP);
 
+  HexagonLoopIdiomRecognize *getTargetLoopIdiomRecognize() const {
+    return HLIR;
+  }
+
   /// @}
 
   /// \name Vector TTI Implementations

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

     return false;
 
   SE = &getAnalysis<ScalarEvolution>();
-  if (SE->hasLoopInvariantBackedgeTakenCount(L))
-    return runOnCountableLoop();
-  return runOnNoncountableLoop();
+  bool HasInvCount = SE->hasLoopInvariantBackedgeTakenCount(L);
+  bool Changed = HasInvCount ? runOnCountableLoop()
+                             : runOnNoncountableLoop();
+
+  if (auto *TLIR = getTargetTransformInfo()->getTargetLoopIdiomRecognize())
+    Changed |= TLIR->run(this, L);
+
+  return Changed;
 }
 
 /// runOnLoopBlock - Process the specified block, which lives in a counted loop