[TargetLowering] Handle multi depth GEPs w/ inline asm constraints

[nickdesaulniers]

Summary

X86TargetLowering::LowerAsmOperandForConstraint had better support than
TargetLowering::LowerAsmOperandForConstraint for arbitrary depth
getelementpointers for "i", "n", and "s" extended inline assembly
constraints. Hoist its support from the derived class into the base
class.

Link: https://github.com/ClangBuiltLinux/linux/issues/469

[nickdesaulniers]

• git-clang-format HEAD~

[nickdesaulniers]

• add test case for arm32

[t.p.northover]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

3488

I think this needs to be uint64_t since the arithmetic SDNodes naturally have 2s-complement behaviour. The final value will still be interpreted in a signed manner, but intermediate calculations need to be define when wrapping.

3500

With the above suggestion, I think you'll need to make sure this extension happens properly. You probably do anyway -- the code below for combining constants can do strange things to the high bits if pointer size is less than i64.

[nickdesaulniers]

• prefer uint64_t, as per @t.p.northover

[nickdesaulniers]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

3500

Thanks for the review. I'm sorry, but I don't fully understand this comment. Can you please provide more information or clarification? Are you suggesting maybe returning early if Offset + C->getSExtValue() is greater than INT_MAX?

[t.p.northover]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

3500

All arithmetic is performed at 64-bits, and the final result is provided at that width. But if the original computation is 32-bits, I think bad things might happen. Consider:

(add (sub X:i32, 1), -1)

I think that leaves Offset as 0xfffffffe because of the odd combination of zero-extending the input and multiplying it by -1 for ISD::SUB. Effectively, some -1s are at 32-bits and some are at 64-bits.

So I think you need to do a manual extension of Offset from Op.getValueType().getSizeInBits() (not looked up the API, but you get the idea) to i64 before creating the constant.

[nickdesaulniers]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

3500

I think that leaves Offset as 0xfffffffe

