Allow rematerialization of ARM Thumb literal pool loads

[philipginsbach]

Summary

Constants are crucial for code size in the ARM Thumb-1 instruction set.
The 16 bit instruction size often does not offer enough space for immediate arguments.
This means that additional instructions are frequently used to load constants into registers.
Since constants are hoisted, this can lead to significant register spillage if they are used multiple times in a single function.
This can be avoided by rematerialization, i.e. recomputing a constant instead of reloading it from the stack.
This patch fixes the rematerialization of literal pool loads in the ARM Thumb instruction set.

[samparker]

Hi Philip,

Could you re-upload the patch with some added context please? Something like -U100 would be great.

cheers,
sam

[samparker]

Hi Philip,

Are these tests standalone for just this patch, or in conjunction with D33935? If it's difficult to test separately (I'm assuming so), I think you should combine these two patches so they can be committed and tested together.

cheers,
sam

[philipginsbach]

Hi Sam,

The patches are related in their purpose but completely separate in the functionality that they actually touch.
Both patches therefore now have a different test, there is no need to merge them.

Best,
Philip

[samparker]

Ok, great. I've just got some inline queries.

test/CodeGen/Thumb/litpoolremat.ll

25

Maybe we also check that there aren't any stack spills and restores?

test/CodeGen/Thumb/select.ll

77

Can you explain why this test has changed please?

[philipginsbach]

test/CodeGen/Thumb/litpoolremat.ll

25

That could be done as well, but I think this more specifically checks the exact functionality of the patch, i.e. to avoid spilling of literal pools loads (and only of them).
For example, if a fourth line of get_value() was added in the middle, the function would still spill after the patch, but at least it would spill once less.

test/CodeGen/Thumb/select.ll

77

Essentially there are two things going on here:

1. The select instruction turns into two conditional branches due to the double being split into two 4-byte chunks. This is unfortunate but not in the scope of this patch.
2. The original code writes -1.0 into the output registers and then conditionally overwrites it with the value of %b. This results in two blt branches (with the same condition %a < 1.234). After the patch, the second chunk is reversed, i.e. it is initialized with part of %b and conditionally overwritten with part of constant -1.0. This is because the second chunk of constant -1.0 is put into a literal pool and loading stuff from there is more expensive than just moving around registers. Before the patch, the compiler isn't aware that it is allowed to make the load from literal pools conditional as it assumes that it is effectful. For the first chunk of -1.0 this is irrelevant, as it is 0x00000000 and thus can be loaded as an immediate.

[samparker]

test/CodeGen/Thumb/litpoolremat.ll

25

Ok, I asked a bad question, I mean why aren't we testing that the immediate is not spilled once its loaded? It would also be good to check what data is at LCPIO_0.

[philipginsbach]

test/CodeGen/Thumb/litpoolremat.ll

25

You are definitely right that it would be nice to verify that LCPIO_0 is indeed where the constant 1764 is stored.
I am not sure how to do that in the FileCheck syntax though, I will look that up.
As for explicitly checking whether it is spilled instead of checking whether it is rematerialized (which is what the test checks right now) I think this does the job and since I emphasized the rematerialization in the patch title it is the preferred way.

[philipginsbach]

test/CodeGen/Thumb/litpoolremat.ll

25

I added the check for LCPIO_0.
As for explicitly checking whether it is spilled instead of checking whether it is rematerialized (which is what the test checks right now) I think this does the job and since I emphasized the rematerialization in the patch title it is the preferred way.

[samparker]

test/CodeGen/Thumb/litpoolremat.ll

25

I didn't mean you should do the spill check instead of what you have done, I just meant as a supplement. It would be nice to have the extra explicit check that there's no 'str r0, [sp]' after the initial load.

for the literal pool check, you could perform the check after the code checks with something like:
CHECK-LABEL: LCPI0_0
CHECK-NEXT: . long 1764

[philipginsbach]

test/CodeGen/Thumb/litpoolremat.ll

25

Agreed, I added both.

[samparker]

Great, thanks, LGTM!

[philipginsbach]

Thanks a lot Sam!

