Source code: Assembler/x86/x86Assembler.java
1 // x86Assembler.java, created Mon Feb 5 23:23:19 2001 by joewhaley
2 // Copyright (C) 2001-3 John Whaley <jwhaley@alum.mit.edu>
3 // Licensed under the terms of the GNU LGPL; see COPYING for details.
4 package Assembler.x86;
5
6 import java.util.HashMap;
7 import java.util.Iterator;
8 import java.util.Map;
9
10 import Allocator.DefaultCodeAllocator;
11 import Allocator.CodeAllocator.x86CodeBuffer;
12 import Main.jq;
13 import Memory.CodeAddress;
14 import Util.Assert;
15 import Util.Strings;
16 import Util.Collections.LightRelation;
17 import Util.Collections.Relation;
18
19 // Referenced classes of package Assembler.x86:
20 // x86Constants, x86CodeBuffer, x86
21
22 /**
23 * x86Assembler
24 *
25 * @author John Whaley <jwhaley@alum.mit.edu>
26 * @version $Id: x86Assembler.java,v 1.16 2003/05/12 10:04:52 joewhaley Exp $
27 */
28 public class x86Assembler implements x86Constants {
29
30 static class PatchInfo {
31
32 int patchLocation, patchSize;
33
34 PatchInfo(int patchLocation, int patchSize) {
35 this.patchLocation = patchLocation;
36 this.patchSize = patchSize;
37 }
38
39 void patchTo(x86CodeBuffer mc, int target) {
40 if (patchSize == 4) {
41 int v = mc.get4_endian(patchLocation - 4);
42 Assert._assert(v == 0x44444444 || v == 0x55555555 || v == 0x66666666 || v == 0x77777777, "Location: "+Strings.hex(patchLocation-4)+" value: "+Strings.hex8(v));
43 mc.put4_endian(patchLocation - 4, target - patchLocation);
44 } else if (patchSize == 1) {
45 byte v = mc.get1(patchLocation - 1);
46 Assert._assert(v == 0);
47 Assert._assert(target - patchLocation <= 127);
48 Assert._assert(target - patchLocation >= -128);
49 mc.put1(patchLocation - 1, (byte)(target - patchLocation));
50 } else
51 Assert.TODO();
52 }
53
54 public String toString() {
55 return "loc:"+Strings.hex(patchLocation)+" size:"+patchSize;
56 }
57
58 }
59
60 static class AbsPatchInfo extends PatchInfo {
61
62 AbsPatchInfo(int patchLocation, int patchSize) {
63 super(patchLocation, patchSize);
64 }
65
66 void patchTo(x86CodeBuffer mc, int target) {
67 if (patchSize == 4) {
68 int v = mc.get4_endian(patchLocation - 4);
69 Assert._assert(v == 0x44444444 || v == 0x55555555 || v == 0x66666666 || v == 0x77777777, "Location: "+Strings.hex(patchLocation-4)+" value: "+Strings.hex8(v));
70 mc.put4_endian(patchLocation - 4, mc.getStartAddress().offset(target).to32BitValue());
71 } else
72 Assert.TODO();
73 }
74
75 public String toString() {
76 return "loc:"+Strings.hex(patchLocation)+" size:"+patchSize+" (abs)";
77 }
78
79 }
80
81 public x86CodeBuffer getCodeBuffer() {
82 if (!branches_to_patch.isEmpty())
83 System.out.println("Error: unresolved forward branches!");
84 return mc;
85 }
86 public int getCurrentOffset() { return mc.getCurrentOffset(); }
87 public CodeAddress getCurrentAddress() { return mc.getCurrentAddress(); }
88 public CodeAddress getStartAddress() { return mc.getStartAddress(); }
89 public void patch1(int offset, byte value) { mc.put1(offset, value); }
90 public void patch4_endian(int offset, int value) { mc.put4_endian(offset, value); }
91
92 public x86Assembler(int num_targets, int est_size, int offset, int alignment) {
93 mc = DefaultCodeAllocator.getCodeBuffer(est_size, offset, alignment);
94 if (TRACE) System.out.println("Assembler start address: "+mc.getCurrentAddress().stringRep());
95 branchtargetmap = new HashMap();
96 branches_to_patch = new LightRelation();
97 }
98
99 public boolean containsTarget(Object target) {
100 return branchtargetmap.containsKey(target);
101 }
102 // backward branches
103 public void recordBranchTarget(Object target) {
104 Assert._assert(ip == mc.getCurrentOffset());
105 branchtargetmap.put(target, new Integer(ip));
106 }
107 public int getBranchTarget(Object target) {
108 Integer i = (Integer)branchtargetmap.get(target);
109 if (i == null) {
110 Assert.UNREACHABLE("Invalid branch target: "+target+" offset "+getCurrentOffset());
111 }
112 return i.intValue();
113 }
114 public Map getBranchTargetMap() {
115 return branchtargetmap;
116 }
117
118 // forward branches
119 public void recordForwardBranch(int patchsize, Object target) {
120 if (TRACE) System.out.println("recording forward branch from "+Strings.hex(ip)+" (size "+patchsize+") to "+target);
121 branches_to_patch.add(target, new PatchInfo(ip, patchsize));
122 }
123 public void recordAbsoluteReference(int patchsize, Object target) {
124 if (TRACE) System.out.println("recording absolute reference from "+Strings.hex(ip)+" (size "+patchsize+") to "+target);
125 branches_to_patch.add(target, new AbsPatchInfo(ip, patchsize));
126 }
127 public void resolveForwardBranches(Object target) {
128 PatchInfo p;
129 Iterator it = branches_to_patch.getValues(target).iterator();
130 while (it.hasNext()) {
131 p = (PatchInfo)it.next();
132 if (TRACE) System.out.println("patching branch to "+target+" ("+p+") to point to "+Strings.hex(ip));
133 p.patchTo(mc, ip);
134 }
135 branches_to_patch.removeKey(target);
136 }
137
138 // dynamic patch section
139 public void startDynamicPatch(int size) {
140 if (jq.SMP) {
141 int end = ip+size;
142 int mask = CACHE_LINE_SIZE-1;
143 while ((ip & mask) != (end & mask))
144 emit1(x86.NOP);
145 }
146 dynPatchStart = ip;
147 dynPatchSize = size;
148 }
149 public void endDynamicPatch() {
150 Assert._assert(ip <= dynPatchStart + dynPatchSize);
151 while (ip < dynPatchStart + dynPatchSize)
152 emit1(x86.NOP);
153 dynPatchSize = 0;
154 }
155
156 // prefix
157 public void emitprefix(byte prefix) {
158 mc.add1(prefix);
159 ++ip;
160 }
161
162 // special case instructions
163 public void emitPUSH_i(int imm) {
164 if (fits(imm, 8))
165 ip += x86.PUSH_i8.emit1_Imm8(mc, imm);
166 else
167 ip += x86.PUSH_i32.emit1_Imm32(mc, imm);
168 }
169 public void emit2_SHIFT_Mem_Imm8(x86 x, int off, int base, byte imm) {
170 if (base == ESP) {
171 if (off == 0) {
172 if (imm == 1)
173 ip += x.emit2_Once_SIB_EA(mc, ESP, ESP, SCALE_1);
174 else
175 ip += x.emit2_SIB_EA_Imm8(mc, ESP, ESP, SCALE_1, imm);
176 } else if (fits_signed(off, 8)) {
177 if (imm == 1)
178 ip += x.emit2_Once_SIB_DISP8(mc, ESP, ESP, SCALE_1, (byte)off);
179 else
180 ip += x.emit2_SIB_DISP8_Imm8(mc, ESP, ESP, SCALE_1, (byte)off, imm);
181 } else {
182 if (imm == 1)
183 ip += x.emit2_Once_SIB_DISP32(mc, ESP, ESP, SCALE_1, off);
184 else
185 ip += x.emit2_SIB_DISP32_Imm8(mc, ESP, ESP, SCALE_1, off, imm);
186 }
187 } else if (off == 0 && base != EBP) {
188 if (imm == 1)
189 ip += x.emit2_Once_EA(mc, base);
190 else
191 ip += x.emit2_EA_Imm8(mc, base, imm);
192 } else if (fits_signed(off, 8)) {
193 if (imm == 1)
194 ip += x.emit2_Once_DISP8(mc, (byte)off, base);
195 else
196 ip += x.emit2_DISP8_Imm8(mc, (byte)off, base, imm);
197 } else {
198 if (imm == 1)
199 ip += x.emit2_Once_DISP32(mc, off, base);
200 else
201 ip += x.emit2_DISP32_Imm8(mc, off, base, imm);
202 }
203 }
204
205 public void emit2_SHIFT_Reg_Imm8(x86 x, int r1, byte imm) {
206 if (imm == 1)
207 ip += x.emit2_Once_Reg(mc, r1);
208 else
209 ip += x.emit2_Reg_Imm8(mc, r1, imm);
210 }
211
212 // swap the order, because it is confusing.
213 public void emitSHLD_r_r_rc(int r1, int r2) {
214 ip += x86.SHLD_r_r_rc.emit3_Reg_Reg(mc, r2, r1);
215 }
216
217 // swap the order, because it is confusing.
218 public void emitSHRD_r_r_rc(int r1, int r2) {
219 ip += x86.SHRD_r_r_rc.emit3_Reg_Reg(mc, r2, r1);
220 }
221
222 // short
223 public void emitShort_Reg(x86 x, int r1) {
224 ip += x.emitShort_Reg(mc, r1);
225 }
226 public void emitShort_Reg_Imm(x86 x, int r1, int imm) {
227 ip += x.emitShort_Reg_Imm32(mc, r1, imm);
228 }
229
230 // length 1
231 public void emit1(x86 x) {
232 ip += x.emit1(mc);
233 }
234 public void emit1_Imm8(x86 x, byte imm) {
235 ip += x.emit1_Imm8(mc, imm);
236 }
237 public void emit1_Imm16(x86 x, char imm) {
238 ip += x.emit1_Imm16(mc, imm);
239 }
240 public void emit1_Imm32(x86 x, int imm) {
241 ip += x.emit1_Imm32(mc, imm);
242 }
243
244 // length 2
245 public void emit2(x86 x) {
246 ip += x.emit2(mc);
247 }
248 public void emit2_FPReg(x86 x, int r) {
249 ip += x.emit2_FPReg(mc, r);
250 }
251 public void emit2_Mem(x86 x, int imm) {
252 ip += x.emit2_Abs32(mc, imm);
253 }
254 public void emit2_Mem(x86 x, int off, int base) {
255 if (base == ESP) {
256 if (off == 0)
257 ip += x.emit2_SIB_EA(mc, ESP, ESP, SCALE_1);
258 else if (fits_signed(off, 8))
259 ip += x.emit2_SIB_DISP8(mc, ESP, ESP, SCALE_1, (byte)off);
260 else
261 ip += x.emit2_SIB_DISP32(mc, ESP, ESP, SCALE_1, off);
262 } else if (off == 0 && base != EBP)
263 ip += x.emit2_EA(mc, base);
264 else if (fits_signed(off, 8))
265 ip += x.emit2_DISP8(mc, (byte)off, base);
266 else
267 ip += x.emit2_DISP32(mc, off, base);
268 }
269 public void emit2_Mem(x86 x, int base, int ind, int scale, int off) {
270 Assert._assert(ind != ESP);
271 Assert._assert(base != ESP);
272 if (off == 0)
273 ip += x.emit2_SIB_EA(mc, base, ind, scale);
274 else if (fits_signed(off, 8))
275 ip += x.emit2_SIB_DISP8(mc, base, ind, scale, (byte)off);
276 else
277 ip += x.emit2_SIB_DISP32(mc, base, ind, scale, off);
278 }
279 public void emit2_Mem_Imm(x86 x, int off, int base, int imm) {
280 if (base == ESP) {
281 if (off == 0)
282 ip += x.emit2_SIB_EA_Imm32(mc, ESP, ESP, SCALE_1, imm);
283 else if (fits_signed(off, 8))
284 ip += x.emit2_SIB_DISP8_Imm32(mc, ESP, ESP, SCALE_1, (byte)off, imm);
285 else
286 ip += x.emit2_SIB_DISP32_Imm32(mc, ESP, ESP, SCALE_1, off, imm);
287 } else if (off == 0 && base != EBP)
288 ip += x.emit2_EA_Imm32(mc, base, imm);
289 else if (fits_signed(off, 8))
290 ip += x.emit2_DISP8_Imm32(mc, (byte)off, base, imm);
291 else
292 ip += x.emit2_DISP32_Imm32(mc, off, base, imm);
293 }
294 public void emit2_Reg(x86 x, int r1) {
295 ip += x.emit2_Reg(mc, r1);
296 }
297 public void emit2_Reg_Mem(x86 x, int r1, int addr) {
298 ip += x.emit2_Reg_Abs32(mc, r1, addr);
299 }
300 public void emit2_Reg_Mem(x86 x, int r1, int off, int base) {
301 if (base == ESP) {
302 if (off == 0)
303 ip += x.emit2_Reg_SIB_EA(mc, r1, ESP, ESP, SCALE_1);
304 else if (fits_signed(off, 8))
305 ip += x.emit2_Reg_SIB_DISP8(mc, r1, ESP, ESP, SCALE_1, (byte)off);
306 else
307 ip += x.emit2_Reg_SIB_DISP32(mc, r1, ESP, ESP, SCALE_1, off);
308 } else if (off == 0 && base != EBP)
309 ip += x.emit2_Reg_EA(mc, r1, base);
310 else if (fits_signed(off, 8))
311 ip += x.emit2_Reg_DISP8(mc, r1, (byte)off, base);
312 else
313 ip += x.emit2_Reg_DISP32(mc, r1, off, base);
314 }
315 public void emit2_Reg_Mem(x86 x, int r1, int base, int ind, int scale, int off) {
316 if (off == 0)
317 ip += x.emit2_Reg_SIB_EA(mc, r1, base, ind, scale);
318 else if (fits_signed(off, 8))
319 ip += x.emit2_Reg_SIB_DISP8(mc, r1, base, ind, scale, (byte)off);
320 else
321 ip += x.emit2_Reg_SIB_DISP32(mc, r1, base, ind, scale, off);
322 }
323 public void emit2_Reg_Reg(x86 x, int r1, int r2) {
324 ip += x.emit2_Reg_Reg(mc, r1, r2);
325 }
326
327 // length 3
328 public void emit3_Reg_Reg(x86 x, int r1, int r2) {
329 ip += x.emit3_Reg_Reg(mc, r1, r2);
330 }
331 public void emit3_Reg_Mem(x86 x, int r1, int addr) {
332 ip += x.emit3_Reg_Abs32(mc, r1, addr);
333 }
334 public void emit3_Reg_Mem(x86 x, int r1, int off, int base) {
335 if (base == ESP) {
336 if (off == 0)
337 ip += x.emit3_Reg_SIB_EA(mc, r1, ESP, ESP, SCALE_1);
338 else if (fits_signed(off, 8))
339 ip += x.emit3_Reg_SIB_DISP8(mc, r1, ESP, ESP, SCALE_1, (byte)off);
340 else
341 ip += x.emit3_Reg_SIB_DISP32(mc, r1, ESP, ESP, SCALE_1, off);
342 } else if (off == 0 && base != EBP)
343 ip += x.emit3_Reg_EA(mc, r1, base);
344 else if (fits_signed(off, 8))
345 ip += x.emit3_Reg_DISP8(mc, r1, (byte)off, base);
346 else
347 ip += x.emit3_Reg_DISP32(mc, r1, off, base);
348 }
349 public void emit3_Reg_Mem(x86 x, int r1, int base, int ind, int mult, int off) {
350 if (off == 0)
351 ip += x.emit3_Reg_SIB_EA(mc, r1, base, ind, mult);
352 else if (fits_signed(off, 8))
353 ip += x.emit3_Reg_SIB_DISP8(mc, r1, base, ind, mult, (byte)off);
354 else
355 ip += x.emit3_Reg_SIB_DISP32(mc, r1, base, ind, mult, off);
356 }
357
358 // arithmetic (with special EAX, Imm forms and 8-bit sign-extended immediates)
359 public void emitARITH_Mem_Imm(x86 x, int off, int base, int imm) {
360 if (base == ESP) {
361 if (off == 0) {
362 if (x != x86.TEST_r_i32 && fits_signed(imm, 8))
363 ip += x.emit2_SIB_EA_SEImm8(mc, ESP, ESP, SCALE_1, (byte)imm);
364 else
365 ip += x.emit2_SIB_EA_Imm32(mc, ESP, ESP, SCALE_1, imm);
366 } else if (fits_signed(off, 8)) {
367 if (x != x86.TEST_r_i32 && fits_signed(imm, 8))
368 ip += x.emit2_SIB_DISP8_SEImm8(mc, ESP, ESP, SCALE_1, (byte)off, (byte)imm);
369 else
370 ip += x.emit2_SIB_DISP8_Imm32(mc, ESP, ESP, SCALE_1, (byte)off, imm);
371 } else {
372 if (x != x86.TEST_r_i32 && fits_signed(imm, 8))
373 ip += x.emit2_SIB_DISP32_SEImm8(mc, ESP, ESP, SCALE_1, off, (byte)imm);
374 else
375 ip += x.emit2_SIB_DISP32_Imm32(mc, ESP, ESP, SCALE_1, off, imm);
376 }
377 } else if (off == 0 && base != 5) {
378 if (x != x86.TEST_r_i32 && fits_signed(imm, 8))
379 ip += x.emit2_EA_SEImm8(mc, base, (byte)imm);
380 else
381 ip += x.emit2_EA_Imm32(mc, base, imm);
382 } else if (fits_signed(off, 8)) {
383 if (x != x86.TEST_r_i32 && fits_signed(imm, 8))
384 ip += x.emit2_DISP8_SEImm8(mc, (byte)off, base, (byte)imm);
385 else
386 ip += x.emit2_DISP8_Imm32(mc, (byte)off, base, imm);
387 } else {
388 if (x != x86.TEST_r_i32 && fits_signed(imm, 8))
389 ip += x.emit2_DISP32_SEImm8(mc, off, base, (byte)imm);
390 else
391 ip += x.emit2_DISP32_Imm32(mc, off, base, imm);
392 }
393 }
394 public void emitARITH_Reg_Imm(x86 x, int r1, int imm) {
395 //if (r1 == EAX)
396 // ip += x.emit1_RA_Imm32(mc, imm);
397 //else
398 if (x != x86.TEST_r_i32 && fits_signed(imm, 8))
399 ip += x.emit2_Reg_SEImm8(mc, r1, (byte)imm);
400 else
401 ip += x.emit2_Reg_Imm32(mc, r1, imm);
402 }
403 public void emitARITH_Reg_Reg(x86 x, int r1, int r2) {
404 ip += x.emit2_Reg_Reg(mc, r1, r2);
405 }
406 public void emitARITH_Reg_Mem(x86 x, int r1, int off, int base) {
407 if (base == ESP) {
408 if (off == 0)
409 ip += x.emit2_Reg_SIB_EA(mc, r1, ESP, ESP, SCALE_1);
410 else if (fits_signed(off, 8))
411 ip += x.emit2_Reg_SIB_DISP8(mc, r1, ESP, ESP, SCALE_1, (byte)off);
412 else
413 ip += x.emit2_Reg_SIB_DISP32(mc, r1, ESP, ESP, SCALE_1, off);
414 } else if (off == 0 && base != 5)
415 ip += x.emit2_Reg_EA(mc, r1, base);
416 else if (fits_signed(off, 8))
417 ip += x.emit2_Reg_DISP8(mc, r1, (byte)off, base);
418 else
419 ip += x.emit2_Reg_DISP32(mc, r1, off, base);
420 }
421
422 // conditional jumps
423 public void emitCJUMP_Back(x86 x, Object target) {
424 Assert._assert(x.length == 1);
425 int offset = getBranchTarget(target) - ip - 2;
426 if (offset >= -128) {
427 if (TRACE) System.out.println("Short cjump back from offset "+Strings.hex(ip+2)+" to "+target+" offset "+getBranchTarget(target)+" (relative offset "+Strings.shex(offset)+")");
428 ip += x.emitCJump_Short(mc, (byte)offset);
429 } else {
430 if (TRACE) System.out.println("Near cjump back from offset "+Strings.hex(ip+6)+" to "+target+" offset "+getBranchTarget(target)+" (relative offset "+Strings.shex(offset-4)+")");
431 ip += x.emitCJump_Near(mc, offset - 4);
432 }
433 }
434 public void emitCJUMP_Short(x86 x, byte offset) {
435 Assert._assert(x.length == 1);
436 ip += x.emitCJump_Short(mc, offset);
437 }
438 public void emitCJUMP_Forw_Short(x86 x, Object target) {
439 Assert._assert(x.length == 1);
440 ip += x.emitCJump_Short(mc, (byte)0);
441 recordForwardBranch(1, target);
442 }
443 public void emitCJUMP_Forw(x86 x, Object target) {
444 Assert._assert(x.length == 1);
445 ip += x.emitCJump_Near(mc, 0x66666666);
446 recordForwardBranch(4, target);
447 }
448
449 // unconditional jumps
450 public void emitJUMP_Back(x86 x, Object target) {
451 Assert._assert(x.length == 1);
452 int offset = getBranchTarget(target) - ip - 2;
453 if(offset >= -128) {
454 if (TRACE) System.out.println("Short jump back from offset "+Strings.hex(ip+2)+" to "+target+" offset "+getBranchTarget(target)+" (relative offset "+Strings.shex(offset)+")");
455 ip += x.emitJump_Short(mc, (byte)offset);
456 } else {
457 if (TRACE) System.out.println("Near jump back from offset "+Strings.hex(ip+5)+" to "+target+" offset "+getBranchTarget(target)+" (relative offset "+Strings.shex(offset-3)+")");
458 ip += x.emitJump_Near(mc, offset - 3);
459 }
460 }
461 public void emitJUMP_Short(x86 x, byte offset) {
462 Assert._assert(x.length == 1);
463 ip += x.emitJump_Short(mc, offset);
464 }
465 public void emitJUMP_Forw_Short(x86 x, Object target) {
466 Assert._assert(x.length == 1);
467 ip += x.emitJump_Short(mc, (byte)0);
468 recordForwardBranch(1, target);
469 }
470 public void emitJUMP_Forw(x86 x, Object target) {
471 Assert._assert(x.length == 1);
472 ip += x.emitJump_Near(mc, 0x55555555);
473 recordForwardBranch(4, target);
474 }
475
476 // relative calls
477 public void emitCALL_rel32(x86 x, int address) {
478 Assert._assert(x.length == 1);
479 ip += x.emitCall_Near(mc, address);
480 }
481 public void emitCALL_Back(x86 x, Object target) {
482 Assert._assert(x.length == 1);
483 int offset = getBranchTarget(target) - ip - 5;
484 ip += x.emitCall_Near(mc, offset);
485 }
486 public void emitCALL_Forw(x86 x, Object target) {
487 Assert._assert(x.length == 1);
488 ip += x.emitCall_Near(mc, 0x44444444);
489 recordForwardBranch(4, target);
490 }
491
492 public void emitDATA(int data) {
493 mc.add4_endian(data);
494 ip += 4;
495 }
496
497 public void skip(int nbytes) {
498 if (TRACE) System.out.println("skipping "+nbytes+" bytes");
499 mc.skip(nbytes);
500 ip += nbytes;
501 }
502
503 public void setEntrypoint() {
504 mc.setEntrypoint();
505 }
506
507 public static boolean fits(int val, int bits) {
508 val >>= bits - 1;
509 return val == 0;
510 }
511
512 public static boolean fits_signed(int val, int bits) {
513 val >>= bits - 1;
514 return val == 0 || val == -1;
515 }
516
517 public static /*final*/ boolean TRACE = false;
518
519 private int ip; // current instruction pointer
520 private x86CodeBuffer mc; // code repository
521 private Map/*<Object,Integer>*/ branchtargetmap;
522 private Relation/*<Object,Set<PatchInfo>>*/ branches_to_patch;
523 private int dynPatchStart, dynPatchSize;
524 }