VEX IR

       VEX不是一种新的语言，它是从机器码转化而来的一种中间表达式，那么为什么要用到这种中间表达式呢?从我理解的程度来说，不同的处理器有不同的架构，其机器码的表现形式也是不一样的，所以为了屏蔽这种差异性，产生了一种新的中间表达式。当然VEX的产生也是带有一定导向的，它可以表示出每一条机器指令对机器产生的影响，程序都走过了哪些路径等等，这样对于在测试中帮助程序改变所走路径，到达程序的高的覆盖率很有帮助。

学习VEX IR应该有一些学习汇编码的基础，下面讲几个VEX中会用到的指令概念：

1.CAS（compare-and-swap）:CAS指令是并行程序设计最基础的基石，随着越来越多的本本都用上了双核，这个世界已经快速步入并行计算时代，CAS指令发挥的作用也就越来越大。CAS指令，在Intel CPU上称为CMPXCHG，作用是将指定内存地址的内容与所给的某个值相比，如果相等，则将其内容替换为所给的另一个值，这一系列操作是原子的，不可能被中断。基本上所有的同步机制，与信号量、Java中的synchronized等的实现最终都要用到CAS指令，即使锁无关的数据结构也离不开CAS指令。

2.load-link/store-conditional(LL/SC):它们是在多线程的环境下实现多线程同步的一对指令。Load-link返回一个存储器位置的当前值；跟在其后的store-conditional如果对同一存储器地址进行操作，那么将会做如下判定：如果从那条load-link指令开始起没有对该地址用store-conditional做过更新，那么一个新的值将会被写入该地址；否则：更新将会失败，使从load-link所读取的值被恢复。他们结合起来实现了一个lock-free 原子的read-modify-write操作。

一.VEX基本数据类型：

/* Always 8 bits. */
typedef  unsigned char   UChar;
typedef    signed char   Char;
typedef           char   HChar; /* signfulness depends on host */
                                /* Only to be used for printf etc
                                   format strings */

/* Always 16 bits. */
typedef  unsigned short  UShort;
typedef    signed short  Short;

/* Always 32 bits. */
typedef  unsigned int    UInt;
typedef    signed int    Int;

/* Always 64 bits. */
typedef  unsigned long long int   ULong;
typedef    signed long long int   Long;

/* Always 128 bits. */
typedef  UInt  U128[4];

/* Always 256 bits. */
typedef  UInt  U256[8];

//集中所有128位的vector，记作v128

typedef
   union {
      UChar  w8[16];
      UShort w16[8];
      UInt   w32[4];
      ULong  w64[2];
   }
   V128;

     static inline函数toBool,tochar,toHchar,toUchar,toUshort,toShort分别把Int型变量转换成to后面的类型，toUInt把long型变量转换成UInt。

      不同的处理器的架构不同，host的字长（32位或64位）不一样，要先搞清楚字长，否则会导致编译错误。这里预编译了x86_64, i386,powerpc,powerpc_64,arm,AIX(64位和非64位)，s390x,mips这9种不同的架构，分别定义了其VEX_HOST_WORDSIZE的大小（4或8）和VEX_REGPARM(_n)（？？暂时不知到这是什么）。 Ptr_to_ULong 和ULong_to_Ptr函数的功能是 cast pointers to and from 64-bit integers(在不考虑host字长的情况下) ,知道host字长写这些函数会很方便。

二.VEX IR结构介绍：

VEX IR是一种隔离不同架构的中间表达式而不是一种语言，它更像是编译器运行的IR。它有一定的结构：

code block：

       代码被分解成多个小的代码块（“superblock”，type：IRSB）。IRSB是单入口多出口的，IRSB里包含3个内容：1.a type environment，表明IRSB中每个临时变量的类型；2.a list of statement；3.a jump that exits from the end the IRSB。