lib/Target/ARM/ARMISelDAGToDAG.cpp

     // If we can't materialize the constant we need to use a literal pool
     if (ConstantMaterializationCost(Val) > 2) {
       SDValue CPIdx = CurDAG->getTargetConstantPool(
           ConstantInt::get(Type::getInt32Ty(*CurDAG->getContext()), Val),
           TLI->getPointerTy(CurDAG->getDataLayout()));
 
       SDNode *ResNode;
       if (Subtarget->isThumb()) {
-        SDValue Pred = getAL(CurDAG, dl);
-        SDValue PredReg = CurDAG->getRegister(0, MVT::i32);
-        SDValue Ops[] = { CPIdx, Pred, PredReg, CurDAG->getEntryNode() };
+        SDValue Ops[] = {
+          CPIdx,
+          getAL(CurDAG, dl),
+          CurDAG->getRegister(0, MVT::i32),
+          CurDAG->getEntryNode()
+        };
         ResNode = CurDAG->getMachineNode(ARM::tLDRpci, dl, MVT::i32, MVT::Other,
                                          Ops);
       } else {
         SDValue Ops[] = {
           CPIdx,
           CurDAG->getTargetConstant(0, dl, MVT::i32),
           getAL(CurDAG, dl),
           CurDAG->getRegister(0, MVT::i32),
           CurDAG->getEntryNode()
         };
         ResNode = CurDAG->getMachineNode(ARM::LDRcp, dl, MVT::i32, MVT::Other,
                                          Ops);
       }
+      // Annotate the Node with memory operand information so that MachineInstr
+      // queries work properly. This e.g. gives the register allocation the
+      // required information for rematerialization.
+      MachineFunction& MF = CurDAG->getMachineFunction();
+      MachineSDNode::mmo_iterator MemOp = MF.allocateMemRefsArray(1);
+      MemOp[0] = MF.getMachineMemOperand(
+          MachinePointerInfo::getConstantPool(MF),
+          MachineMemOperand::MOLoad, 4, 4);
+
+      cast<MachineSDNode>(ResNode)->setMemRefs(MemOp, MemOp+1);
+        
       ReplaceNode(N, ResNode);
       return;
     }
 
     // Other cases are autogenerated.
     break;
   }
   case ISD::FrameIndex: {

test/CodeGen/Thumb/litpoolremat.ll

+; RUN: llc < %s -mtriple=thumb-apple-darwin | FileCheck %s
+
+declare void @consume_value(i32) #1
+
+declare i32 @get_value(...) #1
+
+declare void @consume_three_values(i32, i32, i32) #1
+
+; Function Attrs: nounwind uwtable
+define void @should_not_spill() #0 {
+  tail call void @consume_value(i32 1764) #2
+  %1 = tail call i32 (...) @get_value() #2
+  %2 = tail call i32 (...) @get_value() #2
+  %3 = tail call i32 (...) @get_value() #2
+  tail call void @consume_value(i32 %1) #2
+  tail call void @consume_value(i32 %2) #2
+  tail call void @consume_value(i32 %3) #2
+  tail call void @consume_value(i32 1764) #2
+  tail call void @consume_three_values(i32 %1, i32 %2, i32 %3) #2
+  ret void
+}
+
+; CHECK: ldr r0, LCPI0_0
+; CHECK-NOT: str r0
+; CHECK: bl
+; CHECK: ldr r0, LCPI0_0
+; CHECK-LABEL: LCPI0_0:
+; CHECK-NEXT: .long 1764

test/CodeGen/Thumb/select.ll

 
 define double @f7(double %a, double %b) {
     %tmp = fcmp olt double %a, 1.234e+00
     %tmp1 = select i1 %tmp, double -1.000e+00, double %b
     ret double %tmp1
 }
 ; CHECK-LABEL: f7:
 ; CHECK: blt
-; CHECK: blt
+; CHECK: {{blt|bge}}
 ; CHECK: __ltdf2
 ; CHECK-EABI-LABEL: f7:
 ; CHECK-EABI: __aeabi_dcmplt
 ; CHECK-EABI: bne
-; CHECK-EABI: bne
+; CHECK-EABI: {{bne|beq}}