Subzero: lower the rest of the atomic operations.

src/IceInstX8632.h

 //===- subzero/src/IceInstX8632.h - Low-level x86 instructions --*- C++ -*-===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file declares the InstX8632 and OperandX8632 classes and
@@ skipping 36 matching lines @@
   OperandX8632 &operator=(const OperandX8632 &) LLVM_DELETED_FUNCTION;
 };
 
 // OperandX8632Mem represents the m32 addressing mode, with optional
 // base and index registers, a constant offset, and a fixed shift
 // value for the index register.
 class OperandX8632Mem : public OperandX8632 {
 public:
   enum SegmentRegisters {
     DefaultSegment = -1,
-#define X(val, name)                                                           \
-    val,
-      SEG_REGX8632_TABLE
+#define X(val, name) val,
+    SEG_REGX8632_TABLE
 #undef X
         SegReg_NUM
   };
   static OperandX8632Mem *create(Cfg *Func, Type Ty, Variable *Base,
                                  Constant *Offset, Variable *Index = NULL,
                                  uint16_t Shift = 0,
                                  SegmentRegisters SegmentReg = DefaultSegment) {
     return new (Func->allocate<OperandX8632Mem>())
         OperandX8632Mem(Func, Ty, Base, Offset, Index, Shift, SegmentReg);
   }
@@ skipping 64 matching lines @@
 public:
   enum InstKindX8632 {
     k__Start = Inst::Target,
     Adc,
     Add,
     Addss,
     And,
     Br,
     Call,
     Cdq,
+    Cmpxchg,
+    Cmpxchg8b,
     Cvt,
     Div,
     Divss,
     Fld,
     Fstp,
     Icmp,
     Idiv,
     Imul,
     Label,
     Load,
     Mfence,
     Mov,
     Movq,
     Movsx,
     Movzx,
     Mul,
     Mulss,
+    Neg,
     Or,
     Pop,
     Push,
     Ret,
     Sar,
     Sbb,
     Shl,
     Shld,
     Shr,
     Shrd,
     Store,
     StoreQ,
     Sub,
     Subss,
     Test,
     Ucomiss,
     UD2,
     Xadd,
+    Xchg,
     Xor
   };
   static const char *getWidthString(Type Ty);
   virtual void emit(const Cfg *Func) const = 0;
   virtual void dump(const Cfg *Func) const;
 
 protected:
   InstX8632(Cfg *Func, InstKindX8632 Kind, SizeT Maxsrcs, Variable *Dest)
       : InstTarget(Func, static_cast<InstKind>(Kind), Maxsrcs, Dest) {}
   virtual ~InstX8632() {}
@@ skipping 125 matching lines @@
   virtual void dump(const Cfg *Func) const;
   static bool classof(const Inst *Inst) { return isClassof(Inst, Call); }
 
 private:
   InstX8632Call(Cfg *Func, Variable *Dest, Operand *CallTarget);
   InstX8632Call(const InstX8632Call &) LLVM_DELETED_FUNCTION;
   InstX8632Call &operator=(const InstX8632Call &) LLVM_DELETED_FUNCTION;
   virtual ~InstX8632Call() {}
 };
 
