Handle stack spills in ARM integrated assembler.

src/IceAssemblerARM32.cpp

 //===- subzero/src/IceAssemblerARM32.cpp - Assembler for ARM32 --*- C++ -*-===//
 //
 // Copyright (c) 2013, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 //
 // Modified by the Subzero authors.
 //
 //===----------------------------------------------------------------------===//
 //
@@ skipping 21 matching lines @@
 static constexpr uint32_t B2 = 1 << 2;
 static constexpr uint32_t B3 = 1 << 3;
 static constexpr uint32_t B4 = 1 << 4;
 static constexpr uint32_t B5 = 1 << 5;
 static constexpr uint32_t B6 = 1 << 6;
 static constexpr uint32_t B21 = 1 << 21;
 static constexpr uint32_t B24 = 1 << 24;
 
 // Constants used for the decoding or encoding of the individual fields of
 // instructions. Based on ARM section A5.1.
+static constexpr uint32_t L = 1 << 20; // load (or store)
+static constexpr uint32_t W = 1 << 21; // writeback base register (or leave
+                                       // unchanged)
+static constexpr uint32_t B = 1 << 22; // unsigned byte (or word)
+static constexpr uint32_t U = 1 << 23; // positive (or negative) offset/index
+static constexpr uint32_t P = 1 << 24; // offset/pre-indexed addressing (or
+                                       // post-indexed addressing)
+
 static constexpr uint32_t kConditionShift = 28;
 static constexpr uint32_t kOpcodeShift = 21;
 static constexpr uint32_t kRdShift = 12;
 static constexpr uint32_t kRmShift = 0;
 static constexpr uint32_t kRnShift = 16;
 static constexpr uint32_t kSShift = 20;
 static constexpr uint32_t kTypeShift = 25;
 
 // Immediate instruction fields encoding.
 static constexpr uint32_t kImmed8Bits = 8;
 static constexpr uint32_t kImmed8Shift = 0;
 static constexpr uint32_t kRotateBits = 4;
 static constexpr uint32_t kRotateShift = 8;
 
+static constexpr uint32_t kImmed12Bits = 12;
+static constexpr uint32_t kImm12Shift = 0;
+
+template <typename T> static inline bool isUint(int N, T Value) {

[Jim Stichnoth, 2015/10/15 20:41:29]

Can you just use the (inappropriately named) IsUint() and IsAbsoluteUint() in
IceUtils.h?

[Karl, 2015/10/15 22:03:33]

Done.

+  assert((0 < N) && (static_cast<unsigned>(N) < (CHAR_BIT * sizeof(Value))));
+  T Limit = static_cast<T>(1) << N;
+  return (0 <= Value) && (Value < Limit);
+}
+
+template <typename T> inline bool isAbsoluteUint(int N, T Value) {
+  assert(N < 30 && static_cast<unsigned>(N) < (CHAR_BIT * sizeof(T)));
+  if (Value < 0)
+    Value = -Value;
+  return isUint(N, Value);
+}
+
 inline uint32_t encodeBool(bool b) { return b ? 1 : 0; }
 
 inline uint32_t encodeGPRRegister(RegARM32::GPRRegister Rn) {
   return static_cast<uint32_t>(Rn);
 }
 
 inline bool isGPRRegisterDefined(RegARM32::GPRRegister R) {
   return R != RegARM32::Encoded_Not_GPR;
 }
 
 inline bool isGPRRegisterDefined(uint32_t R) {
   return R != encodeGPRRegister(RegARM32::Encoded_Not_GPR);
 }
 
 inline bool isConditionDefined(CondARM32::Cond Cond) {
   return Cond != CondARM32::kNone;
 }
 
 inline uint32_t encodeCondition(CondARM32::Cond Cond) {
   return static_cast<uint32_t>(Cond);
 }
 
-// The way an operand was decoded in function decode below.
+// Returns the bits int the corresponding masked value

[Jim Stichnoth, 2015/10/15 20:41:29]

"int" ?  Also, end sentence with period.

[Karl, 2015/10/15 22:03:33]

Done.

+inline uint32_t mask(uint32_t Value, uint32_t Shift, uint32_t Bits) {
+  return (Value >> Shift) & ((1 << Bits) - 1);
+}
+
+// Extract out a Bit in Value.
+inline bool isBitSet(uint32_t Bit, uint32_t Value) {
+  return (Value & Bit) == Bit;
+}
+
+// Returns the GPR register at given Shift in Value.
+inline RegARM32::GPRRegister getGPRReg(uint32_t Shift, uint32_t Value) {
+  return static_cast<RegARM32::GPRRegister>((Value >> Shift) & 0xF);
+}
+
+// The way an operand was decoded in functions decodeOperand and decodeAddress
+// below.
 enum DecodedResult {
-  CantDecode = 0, // I.e. will fail in test.
+  // Unable to decode, value left undefined.
+  CantDecode = 0,
+  // Value is register found.
   DecodedAsRegister,
-  DecodedAsRotatedImm8
+  // Value=rrrriiiiiiii where rrrr is the rotation, and iiiiiiii is the imm8
+  // value.
+  DecodedAsRotatedImm8,
+  // i.e. 0000000pu0w0nnnn0000iiiiiiiiiiii where nnnn is the base register Rn,
+  // p=1 if pre-indexed addressing, u=1 if offset positive, w=1 if writeback to
+  // Rn should be used, and iiiiiiiiiiii is the offset.
+  DecodedAsImmRegOffset
 };
 
