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

776

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!

782

The idiom is usually !MO.getReg()

789

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

[djasper]

lib/CodeGen/MachineLICM.cpp

776

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

782

Done.

789

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

     // If it's a leaf node, it's done. Traverse upwards to pop ancestors.
     ExitScopeIfDone(Node, OpenChildren, ParentMap);
   }
+
+  SmallVector<MachineInstr *, 8> Candidates;
+  for (MachineBasicBlock::instr_iterator I = Preheader->instr_begin();
+       I != Preheader->instr_end(); ++I) {
+    if (IsLoopInvariantInst(*I) && !HasLoopPHIUse(I))
+      Candidates.push_back(I);
+  }
+
+  for (MachineInstr *I : Candidates) {
+    const MachineOperand &MO = I->getOperand(0);
+    if (!MO.isDef() || !MO.isReg() || MO.getReg() == 0)
+      continue;
+    if (!MRI->hasOneDef(MO.getReg()) || !MRI->hasOneUse(MO.getReg()))
+      continue;
+    bool CanSink = true;
+    MachineBasicBlock *B = nullptr;
+    for (MachineInstr &MI : MRI->use_instructions(MO.getReg())) {
+      if (!MI.isCopy()) {
+        MI.dump();
+        CanSink = false;
+        break;
+      }
+      if (!B) {
+        B = MI.getParent();
+      } else {
+        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) {