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