1// Copyright (c) 2009 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5// Copyright (c) 1994-2006 Sun Microsystems Inc.
6// All Rights Reserved.
7//
8// Redistribution and use in source and binary forms, with or without
9// modification, are permitted provided that the following conditions are
10// met:
11//
12// - Redistributions of source code must retain the above copyright notice,
13// this list of conditions and the following disclaimer.
14//
15// - Redistribution in binary form must reproduce the above copyright
16// notice, this list of conditions and the following disclaimer in the
17// documentation and/or other materials provided with the distribution.
18//
19// - Neither the name of Sun Microsystems or the names of contributors may
20// be used to endorse or promote products derived from this software without
21// specific prior written permission.
22//
23// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
24// IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
25// THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
26// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
27// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
28// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
29// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
30// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
31// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
32// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
33// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34
35// The original source code covered by the above license above has been
36// modified significantly by Google Inc.
37// Copyright 2006-2008 the V8 project authors. All rights reserved.
38
39// This implements a C++ assembler for dynamically generating machine code.
40// It is heavily based on the v8 assembler, which has a long history of its
41// own.  Relocation information has been removed, and in general things were
42// made a bit simpler (and slower).  Everything is implemented inline.
43
44#ifndef TRACELINE_ASSEMBLER_H_
45#define TRACELINE_ASSEMBLER_H_
46
47#include <windows.h>
48#include <stdio.h>
49#include <string>
50
51#include "logging.h"
52
53#define ASSERT(x) CHECK(x)
54
55enum Register {
56  EAX = 0,
57  ECX = 1,
58  EDX = 2,
59  EBX = 3,
60  ESP = 4,
61  EBP = 5,
62  ESI = 6,
63  EDI = 7
64};
65
66enum Condition {
67  overflow      =  0,
68  no_overflow   =  1,
69  below         =  2,
70  above_equal   =  3,
71  equal         =  4,
72  not_equal     =  5,
73  below_equal   =  6,
74  above         =  7,
75  sign          =  8,
76  not_sign      =  9,
77  parity_even   = 10,
78  parity_odd    = 11,
79  less          = 12,
80  greater_equal = 13,
81  less_equal    = 14,
82  greater       = 15,
83
84  // aliases
85  zero          = equal,
86  not_zero      = not_equal,
87  negative      = sign,
88  positive      = not_sign
89};
90
91// Labels are used for branching, and marks an offset in the CodeBuffer.
92// A label can be in 3 states:
93//  - Unused, the label has never be used in an instruction.
94//  - Linked, the label has been referenced (by a jump, for example), but the
95//    target is not yet known, because the label is unbound.
96//  - Bound, the label has been bound so the offset is known.
97class Label {
98 public:
99  Label() { Unuse(); }
100  ~Label() { ASSERT(!is_linked()); }
101
102  void Unuse() {
103    num_ = 0;
104  }
105
106  bool is_unused() const { return num_ == 0; }
107  bool is_bound() const { return num_ == -1; }
108  bool is_linked() const { return num_ > 0; }
109
110  int binding_pos() const {
111    ASSERT(is_bound());
112    return table_[0];
113  }
114
115  int num_links() const {
116    ASSERT(!is_bound());
117    return num_;  // Will return 0 if unused.
118  }
119
120  int link_pos(int i) const {
121    ASSERT(is_linked());
122    ASSERT(i < num_);
123    return table_[i];
124  }
125
126 private:
127  void bind_to(int pos)  {
128    ASSERT(!is_bound());
129    table_[0] = pos;
130    num_ = -1;
131  }
132  void link_to(int pos)  {
133    ASSERT(!is_bound());
134    ASSERT(num_ < kTableSize);
135
136    table_[num_] = pos;
137    ++num_;
138  }
139
140  static const int kTableSize = 3;
141
142  // We store all links in a fixed size table.  When we're bound, we store the
143  // binding position in the first entry of the table.
144  int table_[kTableSize];
145  // The number of entries in our table, if we're linked.  If 0, then we're
146  // unusued.  If -1, then we are bound (and the pos is at table_[0]).
147  int num_;
148
149  friend class CodeBuffer;  // For binding, linking, etc
150};
151
152
153enum ScaleFactor {
154  SCALE_TIMES_1 = 0,
155  SCALE_TIMES_2 = 1,
156  SCALE_TIMES_4 = 2,
157  SCALE_TIMES_8 = 3
158};
159
160
161class Operand {
162 public:
163  explicit Operand(const Operand& x) : len_(x.len_) {
164    memcpy(buf_, x.buf_, sizeof(buf_));
165  }
166
167  // reg
168  explicit Operand(Register reg) {
169    Init(reg);
170  }
171
172  // [disp/r]
173  explicit Operand(int disp) {
174    Init(disp);
175  }
176
177  // [base + disp/r]
178  Operand(Register base, int disp) {
179    Init(base, disp);
180  }
181
182  // [base + index*scale + disp/r]
183  Operand(Register base, Register index, ScaleFactor scale, int disp) {
184    Init(base, index, scale, disp);
185  }
186
187  // [index*scale + disp/r]
188  Operand(Register index, ScaleFactor scale, int disp) {
189    Init(index, scale, disp);
190  }
191
192  void set_reg(Register reg) {
193    ASSERT(len_ > 0);
194    buf_[0] = (buf_[0] & ~0x38) | static_cast<char>(reg << 3);
195  }
196
197  char* data() { return buf_; }
198  int length() { return len_; }
199
200 private:
201  // reg
202  void Init(Register reg) {
203    set_modrm(3, reg);
204  }
205
206  // [disp/r]
207  void Init(int disp) {
208    set_modrm(0, EBP);
209    set_dispr(disp);
210  }
211
212  // [base + disp/r]
213  void Init(Register base, int disp) {
214    if (disp == 0) {
215      // [base]
216      set_modrm(0, base);
217      if (base == ESP) set_sib(SCALE_TIMES_1, ESP, base);
218    } else if (is_int8(disp)) {
219      // [base + disp8]
220      set_modrm(1, base);
221      if (base == ESP) set_sib(SCALE_TIMES_1, ESP, base);
222      set_disp8(disp);
223    } else {
224      // [base + disp/r]
225      set_modrm(2, base);
226      if (base == ESP) set_sib(SCALE_TIMES_1, ESP, base);
227      set_dispr(disp);
228    }
229  }
230
231  // [base + index*scale + disp/r]
232  void Init(Register base,
233            Register index,
234            ScaleFactor scale,
235            int disp) {
236    ASSERT(index != ESP);  // illegal addressing mode
237    if (disp == 0 && base != EBP) {
238      // [base + index*scale]
239      set_modrm(0, ESP);
240      set_sib(scale, index, base);
241    } else if (is_int8(disp)) {
242      // [base + index*scale + disp8]
243      set_modrm(1, ESP);
244      set_sib(scale, index, base);
245      set_disp8(disp);
246    } else {
247      // [base + index*scale + disp/r]
248      set_modrm(2, ESP);
249      set_sib(scale, index, base);
250      set_dispr(disp);
251    }
252  }
253
254  // [index*scale + disp/r]
255  void Init(Register index,
256            ScaleFactor scale,
257            int disp) {
258    ASSERT(index != ESP);  // illegal addressing mode
259    // We can reduce instruction size by translating instructions of the form:
260    //   8D044510000000    lea eax,[eax*2+0x10]
261    // To the more concise scale=1 version:
262    //   8D440010          lea eax,[eax+eax+0x10]
263    if (scale == SCALE_TIMES_2) {
264      Init(index, index, SCALE_TIMES_1, disp);
265    } else {
266      set_modrm(0, ESP);
267      set_sib(scale, index, EBP);
268      set_dispr(disp);
269    }
270  }
271
272  // Returns true if this Operand is a wrapper for the specified register.
273  bool is_reg(Register reg) const {
274    return ((buf_[0] & 0xF8) == 0xC0)  // addressing mode is register only.
275        && ((buf_[0] & 0x07) == reg);  // register codes match.
276  }
277
278  void set_modrm(int mod, Register rm) {  // reg == 0
279    ASSERT((mod & -4) == 0);
280    buf_[0] = mod << 6 | rm;
281    len_ = 1;
282  }
283
284  void set_sib(ScaleFactor scale, Register index, Register base) {
285    ASSERT(len_ == 1);
286    ASSERT((scale & -4) == 0);
287    buf_[1] = scale << 6 | index << 3 | base;
288    len_ = 2;
289  }
290
291  void set_disp8(char disp) {
292    ASSERT(len_ == 1 || len_ == 2);
293    *reinterpret_cast<char*>(&buf_[len_++]) = disp;
294  }
295
296  void set_dispr(int disp) {
297    ASSERT(len_ == 1 || len_ == 2);
298    *reinterpret_cast<int*>(&buf_[len_]) = disp;
299    len_ += sizeof(int);
300  }
301
302  bool is_int8(int x) { return x >= -128 && x <= 127; }
303
304  // Mutable because reg in ModR/M byte is set by Assembler via set_reg().
305  char buf_[6];
306  // The number of bytes in buf_.
307  unsigned int len_;
308};
309
310// A convenient wrapper around a buffer for emitting code or data, etc.
311class CodeBuffer {
312 public:
313  // Use an externally managed buffer
314  explicit CodeBuffer(char* buf) : pos_(0), buf_(buf) { }
315
316  void* data() { return buf_; }
317  int size() { return pos_; }
318
319  void emit(unsigned char b) {
320    buf_[pos_++] = b;
321  }
322  void emit_word(unsigned short w) {
323    *reinterpret_cast<unsigned short*>(&buf_[pos_]) = w;
324    pos_ += 2;
325  }
326  void emit_dword(unsigned int d) {
327    *reinterpret_cast<unsigned int*>(&buf_[pos_]) = d;
328    pos_ += 4;
329  }
330
331  void emit_bytes(const char* bytes, size_t size) {
332    for (size_t i = 0; i < size; ++i)
333      emit(bytes[i]);
334  }
335
336  void emit_bytes(const std::string& bytes) {
337    emit_bytes(bytes.data(), bytes.size());
338  }
339
340  void put_dword_at(int pos, unsigned int d) {
341    *reinterpret_cast<unsigned int*>(&buf_[pos]) = d;
342  }
343
344  // We pass by value so that we get a copy that we can modify.
345  void emit_operand(Register reg, Operand operand) {
346    operand.set_reg(reg);
347    memcpy(&buf_[pos_], operand.data(), operand.length());
348    pos_ += operand.length();
349  }
350
351  void bind(Label* l) {
352    ASSERT(!l->is_bound());
353    for (int i = 0; i < l->num_links(); ++i) {
354      put_dword_at(l->link_pos(i), pos_ - (l->link_pos(i) + 4));
355    }
356    l->bind_to(pos_);
357  }
358
359  // TODO deprecate blah_imm and use blah(Immediate)
360
361  void add(Register dst, Register src) {
362    emit(0x01); emit(0xc0 | (src << 3) | dst);
363  }
364  void add_imm(Register dst, int d) {
365    if (d >= -128 && d <= 127) {
366      emit(0x83); emit(0xc0 | dst); emit(d & 0xff);
367    } else {
368      emit(0x81); emit(0xc0 | dst); emit_dword(d);
369    }
370  }
371
372  void and_(Register r, unsigned int mask) {
373    emit(0x81); emit(0xe0 | r); emit_dword(mask);
374  }
375
376  void call(Register r) {
377    call(Operand(r));
378  }
379  void call(const Operand& dst) {
380    emit(0xff); emit_operand(EDX, dst);
381  }
382
383  void cmp(Register r1, Register r2) {
384    emit(0x39); emit(0xc0 | (r2 << 3) | r1);
385  }
386
387  void cmp_imm(Register r, int d) {
388    if (d >= -128 && d <= 127) {
389      emit(0x83); emit(0xf8 | r); emit(d & 0xff);
390    } else {
391      emit(0x81); emit(0xf8 | r); emit_dword(d);
392    }
393  }
394
395  void fs() {
396    emit(0x64);
397  }
398
399  // Atomically increment the dword at |mem| with the increment amount in the
400  // register |inc|.  Will replace |inc| with the old unincremented value.
401  void inc_atomic(Register mem, Register inc) {
402    // lock xadd [mem], inc
403    emit(0xF0); emit(0x0F); emit(0xC1); emit((inc << 3) | mem);
404  }
405
406  void int3() {
407    emit(0xcc);
408  }
409
410  void jcc(Condition cc, Label* l) {
411    emit(0x0f); emit(0x80 | cc);
412    if (l->is_bound()) {
413      emit_dword(l->binding_pos() - (pos_ + 4));
414    } else {
415      // Will fix up when the label is bound.
416      l->link_to(pos_);
417      emit_dword(0);
418    }
419  }
420
421  void jmp(Register r) {
422    emit(0xff); emit(0xe0 | r);
423  }
424
425  void jmp(Label* l) {
426    if (l->is_bound()) {
427      jmp_rel(l->binding_pos() - (pos_ + 5));
428    } else {
429      // Will fix up when the label is bound.
430      l->link_to(pos_ + 1);
431      jmp_rel(0);
432    }
433  }
434
435  void jmp_rel(int i) {
436    emit(0xe9); emit_dword(i);
437  }
438
439  void jmp_rel_short(char c) {
440    emit(0xeb); emit(c);
441  }
442
443  void lea(Register dst, const Operand& src) {
444    emit(0x8d); emit_operand(dst, src);
445  }
446
447  void lodsb() {
448    emit(0xac);
449  }
450  void lodsd() {
451    emit(0xad);
452  }
453
454  void loop(Label* l) {
455    ASSERT(l->is_bound());
456    int pos = l->binding_pos() - (pos_ + 2);
457    ASSERT(pos >= -128 && pos < 0);
458
459    emit(0xe2); emit(pos & 0xff);
460  }
461
462  void mov(Register dst, Register src) {
463    emit(0x89); emit(0xc0 | (src << 3) | dst);
464  }
465  void mov(Register dst, const Operand& src) {
466    emit(0x8b); emit_operand(dst, src);
467  }
468  void mov_imm(Register r, unsigned int d) {
469    emit(0xb8 | r); emit_dword(d);
470  }
471
472  void movsb() {
473    emit(0xa4);
474  }
475  void movsd() {
476    emit(0xa5);
477  }
478
479  void or_(Register r, unsigned int mask) {
480    emit(0x81); emit(0xc8 | r); emit_dword(mask);
481  }
482
483  void pop(Register r) {
484    emit(0x58 | r);
485  }
486  void pop(const Operand& dst) {
487    emit(0x8f); emit_operand(EAX, dst);
488  }
489
490  void push(Register r) {
491    emit(0x50 | r);
492  }
493  void push(const Operand& src) {
494    emit(0xff); emit_operand(ESI, src);
495  }
496  void push_imm(int i) {
497    if (i >= -128 && i <= 127) {
498      emit(0x6a); emit(i & 0xff);
499    } else {
500      emit(0x68); emit_dword(i);
501    }
502  }
503
504  // Puts the cycle counter into edx:eax.
505  void rdtsc() {
506    emit(0x0F); emit(0x31);
507  }
508
509  void rep() {
510    emit(0xf3);
511  }
512
513  void ret() {
514    ret(0);
515  }
516  void ret(short c) {
517    if (c == 0) {
518      emit(0xc3);
519    } else {
520      emit(0xc2); emit_word(c);
521    }
522  }
523
524  void spin() {
525    jmp_rel_short(-2);
526  }
527
528  void stosb() {
529    emit(0xaa);
530  }
531  void stosd() {
532    emit(0xab);
533  }
534
535  void sysenter() {
536    emit(0x0f); emit(0x34);
537  }
538
539  // Puts a unique cpu identifier into eax, using sidt to fingerprint cores.
540  void which_cpu() {
541    // Make space
542    push(EAX);
543    push(EAX);
544    // sidt [esp+2]
545    emit(0x0f); emit(0x01); emit_operand(ECX, Operand(ESP, 2));
546    pop(EAX);
547    pop(EAX);  // sidt address
548  }
549
550  // Puts a unique identifier for the thread we're executing on into eax.
551  void which_thread() {
552    // mov eax, [fs:0x24]
553    emit(0x64); emit(0xa1); emit_dword(0x24);
554    // TODO: We could do this but it will use an encoding that is 1 byte bigger.
555    // fs(); mov(EAX, Operand(0x24));
556  }
557
558  void xchg(Register r1, Register r2) {
559    if (r1 == EAX) {
560      emit(0x90 | r2);
561    } else if (r2 == EAX) {
562      emit(0x90 | r1);
563    } else {
564      xchg(r1, Operand(r2));
565    }
566  }
567  void xchg(Register r1, const Operand& oper) {
568    emit(0x87); emit_operand(r1, oper);
569  }
570
571 private:
572  int pos_;
573  char* buf_;
574};
575
576#endif  // TRACELINE_ASSEMBLER_H_
577