LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

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 <set>
00046 using namespace llvm;
00047 
00048 namespace {
00049   Statistic<> NumFXCH("x86-codegen", "Number of fxch instructions inserted");
00050   Statistic<> NumFP  ("x86-codegen", "Number of floating point instructions");
00051 
00052   struct FPS : public MachineFunctionPass {
00053     virtual bool runOnMachineFunction(MachineFunction &MF);
00054 
00055     virtual const char *getPassName() const { return "X86 FP Stackifier"; }
00056 
00057     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00058       AU.addRequired<LiveVariables>();
00059       MachineFunctionPass::getAnalysisUsage(AU);
00060     }
00061   private:
00062     LiveVariables     *LV;    // Live variable info for current function...
00063     MachineBasicBlock *MBB;   // Current basic block
00064     unsigned Stack[8];        // FP<n> Registers in each stack slot...
00065     unsigned RegMap[8];       // Track which stack slot contains each register
00066     unsigned StackTop;        // The current top of the FP stack.
00067 
00068     void dumpStack() const {
00069       std::cerr << "Stack contents:";
00070       for (unsigned i = 0; i != StackTop; ++i) {
00071   std::cerr << " FP" << Stack[i];
00072   assert(RegMap[Stack[i]] == i && "Stack[] doesn't match RegMap[]!"); 
00073       }
00074       std::cerr << "\n";
00075     }
00076   private:
00077     // getSlot - Return the stack slot number a particular register number is
00078     // in...
00079     unsigned getSlot(unsigned RegNo) const {
00080       assert(RegNo < 8 && "Regno out of range!");
00081       return RegMap[RegNo];
00082     }
00083 
00084     // getStackEntry - Return the X86::FP<n> register in register ST(i)
00085     unsigned getStackEntry(unsigned STi) const {
00086       assert(STi < StackTop && "Access past stack top!");
00087       return Stack[StackTop-1-STi];
00088     }
00089 
00090     // getSTReg - Return the X86::ST(i) register which contains the specified
00091     // FP<RegNo> register
00092     unsigned getSTReg(unsigned RegNo) const {
00093       return StackTop - 1 - getSlot(RegNo) + llvm::X86::ST0;
00094     }
00095 
00096     // pushReg - Push the specified FP<n> register onto the stack
00097     void pushReg(unsigned Reg) {
00098       assert(Reg < 8 && "Register number out of range!");
00099       assert(StackTop < 8 && "Stack overflow!");
00100       Stack[StackTop] = Reg;
00101       RegMap[Reg] = StackTop++;
00102     }
00103 
00104     bool isAtTop(unsigned RegNo) const { return getSlot(RegNo) == StackTop-1; }
00105     void moveToTop(unsigned RegNo, MachineBasicBlock::iterator &I) {
00106       if (!isAtTop(RegNo)) {
00107   unsigned Slot = getSlot(RegNo);
00108   unsigned STReg = getSTReg(RegNo);
00109   unsigned RegOnTop = getStackEntry(0);
00110 
00111   // Swap the slots the regs are in
00112   std::swap(RegMap[RegNo], RegMap[RegOnTop]);
00113 
00114   // Swap stack slot contents
00115   assert(RegMap[RegOnTop] < StackTop);
00116   std::swap(Stack[RegMap[RegOnTop]], Stack[StackTop-1]);
00117 
00118   // Emit an fxch to update the runtime processors version of the state
00119   BuildMI(*MBB, I, X86::FXCH, 1).addReg(STReg);
00120   NumFXCH++;
00121       }
00122     }
00123 
00124     void duplicateToTop(unsigned RegNo, unsigned AsReg, MachineInstr *I) {
00125       unsigned STReg = getSTReg(RegNo);
00126       pushReg(AsReg);   // New register on top of stack
00127 
00128       BuildMI(*MBB, I, X86::FLDrr, 1).addReg(STReg);
00129     }
00130 
00131     // popStackAfter - Pop the current value off of the top of the FP stack
00132     // after the specified instruction.
00133     void popStackAfter(MachineBasicBlock::iterator &I);
00134 
00135     // freeStackSlotAfter - Free the specified register from the register stack,
00136     // so that it is no longer in a register.  If the register is currently at
00137     // the top of the stack, we just pop the current instruction, otherwise we
00138     // store the current top-of-stack into the specified slot, then pop the top
00139     // of stack.
00140     void freeStackSlotAfter(MachineBasicBlock::iterator &I, unsigned Reg);
00141 
00142     bool processBasicBlock(MachineFunction &MF, MachineBasicBlock &MBB);
00143 
00144     void handleZeroArgFP(MachineBasicBlock::iterator &I);
00145     void handleOneArgFP(MachineBasicBlock::iterator &I);
00146     void handleOneArgFPRW(MachineBasicBlock::iterator &I);
00147     void handleTwoArgFP(MachineBasicBlock::iterator &I);
00148     void handleCompareFP(MachineBasicBlock::iterator &I);
00149     void handleCondMovFP(MachineBasicBlock::iterator &I);
00150     void handleSpecialFP(MachineBasicBlock::iterator &I);
00151   };
00152 }
00153 
00154 FunctionPass *llvm::createX86FloatingPointStackifierPass() { return new FPS(); }
00155 
00156 /// runOnMachineFunction - Loop over all of the basic blocks, transforming FP
00157 /// register references into FP stack references.
00158 ///
00159 bool FPS::runOnMachineFunction(MachineFunction &MF) {
00160   LV = &getAnalysis<LiveVariables>();
00161   StackTop = 0;
00162 
00163   // Process the function in depth first order so that we process at least one
00164   // of the predecessors for every reachable block in the function.
00165   std::set<MachineBasicBlock*> Processed;
00166   MachineBasicBlock *Entry = MF.begin();
00167 
00168   bool Changed = false;
00169   for (df_ext_iterator<MachineBasicBlock*, std::set<MachineBasicBlock*> >
00170          I = df_ext_begin(Entry, Processed), E = df_ext_end(Entry, Processed);
00171        I != E; ++I)
00172     Changed |= processBasicBlock(MF, **I);
00173 
00174   return Changed;
00175 }
00176 
00177 /// processBasicBlock - Loop over all of the instructions in the basic block,
00178 /// transforming FP instructions into their stack form.
00179 ///
00180 bool FPS::processBasicBlock(MachineFunction &MF, MachineBasicBlock &BB) {
00181   const TargetInstrInfo &TII = *MF.getTarget().getInstrInfo();
00182   bool Changed = false;
00183   MBB = &BB;
00184   
00185   for (MachineBasicBlock::iterator I = BB.begin(); I != BB.end(); ++I) {
00186     MachineInstr *MI = I;
00187     unsigned Flags = TII.get(MI->getOpcode()).TSFlags;
00188     if ((Flags & X86II::FPTypeMask) == X86II::NotFP)
00189       continue;  // Efficiently ignore non-fp insts!
00190 
00191     MachineInstr *PrevMI = 0;
00192     if (I != BB.begin())
00193         PrevMI = prior(I);
00194 
00195     ++NumFP;  // Keep track of # of pseudo instrs
00196     DEBUG(std::cerr << "\nFPInst:\t";
00197     MI->print(std::cerr, &(MF.getTarget())));
00198 
00199     // Get dead variables list now because the MI pointer may be deleted as part
00200     // of processing!
00201     LiveVariables::killed_iterator IB = LV->dead_begin(MI);
00202     LiveVariables::killed_iterator IE = LV->dead_end(MI);
00203 
00204     DEBUG(const MRegisterInfo *MRI = MF.getTarget().getRegisterInfo();
00205     LiveVariables::killed_iterator I = LV->killed_begin(MI);
00206     LiveVariables::killed_iterator E = LV->killed_end(MI);
00207     if (I != E) {
00208       std::cerr << "Killed Operands:";
00209       for (; I != E; ++I)
00210         std::cerr << " %" << MRI->getName(I->second);
00211       std::cerr << "\n";
00212     });
00213 
00214     switch (Flags & X86II::FPTypeMask) {
00215     case X86II::ZeroArgFP:  handleZeroArgFP(I); break;
00216     case X86II::OneArgFP:   handleOneArgFP(I);  break;  // fstp ST(0)
00217     case X86II::OneArgFPRW: handleOneArgFPRW(I); break; // ST(0) = fsqrt(ST(0))
00218     case X86II::TwoArgFP:   handleTwoArgFP(I); break;
00219     case X86II::CompareFP:  handleCompareFP(I); break;
00220     case X86II::CondMovFP:  handleCondMovFP(I); break;
00221     case X86II::SpecialFP:  handleSpecialFP(I); break;
00222     default: assert(0 && "Unknown FP Type!");
00223     }
00224 
00225     // Check to see if any of the values defined by this instruction are dead
00226     // after definition.  If so, pop them.
00227     for (; IB != IE; ++IB) {
00228       unsigned Reg = IB->second;
00229       if (Reg >= X86::FP0 && Reg <= X86::FP6) {
00230   DEBUG(std::cerr << "Register FP#" << Reg-X86::FP0 << " is dead!\n");
00231         freeStackSlotAfter(I, Reg-X86::FP0);
00232       }
00233     }
00234     
00235     // Print out all of the instructions expanded to if -debug
00236     DEBUG(
00237       MachineBasicBlock::iterator PrevI(PrevMI);
00238       if (I == PrevI) {
00239         std::cerr << "Just deleted pseudo instruction\n";
00240       } else {
00241         MachineBasicBlock::iterator Start = I;
00242         // Rewind to first instruction newly inserted.
00243         while (Start != BB.begin() && prior(Start) != PrevI) --Start;
00244         std::cerr << "Inserted instructions:\n\t";
00245         Start->print(std::cerr, &MF.getTarget());
00246         while (++Start != next(I));
00247       }
00248       dumpStack();
00249     );
00250 
00251     Changed = true;
00252   }
00253 
00254   assert(StackTop == 0 && "Stack not empty at end of basic block?");
00255   return Changed;
00256 }
00257 
00258 //===----------------------------------------------------------------------===//
00259 // Efficient Lookup Table Support
00260 //===----------------------------------------------------------------------===//
00261 
00262 namespace {
00263   struct TableEntry {
00264     unsigned from;
00265     unsigned to;
00266     bool operator<(const TableEntry &TE) const { return from < TE.from; }
00267     bool operator<(unsigned V) const { return from < V; }
00268   };
00269 }
00270 
00271 static bool TableIsSorted(const TableEntry *Table, unsigned NumEntries) {
00272   for (unsigned i = 0; i != NumEntries-1; ++i)
00273     if (!(Table[i] < Table[i+1])) return false;
00274   return true;
00275 }
00276 
00277 static int Lookup(const TableEntry *Table, unsigned N, unsigned Opcode) {
00278   const TableEntry *I = std::lower_bound(Table, Table+N, Opcode);
00279   if (I != Table+N && I->from == Opcode)
00280     return I->to;
00281   return -1;
00282 }
00283 
00284 #define ARRAY_SIZE(TABLE)  \
00285    (sizeof(TABLE)/sizeof(TABLE[0]))
00286 
00287 #ifdef NDEBUG
00288 #define ASSERT_SORTED(TABLE)
00289 #else
00290 #define ASSERT_SORTED(TABLE)                                              \
00291   { static bool TABLE##Checked = false;                                   \
00292     if (!TABLE##Checked)                                                  \
00293        assert(TableIsSorted(TABLE, ARRAY_SIZE(TABLE)) &&                  \
00294               "All lookup tables must be sorted for efficient access!");  \
00295   }
00296 #endif
00297 
00298 
00299 //===----------------------------------------------------------------------===//
00300 // Helper Methods
00301 //===----------------------------------------------------------------------===//
00302 
00303 // PopTable - Sorted map of instructions to their popping version.  The first
00304 // element is an instruction, the second is the version which pops.
00305 //
00306 static const TableEntry PopTable[] = {
00307   { X86::FADDrST0 , X86::FADDPrST0  },
00308 
00309   { X86::FDIVRrST0, X86::FDIVRPrST0 },
00310   { X86::FDIVrST0 , X86::FDIVPrST0  },
00311 
00312   { X86::FIST16m  , X86::FISTP16m   },
00313   { X86::FIST32m  , X86::FISTP32m   },
00314 
00315   { X86::FMULrST0 , X86::FMULPrST0  },
00316 
00317   { X86::FST32m   , X86::FSTP32m    },
00318   { X86::FST64m   , X86::FSTP64m    },
00319   { X86::FSTrr    , X86::FSTPrr     },
00320 
00321   { X86::FSUBRrST0, X86::FSUBRPrST0 },
00322   { X86::FSUBrST0 , X86::FSUBPrST0  },
00323 
00324   { X86::FUCOMIr  , X86::FUCOMIPr   },
00325 
00326   { X86::FUCOMPr  , X86::FUCOMPPr   },
00327   { X86::FUCOMr   , X86::FUCOMPr    },
00328 };
00329 
00330 /// popStackAfter - Pop the current value off of the top of the FP stack after
00331 /// the specified instruction.  This attempts to be sneaky and combine the pop
00332 /// into the instruction itself if possible.  The iterator is left pointing to
00333 /// the last instruction, be it a new pop instruction inserted, or the old
00334 /// instruction if it was modified in place.
00335 ///
00336 void FPS::popStackAfter(MachineBasicBlock::iterator &I) {
00337   ASSERT_SORTED(PopTable);
00338   assert(StackTop > 0 && "Cannot pop empty stack!");
00339   RegMap[Stack[--StackTop]] = ~0;     // Update state
00340 
00341   // Check to see if there is a popping version of this instruction...
00342   int Opcode = Lookup(PopTable, ARRAY_SIZE(PopTable), I->getOpcode());
00343   if (Opcode != -1) {
00344     I->setOpcode(Opcode);
00345     if (Opcode == X86::FUCOMPPr)
00346       I->RemoveOperand(0);
00347 
00348   } else {    // Insert an explicit pop
00349     I = BuildMI(*MBB, ++I, X86::FSTPrr, 1).addReg(X86::ST0);
00350   }
00351 }
00352 
00353 /// freeStackSlotAfter - Free the specified register from the register stack, so
00354 /// that it is no longer in a register.  If the register is currently at the top
00355 /// of the stack, we just pop the current instruction, otherwise we store the
00356 /// current top-of-stack into the specified slot, then pop the top of stack.
00357 void FPS::freeStackSlotAfter(MachineBasicBlock::iterator &I, unsigned FPRegNo) {
00358   if (getStackEntry(0) == FPRegNo) {  // already at the top of stack? easy.
00359     popStackAfter(I);
00360     return;
00361   }
00362 
00363   // Otherwise, store the top of stack into the dead slot, killing the operand
00364   // without having to add in an explicit xchg then pop.
00365   //
00366   unsigned STReg    = getSTReg(FPRegNo);
00367   unsigned OldSlot  = getSlot(FPRegNo);
00368   unsigned TopReg   = Stack[StackTop-1];
00369   Stack[OldSlot]    = TopReg;
00370   RegMap[TopReg]    = OldSlot;
00371   RegMap[FPRegNo]   = ~0;
00372   Stack[--StackTop] = ~0;
00373   I = BuildMI(*MBB, ++I, X86::FSTPrr, 1).addReg(STReg);
00374 }
00375 
00376 
00377 static unsigned getFPReg(const MachineOperand &MO) {
00378   assert(MO.isRegister() && "Expected an FP register!");
00379   unsigned Reg = MO.getReg();
00380   assert(Reg >= X86::FP0 && Reg <= X86::FP6 && "Expected FP register!");
00381   return Reg - X86::FP0;
00382 }
00383 
00384 
00385 //===----------------------------------------------------------------------===//
00386 // Instruction transformation implementation
00387 //===----------------------------------------------------------------------===//
00388 
00389 /// handleZeroArgFP - ST(0) = fld0    ST(0) = flds <mem>
00390 ///
00391 void FPS::handleZeroArgFP(MachineBasicBlock::iterator &I) {
00392   MachineInstr *MI = I;
00393   unsigned DestReg = getFPReg(MI->getOperand(0));
00394   MI->RemoveOperand(0);   // Remove the explicit ST(0) operand
00395 
00396   // Result gets pushed on the stack...
00397   pushReg(DestReg);
00398 }
00399 
00400 /// handleOneArgFP - fst <mem>, ST(0)
00401 ///
00402 void FPS::handleOneArgFP(MachineBasicBlock::iterator &I) {
00403   MachineInstr *MI = I;
00404   assert((MI->getNumOperands() == 5 || MI->getNumOperands() == 1) &&
00405          "Can only handle fst* & ftst instructions!");
00406 
00407   // Is this the last use of the source register?
00408   unsigned Reg = getFPReg(MI->getOperand(MI->getNumOperands()-1));
00409   bool KillsSrc = false;
00410   for (LiveVariables::killed_iterator KI = LV->killed_begin(MI),
00411    E = LV->killed_end(MI); KI != E; ++KI)
00412     KillsSrc |= KI->second == X86::FP0+Reg;
00413 
00414   // FSTP80r and FISTP64r are strange because there are no non-popping versions.
00415   // If we have one _and_ we don't want to pop the operand, duplicate the value
00416   // on the stack instead of moving it.  This ensure that popping the value is
00417   // always ok.
00418   //
00419   if ((MI->getOpcode() == X86::FSTP80m ||
00420        MI->getOpcode() == X86::FISTP64m) && !KillsSrc) {
00421     duplicateToTop(Reg, 7 /*temp register*/, I);
00422   } else {
00423     moveToTop(Reg, I);            // Move to the top of the stack...
00424   }
00425   MI->RemoveOperand(MI->getNumOperands()-1);    // Remove explicit ST(0) operand
00426   
00427   if (MI->getOpcode() == X86::FSTP80m || MI->getOpcode() == X86::FISTP64m) {
00428     assert(StackTop > 0 && "Stack empty??");
00429     --StackTop;
00430   } else if (KillsSrc) { // Last use of operand?
00431     popStackAfter(I);
00432   }
00433 }
00434 
00435 
00436 /// handleOneArgFPRW: Handle instructions that read from the top of stack and
00437 /// replace the value with a newly computed value.  These instructions may have
00438 /// non-fp operands after their FP operands.
00439 ///
00440 ///  Examples:
00441 ///     R1 = fchs R2
00442 ///     R1 = fadd R2, [mem]
00443 ///
00444 void FPS::handleOneArgFPRW(MachineBasicBlock::iterator &I) {
00445   MachineInstr *MI = I;
00446   assert(MI->getNumOperands() >= 2 && "FPRW instructions must have 2 ops!!");
00447 
00448   // Is this the last use of the source register?
00449   unsigned Reg = getFPReg(MI->getOperand(1));
00450   bool KillsSrc = false;
00451   for (LiveVariables::killed_iterator KI = LV->killed_begin(MI),
00452    E = LV->killed_end(MI); KI != E; ++KI)
00453     KillsSrc |= KI->second == X86::FP0+Reg;
00454 
00455   if (KillsSrc) {
00456     // If this is the last use of the source register, just make sure it's on
00457     // the top of the stack.
00458     moveToTop(Reg, I);
00459     assert(StackTop > 0 && "Stack cannot be empty!");
00460     --StackTop;
00461     pushReg(getFPReg(MI->getOperand(0)));
00462   } else {
00463     // If this is not the last use of the source register, _copy_ it to the top
00464     // of the stack.
00465     duplicateToTop(Reg, getFPReg(MI->getOperand(0)), I);
00466   }
00467 
00468   MI->RemoveOperand(1);   // Drop the source operand.
00469   MI->RemoveOperand(0);   // Drop the destination operand.
00470 }
00471 
00472 
00473 //===----------------------------------------------------------------------===//
00474 // Define tables of various ways to map pseudo instructions
00475 //
00476 
00477 // ForwardST0Table - Map: A = B op C  into: ST(0) = ST(0) op ST(i)
00478 static const TableEntry ForwardST0Table[] = {
00479   { X86::FpADD  , X86::FADDST0r },
00480   { X86::FpDIV  , X86::FDIVST0r },
00481   { X86::FpMUL  , X86::FMULST0r },
00482   { X86::FpSUB  , X86::FSUBST0r },
00483 };
00484 
00485 // ReverseST0Table - Map: A = B op C  into: ST(0) = ST(i) op ST(0)
00486 static const TableEntry ReverseST0Table[] = {
00487   { X86::FpADD  , X86::FADDST0r  },   // commutative
00488   { X86::FpDIV  , X86::FDIVRST0r },
00489   { X86::FpMUL  , X86::FMULST0r  },   // commutative
00490   { X86::FpSUB  , X86::FSUBRST0r },
00491 };
00492 
00493 // ForwardSTiTable - Map: A = B op C  into: ST(i) = ST(0) op ST(i)
00494 static const TableEntry ForwardSTiTable[] = {
00495   { X86::FpADD  , X86::FADDrST0  },   // commutative
00496   { X86::FpDIV  , X86::FDIVRrST0 },
00497   { X86::FpMUL  , X86::FMULrST0  },   // commutative
00498   { X86::FpSUB  , X86::FSUBRrST0 },
00499 };
00500 
00501 // ReverseSTiTable - Map: A = B op C  into: ST(i) = ST(i) op ST(0)
00502 static const TableEntry ReverseSTiTable[] = {
00503   { X86::FpADD  , X86::FADDrST0 },
00504   { X86::FpDIV  , X86::FDIVrST0 },
00505   { X86::FpMUL  , X86::FMULrST0 },
00506   { X86::FpSUB  , X86::FSUBrST0 },
00507 };
00508 
00509 
00510 /// handleTwoArgFP - Handle instructions like FADD and friends which are virtual
00511 /// instructions which need to be simplified and possibly transformed.
00512 ///
00513 /// Result: ST(0) = fsub  ST(0), ST(i)
00514 ///         ST(i) = fsub  ST(0), ST(i)
00515 ///         ST(0) = fsubr ST(0), ST(i)
00516 ///         ST(i) = fsubr ST(0), ST(i)
00517 /// 
00518 void FPS::handleTwoArgFP(MachineBasicBlock::iterator &I) {
00519   ASSERT_SORTED(ForwardST0Table); ASSERT_SORTED(ReverseST0Table);
00520   ASSERT_SORTED(ForwardSTiTable); ASSERT_SORTED(ReverseSTiTable);
00521   MachineInstr *MI = I;
00522 
00523   unsigned NumOperands = MI->getNumOperands();
00524   assert(NumOperands == 3 && "Illegal TwoArgFP instruction!");
00525   unsigned Dest = getFPReg(MI->getOperand(0));
00526   unsigned Op0 = getFPReg(MI->getOperand(NumOperands-2));
00527   unsigned Op1 = getFPReg(MI->getOperand(NumOperands-1));
00528   bool KillsOp0 = false, KillsOp1 = false;
00529 
00530   for (LiveVariables::killed_iterator KI = LV->killed_begin(MI),
00531    E = LV->killed_end(MI); KI != E; ++KI) {
00532     KillsOp0 |= (KI->second == X86::FP0+Op0);
00533     KillsOp1 |= (KI->second == X86::FP0+Op1);
00534   }
00535 
00536   unsigned TOS = getStackEntry(0);
00537 
00538   // One of our operands must be on the top of the stack.  If neither is yet, we
00539   // need to move one.
00540   if (Op0 != TOS && Op1 != TOS) {   // No operand at TOS?
00541     // We can choose to move either operand to the top of the stack.  If one of
00542     // the operands is killed by this instruction, we want that one so that we
00543     // can update right on top of the old version.
00544     if (KillsOp0) {
00545       moveToTop(Op0, I);         // Move dead operand to TOS.
00546       TOS = Op0;
00547     } else if (KillsOp1) {
00548       moveToTop(Op1, I);
00549       TOS = Op1;
00550     } else {
00551       // All of the operands are live after this instruction executes, so we
00552       // cannot update on top of any operand.  Because of this, we must
00553       // duplicate one of the stack elements to the top.  It doesn't matter
00554       // which one we pick.
00555       //
00556       duplicateToTop(Op0, Dest, I);
00557       Op0 = TOS = Dest;
00558       KillsOp0 = true;
00559     }
00560   } else if (!KillsOp0 && !KillsOp1) {
00561     // If we DO have one of our operands at the top of the stack, but we don't
00562     // have a dead operand, we must duplicate one of the operands to a new slot
00563     // on the stack.
00564     duplicateToTop(Op0, Dest, I);
00565     Op0 = TOS = Dest;
00566     KillsOp0 = true;
00567   }
00568 
00569   // Now we know that one of our operands is on the top of the stack, and at
00570   // least one of our operands is killed by this instruction.
00571   assert((TOS == Op0 || TOS == Op1) && (KillsOp0 || KillsOp1) && 
00572    "Stack conditions not set up right!");
00573 
00574   // We decide which form to use based on what is on the top of the stack, and
00575   // which operand is killed by this instruction.
00576   const TableEntry *InstTable;
00577   bool isForward = TOS == Op0;
00578   bool updateST0 = (TOS == Op0 && !KillsOp1) || (TOS == Op1 && !KillsOp0);
00579   if (updateST0) {
00580     if (isForward)
00581       InstTable = ForwardST0Table;
00582     else
00583       InstTable = ReverseST0Table;
00584   } else {
00585     if (isForward)
00586       InstTable = ForwardSTiTable;
00587     else
00588       InstTable = ReverseSTiTable;
00589   }
00590   
00591   int Opcode = Lookup(InstTable, ARRAY_SIZE(ForwardST0Table), MI->getOpcode());
00592   assert(Opcode != -1 && "Unknown TwoArgFP pseudo instruction!");
00593 
00594   // NotTOS - The register which is not on the top of stack...
00595   unsigned NotTOS = (TOS == Op0) ? Op1 : Op0;
00596 
00597   // Replace the old instruction with a new instruction
00598   MBB->remove(I++);
00599   I = BuildMI(*MBB, I, Opcode, 1).addReg(getSTReg(NotTOS));
00600 
00601   // If both operands are killed, pop one off of the stack in addition to
00602   // overwriting the other one.
00603   if (KillsOp0 && KillsOp1 && Op0 != Op1) {
00604     assert(!updateST0 && "Should have updated other operand!");
00605     popStackAfter(I);   // Pop the top of stack
00606   }
00607 
00608   // Update stack information so that we know the destination register is now on
00609   // the stack.
00610   unsigned UpdatedSlot = getSlot(updateST0 ? TOS : NotTOS);
00611   assert(UpdatedSlot < StackTop && Dest < 7);
00612   Stack[UpdatedSlot]   = Dest;
00613   RegMap[Dest]         = UpdatedSlot;
00614   delete MI;   // Remove the old instruction
00615 }
00616 
00617 /// handleCompareFP - Handle FUCOM and FUCOMI instructions, which have two FP
00618 /// register arguments and no explicit destinations.
00619 /// 
00620 void FPS::handleCompareFP(MachineBasicBlock::iterator &I) {
00621   ASSERT_SORTED(ForwardST0Table); ASSERT_SORTED(ReverseST0Table);
00622   ASSERT_SORTED(ForwardSTiTable); ASSERT_SORTED(ReverseSTiTable);
00623   MachineInstr *MI = I;
00624 
00625   unsigned NumOperands = MI->getNumOperands();
00626   assert(NumOperands == 2 && "Illegal FUCOM* instruction!");
00627   unsigned Op0 = getFPReg(MI->getOperand(NumOperands-2));
00628   unsigned Op1 = getFPReg(MI->getOperand(NumOperands-1));
00629   bool KillsOp0 = false, KillsOp1 = false;
00630 
00631   for (LiveVariables::killed_iterator KI = LV->killed_begin(MI),
00632    E = LV->killed_end(MI); KI != E; ++KI) {
00633     KillsOp0 |= (KI->second == X86::FP0+Op0);
00634     KillsOp1 |= (KI->second == X86::FP0+Op1);
00635   }
00636 
00637   // Make sure the first operand is on the top of stack, the other one can be
00638   // anywhere.
00639   moveToTop(Op0, I);
00640 
00641   MI->getOperand(0).setReg(getSTReg(Op1));
00642   MI->RemoveOperand(1);
00643 
00644   // If any of the operands are killed by this instruction, free them.
00645   if (KillsOp0) freeStackSlotAfter(I, Op0);
00646   if (KillsOp1 && Op0 != Op1) freeStackSlotAfter(I, Op1);
00647 }
00648 
00649 /// handleCondMovFP - Handle two address conditional move instructions.  These
00650 /// instructions move a st(i) register to st(0) iff a condition is true.  These
00651 /// instructions require that the first operand is at the top of the stack, but
00652 /// otherwise don't modify the stack at all.
00653 void FPS::handleCondMovFP(MachineBasicBlock::iterator &I) {
00654   MachineInstr *MI = I;
00655 
00656   unsigned Op0 = getFPReg(MI->getOperand(0));
00657   unsigned Op1 = getFPReg(MI->getOperand(1));
00658 
00659   // The first operand *must* be on the top of the stack.
00660   moveToTop(Op0, I);
00661 
00662   // Change the second operand to the stack register that the operand is in.
00663   MI->RemoveOperand(0);
00664   MI->getOperand(0).setReg(getSTReg(Op1));
00665 
00666   // If we kill the second operand, make sure to pop it from the stack.
00667   if (Op0 != Op1) 
00668     for (LiveVariables::killed_iterator KI = LV->killed_begin(MI),
00669            E = LV->killed_end(MI); KI != E; ++KI)
00670       if (KI->second == X86::FP0+Op1) {
00671         // Get this value off of the register stack.
00672         freeStackSlotAfter(I, Op1);
00673         break;
00674       }
00675 }
00676 
00677 
00678 /// handleSpecialFP - Handle special instructions which behave unlike other
00679 /// floating point instructions.  This is primarily intended for use by pseudo
00680 /// instructions.
00681 ///
00682 void FPS::handleSpecialFP(MachineBasicBlock::iterator &I) {
00683   MachineInstr *MI = I;
00684   switch (MI->getOpcode()) {
00685   default: assert(0 && "Unknown SpecialFP instruction!");
00686   case X86::FpGETRESULT:  // Appears immediately after a call returning FP type!
00687     assert(StackTop == 0 && "Stack should be empty after a call!");
00688     pushReg(getFPReg(MI->getOperand(0)));
00689     break;
00690   case X86::FpSETRESULT:
00691     assert(StackTop == 1 && "Stack should have one element on it to return!");
00692     --StackTop;   // "Forget" we have something on the top of stack!
00693     break;
00694   case X86::FpMOV: {
00695     unsigned SrcReg = getFPReg(MI->getOperand(1));
00696     unsigned DestReg = getFPReg(MI->getOperand(0));
00697     bool KillsSrc = false;
00698     for (LiveVariables::killed_iterator KI = LV->killed_begin(MI),
00699      E = LV->killed_end(MI); KI != E; ++KI)
00700       KillsSrc |= KI->second == X86::FP0+SrcReg;
00701 
00702     if (KillsSrc) {
00703       // If the input operand is killed, we can just change the owner of the
00704       // incoming stack slot into the result.
00705       unsigned Slot = getSlot(SrcReg);
00706       assert(Slot < 7 && DestReg < 7 && "FpMOV operands invalid!");
00707       Stack[Slot] = DestReg;
00708       RegMap[DestReg] = Slot;
00709 
00710     } else {
00711       // For FMOV we just duplicate the specified value to a new stack slot.
00712       // This could be made better, but would require substantial changes.
00713       duplicateToTop(SrcReg, DestReg, I);
00714     }
00715     break;
00716   }
00717   }
00718 
00719   I = MBB->erase(I);  // Remove the pseudo instruction
00720   --I;
00721 }