statement and expression：

         statement（type:IRStmt）表示有side-effects的操作，例如  guest register writes, stores, and assignments to temporaries.expression(type:IRExpr)表示没有side-effects的操作，这些操作可以包含子表达式和表达式树，例如 (3 + (4 * load(addr1))。

guest state 的存储：

        guest state包括guest register和guest machine,VEX库将他们存储在一个默认的内存块。要对他们进行操作，必须用“Get”将guest state读到临时变量，用“Put”写回到guest state。

关于guest state和IR的例子可参考论文《Valgrind: A Framework for Heavyweight Dynamic Binary Instrumentation》3.6.

No need for deallocations：

           当translation完成时，VEX的机制将自动回收allocated的memory。

1.statement种类定义：

/*标志META的tag不代表代码，而是关于代码的额外信息。删除这些表达式不影响代码的功能性行为，但是基于IR的instrument代码的工具需要这样的statement。*/

typedef
   enum {
      Ist_NoOp=0x19000,
      Ist_IMark,     /* META */
      Ist_AbiHint,   /* META */
      Ist_Put,
      Ist_PutI,
      Ist_WrTmp,
      Ist_Store,
      Ist_CAS,
      Ist_LLSC,
      Ist_Dirty,
      Ist_MBE,       /* META (maybe) */
      Ist_Exit
   }
   IRStmtTag;

/*下面的IRStat结构体里有一个数据成员IRStmtTag tag和一个共用体（共用提中罗列了总共的12种statement，每次只能用到一种staement）*/

typedef
   struct _IRStmt {
      IRStmtTag tag;
      union {

 struct {
     } NoOp;//一般是IR优化的结果，可忽略。ppIRStmt output: IR-NoOp。

/*一条指令可转化为多条IR，要对每条指令的IR区分，IMark标志为每条机器指令的起始。

ppIRStmt output: ------ IMark(<addr>, <len>, <delta>) ------,
                         eg. ------ IMark(0x4000792, 5, 0) ------,

addr和len分别代表被转化的机器指令的地址和长度，delta：For x86, amd64, ppc32,ppc64 and arm, the delta value is zero.  For Thumb instructions, the delta value is one.
*/

 struct {
            Addr64 addr;   /* instruction address */
            Int    len;    /* instruction length */
            UChar  delta;  /* addr = program counter as encoded in guest state
                                     - delta */
           } IMark;

/*ABI（应用二进制接口，机器码层的接口，是二进制代码之间的调用规则）。这里的AbiHint指示地址空间的一个给定chunk（[base .. base+len-1]）成为undefined。

ppIRStmt output: ====== AbiHint(<base>, <len>, <nia>) ======
                         eg. ====== AbiHint(t1, 16, t2) ======

base是chunk基址，len是长度，nia是下一条指令的地址

*/

 struct {
            IRExpr* base;     /* Start  of undefined chunk */
            Int     len;      /* Length of undefined chunk */
            IRExpr* nia;      /* Address of next (guest) insn */
           } AbiHint;

//Put是寄存器的写操作，写的地址在寄存器中的偏移量固定。ppIRStmt output: PUT(<offset>) = <data>, eg. PUT(60) = t1

 struct {
            Int     offset;   /* Offset into the guest state */
            IRExpr* data;     /* The value to write */
           } Put;

/*PutI也是寄存器的写操作，偏移量不固定 。详细描述见见GetI。ppIRStmt output: PUTI<descr>[<ix>,<bias>] = <data>,
                         eg. PUTI(64:8xF64)[t5,0] = t1

*/

struct {
            IRPutI* details;
          } PutI;

//临时变量赋值。ppIRStmt output: t<tmp> = <data>, eg. t1 = 3

struct {
            IRTemp  tmp;   /* Temporary  (LHS of assignment) */
            IRExpr* data;  /* Expression (RHS of assignment) */
          } WrTmp;

//写memory。 ppIRStmt output: ST<end>(<addr>) = <data>, eg. STle(t1) = t2

struct {
            IREndness end;    /* Endianness of the store */
            IRExpr*   addr;   /* store address */
            IRExpr*   data;   /* value to write */
          } Store;

/*原子的比较和交换（compare-and-swap）操作，语义在IRCAs中定义。

 ppIRStmt output:
               t<tmp> = CAS<end>(<addr> :: <expected> -> <new>)
            eg
               t1 = CASle(t2 :: t3->Add32(t3,1))
               which denotes a 32-bit atomic increment
               of a value at address t2

*/

 struct {
            IRCAS* details;
          } CAS;

/*如果stroedata是NULL，那么这就是一个 Load-Linked操作：从memory加载数据。result = Load-Linked(addr, end)，转换后的数据类型由result决定（I32，I64等）。

eg ppIRStmt output:

               result = ( ST<end>-Cond(<addr>) = <storedata> )
               eg t3 = ( STbe-Cond(t1, t2) )

 ppIRStmt output:

               result = LD<end>-Linked(<addr>), eg. LDbe-Linked(t1)

如果stroedata不是NULL，那么就是一个Store-Conditional。如果address之前loged reservation，那么操作就会fail，result为0，否则result为1。转化后的类型是storedata的类型，result是Ity_I1类型。

eg ppIRStmt output:

               result = ( ST<end>-Cond(<addr>) = <storedata> )
               eg t3 = ( STbe-Cond(t1, t2) )

*/

 struct {
            IREndness end;
            IRTemp    result;
            IRExpr*   addr;
            IRExpr*   storedata; /* NULL => LL, non-NULL => SC */
          } LLSC;

/*调用一个具有side-efdfects的C函数（ie. is "dirty"）

 ppIRStmt output:
               t<tmp> = DIRTY <guard> <effects>
                  ::: <callee>(<args>)
            eg.
               t1 = DIRTY t27 RdFX-gst(16,4) RdFX-gst(60,4)
                     ::: foo{0x380035f4}(t2)

*/  
 struct {
            IRDirty* details;
           } Dirty;

/*内存总线的事件：a fence, or acquisition/release of the hardware bus lock.

ppIRStmt output: MBusEvent-Fence,
                             MBusEvent-BusLock, MBusEvent-BusUnlock.
*/

 struct {
            IRMBusEvent event;
           } MBE;

/*从IRSB的退出条件。

ppIRStmt output: if (<guard>) goto {<jk>} <dst>
                         eg. if (t69) goto {Boring} 0x4000AAA:I32

*/

 struct {
            IRExpr*    guard;    /* Conditional expression */
            IRConst*   dst;      /* Jump target (constant only) */
            IRJumpKind jk;       /* Jump kind */
            Int        offsIP;   /* Guest state offset for IP */
          } Exit;
      } Ist;
   }
   IRStmt;

2.expression种类定义：

typedef struct _IRQop   IRQop;   /* forward declaration */
typedef struct _IRTriop IRTriop; /* forward declaration */

typedef
   enum {
      Iex_Binder=0x15000,
      Iex_Get,
      Iex_GetI,
      Iex_RdTmp,
      Iex_Qop,
      Iex_Triop,
      Iex_Binop,
      Iex_Unop,
      Iex_Load,
      Iex_Const,
      Iex_Mux0X,
      Iex_CCall
   }
   IRExprTag;

/*expression stored as a tagged union.‘tag’标识了expression的种类。‘Iex’ is the union that holds the fields.如果有一个IRExpr e，e.tag=Iex_Load,则e是一个load expression，访问这块地址的方法是：e.Iex.Load.<fieldname>*/

typedef
   struct _IRExpr
   IRExpr;

struct _IRExpr {
   IRExprTag tag;
   union {
      /* Used only in pattern matching within Vex.  Should not be seen
         outside of Vex. */
      struct {
         Int binder;
      } Binder;

      /* Read a guest register, at a fixed offset in the guest state.
         ppIRExpr output: GET:<ty>(<offset>), eg. GET:I32(0)
      */
      struct {
         Int    offset;    /* Offset into the guest state */
         IRType ty;        /* Type of the value being read */
      } Get;

      /* Read a guest register at a non-fixed offset in the guest
         state.  This allows circular indexing into parts of the guest
         state, which is essential for modelling situations where the
         identity of guest registers is not known until run time.  One
         example is the x87 FP register stack.

         The part of the guest state to be treated as a circular array
         is described in the IRRegArray 'descr' field.  It holds the
         offset of the first element in the array, the type of each
         element, and the number of elements.

         The array index is indicated rather indirectly, in a way
         which makes optimisation easy: as the sum of variable part
         (the 'ix' field) and a constant offset (the 'bias' field).

         Since the indexing is circular, the actual array index to use
         is computed as (ix + bias) % num-of-elems-in-the-array.

         Here's an example.  The description

            (96:8xF64)[t39,-7]

         describes an array of 8 F64-typed values, the
         guest-state-offset of the first being 96.  This array is
         being indexed at (t39 - 7) % 8.

         It is important to get the array size/type exactly correct
         since IR optimisation looks closely at such info in order to
         establish aliasing/non-aliasing between seperate GetI and
         PutI events, which is used to establish when they can be
         reordered, etc.  Putting incorrect info in will lead to
         obscure IR optimisation bugs.

            ppIRExpr output: GETI<descr>[<ix>,<bias]
                         eg. GETI(128:8xI8)[t1,0]
      */
      struct {
         IRRegArray* descr; /* Part of guest state treated as circular */
         IRExpr*     ix;    /* Variable part of index into array */
         Int         bias;  /* Constant offset part of index into array */
      } GetI;

      /* The value held by a temporary.
         ppIRExpr output: t<tmp>, eg. t1
      */
      struct {
         IRTemp tmp;       /* The temporary number */
      } RdTmp;

      /* A quarternary operation.
         ppIRExpr output: <op>(<arg1>, <arg2>, <arg3>, <arg4>),
                      eg. MAddF64r32(t1, t2, t3, t4)
      */
      struct {
        IRQop* details;
      } Qop;

      /* A ternary operation.
         ppIRExpr output: <op>(<arg1>, <arg2>, <arg3>),
                      eg. MulF64(1, 2.0, 3.0)
      */
      struct {
        IRTriop* details;
      } Triop;

      /* A binary operation.
         ppIRExpr output: <op>(<arg1>, <arg2>), eg. Add32(t1,t2)
      */
      struct {
         IROp op;          /* op-code   */
         IRExpr* arg1;     /* operand 1 */
         IRExpr* arg2;     /* operand 2 */
      } Binop;

      /* A unary operation.
         ppIRExpr output: <op>(<arg>), eg. Neg8(t1)
      */
      struct {
         IROp    op;       /* op-code */
         IRExpr* arg;      /* operand */
      } Unop;

      /* A load from memory -- a normal load, not a load-linked.
         Load-Linkeds (and Store-Conditionals) are instead represented
         by IRStmt.LLSC since Load-Linkeds have side effects and so
         are not semantically valid IRExpr's.
         ppIRExpr output: LD<end>:<ty>(<addr>), eg. LDle:I32(t1)
      */
      struct {
         IREndness end;    /* Endian-ness of the load */
         IRType    ty;     /* Type of the loaded value */
         IRExpr*   addr;   /* Address being loaded from */
      } Load;

      /* A constant-valued expression.
         ppIRExpr output: <con>, eg. 0x4:I32
      */
      struct {
         IRConst* con;     /* The constant itself */
      } Const;

      /* A call to a pure (no side-effects) helper C function.

         With the 'cee' field, 'name' is the function's name.  It is
         only used for pretty-printing purposes.  The address to call
         (host address, of course) is stored in the 'addr' field
         inside 'cee'.

         The 'args' field is a NULL-terminated array of arguments.
         The stated return IRType, and the implied argument types,
         must match that of the function being called well enough so
         that the back end can actually generate correct code for the
         call.

         The called function **must** satisfy the following:

         * no side effects -- must be a pure function, the result of
           which depends only on the passed parameters.

         * it may not look at, nor modify, any of the guest state
           since that would hide guest state transitions from
           instrumenters

         * it may not access guest memory, since that would hide
           guest memory transactions from the instrumenters

         * it must not assume that arguments are being evaluated in a
           particular order. The oder of evaluation is unspecified.

         This is restrictive, but makes the semantics clean, and does
         not interfere with IR optimisation.

         If you want to call a helper which can mess with guest state
         and/or memory, instead use Ist_Dirty.  This is a lot more
         flexible, but you have to give a bunch of details about what
         the helper does (and you better be telling the truth,
         otherwise any derived instrumentation will be wrong).  Also
         Ist_Dirty inhibits various IR optimisations and so can cause
         quite poor code to be generated.  Try to avoid it.

         ppIRExpr output: <cee>(<args>):<retty>
                      eg. foo{0x80489304}(t1, t2):I32
      */
      struct {
         IRCallee* cee;    /* Function to call. */
         IRType    retty;  /* Type of return value. */
         IRExpr**  args;   /* Vector of argument expressions. */
      }  CCall;

      /* A ternary if-then-else operator.  It returns expr0 if cond is
         zero, exprX otherwise.  Note that it is STRICT, ie. both
         expr0 and exprX are evaluated in all cases.

         ppIRExpr output: Mux0X(<cond>,<expr0>,<exprX>),
                         eg. Mux0X(t6,t7,t8)
      */
      struct {
         IRExpr* cond;     /* Condition */
         IRExpr* expr0;    /* True expression */
         IRExpr* exprX;    /* False expression */
      } Mux0X;
   } Iex;
};

未完待续～～～～