X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTarget%2FX86%2FX86FloatingPoint.cpp;h=5da6d3ae5cba67c4e2f9747c153c050838f8f1f4;hb=0be938e38916cecd4d3406c8531a341b2e1c9ec5;hp=5fe21ac8a1904ffff683f574479aa6e1cf5584bb;hpb=3eca98bb3ab1ec27ab8763298c416d282cdaa261;p=oota-llvm.git diff --git a/lib/Target/X86/X86FloatingPoint.cpp b/lib/Target/X86/X86FloatingPoint.cpp index 5fe21ac8a19..5da6d3ae5cb 100644 --- a/lib/Target/X86/X86FloatingPoint.cpp +++ b/lib/Target/X86/X86FloatingPoint.cpp @@ -8,23 +8,18 @@ //===----------------------------------------------------------------------===// // // This file defines the pass which converts floating point instructions from -// virtual registers into register stack instructions. This pass uses live +// pseudo registers into register stack instructions. This pass uses live // variable information to indicate where the FPn registers are used and their // lifetimes. // -// This pass is hampered by the lack of decent CFG manipulation routines for -// machine code. In particular, this wants to be able to split critical edges -// as necessary, traverse the machine basic block CFG in depth-first order, and -// allow there to be multiple machine basic blocks for each LLVM basicblock -// (needed for critical edge splitting). +// The x87 hardware tracks liveness of the stack registers, so it is necessary +// to implement exact liveness tracking between basic blocks. The CFG edges are +// partitioned into bundles where the same FP registers must be live in +// identical stack positions. Instructions are inserted at the end of each basic +// block to rearrange the live registers to match the outgoing bundle. // -// In particular, this pass currently barfs on critical edges. Because of this, -// it requires the instruction selector to insert FP_REG_KILL instructions on -// the exits of any basic block that has critical edges going from it, or which -// branch to a critical basic block. -// -// FIXME: this is not implemented yet. The stackifier pass only works on local -// basic blocks. +// This approach avoids splitting critical edges at the potential cost of more +// live register shuffling instructions when critical edges are present. // //===----------------------------------------------------------------------===// @@ -32,6 +27,7 @@ #include "X86.h" #include "X86InstrInfo.h" #include "llvm/ADT/DepthFirstIterator.h" +#include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" @@ -54,7 +50,12 @@ STATISTIC(NumFP , "Number of floating point instructions"); namespace { struct FPS : public MachineFunctionPass { static char ID; - FPS() : MachineFunctionPass(&ID) {} + FPS() : MachineFunctionPass(ID) { + // This is really only to keep valgrind quiet. + // The logic in isLive() is too much for it. + memset(Stack, 0, sizeof(Stack)); + memset(RegMap, 0, sizeof(RegMap)); + } virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesCFG(); @@ -69,11 +70,71 @@ namespace { private: const TargetInstrInfo *TII; // Machine instruction info. + + // Two CFG edges are related if they leave the same block, or enter the same + // block. The transitive closure of an edge under this relation is a + // LiveBundle. It represents a set of CFG edges where the live FP stack + // registers must be allocated identically in the x87 stack. + // + // A LiveBundle is usually all the edges leaving a block, or all the edges + // entering a block, but it can contain more edges if critical edges are + // present. + // + // The set of live FP registers in a LiveBundle is calculated by bundleCFG, + // but the exact mapping of FP registers to stack slots is fixed later. + struct LiveBundle { + // Bit mask of live FP registers. Bit 0 = FP0, bit 1 = FP1, &c. + unsigned Mask; + + // Number of pre-assigned live registers in FixStack. This is 0 when the + // stack order has not yet been fixed. + unsigned FixCount; + + // Assigned stack order for live-in registers. + // FixStack[i] == getStackEntry(i) for all i < FixCount. + unsigned char FixStack[8]; + + LiveBundle(unsigned m = 0) : Mask(m), FixCount(0) {} + + // Have the live registers been assigned a stack order yet? + bool isFixed() const { return !Mask || FixCount; } + }; + + // Numbered LiveBundle structs. LiveBundles[0] is used for all CFG edges + // with no live FP registers. + SmallVector LiveBundles; + + // Map each MBB in the current function to an (ingoing, outgoing) index into + // LiveBundles. Blocks with no FP registers live in or out map to (0, 0) + // and are not actually stored in the map. + DenseMap > BlockBundle; + + // Return a bitmask of FP registers in block's live-in list. + unsigned calcLiveInMask(MachineBasicBlock *MBB) { + unsigned Mask = 0; + for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(), + E = MBB->livein_end(); I != E; ++I) { + unsigned Reg = *I - X86::FP0; + if (Reg < 8) + Mask |= 1 << Reg; + } + return Mask; + } + + // Partition all the CFG edges into LiveBundles. + void bundleCFG(MachineFunction &MF); + MachineBasicBlock *MBB; // Current basic block unsigned Stack[8]; // FP Registers in each stack slot... unsigned RegMap[8]; // Track which stack slot contains each register unsigned StackTop; // The current top of the FP stack. + // Set up our stack model to match the incoming registers to MBB. + void setupBlockStack(); + + // Shuffle live registers to match the expectations of successor blocks. + void finishBlockStack(); + void dumpStack() const { dbgs() << "Stack contents:"; for (unsigned i = 0; i != StackTop; ++i) { @@ -82,27 +143,37 @@ namespace { } dbgs() << "\n"; } - private: - /// isStackEmpty - Return true if the FP stack is empty. - bool isStackEmpty() const { - return StackTop == 0; - } - - // getSlot - Return the stack slot number a particular register number is - // in. + + /// getSlot - Return the stack slot number a particular register number is + /// in. unsigned getSlot(unsigned RegNo) const { assert(RegNo < 8 && "Regno out of range!"); return RegMap[RegNo]; } - // getStackEntry - Return the X86::FP register in register ST(i). + /// isLive - Is RegNo currently live in the stack? + bool isLive(unsigned RegNo) const { + unsigned Slot = getSlot(RegNo); + return Slot < StackTop && Stack[Slot] == RegNo; + } + + /// getScratchReg - Return an FP register that is not currently in use. + unsigned getScratchReg() { + for (int i = 7; i >= 0; --i) + if (!isLive(i)) + return i; + llvm_unreachable("Ran out of scratch FP registers"); + } + + /// getStackEntry - Return the X86::FP register in register ST(i). unsigned getStackEntry(unsigned STi) const { - assert(STi < StackTop && "Access past stack top!"); + if (STi >= StackTop) + report_fatal_error("Access past stack top!"); return Stack[StackTop-1-STi]; } - // getSTReg - Return the X86::ST(i) register which contains the specified - // FP register. + /// getSTReg - Return the X86::ST(i) register which contains the specified + /// FP register. unsigned getSTReg(unsigned RegNo) const { return StackTop - 1 - getSlot(RegNo) + llvm::X86::ST0; } @@ -110,17 +181,17 @@ namespace { // pushReg - Push the specified FP register onto the stack. void pushReg(unsigned Reg) { assert(Reg < 8 && "Register number out of range!"); - assert(StackTop < 8 && "Stack overflow!"); + if (StackTop >= 8) + report_fatal_error("Stack overflow!"); Stack[StackTop] = Reg; RegMap[Reg] = StackTop++; } bool isAtTop(unsigned RegNo) const { return getSlot(RegNo) == StackTop-1; } void moveToTop(unsigned RegNo, MachineBasicBlock::iterator I) { - MachineInstr *MI = I; - DebugLoc dl = MI->getDebugLoc(); + DebugLoc dl = I == MBB->end() ? DebugLoc() : I->getDebugLoc(); if (isAtTop(RegNo)) return; - + unsigned STReg = getSTReg(RegNo); unsigned RegOnTop = getStackEntry(0); @@ -128,33 +199,47 @@ namespace { std::swap(RegMap[RegNo], RegMap[RegOnTop]); // Swap stack slot contents. - assert(RegMap[RegOnTop] < StackTop); + if (RegMap[RegOnTop] >= StackTop) + report_fatal_error("Access past stack top!"); std::swap(Stack[RegMap[RegOnTop]], Stack[StackTop-1]); // Emit an fxch to update the runtime processors version of the state. BuildMI(*MBB, I, dl, TII->get(X86::XCH_F)).addReg(STReg); - NumFXCH++; + ++NumFXCH; } void duplicateToTop(unsigned RegNo, unsigned AsReg, MachineInstr *I) { - DebugLoc dl = I->getDebugLoc(); + DebugLoc dl = I == MBB->end() ? DebugLoc() : I->getDebugLoc(); unsigned STReg = getSTReg(RegNo); pushReg(AsReg); // New register on top of stack BuildMI(*MBB, I, dl, TII->get(X86::LD_Frr)).addReg(STReg); } - // popStackAfter - Pop the current value off of the top of the FP stack - // after the specified instruction. + /// popStackAfter - Pop the current value off of the top of the FP stack + /// after the specified instruction. void popStackAfter(MachineBasicBlock::iterator &I); - // freeStackSlotAfter - Free the specified register from the register stack, - // so that it is no longer in a register. If the register is currently at - // the top of the stack, we just pop the current instruction, otherwise we - // store the current top-of-stack into the specified slot, then pop the top - // of stack. + /// freeStackSlotAfter - Free the specified register from the register + /// stack, so that it is no longer in a register. If the register is + /// currently at the top of the stack, we just pop the current instruction, + /// otherwise we store the current top-of-stack into the specified slot, + /// then pop the top of stack. void freeStackSlotAfter(MachineBasicBlock::iterator &I, unsigned Reg); + /// freeStackSlotBefore - Just the pop, no folding. Return the inserted + /// instruction. + MachineBasicBlock::iterator + freeStackSlotBefore(MachineBasicBlock::iterator I, unsigned FPRegNo); + + /// Adjust the live registers to be the set in Mask. + void adjustLiveRegs(unsigned Mask, MachineBasicBlock::iterator I); + + /// Shuffle the top FixCount stack entries susch that FP reg FixStack[0] is + /// st(0), FP reg FixStack[1] is st(1) etc. + void shuffleStackTop(const unsigned char *FixStack, unsigned FixCount, + MachineBasicBlock::iterator I); + bool processBasicBlock(MachineFunction &MF, MachineBasicBlock &MBB); void handleZeroArgFP(MachineBasicBlock::iterator &I); @@ -164,6 +249,8 @@ namespace { void handleCompareFP(MachineBasicBlock::iterator &I); void handleCondMovFP(MachineBasicBlock::iterator &I); void handleSpecialFP(MachineBasicBlock::iterator &I); + + bool translateCopy(MachineInstr*); }; char FPS::ID = 0; } @@ -179,7 +266,6 @@ static unsigned getFPReg(const MachineOperand &MO) { return Reg - X86::FP0; } - /// runOnMachineFunction - Loop over all of the basic blocks, transforming FP /// register references into FP stack references. /// @@ -199,6 +285,10 @@ bool FPS::runOnMachineFunction(MachineFunction &MF) { if (!FPIsUsed) return false; TII = MF.getTarget().getInstrInfo(); + + // Prepare cross-MBB liveness. + bundleCFG(MF); + StackTop = 0; // Process the function in depth first order so that we process at least one @@ -213,16 +303,111 @@ bool FPS::runOnMachineFunction(MachineFunction &MF) { Changed |= processBasicBlock(MF, **I); // Process any unreachable blocks in arbitrary order now. - if (MF.size() == Processed.size()) - return Changed; + if (MF.size() != Processed.size()) + for (MachineFunction::iterator BB = MF.begin(), E = MF.end(); BB != E; ++BB) + if (Processed.insert(BB)) + Changed |= processBasicBlock(MF, *BB); + + BlockBundle.clear(); + LiveBundles.clear(); - for (MachineFunction::iterator BB = MF.begin(), E = MF.end(); BB != E; ++BB) - if (Processed.insert(BB)) - Changed |= processBasicBlock(MF, *BB); - return Changed; } +/// bundleCFG - Scan all the basic blocks to determine consistent live-in and +/// live-out sets for the FP registers. Consistent means that the set of +/// registers live-out from a block is identical to the live-in set of all +/// successors. This is not enforced by the normal live-in lists since +/// registers may be implicitly defined, or not used by all successors. +void FPS::bundleCFG(MachineFunction &MF) { + assert(LiveBundles.empty() && "Stale data in LiveBundles"); + assert(BlockBundle.empty() && "Stale data in BlockBundle"); + SmallPtrSet PropDown, PropUp; + + // LiveBundle[0] is the empty live-in set. + LiveBundles.resize(1); + + // First gather the actual live-in masks for all MBBs. + for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) { + MachineBasicBlock *MBB = I; + const unsigned Mask = calcLiveInMask(MBB); + if (!Mask) + continue; + // Ingoing bundle index. + unsigned &Idx = BlockBundle[MBB].first; + // Already assigned an ingoing bundle? + if (Idx) + continue; + // Allocate a new LiveBundle struct for this block's live-ins. + const unsigned BundleIdx = Idx = LiveBundles.size(); + DEBUG(dbgs() << "Creating LB#" << BundleIdx << ": in:BB#" + << MBB->getNumber()); + LiveBundles.push_back(Mask); + LiveBundle &Bundle = LiveBundles.back(); + + // Make sure all predecessors have the same live-out set. + PropUp.insert(MBB); + + // Keep pushing liveness up and down the CFG until convergence. + // Only critical edges cause iteration here, but when they do, multiple + // blocks can be assigned to the same LiveBundle index. + do { + // Assign BundleIdx as liveout from predecessors in PropUp. + for (SmallPtrSet::iterator I = PropUp.begin(), + E = PropUp.end(); I != E; ++I) { + MachineBasicBlock *MBB = *I; + for (MachineBasicBlock::const_pred_iterator LinkI = MBB->pred_begin(), + LinkE = MBB->pred_end(); LinkI != LinkE; ++LinkI) { + MachineBasicBlock *PredMBB = *LinkI; + // PredMBB's liveout bundle should be set to LIIdx. + unsigned &Idx = BlockBundle[PredMBB].second; + if (Idx) { + assert(Idx == BundleIdx && "Inconsistent CFG"); + continue; + } + Idx = BundleIdx; + DEBUG(dbgs() << " out:BB#" << PredMBB->getNumber()); + // Propagate to siblings. + if (PredMBB->succ_size() > 1) + PropDown.insert(PredMBB); + } + } + PropUp.clear(); + + // Assign BundleIdx as livein to successors in PropDown. + for (SmallPtrSet::iterator I = PropDown.begin(), + E = PropDown.end(); I != E; ++I) { + MachineBasicBlock *MBB = *I; + for (MachineBasicBlock::const_succ_iterator LinkI = MBB->succ_begin(), + LinkE = MBB->succ_end(); LinkI != LinkE; ++LinkI) { + MachineBasicBlock *SuccMBB = *LinkI; + // LinkMBB's livein bundle should be set to BundleIdx. + unsigned &Idx = BlockBundle[SuccMBB].first; + if (Idx) { + assert(Idx == BundleIdx && "Inconsistent CFG"); + continue; + } + Idx = BundleIdx; + DEBUG(dbgs() << " in:BB#" << SuccMBB->getNumber()); + // Propagate to siblings. + if (SuccMBB->pred_size() > 1) + PropUp.insert(SuccMBB); + // Also accumulate the bundle liveness mask from the liveins here. + Bundle.Mask |= calcLiveInMask(SuccMBB); + } + } + PropDown.clear(); + } while (!PropUp.empty()); + DEBUG({ + dbgs() << " live:"; + for (unsigned i = 0; i < 8; ++i) + if (Bundle.Mask & (1<getDesc().TSFlags; - + unsigned FPInstClass = Flags & X86II::FPTypeMask; if (MI->isInlineAsm()) FPInstClass = X86II::SpecialFP; - + + if (MI->isCopy() && translateCopy(MI)) + FPInstClass = X86II::SpecialFP; + if (FPInstClass == X86II::NotFP) continue; // Efficiently ignore non-fp insts! @@ -297,10 +487,82 @@ bool FPS::processBasicBlock(MachineFunction &MF, MachineBasicBlock &BB) { Changed = true; } - assert(isStackEmpty() && "Stack not empty at end of basic block?"); + finishBlockStack(); + return Changed; } +/// setupBlockStack - Use the BlockBundle map to set up our model of the stack +/// to match predecessors' live out stack. +void FPS::setupBlockStack() { + DEBUG(dbgs() << "\nSetting up live-ins for BB#" << MBB->getNumber() + << " derived from " << MBB->getName() << ".\n"); + StackTop = 0; + const LiveBundle &Bundle = LiveBundles[BlockBundle.lookup(MBB).first]; + + if (!Bundle.Mask) { + DEBUG(dbgs() << "Block has no FP live-ins.\n"); + return; + } + + // Depth-first iteration should ensure that we always have an assigned stack. + assert(Bundle.isFixed() && "Reached block before any predecessors"); + + // Push the fixed live-in registers. + for (unsigned i = Bundle.FixCount; i > 0; --i) { + MBB->addLiveIn(X86::ST0+i-1); + DEBUG(dbgs() << "Live-in st(" << (i-1) << "): %FP" + << unsigned(Bundle.FixStack[i-1]) << '\n'); + pushReg(Bundle.FixStack[i-1]); + } + + // Kill off unwanted live-ins. This can happen with a critical edge. + // FIXME: We could keep these live registers around as zombies. They may need + // to be revived at the end of a short block. It might save a few instrs. + adjustLiveRegs(calcLiveInMask(MBB), MBB->begin()); + DEBUG(MBB->dump()); +} + +/// finishBlockStack - Revive live-outs that are implicitly defined out of +/// MBB. Shuffle live registers to match the expected fixed stack of any +/// predecessors, and ensure that all predecessors are expecting the same +/// stack. +void FPS::finishBlockStack() { + // The RET handling below takes care of return blocks for us. + if (MBB->succ_empty()) + return; + + DEBUG(dbgs() << "Setting up live-outs for BB#" << MBB->getNumber() + << " derived from " << MBB->getName() << ".\n"); + + unsigned BundleIdx = BlockBundle.lookup(MBB).second; + LiveBundle &Bundle = LiveBundles[BundleIdx]; + + // We may need to kill and define some registers to match successors. + // FIXME: This can probably be combined with the shuffle below. + MachineBasicBlock::iterator Term = MBB->getFirstTerminator(); + adjustLiveRegs(Bundle.Mask, Term); + + if (!Bundle.Mask) { + DEBUG(dbgs() << "No live-outs.\n"); + return; + } + + // Has the stack order been fixed yet? + DEBUG(dbgs() << "LB#" << BundleIdx << ": "); + if (Bundle.isFixed()) { + DEBUG(dbgs() << "Shuffling stack to match.\n"); + shuffleStackTop(Bundle.FixStack, Bundle.FixCount, Term); + } else { + // Not fixed yet, we get to choose. + DEBUG(dbgs() << "Fixing stack order now.\n"); + Bundle.FixCount = StackTop; + for (unsigned i = 0; i < StackTop; ++i) + Bundle.FixStack[i] = getStackEntry(i); + } +} + + //===----------------------------------------------------------------------===// // Efficient Lookup Table Support //===----------------------------------------------------------------------===// @@ -313,7 +575,8 @@ namespace { friend bool operator<(const TableEntry &TE, unsigned V) { return TE.from < V; } - friend bool operator<(unsigned V, const TableEntry &TE) { + friend bool LLVM_ATTRIBUTE_USED operator<(unsigned V, + const TableEntry &TE) { return V < TE.from; } }; @@ -565,7 +828,8 @@ void FPS::popStackAfter(MachineBasicBlock::iterator &I) { MachineInstr* MI = I; DebugLoc dl = MI->getDebugLoc(); ASSERT_SORTED(PopTable); - assert(StackTop > 0 && "Cannot pop empty stack!"); + if (StackTop == 0) + report_fatal_error("Cannot pop empty stack!"); RegMap[Stack[--StackTop]] = ~0; // Update state // Check to see if there is a popping version of this instruction... @@ -592,6 +856,13 @@ void FPS::freeStackSlotAfter(MachineBasicBlock::iterator &I, unsigned FPRegNo) { // Otherwise, store the top of stack into the dead slot, killing the operand // without having to add in an explicit xchg then pop. // + I = freeStackSlotBefore(++I, FPRegNo); +} + +/// freeStackSlotBefore - Free the specified register without trying any +/// folding. +MachineBasicBlock::iterator +FPS::freeStackSlotBefore(MachineBasicBlock::iterator I, unsigned FPRegNo) { unsigned STReg = getSTReg(FPRegNo); unsigned OldSlot = getSlot(FPRegNo); unsigned TopReg = Stack[StackTop-1]; @@ -599,9 +870,90 @@ void FPS::freeStackSlotAfter(MachineBasicBlock::iterator &I, unsigned FPRegNo) { RegMap[TopReg] = OldSlot; RegMap[FPRegNo] = ~0; Stack[--StackTop] = ~0; - MachineInstr *MI = I; - DebugLoc dl = MI->getDebugLoc(); - I = BuildMI(*MBB, ++I, dl, TII->get(X86::ST_FPrr)).addReg(STReg); + return BuildMI(*MBB, I, DebugLoc(), TII->get(X86::ST_FPrr)).addReg(STReg); +} + +/// adjustLiveRegs - Kill and revive registers such that exactly the FP +/// registers with a bit in Mask are live. +void FPS::adjustLiveRegs(unsigned Mask, MachineBasicBlock::iterator I) { + unsigned Defs = Mask; + unsigned Kills = 0; + for (unsigned i = 0; i < StackTop; ++i) { + unsigned RegNo = Stack[i]; + if (!(Defs & (1 << RegNo))) + // This register is live, but we don't want it. + Kills |= (1 << RegNo); + else + // We don't need to imp-def this live register. + Defs &= ~(1 << RegNo); + } + assert((Kills & Defs) == 0 && "Register needs killing and def'ing?"); + + // Produce implicit-defs for free by using killed registers. + while (Kills && Defs) { + unsigned KReg = CountTrailingZeros_32(Kills); + unsigned DReg = CountTrailingZeros_32(Defs); + DEBUG(dbgs() << "Renaming %FP" << KReg << " as imp %FP" << DReg << "\n"); + std::swap(Stack[getSlot(KReg)], Stack[getSlot(DReg)]); + std::swap(RegMap[KReg], RegMap[DReg]); + Kills &= ~(1 << KReg); + Defs &= ~(1 << DReg); + } + + // Kill registers by popping. + if (Kills && I != MBB->begin()) { + MachineBasicBlock::iterator I2 = llvm::prior(I); + for (;;) { + unsigned KReg = getStackEntry(0); + if (!(Kills & (1 << KReg))) + break; + DEBUG(dbgs() << "Popping %FP" << KReg << "\n"); + popStackAfter(I2); + Kills &= ~(1 << KReg); + } + } + + // Manually kill the rest. + while (Kills) { + unsigned KReg = CountTrailingZeros_32(Kills); + DEBUG(dbgs() << "Killing %FP" << KReg << "\n"); + freeStackSlotBefore(I, KReg); + Kills &= ~(1 << KReg); + } + + // Load zeros for all the imp-defs. + while(Defs) { + unsigned DReg = CountTrailingZeros_32(Defs); + DEBUG(dbgs() << "Defining %FP" << DReg << " as 0\n"); + BuildMI(*MBB, I, DebugLoc(), TII->get(X86::LD_F0)); + pushReg(DReg); + Defs &= ~(1 << DReg); + } + + // Now we should have the correct registers live. + DEBUG(dumpStack()); + assert(StackTop == CountPopulation_32(Mask) && "Live count mismatch"); +} + +/// shuffleStackTop - emit fxch instructions before I to shuffle the top +/// FixCount entries into the order given by FixStack. +/// FIXME: Is there a better algorithm than insertion sort? +void FPS::shuffleStackTop(const unsigned char *FixStack, + unsigned FixCount, + MachineBasicBlock::iterator I) { + // Move items into place, starting from the desired stack bottom. + while (FixCount--) { + // Old register at position FixCount. + unsigned OldReg = getStackEntry(FixCount); + // Desired register at position FixCount. + unsigned Reg = FixStack[FixCount]; + if (Reg == OldReg) + continue; + // (Reg st0) (OldReg st0) = (Reg OldReg st0) + moveToTop(Reg, I); + moveToTop(OldReg, I); + } + DEBUG(dumpStack()); } @@ -628,7 +980,7 @@ void FPS::handleZeroArgFP(MachineBasicBlock::iterator &I) { void FPS::handleOneArgFP(MachineBasicBlock::iterator &I) { MachineInstr *MI = I; unsigned NumOps = MI->getDesc().getNumOperands(); - assert((NumOps == X86AddrNumOperands + 1 || NumOps == 1) && + assert((NumOps == X86::AddrNumOperands + 1 || NumOps == 1) && "Can only handle fst* & ftst instructions!"); // Is this the last use of the source register? @@ -655,7 +1007,7 @@ void FPS::handleOneArgFP(MachineBasicBlock::iterator &I) { MI->getOpcode() == X86::ISTT_Fp32m80 || MI->getOpcode() == X86::ISTT_Fp64m80 || MI->getOpcode() == X86::ST_FpP80m)) { - duplicateToTop(Reg, 7 /*temp register*/, I); + duplicateToTop(Reg, getScratchReg(), I); } else { moveToTop(Reg, I); // Move to the top of the stack... } @@ -669,7 +1021,8 @@ void FPS::handleOneArgFP(MachineBasicBlock::iterator &I) { MI->getOpcode() == X86::ISTT_FP32m || MI->getOpcode() == X86::ISTT_FP64m || MI->getOpcode() == X86::ST_FP80m) { - assert(StackTop > 0 && "Stack empty??"); + if (StackTop == 0) + report_fatal_error("Stack empty??"); --StackTop; } else if (KillsSrc) { // Last use of operand? popStackAfter(I); @@ -700,7 +1053,8 @@ void FPS::handleOneArgFPRW(MachineBasicBlock::iterator &I) { // If this is the last use of the source register, just make sure it's on // the top of the stack. moveToTop(Reg, I); - assert(StackTop > 0 && "Stack cannot be empty!"); + if (StackTop == 0) + report_fatal_error("Stack cannot be empty!"); --StackTop; pushReg(getFPReg(MI->getOperand(0))); } else { @@ -953,7 +1307,6 @@ void FPS::handleCondMovFP(MachineBasicBlock::iterator &I) { /// void FPS::handleSpecialFP(MachineBasicBlock::iterator &I) { MachineInstr *MI = I; - DebugLoc dl = MI->getDebugLoc(); switch (MI->getOpcode()) { default: llvm_unreachable("Unknown SpecialFP instruction!"); case X86::FpGET_ST0_32:// Appears immediately after a call returning FP type! @@ -994,22 +1347,24 @@ void FPS::handleSpecialFP(MachineBasicBlock::iterator &I) { std::swap(RegMap[RegNo], RegMap[RegOnTop]); // Swap stack slot contents. - assert(RegMap[RegOnTop] < StackTop); + if (RegMap[RegOnTop] >= StackTop) + report_fatal_error("Access past stack top!"); std::swap(Stack[RegMap[RegOnTop]], Stack[StackTop-1]); break; } case X86::FpSET_ST0_32: case X86::FpSET_ST0_64: case X86::FpSET_ST0_80: { + // FpSET_ST0_80 is generated by copyRegToReg for setting up inline asm + // arguments that use an st constraint. We expect a sequence of + // instructions: Fp_SET_ST0 Fp_SET_ST1? INLINEASM unsigned Op0 = getFPReg(MI->getOperand(0)); - // FpSET_ST0_80 is generated by copyRegToReg for both function return - // and inline assembly with the "st" constrain. In the latter case, - // it is possible for ST(0) to be alive after this instruction. if (!MI->killsRegister(X86::FP0 + Op0)) { - // Duplicate Op0 - duplicateToTop(0, 7 /*temp register*/, I); + // Duplicate Op0 into a temporary on the stack top. + duplicateToTop(Op0, getScratchReg(), I); } else { + // Op0 is killed, so just swap it into position. moveToTop(Op0, I); } --StackTop; // "Forget" we have something on the top of stack! @@ -1017,17 +1372,28 @@ void FPS::handleSpecialFP(MachineBasicBlock::iterator &I) { } case X86::FpSET_ST1_32: case X86::FpSET_ST1_64: - case X86::FpSET_ST1_80: - // StackTop can be 1 if a FpSET_ST0_* was before this. Exchange them. - if (StackTop == 1) { - BuildMI(*MBB, I, dl, TII->get(X86::XCH_F)).addReg(X86::ST1); - NumFXCH++; - StackTop = 0; - break; + case X86::FpSET_ST1_80: { + // Set up st(1) for inline asm. We are assuming that st(0) has already been + // set up by FpSET_ST0, and our StackTop is off by one because of it. + unsigned Op0 = getFPReg(MI->getOperand(0)); + // Restore the actual StackTop from before Fp_SET_ST0. + // Note we can't handle Fp_SET_ST1 without a preceeding Fp_SET_ST0, and we + // are not enforcing the constraint. + ++StackTop; + unsigned RegOnTop = getStackEntry(0); // This reg must remain in st(0). + if (!MI->killsRegister(X86::FP0 + Op0)) { + duplicateToTop(Op0, getScratchReg(), I); + moveToTop(RegOnTop, I); + } else if (getSTReg(Op0) != X86::ST1) { + // We have the wrong value at st(1). Shuffle! Untested! + moveToTop(getStackEntry(1), I); + moveToTop(Op0, I); + moveToTop(RegOnTop, I); } - assert(StackTop == 2 && "Stack should have two element on it to return!"); - --StackTop; // "Forget" we have something on the top of stack! + assert(StackTop >= 2 && "Too few live registers"); + StackTop -= 2; // "Forget" both st(0) and st(1). break; + } case X86::MOV_Fp3232: case X86::MOV_Fp3264: case X86::MOV_Fp6432: @@ -1041,32 +1407,6 @@ void FPS::handleSpecialFP(MachineBasicBlock::iterator &I) { unsigned SrcReg = getFPReg(MO1); const MachineOperand &MO0 = MI->getOperand(0); - // These can be created due to inline asm. Two address pass can introduce - // copies from RFP registers to virtual registers. - if (MO0.getReg() == X86::ST0 && SrcReg == 0) { - assert(MO1.isKill()); - // Treat %ST0 = MOV_Fp8080 %FP0 - // like FpSET_ST0_80 %FP0, %ST0 - assert((StackTop == 1 || StackTop == 2) - && "Stack should have one or two element on it to return!"); - --StackTop; // "Forget" we have something on the top of stack! - break; - } else if (MO0.getReg() == X86::ST1 && SrcReg == 1) { - assert(MO1.isKill()); - // Treat %ST1 = MOV_Fp8080 %FP1 - // like FpSET_ST1_80 %FP0, %ST1 - // StackTop can be 1 if a FpSET_ST0_* was before this. Exchange them. - if (StackTop == 1) { - BuildMI(*MBB, I, dl, TII->get(X86::XCH_F)).addReg(X86::ST1); - NumFXCH++; - StackTop = 0; - break; - } - assert(StackTop == 2 && "Stack should have two element on it to return!"); - --StackTop; // "Forget" we have something on the top of stack! - break; - } - unsigned DestReg = getFPReg(MO0); if (MI->killsRegister(X86::FP0+SrcReg)) { // If the input operand is killed, we can just change the owner of the @@ -1126,11 +1466,11 @@ void FPS::handleSpecialFP(MachineBasicBlock::iterator &I) { case X86::RETI: // If RET has an FP register use operand, pass the first one in ST(0) and // the second one in ST(1). - if (isStackEmpty()) return; // Quick check to see if any are possible. - + // Find the register operands. unsigned FirstFPRegOp = ~0U, SecondFPRegOp = ~0U; - + unsigned LiveMask = 0; + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { MachineOperand &Op = MI->getOperand(i); if (!Op.isReg() || Op.getReg() < X86::FP0 || Op.getReg() > X86::FP6) @@ -1149,12 +1489,18 @@ void FPS::handleSpecialFP(MachineBasicBlock::iterator &I) { assert(SecondFPRegOp == ~0U && "More than two fp operands!"); SecondFPRegOp = getFPReg(Op); } + LiveMask |= (1 << getFPReg(Op)); // Remove the operand so that later passes don't see it. MI->RemoveOperand(i); --i, --e; } - + + // We may have been carrying spurious live-ins, so make sure only the returned + // registers are left live. + adjustLiveRegs(LiveMask, MI); + if (!LiveMask) return; // Quick check to see if any are possible. + // There are only four possibilities here: // 1) we are returning a single FP value. In this case, it has to be in // ST(0) already, so just declare success by removing the value from the @@ -1180,7 +1526,7 @@ void FPS::handleSpecialFP(MachineBasicBlock::iterator &I) { // Duplicate the TOS so that we return it twice. Just pick some other FPx // register to hold it. - unsigned NewReg = (FirstFPRegOp+1)%7; + unsigned NewReg = getScratchReg(); duplicateToTop(FirstFPRegOp, NewReg, MI); FirstFPRegOp = NewReg; } @@ -1204,5 +1550,42 @@ void FPS::handleSpecialFP(MachineBasicBlock::iterator &I) { } I = MBB->erase(I); // Remove the pseudo instruction - --I; + + // We want to leave I pointing to the previous instruction, but what if we + // just erased the first instruction? + if (I == MBB->begin()) { + DEBUG(dbgs() << "Inserting dummy KILL\n"); + I = BuildMI(*MBB, I, DebugLoc(), TII->get(TargetOpcode::KILL)); + } else + --I; +} + +// Translate a COPY instruction to a pseudo-op that handleSpecialFP understands. +bool FPS::translateCopy(MachineInstr *MI) { + unsigned DstReg = MI->getOperand(0).getReg(); + unsigned SrcReg = MI->getOperand(1).getReg(); + + if (DstReg == X86::ST0) { + MI->setDesc(TII->get(X86::FpSET_ST0_80)); + MI->RemoveOperand(0); + return true; + } + if (DstReg == X86::ST1) { + MI->setDesc(TII->get(X86::FpSET_ST1_80)); + MI->RemoveOperand(0); + return true; + } + if (SrcReg == X86::ST0) { + MI->setDesc(TII->get(X86::FpGET_ST0_80)); + return true; + } + if (SrcReg == X86::ST1) { + MI->setDesc(TII->get(X86::FpGET_ST1_80)); + return true; + } + if (X86::RFP80RegClass.contains(DstReg, SrcReg)) { + MI->setDesc(TII->get(X86::MOV_Fp8080)); + return true; + } + return false; }