isel_x86.c - platform/external/valgrind - Gitiles


 /*---------------------------------------------------------------*/
 /*---                                                         ---*/
 /*--- This file (isel_x86.c) is                               ---*/
 /*--- Copyright (c) 2004 OpenWorks LLP.  All rights reserved. ---*/
 /*---                                                         ---*/
 /*---------------------------------------------------------------*/

 #include <stdio.h>
 #include <malloc.h>

 #include "basictypes.h"
 #include "ir_defs.h"
 #include "host_regs.h"
 #include "x86h_defs.h"


 /*---------------------------------------------------------*/
 /*--- ISelEnv                                           ---*/
 /*---------------------------------------------------------*/

 /* This carries around:

    - A mapping from IRTemp to IRType, giving the type of any IRTemp we
      might encounter.  This is computed before insn selection starts,
      and does not change.

    - A mapping from IRTemp to HReg.  This tells the insn selector
      which virtual register is associated with each IRTemp temporary.
      This is computed before insn selection starts, and does not
      change.  We expect this mapping to map precisely the same set
      of IRTemps as the type mapping does.

    - The code array, that is, the insns selected so far.

    - A counter, for generating new virtual registers.

    Note, this is all host-independent.
 */

 typedef
    struct {
       IRTemp ir_name;
       HReg   vreg;
    }
    VRegMaplet;

 typedef
    struct {
       IRTypeEnv*   type_env;

       VRegMaplet*  vregmap;
       Int          n_vregmap;

       HInstrArray* code;

       Int          vreg_ctr;
    }
    ISelEnv;


 static HReg lookupIRTemp ( ISelEnv* env, IRTemp tmp )
 {
    Int i;
    for (i = 0; i < env->n_vregmap; i++)
       if (env->vregmap[i].ir_name == tmp)
          return env->vregmap[i].vreg;
    panic("lookupIRTemp");
 }

 static void addInstr ( ISelEnv* env, X86Instr* instr )
 {
    addHInstr(env->code, instr);
    ppX86Instr(stdout, instr);
    printf("\n");
 }

 static HReg newVRegI ( ISelEnv* env )
 {
    HReg reg = mkHReg(env->vreg_ctr, HRcInt, True/*virtual reg*/);
    env->vreg_ctr++;
    return reg;
 }


 /*---------------------------------------------------------*/
 /*--- ISEL: Integer expressions                         ---*/
 /*---------------------------------------------------------*/

 /* forwards ... */
 static X86RMI* iselIntExpr_RMI ( ISelEnv* env, IRExpr* e );


 static X86Instr* mk_MOV_RR ( HReg src, HReg dst )
 {
    assert(hregClass(src) == HRcInt);
    assert(hregClass(dst) == HRcInt);
    return X86Instr_Alu32R(Xalu_MOV, X86RMI_Reg(src), dst);
 }


 /* Select insns for an integer-typed expression, and add them to the
    code list.  Return a vreg holding the result.  The vreg MUST NOT BE
    MODIFIED.  If you want to modify it, ask for a new vreg, copy it in
    there, and modify the copy.  The register allocator will do its
    best to map both vregs to the same real register, so the copies
    will often disappear later in the game.
 */
 static HReg iselIntExpr_R ( ISelEnv* env, IRExpr* e )
 {
    assert(e);
    assert(typeOfIRExpr(env->type_env,e) == Ity_I32);

    switch (e->tag) {

    case Iex_Tmp:
    return lookupIRTemp(env, e->Iex.Tmp.tmp);

    case Iex_Binop:
       /* Add32(x,y).  For commutative ops we assume any literal
          values are on the second operand. */
       if (e->Iex.Binop.op == Iop_Add32) {
          HReg dst    = newVRegI(env);
          HReg reg    = iselIntExpr_R(env, e->Iex.Binop.arg1);
          X86RMI* rmi = iselIntExpr_RMI(env, e->Iex.Binop.arg2);
          addInstr(env, mk_MOV_RR(reg,dst));
          addInstr(env, X86Instr_Alu32R(Xalu_ADD, rmi, dst));
          return dst;
       }
       if (e->Iex.Binop.op == Iop_Shl32) {
          HReg dst    = newVRegI(env);
          HReg regL   = iselIntExpr_R(env, e->Iex.Binop.arg1);
          HReg regR   = iselIntExpr_R(env, e->Iex.Binop.arg2);
 	 addInstr(env, mk_MOV_RR(regL,dst));
 	 addInstr(env, mk_MOV_RR(regR,hregX86_ECX()));
 	 addInstr(env, X86Instr_Sh32(Xsh_SHL, 0/* %cl */, X86RM_Reg(dst)));
 	 return dst;
       }

 #if 0
    /* 32-bit literals */
    case Iex_Const: {
       switch (e->Iex.Const.con->tag) {
          case Ico_U32: {
             HReg r = newVRegI(env);
             addInstr(env,
                X86Instr_Mov32(X86Operand_Imm(e->Iex.Const.con->Ico.U32),
 			      X86Operand_Reg(r)));
             return r;
          }
          default: break;
       }
    }
 #endif

    default:
    break;
    } /* switch (e->tag) */

    /* We get here if no pattern matched. */
    ppIRExpr(stderr, e);
    panic("iselExprI: cannot reduce tree");
 }


 /*---------------------------------------------------------*/
 /*--- ISEL: Integer expression auxiliaries              ---*/
 /*---------------------------------------------------------*/

 /* Return an AMode which computes the value of the specified
    expression, possibly also adding insns to the code list as a
    result.
 */
 static X86AMode* iselIntExpr_AMode ( ISelEnv* env, IRExpr* e )
 {
    assert(e);
    assert(typeOfIRExpr(env->type_env,e) == Ity_I32);

    /* Add32(expr1, Shl32(expr2, imm)) */
    if (e->tag == Iex_Binop
        && e->Iex.Binop.op == Iop_Add32
        && e->Iex.Binop.arg2->tag == Iex_Binop
        && e->Iex.Binop.arg2->Iex.Binop.op == Iop_Shl32
        && e->Iex.Binop.arg2->Iex.Binop.arg2->tag == Iex_Const
        && e->Iex.Binop.arg2->Iex.Binop.arg2->Iex.Const.con->tag == Ico_U32) {
       UInt shift = e->Iex.Binop.arg2->Iex.Binop.arg2->Iex.Const.con->Ico.U32;
       if (shift == 2 || shift == 4 || shift == 8) {
          HReg r1 = iselIntExpr_R(env, e->Iex.Binop.arg1);
          HReg r2 = iselIntExpr_R(env, e->Iex.Binop.arg2->Iex.Binop.arg1 );
          return X86AMode_IRRS(0, r1, r2, shift);
       }
    }

    /* Add32(expr,i) */
    if (e->tag == Iex_Binop
        && e->Iex.Binop.op == Iop_Add32
        && e->Iex.Binop.arg2->tag == Iex_Const
        && e->Iex.Binop.arg2->Iex.Const.con->tag == Ico_U32) {
       HReg r1 = iselIntExpr_R(env,  e->Iex.Binop.arg1);
       return X86AMode_IR(r1, e->Iex.Binop.arg2->Iex.Const.con->Ico.U32);
    }

    /* Doesn't match anything in particular.  Generate it into
       a register and use that. */
    {
       HReg r1 = iselIntExpr_R(env, e);
       return X86AMode_IR(r1, 0);
    }
 }


 /* Similarly, calculate an expression into an X86RMI operand. */

 static X86RMI* iselIntExpr_RMI ( ISelEnv* env, IRExpr* e )
 {
    assert(e);
    assert(typeOfIRExpr(env->type_env,e) == Ity_I32);

    /* special case: immediate */
    if (e->tag == Iex_Const
        && e->Iex.Const.con->tag == Ico_U32) {
       return X86RMI_Imm(e->Iex.Const.con->Ico.U32);
    }

    /* special case: load from memory */

    /* default case: calculate into a register and return that */
    {
       HReg r = iselIntExpr_R ( env, e );
       return X86RMI_Reg(r);
    }
 }


 /* Calculate an expression into an X86RI operand. */

 static X86RI* iselIntExpr_RI ( ISelEnv* env, IRExpr* e )
 {
    assert(e);
    assert(typeOfIRExpr(env->type_env,e) == Ity_I32);

    /* special case: immediate */
    if (e->tag == Iex_Const
        && e->Iex.Const.con->tag == Ico_U32) {
       return X86RI_Imm(e->Iex.Const.con->Ico.U32);
    }

    /* default case: calculate into a register and return that */
    {
       HReg r = iselIntExpr_R ( env, e );
       return X86RI_Reg(r);
    }
 }


 /*---------------------------------------------------------*/
 /*--- ISEL: Statements                                  ---*/
 /*---------------------------------------------------------*/

 void iselStmt ( ISelEnv* env, IRStmt* stmt )
 {
    fprintf(stdout, "-- ");
    ppIRStmt(stdout, stmt);
    fprintf(stdout, "\n");

    switch (stmt->tag) {

    case Ist_Put:
      if (stmt->Ist.Put.size == 4) {
        /* We're going to write to memory, so compute the
 	  RHS into an X86RI. */
        X86RI* ri  = iselIntExpr_RI(env, stmt->Ist.Put.expr);
        addInstr(env,
 		X86Instr_Alu32M(
                    Xalu_MOV,
                    ri,
 		   X86AMode_IR(stmt->Ist.Put.offset,hregX86_EBP())
 	       ));
        return;
      }

    case Ist_Tmp: {
      IRTemp tmp = stmt->Ist.Tmp.tmp;
      IRType ty = lookupIRTypeEnv(env->type_env, tmp);
      if (ty == Ity_I32) {
        X86RMI* rmi = iselIntExpr_RMI(env, stmt->Ist.Tmp.expr);
        HReg dst = lookupIRTemp(env, tmp);
        addInstr(env,
 		X86Instr_Alu32R(Xalu_MOV,rmi,dst));
        return;
    }

   }

    default: break;
    }
    ppIRStmt(stderr, stmt);
    panic("iselStmt");
 }


 /*---------------------------------------------------------*/
 /*--- ISEL: Basic block terminators (Nexts)             ---*/
 /*---------------------------------------------------------*/

 void iselNext ( ISelEnv* env, IRNext* next )
 {
    fprintf(stdout, "-- ");
    ppIRNext(stdout, next);
    fprintf(stdout, "\n");

    switch (next->tag) {
    case Inx_UJump: {
       assert(next->Inx.UJump.dst->tag == Ico_U32);
       addInstr(env, X86Instr_Alu32R(
                        Xalu_MOV,
                        X86RMI_Imm(next->Inx.UJump.dst->Ico.U32),
                        hregX86_EAX()));
       addInstr(env, X86Instr_RET());
       return;
    }
    default:
       ppIRNext(stderr, next);
       panic("iselNext");
    }
 }


 /*---------------------------------------------------------*/
 /*--- Insn selector top-level                           ---*/
 /*---------------------------------------------------------*/

 /* Translate an entire BB to x86 code. */

 HInstrArray* iselBB_X86Instr ( IRBB* bb )
 {
    Int     i;
    HReg    hreg;
    IRStmt* stmt;

    /* Make up an initial environment to use. */
    ISelEnv* env = malloc(sizeof(ISelEnv));
    env->vreg_ctr = 0;

    /* Set up output code array. */
    env->code = newHInstrArray();

    /* Copy BB's type env. */
    env->type_env = bb->tyenv;

    /* Make up an IRTemp -> virtual HReg mapping.  This doesn't
       change as we go along. */
    env->n_vregmap = bb->tyenv->map_used;
    env->vregmap   = malloc(env->n_vregmap * sizeof(VRegMaplet));

    /* For each IR temporary, allocate a suitably-kinded virtual
       register. */
    for (i = 0; i < env->n_vregmap; i++) {
       env->vregmap[i].ir_name = bb->tyenv->map[i].name;
       switch (bb->tyenv->map[i].type) {
          case Ity_I32: hreg = mkHReg(i, HRcInt, True); break;
          default: panic("iselBB: IRTemp type");
       }
       env->vregmap[i].vreg = hreg;
    }
    env->vreg_ctr = env->n_vregmap;

    /* Ok, finally we can iterate over the statements. */
    for (stmt = bb->stmts; stmt; stmt=stmt->link)
       iselStmt(env,stmt);

    iselNext(env,bb->next);

    /* record the number of vregs we used. */
    env->code->n_vregs = env->vreg_ctr;
    return env->code;
 }

	/---------------------------------------------------------------/
	/--- ---/
	/--- This file (isel_x86.c) is ---/
	/--- Copyright (c) 2004 OpenWorks LLP. All rights reserved. ---/
	/--- ---/
	/---------------------------------------------------------------/

	#include <stdio.h>
	#include <malloc.h>

	#include "basictypes.h"
	#include "ir_defs.h"
	#include "host_regs.h"
	#include "x86h_defs.h"


	/---------------------------------------------------------/
	/--- ISelEnv ---/
	/---------------------------------------------------------/

	/* This carries around:

	- A mapping from IRTemp to IRType, giving the type of any IRTemp we
	might encounter. This is computed before insn selection starts,
	and does not change.

	- A mapping from IRTemp to HReg. This tells the insn selector
	which virtual register is associated with each IRTemp temporary.
	This is computed before insn selection starts, and does not
	change. We expect this mapping to map precisely the same set
	of IRTemps as the type mapping does.

	- The code array, that is, the insns selected so far.

	- A counter, for generating new virtual registers.

	Note, this is all host-independent.
	*/

	typedef
	struct {
	IRTemp ir_name;
	HReg vreg;
	}
	VRegMaplet;

	typedef
	struct {
	IRTypeEnv* type_env;

	VRegMaplet* vregmap;
	Int n_vregmap;

	HInstrArray* code;

	Int vreg_ctr;
	}
	ISelEnv;


	static HReg lookupIRTemp ( ISelEnv* env, IRTemp tmp )
	{
	Int i;
	for (i = 0; i < env->n_vregmap; i++)
	if (env->vregmap[i].ir_name == tmp)
	return env->vregmap[i].vreg;
	panic("lookupIRTemp");
	}

	static void addInstr ( ISelEnv* env, X86Instr* instr )
	{
	addHInstr(env->code, instr);
	ppX86Instr(stdout, instr);
	printf("\n");
	}

	static HReg newVRegI ( ISelEnv* env )
	{
	HReg reg = mkHReg(env->vreg_ctr, HRcInt, True/virtual reg/);
	env->vreg_ctr++;
	return reg;
	}


	/---------------------------------------------------------/
	/--- ISEL: Integer expressions ---/
	/---------------------------------------------------------/

	/* forwards ... */
	static X86RMI* iselIntExpr_RMI ( ISelEnv* env, IRExpr* e );


	static X86Instr* mk_MOV_RR ( HReg src, HReg dst )
	{
	assert(hregClass(src) == HRcInt);
	assert(hregClass(dst) == HRcInt);
	return X86Instr_Alu32R(Xalu_MOV, X86RMI_Reg(src), dst);
	}


	/* Select insns for an integer-typed expression, and add them to the
	code list. Return a vreg holding the result. The vreg MUST NOT BE
	MODIFIED. If you want to modify it, ask for a new vreg, copy it in
	there, and modify the copy. The register allocator will do its
	best to map both vregs to the same real register, so the copies
	will often disappear later in the game.
	*/
	static HReg iselIntExpr_R ( ISelEnv* env, IRExpr* e )
	{
	assert(e);
	assert(typeOfIRExpr(env->type_env,e) == Ity_I32);

	switch (e->tag) {

	case Iex_Tmp:
	return lookupIRTemp(env, e->Iex.Tmp.tmp);

	case Iex_Binop:
	/* Add32(x,y). For commutative ops we assume any literal
	values are on the second operand. */
	if (e->Iex.Binop.op == Iop_Add32) {
	HReg dst = newVRegI(env);
	HReg reg = iselIntExpr_R(env, e->Iex.Binop.arg1);
	X86RMI* rmi = iselIntExpr_RMI(env, e->Iex.Binop.arg2);
	addInstr(env, mk_MOV_RR(reg,dst));
	addInstr(env, X86Instr_Alu32R(Xalu_ADD, rmi, dst));
	return dst;
	}
	if (e->Iex.Binop.op == Iop_Shl32) {
	HReg dst = newVRegI(env);
	HReg regL = iselIntExpr_R(env, e->Iex.Binop.arg1);
	HReg regR = iselIntExpr_R(env, e->Iex.Binop.arg2);
	addInstr(env, mk_MOV_RR(regL,dst));
	addInstr(env, mk_MOV_RR(regR,hregX86_ECX()));
	addInstr(env, X86Instr_Sh32(Xsh_SHL, 0/* %cl */, X86RM_Reg(dst)));
	return dst;
	}

	#if 0
	/* 32-bit literals */
	case Iex_Const: {
	switch (e->Iex.Const.con->tag) {
	case Ico_U32: {
	HReg r = newVRegI(env);
	addInstr(env,
	X86Instr_Mov32(X86Operand_Imm(e->Iex.Const.con->Ico.U32),
	X86Operand_Reg(r)));
	return r;
	}
	default: break;
	}
	}
	#endif

	default:
	break;
	} /* switch (e->tag) */

	/* We get here if no pattern matched. */
	ppIRExpr(stderr, e);
	panic("iselExprI: cannot reduce tree");
	}


	/---------------------------------------------------------/
	/--- ISEL: Integer expression auxiliaries ---/
	/---------------------------------------------------------/

	/* Return an AMode which computes the value of the specified
	expression, possibly also adding insns to the code list as a
	result.
	*/
	static X86AMode* iselIntExpr_AMode ( ISelEnv* env, IRExpr* e )
	{
	assert(e);
	assert(typeOfIRExpr(env->type_env,e) == Ity_I32);

	/* Add32(expr1, Shl32(expr2, imm)) */
	if (e->tag == Iex_Binop
	&& e->Iex.Binop.op == Iop_Add32
	&& e->Iex.Binop.arg2->tag == Iex_Binop
	&& e->Iex.Binop.arg2->Iex.Binop.op == Iop_Shl32
	&& e->Iex.Binop.arg2->Iex.Binop.arg2->tag == Iex_Const
	&& e->Iex.Binop.arg2->Iex.Binop.arg2->Iex.Const.con->tag == Ico_U32) {
	UInt shift = e->Iex.Binop.arg2->Iex.Binop.arg2->Iex.Const.con->Ico.U32;
	if (shift == 2 \|\| shift == 4 \|\| shift == 8) {
	HReg r1 = iselIntExpr_R(env, e->Iex.Binop.arg1);
	HReg r2 = iselIntExpr_R(env, e->Iex.Binop.arg2->Iex.Binop.arg1 );
	return X86AMode_IRRS(0, r1, r2, shift);
	}
	}

	/* Add32(expr,i) */
	if (e->tag == Iex_Binop
	&& e->Iex.Binop.op == Iop_Add32
	&& e->Iex.Binop.arg2->tag == Iex_Const
	&& e->Iex.Binop.arg2->Iex.Const.con->tag == Ico_U32) {
	HReg r1 = iselIntExpr_R(env, e->Iex.Binop.arg1);
	return X86AMode_IR(r1, e->Iex.Binop.arg2->Iex.Const.con->Ico.U32);
	}

	/* Doesn't match anything in particular. Generate it into
	a register and use that. */
	{
	HReg r1 = iselIntExpr_R(env, e);
	return X86AMode_IR(r1, 0);
	}
	}


	/* Similarly, calculate an expression into an X86RMI operand. */

	static X86RMI* iselIntExpr_RMI ( ISelEnv* env, IRExpr* e )
	{
	assert(e);
	assert(typeOfIRExpr(env->type_env,e) == Ity_I32);

	/* special case: immediate */
	if (e->tag == Iex_Const
	&& e->Iex.Const.con->tag == Ico_U32) {
	return X86RMI_Imm(e->Iex.Const.con->Ico.U32);
	}

	/* special case: load from memory */

	/* default case: calculate into a register and return that */
	{
	HReg r = iselIntExpr_R ( env, e );
	return X86RMI_Reg(r);
	}
	}


	/* Calculate an expression into an X86RI operand. */

	static X86RI* iselIntExpr_RI ( ISelEnv* env, IRExpr* e )
	{
	assert(e);
	assert(typeOfIRExpr(env->type_env,e) == Ity_I32);

	/* special case: immediate */
	if (e->tag == Iex_Const
	&& e->Iex.Const.con->tag == Ico_U32) {
	return X86RI_Imm(e->Iex.Const.con->Ico.U32);
	}

	/* default case: calculate into a register and return that */
	{
	HReg r = iselIntExpr_R ( env, e );
	return X86RI_Reg(r);
	}
	}


	/---------------------------------------------------------/
	/--- ISEL: Statements ---/
	/---------------------------------------------------------/

	void iselStmt ( ISelEnv* env, IRStmt* stmt )
	{
	fprintf(stdout, "-- ");
	ppIRStmt(stdout, stmt);
	fprintf(stdout, "\n");

	switch (stmt->tag) {

	case Ist_Put:
	if (stmt->Ist.Put.size == 4) {
	/* We're going to write to memory, so compute the
	RHS into an X86RI. */
	X86RI* ri = iselIntExpr_RI(env, stmt->Ist.Put.expr);
	addInstr(env,
	X86Instr_Alu32M(
	Xalu_MOV,
	ri,
	X86AMode_IR(stmt->Ist.Put.offset,hregX86_EBP())
	));
	return;
	}

	case Ist_Tmp: {
	IRTemp tmp = stmt->Ist.Tmp.tmp;
	IRType ty = lookupIRTypeEnv(env->type_env, tmp);
	if (ty == Ity_I32) {
	X86RMI* rmi = iselIntExpr_RMI(env, stmt->Ist.Tmp.expr);
	HReg dst = lookupIRTemp(env, tmp);
	addInstr(env,
	X86Instr_Alu32R(Xalu_MOV,rmi,dst));
	return;
	}

	}

	default: break;
	}
	ppIRStmt(stderr, stmt);
	panic("iselStmt");
	}


	/---------------------------------------------------------/
	/--- ISEL: Basic block terminators (Nexts) ---/
	/---------------------------------------------------------/

	void iselNext ( ISelEnv* env, IRNext* next )
	{
	fprintf(stdout, "-- ");
	ppIRNext(stdout, next);
	fprintf(stdout, "\n");

	switch (next->tag) {
	case Inx_UJump: {
	assert(next->Inx.UJump.dst->tag == Ico_U32);
	addInstr(env, X86Instr_Alu32R(
	Xalu_MOV,
	X86RMI_Imm(next->Inx.UJump.dst->Ico.U32),
	hregX86_EAX()));
	addInstr(env, X86Instr_RET());
	return;
	}
	default:
	ppIRNext(stderr, next);
	panic("iselNext");
	}
	}


	/---------------------------------------------------------/
	/--- Insn selector top-level ---/
	/---------------------------------------------------------/

	/* Translate an entire BB to x86 code. */

	HInstrArray* iselBB_X86Instr ( IRBB* bb )
	{
	Int i;
	HReg hreg;
	IRStmt* stmt;

	/* Make up an initial environment to use. */
	ISelEnv* env = malloc(sizeof(ISelEnv));
	env->vreg_ctr = 0;

	/* Set up output code array. */
	env->code = newHInstrArray();

	/* Copy BB's type env. */
	env->type_env = bb->tyenv;

	/* Make up an IRTemp -> virtual HReg mapping. This doesn't
	change as we go along. */
	env->n_vregmap = bb->tyenv->map_used;
	env->vregmap = malloc(env->n_vregmap * sizeof(VRegMaplet));

	/* For each IR temporary, allocate a suitably-kinded virtual
	register. */
	for (i = 0; i < env->n_vregmap; i++) {
	env->vregmap[i].ir_name = bb->tyenv->map[i].name;
	switch (bb->tyenv->map[i].type) {
	case Ity_I32: hreg = mkHReg(i, HRcInt, True); break;
	default: panic("iselBB: IRTemp type");
	}
	env->vregmap[i].vreg = hreg;
	}
	env->vreg_ctr = env->n_vregmap;

	/* Ok, finally we can iterate over the statements. */
	for (stmt = bb->stmts; stmt; stmt=stmt->link)
	iselStmt(env,stmt);

	iselNext(env,bb->next);

	/* record the number of vregs we used. */
	env->code->n_vregs = env->vreg_ctr;
	return env->code;
	}