lib/Target/X86/X86FloatingPoint.cpp

   1 //===-- X86FloatingPoint.cpp - Floating point Reg -> Stack converter ------===//
   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 defines the pass which converts floating point instructions from
  11 // virtual registers into register stack instructions.  This pass uses live
  12 // variable information to indicate where the FPn registers are used and their
  13 // lifetimes.
  14 //
  15 // This pass is hampered by the lack of decent CFG manipulation routines for
  16 // machine code.  In particular, this wants to be able to split critical edges
  17 // as necessary, traverse the machine basic block CFG in depth-first order, and
  18 // allow there to be multiple machine basic blocks for each LLVM basicblock
  19 // (needed for critical edge splitting).
  20 //
  21 // In particular, this pass currently barfs on critical edges.  Because of this,
  22 // it requires the instruction selector to insert FP_REG_KILL instructions on
  23 // the exits of any basic block that has critical edges going from it, or which
  24 // branch to a critical basic block.
  25 //
  26 // FIXME: this is not implemented yet.  The stackifier pass only works on local
  27 // basic blocks.
  28 //
  29 //===----------------------------------------------------------------------===//
  30
  31 #define DEBUG_TYPE "fp"
  32 #include "X86.h"
  33 #include "X86InstrInfo.h"
  34 #include "llvm/CodeGen/MachineFunctionPass.h"
  35 #include "llvm/CodeGen/MachineInstrBuilder.h"
  36 #include "llvm/CodeGen/LiveVariables.h"
  37 #include "llvm/CodeGen/Passes.h"
  38 #include "llvm/Target/TargetInstrInfo.h"
  39 #include "llvm/Target/TargetMachine.h"
  40 #include "llvm/Support/Debug.h"
  41 #include "llvm/Support/Compiler.h"
  42 #include "llvm/ADT/DepthFirstIterator.h"
  43 #include "llvm/ADT/Statistic.h"
  44 #include "llvm/ADT/STLExtras.h"
  45 #include <algorithm>
  46 #include <iostream>
  47 #include <set>
  48 using namespace llvm;
  49
  50 namespace {
  51   Statistic<> NumFXCH("x86-codegen", "Number of fxch instructions inserted");
  52   Statistic<> NumFP  ("x86-codegen", "Number of floating point instructions");
  53
  54   struct VISIBILITY_HIDDEN FPS : public MachineFunctionPass {
  55     virtual bool runOnMachineFunction(MachineFunction &MF);
  56
  57     virtual const char *getPassName() const { return "X86 FP Stackifier"; }
  58
  59     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  60       AU.addRequired<LiveVariables>();
  61       MachineFunctionPass::getAnalysisUsage(AU);
  62     }
  63   private:
  64     LiveVariables     *LV;    // Live variable info for current function...
  65     MachineBasicBlock *MBB;   // Current basic block
  66     unsigned Stack[8];        // FP<n> Registers in each stack slot...
  67     unsigned RegMap[8];       // Track which stack slot contains each register
  68     unsigned StackTop;        // The current top of the FP stack.
  69
  70     void dumpStack() const {
  71       std::cerr << "Stack contents:";
  72       for (unsigned i = 0; i != StackTop; ++i) {
  73         std::cerr << " FP" << Stack[i];
  74         assert(RegMap[Stack[i]] == i && "Stack[] doesn't match RegMap[]!");
  75       }
  76       std::cerr << "\n";
  77     }
  78   private:
  79     // getSlot - Return the stack slot number a particular register number is
  80     // in...
  81     unsigned getSlot(unsigned RegNo) const {
  82       assert(RegNo < 8 && "Regno out of range!");
  83       return RegMap[RegNo];
  84     }
  85
  86     // getStackEntry - Return the X86::FP<n> register in register ST(i)
  87     unsigned getStackEntry(unsigned STi) const {
  88       assert(STi < StackTop && "Access past stack top!");
  89       return Stack[StackTop-1-STi];
  90     }
  91
  92     // getSTReg - Return the X86::ST(i) register which contains the specified
  93     // FP<RegNo> register
  94     unsigned getSTReg(unsigned RegNo) const {
  95       return StackTop - 1 - getSlot(RegNo) + llvm::X86::ST0;
  96     }
  97
  98     // pushReg - Push the specified FP<n> register onto the stack
  99     void pushReg(unsigned Reg) {
 100       assert(Reg < 8 && "Register number out of range!");
 101       assert(StackTop < 8 && "Stack overflow!");
 102       Stack[StackTop] = Reg;
 103       RegMap[Reg] = StackTop++;
 104     }
 105
 106     bool isAtTop(unsigned RegNo) const { return getSlot(RegNo) == StackTop-1; }
 107     void moveToTop(unsigned RegNo, MachineBasicBlock::iterator &I) {
 108       if (!isAtTop(RegNo)) {
 109         unsigned STReg = getSTReg(RegNo);
 110         unsigned RegOnTop = getStackEntry(0);
 111
 112         // Swap the slots the regs are in
 113         std::swap(RegMap[RegNo], RegMap[RegOnTop]);
 114
 115         // Swap stack slot contents
 116         assert(RegMap[RegOnTop] < StackTop);
 117         std::swap(Stack[RegMap[RegOnTop]], Stack[StackTop-1]);
 118
 119         // Emit an fxch to update the runtime processors version of the state
 120         BuildMI(*MBB, I, X86::FXCH, 1).addReg(STReg);
 121         NumFXCH++;
 122       }
 123     }
 124
 125     void duplicateToTop(unsigned RegNo, unsigned AsReg, MachineInstr *I) {
 126       unsigned STReg = getSTReg(RegNo);
 127       pushReg(AsReg);   // New register on top of stack
 128
 129       BuildMI(*MBB, I, X86::FLDrr, 1).addReg(STReg);
 130     }
 131
 132     // popStackAfter - Pop the current value off of the top of the FP stack
 133     // after the specified instruction.
 134     void popStackAfter(MachineBasicBlock::iterator &I);
 135
 136     // freeStackSlotAfter - Free the specified register from the register stack,
 137     // so that it is no longer in a register.  If the register is currently at
 138     // the top of the stack, we just pop the current instruction, otherwise we
 139     // store the current top-of-stack into the specified slot, then pop the top
 140     // of stack.
 141     void freeStackSlotAfter(MachineBasicBlock::iterator &I, unsigned Reg);
 142
 143     bool processBasicBlock(MachineFunction &MF, MachineBasicBlock &MBB);
 144
 145     void handleZeroArgFP(MachineBasicBlock::iterator &I);
 146     void handleOneArgFP(MachineBasicBlock::iterator &I);
 147     void handleOneArgFPRW(MachineBasicBlock::iterator &I);
 148     void handleTwoArgFP(MachineBasicBlock::iterator &I);
 149     void handleCompareFP(MachineBasicBlock::iterator &I);
 150     void handleCondMovFP(MachineBasicBlock::iterator &I);
 151     void handleSpecialFP(MachineBasicBlock::iterator &I);
 152   };
 153 }
 154
 155 FunctionPass *llvm::createX86FloatingPointStackifierPass() { return new FPS(); }
 156
 157 /// runOnMachineFunction - Loop over all of the basic blocks, transforming FP
 158 /// register references into FP stack references.
 159 ///
 160 bool FPS::runOnMachineFunction(MachineFunction &MF) {
 161   // We only need to run this pass if there are any FP registers used in this
 162   // function.  If it is all integer, there is nothing for us to do!
 163   const bool *PhysRegsUsed = MF.getUsedPhysregs();
 164   bool FPIsUsed = false;
 165
 166   assert(X86::FP6 == X86::FP0+6 && "Register enums aren't sorted right!");
 167   for (unsigned i = 0; i <= 6; ++i)
 168     if (PhysRegsUsed[X86::FP0+i]) {
 169       FPIsUsed = true;
 170       break;
 171     }
 172
 173   // Early exit.
 174   if (!FPIsUsed) return false;
 175
 176   LV = &getAnalysis<LiveVariables>();
 177   StackTop = 0;
 178
 179   // Process the function in depth first order so that we process at least one
 180   // of the predecessors for every reachable block in the function.
 181   std::set<MachineBasicBlock*> Processed;
 182   MachineBasicBlock *Entry = MF.begin();
 183
 184   bool Changed = false;
 185   for (df_ext_iterator<MachineBasicBlock*, std::set<MachineBasicBlock*> >
 186          I = df_ext_begin(Entry, Processed), E = df_ext_end(Entry, Processed);
 187        I != E; ++I)
 188     Changed |= processBasicBlock(MF, **I);
 189
 190   return Changed;
 191 }
 192
 193 /// processBasicBlock - Loop over all of the instructions in the basic block,
 194 /// transforming FP instructions into their stack form.
 195 ///
 196 bool FPS::processBasicBlock(MachineFunction &MF, MachineBasicBlock &BB) {
 197   const TargetInstrInfo &TII = *MF.getTarget().getInstrInfo();
 198   bool Changed = false;
 199   MBB = &BB;
 200
 201   for (MachineBasicBlock::iterator I = BB.begin(); I != BB.end(); ++I) {
 202     MachineInstr *MI = I;
 203     unsigned Flags = TII.get(MI->getOpcode()).TSFlags;
 204     if ((Flags & X86II::FPTypeMask) == X86II::NotFP)
 205       continue;  // Efficiently ignore non-fp insts!
 206
 207     MachineInstr *PrevMI = 0;
 208     if (I != BB.begin())
 209         PrevMI = prior(I);
 210
 211     ++NumFP;  // Keep track of # of pseudo instrs
 212     DEBUG(std::cerr << "\nFPInst:\t"; MI->print(std::cerr, &(MF.getTarget())));
 213
 214     // Get dead variables list now because the MI pointer may be deleted as part
 215     // of processing!
 216     LiveVariables::killed_iterator IB, IE;
 217     tie(IB, IE) = LV->dead_range(MI);
 218
 219     DEBUG(
 220       const MRegisterInfo *MRI = MF.getTarget().getRegisterInfo();
 221       LiveVariables::killed_iterator I = LV->killed_begin(MI);
 222       LiveVariables::killed_iterator E = LV->killed_end(MI);
 223       if (I != E) {
 224         std::cerr << "Killed Operands:";
 225         for (; I != E; ++I)
 226           std::cerr << " %" << MRI->getName(*I);
 227         std::cerr << "\n";
 228       }
 229     );
 230
 231     switch (Flags & X86II::FPTypeMask) {
 232     case X86II::ZeroArgFP:  handleZeroArgFP(I); break;
 233     case X86II::OneArgFP:   handleOneArgFP(I);  break;  // fstp ST(0)
 234     case X86II::OneArgFPRW: handleOneArgFPRW(I); break; // ST(0) = fsqrt(ST(0))
 235     case X86II::TwoArgFP:   handleTwoArgFP(I); break;
 236     case X86II::CompareFP:  handleCompareFP(I); break;
 237     case X86II::CondMovFP:  handleCondMovFP(I); break;
 238     case X86II::SpecialFP:  handleSpecialFP(I); break;
 239     default: assert(0 && "Unknown FP Type!");
 240     }
 241
 242     // Check to see if any of the values defined by this instruction are dead
 243     // after definition.  If so, pop them.
 244     for (; IB != IE; ++IB) {
 245       unsigned Reg = *IB;
 246       if (Reg >= X86::FP0 && Reg <= X86::FP6) {
 247         DEBUG(std::cerr << "Register FP#" << Reg-X86::FP0 << " is dead!\n");
 248         freeStackSlotAfter(I, Reg-X86::FP0);
 249       }
 250     }
 251
 252     // Print out all of the instructions expanded to if -debug
 253     DEBUG(
 254       MachineBasicBlock::iterator PrevI(PrevMI);
 255       if (I == PrevI) {
 256         std::cerr << "Just deleted pseudo instruction\n";
 257       } else {
 258         MachineBasicBlock::iterator Start = I;
 259         // Rewind to first instruction newly inserted.
 260         while (Start != BB.begin() && prior(Start) != PrevI) --Start;
 261         std::cerr << "Inserted instructions:\n\t";
 262         Start->print(std::cerr, &MF.getTarget());
 263         while (++Start != next(I));
 264       }
 265       dumpStack();
 266     );
 267
 268     Changed = true;
 269   }
 270
 271   assert(StackTop == 0 && "Stack not empty at end of basic block?");
 272   return Changed;
 273 }
 274
 275 //===----------------------------------------------------------------------===//
 276 // Efficient Lookup Table Support
 277 //===----------------------------------------------------------------------===//
 278
 279 namespace {
 280   struct TableEntry {
 281     unsigned from;
 282     unsigned to;
 283     bool operator<(const TableEntry &TE) const { return from < TE.from; }
 284     friend bool operator<(const TableEntry &TE, unsigned V) {
 285       return TE.from < V;
 286     }
 287     friend bool operator<(unsigned V, const TableEntry &TE) {
 288       return V < TE.from;
 289     }
 290   };
 291 }
 292
 293 static bool TableIsSorted(const TableEntry *Table, unsigned NumEntries) {
 294   for (unsigned i = 0; i != NumEntries-1; ++i)
 295     if (!(Table[i] < Table[i+1])) return false;
 296   return true;
 297 }
 298
 299 static int Lookup(const TableEntry *Table, unsigned N, unsigned Opcode) {
 300   const TableEntry *I = std::lower_bound(Table, Table+N, Opcode);
 301   if (I != Table+N && I->from == Opcode)
 302     return I->to;
 303   return -1;
 304 }
 305
 306 #define ARRAY_SIZE(TABLE)  \
 307    (sizeof(TABLE)/sizeof(TABLE[0]))
 308
 309 #ifdef NDEBUG
 310 #define ASSERT_SORTED(TABLE)
 311 #else
 312 #define ASSERT_SORTED(TABLE)                                              \
 313   { static bool TABLE##Checked = false;                                   \
 314     if (!TABLE##Checked) {                                                \
 315        assert(TableIsSorted(TABLE, ARRAY_SIZE(TABLE)) &&                  \
 316               "All lookup tables must be sorted for efficient access!");  \
 317        TABLE##Checked = true;                                             \
 318     }                                                                     \
 319   }
 320 #endif
 321
 322 //===----------------------------------------------------------------------===//
 323 // Register File -> Register Stack Mapping Methods
 324 //===----------------------------------------------------------------------===//
 325
 326 // OpcodeTable - Sorted map of register instructions to their stack version.
 327 // The first element is an register file pseudo instruction, the second is the
 328 // concrete X86 instruction which uses the register stack.
 329 //
 330 static const TableEntry OpcodeTable[] = {
 331   { X86::FpABS     , X86::FABS     },
 332   { X86::FpADD32m  , X86::FADD32m  },
 333   { X86::FpADD64m  , X86::FADD64m  },
 334   { X86::FpCHS     , X86::FCHS     },
 335   { X86::FpCMOVB   , X86::FCMOVB   },
 336   { X86::FpCMOVBE  , X86::FCMOVBE  },
 337   { X86::FpCMOVE   , X86::FCMOVE   },
 338   { X86::FpCMOVNB  , X86::FCMOVNB  },
 339   { X86::FpCMOVNBE , X86::FCMOVNBE },
 340   { X86::FpCMOVNE  , X86::FCMOVNE  },
 341   { X86::FpCMOVNP  , X86::FCMOVNP  },
 342   { X86::FpCMOVP   , X86::FCMOVP   },
 343   { X86::FpCOS     , X86::FCOS     },
 344   { X86::FpDIV32m  , X86::FDIV32m  },
 345   { X86::FpDIV64m  , X86::FDIV64m  },
 346   { X86::FpDIVR32m , X86::FDIVR32m },
 347   { X86::FpDIVR64m , X86::FDIVR64m },
 348   { X86::FpIADD16m , X86::FIADD16m },
 349   { X86::FpIADD32m , X86::FIADD32m },
 350   { X86::FpIDIV16m , X86::FIDIV16m },
 351   { X86::FpIDIV32m , X86::FIDIV32m },
 352   { X86::FpIDIVR16m, X86::FIDIVR16m},
 353   { X86::FpIDIVR32m, X86::FIDIVR32m},
 354   { X86::FpILD16m  , X86::FILD16m  },
 355   { X86::FpILD32m  , X86::FILD32m  },
 356   { X86::FpILD64m  , X86::FILD64m  },
 357   { X86::FpIMUL16m , X86::FIMUL16m },
 358   { X86::FpIMUL32m , X86::FIMUL32m },
 359   { X86::FpIST16m  , X86::FIST16m  },
 360   { X86::FpIST32m  , X86::FIST32m  },
 361   { X86::FpIST64m  , X86::FISTP64m },
 362   { X86::FpISTT16m , X86::FISTTP16m},
 363   { X86::FpISTT32m , X86::FISTTP32m},
 364   { X86::FpISTT64m , X86::FISTTP64m},
 365   { X86::FpISUB16m , X86::FISUB16m },
 366   { X86::FpISUB32m , X86::FISUB32m },
 367   { X86::FpISUBR16m, X86::FISUBR16m},
 368   { X86::FpISUBR32m, X86::FISUBR32m},
 369   { X86::FpLD0     , X86::FLD0     },
 370   { X86::FpLD1     , X86::FLD1     },
 371   { X86::FpLD32m   , X86::FLD32m   },
 372   { X86::FpLD64m   , X86::FLD64m   },
 373   { X86::FpMUL32m  , X86::FMUL32m  },
 374   { X86::FpMUL64m  , X86::FMUL64m  },
 375   { X86::FpSIN     , X86::FSIN     },
 376   { X86::FpSQRT    , X86::FSQRT    },
 377   { X86::FpST32m   , X86::FST32m   },
 378   { X86::FpST64m   , X86::FST64m   },
 379   { X86::FpSUB32m  , X86::FSUB32m  },
 380   { X86::FpSUB64m  , X86::FSUB64m  },
 381   { X86::FpSUBR32m , X86::FSUBR32m },
 382   { X86::FpSUBR64m , X86::FSUBR64m },
 383   { X86::FpTST     , X86::FTST     },
 384   { X86::FpUCOMIr  , X86::FUCOMIr  },
 385   { X86::FpUCOMr   , X86::FUCOMr   },
 386 };
 387
 388 static unsigned getConcreteOpcode(unsigned Opcode) {
 389   ASSERT_SORTED(OpcodeTable);
 390   int Opc = Lookup(OpcodeTable, ARRAY_SIZE(OpcodeTable), Opcode);
 391   assert(Opc != -1 && "FP Stack instruction not in OpcodeTable!");
 392   return Opc;
 393 }
 394
 395 //===----------------------------------------------------------------------===//
 396 // Helper Methods
 397 //===----------------------------------------------------------------------===//
 398
 399 // PopTable - Sorted map of instructions to their popping version.  The first
 400 // element is an instruction, the second is the version which pops.
 401 //
 402 static const TableEntry PopTable[] = {
 403   { X86::FADDrST0 , X86::FADDPrST0  },
 404
 405   { X86::FDIVRrST0, X86::FDIVRPrST0 },
 406   { X86::FDIVrST0 , X86::FDIVPrST0  },
 407
 408   { X86::FIST16m  , X86::FISTP16m   },
 409   { X86::FIST32m  , X86::FISTP32m   },
 410
 411   { X86::FMULrST0 , X86::FMULPrST0  },
 412
 413   { X86::FST32m   , X86::FSTP32m    },
 414   { X86::FST64m   , X86::FSTP64m    },
 415   { X86::FSTrr    , X86::FSTPrr     },
 416
 417   { X86::FSUBRrST0, X86::FSUBRPrST0 },
 418   { X86::FSUBrST0 , X86::FSUBPrST0  },
 419
 420   { X86::FUCOMIr  , X86::FUCOMIPr   },
 421
 422   { X86::FUCOMPr  , X86::FUCOMPPr   },
 423   { X86::FUCOMr   , X86::FUCOMPr    },
 424 };
 425
 426 /// popStackAfter - Pop the current value off of the top of the FP stack after
 427 /// the specified instruction.  This attempts to be sneaky and combine the pop
 428 /// into the instruction itself if possible.  The iterator is left pointing to
 429 /// the last instruction, be it a new pop instruction inserted, or the old
 430 /// instruction if it was modified in place.
 431 ///
 432 void FPS::popStackAfter(MachineBasicBlock::iterator &I) {
 433   ASSERT_SORTED(PopTable);
 434   assert(StackTop > 0 && "Cannot pop empty stack!");
 435   RegMap[Stack[--StackTop]] = ~0;     // Update state
 436
 437   // Check to see if there is a popping version of this instruction...
 438   int Opcode = Lookup(PopTable, ARRAY_SIZE(PopTable), I->getOpcode());
 439   if (Opcode != -1) {
 440     I->setOpcode(Opcode);
 441     if (Opcode == X86::FUCOMPPr)
 442       I->RemoveOperand(0);
 443
 444   } else {    // Insert an explicit pop
 445     I = BuildMI(*MBB, ++I, X86::FSTPrr, 1).addReg(X86::ST0);
 446   }
 447 }
 448
 449 /// freeStackSlotAfter - Free the specified register from the register stack, so
 450 /// that it is no longer in a register.  If the register is currently at the top
 451 /// of the stack, we just pop the current instruction, otherwise we store the
 452 /// current top-of-stack into the specified slot, then pop the top of stack.
 453 void FPS::freeStackSlotAfter(MachineBasicBlock::iterator &I, unsigned FPRegNo) {
 454   if (getStackEntry(0) == FPRegNo) {  // already at the top of stack? easy.
 455     popStackAfter(I);
 456     return;
 457   }
 458
 459   // Otherwise, store the top of stack into the dead slot, killing the operand
 460   // without having to add in an explicit xchg then pop.
 461   //
 462   unsigned STReg    = getSTReg(FPRegNo);
 463   unsigned OldSlot  = getSlot(FPRegNo);
 464   unsigned TopReg   = Stack[StackTop-1];
 465   Stack[OldSlot]    = TopReg;
 466   RegMap[TopReg]    = OldSlot;
 467   RegMap[FPRegNo]   = ~0;
 468   Stack[--StackTop] = ~0;
 469   I = BuildMI(*MBB, ++I, X86::FSTPrr, 1).addReg(STReg);
 470 }
 471
 472
 473 static unsigned getFPReg(const MachineOperand &MO) {
 474   assert(MO.isRegister() && "Expected an FP register!");
 475   unsigned Reg = MO.getReg();
 476   assert(Reg >= X86::FP0 && Reg <= X86::FP6 && "Expected FP register!");
 477   return Reg - X86::FP0;
 478 }
 479
 480
 481 //===----------------------------------------------------------------------===//
 482 // Instruction transformation implementation
 483 //===----------------------------------------------------------------------===//
 484
 485 /// handleZeroArgFP - ST(0) = fld0    ST(0) = flds <mem>
 486 ///
 487 void FPS::handleZeroArgFP(MachineBasicBlock::iterator &I) {
 488   MachineInstr *MI = I;
 489   unsigned DestReg = getFPReg(MI->getOperand(0));
 490
 491   // Change from the pseudo instruction to the concrete instruction.
 492   MI->RemoveOperand(0);   // Remove the explicit ST(0) operand
 493   MI->setOpcode(getConcreteOpcode(MI->getOpcode()));
 494
 495   // Result gets pushed on the stack.
 496   pushReg(DestReg);
 497 }
 498
 499 /// handleOneArgFP - fst <mem>, ST(0)
 500 ///
 501 void FPS::handleOneArgFP(MachineBasicBlock::iterator &I) {
 502   MachineInstr *MI = I;
 503   assert((MI->getNumOperands() == 5 || MI->getNumOperands() == 1) &&
 504          "Can only handle fst* & ftst instructions!");
 505
 506   // Is this the last use of the source register?
 507   unsigned Reg = getFPReg(MI->getOperand(MI->getNumOperands()-1));
 508   bool KillsSrc = LV->KillsRegister(MI, X86::FP0+Reg);
 509
 510   // FISTP64m is strange because there isn't a non-popping versions.
 511   // If we have one _and_ we don't want to pop the operand, duplicate the value
 512   // on the stack instead of moving it.  This ensure that popping the value is
 513   // always ok.
 514   // Ditto FISTTP16m, FISTTP32m, FISTTP64m.
 515   //
 516   if (!KillsSrc &&
 517       (MI->getOpcode() == X86::FpIST64m ||
 518        MI->getOpcode() == X86::FpISTT16m ||
 519        MI->getOpcode() == X86::FpISTT32m ||
 520        MI->getOpcode() == X86::FpISTT64m)) {
 521     duplicateToTop(Reg, 7 /*temp register*/, I);
 522   } else {
 523     moveToTop(Reg, I);            // Move to the top of the stack...
 524   }
 525
 526   // Convert from the pseudo instruction to the concrete instruction.
 527   MI->RemoveOperand(MI->getNumOperands()-1);    // Remove explicit ST(0) operand
 528   MI->setOpcode(getConcreteOpcode(MI->getOpcode()));
 529
 530   if (MI->getOpcode() == X86::FISTP64m ||
 531       MI->getOpcode() == X86::FISTTP16m ||
 532       MI->getOpcode() == X86::FISTTP32m ||
 533       MI->getOpcode() == X86::FISTTP64m) {
 534     assert(StackTop > 0 && "Stack empty??");
 535     --StackTop;
 536   } else if (KillsSrc) { // Last use of operand?
 537     popStackAfter(I);
 538   }
 539 }
 540
 541
 542 /// handleOneArgFPRW: Handle instructions that read from the top of stack and
 543 /// replace the value with a newly computed value.  These instructions may have
 544 /// non-fp operands after their FP operands.
 545 ///
 546 ///  Examples:
 547 ///     R1 = fchs R2
 548 ///     R1 = fadd R2, [mem]
 549 ///
 550 void FPS::handleOneArgFPRW(MachineBasicBlock::iterator &I) {
 551   MachineInstr *MI = I;
 552   assert(MI->getNumOperands() >= 2 && "FPRW instructions must have 2 ops!!");
 553
 554   // Is this the last use of the source register?
 555   unsigned Reg = getFPReg(MI->getOperand(1));
 556   bool KillsSrc = LV->KillsRegister(MI, X86::FP0+Reg);
 557
 558   if (KillsSrc) {
 559     // If this is the last use of the source register, just make sure it's on
 560     // the top of the stack.
 561     moveToTop(Reg, I);
 562     assert(StackTop > 0 && "Stack cannot be empty!");
 563     --StackTop;
 564     pushReg(getFPReg(MI->getOperand(0)));
 565   } else {
 566     // If this is not the last use of the source register, _copy_ it to the top
 567     // of the stack.
 568     duplicateToTop(Reg, getFPReg(MI->getOperand(0)), I);
 569   }
 570
 571   // Change from the pseudo instruction to the concrete instruction.
 572   MI->RemoveOperand(1);   // Drop the source operand.
 573   MI->RemoveOperand(0);   // Drop the destination operand.
 574   MI->setOpcode(getConcreteOpcode(MI->getOpcode()));
 575 }
 576
 577
 578 //===----------------------------------------------------------------------===//
 579 // Define tables of various ways to map pseudo instructions
 580 //
 581
 582 // ForwardST0Table - Map: A = B op C  into: ST(0) = ST(0) op ST(i)
 583 static const TableEntry ForwardST0Table[] = {
 584   { X86::FpADD  , X86::FADDST0r },
 585   { X86::FpDIV  , X86::FDIVST0r },
 586   { X86::FpMUL  , X86::FMULST0r },
 587   { X86::FpSUB  , X86::FSUBST0r },
 588 };
 589
 590 // ReverseST0Table - Map: A = B op C  into: ST(0) = ST(i) op ST(0)
 591 static const TableEntry ReverseST0Table[] = {
 592   { X86::FpADD  , X86::FADDST0r  },   // commutative
 593   { X86::FpDIV  , X86::FDIVRST0r },
 594   { X86::FpMUL  , X86::FMULST0r  },   // commutative
 595   { X86::FpSUB  , X86::FSUBRST0r },
 596 };
 597
 598 // ForwardSTiTable - Map: A = B op C  into: ST(i) = ST(0) op ST(i)
 599 static const TableEntry ForwardSTiTable[] = {
 600   { X86::FpADD  , X86::FADDrST0  },   // commutative
 601   { X86::FpDIV  , X86::FDIVRrST0 },
 602   { X86::FpMUL  , X86::FMULrST0  },   // commutative
 603   { X86::FpSUB  , X86::FSUBRrST0 },
 604 };
 605
 606 // ReverseSTiTable - Map: A = B op C  into: ST(i) = ST(i) op ST(0)
 607 static const TableEntry ReverseSTiTable[] = {
 608   { X86::FpADD  , X86::FADDrST0 },
 609   { X86::FpDIV  , X86::FDIVrST0 },
 610   { X86::FpMUL  , X86::FMULrST0 },
 611   { X86::FpSUB  , X86::FSUBrST0 },
 612 };
 613
 614
 615 /// handleTwoArgFP - Handle instructions like FADD and friends which are virtual
 616 /// instructions which need to be simplified and possibly transformed.
 617 ///
 618 /// Result: ST(0) = fsub  ST(0), ST(i)
 619 ///         ST(i) = fsub  ST(0), ST(i)
 620 ///         ST(0) = fsubr ST(0), ST(i)
 621 ///         ST(i) = fsubr ST(0), ST(i)
 622 ///
 623 void FPS::handleTwoArgFP(MachineBasicBlock::iterator &I) {
 624   ASSERT_SORTED(ForwardST0Table); ASSERT_SORTED(ReverseST0Table);
 625   ASSERT_SORTED(ForwardSTiTable); ASSERT_SORTED(ReverseSTiTable);
 626   MachineInstr *MI = I;
 627
 628   unsigned NumOperands = MI->getNumOperands();
 629   assert(NumOperands == 3 && "Illegal TwoArgFP instruction!");
 630   unsigned Dest = getFPReg(MI->getOperand(0));
 631   unsigned Op0 = getFPReg(MI->getOperand(NumOperands-2));
 632   unsigned Op1 = getFPReg(MI->getOperand(NumOperands-1));
 633   bool KillsOp0 = LV->KillsRegister(MI, X86::FP0+Op0);
 634   bool KillsOp1 = LV->KillsRegister(MI, X86::FP0+Op1);
 635
 636   unsigned TOS = getStackEntry(0);
 637
 638   // One of our operands must be on the top of the stack.  If neither is yet, we
 639   // need to move one.
 640   if (Op0 != TOS && Op1 != TOS) {   // No operand at TOS?
 641     // We can choose to move either operand to the top of the stack.  If one of
 642     // the operands is killed by this instruction, we want that one so that we
 643     // can update right on top of the old version.
 644     if (KillsOp0) {
 645       moveToTop(Op0, I);         // Move dead operand to TOS.
 646       TOS = Op0;
 647     } else if (KillsOp1) {
 648       moveToTop(Op1, I);
 649       TOS = Op1;
 650     } else {
 651       // All of the operands are live after this instruction executes, so we
 652       // cannot update on top of any operand.  Because of this, we must
 653       // duplicate one of the stack elements to the top.  It doesn't matter
 654       // which one we pick.
 655       //
 656       duplicateToTop(Op0, Dest, I);
 657       Op0 = TOS = Dest;
 658       KillsOp0 = true;
 659     }
 660   } else if (!KillsOp0 && !KillsOp1) {
 661     // If we DO have one of our operands at the top of the stack, but we don't
 662     // have a dead operand, we must duplicate one of the operands to a new slot
 663     // on the stack.
 664     duplicateToTop(Op0, Dest, I);
 665     Op0 = TOS = Dest;
 666     KillsOp0 = true;
 667   }
 668
 669   // Now we know that one of our operands is on the top of the stack, and at
 670   // least one of our operands is killed by this instruction.
 671   assert((TOS == Op0 || TOS == Op1) && (KillsOp0 || KillsOp1) &&
 672          "Stack conditions not set up right!");
 673
 674   // We decide which form to use based on what is on the top of the stack, and
 675   // which operand is killed by this instruction.
 676   const TableEntry *InstTable;
 677   bool isForward = TOS == Op0;
 678   bool updateST0 = (TOS == Op0 && !KillsOp1) || (TOS == Op1 && !KillsOp0);
 679   if (updateST0) {
 680     if (isForward)
 681       InstTable = ForwardST0Table;
 682     else
 683       InstTable = ReverseST0Table;
 684   } else {
 685     if (isForward)
 686       InstTable = ForwardSTiTable;
 687     else
 688       InstTable = ReverseSTiTable;
 689   }
 690
 691   int Opcode = Lookup(InstTable, ARRAY_SIZE(ForwardST0Table), MI->getOpcode());
 692   assert(Opcode != -1 && "Unknown TwoArgFP pseudo instruction!");
 693
 694   // NotTOS - The register which is not on the top of stack...
 695   unsigned NotTOS = (TOS == Op0) ? Op1 : Op0;
 696
 697   // Replace the old instruction with a new instruction
 698   MBB->remove(I++);
 699   I = BuildMI(*MBB, I, Opcode, 1).addReg(getSTReg(NotTOS));
 700
 701   // If both operands are killed, pop one off of the stack in addition to
 702   // overwriting the other one.
 703   if (KillsOp0 && KillsOp1 && Op0 != Op1) {
 704     assert(!updateST0 && "Should have updated other operand!");
 705     popStackAfter(I);   // Pop the top of stack
 706   }
 707
 708   // Update stack information so that we know the destination register is now on
 709   // the stack.
 710   unsigned UpdatedSlot = getSlot(updateST0 ? TOS : NotTOS);
 711   assert(UpdatedSlot < StackTop && Dest < 7);
 712   Stack[UpdatedSlot]   = Dest;
 713   RegMap[Dest]         = UpdatedSlot;
 714   delete MI;   // Remove the old instruction
 715 }
 716
 717 /// handleCompareFP - Handle FUCOM and FUCOMI instructions, which have two FP
 718 /// register arguments and no explicit destinations.
 719 ///
 720 void FPS::handleCompareFP(MachineBasicBlock::iterator &I) {
 721   ASSERT_SORTED(ForwardST0Table); ASSERT_SORTED(ReverseST0Table);
 722   ASSERT_SORTED(ForwardSTiTable); ASSERT_SORTED(ReverseSTiTable);
 723   MachineInstr *MI = I;
 724
 725   unsigned NumOperands = MI->getNumOperands();
 726   assert(NumOperands == 2 && "Illegal FUCOM* instruction!");
 727   unsigned Op0 = getFPReg(MI->getOperand(NumOperands-2));
 728   unsigned Op1 = getFPReg(MI->getOperand(NumOperands-1));
 729   bool KillsOp0 = LV->KillsRegister(MI, X86::FP0+Op0);
 730   bool KillsOp1 = LV->KillsRegister(MI, X86::FP0+Op1);
 731
 732   // Make sure the first operand is on the top of stack, the other one can be
 733   // anywhere.
 734   moveToTop(Op0, I);
 735
 736   // Change from the pseudo instruction to the concrete instruction.
 737   MI->getOperand(0).setReg(getSTReg(Op1));
 738   MI->RemoveOperand(1);
 739   MI->setOpcode(getConcreteOpcode(MI->getOpcode()));
 740
 741   // If any of the operands are killed by this instruction, free them.
 742   if (KillsOp0) freeStackSlotAfter(I, Op0);
 743   if (KillsOp1 && Op0 != Op1) freeStackSlotAfter(I, Op1);
 744 }
 745
 746 /// handleCondMovFP - Handle two address conditional move instructions.  These
 747 /// instructions move a st(i) register to st(0) iff a condition is true.  These
 748 /// instructions require that the first operand is at the top of the stack, but
 749 /// otherwise don't modify the stack at all.
 750 void FPS::handleCondMovFP(MachineBasicBlock::iterator &I) {
 751   MachineInstr *MI = I;
 752
 753   unsigned Op0 = getFPReg(MI->getOperand(0));
 754   unsigned Op1 = getFPReg(MI->getOperand(2));
 755
 756   // The first operand *must* be on the top of the stack.
 757   moveToTop(Op0, I);
 758
 759   // Change the second operand to the stack register that the operand is in.
 760   // Change from the pseudo instruction to the concrete instruction.
 761   MI->RemoveOperand(0);
 762   MI->RemoveOperand(1);
 763   MI->getOperand(0).setReg(getSTReg(Op1));
 764   MI->setOpcode(getConcreteOpcode(MI->getOpcode()));
 765
 766
 767   // If we kill the second operand, make sure to pop it from the stack.
 768   if (Op0 != Op1 && LV->KillsRegister(MI, X86::FP0+Op1)) {
 769     // Get this value off of the register stack.
 770     freeStackSlotAfter(I, Op1);
 771   }
 772 }
 773
 774
 775 /// handleSpecialFP - Handle special instructions which behave unlike other
 776 /// floating point instructions.  This is primarily intended for use by pseudo
 777 /// instructions.
 778 ///
 779 void FPS::handleSpecialFP(MachineBasicBlock::iterator &I) {
 780   MachineInstr *MI = I;
 781   switch (MI->getOpcode()) {
 782   default: assert(0 && "Unknown SpecialFP instruction!");
 783   case X86::FpGETRESULT:  // Appears immediately after a call returning FP type!
 784     assert(StackTop == 0 && "Stack should be empty after a call!");
 785     pushReg(getFPReg(MI->getOperand(0)));
 786     break;
 787   case X86::FpSETRESULT:
 788     assert(StackTop == 1 && "Stack should have one element on it to return!");
 789     --StackTop;   // "Forget" we have something on the top of stack!
 790     break;
 791   case X86::FpMOV: {
 792     unsigned SrcReg = getFPReg(MI->getOperand(1));
 793     unsigned DestReg = getFPReg(MI->getOperand(0));
 794
 795     if (LV->KillsRegister(MI, X86::FP0+SrcReg)) {
 796       // If the input operand is killed, we can just change the owner of the
 797       // incoming stack slot into the result.
 798       unsigned Slot = getSlot(SrcReg);
 799       assert(Slot < 7 && DestReg < 7 && "FpMOV operands invalid!");
 800       Stack[Slot] = DestReg;
 801       RegMap[DestReg] = Slot;
 802
 803     } else {
 804       // For FMOV we just duplicate the specified value to a new stack slot.
 805       // This could be made better, but would require substantial changes.
 806       duplicateToTop(SrcReg, DestReg, I);
 807     }
 808     break;
 809   }
 810   }
 811
 812   I = MBB->erase(I);  // Remove the pseudo instruction
 813   --I;
 814 }