Can you please walk me through the arithmetic on that (I might be mixing up my 2's compliment arithmetic, or order of operations)?

[nickdesaulniers]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

3500

Also, it looks like SelectionDAG::FoldConstantArithmetic() could help here.

[nickdesaulniers]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

3500

Ok, I agree that we should be Sign extending, not Z extending. SelectionDAG::FoldSymbolOffset seems to agree (or have the same misunderstanding). @srhines also points out I dropped the commutative nature of the pre-existing code, so I'll add that back in.

[nickdesaulniers]

• check both operands for the constant, use SExt

[nickdesaulniers]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

3500

ok, I've switched to SExt from ZExt (as per SelectionDAG::FoldSymbolOffset). @t.p.northover can you please triple check?

[nickdesaulniers]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

3494

Maybe I should initialize C to nullptr and then keep the C ? SDLoc(C) : SDLoc()? I'm not verify familiar with SDLoc, but it seems that I'm potentially messing up debug info? Should the previous code be constructing empty SDLocs (as opposed to SDLoc(GA)?

[t.p.northover]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

3500

Yep, I think that bit's OK now.

3509

Subtraction is not commutative, so you need to be more careful here.

[nickdesaulniers]

• subtraction is not commutative

[nickdesaulniers]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

3509

Good catch, thank you. How's that look? Any thoughts on my SDLoc comment, above?

[t.p.northover]

I think it looks reasonable now. Thanks for updating it!

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

if (Op.getOpcode() == ISD::BasicBlock ||
         Op.getOpcode() == ISD::TargetBlockAddress) {
       Ops.push_back(Op);
       return;
     }
     LLVM_FALLTHROUGH;
   case 'i':    // Simple Integer or Relocatable Constant
   case 'n':    // Simple Integer
   case 's': {  // Relocatable Constant
-    // These operands are interested in values of the form (GV+C), where C may
-    // be folded in as an offset of GV, or it may be explicitly added.  Also, it
-    // is possible and fine if either GV or C are missing.
-    ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op);
-    GlobalAddressSDNode *GA = dyn_cast<GlobalAddressSDNode>(Op);
-
-    // If we have "(add GV, C)", pull out GV/C
-    if (Op.getOpcode() == ISD::ADD) {
-      C = dyn_cast<ConstantSDNode>(Op.getOperand(1));
-      GA = dyn_cast<GlobalAddressSDNode>(Op.getOperand(0));
-      if (!C || !GA) {
-        C = dyn_cast<ConstantSDNode>(Op.getOperand(0));
-        GA = dyn_cast<GlobalAddressSDNode>(Op.getOperand(1));
-      }
-      if (!C || !GA) {
-        C = nullptr;
-        GA = nullptr;
-      }
-    }
 
-    // If we find a valid operand, map to the TargetXXX version so that the
-    // value itself doesn't get selected.
-    if (GA) {   // Either &GV   or   &GV+C
-      if (ConstraintLetter != 'n') {
-        int64_t Offs = GA->getOffset();
-        if (C) Offs += C->getZExtValue();
-        Ops.push_back(DAG.getTargetGlobalAddress(GA->getGlobal(),
-                                                 C ? SDLoc(C) : SDLoc(),
-                                                 Op.getValueType(), Offs));
-      }
+    GlobalAddressSDNode *GA;
+    ConstantSDNode *C;
+    uint64_t Offset = 0;
+
+    // Match (GA) or (C) or (GA+C) or (GA-C) or ((GA+C)+C) or (((GA+C)+C)+C),
+    // etc., since getelementpointer is variadic. We can't use
+    // SelectionDAG::FoldSymbolOffset because it expects the GA to be accessible
+    // while in this case the GA may be furthest from the root node which is
+    // likely an ISD::ADD.
+    while (1) {
+      if ((GA = dyn_cast<GlobalAddressSDNode>(Op)) && ConstraintLetter != 'n') {
+        Ops.push_back(DAG.getTargetGlobalAddress(GA->getGlobal(), SDLoc(Op),
+                                                 GA->getValueType(0),
+                                                 Offset + GA->getOffset()));
         return;
-    }
-    if (C) {   // just C, no GV.
-      // Simple constants are not allowed for 's'.
-      if (ConstraintLetter != 's') {
-        // gcc prints these as sign extended.  Sign extend value to 64 bits
-        // now; without this it would get ZExt'd later in
-        // ScheduleDAGSDNodes::EmitNode, which is very generic.
-        Ops.push_back(DAG.getTargetConstant(C->getSExtValue(),
+      } else if ((C = dyn_cast<ConstantSDNode>(Op)) &&
+                 ConstraintLetter != 's') {
+        Ops.push_back(DAG.getTargetConstant(Offset + C->getSExtValue(),
                                             SDLoc(C), MVT::i64));
+        return;
+      } else {
+        const unsigned OpCode = Op.getOpcode();
+        if (OpCode == ISD::ADD || OpCode == ISD::SUB) {
+          if ((C = dyn_cast<ConstantSDNode>(Op.getOperand(0))))
+            Op = Op.getOperand(1);
+          // Subtraction is not commutative.
+          else if (OpCode == ISD::ADD &&
+                   (C = dyn_cast<ConstantSDNode>(Op.getOperand(1))))
+            Op = Op.getOperand(0);
+          else
+            return;
+          Offset += (OpCode == ISD::ADD ? 1 : -1) * C->getSExtValue();
+          continue;
+        }
       }
       return;
     }
     break;
   }
   }
 }
 

llvm/lib/Target/X86/X86ISelLowering.cpp

     // In any sort of PIC mode addresses need to be computed at runtime by
     // adding in a register or some sort of table lookup.  These can't
     // be used as immediates.
     if (Subtarget.isPICStyleGOT() || Subtarget.isPICStyleStubPIC())
       return;
 
     // If we are in non-pic codegen mode, we allow the address of a global (with
     // an optional displacement) to be used with 'i'.
-    GlobalAddressSDNode *GA = nullptr;
-    int64_t Offset = 0;
-
-    // Match either (GA), (GA+C), (GA+C1+C2), etc.
-    while (1) {
-      if ((GA = dyn_cast<GlobalAddressSDNode>(Op))) {
-        Offset += GA->getOffset();
-        break;
-      } else if (Op.getOpcode() == ISD::ADD) {
-        if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
-          Offset += C->getZExtValue();
-          Op = Op.getOperand(0);
-          continue;
-        }
-      } else if (Op.getOpcode() == ISD::SUB) {
-        if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
-          Offset += -C->getZExtValue();
-          Op = Op.getOperand(0);
-          continue;
-        }
-      }
-
-      // Otherwise, this isn't something we can handle, reject it.
-      return;
-    }
-
-    const GlobalValue *GV = GA->getGlobal();
-    // If we require an extra load to get this address, as in PIC mode, we
-    // can't accept it.
-    if (isGlobalStubReference(Subtarget.classifyGlobalReference(GV)))
-      return;
-
-    Result = DAG.getTargetGlobalAddress(GV, SDLoc(Op),
-                                        GA->getValueType(0), Offset);
+    if (auto *GA = dyn_cast<GlobalAddressSDNode>(Op))
+      // If we require an extra load to get this address, as in PIC mode, we
+      // can't accept it.
+      if (isGlobalStubReference(
+              Subtarget.classifyGlobalReference(GA->getGlobal())))
+        return;
     break;
   }
   }
 
   if (Result.getNode()) {
     Ops.push_back(Result);
     return;
   }

