Experiment with keeping GEPs near calls

[djasper]

Summary

This is not meant as an actual code review to get this patch submitted but to have a basis for further discussion.

It is meant to experiment around a solution for http://llvm.org/PR22230

With this patch, LLVM, generates pretty nice code for the example from the bug report (see below). Obviously it is far from complete or correct.

.section TEXT,text,regular,pure_instructions
.macosx_version_min 10, 10
.globl Z1fPhP1A
.align 4, 0x90
Z1fPhP1A: ## @_Z1fPhP1A
.cfi_startproc

BB#0: ## %entry

pushq %rbp
Ltmp0:
.cfi_def_cfa_offset 16
Ltmp1:
.cfi_offset %rbp, -16
movq %rsp, %rbp
Ltmp2:
.cfi_def_cfa_register %rbp
pushq %r15
pushq %r14
pushq %rbx
pushq %rax
Ltmp3:
.cfi_offset %rbx, -40
Ltmp4:
.cfi_offset %r14, -32
Ltmp5:
.cfi_offset %r15, -24
movq %rsi, %r14
movq %rdi, %rbx
incq %rbx
leaq LJTI0_0(%rip), %r15
jmp LBB0_1
.align 4, 0x90
LBB0_6: ## %for.cond.backedge

1. in Loop: Header=BB0_1 Depth=1

incq %rbx
LBB0_1: ## %for.cond

1. =>This Inner Loop Header: Depth=1

movzbl (%rbx), %eax
cmpq $3, %rax
ja LBB0_6

1. BB#2: ## %for.cond
2. in Loop: Header=BB0_1 Depth=1

movslq (%r15,%rax,4), %rax
addq %r15, %rax
jmpq *%rax
LBB0_3: ## %if.then

1. in Loop: Header=BB0_1 Depth=1

movq %r14, %rdi
jmp LBB0_5
LBB0_4: ## %if.then4

1. in Loop: Header=BB0_1 Depth=1

leaq 4(%r14), %rdi
jmp LBB0_5
LBB0_7: ## %if.then8

1. in Loop: Header=BB0_1 Depth=1

leaq 8(%r14), %rdi
jmp LBB0_5
LBB0_8: ## %if.then12

1. in Loop: Header=BB0_1 Depth=1

leaq 12(%r14), %rdi
LBB0_5: ## %for.cond.backedge

1. in Loop: Header=BB0_1 Depth=1

callq __Z6assignPj
jmp LBB0_6
.cfi_endproc
.align 2, 0x90
L0_0_set_3 = LBB0_3-LJTI0_0
L0_0_set_4 = LBB0_4-LJTI0_0
L0_0_set_7 = LBB0_7-LJTI0_0
L0_0_set_8 = LBB0_8-LJTI0_0
LJTI0_0:
.long L0_0_set_3
.long L0_0_set_4
.long L0_0_set_7
.long L0_0_set_8

.subsections_via_symbols

[qcolombet]

Hi Daniel,

I do not know if you still expect feedback from this post, as we already discuss the matter on IRC.
I add a couple of comment here for the record.

Note: Please move the commit list to llvm instead of CFE :).

Thanks,
Q.

lib/CodeGen/RegisterCoalescer.cpp

847 ↗

