LLVM API Documentation

X86FloatingPoint.cpp

Go to the documentation of this file.
00001 //===-- X86FloatingPoint.cpp - Floating point Reg -> Stack converter ------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file defines the pass which converts floating point instructions from
00011 // virtual registers into register stack instructions.  This pass uses live
00012 // variable information to indicate where the FPn registers are used and their
00013 // lifetimes.
00014 //
00015 // This pass is hampered by the lack of decent CFG manipulation routines for
00016 // machine code.  In particular, this wants to be able to split critical edges
00017 // as necessary, traverse the machine basic block CFG in depth-first order, and
00018 // allow there to be multiple machine basic blocks for each LLVM basicblock
00019 // (needed for critical edge splitting).
00020 //
00021 // In particular, this pass currently barfs on critical edges.  Because of this,
00022 // it requires the instruction selector to insert FP_REG_KILL instructions on
00023 // the exits of any basic block that has critical edges going from it, or which
00024 // branch to a critical basic block.
00025 //
00026 // FIXME: this is not implemented yet.  The stackifier pass only works on local
00027 // basic blocks.
00028 //
00029 //===----------------------------------------------------------------------===//
00030 
00031 #define DEBUG_TYPE "fp"
00032 #include "X86.h"
00033 #include "X86InstrInfo.h"
00034 #include "llvm/CodeGen/MachineFunctionPass.h"
00035 #include "llvm/CodeGen/MachineInstrBuilder.h"
00036 #include "llvm/CodeGen/LiveVariables.h"
00037 #include "llvm/CodeGen/Passes.h"
00038 #include "llvm/Target/TargetInstrInfo.h"
00039 #include "llvm/Target/TargetMachine.h"
00040 #include "llvm/Support/Debug.h"
00041 #include "llvm/ADT/DepthFirstIterator.h"
00042 #include "llvm/ADT/Statistic.h"
00043 #include "llvm/ADT/STLExtras.h"
00044 #include <algorithm>
00045 #include <iostream>
00046 #include <set>
00047 using namespace llvm;
00048 
00049 namespace {
00050   Statistic<> NumFXCH("x86-codegen", "Number of fxch instructions inserted");
00051   Statistic<> NumFP  ("x86-codegen", "Number of floating point instructions");
00052 
00053   struct FPS : public MachineFunctionPass {
00054     virtual bool runOnMachineFunction(MachineFunction &MF);
00055 
00056     virtual const char *getPassName() const { return "X86 FP Stackifier"; }
00057 
00058     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00059       AU.addRequired<LiveVariables>();
00060       MachineFunctionPass::getAnalysisUsage(AU);
00061     }
00062   private:
00063     LiveVariables     *LV;    // Live variable info for current function...
00064     MachineBasicBlock *MBB;   // Current basic block
00065     unsigned Stack[8];        // FP<n> Registers in each stack slot...
00066     unsigned RegMap[8];       // Track which stack slot contains each register
00067     unsigned StackTop;        // The current top of the FP stack.
00068 
00069     void dumpStack() const {
00070       std::cerr << "Stack contents:";
00071       for (unsigned i = 0; i != StackTop; ++i) {
00072         std::cerr << " FP" << Stack[i];
00073         assert(RegMap[Stack[i]] == i && "Stack[] doesn't match RegMap[]!");
00074       }
00075       std::cerr << "\n";
00076     }
00077   private:
00078     // getSlot - Return the stack slot number a particular register number is
00079     // in...
00080     unsigned getSlot(unsigned RegNo) const {
00081       assert(RegNo < 8 && "Regno out of range!");
00082       return RegMap[RegNo];
00083     }
00084 
00085     // getStackEntry - Return the X86::FP<n> register in register ST(i)
00086     unsigned getStackEntry(unsigned STi) const {
00087       assert(STi < StackTop && "Access past stack top!");
00088       return Stack[StackTop-1-STi];
00089     }
00090 
00091     // getSTReg - Return the X86::ST(i) register which contains the specified
00092     // FP<RegNo> register
00093     unsigned getSTReg(unsigned RegNo) const {
00094       return StackTop - 1 - getSlot(RegNo) + llvm::X86::ST0;
00095     }
00096 
00097     // pushReg - Push the specified FP<n> register onto the stack
00098     void pushReg(unsigned Reg) {
00099       assert(Reg < 8 && "Register number out of range!");
00100       assert(StackTop < 8 && "Stack overflow!");
00101       Stack[StackTop] = Reg;
00102       RegMap[Reg] = StackTop++;
00103     }
00104 
00105     bool isAtTop(unsigned RegNo) const { return getSlot(RegNo) == StackTop-1; }
00106     void moveToTop(unsigned RegNo, MachineBasicBlock::iterator &I) {
00107       if (!isAtTop(RegNo)) {
00108         unsigned Slot = getSlot(RegNo);
00109         unsigned STReg = getSTReg(RegNo);
00110         unsigned RegOnTop = getStackEntry(0);
00111 
00112         // Swap the slots the regs are in
00113         std::swap(RegMap[RegNo], RegMap[RegOnTop]);
00114 
00115         // Swap stack slot contents
00116         assert(RegMap[RegOnTop] < StackTop);
00117         std::swap(Stack[RegMap[RegOnTop]], Stack[StackTop-1]);
00118 
00119         // Emit an fxch to update the runtime processors version of the state
00120         BuildMI(*MBB, I, X86::FXCH, 1).addReg(STReg);
00121         NumFXCH++;
00122       }
00123     }
00124 
00125     void duplicateToTop(unsigned RegNo, unsigned AsReg, MachineInstr *I) {
00126       unsigned STReg = getSTReg(RegNo);
00127       pushReg(AsReg);   // New register on top of stack
00128 
00129       BuildMI(*MBB, I, X86::FLDrr, 1).addReg(STReg);
00130     }
00131 
00132     // popStackAfter - Pop the current value off of the top of the FP stack
00133     // after the specified instruction.
00134     void popStackAfter(MachineBasicBlock::iterator &I);
00135 
00136     // freeStackSlotAfter - Free the specified register from the register stack,
00137     // so that it is no longer in a register.  If the register is currently at
00138     // the top of the stack, we just pop the current instruction, otherwise we
00139     // store the current top-of-stack into the specified slot, then pop the top
00140     // of stack.
00141     void freeStackSlotAfter(MachineBasicBlock::iterator &I, unsigned Reg);
00142 
00143     bool processBasicBlock(MachineFunction &MF, MachineBasicBlock &MBB);
00144 
00145     void handleZeroArgFP(MachineBasicBlock::iterator &I);
00146     void handleOneArgFP(MachineBasicBlock::iterator &I);
00147     void handleOneArgFPRW(MachineBasicBlock::iterator &I);
00148     void handleTwoArgFP(MachineBasicBlock::iterator &I);
00149     void handleCompareFP(MachineBasicBlock::iterator &I);
00150     void handleCondMovFP(MachineBasicBlock::iterator &I);
00151     void handleSpecialFP(MachineBasicBlock::iterator &I);
00152   };
00153 }
00154 
00155 FunctionPass *llvm::createX86FloatingPointStackifierPass() { return new FPS(); }
00156 
00157 /// runOnMachineFunction - Loop over all of the basic blocks, transforming FP
00158 /// register references into FP stack references.
00159 ///
00160 bool FPS::runOnMachineFunction(MachineFunction &MF) {
00161   // We only need to run this pass if there are any FP registers used in this
00162   // function.  If it is all integer, there is nothing for us to do!
00163   const bool *PhysRegsUsed = MF.getUsedPhysregs();
00164   bool FPIsUsed = false;
00165 
00166   assert(X86::FP6 == X86::FP0+6 && "Register enums aren't sorted right!");
00167   for (unsigned i = 0; i <= 6; ++i)
00168     if (PhysRegsUsed[X86::FP0+i]) {
00169       FPIsUsed = true;
00170       break;
00171     }
00172 
00173   // Early exit.
00174   if (!FPIsUsed) return false;
00175 
00176   LV = &getAnalysis<LiveVariables>();
00177   StackTop = 0;
00178 
00179   // Process the function in depth first order so that we process at least one
00180   // of the predecessors for every reachable block in the function.
00181   std::set<MachineBasicBlock*> Processed;
00182   MachineBasicBlock *Entry = MF.begin();
00183 
00184   bool Changed = false;
00185   for (df_ext_iterator<MachineBasicBlock*, std::set<MachineBasicBlock*> >
00186          I = df_ext_begin(Entry, Processed), E = df_ext_end(Entry, Processed);
00187        I != E; ++I)
00188     Changed |= processBasicBlock(MF, **I);
00189 
00190   return Changed;
00191 }
00192 
00193 /// processBasicBlock - Loop over all of the instructions in the basic block,
00194 /// transforming FP instructions into their stack form.
00195 ///
00196 bool FPS::processBasicBlock(MachineFunction &MF, MachineBasicBlock &BB) {
00197   const TargetInstrInfo &TII = *MF.getTarget().getInstrInfo();
00198   bool Changed = false;
00199   MBB = &BB;
00200 
00201   for (MachineBasicBlock::iterator I = BB.begin(); I != BB.end(); ++I) {
00202     MachineInstr *MI = I;
00203     unsigned Flags = TII.get(MI->getOpcode()).TSFlags;
00204     if ((Flags & X86II::FPTypeMask) == X86II::NotFP)
00205       continue;  // Efficiently ignore non-fp insts!
00206 
00207     MachineInstr *PrevMI = 0;
00208     if (I != BB.begin())
00209         PrevMI = prior(I);
00210 
00211     ++NumFP;  // Keep track of # of pseudo instrs
00212     DEBUG(std::cerr << "\nFPInst:\t"; MI->print(std::cerr, &(MF.getTarget())));
00213 
00214     // Get dead variables list now because the MI pointer may be deleted as part
00215     // of processing!
00216     LiveVariables::killed_iterator IB, IE;
00217     tie(IB, IE) = LV->dead_range(MI);
00218 
00219     DEBUG(
00220       const MRegisterInfo *MRI = MF.getTarget().getRegisterInfo();
00221       LiveVariables::killed_iterator I = LV->killed_begin(MI);
00222       LiveVariables::killed_iterator E = LV->killed_end(MI);
00223       if (I != E) {
00224         std::cerr << "Killed Operands:";
00225         for (; I != E; ++I)
00226           std::cerr << " %" << MRI->getName(*I);
00227         std::cerr << "\n";
00228       }
00229     );
00230 
00231     switch (Flags & X86II::FPTypeMask) {
00232     case X86II::ZeroArgFP:  handleZeroArgFP(I); break;
00233     case X86II::OneArgFP:   handleOneArgFP(I);  break;  // fstp ST(0)
00234     case X86II::OneArgFPRW: handleOneArgFPRW(I); break; // ST(0) = fsqrt(ST(0))
00235     case X86II::TwoArgFP:   handleTwoArgFP(I); break;
00236     case X86II::CompareFP:  handleCompareFP(I); break;
00237     case X86II::CondMovFP:  handleCondMovFP(I); break;
00238     case X86II::SpecialFP:  handleSpecialFP(I); break;
00239     default: assert(0 && "Unknown FP Type!");
00240     }
00241 
00242     // Check to see if any of the values defined by this instruction are dead
00243     // after definition.  If so, pop them.
00244     for (; IB != IE; ++IB) {
00245       unsigned Reg = *IB;
00246       if (Reg >= X86::FP0 && Reg <= X86::FP6) {
00247         DEBUG(std::cerr << "Register FP#" << Reg-X86::FP0 << " is dead!\n");
00248         freeStackSlotAfter(I, Reg-X86::FP0);
00249       }
00250     }
00251 
00252     // Print out all of the instructions expanded to if -debug
00253     DEBUG(
00254       MachineBasicBlock::iterator PrevI(PrevMI);
00255       if (I == PrevI) {
00256         std::cerr << "Just deleted pseudo instruction\n";
00257       } else {
00258         MachineBasicBlock::iterator Start = I;
00259         // Rewind to first instruction newly inserted.
00260         while (Start != BB.begin() && prior(Start) != PrevI) --Start;
00261         std::cerr << "Inserted instructions:\n\t";
00262         Start->print(std::cerr, &MF.getTarget());
00263         while (++Start != next(I));
00264       }
00265       dumpStack();
00266     );
00267 
00268     Changed = true;
00269   }
00270 
00271   assert(StackTop == 0 && "Stack not empty at end of basic block?");
00272   return Changed;
00273 }
00274 
00275 //===----------------------------------------------------------------------===//
00276 // Efficient Lookup Table Support
00277 //===----------------------------------------------------------------------===//
00278 
00279 namespace {
00280   struct TableEntry {
00281     unsigned from;
00282     unsigned to;
00283     bool operator<(const TableEntry &TE) const { return from < TE.from; }
00284     friend bool operator<(const TableEntry &TE, unsigned V) {
00285       return TE.from < V;
00286     }
00287     friend bool operator<(unsigned V, const TableEntry &TE) {
00288       return V < TE.from;
00289     }
00290   };
00291 }
00292 
00293 static bool TableIsSorted(const TableEntry *Table, unsigned NumEntries) {
00294   for (unsigned i = 0; i != NumEntries-1; ++i)
00295     if (!(Table[i] < Table[i+1])) return false;
00296   return true;
00297 }
00298 
00299 static int Lookup(const TableEntry *Table, unsigned N, unsigned Opcode) {
00300   const TableEntry *I = std::lower_bound(Table, Table+N, Opcode);
00301   if (I != Table+N && I->from == Opcode)
00302     return I->to;
00303   return -1;
00304 }
00305 
00306 #define ARRAY_SIZE(TABLE)  \
00307    (sizeof(TABLE)/sizeof(TABLE[0]))
00308 
00309 #ifdef NDEBUG
00310 #define ASSERT_SORTED(TABLE)
00311 #else
00312 #define ASSERT_SORTED(TABLE)                                              \
00313   { static bool TABLE##Checked = false;                                   \
00314     if (!TABLE##Checked)                                                  \
00315        assert(TableIsSorted(TABLE, ARRAY_SIZE(TABLE)) &&                  \
00316               "All lookup tables must be sorted for efficient access!");  \
00317   }
00318 #endif
00319 
00320 //===----------------------------------------------------------------------===//
00321 // Register File -> Register Stack Mapping Methods
00322 //===----------------------------------------------------------------------===//
00323 
00324 // OpcodeTable - Sorted map of register instructions to their stack version.
00325 // The first element is an register file pseudo instruction, the second is the
00326 // concrete X86 instruction which uses the register stack.
00327 //
00328 static const TableEntry OpcodeTable[] = {
00329   { X86::FpABS     , X86::FABS     },
00330   { X86::FpADD32m  , X86::FADD32m  },
00331   { X86::FpADD64m  , X86::FADD64m  },
00332   { X86::FpCHS     , X86::FCHS     },
00333   { X86::FpCMOVB   , X86::FCMOVB   },
00334   { X86::FpCMOVBE  , X86::FCMOVBE  },
00335   { X86::FpCMOVE   , X86::FCMOVE   },
00336   { X86::FpCMOVNB  , X86::FCMOVNB  },
00337   { X86::FpCMOVNBE , X86::FCMOVNBE },
00338   { X86::FpCMOVNE  , X86::FCMOVNE  },
00339   { X86::FpCMOVNP  , X86::FCMOVNP  },
00340   { X86::FpCMOVP   , X86::FCMOVP   },
00341   { X86::FpCOS     , X86::FCOS     },
00342   { X86::FpDIV32m  , X86::FDIV32m  },
00343   { X86::FpDIV64m  , X86::FDIV64m  },
00344   { X86::FpDIVR32m , X86::FDIVR32m },
00345   { X86::FpDIVR64m , X86::FDIVR64m },
00346   { X86::FpIADD16m , X86::FIADD16m },
00347   { X86::FpIADD32m , X86::FIADD32m },
00348   { X86::FpIDIV16m , X86::FIDIV16m },
00349   { X86::FpIDIV32m , X86::FIDIV32m },
00350   { X86::FpIDIVR16m, X86::FIDIVR16m},
00351   { X86::FpIDIVR32m, X86::FIDIVR32m},
00352   { X86::FpILD16m  , X86::FILD16m  },
00353   { X86::FpILD32m  , X86::FILD32m  },
00354   { X86::FpILD64m  , X86::FILD64m  },
00355   { X86::FpIMUL16m , X86::FIMUL16m },
00356   { X86::FpIMUL32m , X86::FIMUL32m },
00357   { X86::FpIST16m  , X86::FIST16m  },
00358   { X86::FpIST32m  , X86::FIST32m  },
00359   { X86::FpIST64m  , X86::FISTP64m },
00360   { X86::FpISTT16m , X86::FISTTP16m},
00361   { X86::FpISTT32m , X86::FISTTP32m},
00362   { X86::FpISTT64m , X86::FISTTP64m},
00363   { X86::FpISUB16m , X86::FISUB16m },
00364   { X86::FpISUB32m , X86::FISUB32m },
00365   { X86::FpISUBR16m, X86::FISUBR16m},
00366   { X86::FpISUBR32m, X86::FISUBR32m},
00367   { X86::FpLD0     , X86::FLD0     },
00368   { X86::FpLD1     , X86::FLD1     },
00369   { X86::FpLD32m   , X86::FLD32m   },
00370   { X86::FpLD64m   , X86::FLD64m   },
00371   { X86::FpMUL32m  , X86::FMUL32m  },
00372   { X86::FpMUL64m  , X86::FMUL64m  },
00373   { X86::FpSIN     , X86::FSIN     },
00374   { X86::FpSQRT    , X86::FSQRT    },
00375   { X86::FpST32m   , X86::FST32m   },
00376   { X86::FpST64m   , X86::FST64m   },
00377   { X86::FpSUB32m  , X86::FSUB32m  },
00378   { X86::FpSUB64m  , X86::FSUB64m  },
00379   { X86::FpSUBR32m , X86::FSUBR32m },
00380   { X86::FpSUBR64m , X86::FSUBR64m },
00381   { X86::FpTST     , X86::FTST     },
00382   { X86::FpUCOMIr  , X86::FUCOMIr  },
00383   { X86::FpUCOMr   , X86::FUCOMr   },
00384 };
00385 
00386 static unsigned getConcreteOpcode(unsigned Opcode) {
00387   ASSERT_SORTED(OpcodeTable);
00388   int Opc = Lookup(OpcodeTable, ARRAY_SIZE(OpcodeTable), Opcode);
00389   assert(Opc != -1 && "FP Stack instruction not in OpcodeTable!");
00390   return Opc;
00391 }
00392 
00393 //===----------------------------------------------------------------------===//
00394 // Helper Methods
00395 //===----------------------------------------------------------------------===//
00396 
00397 // PopTable - Sorted map of instructions to their popping version.  The first
00398 // element is an instruction, the second is the version which pops.
00399 //
00400 static const TableEntry PopTable[] = {
00401   { X86::FADDrST0 , X86::FADDPrST0  },
00402 
00403   { X86::FDIVRrST0, X86::FDIVRPrST0 },
00404   { X86::FDIVrST0 , X86::FDIVPrST0  },
00405 
00406   { X86::FIST16m  , X86::FISTP16m   },
00407   { X86::FIST32m  , X86::FISTP32m   },
00408 
00409   { X86::FMULrST0 , X86::FMULPrST0  },
00410 
00411   { X86::FST32m   , X86::FSTP32m    },
00412   { X86::FST64m   , X86::FSTP64m    },
00413   { X86::FSTrr    , X86::FSTPrr     },
00414 
00415   { X86::FSUBRrST0, X86::FSUBRPrST0 },
00416   { X86::FSUBrST0 , X86::FSUBPrST0  },
00417 
00418   { X86::FUCOMIr  , X86::FUCOMIPr   },
00419 
00420   { X86::FUCOMPr  , X86::FUCOMPPr   },
00421   { X86::FUCOMr   , X86::FUCOMPr    },
00422 };
00423 
00424 /// popStackAfter - Pop the current value off of the top of the FP stack after
00425 /// the specified instruction.  This attempts to be sneaky and combine the pop
00426 /// into the instruction itself if possible.  The iterator is left pointing to
00427 /// the last instruction, be it a new pop instruction inserted, or the old
00428 /// instruction if it was modified in place.
00429 ///
00430 void FPS::popStackAfter(MachineBasicBlock::iterator &I) {
00431   ASSERT_SORTED(PopTable);
00432   assert(StackTop > 0 && "Cannot pop empty stack!");
00433   RegMap[Stack[--StackTop]] = ~0;     // Update state
00434 
00435   // Check to see if there is a popping version of this instruction...
00436   int Opcode = Lookup(PopTable, ARRAY_SIZE(PopTable), I->getOpcode());
00437   if (Opcode != -1) {
00438     I->setOpcode(Opcode);
00439     if (Opcode == X86::FUCOMPPr)
00440       I->RemoveOperand(0);
00441 
00442   } else {    // Insert an explicit pop
00443     I = BuildMI(*MBB, ++I, X86::FSTPrr, 1).addReg(X86::ST0);
00444   }
00445 }
00446 
00447 /// freeStackSlotAfter - Free the specified register from the register stack, so
00448 /// that it is no longer in a register.  If the register is currently at the top
00449 /// of the stack, we just pop the current instruction, otherwise we store the
00450 /// current top-of-stack into the specified slot, then pop the top of stack.
00451 void FPS::freeStackSlotAfter(MachineBasicBlock::iterator &I, unsigned FPRegNo) {
00452   if (getStackEntry(0) == FPRegNo) {  // already at the top of stack? easy.
00453     popStackAfter(I);
00454     return;
00455   }
00456 
00457   // Otherwise, store the top of stack into the dead slot, killing the operand
00458   // without having to add in an explicit xchg then pop.
00459   //
00460   unsigned STReg    = getSTReg(FPRegNo);
00461   unsigned OldSlot  = getSlot(FPRegNo);
00462   unsigned TopReg   = Stack[StackTop-1];
00463   Stack[OldSlot]    = TopReg;
00464   RegMap[TopReg]    = OldSlot;
00465   RegMap[FPRegNo]   = ~0;
00466   Stack[--StackTop] = ~0;
00467   I = BuildMI(*MBB, ++I, X86::FSTPrr, 1).addReg(STReg);
00468 }
00469 
00470 
00471 static unsigned getFPReg(const MachineOperand &MO) {
00472   assert(MO.isRegister() && "Expected an FP register!");
00473   unsigned Reg = MO.getReg();
00474   assert(Reg >= X86::FP0 && Reg <= X86::FP6 && "Expected FP register!");
00475   return Reg - X86::FP0;
00476 }
00477 
00478 
00479 //===----------------------------------------------------------------------===//
00480 // Instruction transformation implementation
00481 //===----------------------------------------------------------------------===//
00482 
00483 /// handleZeroArgFP - ST(0) = fld0    ST(0) = flds <mem>
00484 ///
00485 void FPS::handleZeroArgFP(MachineBasicBlock::iterator &I) {
00486   MachineInstr *MI = I;
00487   unsigned DestReg = getFPReg(MI->getOperand(0));
00488 
00489   // Change from the pseudo instruction to the concrete instruction.
00490   MI->RemoveOperand(0);   // Remove the explicit ST(0) operand
00491   MI->setOpcode(getConcreteOpcode(MI->getOpcode()));
00492   
00493   // Result gets pushed on the stack.
00494   pushReg(DestReg);
00495 }
00496 
00497 /// handleOneArgFP - fst <mem>, ST(0)
00498 ///
00499 void FPS::handleOneArgFP(MachineBasicBlock::iterator &I) {
00500   MachineInstr *MI = I;
00501   assert((MI->getNumOperands() == 5 || MI->getNumOperands() == 1) &&
00502          "Can only handle fst* & ftst instructions!");
00503 
00504   // Is this the last use of the source register?
00505   unsigned Reg = getFPReg(MI->getOperand(MI->getNumOperands()-1));
00506   bool KillsSrc = LV->KillsRegister(MI, X86::FP0+Reg);
00507 
00508   // FISTP64m is strange because there isn't a non-popping versions.
00509   // If we have one _and_ we don't want to pop the operand, duplicate the value
00510   // on the stack instead of moving it.  This ensure that popping the value is
00511   // always ok.
00512   // Ditto FISTTP16m, FISTTP32m, FISTTP64m.
00513   //
00514   if (!KillsSrc &&
00515       (MI->getOpcode() == X86::FpIST64m ||
00516        MI->getOpcode() == X86::FpISTT16m ||
00517        MI->getOpcode() == X86::FpISTT32m ||
00518        MI->getOpcode() == X86::FpISTT64m)) {
00519     duplicateToTop(Reg, 7 /*temp register*/, I);
00520   } else {
00521     moveToTop(Reg, I);            // Move to the top of the stack...
00522   }
00523   
00524   // Convert from the pseudo instruction to the concrete instruction.
00525   MI->RemoveOperand(MI->getNumOperands()-1);    // Remove explicit ST(0) operand
00526   MI->setOpcode(getConcreteOpcode(MI->getOpcode()));
00527 
00528   if (MI->getOpcode() == X86::FISTP64m ||
00529       MI->getOpcode() == X86::FISTTP16m ||
00530       MI->getOpcode() == X86::FISTTP32m ||
00531       MI->getOpcode() == X86::FISTTP64m) {
00532     assert(StackTop > 0 && "Stack empty??");
00533     --StackTop;
00534   } else if (KillsSrc) { // Last use of operand?
00535     popStackAfter(I);
00536   }
00537 }
00538 
00539 
00540 /// handleOneArgFPRW: Handle instructions that read from the top of stack and
00541 /// replace the value with a newly computed value.  These instructions may have
00542 /// non-fp operands after their FP operands.
00543 ///
00544 ///  Examples:
00545 ///     R1 = fchs R2
00546 ///     R1 = fadd R2, [mem]
00547 ///
00548 void FPS::handleOneArgFPRW(MachineBasicBlock::iterator &I) {
00549   MachineInstr *MI = I;
00550   assert(MI->getNumOperands() >= 2 && "FPRW instructions must have 2 ops!!");
00551 
00552   // Is this the last use of the source register?
00553   unsigned Reg = getFPReg(MI->getOperand(1));
00554   bool KillsSrc = LV->KillsRegister(MI, X86::FP0+Reg);
00555 
00556   if (KillsSrc) {
00557     // If this is the last use of the source register, just make sure it's on
00558     // the top of the stack.
00559     moveToTop(Reg, I);
00560     assert(StackTop > 0 && "Stack cannot be empty!");
00561     --StackTop;
00562     pushReg(getFPReg(MI->getOperand(0)));
00563   } else {
00564     // If this is not the last use of the source register, _copy_ it to the top
00565     // of the stack.
00566     duplicateToTop(Reg, getFPReg(MI->getOperand(0)), I);
00567   }
00568 
00569   // Change from the pseudo instruction to the concrete instruction.
00570   MI->RemoveOperand(1);   // Drop the source operand.
00571   MI->RemoveOperand(0);   // Drop the destination operand.
00572   MI->setOpcode(getConcreteOpcode(MI->getOpcode()));
00573 }
00574 
00575 
00576 //===----------------------------------------------------------------------===//
00577 // Define tables of various ways to map pseudo instructions
00578 //
00579 
00580 // ForwardST0Table - Map: A = B op C  into: ST(0) = ST(0) op ST(i)
00581 static const TableEntry ForwardST0Table[] = {
00582   { X86::FpADD  , X86::FADDST0r },
00583   { X86::FpDIV  , X86::FDIVST0r },
00584   { X86::FpMUL  , X86::FMULST0r },
00585   { X86::FpSUB  , X86::FSUBST0r },
00586 };
00587 
00588 // ReverseST0Table - Map: A = B op C  into: ST(0) = ST(i) op ST(0)
00589 static const TableEntry ReverseST0Table[] = {
00590   { X86::FpADD  , X86::FADDST0r  },   // commutative
00591   { X86::FpDIV  , X86::FDIVRST0r },
00592   { X86::FpMUL  , X86::FMULST0r  },   // commutative
00593   { X86::FpSUB  , X86::FSUBRST0r },
00594 };
00595 
00596 // ForwardSTiTable - Map: A = B op C  into: ST(i) = ST(0) op ST(i)
00597 static const TableEntry ForwardSTiTable[] = {
00598   { X86::FpADD  , X86::FADDrST0  },   // commutative
00599   { X86::FpDIV  , X86::FDIVRrST0 },
00600   { X86::FpMUL  , X86::FMULrST0  },   // commutative
00601   { X86::FpSUB  , X86::FSUBRrST0 },
00602 };
00603 
00604 // ReverseSTiTable - Map: A = B op C  into: ST(i) = ST(i) op ST(0)
00605 static const TableEntry ReverseSTiTable[] = {
00606   { X86::FpADD  , X86::FADDrST0 },
00607   { X86::FpDIV  , X86::FDIVrST0 },
00608   { X86::FpMUL  , X86::FMULrST0 },
00609   { X86::FpSUB  , X86::FSUBrST0 },
00610 };
00611 
00612 
00613 /// handleTwoArgFP - Handle instructions like FADD and friends which are virtual
00614 /// instructions which need to be simplified and possibly transformed.
00615 ///
00616 /// Result: ST(0) = fsub  ST(0), ST(i)
00617 ///         ST(i) = fsub  ST(0), ST(i)
00618 ///         ST(0) = fsubr ST(0), ST(i)
00619 ///         ST(i) = fsubr ST(0), ST(i)
00620 ///
00621 void FPS::handleTwoArgFP(MachineBasicBlock::iterator &I) {
00622   ASSERT_SORTED(ForwardST0Table); ASSERT_SORTED(ReverseST0Table);
00623   ASSERT_SORTED(ForwardSTiTable); ASSERT_SORTED(ReverseSTiTable);
00624   MachineInstr *MI = I;
00625 
00626   unsigned NumOperands = MI->getNumOperands();
00627   assert(NumOperands == 3 && "Illegal TwoArgFP instruction!");
00628   unsigned Dest = getFPReg(MI->getOperand(0));
00629   unsigned Op0 = getFPReg(MI->getOperand(NumOperands-2));
00630   unsigned Op1 = getFPReg(MI->getOperand(NumOperands-1));
00631   bool KillsOp0 = LV->KillsRegister(MI, X86::FP0+Op0);
00632   bool KillsOp1 = LV->KillsRegister(MI, X86::FP0+Op1);
00633 
00634   unsigned TOS = getStackEntry(0);
00635 
00636   // One of our operands must be on the top of the stack.  If neither is yet, we
00637   // need to move one.
00638   if (Op0 != TOS && Op1 != TOS) {   // No operand at TOS?
00639     // We can choose to move either operand to the top of the stack.  If one of
00640     // the operands is killed by this instruction, we want that one so that we
00641     // can update right on top of the old version.
00642     if (KillsOp0) {
00643       moveToTop(Op0, I);         // Move dead operand to TOS.
00644       TOS = Op0;
00645     } else if (KillsOp1) {
00646       moveToTop(Op1, I);
00647       TOS = Op1;
00648     } else {
00649       // All of the operands are live after this instruction executes, so we
00650       // cannot update on top of any operand.  Because of this, we must
00651       // duplicate one of the stack elements to the top.  It doesn't matter
00652       // which one we pick.
00653       //
00654       duplicateToTop(Op0, Dest, I);
00655       Op0 = TOS = Dest;
00656       KillsOp0 = true;
00657     }
00658   } else if (!KillsOp0 && !KillsOp1) {
00659     // If we DO have one of our operands at the top of the stack, but we don't
00660     // have a dead operand, we must duplicate one of the operands to a new slot
00661     // on the stack.
00662     duplicateToTop(Op0, Dest, I);
00663     Op0 = TOS = Dest;
00664     KillsOp0 = true;
00665   }
00666 
00667   // Now we know that one of our operands is on the top of the stack, and at
00668   // least one of our operands is killed by this instruction.
00669   assert((TOS == Op0 || TOS == Op1) && (KillsOp0 || KillsOp1) &&
00670          "Stack conditions not set up right!");
00671 
00672   // We decide which form to use based on what is on the top of the stack, and
00673   // which operand is killed by this instruction.
00674   const TableEntry *InstTable;
00675   bool isForward = TOS == Op0;
00676   bool updateST0 = (TOS == Op0 && !KillsOp1) || (TOS == Op1 && !KillsOp0);
00677   if (updateST0) {
00678     if (isForward)
00679       InstTable = ForwardST0Table;
00680     else
00681       InstTable = ReverseST0Table;
00682   } else {
00683     if (isForward)
00684       InstTable = ForwardSTiTable;
00685     else
00686       InstTable = ReverseSTiTable;
00687   }
00688 
00689   int Opcode = Lookup(InstTable, ARRAY_SIZE(ForwardST0Table), MI->getOpcode());
00690   assert(Opcode != -1 && "Unknown TwoArgFP pseudo instruction!");
00691 
00692   // NotTOS - The register which is not on the top of stack...
00693   unsigned NotTOS = (TOS == Op0) ? Op1 : Op0;
00694 
00695   // Replace the old instruction with a new instruction
00696   MBB->remove(I++);
00697   I = BuildMI(*MBB, I, Opcode, 1).addReg(getSTReg(NotTOS));
00698 
00699   // If both operands are killed, pop one off of the stack in addition to
00700   // overwriting the other one.
00701   if (KillsOp0 && KillsOp1 && Op0 != Op1) {
00702     assert(!updateST0 && "Should have updated other operand!");
00703     popStackAfter(I);   // Pop the top of stack
00704   }
00705 
00706   // Update stack information so that we know the destination register is now on
00707   // the stack.
00708   unsigned UpdatedSlot = getSlot(updateST0 ? TOS : NotTOS);
00709   assert(UpdatedSlot < StackTop && Dest < 7);
00710   Stack[UpdatedSlot]   = Dest;
00711   RegMap[Dest]         = UpdatedSlot;
00712   delete MI;   // Remove the old instruction
00713 }
00714 
00715 /// handleCompareFP - Handle FUCOM and FUCOMI instructions, which have two FP
00716 /// register arguments and no explicit destinations.
00717 ///
00718 void FPS::handleCompareFP(MachineBasicBlock::iterator &I) {
00719   ASSERT_SORTED(ForwardST0Table); ASSERT_SORTED(ReverseST0Table);
00720   ASSERT_SORTED(ForwardSTiTable); ASSERT_SORTED(ReverseSTiTable);
00721   MachineInstr *MI = I;
00722 
00723   unsigned NumOperands = MI->getNumOperands();
00724   assert(NumOperands == 2 && "Illegal FUCOM* instruction!");
00725   unsigned Op0 = getFPReg(MI->getOperand(NumOperands-2));
00726   unsigned Op1 = getFPReg(MI->getOperand(NumOperands-1));
00727   bool KillsOp0 = LV->KillsRegister(MI, X86::FP0+Op0);
00728   bool KillsOp1 = LV->KillsRegister(MI, X86::FP0+Op1);
00729 
00730   // Make sure the first operand is on the top of stack, the other one can be
00731   // anywhere.
00732   moveToTop(Op0, I);
00733 
00734   // Change from the pseudo instruction to the concrete instruction.
00735   MI->getOperand(0).setReg(getSTReg(Op1));
00736   MI->RemoveOperand(1);
00737   MI->setOpcode(getConcreteOpcode(MI->getOpcode()));
00738 
00739   // If any of the operands are killed by this instruction, free them.
00740   if (KillsOp0) freeStackSlotAfter(I, Op0);
00741   if (KillsOp1 && Op0 != Op1) freeStackSlotAfter(I, Op1);
00742 }
00743 
00744 /// handleCondMovFP - Handle two address conditional move instructions.  These
00745 /// instructions move a st(i) register to st(0) iff a condition is true.  These
00746 /// instructions require that the first operand is at the top of the stack, but
00747 /// otherwise don't modify the stack at all.
00748 void FPS::handleCondMovFP(MachineBasicBlock::iterator &I) {
00749   MachineInstr *MI = I;
00750 
00751   unsigned Op0 = getFPReg(MI->getOperand(0));
00752   unsigned Op1 = getFPReg(MI->getOperand(1));
00753 
00754   // The first operand *must* be on the top of the stack.
00755   moveToTop(Op0, I);
00756 
00757   // Change the second operand to the stack register that the operand is in.
00758   // Change from the pseudo instruction to the concrete instruction.
00759   MI->RemoveOperand(0);
00760   MI->getOperand(0).setReg(getSTReg(Op1));
00761   MI->setOpcode(getConcreteOpcode(MI->getOpcode()));
00762   
00763   
00764   // If we kill the second operand, make sure to pop it from the stack.
00765   if (Op0 != Op1 && LV->KillsRegister(MI, X86::FP0+Op1)) {
00766     // Get this value off of the register stack.
00767     freeStackSlotAfter(I, Op1);
00768   }
00769 }
00770 
00771 
00772 /// handleSpecialFP - Handle special instructions which behave unlike other
00773 /// floating point instructions.  This is primarily intended for use by pseudo
00774 /// instructions.
00775 ///
00776 void FPS::handleSpecialFP(MachineBasicBlock::iterator &I) {
00777   MachineInstr *MI = I;
00778   switch (MI->getOpcode()) {
00779   default: assert(0 && "Unknown SpecialFP instruction!");
00780   case X86::FpGETRESULT:  // Appears immediately after a call returning FP type!
00781     assert(StackTop == 0 && "Stack should be empty after a call!");
00782     pushReg(getFPReg(MI->getOperand(0)));
00783     break;
00784   case X86::FpSETRESULT:
00785     assert(StackTop == 1 && "Stack should have one element on it to return!");
00786     --StackTop;   // "Forget" we have something on the top of stack!
00787     break;
00788   case X86::FpMOV: {
00789     unsigned SrcReg = getFPReg(MI->getOperand(1));
00790     unsigned DestReg = getFPReg(MI->getOperand(0));
00791 
00792     if (LV->KillsRegister(MI, X86::FP0+SrcReg)) {
00793       // If the input operand is killed, we can just change the owner of the
00794       // incoming stack slot into the result.
00795       unsigned Slot = getSlot(SrcReg);
00796       assert(Slot < 7 && DestReg < 7 && "FpMOV operands invalid!");
00797       Stack[Slot] = DestReg;
00798       RegMap[DestReg] = Slot;
00799 
00800     } else {
00801       // For FMOV we just duplicate the specified value to a new stack slot.
00802       // This could be made better, but would require substantial changes.
00803       duplicateToTop(SrcReg, DestReg, I);
00804     }
00805     break;
00806   }
00807   }
00808 
00809   I = MBB->erase(I);  // Remove the pseudo instruction
00810   --I;
00811 }