+template <InstX8632::InstKindX8632 K>
+class InstX8632Unaryop : public InstX8632 {
+public:
+  // Create an unary-op instruction like neg.
+  // The source and dest are the same variable.
+  static InstX8632Unaryop *create(Cfg *Func, Variable *SrcDest) {

[Jim Stichnoth, 2014/07/08 04:50:19]

An instruction like this is valid x86:
  neg [eax+4*ecx]
but this implementation of UnaryOp only allows these forms:
  neg eax
  neg [esp+16]
since SrcDest is a Variable.  That's probably sufficient for our needs, but
ought to be documented.

Another possibility might be to declare SrcDest as Operand*, and set
Dest=llvm::dyn_cast<Variable>(SrcDest), but I don't know if that would create
any liveness problems.  (BTW, I see that you've done exactly that with cmpxchg.)

[jvoung (off chromium), 2014/07/08 18:14:07]

Okay, I think I will try making it a more generic Operand.

[jvoung (off chromium), 2014/07/09 17:07:55]

Done.

Not sure about liveness either, but Dest would only be null if it's not a
Variable, and then that would mean memory. In that case, it's like a store,
where Dest is also null?

[Jim Stichnoth, 2014/07/09 18:14:28]

Yes, that's also what I'd expect.

+    return new (Func->allocate<InstX8632Unaryop>())
+        InstX8632Unaryop(Func, SrcDest);
+  }
+  virtual void emit(const Cfg *Func) const {
+    Ostream &Str = Func->getContext()->getStrEmit();
+    assert(getSrcSize() == 1);
+    Str << "\t" << Opcode << "\t";
+    getSrc(0)->emit(Func);
+    Str << "\n";
+  }
+  virtual void dump(const Cfg *Func) const {
+    Ostream &Str = Func->getContext()->getStrDump();
+    dumpDest(Func);
+    Str << " = " << Opcode << "." << getDest()->getType() << " ";
+    dumpSources(Func);
+  }
+  static bool classof(const Inst *Inst) { return isClassof(Inst, K); }
+
+private:
+  InstX8632Unaryop(Cfg *Func, Variable *SrcDest)
+      : InstX8632(Func, K, 1, SrcDest) {
+    addSource(SrcDest);
+  }
+  InstX8632Unaryop(const InstX8632Unaryop &) LLVM_DELETED_FUNCTION;
+  InstX8632Unaryop &operator=(const InstX8632Unaryop &) LLVM_DELETED_FUNCTION;
+  virtual ~InstX8632Unaryop() {}
+  static const char *Opcode;
+};
+
 // See the definition of emitTwoAddress() for a description of
 // ShiftHack.
 void emitTwoAddress(const char *Opcode, const Inst *Inst, const Cfg *Func,
                     bool ShiftHack = false);
 
 template <InstX8632::InstKindX8632 K, bool ShiftHack = false>
 class InstX8632Binop : public InstX8632 {
 public:
   // Create an ordinary binary-op instruction like add or sub.
   static InstX8632Binop *create(Cfg *Func, Variable *Dest, Operand *Source) {
@@ skipping 52 matching lines @@
     addSource(Dest);
     addSource(Source1);
     addSource(Source2);
   }
   InstX8632Ternop(const InstX8632Ternop &) LLVM_DELETED_FUNCTION;
   InstX8632Ternop &operator=(const InstX8632Ternop &) LLVM_DELETED_FUNCTION;
   virtual ~InstX8632Ternop() {}
   static const char *Opcode;
 };
 
+typedef InstX8632Unaryop<InstX8632::Neg> InstX8632Neg;
 typedef InstX8632Binop<InstX8632::Add> InstX8632Add;
 typedef InstX8632Binop<InstX8632::Adc> InstX8632Adc;
 typedef InstX8632Binop<InstX8632::Addss> InstX8632Addss;
 typedef InstX8632Binop<InstX8632::Sub> InstX8632Sub;
 typedef InstX8632Binop<InstX8632::Subss> InstX8632Subss;
 typedef InstX8632Binop<InstX8632::Sbb> InstX8632Sbb;
 typedef InstX8632Binop<InstX8632::And> InstX8632And;
 typedef InstX8632Binop<InstX8632::Or> InstX8632Or;
 typedef InstX8632Binop<InstX8632::Xor> InstX8632Xor;
 typedef InstX8632Binop<InstX8632::Imul> InstX8632Imul;
 typedef InstX8632Binop<InstX8632::Mulss> InstX8632Mulss;
 typedef InstX8632Binop<InstX8632::Divss> InstX8632Divss;
 typedef InstX8632Binop<InstX8632::Shl, true> InstX8632Shl;
 typedef InstX8632Binop<InstX8632::Shr, true> InstX8632Shr;
 typedef InstX8632Binop<InstX8632::Sar, true> InstX8632Sar;
 typedef InstX8632Ternop<InstX8632::Idiv> InstX8632Idiv;
 typedef InstX8632Ternop<InstX8632::Div> InstX8632Div;
 
+// Base class for a lockable x86-32 instruction (emits a locked prefix).
+class InstX8632Lockable : public InstX8632 {
+public:
+  virtual void emit(const Cfg *Func) const = 0;
+  virtual void dump(const Cfg *Func) const;
+
+protected:
+  InstX8632Lockable(Cfg *Func, InstKindX8632 Kind, SizeT Maxsrcs,
+                    Variable *Dest, bool Locked)
+      : InstX8632(Func, Kind, Maxsrcs, Dest), Locked(Locked) {
+    // Assume that such instructions are used for Atomics and be careful
+    // with optimizations.
+    HasSideEffects = Locked;
+  }
+  bool Locked;
+
+private:
+  InstX8632Lockable(const InstX8632Lockable &) LLVM_DELETED_FUNCTION;
+  InstX8632Lockable &operator=(const InstX8632Lockable &) LLVM_DELETED_FUNCTION;
+};
+
 // Mul instruction - unsigned multiply.
 class InstX8632Mul : public InstX8632 {
 public:
   static InstX8632Mul *create(Cfg *Func, Variable *Dest, Variable *Source1,
                               Operand *Source2) {
     return new (Func->allocate<InstX8632Mul>())
         InstX8632Mul(Func, Dest, Source1, Source2);
   }
   virtual void emit(const Cfg *Func) const;
   virtual void dump(const Cfg *Func) const;
@@ skipping 59 matching lines @@
   virtual void dump(const Cfg *Func) const;
   static bool classof(const Inst *Inst) { return isClassof(Inst, Cdq); }
 
 private:
   InstX8632Cdq(Cfg *Func, Variable *Dest, Operand *Source);
   InstX8632Cdq(const InstX8632Cdq &) LLVM_DELETED_FUNCTION;
   InstX8632Cdq &operator=(const InstX8632Cdq &) LLVM_DELETED_FUNCTION;
   virtual ~InstX8632Cdq() {}
 };
 
+// Cmpxchg instruction - cmpxchg <dest>, <desired> will compare if <dest>
+// equals eax. If so, the ZF is set and <desired> is stored in <dest>.
+// If not, ZF is cleared and <dest> is copied to eax (or subregister).
+// The user is responsible for making a FakeDef to mark eax as
+// possibly changed.

[Jim Stichnoth, 2014/07/08 04:50:19]

Would it be simpler to swap the roles of Eax and DestOrAddr with respect to the
Dest operand?  That way, the instruction would always have a non-NULL Dest, and
the lowering code could conditionally create the FakeDef if DestOrAddr is a
Variable.

[jvoung (off chromium), 2014/07/08 18:14:07]

I think this is similar to Xchg. See below?

[jvoung (off chromium), 2014/07/09 17:07:55]

Okay, this is slightly different from Xchg, in that it has an explicit Locked
parameter.

As we discussed, if DestOrAddr is a memory operand, and we don't want it to be
DCE'ed when Eax is unused. Locked=true helps because it marks the instruction as
HasSideEffects. It doesn't help when Locked=false (the caller has the option to
make that mistake)... I'm not sure sure how likely that is. Interestingly
enough, in contrast, Xchg seems more useful to use not-Locked, though Locking is
automatic there (can be used for 16-bit bswap w/ two register operands)...

