Add atomic load/store, fetch_add, fence, and is-lock-free lowering.

src/IceTargetLoweringX8632.cpp

 //===- subzero/src/IceTargetLoweringX8632.cpp - x86-32 lowering -----------===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the TargetLoweringX8632 class, which
@@ skipping 1582 matching lines @@
       assert(Src0RM->getType() == IceType_f64);
       // a.i64 = bitcast b.f64 ==>
       //   s.f64 = spill b.f64
       //   t_lo.i32 = lo(s.f64)
       //   a_lo.i32 = t_lo.i32
       //   t_hi.i32 = hi(s.f64)
       //   a_hi.i32 = t_hi.i32
       Variable *Spill = Func->makeVariable(IceType_f64, Context.getNode());
       Spill->setWeight(RegWeight::Zero);
       Spill->setPreferredRegister(llvm::dyn_cast<Variable>(Src0RM), true);
-      _mov(Spill, Src0RM);
+      _movq(Spill, Src0RM);
 
       Variable *DestLo = llvm::cast<Variable>(loOperand(Dest));
       Variable *DestHi = llvm::cast<Variable>(hiOperand(Dest));
       Variable *T_Lo = makeReg(IceType_i32);
       Variable *T_Hi = makeReg(IceType_i32);
       VariableSplit *SpillLo =
           VariableSplit::create(Func, Spill, VariableSplit::Low);
       VariableSplit *SpillHi =
           VariableSplit::create(Func, Spill, VariableSplit::High);
 
@@ skipping 19 matching lines @@
 
       Variable *T_Lo = NULL, *T_Hi = NULL;
       VariableSplit *SpillLo =
           VariableSplit::create(Func, Spill, VariableSplit::Low);
       VariableSplit *SpillHi =
           VariableSplit::create(Func, Spill, VariableSplit::High);
       _mov(T_Lo, loOperand(Src0RM));
       _store(T_Lo, SpillLo);
       _mov(T_Hi, hiOperand(Src0RM));
       _store(T_Hi, SpillHi);
