Add memory operand folding support for MUL, DIV, IDIV, NEG, NOT,
[oota-llvm.git] / lib / Target / X86 / X86RegisterInfo.cpp
1 //===- X86RegisterInfo.cpp - X86 Register Information -----------*- C++ -*-===//
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 X86 implementation of the MRegisterInfo class.  This
11 // file is responsible for the frame pointer elimination optimization on X86.
12 //
13 //===----------------------------------------------------------------------===//
14
15 #include "X86.h"
16 #include "X86RegisterInfo.h"
17 #include "X86InstrBuilder.h"
18 #include "llvm/Constants.h"
19 #include "llvm/Type.h"
20 #include "llvm/CodeGen/ValueTypes.h"
21 #include "llvm/CodeGen/MachineInstrBuilder.h"
22 #include "llvm/CodeGen/MachineFunction.h"
23 #include "llvm/CodeGen/MachineFrameInfo.h"
24 #include "llvm/Target/TargetMachine.h"
25 #include "llvm/Target/TargetFrameInfo.h"
26 #include "Support/CommandLine.h"
27 #include "Support/STLExtras.h"
28 using namespace llvm;
29
30 namespace {
31   cl::opt<bool>
32   NoFPElim("disable-fp-elim",
33            cl::desc("Disable frame pointer elimination optimization"));
34   cl::opt<bool>
35   NoFusing("disable-spill-fusing",
36            cl::desc("Disable fusing of spill code into instructions"));
37   cl::opt<bool>
38   PrintFailedFusing("print-failed-fuse-candidates",
39                     cl::desc("Print instructions that the allocator wants to"
40                              " fuse, but the X86 backend currently can't"),
41                     cl::Hidden);
42 }
43
44 X86RegisterInfo::X86RegisterInfo()
45   : X86GenRegisterInfo(X86::ADJCALLSTACKDOWN, X86::ADJCALLSTACKUP) {}
46
47 static unsigned getIdx(const TargetRegisterClass *RC) {
48   switch (RC->getSize()) {
49   default: assert(0 && "Invalid data size!");
50   case 1:  return 0;
51   case 2:  return 1;
52   case 4:  return 2;
53   case 10: return 3;
54   }
55 }
56
57 int X86RegisterInfo::storeRegToStackSlot(MachineBasicBlock &MBB,
58                                          MachineBasicBlock::iterator MI,
59                                          unsigned SrcReg, int FrameIdx,
60                                          const TargetRegisterClass *RC) const {
61   static const unsigned Opcode[] =
62     { X86::MOVmr8, X86::MOVmr16, X86::MOVmr32, X86::FSTPr80 };
63   MachineInstr *I = addFrameReference(BuildMI(Opcode[getIdx(RC)], 5),
64                                        FrameIdx).addReg(SrcReg);
65   MBB.insert(MI, I);
66   return 1;
67 }
68
69 int X86RegisterInfo::loadRegFromStackSlot(MachineBasicBlock &MBB,
70                                           MachineBasicBlock::iterator MI,
71                                           unsigned DestReg, int FrameIdx,
72                                           const TargetRegisterClass *RC) const{
73   static const unsigned Opcode[] =
74     { X86::MOVrm8, X86::MOVrm16, X86::MOVrm32, X86::FLDr80 };
75   unsigned OC = Opcode[getIdx(RC)];
76   MBB.insert(MI, addFrameReference(BuildMI(OC, 4, DestReg), FrameIdx));
77   return 1;
78 }
79
80 int X86RegisterInfo::copyRegToReg(MachineBasicBlock &MBB,
81                                   MachineBasicBlock::iterator MI,
82                                   unsigned DestReg, unsigned SrcReg,
83                                   const TargetRegisterClass *RC) const {
84   static const unsigned Opcode[] =
85     { X86::MOVrr8, X86::MOVrr16, X86::MOVrr32, X86::FpMOV };
86   MBB.insert(MI, BuildMI(Opcode[getIdx(RC)],1,DestReg).addReg(SrcReg));
87   return 1;
88 }
89
90 static MachineInstr *MakeMInst(unsigned Opcode, unsigned FrameIndex,
91                                MachineInstr *MI) {
92   return addFrameReference(BuildMI(Opcode, 1, MI->getOperand(0).getReg()),
93                            FrameIndex);
94 }
95
96 static MachineInstr *MakeMRInst(unsigned Opcode, unsigned FrameIndex,
97                                 MachineInstr *MI) {
98   return addFrameReference(BuildMI(Opcode, 5), FrameIndex)
99                  .addReg(MI->getOperand(1).getReg());
100 }
101
102 static MachineInstr *MakeMIInst(unsigned Opcode, unsigned FrameIndex,
103                                 MachineInstr *MI) {
104   return addFrameReference(BuildMI(Opcode, 5), FrameIndex)
105                  .addZImm(MI->getOperand(1).getImmedValue());
106 }
107
108 static MachineInstr *MakeRMInst(unsigned Opcode, unsigned FrameIndex,
109                                 MachineInstr *MI) {
110   return addFrameReference(BuildMI(Opcode, 5, MI->getOperand(0).getReg()),
111                            FrameIndex);
112 }
113
114 static MachineInstr *MakeRMIInst(unsigned Opcode, unsigned FrameIndex,
115                                  MachineInstr *MI) {
116   return addFrameReference(BuildMI(Opcode, 5, MI->getOperand(0).getReg()),
117                         FrameIndex).addZImm(MI->getOperand(2).getImmedValue());
118 }
119
120
121 bool X86RegisterInfo::foldMemoryOperand(MachineBasicBlock::iterator &MI,
122                                         unsigned i, int FrameIndex) const {
123   if (NoFusing) return false;
124
125   /// FIXME: This should obviously be autogenerated by tablegen when patterns
126   /// are available!
127   MachineBasicBlock& MBB = *MI->getParent();
128   MachineInstr* NI = 0;
129   if (i == 0) {
130     switch(MI->getOpcode()) {
131     case X86::MOVrr8:  NI = MakeMRInst(X86::MOVmr8 , FrameIndex, MI); break;
132     case X86::MOVrr16: NI = MakeMRInst(X86::MOVmr16, FrameIndex, MI); break;
133     case X86::MOVrr32: NI = MakeMRInst(X86::MOVmr32, FrameIndex, MI); break;
134     case X86::MOVri8:  NI = MakeMIInst(X86::MOVmi8 , FrameIndex, MI); break;
135     case X86::MOVri16: NI = MakeMIInst(X86::MOVmi16, FrameIndex, MI); break;
136     case X86::MOVri32: NI = MakeMIInst(X86::MOVmi32, FrameIndex, MI); break;
137     case X86::MULr8:   NI = MakeMInst(X86::MULm8 , FrameIndex, MI); break;
138     case X86::MULr16:  NI = MakeMInst(X86::MULm16, FrameIndex, MI); break;
139     case X86::MULr32:  NI = MakeMInst(X86::MULm32, FrameIndex, MI); break;
140     case X86::DIVr8:   NI = MakeMInst(X86::DIVm8 , FrameIndex, MI); break;
141     case X86::DIVr16:  NI = MakeMInst(X86::DIVm16, FrameIndex, MI); break;
142     case X86::DIVr32:  NI = MakeMInst(X86::DIVm32, FrameIndex, MI); break;
143     case X86::IDIVr8:  NI = MakeMInst(X86::IDIVm8 , FrameIndex, MI); break;
144     case X86::IDIVr16: NI = MakeMInst(X86::IDIVm16, FrameIndex, MI); break;
145     case X86::IDIVr32: NI = MakeMInst(X86::IDIVm32, FrameIndex, MI); break;
146     case X86::NEGr8:   NI = MakeMInst(X86::NEGm8 , FrameIndex, MI); break;
147     case X86::NEGr16:  NI = MakeMInst(X86::NEGm16, FrameIndex, MI); break;
148     case X86::NEGr32:  NI = MakeMInst(X86::NEGm32, FrameIndex, MI); break;
149     case X86::NOTr8:   NI = MakeMInst(X86::NOTm8 , FrameIndex, MI); break;
150     case X86::NOTr16:  NI = MakeMInst(X86::NOTm16, FrameIndex, MI); break;
151     case X86::NOTr32:  NI = MakeMInst(X86::NOTm32, FrameIndex, MI); break;
152     case X86::INCr8:   NI = MakeMInst(X86::INCm8 , FrameIndex, MI); break;
153     case X86::INCr16:  NI = MakeMInst(X86::INCm16, FrameIndex, MI); break;
154     case X86::INCr32:  NI = MakeMInst(X86::INCm32, FrameIndex, MI); break;
155     case X86::DECr8:   NI = MakeMInst(X86::DECm8 , FrameIndex, MI); break;
156     case X86::DECr16:  NI = MakeMInst(X86::DECm16, FrameIndex, MI); break;
157     case X86::DECr32:  NI = MakeMInst(X86::DECm32, FrameIndex, MI); break;
158     case X86::ADDrr8:  NI = MakeMRInst(X86::ADDmr8 , FrameIndex, MI); break;
159     case X86::ADDrr16: NI = MakeMRInst(X86::ADDmr16, FrameIndex, MI); break;
160     case X86::ADDrr32: NI = MakeMRInst(X86::ADDmr32, FrameIndex, MI); break;
161     case X86::ADCrr32: NI = MakeMRInst(X86::ADCmr32, FrameIndex, MI); break;
162     case X86::ADDri8:  NI = MakeMIInst(X86::ADDmi8 , FrameIndex, MI); break;
163     case X86::ADDri16: NI = MakeMIInst(X86::ADDmi16, FrameIndex, MI); break;
164     case X86::ADDri32: NI = MakeMIInst(X86::ADDmi32, FrameIndex, MI); break;
165     case X86::SUBrr8:  NI = MakeMRInst(X86::SUBmr8 , FrameIndex, MI); break;
166     case X86::SUBrr16: NI = MakeMRInst(X86::SUBmr16, FrameIndex, MI); break;
167     case X86::SUBrr32: NI = MakeMRInst(X86::SUBmr32, FrameIndex, MI); break;
168     case X86::SBBrr32: NI = MakeMRInst(X86::SBBmr32, FrameIndex, MI); break;
169     case X86::SUBri8:  NI = MakeMIInst(X86::SUBmi8 , FrameIndex, MI); break;
170     case X86::SUBri16: NI = MakeMIInst(X86::SUBmi16, FrameIndex, MI); break;
171     case X86::SUBri32: NI = MakeMIInst(X86::SUBmi32, FrameIndex, MI); break;
172     case X86::ANDrr8:  NI = MakeMRInst(X86::ANDmr8 , FrameIndex, MI); break;
173     case X86::ANDrr16: NI = MakeMRInst(X86::ANDmr16, FrameIndex, MI); break;
174     case X86::ANDrr32: NI = MakeMRInst(X86::ANDmr32, FrameIndex, MI); break;
175     case X86::ANDri8:  NI = MakeMIInst(X86::ANDmi8 , FrameIndex, MI); break;
176     case X86::ANDri16: NI = MakeMIInst(X86::ANDmi16, FrameIndex, MI); break;
177     case X86::ANDri32: NI = MakeMIInst(X86::ANDmi32, FrameIndex, MI); break;
178     case X86::CMPrr8:  NI = MakeMRInst(X86::CMPmr8 , FrameIndex, MI); break;
179     case X86::CMPrr16: NI = MakeMRInst(X86::CMPmr16, FrameIndex, MI); break;
180     case X86::CMPrr32: NI = MakeMRInst(X86::CMPmr32, FrameIndex, MI); break;
181     case X86::CMPri8:  NI = MakeMIInst(X86::CMPmi8 , FrameIndex, MI); break;
182     case X86::CMPri16: NI = MakeMIInst(X86::CMPmi16, FrameIndex, MI); break;
183     case X86::CMPri32: NI = MakeMIInst(X86::CMPmi32, FrameIndex, MI); break;
184     default: break; // Cannot fold
185     }
186   } else if (i == 1) {
187     switch(MI->getOpcode()) {
188     case X86::MOVrr8:  NI = MakeRMInst(X86::MOVrm8 , FrameIndex, MI); break;
189     case X86::MOVrr16: NI = MakeRMInst(X86::MOVrm16, FrameIndex, MI); break;
190     case X86::MOVrr32: NI = MakeRMInst(X86::MOVrm32, FrameIndex, MI); break;
191     case X86::ADDrr8:  NI = MakeRMInst(X86::ADDrm8 , FrameIndex, MI); break;
192     case X86::ADDrr16: NI = MakeRMInst(X86::ADDrm16, FrameIndex, MI); break;
193     case X86::ADDrr32: NI = MakeRMInst(X86::ADDrm32, FrameIndex, MI); break;
194     case X86::ADCrr32: NI = MakeRMInst(X86::ADCrm32, FrameIndex, MI); break;
195     case X86::SUBrr8:  NI = MakeRMInst(X86::SUBrm8 , FrameIndex, MI); break;
196     case X86::SUBrr16: NI = MakeRMInst(X86::SUBrm16, FrameIndex, MI); break;
197     case X86::SUBrr32: NI = MakeRMInst(X86::SUBrm32, FrameIndex, MI); break;
198     case X86::SBBrr32: NI = MakeRMInst(X86::SBBrm32, FrameIndex, MI); break;
199     case X86::ANDrr8:  NI = MakeRMInst(X86::ANDrm8 , FrameIndex, MI); break;
200     case X86::ANDrr16: NI = MakeRMInst(X86::ANDrm16, FrameIndex, MI); break;
201     case X86::ANDrr32: NI = MakeRMInst(X86::ANDrm32, FrameIndex, MI); break;
202     case X86::IMULrr16:NI = MakeRMInst(X86::IMULrm16, FrameIndex, MI); break;
203     case X86::IMULrr32:NI = MakeRMInst(X86::IMULrm32, FrameIndex, MI); break;
204     case X86::IMULrri16: NI = MakeRMIInst(X86::IMULrmi16, FrameIndex, MI);break;
205     case X86::IMULrri32: NI = MakeRMIInst(X86::IMULrmi32, FrameIndex, MI);break;
206     case X86::CMPrr8:  NI = MakeRMInst(X86::CMPrm8 , FrameIndex, MI); break;
207     case X86::CMPrr16: NI = MakeRMInst(X86::CMPrm16, FrameIndex, MI); break;
208     case X86::CMPrr32: NI = MakeRMInst(X86::CMPrm32, FrameIndex, MI); break;
209
210     case X86::MOVSXr16r8: NI = MakeRMInst(X86::MOVSXr16m8 , FrameIndex, MI); break;
211     case X86::MOVSXr32r8: NI = MakeRMInst(X86::MOVSXr32m8, FrameIndex, MI); break;
212     case X86::MOVSXr32r16:NI = MakeRMInst(X86::MOVSXr32m16, FrameIndex, MI); break;
213     case X86::MOVZXr16r8: NI = MakeRMInst(X86::MOVZXr16m8 , FrameIndex, MI); break;
214     case X86::MOVZXr32r8: NI = MakeRMInst(X86::MOVZXr32m8, FrameIndex, MI); break;
215     case X86::MOVZXr32r16:NI = MakeRMInst(X86::MOVZXr32m16, FrameIndex, MI); break;
216     default: break;
217     }
218   }
219   if (NI) {
220     MI = MBB.insert(MBB.erase(MI), NI);
221     return true;
222   } else {
223     if (PrintFailedFusing)
224       std::cerr << "We failed to fuse: " << *MI;
225     return false;
226   }
227 }
228
229 //===----------------------------------------------------------------------===//
230 // Stack Frame Processing methods
231 //===----------------------------------------------------------------------===//
232
233 // hasFP - Return true if the specified function should have a dedicated frame
234 // pointer register.  This is true if the function has variable sized allocas or
235 // if frame pointer elimination is disabled.
236 //
237 static bool hasFP(MachineFunction &MF) {
238   return NoFPElim || MF.getFrameInfo()->hasVarSizedObjects();
239 }
240
241 void X86RegisterInfo::
242 eliminateCallFramePseudoInstr(MachineFunction &MF, MachineBasicBlock &MBB,
243                               MachineBasicBlock::iterator I) const {
244   if (hasFP(MF)) {
245     // If we have a frame pointer, turn the adjcallstackup instruction into a
246     // 'sub ESP, <amt>' and the adjcallstackdown instruction into 'add ESP,
247     // <amt>'
248     MachineInstr *Old = I;
249     unsigned Amount = Old->getOperand(0).getImmedValue();
250     if (Amount != 0) {
251       // We need to keep the stack aligned properly.  To do this, we round the
252       // amount of space needed for the outgoing arguments up to the next
253       // alignment boundary.
254       unsigned Align = MF.getTarget().getFrameInfo().getStackAlignment();
255       Amount = (Amount+Align-1)/Align*Align;
256
257       MachineInstr *New;
258       if (Old->getOpcode() == X86::ADJCALLSTACKDOWN) {
259         New=BuildMI(X86::SUBri32, 1, X86::ESP, MOTy::UseAndDef).addZImm(Amount);
260       } else {
261         assert(Old->getOpcode() == X86::ADJCALLSTACKUP);
262         New=BuildMI(X86::ADDri32, 1, X86::ESP, MOTy::UseAndDef).addZImm(Amount);
263       }
264
265       // Replace the pseudo instruction with a new instruction...
266       MBB.insert(I, New);
267     }
268   }
269
270   MBB.erase(I);
271 }
272
273 void X86RegisterInfo::eliminateFrameIndex(MachineFunction &MF,
274                                          MachineBasicBlock::iterator II) const {
275   unsigned i = 0;
276   MachineInstr &MI = *II;
277   while (!MI.getOperand(i).isFrameIndex()) {
278     ++i;
279     assert(i < MI.getNumOperands() && "Instr doesn't have FrameIndex operand!");
280   }
281
282   int FrameIndex = MI.getOperand(i).getFrameIndex();
283
284   // This must be part of a four operand memory reference.  Replace the
285   // FrameIndex with base register with EBP.  Add add an offset to the offset.
286   MI.SetMachineOperandReg(i, hasFP(MF) ? X86::EBP : X86::ESP);
287
288   // Now add the frame object offset to the offset from EBP.
289   int Offset = MF.getFrameInfo()->getObjectOffset(FrameIndex) +
290                MI.getOperand(i+3).getImmedValue()+4;
291
292   if (!hasFP(MF))
293     Offset += MF.getFrameInfo()->getStackSize();
294   else
295     Offset += 4;  // Skip the saved EBP
296
297   MI.SetMachineOperandConst(i+3, MachineOperand::MO_SignExtendedImmed, Offset);
298 }
299
300 void
301 X86RegisterInfo::processFunctionBeforeFrameFinalized(MachineFunction &MF) const{
302   if (hasFP(MF)) {
303     // Create a frame entry for the EBP register that must be saved.
304     int FrameIdx = MF.getFrameInfo()->CreateFixedObject(4, -8);
305     assert(FrameIdx == MF.getFrameInfo()->getObjectIndexBegin() &&
306            "Slot for EBP register must be last in order to be found!");
307   }
308 }
309
310 void X86RegisterInfo::emitPrologue(MachineFunction &MF) const {
311   MachineBasicBlock &MBB = MF.front();   // Prolog goes in entry BB
312   MachineBasicBlock::iterator MBBI = MBB.begin();
313   MachineFrameInfo *MFI = MF.getFrameInfo();
314   MachineInstr *MI;
315
316   // Get the number of bytes to allocate from the FrameInfo
317   unsigned NumBytes = MFI->getStackSize();
318   if (hasFP(MF)) {
319     // Get the offset of the stack slot for the EBP register... which is
320     // guaranteed to be the last slot by processFunctionBeforeFrameFinalized.
321     int EBPOffset = MFI->getObjectOffset(MFI->getObjectIndexBegin())+4;
322
323     if (NumBytes) {   // adjust stack pointer: ESP -= numbytes
324       MI= BuildMI(X86::SUBri32, 1, X86::ESP, MOTy::UseAndDef).addZImm(NumBytes);
325       MBB.insert(MBBI, MI);
326     }
327
328     // Save EBP into the appropriate stack slot...
329     MI = addRegOffset(BuildMI(X86::MOVmr32, 5),    // mov [ESP-<offset>], EBP
330                       X86::ESP, EBPOffset+NumBytes).addReg(X86::EBP);
331     MBB.insert(MBBI, MI);
332
333     // Update EBP with the new base value...
334     if (NumBytes == 4)    // mov EBP, ESP
335       MI = BuildMI(X86::MOVrr32, 2, X86::EBP).addReg(X86::ESP);
336     else                  // lea EBP, [ESP+StackSize]
337       MI = addRegOffset(BuildMI(X86::LEAr32, 5, X86::EBP), X86::ESP,NumBytes-4);
338
339     MBB.insert(MBBI, MI);
340
341   } else {
342     if (MFI->hasCalls()) {
343       // When we have no frame pointer, we reserve argument space for call sites
344       // in the function immediately on entry to the current function.  This
345       // eliminates the need for add/sub ESP brackets around call sites.
346       //
347       NumBytes += MFI->getMaxCallFrameSize();
348       
349       // Round the size to a multiple of the alignment (don't forget the 4 byte
350       // offset though).
351       unsigned Align = MF.getTarget().getFrameInfo().getStackAlignment();
352       NumBytes = ((NumBytes+4)+Align-1)/Align*Align - 4;
353     }
354
355     // Update frame info to pretend that this is part of the stack...
356     MFI->setStackSize(NumBytes);
357
358     if (NumBytes) {
359       // adjust stack pointer: ESP -= numbytes
360       MI= BuildMI(X86::SUBri32, 1, X86::ESP, MOTy::UseAndDef).addZImm(NumBytes);
361       MBB.insert(MBBI, MI);
362     }
363   }
364 }
365
366 void X86RegisterInfo::emitEpilogue(MachineFunction &MF,
367                                    MachineBasicBlock &MBB) const {
368   const MachineFrameInfo *MFI = MF.getFrameInfo();
369   MachineBasicBlock::iterator MBBI = prior(MBB.end());
370   MachineInstr *MI;
371   assert(MBBI->getOpcode() == X86::RET &&
372          "Can only insert epilog into returning blocks");
373
374   if (hasFP(MF)) {
375     // Get the offset of the stack slot for the EBP register... which is
376     // guaranteed to be the last slot by processFunctionBeforeFrameFinalized.
377     int EBPOffset = MFI->getObjectOffset(MFI->getObjectIndexEnd()-1)+4;
378     
379     // mov ESP, EBP
380     MI = BuildMI(X86::MOVrr32, 1,X86::ESP).addReg(X86::EBP);
381     MBB.insert(MBBI, MI);
382
383     // pop EBP
384     MI = BuildMI(X86::POPr32, 0, X86::EBP);
385     MBB.insert(MBBI, MI);
386   } else {
387     // Get the number of bytes allocated from the FrameInfo...
388     unsigned NumBytes = MFI->getStackSize();
389
390     if (NumBytes) {    // adjust stack pointer back: ESP += numbytes
391       MI =BuildMI(X86::ADDri32, 1, X86::ESP, MOTy::UseAndDef).addZImm(NumBytes);
392       MBB.insert(MBBI, MI);
393     }
394   }
395 }
396
397 #include "X86GenRegisterInfo.inc"
398
399 const TargetRegisterClass*
400 X86RegisterInfo::getRegClassForType(const Type* Ty) const {
401   switch (Ty->getPrimitiveID()) {
402   case Type::LongTyID:
403   case Type::ULongTyID: assert(0 && "Long values can't fit in registers!");
404   default:              assert(0 && "Invalid type to getClass!");
405   case Type::BoolTyID:
406   case Type::SByteTyID:
407   case Type::UByteTyID:   return &R8Instance;
408   case Type::ShortTyID:
409   case Type::UShortTyID:  return &R16Instance;
410   case Type::IntTyID:
411   case Type::UIntTyID:
412   case Type::PointerTyID: return &R32Instance;
413     
414   case Type::FloatTyID:
415   case Type::DoubleTyID: return &RFPInstance;
416   }
417 }