[Jim Stichnoth, 2014/07/09 18:14:27]

After more thought, I would go simple and just disable DCE of xchg and cmpxchg
instructions always.  Using a NULL dest is an "approved" way of doing this, and
is minimally disruptive to the current patch since the emit/dump code doesn't
reference Dest.

+// <dest> can be a register or memory, while <desired> must be a register.
+class InstX8632Cmpxchg : public InstX8632Lockable {
+public:
+  static InstX8632Cmpxchg *create(Cfg *Func, Operand *DestOrAddr, Variable *Eax,
+                                  Variable *Desired, bool Locked) {
+    return new (Func->allocate<InstX8632Cmpxchg>())
+        InstX8632Cmpxchg(Func, DestOrAddr, Eax, Desired, Locked);
+  }
+  virtual void emit(const Cfg *Func) const;
+  virtual void dump(const Cfg *Func) const;
+  static bool classof(const Inst *Inst) { return isClassof(Inst, Cmpxchg); }
+
+private:
+  InstX8632Cmpxchg(Cfg *Func, Operand *DestOrAddr, Variable *Eax,
+                   Variable *Desired, bool Locked);
+  InstX8632Cmpxchg(const InstX8632Cmpxchg &) LLVM_DELETED_FUNCTION;
+  InstX8632Cmpxchg &operator=(const InstX8632Cmpxchg &) LLVM_DELETED_FUNCTION;
+  virtual ~InstX8632Cmpxchg() {}
+};
+
+// Cmpxchg8b instruction - cmpxchg8b <m64> will compare if <m64>
+// equals edx:eax. If so, the ZF is set and ecx:ebx is stored in <m64>.
+// If not, ZF is cleared and <m64> is copied to edx:eax.
+// <m64> must be a memory operand.