-      _mov(Dest, Spill);
+      _movq(Dest, Spill);
     } break;
     }
     break;
   }
 }
 
 void TargetX8632::lowerFcmp(const InstFcmp *Inst) {
   Operand *Src0 = Inst->getSrc(0);
   Operand *Src1 = Inst->getSrc(1);
   Variable *Dest = Inst->getDest();
@@ skipping 120 matching lines @@
   _mov(Dest, One);
   _br(getIcmp32Mapping(Inst->getCondition()), Label);
   Context.insert(InstFakeUse::create(Func, Dest));
   _mov(Dest, Zero);
   Context.insert(Label);
 }
 
 void TargetX8632::lowerIntrinsicCall(const InstIntrinsicCall *Instr) {
   switch (Instr->getIntrinsicInfo().ID) {
   case Intrinsics::AtomicCmpxchg:
+    if (!Intrinsics::VerifyMemoryOrder(
+             llvm::cast<ConstantInteger>(Instr->getArg(3))->getValue())) {
+      Func->setError("Unexpected memory order for AtomicCmpxchg");
+      return;
+    }
+    // TODO(jvoung): fill it in.
+    Func->setError("Unhandled intrinsic");
+    return;
   case Intrinsics::AtomicFence:
+    if (!Intrinsics::VerifyMemoryOrder(
+             llvm::cast<ConstantInteger>(Instr->getArg(0))->getValue())) {
+      Func->setError("Unexpected memory order for AtomicFence");
+      return;
+    }
+    _mfence();
+    return;
   case Intrinsics::AtomicFenceAll:
-  case Intrinsics::AtomicIsLockFree:
-  case Intrinsics::AtomicLoad:
+    _mfence();

[JF, 2014/06/24 01:23:29]

FenceAll is meant as an equivalent to asm(:::"m"), so there should be a TODO
here to ensure no memory operations move past it in Subzero (not just atomic
accesses, but regular memory too).

[jvoung (off chromium), 2014/06/24 21:16:55]

Added a comment, and a couple of speculative tests using globals and allocas.
Otherwise, I don't think we really have the aliasing information (or budget to
run alias analysis) on pointers to move loads/stores.

We also don't really have any code that moves loads and stores at the moment, so
there's no existing flag to check, but I've marked mfence w/ the coarse-grained
"HasSideEffects" flag.

Well, there is some code that could possibly move a load. That is the load + add
fusing. It could move the load to where the add is, which would be dangerous if
split by a fence. The test tests this case. Also added a comment to the load+add
fusing code to be more careful if it is beefed up any more.

+    return;
+  case Intrinsics::AtomicIsLockFree: {
+    Constant *One = Ctx->getConstantInt(IceType_i32, 1);

[JF, 2014/06/24 01:23:29]

It would be good to explain that x86 is always lock free for 8/16/32/64 bit
accesses. A check for wider bitwidth would be useful, to make sure this fails
if/when we add support for them.

This should also be used to key DCE in Subzero, since it's not known at
compilation time but is known at translation time.

[jvoung (off chromium), 2014/06/24 21:16:55]

iOn 2014/06/24 01:23:29, JF wrote:
Ah!  I actually misread what the arguments were... Added a comment, the checks
(for exactly those bit widths), and test.
Added a TODO and a test that should illustrate what can be optimized.

I think that such DCE will likely be a separate pass. Depends on tradeoff of
time spent by the compiler looking for and marking dead code, and the benefit of
skipping code generation for the dead code.

+    Variable *Dest = Instr->getDest();
+    _mov(Dest, One);
+    return;
+  }
+  case Intrinsics::AtomicLoad: {
+    // We require the memory address to be naturally aligned.
+    // Given that is the case, then normal loads are atomic.
+    if (!Intrinsics::VerifyMemoryOrder(
+             llvm::cast<ConstantInteger>(Instr->getArg(1))->getValue())) {
+      Func->setError("Unexpected memory ordering for AtomicLoad");
+      return;
+    }
+    Variable *Dest = Instr->getDest();
+    if (Dest->getType() == IceType_i64) {
+      // Follow what GCC does and use a movq instead of what lowerLoad()
+      // normally does (split the load into two).
+      // Thus, this skips load/arithmetic op folding. Load/arithmetic folding
+      // can't happen anyway, since this is x86-32 and integer arithmetic only
+      // happens on 32-bit quantities.
+      Variable *T = makeReg(IceType_f64);
+      OperandX8632Mem *Addr = FormMemoryOperand(Instr->getArg(0), IceType_f64);
+      _movq(T, Addr);
+      // Then cast the bits back out of the XMM register to the i64 Dest.
+      InstCast *Cast = InstCast::create(Func, InstCast::Bitcast, Dest, T);
+      lowerCast(Cast);
+      // Make sure that the atomic load isn't elided.
+      Context.insert(InstFakeUse::create(Func, Dest->getLo()));
+      Context.insert(InstFakeUse::create(Func, Dest->getHi()));
+      return;
+    }
+    InstLoad *Load = InstLoad::create(Func, Dest, Instr->getArg(0));
+    lowerLoad(Load);
+    // Make sure the atomic load isn't elided.
+    Context.insert(InstFakeUse::create(Func, Dest));
+    return;
+  }
   case Intrinsics::AtomicRMW:
-  case Intrinsics::AtomicStore:
+    if (!Intrinsics::VerifyMemoryOrder(
+             llvm::cast<ConstantInteger>(Instr->getArg(3))->getValue())) {
+      Func->setError("Unexpected memory ordering for AtomicRMW");
+      return;
+    }
+    lowerAtomicRMW(Instr->getDest(),
+                   static_cast<uint32_t>(llvm::cast<ConstantInteger>(
+                       Instr->getArg(0))->getValue()),
+                   Instr->getArg(1), Instr->getArg(2));
+    return;
+  case Intrinsics::AtomicStore: {
+    if (!Intrinsics::VerifyMemoryOrder(
+             llvm::cast<ConstantInteger>(Instr->getArg(2))->getValue())) {
+      Func->setError("Unexpected memory ordering for AtomicStore");
+      return;
+    }
+    // We require the memory address to be naturally aligned.
+    // Given that is the case, then normal stores are atomic.
+    // Add a fence after the store to make it visible.
+    Operand *Value = Instr->getArg(0);
+    Operand *Ptr = Instr->getArg(1);
+    if (Value->getType() == IceType_i64) {
+      // Use a movq instead of what lowerStore() normally does
+      // (split the store into two), following what GCC does.
+      // Cast the bits from int -> to an xmm register first.
+      Variable *T = makeReg(IceType_f64);
+      InstCast *Cast = InstCast::create(Func, InstCast::Bitcast, T, Value);
+      lowerCast(Cast);
+      // Then store XMM w/ a movq.
+      OperandX8632Mem *Addr = FormMemoryOperand(Ptr, IceType_f64);
+      _storeq(T, Addr);
+      _mfence();
+      return;
+    }
+    InstStore *Store = InstStore::create(Func, Value, Ptr);
+    lowerStore(Store);
+    _mfence();
+    return;
+  }
   case Intrinsics::Bswap:
   case Intrinsics::Ctlz:
   case Intrinsics::Ctpop:
   case Intrinsics::Cttz:
+    // TODO(jvoung): fill it in.
     Func->setError("Unhandled intrinsic");
     return;
   case Intrinsics::Longjmp: {
     InstCall *Call = makeHelperCall("longjmp", NULL, 2);
     Call->addArg(Instr->getArg(0));
     Call->addArg(Instr->getArg(1));
     lowerCall(Call);
-    break;
+    return;
   }
   case Intrinsics::Memcpy: {
     // In the future, we could potentially emit an inline memcpy/memset, etc.
     // for intrinsic calls w/ a known length.
     InstCall *Call = makeHelperCall("memcpy", NULL, 3);
     Call->addArg(Instr->getArg(0));
     Call->addArg(Instr->getArg(1));
     Call->addArg(Instr->getArg(2));
     lowerCall(Call);
-    break;
+    return;
   }
   case Intrinsics::Memmove: {
     InstCall *Call = makeHelperCall("memmove", NULL, 3);
     Call->addArg(Instr->getArg(0));
     Call->addArg(Instr->getArg(1));
     Call->addArg(Instr->getArg(2));
     lowerCall(Call);
-    break;
+    return;
   }
   case Intrinsics::Memset: {
     // The value operand needs to be extended to a stack slot size
     // because we "push" only works for a specific operand size.
     Operand *ValOp = Instr->getArg(1);
     assert(ValOp->getType() == IceType_i8);
     Variable *ValExt = makeReg(stackSlotType());
     _movzx(ValExt, ValOp);
     InstCall *Call = makeHelperCall("memset", NULL, 3);
     Call->addArg(Instr->getArg(0));
     Call->addArg(ValExt);
     Call->addArg(Instr->getArg(2));
     lowerCall(Call);
-    break;
+    return;
   }
   case Intrinsics::NaClReadTP: {
-    Constant *Zero = Ctx->getConstantInt(IceType_i32, 0);
+    Constant *Zero = Ctx->getConstantZero(IceType_i32);
     Operand *Src = OperandX8632Mem::create(Func, IceType_i32, NULL, Zero, NULL,
                                            0, OperandX8632Mem::SegReg_GS);
     Variable *Dest = Instr->getDest();
     Variable *T = NULL;
     _mov(T, Src);
     _mov(Dest, T);
-    break;
+    return;
   }
   case Intrinsics::Setjmp: {
     InstCall *Call = makeHelperCall("setjmp", Instr->getDest(), 1);
     Call->addArg(Instr->getArg(0));
     lowerCall(Call);
-    break;
+    return;
   }
   case Intrinsics::Sqrt:
   case Intrinsics::Stacksave:
   case Intrinsics::Stackrestore:
+    // TODO(jvoung): fill it in.
     Func->setError("Unhandled intrinsic");
     return;
   case Intrinsics::Trap:
     _ud2();
-    break;
+    return;
   case Intrinsics::UnknownIntrinsic:
     Func->setError("Should not be lowering UnknownIntrinsic");
     return;
   }
   return;
 }
 