(On Diff #18977)

This test is used to avoid rematerializing expensive operation.

849 ↗

(On Diff #18977)

This check is used to ensure that we won’t introduce correctness issues.
The following code only supports trivial rematerialization. For more general rematerialization, you have to do more interfere checks.

[hfinkel]

And for the rest of us... Am I right in gleaning from this that we need to do a better job of taking advantage of addressing modes used to compute the targets of indirect calls?

[djasper]

Current work-in-progress.

To summarize what was discussed through other channels (IRC mostly):

• We eventually want to have a lazy code motion pass which sinks GEPs into loops if they can be folded into address mode instructions (well, if sinking does not significantly increase the cost of the operation inside the loop) and dependent on register pressure.
• For the first attempts, it seems easier to re-use MachineLICM. Conceptually, this move loop-invariant code, so it isn't the "wrong" place and it already calculates much of the required information.

Still incomplete, but feedback is appreciated.

[qcolombet]

Hi Daniel,

Could you upload a patch with the full context?

Thanks,
-Quentin

[djasper]

Slightly updated patch with full context.

[djasper]

Uploaded patch with full context. We probably want to hide this behavior behind a flag, too, and do some benchmarks/experiments.

[qcolombet]

Hi Daniel,

Thanks for your patience.

First of all, yes this new logic needs to be hidden behind a flag until it is properly tuned.
In particular, we miss a profitability model, i.e., reduce exceeded register pressure, before doing the sinking.

Now, regarding the code itself, the sinking logic, modulo the missing profitability model, looks right to me, but it does not seem correct to have it in HoistOutOfLoop :).

Cheers,
-Quentin

lib/CodeGen/MachineLICM.cpp

790

A comment here would be welcome.
I suspect you are just interested in the fact that the instruction shouldn't use or define physical registers as well as memory operand (which is part of what this function does).
Without a comment, at first glance, this is confusing because instructions in the preheader should be loop invariant!

796

The idiom is usually !MO.getReg()

803

I believe this check shouldn't be needed for the general approach.

[djasper]

lib/CodeGen/MachineLICM.cpp

790

Added comment and removed HasLoopPHIUse, which I am no longer sure is necessary.

796

Done.

803

I generally agree, but we need some sort of cost model. And for now, assuming that we'd always want to sink copies seems like a reasonable first one. Added a comment to this effect.

[djasper]

• Addressed review comments
• Added test.

[qcolombet]

Hi Daniel,

LGTM with minor nitpicks.

Thanks,
-Quentin

lib/CodeGen/MachineLICM.cpp

797

-> it must *not* have...

798

The test for HasLoopPHIUse is not strictly necessary, but it acts as an optimization for the next check I believe.
Indeed, if the candidate is used within a phi for the loop, it won’t be sunken.

[djasper]

Addressed comments and submitted as r232262.

lib/CodeGen/MachineLICM.cpp

797

Fixed.

798

Re-instated.

lib/CodeGen/MachineLICM.cpp

AvoidSpeculation("avoid-speculation",
                  cl::desc("MachineLICM should avoid speculation"),
                  cl::init(true), cl::Hidden);
 
 static cl::opt<bool>
 HoistCheapInsts("hoist-cheap-insts",
                 cl::desc("MachineLICM should hoist even cheap instructions"),
                 cl::init(false), cl::Hidden);
 
+static cl::opt<bool>
+SinkInstsToAvoidSpills("sink-insts-to-avoid-spills",
+                       cl::desc("MachineLICM should sink instructions into "
+                                "loops to avoid register spills"),
+                       cl::init(false), cl::Hidden);
+
 STATISTIC(NumHoisted,
           "Number of machine instructions hoisted out of loops");
 STATISTIC(NumLowRP,
           "Number of instructions hoisted in low reg pressure situation");
 STATISTIC(NumHighLatency,
           "Number of high latency instructions hoisted");
 STATISTIC(NumCSEed,
           "Number of hoisted machine instructions CSEed");
private:
     /// blocks dominated by the specified header block, and that are in the
     /// current loop) in depth first order w.r.t the DominatorTree. This allows
     /// us to visit definitions before uses, allowing us to hoist a loop body in
     /// one pass without iteration.
     ///
     void HoistOutOfLoop(MachineDomTreeNode *LoopHeaderNode);
     void HoistRegion(MachineDomTreeNode *N, bool IsHeader);
 
+    /// SinkIntoLoop - Sink instructions into loops if profitable. This
+    /// especially tries to prevent register spills caused by register pressure
+    /// if there is little to no overhead moving instructions into loops.
+    void SinkIntoLoop();
+
     /// getRegisterClassIDAndCost - For a given MI, register, and the operand
     /// index, return the ID and cost of its representative register class by
     /// reference.
     void getRegisterClassIDAndCost(const MachineInstr *MI,
                                    unsigned Reg, unsigned OpIdx,
                                    unsigned &RCId, unsigned &RCCost) const;
 
     /// InitRegPressure - Find all virtual register references that are liveout
if (!PreRegAlloc)
       HoistRegionPostRA();
     else {
       // CSEMap is initialized for loop header when the first instruction is
       // being hoisted.
       MachineDomTreeNode *N = DT->getNode(CurLoop->getHeader());
       FirstInLoop = true;
       HoistOutOfLoop(N);
       CSEMap.clear();
+
+      if (SinkInstsToAvoidSpills)
+        SinkIntoLoop();
     }
   }
 
   return Changed;
 }
 
 /// InstructionStoresToFI - Return true if instruction stores to the
 /// specified frame.
for (MachineBasicBlock::iterator
       MII = NextMII;
     }
 
     // If it's a leaf node, it's done. Traverse upwards to pop ancestors.
     ExitScopeIfDone(Node, OpenChildren, ParentMap);
   }
 }
 
