Several related changes:
[oota-llvm.git] / lib / Target / X86 / X86CodeEmitter.cpp
1 //===-- X86/X86CodeEmitter.cpp - Convert X86 code to machine code ---------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file contains the pass that transforms the X86 machine instructions into
11 // relocatable machine code.
12 //
13 //===----------------------------------------------------------------------===//
14
15 #include "X86TargetMachine.h"
16 #include "X86Relocations.h"
17 #include "X86.h"
18 #include "llvm/PassManager.h"
19 #include "llvm/CodeGen/MachineCodeEmitter.h"
20 #include "llvm/CodeGen/MachineFunctionPass.h"
21 #include "llvm/CodeGen/MachineInstr.h"
22 #include "llvm/CodeGen/Passes.h"
23 #include "llvm/Function.h"
24 #include "llvm/ADT/Statistic.h"
25 #include "llvm/Target/TargetOptions.h"
26 #include <iostream>
27 using namespace llvm;
28
29 namespace {
30   Statistic<>
31   NumEmitted("x86-emitter", "Number of machine instructions emitted");
32 }
33
34 namespace {
35   class Emitter : public MachineFunctionPass {
36     const X86InstrInfo  *II;
37     MachineCodeEmitter  &MCE;
38     std::map<MachineBasicBlock*, uint64_t> BasicBlockAddrs;
39     std::vector<std::pair<MachineBasicBlock *, unsigned> > BBRefs;
40   public:
41     explicit Emitter(MachineCodeEmitter &mce) : II(0), MCE(mce) {}
42     Emitter(MachineCodeEmitter &mce, const X86InstrInfo& ii)
43         : II(&ii), MCE(mce) {}
44
45     bool runOnMachineFunction(MachineFunction &MF);
46
47     virtual const char *getPassName() const {
48       return "X86 Machine Code Emitter";
49     }
50
51     void emitInstruction(const MachineInstr &MI);
52
53   private:
54     void emitBasicBlock(MachineBasicBlock &MBB);
55     void emitPCRelativeBlockAddress(MachineBasicBlock *MBB);
56     void emitPCRelativeValue(unsigned Address);
57     void emitGlobalAddressForCall(GlobalValue *GV, bool isTailCall);
58     void emitGlobalAddressForPtr(GlobalValue *GV, int Disp = 0);
59     void emitExternalSymbolAddress(const char *ES, bool isPCRelative,
60                                    bool isTailCall);
61
62     void emitRegModRMByte(unsigned ModRMReg, unsigned RegOpcodeField);
63     void emitSIBByte(unsigned SS, unsigned Index, unsigned Base);
64     void emitConstant(unsigned Val, unsigned Size);
65
66     void emitMemModRMByte(const MachineInstr &MI,
67                           unsigned Op, unsigned RegOpcodeField);
68
69   };
70 }
71
72 /// createX86CodeEmitterPass - Return a pass that emits the collected X86 code
73 /// to the specified MCE object.
74 FunctionPass *llvm::createX86CodeEmitterPass(MachineCodeEmitter &MCE) {
75   return new Emitter(MCE);
76 }
77
78 bool Emitter::runOnMachineFunction(MachineFunction &MF) {
79   assert((MF.getTarget().getRelocationModel() != Reloc::Default ||
80           MF.getTarget().getRelocationModel() != Reloc::Static) &&
81          "JIT relocation model must be set to static or default!");
82   II = ((X86TargetMachine&)MF.getTarget()).getInstrInfo();
83
84   do {
85     BBRefs.clear();
86     BasicBlockAddrs.clear();
87
88     MCE.startFunction(MF);
89     for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
90       emitBasicBlock(*I);
91     MCE.emitJumpTableInfo(MF.getJumpTableInfo(), BasicBlockAddrs);
92   } while (MCE.finishFunction(MF));
93
94   // Resolve all forward branches now.
95   for (unsigned i = 0, e = BBRefs.size(); i != e; ++i) {
96     unsigned Location = BasicBlockAddrs[BBRefs[i].first];
97     unsigned Ref = BBRefs[i].second;
98     *((unsigned*)(intptr_t)Ref) = Location-Ref-4;
99   }
100   BBRefs.clear();
101   BasicBlockAddrs.clear();
102   return false;
103 }
104
105 void Emitter::emitBasicBlock(MachineBasicBlock &MBB) {
106   if (uint64_t Addr = MCE.getCurrentPCValue())
107     BasicBlockAddrs[&MBB] = Addr;
108
109   for (MachineBasicBlock::const_iterator I = MBB.begin(), E = MBB.end();
110        I != E; ++I)
111     emitInstruction(*I);
112 }
113
114 /// emitPCRelativeValue - Emit a 32-bit PC relative address.
115 ///
116 void Emitter::emitPCRelativeValue(unsigned Address) {
117   MCE.emitWordLE(Address-MCE.getCurrentPCValue()-4);
118 }
119
120 /// emitPCRelativeBlockAddress - This method emits the PC relative address of
121 /// the specified basic block, or if the basic block hasn't been emitted yet
122 /// (because this is a forward branch), it keeps track of the information
123 /// necessary to resolve this address later (and emits a dummy value).
124 ///
125 void Emitter::emitPCRelativeBlockAddress(MachineBasicBlock *MBB) {
126   // If this is a backwards branch, we already know the address of the target,
127   // so just emit the value.
128   std::map<MachineBasicBlock*,uint64_t>::iterator I = BasicBlockAddrs.find(MBB);
129   if (I != BasicBlockAddrs.end()) {
130     emitPCRelativeValue(I->second);
131   } else {
132     // Otherwise, remember where this reference was and where it is to so we can
133     // deal with it later.
134     BBRefs.push_back(std::make_pair(MBB, MCE.getCurrentPCValue()));
135     MCE.emitWordLE(0);
136   }
137 }
138
139 /// emitGlobalAddressForCall - Emit the specified address to the code stream
140 /// assuming this is part of a function call, which is PC relative.
141 ///
142 void Emitter::emitGlobalAddressForCall(GlobalValue *GV, bool isTailCall) {
143   MCE.addRelocation(MachineRelocation(MCE.getCurrentPCOffset(),
144                                       X86::reloc_pcrel_word, GV, 0,
145                                       !isTailCall /*Doesn'tNeedStub*/));
146   MCE.emitWordLE(0);
147 }
148
149 /// emitGlobalAddress - Emit the specified address to the code stream assuming
150 /// this is part of a "take the address of a global" instruction, which is not
151 /// PC relative.
152 ///
153 void Emitter::emitGlobalAddressForPtr(GlobalValue *GV, int Disp /* = 0 */) {
154   MCE.addRelocation(MachineRelocation(MCE.getCurrentPCOffset(),
155                                       X86::reloc_absolute_word, GV));
156   MCE.emitWordLE(Disp); // The relocated value will be added to the displacement
157 }
158
159 /// emitExternalSymbolAddress - Arrange for the address of an external symbol to
160 /// be emitted to the current location in the function, and allow it to be PC
161 /// relative.
162 void Emitter::emitExternalSymbolAddress(const char *ES, bool isPCRelative,
163                                         bool isTailCall) {
164   MCE.addRelocation(MachineRelocation(MCE.getCurrentPCOffset(),
165           isPCRelative ? X86::reloc_pcrel_word : X86::reloc_absolute_word, ES));
166   MCE.emitWordLE(0);
167 }
168
169 /// N86 namespace - Native X86 Register numbers... used by X86 backend.
170 ///
171 namespace N86 {
172   enum {
173     EAX = 0, ECX = 1, EDX = 2, EBX = 3, ESP = 4, EBP = 5, ESI = 6, EDI = 7
174   };
175 }
176
177
178 // getX86RegNum - This function maps LLVM register identifiers to their X86
179 // specific numbering, which is used in various places encoding instructions.
180 //
181 static unsigned getX86RegNum(unsigned RegNo) {
182   switch(RegNo) {
183   case X86::EAX: case X86::AX: case X86::AL: return N86::EAX;
184   case X86::ECX: case X86::CX: case X86::CL: return N86::ECX;
185   case X86::EDX: case X86::DX: case X86::DL: return N86::EDX;
186   case X86::EBX: case X86::BX: case X86::BL: return N86::EBX;
187   case X86::ESP: case X86::SP: case X86::AH: return N86::ESP;
188   case X86::EBP: case X86::BP: case X86::CH: return N86::EBP;
189   case X86::ESI: case X86::SI: case X86::DH: return N86::ESI;
190   case X86::EDI: case X86::DI: case X86::BH: return N86::EDI;
191
192   case X86::ST0: case X86::ST1: case X86::ST2: case X86::ST3:
193   case X86::ST4: case X86::ST5: case X86::ST6: case X86::ST7:
194     return RegNo-X86::ST0;
195
196   case X86::XMM0: case X86::XMM1: case X86::XMM2: case X86::XMM3:
197   case X86::XMM4: case X86::XMM5: case X86::XMM6: case X86::XMM7:
198     return RegNo-X86::XMM0;
199
200   default:
201     assert(MRegisterInfo::isVirtualRegister(RegNo) &&
202            "Unknown physical register!");
203     assert(0 && "Register allocator hasn't allocated reg correctly yet!");
204     return 0;
205   }
206 }
207
208 inline static unsigned char ModRMByte(unsigned Mod, unsigned RegOpcode,
209                                       unsigned RM) {
210   assert(Mod < 4 && RegOpcode < 8 && RM < 8 && "ModRM Fields out of range!");
211   return RM | (RegOpcode << 3) | (Mod << 6);
212 }
213
214 void Emitter::emitRegModRMByte(unsigned ModRMReg, unsigned RegOpcodeFld){
215   MCE.emitByte(ModRMByte(3, RegOpcodeFld, getX86RegNum(ModRMReg)));
216 }
217
218 void Emitter::emitSIBByte(unsigned SS, unsigned Index, unsigned Base) {
219   // SIB byte is in the same format as the ModRMByte...
220   MCE.emitByte(ModRMByte(SS, Index, Base));
221 }
222
223 void Emitter::emitConstant(unsigned Val, unsigned Size) {
224   // Output the constant in little endian byte order...
225   for (unsigned i = 0; i != Size; ++i) {
226     MCE.emitByte(Val & 255);
227     Val >>= 8;
228   }
229 }
230
231 static bool isDisp8(int Value) {
232   return Value == (signed char)Value;
233 }
234
235 void Emitter::emitMemModRMByte(const MachineInstr &MI,
236                                unsigned Op, unsigned RegOpcodeField) {
237   const MachineOperand &Op3 = MI.getOperand(Op+3);
238   GlobalValue *GV = 0;
239   int DispVal = 0;
240
241   if (Op3.isGlobalAddress()) {
242     GV = Op3.getGlobal();
243     DispVal = Op3.getOffset();
244   } else if (Op3.isConstantPoolIndex()) {
245     DispVal += MCE.getConstantPoolEntryAddress(Op3.getConstantPoolIndex());
246     DispVal += Op3.getOffset();
247   } else if (Op3.isJumpTableIndex()) {
248     DispVal += MCE.getJumpTableEntryAddress(Op3.getJumpTableIndex());
249   } else {
250     DispVal = Op3.getImmedValue();
251   }
252
253   const MachineOperand &Base     = MI.getOperand(Op);
254   const MachineOperand &Scale    = MI.getOperand(Op+1);
255   const MachineOperand &IndexReg = MI.getOperand(Op+2);
256
257   unsigned BaseReg = Base.getReg();
258
259   // Is a SIB byte needed?
260   if (IndexReg.getReg() == 0 && BaseReg != X86::ESP) {
261     if (BaseReg == 0) {  // Just a displacement?
262       // Emit special case [disp32] encoding
263       MCE.emitByte(ModRMByte(0, RegOpcodeField, 5));
264       if (GV)
265         emitGlobalAddressForPtr(GV, DispVal);
266       else
267         emitConstant(DispVal, 4);
268     } else {
269       unsigned BaseRegNo = getX86RegNum(BaseReg);
270       if (GV) {
271         // Emit the most general non-SIB encoding: [REG+disp32]
272         MCE.emitByte(ModRMByte(2, RegOpcodeField, BaseRegNo));
273         emitGlobalAddressForPtr(GV, DispVal);
274       } else if (DispVal == 0 && BaseRegNo != N86::EBP) {
275         // Emit simple indirect register encoding... [EAX] f.e.
276         MCE.emitByte(ModRMByte(0, RegOpcodeField, BaseRegNo));
277       } else if (isDisp8(DispVal)) {
278         // Emit the disp8 encoding... [REG+disp8]
279         MCE.emitByte(ModRMByte(1, RegOpcodeField, BaseRegNo));
280         emitConstant(DispVal, 1);
281       } else {
282         // Emit the most general non-SIB encoding: [REG+disp32]
283         MCE.emitByte(ModRMByte(2, RegOpcodeField, BaseRegNo));
284         emitConstant(DispVal, 4);
285       }
286     }
287
288   } else {  // We need a SIB byte, so start by outputting the ModR/M byte first
289     assert(IndexReg.getReg() != X86::ESP && "Cannot use ESP as index reg!");
290
291     bool ForceDisp32 = false;
292     bool ForceDisp8  = false;
293     if (BaseReg == 0) {
294       // If there is no base register, we emit the special case SIB byte with
295       // MOD=0, BASE=5, to JUST get the index, scale, and displacement.
296       MCE.emitByte(ModRMByte(0, RegOpcodeField, 4));
297       ForceDisp32 = true;
298     } else if (GV) {
299       // Emit the normal disp32 encoding...
300       MCE.emitByte(ModRMByte(2, RegOpcodeField, 4));
301       ForceDisp32 = true;
302     } else if (DispVal == 0 && BaseReg != X86::EBP) {
303       // Emit no displacement ModR/M byte
304       MCE.emitByte(ModRMByte(0, RegOpcodeField, 4));
305     } else if (isDisp8(DispVal)) {
306       // Emit the disp8 encoding...
307       MCE.emitByte(ModRMByte(1, RegOpcodeField, 4));
308       ForceDisp8 = true;           // Make sure to force 8 bit disp if Base=EBP
309     } else {
310       // Emit the normal disp32 encoding...
311       MCE.emitByte(ModRMByte(2, RegOpcodeField, 4));
312     }
313
314     // Calculate what the SS field value should be...
315     static const unsigned SSTable[] = { ~0, 0, 1, ~0, 2, ~0, ~0, ~0, 3 };
316     unsigned SS = SSTable[Scale.getImmedValue()];
317
318     if (BaseReg == 0) {
319       // Handle the SIB byte for the case where there is no base.  The
320       // displacement has already been output.
321       assert(IndexReg.getReg() && "Index register must be specified!");
322       emitSIBByte(SS, getX86RegNum(IndexReg.getReg()), 5);
323     } else {
324       unsigned BaseRegNo = getX86RegNum(BaseReg);
325       unsigned IndexRegNo;
326       if (IndexReg.getReg())
327         IndexRegNo = getX86RegNum(IndexReg.getReg());
328       else
329         IndexRegNo = 4;   // For example [ESP+1*<noreg>+4]
330       emitSIBByte(SS, IndexRegNo, BaseRegNo);
331     }
332
333     // Do we need to output a displacement?
334     if (DispVal != 0 || ForceDisp32 || ForceDisp8) {
335       if (!ForceDisp32 && isDisp8(DispVal))
336         emitConstant(DispVal, 1);
337       else if (GV)
338         emitGlobalAddressForPtr(GV, DispVal);
339       else
340         emitConstant(DispVal, 4);
341     }
342   }
343 }
344
345 static unsigned sizeOfImm(const TargetInstrDescriptor &Desc) {
346   switch (Desc.TSFlags & X86II::ImmMask) {
347   case X86II::Imm8:   return 1;
348   case X86II::Imm16:  return 2;
349   case X86II::Imm32:  return 4;
350   default: assert(0 && "Immediate size not set!");
351     return 0;
352   }
353 }
354
355 void Emitter::emitInstruction(const MachineInstr &MI) {
356   NumEmitted++;  // Keep track of the # of mi's emitted
357
358   unsigned Opcode = MI.getOpcode();
359   const TargetInstrDescriptor &Desc = II->get(Opcode);
360
361   // Emit the repeat opcode prefix as needed.
362   if ((Desc.TSFlags & X86II::Op0Mask) == X86II::REP) MCE.emitByte(0xF3);
363
364   // Emit the operand size opcode prefix as needed.
365   if (Desc.TSFlags & X86II::OpSize) MCE.emitByte(0x66);
366
367   switch (Desc.TSFlags & X86II::Op0Mask) {
368   case X86II::TB:
369     MCE.emitByte(0x0F);   // Two-byte opcode prefix
370     break;
371   case X86II::REP: break; // already handled.
372   case X86II::XS:   // F3 0F
373     MCE.emitByte(0xF3);
374     MCE.emitByte(0x0F);
375     break;
376   case X86II::XD:   // F2 0F
377     MCE.emitByte(0xF2);
378     MCE.emitByte(0x0F);
379     break;
380   case X86II::D8: case X86II::D9: case X86II::DA: case X86II::DB:
381   case X86II::DC: case X86II::DD: case X86II::DE: case X86II::DF:
382     MCE.emitByte(0xD8+
383                  (((Desc.TSFlags & X86II::Op0Mask)-X86II::D8)
384                                    >> X86II::Op0Shift));
385     break; // Two-byte opcode prefix
386   default: assert(0 && "Invalid prefix!");
387   case 0: break;  // No prefix!
388   }
389
390   unsigned char BaseOpcode = II->getBaseOpcodeFor(Opcode);
391   switch (Desc.TSFlags & X86II::FormMask) {
392   default: assert(0 && "Unknown FormMask value in X86 MachineCodeEmitter!");
393   case X86II::Pseudo:
394 #ifndef NDEBUG
395     switch (Opcode) {
396     default: 
397       assert(0 && "psuedo instructions should be removed before code emission");
398     case X86::IMPLICIT_USE:
399     case X86::IMPLICIT_DEF:
400     case X86::IMPLICIT_DEF_R8:
401     case X86::IMPLICIT_DEF_R16:
402     case X86::IMPLICIT_DEF_R32:
403     case X86::IMPLICIT_DEF_FR32:
404     case X86::IMPLICIT_DEF_FR64:
405     case X86::IMPLICIT_DEF_VR64:
406     case X86::IMPLICIT_DEF_VR128:
407     case X86::FP_REG_KILL:
408       break;
409     }
410 #endif
411     break;
412
413   case X86II::RawFrm:
414     MCE.emitByte(BaseOpcode);
415     if (MI.getNumOperands() == 1) {
416       const MachineOperand &MO = MI.getOperand(0);
417       if (MO.isMachineBasicBlock()) {
418         emitPCRelativeBlockAddress(MO.getMachineBasicBlock());
419       } else if (MO.isGlobalAddress()) {
420         bool isTailCall = Opcode == X86::TAILJMPd ||
421                           Opcode == X86::TAILJMPr || Opcode == X86::TAILJMPm;
422         emitGlobalAddressForCall(MO.getGlobal(), isTailCall);
423       } else if (MO.isExternalSymbol()) {
424         bool isTailCall = Opcode == X86::TAILJMPd ||
425                           Opcode == X86::TAILJMPr || Opcode == X86::TAILJMPm;
426         emitExternalSymbolAddress(MO.getSymbolName(), true, isTailCall);
427       } else if (MO.isImmediate()) {
428         emitConstant(MO.getImmedValue(), sizeOfImm(Desc));
429       } else {
430         assert(0 && "Unknown RawFrm operand!");
431       }
432     }
433     break;
434
435   case X86II::AddRegFrm:
436     MCE.emitByte(BaseOpcode + getX86RegNum(MI.getOperand(0).getReg()));
437     if (MI.getNumOperands() == 2) {
438       const MachineOperand &MO1 = MI.getOperand(1);
439       if (Value *V = MO1.getVRegValueOrNull()) {
440         assert(sizeOfImm(Desc) == 4 &&
441                "Don't know how to emit non-pointer values!");
442         emitGlobalAddressForPtr(cast<GlobalValue>(V));
443       } else if (MO1.isGlobalAddress()) {
444         assert(sizeOfImm(Desc) == 4 &&
445                "Don't know how to emit non-pointer values!");
446         assert(!MO1.isPCRelative() && "Function pointer ref is PC relative?");
447         emitGlobalAddressForPtr(MO1.getGlobal(), MO1.getOffset());
448       } else if (MO1.isExternalSymbol()) {
449         assert(sizeOfImm(Desc) == 4 &&
450                "Don't know how to emit non-pointer values!");
451         emitExternalSymbolAddress(MO1.getSymbolName(), false, false);
452       } else if (MO1.isJumpTableIndex()) {
453         assert(sizeOfImm(Desc) == 4 &&
454                "Don't know how to emit non-pointer values!");
455         emitConstant(MCE.getJumpTableEntryAddress(MO1.getJumpTableIndex()), 4);
456       } else {
457         emitConstant(MO1.getImmedValue(), sizeOfImm(Desc));
458       }
459     }
460     break;
461
462   case X86II::MRMDestReg: {
463     MCE.emitByte(BaseOpcode);
464     emitRegModRMByte(MI.getOperand(0).getReg(),
465                      getX86RegNum(MI.getOperand(1).getReg()));
466     if (MI.getNumOperands() == 3)
467       emitConstant(MI.getOperand(2).getImmedValue(), sizeOfImm(Desc));
468     break;
469   }
470   case X86II::MRMDestMem:
471     MCE.emitByte(BaseOpcode);
472     emitMemModRMByte(MI, 0, getX86RegNum(MI.getOperand(4).getReg()));
473     if (MI.getNumOperands() == 6)
474       emitConstant(MI.getOperand(5).getImmedValue(), sizeOfImm(Desc));
475     break;
476
477   case X86II::MRMSrcReg:
478     MCE.emitByte(BaseOpcode);
479     emitRegModRMByte(MI.getOperand(1).getReg(),
480                      getX86RegNum(MI.getOperand(0).getReg()));
481     if (MI.getNumOperands() == 3)
482       emitConstant(MI.getOperand(2).getImmedValue(), sizeOfImm(Desc));
483     break;
484
485   case X86II::MRMSrcMem:
486     MCE.emitByte(BaseOpcode);
487     emitMemModRMByte(MI, 1, getX86RegNum(MI.getOperand(0).getReg()));
488     if (MI.getNumOperands() == 2+4)
489       emitConstant(MI.getOperand(5).getImmedValue(), sizeOfImm(Desc));
490     break;
491
492   case X86II::MRM0r: case X86II::MRM1r:
493   case X86II::MRM2r: case X86II::MRM3r:
494   case X86II::MRM4r: case X86II::MRM5r:
495   case X86II::MRM6r: case X86II::MRM7r:
496     MCE.emitByte(BaseOpcode);
497     emitRegModRMByte(MI.getOperand(0).getReg(),
498                      (Desc.TSFlags & X86II::FormMask)-X86II::MRM0r);
499
500     if (MI.getOperand(MI.getNumOperands()-1).isImmediate()) {
501       emitConstant(MI.getOperand(MI.getNumOperands()-1).getImmedValue(),
502                    sizeOfImm(Desc));
503     }
504     break;
505
506   case X86II::MRM0m: case X86II::MRM1m:
507   case X86II::MRM2m: case X86II::MRM3m:
508   case X86II::MRM4m: case X86II::MRM5m:
509   case X86II::MRM6m: case X86II::MRM7m:
510     MCE.emitByte(BaseOpcode);
511     emitMemModRMByte(MI, 0, (Desc.TSFlags & X86II::FormMask)-X86II::MRM0m);
512
513     if (MI.getNumOperands() == 5) {
514       if (MI.getOperand(4).isImmediate())
515         emitConstant(MI.getOperand(4).getImmedValue(), sizeOfImm(Desc));
516       else if (MI.getOperand(4).isGlobalAddress())
517         emitGlobalAddressForPtr(MI.getOperand(4).getGlobal(),
518                                 MI.getOperand(4).getOffset());
519       else
520         assert(0 && "Unknown operand!");
521     }
522     break;
523
524   case X86II::MRMInitReg:
525     MCE.emitByte(BaseOpcode);
526     emitRegModRMByte(MI.getOperand(0).getReg(),
527                      getX86RegNum(MI.getOperand(0).getReg()));
528     break;
529   }
530 }