sewardj | c97096c | 2004-06-30 09:28:04 +0000 | [diff] [blame] | 1 | |
| 2 | /*---------------------------------------------------------------*/ |
| 3 | /*--- ---*/ |
| 4 | /*--- This file (isel_x86.c) is ---*/ |
| 5 | /*--- Copyright (c) 2004 OpenWorks LLP. All rights reserved. ---*/ |
| 6 | /*--- ---*/ |
| 7 | /*---------------------------------------------------------------*/ |
| 8 | |
| 9 | #include <stdio.h> |
| 10 | #include <malloc.h> |
| 11 | |
| 12 | #include "basictypes.h" |
| 13 | #include "ir_defs.h" |
| 14 | #include "host_regs.h" |
| 15 | #include "x86h_defs.h" |
| 16 | |
| 17 | |
| 18 | /*---------------------------------------------------------*/ |
| 19 | /*--- ISelEnv ---*/ |
| 20 | /*---------------------------------------------------------*/ |
| 21 | |
| 22 | /* This carries around: |
| 23 | |
| 24 | - A mapping from IRTemp to IRType, giving the type of any IRTemp we |
| 25 | might encounter. This is computed before insn selection starts, |
| 26 | and does not change. |
| 27 | |
| 28 | - A mapping from IRTemp to HReg. This tells the insn selector |
| 29 | which virtual register is associated with each IRTemp temporary. |
| 30 | This is computed before insn selection starts, and does not |
| 31 | change. We expect this mapping to map precisely the same set |
| 32 | of IRTemps as the type mapping does. |
| 33 | |
| 34 | - The code array, that is, the insns selected so far. |
| 35 | |
| 36 | - A counter, for generating new virtual registers. |
| 37 | |
| 38 | Note, this is all host-independent. |
| 39 | */ |
| 40 | |
| 41 | typedef |
| 42 | struct { |
| 43 | IRTemp ir_name; |
| 44 | HReg vreg; |
| 45 | } |
| 46 | VRegMaplet; |
| 47 | |
| 48 | typedef |
| 49 | struct { |
sewardj | 194d54a | 2004-07-03 19:08:18 +0000 | [diff] [blame] | 50 | IRTypeEnv* type_env; |
sewardj | c97096c | 2004-06-30 09:28:04 +0000 | [diff] [blame] | 51 | |
sewardj | 194d54a | 2004-07-03 19:08:18 +0000 | [diff] [blame] | 52 | VRegMaplet* vregmap; |
| 53 | Int n_vregmap; |
sewardj | c97096c | 2004-06-30 09:28:04 +0000 | [diff] [blame] | 54 | |
sewardj | 2cd80dc | 2004-07-02 15:20:40 +0000 | [diff] [blame] | 55 | HInstrArray* code; |
sewardj | c97096c | 2004-06-30 09:28:04 +0000 | [diff] [blame] | 56 | |
sewardj | 194d54a | 2004-07-03 19:08:18 +0000 | [diff] [blame] | 57 | Int vreg_ctr; |
sewardj | c97096c | 2004-06-30 09:28:04 +0000 | [diff] [blame] | 58 | } |
| 59 | ISelEnv; |
| 60 | |
| 61 | |
| 62 | static HReg lookupIRTemp ( ISelEnv* env, IRTemp tmp ) |
| 63 | { |
| 64 | Int i; |
| 65 | for (i = 0; i < env->n_vregmap; i++) |
| 66 | if (env->vregmap[i].ir_name == tmp) |
| 67 | return env->vregmap[i].vreg; |
| 68 | panic("lookupIRTemp"); |
| 69 | } |
| 70 | |
sewardj | 2cd80dc | 2004-07-02 15:20:40 +0000 | [diff] [blame] | 71 | static void addInstr ( ISelEnv* env, X86Instr* instr ) |
sewardj | c97096c | 2004-06-30 09:28:04 +0000 | [diff] [blame] | 72 | { |
sewardj | 2cd80dc | 2004-07-02 15:20:40 +0000 | [diff] [blame] | 73 | addHInstr(env->code, instr); |
sewardj | c97096c | 2004-06-30 09:28:04 +0000 | [diff] [blame] | 74 | ppX86Instr(stdout, instr); |
| 75 | printf("\n"); |
| 76 | } |
| 77 | |
| 78 | static HReg newVRegI ( ISelEnv* env ) |
| 79 | { |
sewardj | 194d54a | 2004-07-03 19:08:18 +0000 | [diff] [blame] | 80 | HReg reg = mkHReg(env->vreg_ctr, HRcInt, True/*virtual reg*/); |
| 81 | env->vreg_ctr++; |
sewardj | c97096c | 2004-06-30 09:28:04 +0000 | [diff] [blame] | 82 | return reg; |
| 83 | } |
| 84 | |
| 85 | |
| 86 | /*---------------------------------------------------------*/ |
| 87 | /*--- ISEL: Integer expressions ---*/ |
| 88 | /*---------------------------------------------------------*/ |
| 89 | |
sewardj | 66f2f79 | 2004-06-30 16:37:16 +0000 | [diff] [blame] | 90 | /* forwards ... */ |
| 91 | static X86RMI* iselIntExpr_RMI ( ISelEnv* env, IRExpr* e ); |
| 92 | |
| 93 | |
| 94 | static X86Instr* mk_MOV_RR ( HReg src, HReg dst ) |
| 95 | { |
| 96 | assert(hregClass(src) == HRcInt); |
| 97 | assert(hregClass(dst) == HRcInt); |
| 98 | return X86Instr_Alu32R(Xalu_MOV, X86RMI_Reg(src), dst); |
| 99 | } |
| 100 | |
| 101 | |
sewardj | c97096c | 2004-06-30 09:28:04 +0000 | [diff] [blame] | 102 | /* Select insns for an integer-typed expression, and add them to the |
| 103 | code list. Return a vreg holding the result. The vreg MUST NOT BE |
| 104 | MODIFIED. If you want to modify it, ask for a new vreg, copy it in |
| 105 | there, and modify the copy. The register allocator will do its |
| 106 | best to map both vregs to the same real register, so the copies |
| 107 | will often disappear later in the game. |
| 108 | */ |
sewardj | 66f2f79 | 2004-06-30 16:37:16 +0000 | [diff] [blame] | 109 | static HReg iselIntExpr_R ( ISelEnv* env, IRExpr* e ) |
sewardj | c97096c | 2004-06-30 09:28:04 +0000 | [diff] [blame] | 110 | { |
| 111 | assert(e); |
| 112 | assert(typeOfIRExpr(env->type_env,e) == Ity_I32); |
| 113 | |
| 114 | switch (e->tag) { |
| 115 | |
| 116 | case Iex_Tmp: |
| 117 | return lookupIRTemp(env, e->Iex.Tmp.tmp); |
| 118 | |
| 119 | case Iex_Binop: |
sewardj | 66f2f79 | 2004-06-30 16:37:16 +0000 | [diff] [blame] | 120 | /* Add32(x,y). For commutative ops we assume any literal |
| 121 | values are on the second operand. */ |
sewardj | c97096c | 2004-06-30 09:28:04 +0000 | [diff] [blame] | 122 | if (e->Iex.Binop.op == Iop_Add32) { |
sewardj | 66f2f79 | 2004-06-30 16:37:16 +0000 | [diff] [blame] | 123 | HReg dst = newVRegI(env); |
| 124 | HReg reg = iselIntExpr_R(env, e->Iex.Binop.arg1); |
| 125 | X86RMI* rmi = iselIntExpr_RMI(env, e->Iex.Binop.arg2); |
| 126 | addInstr(env, mk_MOV_RR(reg,dst)); |
| 127 | addInstr(env, X86Instr_Alu32R(Xalu_ADD, rmi, dst)); |
| 128 | return dst; |
sewardj | c97096c | 2004-06-30 09:28:04 +0000 | [diff] [blame] | 129 | } |
sewardj | 96efe57 | 2004-07-03 14:48:24 +0000 | [diff] [blame] | 130 | if (e->Iex.Binop.op == Iop_Shl32) { |
| 131 | HReg dst = newVRegI(env); |
| 132 | HReg regL = iselIntExpr_R(env, e->Iex.Binop.arg1); |
| 133 | HReg regR = iselIntExpr_R(env, e->Iex.Binop.arg2); |
| 134 | addInstr(env, mk_MOV_RR(regL,dst)); |
| 135 | addInstr(env, mk_MOV_RR(regR,hregX86_ECX())); |
| 136 | addInstr(env, X86Instr_Sh32(Xsh_SHL, 0/* %cl */, X86RM_Reg(dst))); |
| 137 | return dst; |
| 138 | } |
sewardj | c97096c | 2004-06-30 09:28:04 +0000 | [diff] [blame] | 139 | |
sewardj | 66f2f79 | 2004-06-30 16:37:16 +0000 | [diff] [blame] | 140 | #if 0 |
sewardj | c97096c | 2004-06-30 09:28:04 +0000 | [diff] [blame] | 141 | /* 32-bit literals */ |
| 142 | case Iex_Const: { |
| 143 | switch (e->Iex.Const.con->tag) { |
| 144 | case Ico_U32: { |
| 145 | HReg r = newVRegI(env); |
| 146 | addInstr(env, |
| 147 | X86Instr_Mov32(X86Operand_Imm(e->Iex.Const.con->Ico.U32), |
| 148 | X86Operand_Reg(r))); |
| 149 | return r; |
| 150 | } |
| 151 | default: break; |
| 152 | } |
| 153 | } |
sewardj | 66f2f79 | 2004-06-30 16:37:16 +0000 | [diff] [blame] | 154 | #endif |
sewardj | c97096c | 2004-06-30 09:28:04 +0000 | [diff] [blame] | 155 | |
| 156 | default: |
| 157 | break; |
| 158 | } /* switch (e->tag) */ |
| 159 | |
| 160 | /* We get here if no pattern matched. */ |
| 161 | ppIRExpr(stderr, e); |
| 162 | panic("iselExprI: cannot reduce tree"); |
| 163 | } |
| 164 | |
| 165 | |
sewardj | 66f2f79 | 2004-06-30 16:37:16 +0000 | [diff] [blame] | 166 | /*---------------------------------------------------------*/ |
| 167 | /*--- ISEL: Integer expression auxiliaries ---*/ |
| 168 | /*---------------------------------------------------------*/ |
| 169 | |
| 170 | /* Return an AMode which computes the value of the specified |
| 171 | expression, possibly also adding insns to the code list as a |
| 172 | result. |
sewardj | c97096c | 2004-06-30 09:28:04 +0000 | [diff] [blame] | 173 | */ |
sewardj | 66f2f79 | 2004-06-30 16:37:16 +0000 | [diff] [blame] | 174 | static X86AMode* iselIntExpr_AMode ( ISelEnv* env, IRExpr* e ) |
sewardj | c97096c | 2004-06-30 09:28:04 +0000 | [diff] [blame] | 175 | { |
| 176 | assert(e); |
| 177 | assert(typeOfIRExpr(env->type_env,e) == Ity_I32); |
| 178 | |
| 179 | /* Add32(expr1, Shl32(expr2, imm)) */ |
| 180 | if (e->tag == Iex_Binop |
| 181 | && e->Iex.Binop.op == Iop_Add32 |
| 182 | && e->Iex.Binop.arg2->tag == Iex_Binop |
| 183 | && e->Iex.Binop.arg2->Iex.Binop.op == Iop_Shl32 |
| 184 | && e->Iex.Binop.arg2->Iex.Binop.arg2->tag == Iex_Const |
| 185 | && e->Iex.Binop.arg2->Iex.Binop.arg2->Iex.Const.con->tag == Ico_U32) { |
| 186 | UInt shift = e->Iex.Binop.arg2->Iex.Binop.arg2->Iex.Const.con->Ico.U32; |
| 187 | if (shift == 2 || shift == 4 || shift == 8) { |
sewardj | 66f2f79 | 2004-06-30 16:37:16 +0000 | [diff] [blame] | 188 | HReg r1 = iselIntExpr_R(env, e->Iex.Binop.arg1); |
| 189 | HReg r2 = iselIntExpr_R(env, e->Iex.Binop.arg2->Iex.Binop.arg1 ); |
sewardj | c97096c | 2004-06-30 09:28:04 +0000 | [diff] [blame] | 190 | return X86AMode_IRRS(0, r1, r2, shift); |
| 191 | } |
| 192 | } |
| 193 | |
| 194 | /* Add32(expr,i) */ |
| 195 | if (e->tag == Iex_Binop |
| 196 | && e->Iex.Binop.op == Iop_Add32 |
| 197 | && e->Iex.Binop.arg2->tag == Iex_Const |
| 198 | && e->Iex.Binop.arg2->Iex.Const.con->tag == Ico_U32) { |
sewardj | 66f2f79 | 2004-06-30 16:37:16 +0000 | [diff] [blame] | 199 | HReg r1 = iselIntExpr_R(env, e->Iex.Binop.arg1); |
sewardj | c97096c | 2004-06-30 09:28:04 +0000 | [diff] [blame] | 200 | return X86AMode_IR(r1, e->Iex.Binop.arg2->Iex.Const.con->Ico.U32); |
| 201 | } |
| 202 | |
| 203 | /* Doesn't match anything in particular. Generate it into |
| 204 | a register and use that. */ |
| 205 | { |
sewardj | 66f2f79 | 2004-06-30 16:37:16 +0000 | [diff] [blame] | 206 | HReg r1 = iselIntExpr_R(env, e); |
sewardj | c97096c | 2004-06-30 09:28:04 +0000 | [diff] [blame] | 207 | return X86AMode_IR(r1, 0); |
| 208 | } |
| 209 | } |
| 210 | |
| 211 | |
sewardj | 66f2f79 | 2004-06-30 16:37:16 +0000 | [diff] [blame] | 212 | /* Similarly, calculate an expression into an X86RMI operand. */ |
| 213 | |
| 214 | static X86RMI* iselIntExpr_RMI ( ISelEnv* env, IRExpr* e ) |
| 215 | { |
| 216 | assert(e); |
| 217 | assert(typeOfIRExpr(env->type_env,e) == Ity_I32); |
| 218 | |
| 219 | /* special case: immediate */ |
| 220 | if (e->tag == Iex_Const |
| 221 | && e->Iex.Const.con->tag == Ico_U32) { |
| 222 | return X86RMI_Imm(e->Iex.Const.con->Ico.U32); |
| 223 | } |
| 224 | |
| 225 | /* special case: load from memory */ |
| 226 | |
| 227 | /* default case: calculate into a register and return that */ |
| 228 | { |
| 229 | HReg r = iselIntExpr_R ( env, e ); |
| 230 | return X86RMI_Reg(r); |
| 231 | } |
| 232 | } |
| 233 | |
| 234 | |
| 235 | /* Calculate an expression into an X86RI operand. */ |
| 236 | |
| 237 | static X86RI* iselIntExpr_RI ( ISelEnv* env, IRExpr* e ) |
| 238 | { |
| 239 | assert(e); |
| 240 | assert(typeOfIRExpr(env->type_env,e) == Ity_I32); |
| 241 | |
| 242 | /* special case: immediate */ |
| 243 | if (e->tag == Iex_Const |
| 244 | && e->Iex.Const.con->tag == Ico_U32) { |
| 245 | return X86RI_Imm(e->Iex.Const.con->Ico.U32); |
| 246 | } |
| 247 | |
| 248 | /* default case: calculate into a register and return that */ |
| 249 | { |
| 250 | HReg r = iselIntExpr_R ( env, e ); |
| 251 | return X86RI_Reg(r); |
| 252 | } |
| 253 | } |
| 254 | |
| 255 | |
sewardj | c97096c | 2004-06-30 09:28:04 +0000 | [diff] [blame] | 256 | /*---------------------------------------------------------*/ |
| 257 | /*--- ISEL: Statements ---*/ |
| 258 | /*---------------------------------------------------------*/ |
| 259 | |
| 260 | void iselStmt ( ISelEnv* env, IRStmt* stmt ) |
| 261 | { |
sewardj | 66f2f79 | 2004-06-30 16:37:16 +0000 | [diff] [blame] | 262 | fprintf(stdout, "-- "); |
| 263 | ppIRStmt(stdout, stmt); |
| 264 | fprintf(stdout, "\n"); |
| 265 | |
sewardj | c97096c | 2004-06-30 09:28:04 +0000 | [diff] [blame] | 266 | switch (stmt->tag) { |
| 267 | |
| 268 | case Ist_Put: |
| 269 | if (stmt->Ist.Put.size == 4) { |
sewardj | 66f2f79 | 2004-06-30 16:37:16 +0000 | [diff] [blame] | 270 | /* We're going to write to memory, so compute the |
| 271 | RHS into an X86RI. */ |
sewardj | 66f2f79 | 2004-06-30 16:37:16 +0000 | [diff] [blame] | 272 | X86RI* ri = iselIntExpr_RI(env, stmt->Ist.Put.expr); |
sewardj | c97096c | 2004-06-30 09:28:04 +0000 | [diff] [blame] | 273 | addInstr(env, |
sewardj | 66f2f79 | 2004-06-30 16:37:16 +0000 | [diff] [blame] | 274 | X86Instr_Alu32M( |
| 275 | Xalu_MOV, |
| 276 | ri, |
sewardj | 53f85a9 | 2004-07-02 13:45:17 +0000 | [diff] [blame] | 277 | X86AMode_IR(stmt->Ist.Put.offset,hregX86_EBP()) |
sewardj | 66f2f79 | 2004-06-30 16:37:16 +0000 | [diff] [blame] | 278 | )); |
sewardj | c97096c | 2004-06-30 09:28:04 +0000 | [diff] [blame] | 279 | return; |
| 280 | } |
| 281 | |
sewardj | 7945308 | 2004-07-02 17:29:14 +0000 | [diff] [blame] | 282 | case Ist_Tmp: { |
| 283 | IRTemp tmp = stmt->Ist.Tmp.tmp; |
| 284 | IRType ty = lookupIRTypeEnv(env->type_env, tmp); |
| 285 | if (ty == Ity_I32) { |
| 286 | X86RMI* rmi = iselIntExpr_RMI(env, stmt->Ist.Tmp.expr); |
| 287 | HReg dst = lookupIRTemp(env, tmp); |
| 288 | addInstr(env, |
| 289 | X86Instr_Alu32R(Xalu_MOV,rmi,dst)); |
| 290 | return; |
| 291 | } |
| 292 | |
| 293 | } |
| 294 | |
sewardj | c97096c | 2004-06-30 09:28:04 +0000 | [diff] [blame] | 295 | default: break; |
| 296 | } |
| 297 | ppIRStmt(stderr, stmt); |
| 298 | panic("iselStmt"); |
| 299 | } |
| 300 | |
| 301 | |
| 302 | /*---------------------------------------------------------*/ |
| 303 | /*--- ISEL: Basic block terminators (Nexts) ---*/ |
| 304 | /*---------------------------------------------------------*/ |
| 305 | |
| 306 | void iselNext ( ISelEnv* env, IRNext* next ) |
| 307 | { |
sewardj | 66f2f79 | 2004-06-30 16:37:16 +0000 | [diff] [blame] | 308 | fprintf(stdout, "-- "); |
| 309 | ppIRNext(stdout, next); |
| 310 | fprintf(stdout, "\n"); |
| 311 | |
sewardj | c97096c | 2004-06-30 09:28:04 +0000 | [diff] [blame] | 312 | switch (next->tag) { |
sewardj | 66f2f79 | 2004-06-30 16:37:16 +0000 | [diff] [blame] | 313 | case Inx_UJump: { |
sewardj | 66f2f79 | 2004-06-30 16:37:16 +0000 | [diff] [blame] | 314 | assert(next->Inx.UJump.dst->tag == Ico_U32); |
| 315 | addInstr(env, X86Instr_Alu32R( |
| 316 | Xalu_MOV, |
| 317 | X86RMI_Imm(next->Inx.UJump.dst->Ico.U32), |
sewardj | 53f85a9 | 2004-07-02 13:45:17 +0000 | [diff] [blame] | 318 | hregX86_EAX())); |
sewardj | 66f2f79 | 2004-06-30 16:37:16 +0000 | [diff] [blame] | 319 | addInstr(env, X86Instr_RET()); |
| 320 | return; |
| 321 | } |
| 322 | default: |
sewardj | c97096c | 2004-06-30 09:28:04 +0000 | [diff] [blame] | 323 | ppIRNext(stderr, next); |
| 324 | panic("iselNext"); |
| 325 | } |
| 326 | } |
| 327 | |
| 328 | |
| 329 | /*---------------------------------------------------------*/ |
| 330 | /*--- Insn selector top-level ---*/ |
| 331 | /*---------------------------------------------------------*/ |
| 332 | |
sewardj | 194d54a | 2004-07-03 19:08:18 +0000 | [diff] [blame] | 333 | /* Translate an entire BB to x86 code. */ |
| 334 | |
| 335 | HInstrArray* iselBB_X86Instr ( IRBB* bb ) |
sewardj | c97096c | 2004-06-30 09:28:04 +0000 | [diff] [blame] | 336 | { |
| 337 | Int i; |
| 338 | HReg hreg; |
| 339 | IRStmt* stmt; |
| 340 | |
| 341 | /* Make up an initial environment to use. */ |
| 342 | ISelEnv* env = malloc(sizeof(ISelEnv)); |
sewardj | 194d54a | 2004-07-03 19:08:18 +0000 | [diff] [blame] | 343 | env->vreg_ctr = 0; |
sewardj | c97096c | 2004-06-30 09:28:04 +0000 | [diff] [blame] | 344 | |
| 345 | /* Set up output code array. */ |
sewardj | 2cd80dc | 2004-07-02 15:20:40 +0000 | [diff] [blame] | 346 | env->code = newHInstrArray(); |
sewardj | c97096c | 2004-06-30 09:28:04 +0000 | [diff] [blame] | 347 | |
| 348 | /* Copy BB's type env. */ |
| 349 | env->type_env = bb->tyenv; |
| 350 | |
| 351 | /* Make up an IRTemp -> virtual HReg mapping. This doesn't |
| 352 | change as we go along. */ |
| 353 | env->n_vregmap = bb->tyenv->map_used; |
| 354 | env->vregmap = malloc(env->n_vregmap * sizeof(VRegMaplet)); |
| 355 | |
| 356 | /* For each IR temporary, allocate a suitably-kinded virtual |
| 357 | register. */ |
| 358 | for (i = 0; i < env->n_vregmap; i++) { |
| 359 | env->vregmap[i].ir_name = bb->tyenv->map[i].name; |
| 360 | switch (bb->tyenv->map[i].type) { |
| 361 | case Ity_I32: hreg = mkHReg(i, HRcInt, True); break; |
| 362 | default: panic("iselBB: IRTemp type"); |
| 363 | } |
| 364 | env->vregmap[i].vreg = hreg; |
| 365 | } |
sewardj | 194d54a | 2004-07-03 19:08:18 +0000 | [diff] [blame] | 366 | env->vreg_ctr = env->n_vregmap; |
sewardj | c97096c | 2004-06-30 09:28:04 +0000 | [diff] [blame] | 367 | |
| 368 | /* Ok, finally we can iterate over the statements. */ |
| 369 | for (stmt = bb->stmts; stmt; stmt=stmt->link) |
| 370 | iselStmt(env,stmt); |
| 371 | |
| 372 | iselNext(env,bb->next); |
sewardj | 2cd80dc | 2004-07-02 15:20:40 +0000 | [diff] [blame] | 373 | |
sewardj | 194d54a | 2004-07-03 19:08:18 +0000 | [diff] [blame] | 374 | /* record the number of vregs we used. */ |
| 375 | env->code->n_vregs = env->vreg_ctr; |
sewardj | 2cd80dc | 2004-07-02 15:20:40 +0000 | [diff] [blame] | 376 | return env->code; |
sewardj | c97096c | 2004-06-30 09:28:04 +0000 | [diff] [blame] | 377 | } |