+void MachineLICM::SinkIntoLoop() {
+  MachineBasicBlock *Preheader = getCurPreheader();
+  if (!Preheader)
+    return;
+
+  SmallVector<MachineInstr *, 8> Candidates;
+  for (MachineBasicBlock::instr_iterator I = Preheader->instr_begin();
+       I != Preheader->instr_end(); ++I) {
+    // We need to ensure that we can safely move this instruction into the loop.
+    // As such, it must have side-effects, e.g. such as a call has.  
+    if (IsLoopInvariantInst(*I))
+      Candidates.push_back(I);
+  }
+
+  for (MachineInstr *I : Candidates) {
+    const MachineOperand &MO = I->getOperand(0);
+    if (!MO.isDef() || !MO.isReg() || !MO.getReg())
+      continue;
+    if (!MRI->hasOneDef(MO.getReg()))
+      continue;
+    bool CanSink = true;
+    MachineBasicBlock *B = nullptr;
+    for (MachineInstr &MI : MRI->use_instructions(MO.getReg())) {
+      // FIXME: Come up with a proper cost model that estimates whether sinking
+      // the instruction (and thus possibly executing it on every loop
+      // iteration) is more expensive than a register.
+      // For now assumes that copies are cheap and thus almost always worth it.
+      if (!MI.isCopy()) {
+        CanSink = false;
+        break;
+      }
+      if (!B) {
+        B = MI.getParent();
+        continue;
+      }
+      B = DT->findNearestCommonDominator(B, MI.getParent());
+      if (!B) {
+        CanSink = false;
+        break;
+      }
+    }
+    if (!CanSink || !B || B == Preheader)
+      continue;
+    B->splice(B->getFirstNonPHI(), Preheader, I);
+  }
+}
+
 static bool isOperandKill(const MachineOperand &MO, MachineRegisterInfo *MRI) {
   return MO.isKill() || MRI->hasOneNonDBGUse(MO.getReg());
 }
 
 /// getRegisterClassIDAndCost - For a given MI, register, and the operand
 /// index, return the ID and cost of its representative register class.
 void
 MachineLICM::getRegisterClassIDAndCost(const MachineInstr *MI,

test/CodeGen/X86/sink-cheap-instructions.ll

+; RUN: llc < %s -mtriple=x86_64-linux | FileCheck %s -check-prefix=CHECK
+; RUN: llc < %s -mtriple=x86_64-linux -sink-insts-to-avoid-spills | FileCheck %s -check-prefix=SINK
+
+; Ensure that we sink copy-like instructions into loops to avoid register
+; spills.
+
+; CHECK: Spill
+; SINK-NOT: Spill
+
+%struct.A = type { i32, i32, i32, i32, i32, i32 }
+
+define void @_Z1fPhP1A(i8* nocapture readonly %input, %struct.A* %a) {
+  %1 = getelementptr inbounds %struct.A, %struct.A* %a, i64 0, i32 0
+  %2 = getelementptr inbounds %struct.A, %struct.A* %a, i64 0, i32 1
+  %3 = getelementptr inbounds %struct.A, %struct.A* %a, i64 0, i32 2
+  %4 = getelementptr inbounds %struct.A, %struct.A* %a, i64 0, i32 3
+  %5 = getelementptr inbounds %struct.A, %struct.A* %a, i64 0, i32 4
+  %6 = getelementptr inbounds %struct.A, %struct.A* %a, i64 0, i32 5
+  br label %.backedge
+
+.backedge:
+  %.0 = phi i8* [ %input, %0 ], [ %7, %.backedge.backedge ]
+  %7 = getelementptr inbounds i8, i8* %.0, i64 1
+  %8 = load i8, i8* %7, align 1
+  switch i8 %8, label %.backedge.backedge [
+    i8 0, label %9
+    i8 10, label %10
+    i8 20, label %11
+    i8 30, label %12
+    i8 40, label %13
+    i8 50, label %14
+  ]
+
+; <label>:9
+  tail call void @_Z6assignPj(i32* %1)
+  br label %.backedge.backedge
+
+; <label>:10
+  tail call void @_Z6assignPj(i32* %2)
+  br label %.backedge.backedge
+
+.backedge.backedge:
+  br label %.backedge
+
+; <label>:11
+  tail call void @_Z6assignPj(i32* %3)
+  br label %.backedge.backedge
+
+; <label>:12
+  tail call void @_Z6assignPj(i32* %4)
+  br label %.backedge.backedge
+
+; <label>:13
+  tail call void @_Z6assignPj(i32* %5)
+  br label %.backedge.backedge
+
+; <label>:14
+  tail call void @_Z6assignPj(i32* %6)
+  br label %.backedge.backedge
+}
+
+declare void @_Z6assignPj(i32*)