[Jim Stichnoth, 2014/07/08 04:50:19]

Document the user's responsibility to add appropriate FakeDefs.

BTW, in the style of some other 64-bit integer instructions, you could also
define eax to be the Dest variable, and then only have to create a FakeDef for
edx.

[jvoung (off chromium), 2014/07/09 17:07:55]

Documented.

The other 64-bit integer instruction touching eax would be mul?

I feel that this a bit different from that, and this is more like a store
instead.

For mul, what's modified is registers (edx:eax), so it makes sense to just put
Eax in the Dest so that you don't need two FakeDefs and you have some Dest'ed
variable to chain the edx FakeDef against. However, cmpxchg8b, like cmpxchg,
will modify memory as well and the choice of Locked=true/false is again up to
the user.

Maybe for cmpxchg8b it will always "HaveSideEffects", because one of the dests
is always memory (in contrast to cmpxchg, where there is a choice).

[Jim Stichnoth, 2014/07/09 18:14:28]

I was thinking of the 64-bit ret, but there may be others.
As I commented elsewhere, I changed my mind and think that these xchg
instructions should probably have NULL dest, so never mind my earlier
suggestion. :)

+class InstX8632Cmpxchg8b : public InstX8632Lockable {
+public:
+  static InstX8632Cmpxchg8b *create(Cfg *Func, OperandX8632 *Dest,
+                                    Variable *Edx, Variable *Eax, Variable *Ecx,
+                                    Variable *Ebx, bool Locked) {
+    return new (Func->allocate<InstX8632Cmpxchg8b>())
+        InstX8632Cmpxchg8b(Func, Dest, Edx, Eax, Ecx, Ebx, Locked);
+  }
+  virtual void emit(const Cfg *Func) const;
+  virtual void dump(const Cfg *Func) const;
+  static bool classof(const Inst *Inst) { return isClassof(Inst, Cmpxchg8b); }
+
+private:
+  InstX8632Cmpxchg8b(Cfg *Func, OperandX8632 *Dest, Variable *Edx,
+                     Variable *Eax, Variable *Ecx, Variable *Ebx, bool Locked);
+  InstX8632Cmpxchg8b(const InstX8632Cmpxchg8b &) LLVM_DELETED_FUNCTION;
+  InstX8632Cmpxchg8b &
+  operator=(const InstX8632Cmpxchg8b &) LLVM_DELETED_FUNCTION;
+  virtual ~InstX8632Cmpxchg8b() {}
+};
+
 // Cvt instruction - wrapper for cvtsX2sY where X and Y are in {s,d,i}
 // as appropriate.  s=float, d=double, i=int.  X and Y are determined
 // from dest/src types.  Sign and zero extension on the integer
 // operand needs to be done separately.
 class InstX8632Cvt : public InstX8632 {
 public:
   static InstX8632Cvt *create(Cfg *Func, Variable *Dest, Operand *Source) {
     return new (Func->allocate<InstX8632Cvt>())
         InstX8632Cvt(Func, Dest, Source);
   }
@@ skipping 301 matching lines @@
   virtual ~InstX8632Ret() {}
 };
 
 // Exchanging Add instruction.  Exchanges the first operand (destination
 // operand) with the second operand (source operand), then loads the sum
 // of the two values into the destination operand. The destination may be
 // a register or memory, while the source must be a register.
 //
 // Both the dest and source are updated. The caller should then insert a
 // FakeDef to reflect the second udpate.