-DecodedResult decode(const Operand *Opnd, uint32_t &Value) {
+DecodedResult decodeOperand(const Operand *Opnd, uint32_t &Value) {
   if (const auto *Var = llvm::dyn_cast<Variable>(Opnd)) {
     if (Var->hasReg()) {
       Value = Var->getRegNum();
       return DecodedAsRegister;
     }
   } else if (const auto *FlexImm = llvm::dyn_cast<OperandARM32FlexImm>(Opnd)) {
     uint32_t Immed8 = FlexImm->getImm();
     uint32_t Rotate = FlexImm->getRotateAmt();
     assert((Rotate < (1 << kRotateBits)) && (Immed8 < (1 << kImmed8Bits)));
     Value = (Rotate << kRotateShift) | (Immed8 << kImmed8Shift);
     return DecodedAsRotatedImm8;
   }
   return CantDecode;
 }
 
+uint32_t decodeImmRegOffset(RegARM32::GPRRegister Reg, int32_t Offset,
+                            OperandARM32Mem::AddrMode Mode) {
+  uint32_t Value = Mode | (encodeGPRRegister(Reg) << kRnShift);
+  if (Offset < 0) {
+    Value = (Value ^ U) | -Offset; // Flip U to adjust sign.
+  } else {
+    Value |= Offset;
+  }
+  return Value;
+}
+
+// Decodes memory address Opnd, and encodes that information into Value,
+// based on how ARM represents the address. Returns how the value was encoded.
+DecodedResult decodeAddress(const Operand *Opnd, uint32_t &Value) {
+  // Note: Loop is used so that we can short ciruit using break;

[Jim Stichnoth, 2015/10/15 20:41:29]

Would it make sense here to just "return CantDecode" instead of "break"?

[Karl, 2015/10/15 22:03:33]

Good idea. Removing loop as well.

+  do {
+    if (const auto *Var = llvm::dyn_cast<Variable>(Opnd)) {
+      // Should be a stack variable, with an offset.
+      if (Var->hasReg())
+        break;
+      int32_t Offset = Var->getStackOffset();
+      if (!isAbsoluteUint(12, Offset))
+        break;
+      Value = decodeImmRegOffset(RegARM32::Encoded_Reg_sp, Offset,
+                                 OperandARM32Mem::Offset);
+      return DecodedAsImmRegOffset;
+    }
+  } while (0);
+  return CantDecode;
+}
+
 } // end of anonymous namespace
 
 namespace Ice {
 
 Label *ARM32::AssemblerARM32::getOrCreateLabel(SizeT Number,
                                                LabelVector &Labels) {
   Label *L = nullptr;
   if (Number == Labels.size()) {
     L = new (this->allocate<Label>()) Label();
     Labels.push_back(L);
@@ skipping 22 matching lines @@
   // TODO(kschimpf) Decide if we have near jumps.
   label->bindTo(bound);
 }
 
 void ARM32::AssemblerARM32::emitType01(CondARM32::Cond Cond, uint32_t Type,
                                        uint32_t Opcode, bool SetCc, uint32_t Rn,
                                        uint32_t Rd, uint32_t Imm12) {
   assert(isGPRRegisterDefined(Rd));
   assert(Cond != CondARM32::kNone);
   AssemblerBuffer::EnsureCapacity ensured(&Buffer);
-  uint32_t Encoding = encodeCondition(Cond) << kConditionShift |
+  uint32_t Encoding = (encodeCondition(Cond) << kConditionShift) |
                       (Type << kTypeShift) | (Opcode << kOpcodeShift) |
                       (encodeBool(SetCc) << kSShift) | (Rn << kRnShift) |
                       (Rd << kRdShift) | Imm12;
   emitInst(Encoding);
 }
 
+void ARM32::AssemblerARM32::emitMemOp(CondARM32::Cond Cond, uint32_t InstType,
+                                      bool IsLoad, bool IsByte, uint32_t Rt,
+                                      uint32_t Address) {
+  assert(isGPRRegisterDefined(Rt));
+  assert(Cond != CondARM32::kNone);
+  AssemblerBuffer::EnsureCapacity ensured(&Buffer);
+  uint32_t Encoding = (encodeCondition(Cond) << kConditionShift) |
+                      (InstType << kTypeShift) | (IsLoad ? L : 0) |
+                      (IsByte ? B : 0) | (Rt << kRdShift) | Address;
+  emitInst(Encoding);
+}
+
 void ARM32::AssemblerARM32::add(const Operand *OpRd, const Operand *OpRn,
                                 const Operand *OpSrc1, bool SetFlags,
                                 CondARM32::Cond Cond) {
   // Note: Loop is used so that we can short circuit using break;
   do {
     uint32_t Rd;
-    if (decode(OpRd, Rd) != DecodedAsRegister)
+    if (decodeOperand(OpRd, Rd) != DecodedAsRegister)
       break;
     uint32_t Rn;
-    if (decode(OpRn, Rn) != DecodedAsRegister)
+    if (decodeOperand(OpRn, Rn) != DecodedAsRegister)
       break;
     uint32_t Src1Value;
     // TODO(kschimpf) Other possible decodings of add.
-    if (decode(OpSrc1, Src1Value) == DecodedAsRotatedImm8) {
+    if (decodeOperand(OpSrc1, Src1Value) == DecodedAsRotatedImm8) {
       // ADD (Immediate): See ARM section A8.8.5, rule A1.
       // cccc0010100snnnnddddiiiiiiiiiiii where cccc=Cond, dddd=Rd, nnnn=Rn,
       // s=SetFlags and iiiiiiiiiiii=Src1Value
       if (!isConditionDefined(Cond) || (Rd == RegARM32::Reg_pc && SetFlags) ||
           (Rn == RegARM32::Reg_lr) || (Rn == RegARM32::Reg_pc && SetFlags))
         // Conditions of rule violated.
         break;
       uint32_t Add = B2; // 0100
       uint32_t InstType = 1;
       emitType01(Cond, InstType, Add, SetFlags, Rn, Rd, Src1Value);
@@ skipping 14 matching lines @@
   // cccc000100101111111111110001mmmm where mmmm=rm and cccc=Cond.
   // (ARM section A8.8.27, encoding A1).
   assert(isGPRRegisterDefined(Rm));
   assert(isConditionDefined(Cond));
   AssemblerBuffer::EnsureCapacity ensured(&Buffer);
   uint32_t Encoding = (encodeCondition(Cond) << kConditionShift) | B24 | B21 |
                       (0xfff << 8) | B4 | (encodeGPRRegister(Rm) << kRmShift);
   emitInst(Encoding);
 }
 
+void ARM32::AssemblerARM32::ldr(const Operand *OpRt, const Operand *OpAddress,
+                                CondARM32::Cond Cond) {
+  // Note: Loop is used so that we can short ciruit using break;
+  do {
+    uint32_t Rt;
+    if (decodeOperand(OpRt, Rt) != DecodedAsRegister)
+      break;
+    uint32_t Address;
+    if (decodeAddress(OpAddress, Address) != DecodedAsImmRegOffset)
+      break;
+    // cccc010pu0w1nnnnttttiiiiiiiiiiii (ARM section A8.8.63, encoding A1; and
+    // section A8.6.68, encoding A1).
+    uint32_t InstType = B1; // 010
+    bool IsLoad = true;
+    Type Ty = OpRt->getType();
+    if (!(Ty == IceType_i32 || Ty == IceType_i8)) // TODO(kschimpf) Expand?
+      break;
+    bool IsByte = Ty == IceType_i8;
+    if ((getGPRReg(kRnShift, Address) == RegARM32::Encoded_Reg_pc) ||
+        (!IsByte && !isBitSet(P, Address) && isBitSet(W, Address)) ||
+        ((getGPRReg(kRnShift, Address) == RegARM32::Encoded_Reg_sp) &&
+         !isBitSet(P, Address) &&
+         isBitSet(U, Address) & !isBitSet(W, Address) &&
+         (mask(Address, kImm12Shift, kImmed12Bits) == 0x8 /* 000000000100 */)))
+      break;
+    emitMemOp(Cond, InstType, IsLoad, IsByte, Rt, Address);
+    return;
+  } while (0);
+  UnimplementedError(Ctx->getFlags());
+}
+
 void ARM32::AssemblerARM32::mov(const Operand *OpRd, const Operand *OpSrc,
                                 CondARM32::Cond Cond) {
   // Note: Loop is used so that we can short ciruit using break;
   do {
     uint32_t Rd;
-    if (decode(OpRd, Rd) != DecodedAsRegister)
+    if (decodeOperand(OpRd, Rd) != DecodedAsRegister)
       break;
     uint32_t Src;
     // TODO(kschimpf) Handle other forms of mov.
-    if (decode(OpSrc, Src) == DecodedAsRotatedImm8) {
+    if (decodeOperand(OpSrc, Src) == DecodedAsRotatedImm8) {
       // cccc0011101s0000ddddiiiiiiiiiiii (ARM section A8.8.102, encoding A1)
       // Note: We don't use movs in this assembler.
       constexpr bool SetFlags = false;
       if (!isConditionDefined(Cond) || (Rd == RegARM32::Reg_pc && SetFlags))
         // Conditions of rule violated.
         break;
       uint32_t Rn = 0;
       uint32_t Mov = B3 | B2 | B0; // 1101.
       uint32_t InstType = 1;
       emitType01(Cond, InstType, Mov, SetFlags, Rn, Rd, Src);
       return;
     }
   } while (0);
   UnimplementedError(Ctx->getFlags());
 }
 
+void ARM32::AssemblerARM32::str(const Operand *OpRt, const Operand *OpAddress,
+                                CondARM32::Cond Cond) {
+  // Note: Loop is used so that we can short ciruit using break;
+  do {
+    uint32_t Rt;
+    if (decodeOperand(OpRt, Rt) != DecodedAsRegister)
+      break;
+    uint32_t Address;
+    if (decodeAddress(OpAddress, Address) != DecodedAsImmRegOffset)
+      break;
+    // cccc010pub0nnnnttttiiiiiiiiiiii (ARM section A8.8.204, encoding A1; and
+    // section 18.8.207, encoding A1).
+    uint32_t InstType = B1; // 010
+    bool IsLoad = false;
+    Type Ty = OpRt->getType();
+    if (!(Ty == IceType_i32 || Ty == IceType_i8)) // TODO(kschimpf) Expand?
+      break;
+    bool IsByte = Ty == IceType_i8;

[Jim Stichnoth, 2015/10/15 20:41:29]

IceType_i1 should also qualify as IsByte, since str() is used for stack stores. 
(assuming this is how i1 variables are lowered)

[John, 2015/10/15 20:59:25]

const bool IsByte = ...

also, please assert that Ty != IceType_i1 here. I would not like to load/store
i1

[Karl, 2015/10/15 22:03:33]

Using typeWidthInBytes to resolve if is byte. Note that currently, we only allow
i32 and i8 (see test above). I have intentionally left out the other cases until
I can see an example.

+    // Check for rule violations.
+    if ((getGPRReg(kRnShift, Address) == RegARM32::Encoded_Reg_pc) ||
+        (!isBitSet(P, Address) && isBitSet(W, Address)) ||
+        (!IsByte &&
+         (getGPRReg(kRnShift, Address) == RegARM32::Encoded_Reg_sp) &&
+         isBitSet(P, Address) && !isBitSet(U, Address) &&
+         isBitSet(W, Address) &&
+         (mask(Address, kImm12Shift, kImmed12Bits) == 0x8 /* 000000000100 */)))
+      break;
+    emitMemOp(Cond, InstType, IsLoad, IsByte, Rt, Address);
+    return;
+  } while (0);
+  UnimplementedError(Ctx->getFlags());
+}
+
 void ARM32::AssemblerARM32::sub(const Operand *OpRd, const Operand *OpRn,
                                 const Operand *OpSrc1, bool SetFlags,
                                 CondARM32::Cond Cond) {
   // Note: Loop is used so that we can short circuit using break;
   do {
     uint32_t Rd;
-    if (decode(OpRd, Rd) != DecodedAsRegister)
+    if (decodeOperand(OpRd, Rd) != DecodedAsRegister)
       break;
     uint32_t Rn;
-    if (decode(OpRn, Rn) != DecodedAsRegister)
+    if (decodeOperand(OpRn, Rn) != DecodedAsRegister)
       break;
     uint32_t Src1Value;
     // TODO(kschimpf) Other possible decodings of add.
-    if (decode(OpSrc1, Src1Value) == DecodedAsRotatedImm8) {
+    if (decodeOperand(OpSrc1, Src1Value) == DecodedAsRotatedImm8) {
       // Sub (Immediate): See ARM section A8.8.222, rule A1.
       // cccc0010010snnnnddddiiiiiiiiiiii where cccc=Cond, dddd=Rd, nnnn=Rn,
       // s=SetFlags and iiiiiiiiiiii=Src1Value
       if (!isConditionDefined(Cond) || (Rd == RegARM32::Reg_pc && SetFlags) ||
           (Rn == RegARM32::Reg_lr) || (Rn == RegARM32::Reg_pc && SetFlags))
         // Conditions of rule violated.
         break;
       uint32_t Add = B1; // 0010
       uint32_t InstType = 1;
       emitType01(Cond, InstType, Add, SetFlags, Rn, Rd, Src1Value);
       return;
     }
   } while (0);
   UnimplementedError(Ctx->getFlags());
 }
 
 } // end of namespace Ice