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

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

88

Description comments should be in the pass file instead

lib/Target/AMDGPU/AMDGPU64bitDivision.cpp

8 ↗

(On Diff #50381)

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

lib/Target/AMDGPU/AMDGPU64bitDivision.h

1–2

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

3–6

You don't need these

8–14

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

257–260

Random whitespace change

lib/Target/AMDGPU/AMDGPUIntegerDivisionPass.cpp

1

Name out of date

9–11

This should have a description or be removed

13

AMDGPU.h should be the first included file

27

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

37

This should be removed

67

Dead code

70–74

Dead code

90–91

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

93

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

106

You can do Type->isIntegerTy(64)

150

This shouldn't be here

lib/Target/AMDGPU/AMDGPUTargetMachine.cpp

39 ↗

(On Diff #50381)

Random whitespace

56 ↗

(On Diff #50381)

Comment not needed

207 ↗

(On Diff #50381)

Comments should never include names

208 ↗

(On Diff #50381)

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

[• tstellarAMD]

include/llvm/CodeGen/Passes.h

395–397

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

649–650

This should go in AMDGPU.h too.

include/llvm/InitializePasses.h

152

This in AMDGPU.h too.

include/llvm/LinkAllPasses.h

148–149

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/CodeGen/Passes.h

namespace llvm {
   /// createCodeGenPreparePass - Transform the code to expose more pattern
   /// matching during instruction selection.
   FunctionPass *createCodeGenPreparePass(const TargetMachine *TM = nullptr);
 
   /// AtomicExpandID -- Lowers atomic operations in terms of either cmpxchg
   /// load-linked/store-conditional loops.
   extern char &AtomicExpandID;
 
-  /// Lowers unsupported integer division.
-  extern char &IntegerDivisionID;
-
   /// MachineLoopInfo - This pass is a loop analysis pass.
   extern char &MachineLoopInfoID;
 
   /// MachineDominators - This pass is a machine dominators analysis pass.
   extern char &MachineDominatorsID;
 
 /// MachineDominanaceFrontier - This pass is a machine dominators analysis pass.
   extern char &MachineDominanceFrontierID;
 
   /// EdgeBundles analysis - Bundle machine CFG edges.
   extern char &EdgeBundlesID;
/// MachineDominanaceFrontier - This pass is a machine dominators analysis pass.
   extern char &StackMapLivenessID;
 
   /// LiveDebugValues pass
   extern char &LiveDebugValuesID;
 
   /// createJumpInstrTables - This pass creates jump-instruction tables.
   ModulePass *createJumpInstrTablesPass();
 
-  /// Lower unsupported integer division
-  FunctionPass *createIntegerDivisionPass(const TargetMachine *TM);
-
   /// createForwardControlFlowIntegrityPass - This pass adds control-flow
   /// integrity.
   ModulePass *createForwardControlFlowIntegrityPass();
 
   /// InterleavedAccess Pass - This pass identifies and matches interleaved
   /// memory accesses to target specific intrinsics.
   ///
   FunctionPass *createInterleavedAccessPass(const TargetMachine *TM);
 } // End llvm namespace
 

include/llvm/InitializePasses.h

 void initializeIfConverterPass(PassRegistry&);
 void initializeInductiveRangeCheckEliminationPass(PassRegistry&);
 void initializeIndVarSimplifyPass(PassRegistry&);
 void initializeInferFunctionAttrsLegacyPassPass(PassRegistry&);
 void initializeInlineCostAnalysisPass(PassRegistry&);
 void initializeInstructionCombiningPassPass(PassRegistry&);
 void initializeInstCountPass(PassRegistry&);
 void initializeInstNamerPass(PassRegistry&);
-void initializeIntegerDivisionPass(PassRegistry&);
 void initializeInternalizePassPass(PassRegistry&);
 void initializeIntervalPartitionPass(PassRegistry&);
 void initializeJumpThreadingPass(PassRegistry&);
 void initializeLCSSAPass(PassRegistry&);
 void initializeLICMPass(PassRegistry&);
 void initializeLazyValueInfoPass(PassRegistry&);
 void initializeLintPass(PassRegistry&);
 void initializeLiveDebugVariablesPass(PassRegistry&);
 void initializeLiveIntervalsPass(PassRegistry&);

include/llvm/LinkAllPasses.h

ForcePassLinking() {
       (void) llvm::createScalarReplAggregatesPass();
       (void) llvm::createSingleLoopExtractorPass();
       (void) llvm::createStripSymbolsPass();
       (void) llvm::createStripNonDebugSymbolsPass();
       (void) llvm::createStripDeadDebugInfoPass();
       (void) llvm::createStripDeadPrototypesPass();
       (void) llvm::createTailCallEliminationPass();
       (void) llvm::createJumpThreadingPass();
-      /*AMDGPU64bit*/
-      //(void) llvm::createIntegerDivisionPass(nullptr);
       (void) llvm::createUnifyFunctionExitNodesPass();
       (void) llvm::createInstCountPass();
       (void) llvm::createConstantHoistingPass();
       (void) llvm::createCodeGenPreparePass();
       (void) llvm::createEarlyCSEPass();
       (void) llvm::createMergedLoadStoreMotionPass();
       (void) llvm::createGVNPass();
       (void) llvm::createMemCpyOptPass();
       (void) llvm::createLoopDeletionPass();
       (void) llvm::createPostDomTree();

lib/Target/AMDGPU/AMDGPU.h

 void initializeSIFixControlFlowLiveIntervalsPass(PassRegistry&);
 extern char &SIFixControlFlowLiveIntervalsID;
 
 void initializeSIFixSGPRLiveRangesPass(PassRegistry&);
 extern char &SIFixSGPRLiveRangesID;
 
 void initializeAMDGPUAnnotateUniformValuesPass(PassRegistry&);
 extern char &AMDGPUAnnotateUniformValuesPassID;
-
-/*Modified Integer Division : IR Pass to perform 64bit integer division*/
-
 void initializeAMDGPUIntegerDivisionPass(PassRegistry&);
 extern char AMDGPU64bitDivisionID;
 
 
 extern Target TheAMDGPUTarget;
 extern Target TheGCNTarget;
 
 namespace AMDGPU {
 enum TargetIndex {

lib/Target/AMDGPU/AMDGPU64bitDivision.h

-#include "AMDGPUISelLowering.h"
-#include "AMDGPU.h"
-#include "AMDGPUDiagnosticInfoUnsupported.h"
-#include "AMDGPUFrameLowering.h"
-#include "AMDGPUIntrinsicInfo.h"
-#include "AMDGPURegisterInfo.h"
-#include "AMDGPUSubtarget.h"
-#include "R600MachineFunctionInfo.h"
-#include "SIMachineFunctionInfo.h"
-#include "llvm/CodeGen/CallingConvLower.h"
-#include "llvm/CodeGen/MachineFunction.h"
-#include "llvm/CodeGen/MachineRegisterInfo.h"
-#include "llvm/CodeGen/SelectionDAG.h"
-#include "llvm/CodeGen/TargetLoweringObjectFileImpl.h"
-#include "llvm/IR/DataLayout.h"
-#include "llvm/IR/IRBuilder.h"
-
 namespace llvm
 {
   class BinaryOperator;
 }
 
 namespace llvm{
 
 
 
 bool AMDExpandUDivision(BinaryOperator *Div);
 
 }
 No newline at end of file

lib/Target/AMDGPU/AMDGPUISelLowering.cpp

for (MVT VT : ScalarIntVTs) {
 
     // GPU does not have [S|U]MUL_LOHI functions as a single instruction.
     setOperationAction(ISD::SMUL_LOHI, VT, Expand);
     setOperationAction(ISD::UMUL_LOHI, VT, Expand);
 
     setOperationAction(ISD::BSWAP, VT, Expand);
     setOperationAction(ISD::CTTZ, VT, Expand);
     setOperationAction(ISD::CTLZ, VT, Expand);
-
-    setOperationAction(ISD::CTLZ_ZERO_UNDEF, VT, Expand);
   }
 
 
 
   if (!Subtarget->hasBCNT(32))
     setOperationAction(ISD::CTPOP, MVT::i32, Expand);
 
   if (!Subtarget->hasBCNT(64))
     setOperationAction(ISD::CTPOP, MVT::i64, Expand);
 
   // The hardware supports 32-bit ROTR, but not ROTL.
   setOperationAction(ISD::ROTL, MVT::i32, Expand);
   setOperationAction(ISD::ROTL, MVT::i64, Expand);

lib/Target/AMDGPU/AMDGPUIntegerDivisionPass.cpp

-//===-- IntegerDivisionPass.cpp - Expand div/mod instructions -------------===//
+//===-- 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
+/// \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 "AMDGPU.h"
 #include "AMDGPU64bitDivision.h"
 
 using namespace llvm;
 
-#define DEBUG_TYPE "AMDGPU integer-division"
+#define DEBUG_TYPE "amdgpu-integer-division"
 
 namespace {
 
 class AMDGPUIntegerDivision : public FunctionPass,
                         public InstVisitor<AMDGPUIntegerDivision, bool> {
 
   const TargetMachine *TM;
   const TargetLowering *TLI;
 
-  int checkingVariable;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 
+  //int checkingVariable;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 
 
   bool shouldExpandDivRem(const BinaryOperator &I);
 
 public:
   static char ID;
   explicit AMDGPUIntegerDivision(const TargetMachine *TM = nullptr)
     : FunctionPass(ID), TM(TM), TLI(nullptr) {
   }
 
public:
   bool visitUDiv(BinaryOperator &I);
   bool visitSRem(BinaryOperator &I);
   bool visitURem(BinaryOperator &I);
 };
 
 } // End anonymous namespace
 
 char AMDGPUIntegerDivision::ID = 0;
-//char &llvm::IntegerDivisionID = AMDGPUIntegerDivision::ID;
 INITIALIZE_TM_PASS(AMDGPUIntegerDivision, DEBUG_TYPE,"Expand integer division", false, false);
-
 char &llvm::AMDGPUIntegerDivisionID = AMDGPUIntegerDivision::ID;
-/*INITIALIZE_PASS_BEGIN(AMDGPUIntegerDivision, DEBUG_TYPE,
-                      "Add AMDGPU function attributes", false, false)
-INITIALIZE_PASS_END(AMDGPUIntegerDivision, DEBUG_TYPE,
-                    "Add AMDGPU function attributes", false, false)*/
 
 bool AMDGPUIntegerDivision::doInitialization(Module &M) {
   return false;
 }
 
 bool AMDGPUIntegerDivision::runOnFunction(Function &F) {
 //  llvm_unreachable("does this happen");
   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);
-  // TODO:Uthkarsh later modify to handle signed 64 bit too.  
-  bool isUdiv64 = I.getOpcode() == Instruction::UDiv &&  I.getType()->getIntegerBitWidth() == 64;
+  bool shouldExpandInIr = TLI && TLI->shouldExpandDivRemInIR(I);  
+  bool isUdiv64 = I.getOpcode() == Instruction::UDiv &&  I.getType()->isIntegerTy(64);
   return shouldExpandInIr && isUdiv64;
 }
 /*TODO:Uthkarsh 
   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)) {
     expandRemainder(&I);
     return true;
   }
   return false;
 }
 
 FunctionPass *llvm::createAMDGPUIntegerDivisionPass(const TargetMachine *TM) {
   return new AMDGPUIntegerDivision(TM);
-}
-
-//static RegisterPass<AMDGPUIntegerDivision> X("AMD GPU Integer Division", "IR level 64 bit integer division",false,false);
+}