+void TargetX8632::lowerAtomicRMW(Variable *Dest, uint32_t Operation,
+                                 Operand *Ptr, Operand *Val) {
+  switch (Operation) {
+  default:
+    Func->setError("Unknown AtomicRMW operation");
+    return;
+  case Intrinsics::AtomicAdd: {
+    if (Dest->getType() == IceType_i64) {
+      // Do a nasty cmpxchg8b loop. Factor this into a function.
+      // TODO(jvoung): fill it in.
+      Func->setError("Unhandled AtomicRMW operation");
+      return;
+    }
+    OperandX8632Mem *Addr = FormMemoryOperand(Ptr, Dest->getType());
+    const bool Locked = true;
+    Variable *T = NULL;
+    _mov(T, Val);
+    _xadd(Addr, T, Locked);
+    _mov(Dest, T);
+    return;
+  }
+  case Intrinsics::AtomicSub: {
+    if (Dest->getType() == IceType_i64) {
+      // Do a nasty cmpxchg8b loop.
+      // TODO(jvoung): fill it in.
+      Func->setError("Unhandled AtomicRMW operation");
+      return;
+    }
+    // Generate a memory operand from Ptr.
+    // neg...
+    // Then do the same as AtomicAdd.
+    // TODO(jvoung): fill it in.
+    Func->setError("Unhandled AtomicRMW operation");
+    return;
+  }
+  case Intrinsics::AtomicOr:
+  case Intrinsics::AtomicAnd:
+  case Intrinsics::AtomicXor:
+  case Intrinsics::AtomicExchange:
+    // TODO(jvoung): fill it in.
+    Func->setError("Unhandled AtomicRMW operation");
+    return;
+  }
+}
+
 namespace {
 
 bool isAdd(const Inst *Inst) {
   if (const InstArithmetic *Arith =
           llvm::dyn_cast_or_null<const InstArithmetic>(Inst)) {
     return (Arith->getOp() == InstArithmetic::Add);
   }
   return false;
 }
 
@@ skipping 116 matching lines @@
 
 } // anonymous namespace
 
 void TargetX8632::lowerLoad(const InstLoad *Inst) {
   // A Load instruction can be treated the same as an Assign
   // instruction, after the source operand is transformed into an
   // OperandX8632Mem operand.  Note that the address mode
   // optimization already creates an OperandX8632Mem operand, so it
   // doesn't need another level of transformation.
   Type Ty = Inst->getDest()->getType();
-  Operand *Src0 = Inst->getSourceAddress();
-  // Address mode optimization already creates an OperandX8632Mem
-  // operand, so it doesn't need another level of transformation.
-  if (!llvm::isa<OperandX8632Mem>(Src0)) {
-    Variable *Base = llvm::dyn_cast<Variable>(Src0);
-    Constant *Offset = llvm::dyn_cast<Constant>(Src0);
-    assert(Base || Offset);
-    Src0 = OperandX8632Mem::create(Func, Ty, Base, Offset);
-  }
+  Operand *Src0 = FormMemoryOperand(Inst->getSourceAddress(), Ty);
 
   // Fuse this load with a subsequent Arithmetic instruction in the
   // following situations:
   //   a=[mem]; c=b+a ==> c=b+[mem] if last use of a and a not in b
   //   a=[mem]; c=a+b ==> c=b+[mem] if commutative and above is true
   //
   // TODO: Clean up and test thoroughly.
   //
   // TODO: Why limit to Arithmetic instructions?  This could probably be
   // applied to most any instruction type.  Look at all source operands
@@ skipping 117 matching lines @@
     SrcF = legalize(SrcF, Legal_Reg | Legal_Imm, true);
     _mov(Dest, SrcF);
   }
 
   Context.insert(Label);
 }
 
 void TargetX8632::lowerStore(const InstStore *Inst) {
   Operand *Value = Inst->getData();
   Operand *Addr = Inst->getAddr();
-  OperandX8632Mem *NewAddr = llvm::dyn_cast<OperandX8632Mem>(Addr);
-  // Address mode optimization already creates an OperandX8632Mem
-  // operand, so it doesn't need another level of transformation.
-  if (!NewAddr) {
-    // The address will be either a constant (which represents a global
-    // variable) or a variable, so either the Base or Offset component
-    // of the OperandX8632Mem will be set.
-    Variable *Base = llvm::dyn_cast<Variable>(Addr);
-    Constant *Offset = llvm::dyn_cast<Constant>(Addr);
-    assert(Base || Offset);
-    NewAddr = OperandX8632Mem::create(Func, Value->getType(), Base, Offset);
-  }
-  NewAddr = llvm::cast<OperandX8632Mem>(legalize(NewAddr));
+  OperandX8632Mem *NewAddr = FormMemoryOperand(Addr, Value->getType());
 
   if (NewAddr->getType() == IceType_i64) {
     Value = legalize(Value);
     Operand *ValueHi = legalize(hiOperand(Value), Legal_Reg | Legal_Imm, true);
     Operand *ValueLo = legalize(loOperand(Value), Legal_Reg | Legal_Imm, true);
     _store(ValueHi, llvm::cast<OperandX8632Mem>(hiOperand(NewAddr)));
     _store(ValueLo, llvm::cast<OperandX8632Mem>(loOperand(NewAddr)));
   } else {
     Value = legalize(Value, Legal_Reg | Legal_Imm, true);
     _store(Value, NewAddr);
@@ skipping 97 matching lines @@
       //
       // If in the future the implementation is changed to lower undef
       // values to uninitialized registers, a FakeDef will be needed:
       //     Context.insert(InstFakeDef::create(Func, Reg));
       // This is in order to ensure that the live range of Reg is not
       // overestimated.  If the constant being lowered is a 64 bit value,
       // then the result should be split and the lo and hi components will
       // need to go in uninitialized registers.
       From = Ctx->getConstantZero(From->getType());
     }
-    bool NeedsReg = !(Allowed & Legal_Imm) ||
+    bool NeedsReg =
+        !(Allowed & Legal_Imm) ||
         // ConstantFloat and ConstantDouble are actually memory operands.
-        (!(Allowed & Legal_Mem) && (From->getType() == IceType_f32 ||
-                                    From->getType() == IceType_f64));
+        (!(Allowed & Legal_Mem) &&
+         (From->getType() == IceType_f32 || From->getType() == IceType_f64));
     if (NeedsReg) {
       Variable *Reg = makeReg(From->getType(), RegNum);
       _mov(Reg, From);
       From = Reg;
     }
     return From;
   }
   if (Variable *Var = llvm::dyn_cast<Variable>(From)) {
     // We need a new physical register for the operand if:
     //   Mem is not allowed and Var->getRegNum() is unknown, or
@@ skipping 12 matching lines @@
   llvm_unreachable("Unhandled operand kind in legalize()");
   return From;
 }
 
 // Provide a trivial wrapper to legalize() for this common usage.
 Variable *TargetX8632::legalizeToVar(Operand *From, bool AllowOverlap,
                                      int32_t RegNum) {
   return llvm::cast<Variable>(legalize(From, Legal_Reg, AllowOverlap, RegNum));
 }
 
