MachineCSE: Add a target query for the LookAheadLimit heurisitic

[• tstellarAMD]

Summary

This heurisitc is used to determine whether or not to CSE physical register defs. My understanding is that this pass will only CSE a physical register def that is within 'LookAheadLimit' instructions of a common expression.

I'm adding a target query for this because the R600 backend needs this LookAheadLimit to be MAX_UINT.

I'm not sure what the original intent of this heuristic was and why the value is 5, so another possibility would be to remove it entirely.

[MatzeB]

Hi Tom,

I don't know the history here, but as this does scan forward for each instruction of the basic block it looks like a way to avoid quadratic runtime behavior for (corner) cases with thousands of instructions in a basic block. I think it is no problem to go to a much higher limit than 5. But why go completely boundless, do you need a guarantee here that the CSE is happening?

• Matthias

[• tstellarAMD]

In D9472#165425, @MatzeB wrote:

Hi Tom,

I don't know the history here, but as this does scan forward for each instruction of the basic block it looks like a way to avoid quadratic runtime behavior for (corner) cases with thousands of instructions in a basic block. I think it is no problem to go to a much higher limit than 5. But why go completely boundless, do you need a guarantee here that the CSE is happening?

Yes, I would like a guarantee that CSE is happening. For AMD GPUs, there is a control register (m0), which is used to clamp memory addresses to avoid out of bound reads and writes. Before each load/store instruction, we emit: s_mov_b32 m0, -1 (-1 disables address clamping) and then rely on MachineCSE to eliminate all the unnecessary moves.

[MatzeB]

In D9472#165495, @tstellarAMD wrote:

In D9472#165425, @MatzeB wrote:

Hi Tom,

I don't know the history here, but as this does scan forward for each instruction of the basic block it looks like a way to avoid quadratic runtime behavior for (corner) cases with thousands of instructions in a basic block. I think it is no problem to go to a much higher limit than 5. But why go completely boundless, do you need a guarantee here that the CSE is happening?

Yes, I would like a guarantee that CSE is happening. For AMD GPUs, there is a control register (m0), which is used to clamp memory addresses to avoid out of bound reads and writes. Before each load/store instruction, we emit: s_mov_b32 m0, -1 (-1 disables address clamping) and then rely on MachineCSE to eliminate all the unnecessary moves.

I assume SelectionDAG CSE isn't enough for you because it does not cover multiple blocks. I'm not happy about the quadratic runtime resulting from an unbounded search, but as this is a target specific option, the patch LGTM.

[hfinkel]

include/llvm/Target/TargetInstrInfo.h

1242 ↗

(On Diff #24880)

Can we just say something like, "The default lookahead is small to prevent unprofitable quadratic behavior." Next year, no one will know to whom "I" refers without a lot of work ;)

llvm/trunk/include/llvm/Target/TargetInstrInfo.h

areMemAccessesTriviallyDisjoint(MachineInstr *MIa, MachineInstr *MIb,
                                   AliasAnalysis *AA = nullptr) const {
     assert(MIa && (MIa->mayLoad() || MIa->mayStore()) &&
            "MIa must load from or modify a memory location");
     assert(MIb && (MIb->mayLoad() || MIb->mayStore()) &&
            "MIb must load from or modify a memory location");
     return false;
   }
 
+  /// \brief Return the value to use for the MachineCSE's LookAheadLimit,
+  /// which is a heuristic used for CSE'ing phys reg defs.
+  virtual unsigned getMachineCSELookAheadLimit () const {
+    // The default lookahead is small to prevent unprofitable quadratic
+    // behavior.
+    return 5;
+  }
+
 private:
   int CallFrameSetupOpcode, CallFrameDestroyOpcode;
 };
 
 } // End llvm namespace
 
 #endif

llvm/trunk/lib/CodeGen/MachineCSE.cpp

namespace {
   class MachineCSE : public MachineFunctionPass {
     const TargetInstrInfo *TII;
     const TargetRegisterInfo *TRI;
     AliasAnalysis *AA;
     MachineDominatorTree *DT;
     MachineRegisterInfo *MRI;
   public:
     static char ID; // Pass identification
-    MachineCSE() : MachineFunctionPass(ID), LookAheadLimit(5), CurrVN(0) {
+    MachineCSE() : MachineFunctionPass(ID), LookAheadLimit(0), CurrVN(0) {
       initializeMachineCSEPass(*PassRegistry::getPassRegistry());
     }
 
     bool runOnMachineFunction(MachineFunction &MF) override;
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.setPreservesCFG();
       MachineFunctionPass::getAnalysisUsage(AU);
       AU.addRequired<AliasAnalysis>();
       AU.addPreservedID(MachineLoopInfoID);
       AU.addRequired<MachineDominatorTree>();
       AU.addPreserved<MachineDominatorTree>();
     }
 
     void releaseMemory() override {
       ScopeMap.clear();
       Exps.clear();
     }
 
   private:
-    const unsigned LookAheadLimit;
+    unsigned LookAheadLimit;
     typedef RecyclingAllocator<BumpPtrAllocator,
         ScopedHashTableVal<MachineInstr*, unsigned> > AllocatorTy;
     typedef ScopedHashTable<MachineInstr*, unsigned,
         MachineInstrExpressionTrait, AllocatorTy> ScopedHTType;
     typedef ScopedHTType::ScopeTy ScopeType;
     DenseMap<MachineBasicBlock*, ScopeType*> ScopeMap;
     ScopedHTType VNT;
     SmallVector<MachineInstr*, 64> Exps;
bool MachineCSE::runOnMachineFunction(MachineFunction &MF) {
   if (skipOptnoneFunction(*MF.getFunction()))
     return false;
 
   TII = MF.getSubtarget().getInstrInfo();
   TRI = MF.getSubtarget().getRegisterInfo();
   MRI = &MF.getRegInfo();
   AA = &getAnalysis<AliasAnalysis>();
   DT = &getAnalysis<MachineDominatorTree>();
+  LookAheadLimit = TII->getMachineCSELookAheadLimit();
   return PerformCSE(DT->getRootNode());
 }

llvm/trunk/lib/Target/R600/SIInstrInfo.h

MachineInstr *buildMovInstr(MachineBasicBlock *MBB,
                               unsigned DstReg, unsigned SrcReg) const override;
   bool isMov(unsigned Opcode) const override;
 
   bool isSafeToMoveRegClassDefs(const TargetRegisterClass *RC) const override;
 
   bool FoldImmediate(MachineInstr *UseMI, MachineInstr *DefMI,
                      unsigned Reg, MachineRegisterInfo *MRI) const final;
 
+  unsigned getMachineCSELookAheadLimit() const override { return 500; }
+
   bool isSALU(uint16_t Opcode) const {
     return get(Opcode).TSFlags & SIInstrFlags::SALU;
   }
 
   bool isVALU(uint16_t Opcode) const {
     return get(Opcode).TSFlags & SIInstrFlags::VALU;
   }