-class InstX8632Xadd : public InstX8632 {
+class InstX8632Xadd : public InstX8632Lockable {
 public:
   static InstX8632Xadd *create(Cfg *Func, Operand *Dest, Variable *Source,
                                bool Locked) {
     return new (Func->allocate<InstX8632Xadd>())
         InstX8632Xadd(Func, Dest, Source, Locked);
   }
   virtual void emit(const Cfg *Func) const;
   virtual void dump(const Cfg *Func) const;
   static bool classof(const Inst *Inst) { return isClassof(Inst, Xadd); }
 
 private:
-  bool Locked;
-
   InstX8632Xadd(Cfg *Func, Operand *Dest, Variable *Source, bool Locked);
   InstX8632Xadd(const InstX8632Xadd &) LLVM_DELETED_FUNCTION;
   InstX8632Xadd &operator=(const InstX8632Xadd &) LLVM_DELETED_FUNCTION;
   virtual ~InstX8632Xadd() {}
 };
 
+// Exchange instruction.  Exchanges the first operand (destination
+// operand) with the second operand (source operand). At least one of
+// the operands must be a register (and the other can be reg or mem).
+// Both the Dest and Source are updated. If there is a memory operand,
+// then the instruction is automatically "locked" without the need for
+// a lock prefix.
+class InstX8632Xchg : public InstX8632 {
+public:
+  static InstX8632Xchg *create(Cfg *Func, Operand *Dest, Variable *Source) {

[Jim Stichnoth, 2014/07/08 04:50:19]

Can we structure this so that Dest is the Variable and Source is the Operand?

[jvoung (off chromium), 2014/07/08 18:14:07]

I think the motivation for this was to make it like "Store" in the sense that if
Dest is not a variable, then Dest is NULL and it cannot be DCE'ed when the Dest
is actually a dead variable (it shouldn't be because Source might be memory and
we don't know if that is a dead store).

If we flip Dest and Source, is there another way to prevent it from DCE'ed? Just
mark the instruction as HasSideEffects when the source is memory?

[Jim Stichnoth, 2014/07/09 18:14:27]

At least for now, I would just be conservative and mark HasSideEffects whenever
the instruction is locked.  The main purpose of HasSideEffects is to suppress
DCE.

+    return new (Func->allocate<InstX8632Xchg>())
+        InstX8632Xchg(Func, Dest, Source);
+  }
+  virtual void emit(const Cfg *Func) const;
+  virtual void dump(const Cfg *Func) const;
+  static bool classof(const Inst *Inst) { return isClassof(Inst, Xchg); }
+
+private:
+  InstX8632Xchg(Cfg *Func, Operand *Dest, Variable *Source);
+  InstX8632Xchg(const InstX8632Xchg &) LLVM_DELETED_FUNCTION;
+  InstX8632Xchg &operator=(const InstX8632Xchg &) LLVM_DELETED_FUNCTION;
+  virtual ~InstX8632Xchg() {}
+};
+
 } // end of namespace Ice
 
 #endif // SUBZERO_SRC_ICEINSTX8632_H