+OperandX8632Mem *TargetX8632::FormMemoryOperand(Operand *Operand, Type Ty) {
+  OperandX8632Mem *Mem = llvm::dyn_cast<OperandX8632Mem>(Operand);
+  // It may be the case that address mode optimization already creates
+  // an OperandX8632Mem, so in that case it wouldn't need another level
+  // of transformation.
+  if (!Mem) {
+    Variable *Base = llvm::dyn_cast<Variable>(Operand);
+    Constant *Offset = llvm::dyn_cast<Constant>(Operand);
+    assert(Base || Offset);
+    Mem = OperandX8632Mem::create(Func, Ty, Base, Offset);
+  }
+  return llvm::cast<OperandX8632Mem>(legalize(Mem));
+}
+
 Variable *TargetX8632::makeReg(Type Type, int32_t RegNum) {
   Variable *Reg = Func->makeVariable(Type, Context.getNode());
   if (RegNum == Variable::NoRegister)
     Reg->setWeightInfinite();
   else
     Reg->setRegNum(RegNum);
   return Reg;
 }
 
 void TargetX8632::postLower() {
@@ skipping 64 matching lines @@
   // llvm-mc doesn't parse "dword ptr [.L$foo]".
   Str << "dword ptr [L$" << IceType_f32 << "$" << getPoolEntryID() << "]";
 }
 
 template <> void ConstantDouble::emit(GlobalContext *Ctx) const {
   Ostream &Str = Ctx->getStrEmit();
   Str << "qword ptr [L$" << IceType_f64 << "$" << getPoolEntryID() << "]";
 }
 
 } // end of namespace Ice