Skeleton for the IR level pass to perform 64bit Integer Division

[Uthkarsh]

Summary

This contains the required pass for performing the 64bit integer division at the IR level. The algorithm has not been incorporated yet but just the skeleton is given for review.

[arsenm]

include/llvm/CodeGen/Passes.h

395–397 ↗

(On Diff #50381)

These parts touching generic code should be removed since it is a backend pass now. The IDs etc. declarations should be only in AMDGPU.h

lib/Target/AMDGPU/AMDGPU.h

89

Description comments should be in the pass file instead

lib/Target/AMDGPU/AMDGPU64bitDivision.cpp

9

There should not be a free function like this. This should be a method of the pass

lib/Target/AMDGPU/AMDGPU64bitDivision.h

2–3

This header is unnecessary, this can be done entirely in the one cpp file

4–7

You don't need these

9–15

Also any of these

lib/Target/AMDGPU/AMDGPUISelLowering.cpp

256–257

This looks like an unrelated change, and is also incorrect since this should work already. i32 has an instruction and i64 should already be expanded

259–261

Random whitespace change

lib/Target/AMDGPU/AMDGPUIntegerDivisionPass.cpp

2

Name out of date

10–12

This should have a description or be removed

14

AMDGPU.h should be the first included file

28

This should be all lower case and - separated, otherwise it won't really work as a -debug-only= argument

38

This should be removed

68

Dead code

71–75

Dead code

91–92

You're going to need to pre-increment this pointer to avoid iterator invalidation issues when you delete the original div instruction

94

You can pre-increment the iterators to avoid skipping back to the beginning

107

You can do Type->isIntegerTy(64)

151

This shouldn't be here

lib/Target/AMDGPU/AMDGPUTargetMachine.cpp

39

Random whitespace

56

Comment not needed

207

Comments should never include names

208

I think this should be moved to addCodeGenPrepare after TargetPassConfig::addCodeGenPrepare()

[• tstellarAMD]

include/llvm/CodeGen/Passes.h

395–397 ↗

(On Diff #50381)

Since this is a target specific pass the ID should be defined in AMDGPU.h like the other AMDGPU passes.

652–653 ↗

(On Diff #50381)

This should go in AMDGPU.h too.

include/llvm/InitializePasses.h

152 ↗

(On Diff #50381)

This in AMDGPU.h too.

include/llvm/LinkAllPasses.h

148–149 ↗

(On Diff #50381)

I don't think this is needed.

[Uthkarsh]

Have modified most of the requested changes.

[Uthkarsh]

Unnecessary comments deleted.

[arsenm]

The current diff seems to be just the comment changes

[Uthkarsh]

Consolidated diff of the previous commits, along with the changes.

include/llvm/Target/TargetLowering.h

 
   virtual bool useSoftFloat() const { return false; }
 
+  /// Returns true if the instruction should be expanded by the IR-level
+  /// IntegerDivision pass.
+  virtual bool shouldExpandDivRemInIR(const BinaryOperator &I) const {
+    return false;
+  }
+
   /// Return the pointer type for the given address space, defaults to
   /// the pointer type from the data layout.
   /// FIXME: The default needs to be removed once all the code is updated.

lib/Target/AMDGPU/AMDGPU.h

 FunctionPass *createSIInsertWaits(TargetMachine &tm);
 
 ModulePass *createAMDGPUAnnotateKernelFeaturesPass();
+/*Modified Integer Division*/
+FunctionPass *createAMDGPUIntegerDivisionPass(const TargetMachine *TM);
+extern char &AMDGPUIntegerDivisionID;
+
 void initializeAMDGPUAnnotateKernelFeaturesPass(PassRegistry &);
 extern char &AMDGPUAnnotateKernelFeaturesID;
 

 
 void initializeAMDGPUAnnotateUniformValuesPass(PassRegistry&);
 extern char &AMDGPUAnnotateUniformValuesPassID;
+void initializeAMDGPUIntegerDivisionPass(PassRegistry&);
+extern char AMDGPU64bitDivisionID;
+
 
 extern Target TheAMDGPUTarget;
 extern Target TheGCNTarget;

lib/Target/AMDGPU/AMDGPU64bitDivision.h

+namespace llvm
+{
+  class BinaryOperator;
+}
+
+namespace llvm{
+
+
+
+bool AMDExpandUDivision(BinaryOperator *Div);
+
+}
 No newline at end of file

lib/Target/AMDGPU/AMDGPU64bitDivision.cpp

+#include "AMDGPU64bitDivision.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/IR/Instructions.h"
+
+using namespace llvm;
+
+
+bool llvm::AMDExpandUDivision(BinaryOperator *Div)
+{
+
+  errs()<<"\n AMDExpandUDivision Called\n";
+
+  return true;
+
+}

lib/Target/AMDGPU/AMDGPUISelLowering.h

 public:
   AMDGPUTargetLowering(TargetMachine &TM, const AMDGPUSubtarget &STI);
 
+  bool shouldExpandDivRemInIR(const BinaryOperator &I) const override {
+    return true;
+  }
+
   bool isFAbsFree(EVT VT) const override;
   bool isFNegFree(EVT VT) const override;
   bool isTruncateFree(EVT Src, EVT Dest) const override;

lib/Target/AMDGPU/AMDGPUISelLowering.cpp

     setOperationAction(ISD::CTLZ, VT, Expand);
   }
 
+
+
   if (!Subtarget->hasBCNT(32))
     setOperationAction(ISD::CTPOP, MVT::i32, Expand);
 

   return DAG.getMergeValues(Res, DL);
 }
 
+// FIXME: This seems to be extremely inefficient. SC produces almost 1/3rd as
+// many instructions for i64 udiv.
 void AMDGPUTargetLowering::LowerUDIVREM64(SDValue Op,
                                       SelectionDAG &DAG,
                                       SmallVectorImpl<SDValue> &Results) const {

lib/Target/AMDGPU/AMDGPUIntegerDivisionPass.cpp

+//===-- AMDGPUIntegerDivisionPass.cpp - Expand div/mod instructions -------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+/// \file: An IR level pass to perform 64bit Integer division
+//===----------------------------------------------------------------------===//
+
+/*Modified Integer Division Pass*/
+#include "AMDGPU.h"
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/InstVisitor.h"
+#include "llvm/Target/TargetLowering.h"
+#include "llvm/Target/TargetMachine.h"
+#include "llvm/Target/TargetSubtargetInfo.h"
+#include "llvm/Transforms/Utils/IntegerDivision.h"
+#include "AMDGPU64bitDivision.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "amdgpu-integer-division"
+
+namespace {
+
+class AMDGPUIntegerDivision : public FunctionPass,
+                        public InstVisitor<AMDGPUIntegerDivision, bool> {
+
+  const TargetMachine *TM;
+  const TargetLowering *TLI;
+
+  //int checkingVariable;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 
+
+  bool shouldExpandDivRem(const BinaryOperator &I);
+
+public:
+  static char ID;
+  explicit AMDGPUIntegerDivision(const TargetMachine *TM = nullptr)
+    : FunctionPass(ID), TM(TM), TLI(nullptr) {
+  }
+
+  bool doInitialization(Module &M) override;
+  bool runOnFunction(Function &F) override;
+
+  const char *getPassName() const override {
+    return "Integer Division Pass";
+  }
+
+  bool visitInstruction(Instruction &I) {
+    return false;
+  }
+
+  bool visitSDiv(BinaryOperator &I);
+  bool visitUDiv(BinaryOperator &I);
+  bool visitSRem(BinaryOperator &I);
+  bool visitURem(BinaryOperator &I);
+};
+
+} // End anonymous namespace
+
+char AMDGPUIntegerDivision::ID = 0;
+INITIALIZE_TM_PASS(AMDGPUIntegerDivision, DEBUG_TYPE,"Expand integer division", false, false);
+char &llvm::AMDGPUIntegerDivisionID = AMDGPUIntegerDivision::ID;
+
+bool AMDGPUIntegerDivision::doInitialization(Module &M) {
+  return false;
+}
+
+bool AMDGPUIntegerDivision::runOnFunction(Function &F) {
+  if (TM)
+    TLI = TM->getSubtargetImpl(F)->getTargetLowering();
+
+  else 
+    errs()<<"\n Target Machine Not Initialized\n";
+
+  for (Function::iterator BBI = F.begin(), BBE = F.end(); BBI != BBE; ++BBI) {
+    BasicBlock *BB = &*BBI;
+    for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); II != IE; ++II) {
+      Instruction *I = &*II;
+      if (visit(*I)) {
+        BBI = F.begin();
+        break;
+      }
+    }
+  }
+
+  return false;
+}
+
+bool AMDGPUIntegerDivision::shouldExpandDivRem(const BinaryOperator &I) {
+  assert(TLI);
+  bool shouldExpandInIr = TLI && TLI->shouldExpandDivRemInIR(I);  
+  bool isUdiv64 = I.getOpcode() == Instruction::UDiv &&  I.getType()->isIntegerTy(64);
+  return shouldExpandInIr && isUdiv64;
+}
+/* 
+  Change the function calls to your own menthods instead of the in-built integer division which
+  introduces more control flow. 
+*/
+bool AMDGPUIntegerDivision::visitSDiv(BinaryOperator &I) {
+  if (shouldExpandDivRem(I)) {
+    expandDivision(&I);
+    return true;
+  }
+  return false;
+}
+
+bool AMDGPUIntegerDivision::visitUDiv(BinaryOperator &I) {
+  // Should call the underlying IR expansion only for 64 bit divisions
+  if (shouldExpandDivRem(I)) {
+    AMDExpandUDivision(&I);
+    return true;
+  }
+  return false;
+}
+
+bool AMDGPUIntegerDivision::visitSRem(BinaryOperator &I) {
+  if (shouldExpandDivRem(I)) {
+    expandRemainder(&I);
+    return true;
+  }
+  return false;
+}
+
+bool AMDGPUIntegerDivision::visitURem(BinaryOperator &I) {
+  if (shouldExpandDivRem(I)) {
+    expandRemainder(&I);
+    return true;
+  }
+  return false;
+}
+
+FunctionPass *llvm::createAMDGPUIntegerDivisionPass(const TargetMachine *TM) {
+  return new AMDGPUIntegerDivision(TM);
+}
 No newline at end of file

lib/Target/AMDGPU/AMDGPUTargetMachine.cpp

 #include "llvm/Transforms/Scalar.h"
 #include <llvm/CodeGen/Passes.h>
 
+
 using namespace llvm;
 
 extern "C" void LLVMInitializeAMDGPUTarget() {

   initializeSILoadStoreOptimizerPass(*PR);
   initializeAMDGPUAnnotateKernelFeaturesPass(*PR);
   initializeAMDGPUAnnotateUniformValuesPass(*PR);
+  /*Modified Integer Division Pass*/
+  initializeAMDGPUIntegerDivisionPass(*PR);
+
 }
 
 static std::unique_ptr<TargetLoweringObjectFile> createTLOF(const Triple &TT) {

 
   // Handle uses of OpenCL image2d_t, image3d_t and sampler_t arguments.
   addPass(createAMDGPUOpenCLImageTypeLoweringPass());
-
+  addPass(createAMDGPUIntegerDivisionPass(&getAMDGPUTargetMachine()));
   TargetPassConfig::addIRPasses();
 }
 

     addPass(createAMDGPUPromoteAlloca(ST));
     addPass(createSROAPass());
   }
+
   TargetPassConfig::addCodeGenPrepare();
+
+  //  addPass(createIntegerDivisionPass(&getAMDGPUTargetMachine()));
 }
 
 bool

lib/Target/AMDGPU/CMakeLists.txt

 add_public_tablegen_target(AMDGPUCommonTableGen)
 
 add_llvm_target(AMDGPUCodeGen
+  AMDGPU64bitDivision.cpp
+  AMDGPU64bitDivision.h
   AMDILCFGStructurizer.cpp
   AMDGPUAlwaysInlinePass.cpp
   AMDGPUAnnotateKernelFeatures.cpp

   AMDGPUInstrInfo.cpp
   AMDGPUPromoteAlloca.cpp
   AMDGPURegisterInfo.cpp
+  AMDGPUIntegerDivisionPass.cpp
   R600ClauseMergePass.cpp
   R600ControlFlowFinalizer.cpp
   R600EmitClauseMarkers.cpp

tools/opt/opt.cpp

   // supported.
   initializeCodeGenPreparePass(Registry);
   initializeAtomicExpandPass(Registry);
+  initializeIntegerDivisionPass(Registry);
   initializeRewriteSymbolsPass(Registry);
   initializeWinEHPreparePass(Registry);
   initializeDwarfEHPreparePass(Registry);