[AVR] Fix incorrect stack parameter push order

[Jim]

Summary

Transform all store nodes into one single node to ensure the order of all store nodes can't be changed.
So that the push instruction sequence generated would be correct.

[hfinkel]

Transform all store nodes into one single node to ensure the order of all store nodes can't be changed. So that the push instruction sequence generated would be correct.

The code here is probably correct - the various stores onto the stack seem to be independent - but the description here seems off. By grouping all of the stores into one TokenFactor, you're providing more ordering freedom, not less.

lib/Target/AVR/AVRISelLowering.cpp

1263

IIRC, the order of the operands of a TokenFactor don't carry any significance.

[Jim]

@hfinkel
Hi, I am not really sure the means of TokenFactor. I refer the implement of other target.
From document, TokenFactor is used to represent the fact that the operand operators are independent of each other.
I am not sure why other target transform all stores into one single node by using TokenFactor.
Most of target, it uses sp+offset to store arguments into stack. So the order of store instruction doesn't matter.
In AVR, it uses push instruction to store arguments. Therefore. the order of store(push) instruction can't be changed.
Could you give me some suggestion? Thanks.

[efriedma]

In AVR, it uses push instruction to store arguments. Therefore. the order of store(push) instruction can't be changed.

During isel, the stores are modeled using regular store instructions. And it should be possible (although maybe not efficient) to lower those stores into regular store instructions, which don't modify the stack pointer.

It looks like AVRFrameLowering::eliminateCallFramePseudoInstr has a bug: it assumes that the store instructions that are used to store arguments exist in some specific order. The target-independent backend code does not guarantee that; the stores can be rearranged during or after isel. If the stores need to be in a specific order for the store->push optimization, the AVR backend needs to rearrange them into the correct order explicitly.

x86 has a similar "push" instruction, and a specialized transform pass dedicated to optimizing store instructions to push instructions. See lib/Target/X86/X86CallFrameOptimization.cpp .

[dylanmckay]

This is superseded by D68524, which rewrites most of the calling convention implementation. Sorry for taking so long to get to this @Jim!

[Jim]

Ok. Thanks

lib/Target/AVR/AVRISelLowering.cpp

analyzeArguments(&CLI, F, &DAG.getDataLayout(), &Outs, 0, CallConv, ArgLocs, CCInfo,
                    true, isVarArg);
 
   // Get a count of how many bytes are to be pushed on the stack.
   unsigned NumBytes = CCInfo.getNextStackOffset();
 
   Chain = DAG.getCALLSEQ_START(Chain, NumBytes, 0, DL);
 
   SmallVector<std::pair<unsigned, SDValue>, 8> RegsToPass;
+  SmallVector<SDValue, 8> MemOpChains;
 
   // First, walk the register assignments, inserting copies.
   unsigned AI, AE;
   bool HasStackArgs = false;
   for (AI = 0, AE = ArgLocs.size(); AI != AE; ++AI) {
     CCValAssign &VA = ArgLocs[AI];
     EVT RegVT = VA.getLocVT();
     SDValue Arg = OutVals[AI];
for (AE = AI, AI = ArgLocs.size(); AI != AE; --AI) {
       assert(VA.isMemLoc());
 
       // SP points to one stack slot further so add one to adjust it.
       SDValue PtrOff = DAG.getNode(
           ISD::ADD, DL, getPointerTy(DAG.getDataLayout()),
           DAG.getRegister(AVR::SP, getPointerTy(DAG.getDataLayout())),
           DAG.getIntPtrConstant(VA.getLocMemOffset() + 1, DL));
 
-      Chain =
-          DAG.getStore(Chain, DL, Arg, PtrOff,
-                       MachinePointerInfo::getStack(MF, VA.getLocMemOffset()),
-                       0);
+      MemOpChains.push_back(DAG.getStore(
+          Chain, DL, Arg, PtrOff,
+          MachinePointerInfo::getStack(MF, VA.getLocMemOffset()), 0));
     }
   }
 
+  // Transform all store nodes into one single node because all store
+  // nodes are independent of each other.
+  if (!MemOpChains.empty()) {
+    // Reverse the order in MemOpChains to match the push order.
+    std::reverse(MemOpChains.begin(), MemOpChains.end());
+    Chain = DAG.getNode(ISD::TokenFactor, DL, MVT::Other, MemOpChains);
+  }
+
   // Build a sequence of copy-to-reg nodes chained together with token chain and
   // flag operands which copy the outgoing args into registers.  The InFlag in
   // necessary since all emited instructions must be stuck together.
   SDValue InFlag;
   for (auto Reg : RegsToPass) {
     Chain = DAG.getCopyToReg(Chain, DL, Reg.first, Reg.second, InFlag);
     InFlag = Chain.getValue(1);
   }