llvm/test/CodeGen/AArch64/inline-asm-multilevel-gep.ll

+; RUN: llc < %s -mtriple aarch64-gnu-linux | FileCheck %s
+
+; @foo is a 2d array of i32s, ex.
+; i32 foo [2][2]
+@foo = internal global [2 x [2 x i32]] zeroinitializer, align 4
+
+define void @bar() {
+; access foo[1][1]
+; CHECK: // foo+12
+  tail call void asm sideeffect "// ${0:c}", "i"(i32* getelementptr inbounds ([2 x [2 x i32]], [2 x [2 x i32]]* @foo, i64 0, i64 1, i64 1))
+  ret void
+}

llvm/test/CodeGen/ARM/inline-asm-multilevel-gep.ll

+; RUN: llc < %s -mtriple armv7-linux-gnueabi | FileCheck %s
+
+; @foo is a 2d array of i32s, ex.
+; i32 foo [2][2]
+@foo = internal global [2 x [2 x i32]] zeroinitializer, align 4
+
+define void @bar() {
+; access foo[1][1]
+; CHECK: @ foo+12
+  tail call void asm sideeffect "@ ${0:c}", "i"(i32* getelementptr inbounds ([2 x [2 x i32]], [2 x [2 x i32]]* @foo, i64 0, i64 1, i64 1))
+  ret void
+}

llvm/test/CodeGen/PowerPC/inline-asm-multilevel-gep.ll

+; RUN: llc < %s -mtriple ppc32-- | FileCheck %s
+
+; @foo is a 2d array of i32s, ex.
+; i32 foo [2][2]
+@foo = internal global [2 x [2 x i32]] zeroinitializer, align 4
+
+define void @bar() {
+; access foo[1][1]
+; CHECK: # foo+12
+  tail call void asm sideeffect "# ${0:c}", "i"(i32* getelementptr inbounds ([2 x [2 x i32]], [2 x [2 x i32]]* @foo, i64 0, i64 1, i64 1))
+  ret void
+}

llvm/test/CodeGen/X86/inline-asm-multilevel-gep.ll

+; RUN: llc < %s -mtriple x86_64-gnu-linux | FileCheck %s
+
+; @foo is a 2d array of i32s, ex.
+; i32 foo [2][2]
+@foo = internal global [2 x [2 x i32]] zeroinitializer, align 4
+
+define void @bar() {
+; access foo[1][1]
+; CHECK: # foo+12
+  tail call void asm sideeffect "# ${0:c}", "i"(i32* getelementptr inbounds ([2 x [2 x i32]], [2 x [2 x i32]]* @foo, i64 0, i64 1, i64 1))
+  ret void
+}