test/CodeGen/AVR/call.ll

 ; CHECK: ldi r23, 2
 ; CHECK: call foo16_1
     %result1 = call i16 @foo16_1(i16 513, i16 514)
     ret i16 %result1
 }
 
 define i16 @calli16_stack() {
 ; CHECK-LABEL: calli16_stack:
-; CHECK: ldi [[REG1:r[0-9]+]], 9
+; CHECK: ldi [[REG1:r[0-9]+]], 10
 ; CHECK: ldi [[REG2:r[0-9]+]], 2 
 ; CHECK: push [[REG2]]
 ; CHECK: push [[REG1]]
-; CHECK: ldi [[REG1:r[0-9]+]], 10
+; CHECK: ldi [[REG1:r[0-9]+]], 9
 ; CHECK: ldi [[REG2:r[0-9]+]], 2
 ; CHECK: push [[REG2]]
 ; CHECK: push [[REG1]]
 ; CHECK: call foo16_2
     %result1 = call i16 @foo16_2(i16 512, i16 513, i16 514, i16 515, i16 516, i16 517, i16 518, i16 519, i16 520, i16 521, i16 522)
     ret i16 %result1
 }
 

 ; CHECK: ldi r21, 2
 ; CHECK: call foo32_1
     %result1 = call i32 @foo32_1(i32 34554432, i32 35554432)
     ret i32 %result1
 }
 
 define i32 @calli32_stack() {
 ; CHECK-LABEL: calli32_stack:
-; CHECK: ldi [[REG1:r[0-9]+]], 64
-; CHECK: ldi [[REG2:r[0-9]+]], 66
-; CHECK: push [[REG2]]
-; CHECK: push [[REG1]]
 ; CHECK: ldi [[REG1:r[0-9]+]], 15
 ; CHECK: ldi [[REG2:r[0-9]+]], 2
 ; CHECK: push [[REG2]]
 ; CHECK: push [[REG1]]
+; CHECK: ldi [[REG1:r[0-9]+]], 64
+; CHECK: ldi [[REG2:r[0-9]+]], 66
+; CHECK: push [[REG2]]
+; CHECK: push [[REG1]]
 ; CHECK: call foo32_2
     %result1 = call i32 @foo32_2(i32 1, i32 2, i32 3, i32 4, i32 34554432)
     ret i32 %result1
 }
 
 define i64 @calli64_reg() {
 ; CHECK-LABEL: calli64_reg:
 ; CHECK: ldi r18, 255
 ; CHECK: ldi r19, 255
 ; CHECK: ldi r20, 155
 ; CHECK: ldi r21, 88
 ; CHECK: ldi r22, 76
 ; CHECK: ldi r23, 73
 ; CHECK: ldi r24, 31
 ; CHECK: ldi r25, 242
 ; CHECK: call foo64_1
     %result1 = call i64 @foo64_1(i64 17446744073709551615)
     ret i64 %result1
 }
 
 define i64 @calli64_stack() {
 ; CHECK-LABEL: calli64_stack:
 
-; CHECK: ldi [[REG1:r[0-9]+]], 76
-; CHECK: ldi [[REG2:r[0-9]+]], 73
-; CHECK: push [[REG2]]
-; CHECK: push [[REG1]]
 ; CHECK: ldi [[REG1:r[0-9]+]], 31
 ; CHECK: ldi [[REG2:r[0-9]+]], 242
 ; CHECK: push [[REG2]]
 ; CHECK: push [[REG1]]
+; CHECK: ldi [[REG1:r[0-9]+]], 76
+; CHECK: ldi [[REG2:r[0-9]+]], 73
+; CHECK: push [[REG2]]
+; CHECK: push [[REG1]]
 ; CHECK: ldi [[REG1:r[0-9]+]], 155
 ; CHECK: ldi [[REG2:r[0-9]+]], 88
 ; CHECK: push [[REG2]]
 ; CHECK: push [[REG1]]
 ; CHECK: ldi [[REG1:r[0-9]+]], 255
 ; CHECK: ldi [[REG2:r[0-9]+]], 255
 ; CHECK: push [[REG2]]
 ; CHECK: push [[REG1]]

test/CodeGen/AVR/varargs.ll

; CHECK: ldd r25, [[REG]]+{{[0-9]+}}
   %1 = va_arg i8** %ap, i16
   call void @llvm.va_end(i8* %ap1)
   ret i16 %1
 }
 
 declare void @var1223(i16, ...)
 define void @varargcall() {
 ; CHECK-LABEL: varargcall:
-; CHECK: ldi [[REG1:r[0-9]+]], 189
-; CHECK: ldi [[REG2:r[0-9]+]], 205
-; CHECK: push [[REG2]]
-; CHECK: push [[REG1]]
 ; CHECK: ldi [[REG1:r[0-9]+]], 191
 ; CHECK: ldi [[REG2:r[0-9]+]], 223
 ; CHECK: push [[REG2]]
 ; CHECK: push [[REG1]]
+; CHECK: ldi [[REG1:r[0-9]+]], 189
+; CHECK: ldi [[REG2:r[0-9]+]], 205
+; CHECK: push [[REG2]]
+; CHECK: push [[REG1]]
 ; CHECK: ldi [[REG1:r[0-9]+]], 205
 ; CHECK: ldi [[REG2:r[0-9]+]], 171
 ; CHECK: push [[REG2]]
 ; CHECK: push [[REG1]]
 ; CHECK: call
 ; CHECK: adiw r30, 6
   tail call void (i16, ...) @var1223(i16 -21555, i16 -12867, i16 -8257)
   ret void
 }