X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTarget%2FX86%2FX86FloatingPoint.cpp;h=3b0bd03095a9f467995440b0c48268ba8207f379;hb=cd52a7a381a73c53ec4ef517ad87f19808cb1a28;hp=627510d87d379615cfff99b5fa0428227c86a465;hpb=e098e7a96d869367f95df0dbcafa3ededce765b6;p=oota-llvm.git diff --git a/lib/Target/X86/X86FloatingPoint.cpp b/lib/Target/X86/X86FloatingPoint.cpp index 627510d87d3..3b0bd03095a 100644 --- a/lib/Target/X86/X86FloatingPoint.cpp +++ b/lib/Target/X86/X86FloatingPoint.cpp @@ -23,45 +23,60 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "x86-codegen" #include "X86.h" #include "X86InstrInfo.h" #include "llvm/ADT/DepthFirstIterator.h" -#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" -#include "llvm/ADT/STLExtras.h" +#include "llvm/CodeGen/EdgeBundles.h" +#include "llvm/CodeGen/LivePhysRegs.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineInstrBuilder.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/Passes.h" +#include "llvm/IR/InlineAsm.h" #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetSubtargetInfo.h" #include +#include using namespace llvm; +#define DEBUG_TYPE "x86-codegen" + STATISTIC(NumFXCH, "Number of fxch instructions inserted"); STATISTIC(NumFP , "Number of floating point instructions"); namespace { + const unsigned ScratchFPReg = 7; + struct FPS : public MachineFunctionPass { static char ID; - FPS() : MachineFunctionPass(&ID) {} + FPS() : MachineFunctionPass(ID) { + initializeEdgeBundlesPass(*PassRegistry::getPassRegistry()); + // 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 { + void getAnalysisUsage(AnalysisUsage &AU) const override { AU.setPreservesCFG(); + AU.addRequired(); AU.addPreservedID(MachineLoopInfoID); AU.addPreservedID(MachineDominatorsID); MachineFunctionPass::getAnalysisUsage(AU); } - virtual bool runOnMachineFunction(MachineFunction &MF); + bool runOnMachineFunction(MachineFunction &MF) override; - virtual const char *getPassName() const { return "X86 FP Stackifier"; } + const char *getPassName() const override { return "X86 FP Stackifier"; } private: const TargetInstrInfo *TII; // Machine instruction info. @@ -89,7 +104,7 @@ namespace { // FixStack[i] == getStackEntry(i) for all i < FixCount. unsigned char FixStack[8]; - LiveBundle(unsigned m = 0) : Mask(m), FixCount(0) {} + LiveBundle() : Mask(0), FixCount(0) {} // Have the live registers been assigned a stack order yet? bool isFixed() const { return !Mask || FixCount; } @@ -99,19 +114,18 @@ namespace { // 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; + // The edge bundle analysis provides indices into the LiveBundles vector. + EdgeBundles *Bundles; // Return a bitmask of FP registers in block's live-in list. - unsigned calcLiveInMask(MachineBasicBlock *MBB) { + static 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; + unsigned Reg = *I; + if (Reg < X86::FP0 || Reg > X86::FP6) + continue; + Mask |= 1 << (Reg - X86::FP0); } return Mask; } @@ -120,67 +134,71 @@ namespace { void bundleCFG(MachineFunction &MF); MachineBasicBlock *MBB; // Current basic block + + // The hardware keeps track of how many FP registers are live, so we have + // to model that exactly. Usually, each live register corresponds to an + // FP register, but when dealing with calls, returns, and inline + // assembly, it is sometimes necessary to have live scratch registers. 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. + enum { + NumFPRegs = 8 // Including scratch pseudo-registers. + }; + + // For each live FP register, point to its Stack[] entry. + // The first entries correspond to FP0-FP6, the rest are scratch registers + // used when we need slightly different live registers than what the + // register allocator thinks. + unsigned RegMap[NumFPRegs]; + // 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(); +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) void dumpStack() const { dbgs() << "Stack contents:"; for (unsigned i = 0; i != StackTop; ++i) { dbgs() << " FP" << Stack[i]; assert(RegMap[Stack[i]] == i && "Stack[] doesn't match RegMap[]!"); } - dbgs() << "\n"; - } - - /// isStackEmpty - Return true if the FP stack is empty. - bool isStackEmpty() const { - return StackTop == 0; } +#endif - // 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!"); + assert(RegNo < NumFPRegs && "Regno out of range!"); return RegMap[RegNo]; } - // isLive - Is RegNo currently live in the stack? + /// 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). + /// 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; + return StackTop - 1 - getSlot(RegNo) + X86::ST0; } // 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!"); + assert(Reg < NumFPRegs && "Register number out of range!"); + if (StackTop >= 8) + report_fatal_error("Stack overflow!"); Stack[StackTop] = Reg; RegMap[Reg] = StackTop++; } @@ -197,7 +215,8 @@ 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. @@ -213,32 +232,33 @@ namespace { 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. + /// 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. + /// 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. + /// Shuffle the top FixCount stack entries such 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 handleCall(MachineBasicBlock::iterator &I); void handleZeroArgFP(MachineBasicBlock::iterator &I); void handleOneArgFP(MachineBasicBlock::iterator &I); void handleOneArgFPRW(MachineBasicBlock::iterator &I); @@ -247,7 +267,16 @@ namespace { void handleCondMovFP(MachineBasicBlock::iterator &I); void handleSpecialFP(MachineBasicBlock::iterator &I); - bool translateCopy(MachineInstr*); + // Check if a COPY instruction is using FP registers. + static bool isFPCopy(MachineInstr *MI) { + unsigned DstReg = MI->getOperand(0).getReg(); + unsigned SrcReg = MI->getOperand(1).getReg(); + + return X86::RFP80RegClass.contains(DstReg) || + X86::RFP80RegClass.contains(SrcReg); + } + + void setKillFlags(MachineBasicBlock &MBB) const; }; char FPS::ID = 0; } @@ -271,7 +300,7 @@ bool FPS::runOnMachineFunction(MachineFunction &MF) { // function. If it is all integer, there is nothing for us to do! bool FPIsUsed = false; - assert(X86::FP6 == X86::FP0+6 && "Register enums aren't sorted right!"); + static_assert(X86::FP6 == X86::FP0+6, "Register enums aren't sorted right!"); for (unsigned i = 0; i <= 6; ++i) if (MF.getRegInfo().isPhysRegUsed(X86::FP0+i)) { FPIsUsed = true; @@ -281,7 +310,8 @@ bool FPS::runOnMachineFunction(MachineFunction &MF) { // Early exit. if (!FPIsUsed) return false; - TII = MF.getTarget().getInstrInfo(); + Bundles = &getAnalysis(); + TII = MF.getSubtarget().getInstrInfo(); // Prepare cross-MBB liveness. bundleCFG(MF); @@ -294,18 +324,15 @@ bool FPS::runOnMachineFunction(MachineFunction &MF) { MachineBasicBlock *Entry = MF.begin(); bool Changed = false; - for (df_ext_iterator > - I = df_ext_begin(Entry, Processed), E = df_ext_end(Entry, Processed); - I != E; ++I) - Changed |= processBasicBlock(MF, **I); + for (MachineBasicBlock *BB : depth_first_ext(Entry, Processed)) + Changed |= processBasicBlock(MF, *BB); // Process any unreachable blocks in arbitrary order now. if (MF.size() != Processed.size()) for (MachineFunction::iterator BB = MF.begin(), E = MF.end(); BB != E; ++BB) - if (Processed.insert(BB)) + if (Processed.insert(BB).second) Changed |= processBasicBlock(MF, *BB); - BlockBundle.clear(); LiveBundles.clear(); return Changed; @@ -318,90 +345,16 @@ bool FPS::runOnMachineFunction(MachineFunction &MF) { /// 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; + LiveBundles.resize(Bundles->getNumBundles()); - // LiveBundle[0] is the empty live-in set. - LiveBundles.resize(1); - - // First gather the actual live-in masks for all MBBs. + // 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<getBundle(MBB->getNumber(), false)].Mask |= Mask; } } @@ -412,6 +365,7 @@ bool FPS::processBasicBlock(MachineFunction &MF, MachineBasicBlock &BB) { bool Changed = false; MBB = &BB; + setKillFlags(BB); setupBlockStack(); for (MachineBasicBlock::iterator I = BB.begin(); I != BB.end(); ++I) { @@ -422,15 +376,22 @@ bool FPS::processBasicBlock(MachineFunction &MF, MachineBasicBlock &BB) { if (MI->isInlineAsm()) FPInstClass = X86II::SpecialFP; - if (MI->isCopy() && translateCopy(MI)) + if (MI->isCopy() && isFPCopy(MI)) + FPInstClass = X86II::SpecialFP; + + if (MI->isImplicitDef() && + X86::RFP80RegClass.contains(MI->getOperand(0).getReg())) + FPInstClass = X86II::SpecialFP; + + if (MI->isCall()) FPInstClass = X86II::SpecialFP; if (FPInstClass == X86II::NotFP) continue; // Efficiently ignore non-fp insts! - MachineInstr *PrevMI = 0; + MachineInstr *PrevMI = nullptr; if (I != BB.begin()) - PrevMI = prior(I); + PrevMI = std::prev(I); ++NumFP; // Keep track of # of pseudo instrs DEBUG(dbgs() << "\nFPInst:\t" << *MI); @@ -459,7 +420,9 @@ bool FPS::processBasicBlock(MachineFunction &MF, MachineBasicBlock &BB) { // after definition. If so, pop them. for (unsigned i = 0, e = DeadRegs.size(); i != e; ++i) { unsigned Reg = DeadRegs[i]; - if (Reg >= X86::FP0 && Reg <= X86::FP6) { + // Check if Reg is live on the stack. An inline-asm register operand that + // is in the clobber list and marked dead might not be live on the stack. + if (Reg >= X86::FP0 && Reg <= X86::FP6 && isLive(Reg-X86::FP0)) { DEBUG(dbgs() << "Register FP#" << Reg-X86::FP0 << " is dead!\n"); freeStackSlotAfter(I, Reg-X86::FP0); } @@ -473,13 +436,14 @@ bool FPS::processBasicBlock(MachineFunction &MF, MachineBasicBlock &BB) { } else { MachineBasicBlock::iterator Start = I; // Rewind to first instruction newly inserted. - while (Start != BB.begin() && prior(Start) != PrevI) --Start; + while (Start != BB.begin() && std::prev(Start) != PrevI) --Start; dbgs() << "Inserted instructions:\n\t"; - Start->print(dbgs(), &MF.getTarget()); - while (++Start != llvm::next(I)) {} + Start->print(dbgs()); + while (++Start != std::next(I)) {} } dumpStack(); ); + (void)PrevMI; Changed = true; } @@ -489,13 +453,15 @@ bool FPS::processBasicBlock(MachineFunction &MF, MachineBasicBlock &BB) { return Changed; } -/// setupBlockStack - Use the BlockBundle map to set up our model of the stack +/// setupBlockStack - Use the live bundles 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]; + // Get the live-in bundle for MBB. + const LiveBundle &Bundle = + LiveBundles[Bundles->getBundle(MBB->getNumber(), false)]; if (!Bundle.Mask) { DEBUG(dbgs() << "Block has no FP live-ins.\n"); @@ -532,7 +498,8 @@ void FPS::finishBlockStack() { DEBUG(dbgs() << "Setting up live-outs for BB#" << MBB->getNumber() << " derived from " << MBB->getName() << ".\n"); - unsigned BundleIdx = BlockBundle.lookup(MBB).second; + // Get MBB's live-out bundle. + unsigned BundleIdx = Bundles->getBundle(MBB->getNumber(), true); LiveBundle &Bundle = LiveBundles[BundleIdx]; // We may need to kill and define some registers to match successors. @@ -566,13 +533,14 @@ void FPS::finishBlockStack() { namespace { struct TableEntry { - unsigned from; - unsigned to; + uint16_t from; + uint16_t to; bool operator<(const TableEntry &TE) const { return from < TE.from; } friend bool operator<(const TableEntry &TE, unsigned V) { return TE.from < V; } - friend bool operator<(unsigned V, const TableEntry &TE) { + friend bool LLVM_ATTRIBUTE_UNUSED operator<(unsigned V, + const TableEntry &TE) { return V < TE.from; } }; @@ -824,7 +792,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... @@ -865,7 +834,9 @@ FPS::freeStackSlotBefore(MachineBasicBlock::iterator I, unsigned FPRegNo) { RegMap[TopReg] = OldSlot; RegMap[FPRegNo] = ~0; Stack[--StackTop] = ~0; - return BuildMI(*MBB, I, DebugLoc(), TII->get(X86::ST_FPrr)).addReg(STReg); + return BuildMI(*MBB, I, DebugLoc(), TII->get(X86::ST_FPrr)) + .addReg(STReg) + .getInstr(); } /// adjustLiveRegs - Kill and revive registers such that exactly the FP @@ -886,8 +857,8 @@ void FPS::adjustLiveRegs(unsigned Mask, MachineBasicBlock::iterator I) { // Produce implicit-defs for free by using killed registers. while (Kills && Defs) { - unsigned KReg = CountTrailingZeros_32(Kills); - unsigned DReg = CountTrailingZeros_32(Defs); + unsigned KReg = countTrailingZeros(Kills); + unsigned DReg = countTrailingZeros(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]); @@ -897,8 +868,8 @@ void FPS::adjustLiveRegs(unsigned Mask, MachineBasicBlock::iterator I) { // Kill registers by popping. if (Kills && I != MBB->begin()) { - MachineBasicBlock::iterator I2 = llvm::prior(I); - for (;;) { + MachineBasicBlock::iterator I2 = std::prev(I); + while (StackTop) { unsigned KReg = getStackEntry(0); if (!(Kills & (1 << KReg))) break; @@ -910,7 +881,7 @@ void FPS::adjustLiveRegs(unsigned Mask, MachineBasicBlock::iterator I) { // Manually kill the rest. while (Kills) { - unsigned KReg = CountTrailingZeros_32(Kills); + unsigned KReg = countTrailingZeros(Kills); DEBUG(dbgs() << "Killing %FP" << KReg << "\n"); freeStackSlotBefore(I, KReg); Kills &= ~(1 << KReg); @@ -918,7 +889,7 @@ void FPS::adjustLiveRegs(unsigned Mask, MachineBasicBlock::iterator I) { // Load zeros for all the imp-defs. while(Defs) { - unsigned DReg = CountTrailingZeros_32(Defs); + unsigned DReg = countTrailingZeros(Defs); DEBUG(dbgs() << "Defining %FP" << DReg << " as 0\n"); BuildMI(*MBB, I, DebugLoc(), TII->get(X86::LD_F0)); pushReg(DReg); @@ -927,7 +898,7 @@ void FPS::adjustLiveRegs(unsigned Mask, MachineBasicBlock::iterator I) { // Now we should have the correct registers live. DEBUG(dumpStack()); - assert(StackTop == CountPopulation_32(Mask) && "Live count mismatch"); + assert(StackTop == countPopulation(Mask) && "Live count mismatch"); } /// shuffleStackTop - emit fxch instructions before I to shuffle the top @@ -946,7 +917,8 @@ void FPS::shuffleStackTop(const unsigned char *FixStack, continue; // (Reg st0) (OldReg st0) = (Reg OldReg st0) moveToTop(Reg, I); - moveToTop(OldReg, I); + if (FixCount > 0) + moveToTop(OldReg, I); } DEBUG(dumpStack()); } @@ -956,6 +928,31 @@ void FPS::shuffleStackTop(const unsigned char *FixStack, // Instruction transformation implementation //===----------------------------------------------------------------------===// +void FPS::handleCall(MachineBasicBlock::iterator &I) { + unsigned STReturns = 0; + + for (const auto &MO : I->operands()) { + if (!MO.isReg()) + continue; + + unsigned R = MO.getReg() - X86::FP0; + + if (R < 8) { + assert(MO.isDef() && MO.isImplicit()); + STReturns |= 1 << R; + } + } + + unsigned N = countTrailingOnes(STReturns); + + // FP registers used for function return must be consecutive starting at + // FP0. + assert(STReturns == 0 || (isMask_32(STReturns) && N <= 2)); + + for (unsigned I = 0; I < N; ++I) + pushReg(N - I - 1); +} + /// handleZeroArgFP - ST(0) = fld0 ST(0) = flds /// void FPS::handleZeroArgFP(MachineBasicBlock::iterator &I) { @@ -965,7 +962,7 @@ void FPS::handleZeroArgFP(MachineBasicBlock::iterator &I) { // Change from the pseudo instruction to the concrete instruction. MI->RemoveOperand(0); // Remove the explicit ST(0) operand MI->setDesc(TII->get(getConcreteOpcode(MI->getOpcode()))); - + // Result gets pushed on the stack. pushReg(DestReg); } @@ -1002,11 +999,11 @@ void FPS::handleOneArgFP(MachineBasicBlock::iterator &I) { MI->getOpcode() == X86::ISTT_Fp32m80 || MI->getOpcode() == X86::ISTT_Fp64m80 || MI->getOpcode() == X86::ST_FpP80m)) { - duplicateToTop(Reg, getScratchReg(), I); + duplicateToTop(Reg, ScratchFPReg, I); } else { moveToTop(Reg, I); // Move to the top of the stack... } - + // Convert from the pseudo instruction to the concrete instruction. MI->RemoveOperand(NumOps-1); // Remove explicit ST(0) operand MI->setDesc(TII->get(getConcreteOpcode(MI->getOpcode()))); @@ -1016,7 +1013,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); @@ -1047,7 +1045,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 { @@ -1285,7 +1284,7 @@ void FPS::handleCondMovFP(MachineBasicBlock::iterator &I) { MI->RemoveOperand(1); MI->getOperand(0).setReg(getSTReg(Op1)); MI->setDesc(TII->get(getConcreteOpcode(MI->getOpcode()))); - + // If we kill the second operand, make sure to pop it from the stack. if (Op0 != Op1 && KillsOp1) { // Get this value off of the register stack. @@ -1298,146 +1297,211 @@ void FPS::handleCondMovFP(MachineBasicBlock::iterator &I) { /// floating point instructions. This is primarily intended for use by pseudo /// instructions. /// -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! - case X86::FpGET_ST0_64:// Appears immediately after a call returning FP type! - case X86::FpGET_ST0_80:// Appears immediately after a call returning FP type! - assert(StackTop == 0 && "Stack should be empty after a call!"); - pushReg(getFPReg(MI->getOperand(0))); - break; - case X86::FpGET_ST1_32:// Appears immediately after a call returning FP type! - case X86::FpGET_ST1_64:// Appears immediately after a call returning FP type! - case X86::FpGET_ST1_80:{// Appears immediately after a call returning FP type! - // FpGET_ST1 should occur right after a FpGET_ST0 for a call or inline asm. - // The pattern we expect is: - // CALL - // FP1 = FpGET_ST0 - // FP4 = FpGET_ST1 - // - // At this point, we've pushed FP1 on the top of stack, so it should be - // present if it isn't dead. If it was dead, we already emitted a pop to - // remove it from the stack and StackTop = 0. - - // Push FP4 as top of stack next. - pushReg(getFPReg(MI->getOperand(0))); +void FPS::handleSpecialFP(MachineBasicBlock::iterator &Inst) { + MachineInstr *MI = Inst; - // If StackTop was 0 before we pushed our operand, then ST(0) must have been - // dead. In this case, the ST(1) value is the only thing that is live, so - // it should be on the TOS (after the pop that was emitted) and is. Just - // continue in this case. - if (StackTop == 1) - break; - - // Because pushReg just pushed ST(1) as TOS, we now have to swap the two top - // elements so that our accounting is correct. - unsigned RegOnTop = getStackEntry(0); - unsigned RegNo = getStackEntry(1); - - // Swap the slots the regs are in. - std::swap(RegMap[RegNo], RegMap[RegOnTop]); - - // Swap stack slot contents. - assert(RegMap[RegOnTop] < StackTop); - 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)); - - if (!MI->killsRegister(X86::FP0 + Op0)) { - // 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! - break; - } - case X86::FpSET_ST1_32: - case X86::FpSET_ST1_64: - 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 && "Too few live registers"); - StackTop -= 2; // "Forget" both st(0) and st(1). - break; + if (MI->isCall()) { + handleCall(Inst); + return; } - case X86::MOV_Fp3232: - case X86::MOV_Fp3264: - case X86::MOV_Fp6432: - case X86::MOV_Fp6464: - case X86::MOV_Fp3280: - case X86::MOV_Fp6480: - case X86::MOV_Fp8032: - case X86::MOV_Fp8064: - case X86::MOV_Fp8080: { - const MachineOperand &MO1 = MI->getOperand(1); - unsigned SrcReg = getFPReg(MO1); + switch (MI->getOpcode()) { + default: llvm_unreachable("Unknown SpecialFP instruction!"); + case TargetOpcode::COPY: { + // We handle three kinds of copies: FP <- FP, FP <- ST, and ST <- FP. + const MachineOperand &MO1 = MI->getOperand(1); const MachineOperand &MO0 = MI->getOperand(0); - unsigned DestReg = getFPReg(MO0); - if (MI->killsRegister(X86::FP0+SrcReg)) { + bool KillsSrc = MI->killsRegister(MO1.getReg()); + + // FP <- FP copy. + unsigned DstFP = getFPReg(MO0); + unsigned SrcFP = getFPReg(MO1); + assert(isLive(SrcFP) && "Cannot copy dead register"); + if (KillsSrc) { // If the input operand is killed, we can just change the owner of the // incoming stack slot into the result. - unsigned Slot = getSlot(SrcReg); - assert(Slot < 7 && DestReg < 7 && "FpMOV operands invalid!"); - Stack[Slot] = DestReg; - RegMap[DestReg] = Slot; - + unsigned Slot = getSlot(SrcFP); + Stack[Slot] = DstFP; + RegMap[DstFP] = Slot; } else { - // For FMOV we just duplicate the specified value to a new stack slot. + // For COPY we just duplicate the specified value to a new stack slot. // This could be made better, but would require substantial changes. - duplicateToTop(SrcReg, DestReg, I); - } + duplicateToTop(SrcFP, DstFP, Inst); } break; + } + + case TargetOpcode::IMPLICIT_DEF: { + // All FP registers must be explicitly defined, so load a 0 instead. + unsigned Reg = MI->getOperand(0).getReg() - X86::FP0; + DEBUG(dbgs() << "Emitting LD_F0 for implicit FP" << Reg << '\n'); + BuildMI(*MBB, Inst, MI->getDebugLoc(), TII->get(X86::LD_F0)); + pushReg(Reg); + break; + } + case TargetOpcode::INLINEASM: { // The inline asm MachineInstr currently only *uses* FP registers for the // 'f' constraint. These should be turned into the current ST(x) register - // in the machine instr. Also, any kills should be explicitly popped after - // the inline asm. - unsigned Kills = 0; + // in the machine instr. + // + // There are special rules for x87 inline assembly. The compiler must know + // exactly how many registers are popped and pushed implicitly by the asm. + // Otherwise it is not possible to restore the stack state after the inline + // asm. + // + // There are 3 kinds of input operands: + // + // 1. Popped inputs. These must appear at the stack top in ST0-STn. A + // popped input operand must be in a fixed stack slot, and it is either + // tied to an output operand, or in the clobber list. The MI has ST use + // and def operands for these inputs. + // + // 2. Fixed inputs. These inputs appear in fixed stack slots, but are + // preserved by the inline asm. The fixed stack slots must be STn-STm + // following the popped inputs. A fixed input operand cannot be tied to + // an output or appear in the clobber list. The MI has ST use operands + // and no defs for these inputs. + // + // 3. Preserved inputs. These inputs use the "f" constraint which is + // represented as an FP register. The inline asm won't change these + // stack slots. + // + // Outputs must be in ST registers, FP outputs are not allowed. Clobbered + // registers do not count as output operands. The inline asm changes the + // stack as if it popped all the popped inputs and then pushed all the + // output operands. + + // Scan the assembly for ST registers used, defined and clobbered. We can + // only tell clobbers from defs by looking at the asm descriptor. + unsigned STUses = 0, STDefs = 0, STClobbers = 0, STDeadDefs = 0; + unsigned NumOps = 0; + SmallSet FRegIdx; + unsigned RCID; + + for (unsigned i = InlineAsm::MIOp_FirstOperand, e = MI->getNumOperands(); + i != e && MI->getOperand(i).isImm(); i += 1 + NumOps) { + unsigned Flags = MI->getOperand(i).getImm(); + + NumOps = InlineAsm::getNumOperandRegisters(Flags); + if (NumOps != 1) + continue; + const MachineOperand &MO = MI->getOperand(i + 1); + if (!MO.isReg()) + continue; + unsigned STReg = MO.getReg() - X86::FP0; + if (STReg >= 8) + continue; + + // If the flag has a register class constraint, this must be an operand + // with constraint "f". Record its index and continue. + if (InlineAsm::hasRegClassConstraint(Flags, RCID)) { + FRegIdx.insert(i + 1); + continue; + } + + switch (InlineAsm::getKind(Flags)) { + case InlineAsm::Kind_RegUse: + STUses |= (1u << STReg); + break; + case InlineAsm::Kind_RegDef: + case InlineAsm::Kind_RegDefEarlyClobber: + STDefs |= (1u << STReg); + if (MO.isDead()) + STDeadDefs |= (1u << STReg); + break; + case InlineAsm::Kind_Clobber: + STClobbers |= (1u << STReg); + break; + default: + break; + } + } + + if (STUses && !isMask_32(STUses)) + MI->emitError("fixed input regs must be last on the x87 stack"); + unsigned NumSTUses = countTrailingOnes(STUses); + + // Defs must be contiguous from the stack top. ST0-STn. + if (STDefs && !isMask_32(STDefs)) { + MI->emitError("output regs must be last on the x87 stack"); + STDefs = NextPowerOf2(STDefs) - 1; + } + unsigned NumSTDefs = countTrailingOnes(STDefs); + + // So must the clobbered stack slots. ST0-STm, m >= n. + if (STClobbers && !isMask_32(STDefs | STClobbers)) + MI->emitError("clobbers must be last on the x87 stack"); + + // Popped inputs are the ones that are also clobbered or defined. + unsigned STPopped = STUses & (STDefs | STClobbers); + if (STPopped && !isMask_32(STPopped)) + MI->emitError("implicitly popped regs must be last on the x87 stack"); + unsigned NumSTPopped = countTrailingOnes(STPopped); + + DEBUG(dbgs() << "Asm uses " << NumSTUses << " fixed regs, pops " + << NumSTPopped << ", and defines " << NumSTDefs << " regs.\n"); + +#ifndef NDEBUG + // If any input operand uses constraint "f", all output register + // constraints must be early-clobber defs. + for (unsigned I = 0, E = MI->getNumOperands(); I < E; ++I) + if (FRegIdx.count(I)) { + assert((1 << getFPReg(MI->getOperand(I)) & STDefs) == 0 && + "Operands with constraint \"f\" cannot overlap with defs"); + } +#endif + + // Collect all FP registers (register operands with constraints "t", "u", + // and "f") to kill afer the instruction. + unsigned FPKills = ((1u << NumFPRegs) - 1) & ~0xff; 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) continue; - assert(Op.isUse() && "Only handle inline asm uses right now"); - unsigned FPReg = getFPReg(Op); - Op.setReg(getSTReg(FPReg)); - + // If we kill this operand, make sure to pop it from the stack after the // asm. We just remember it for now, and pop them all off at the end in // a batch. - if (Op.isKill()) - Kills |= 1U << FPReg; + if (Op.isUse() && Op.isKill()) + FPKills |= 1U << FPReg; } + // Do not include registers that are implicitly popped by defs/clobbers. + FPKills &= ~(STDefs | STClobbers); + + // Now we can rearrange the live registers to match what was requested. + unsigned char STUsesArray[8]; + + for (unsigned I = 0; I < NumSTUses; ++I) + STUsesArray[I] = I; + + shuffleStackTop(STUsesArray, NumSTUses, Inst); + DEBUG({dbgs() << "Before asm: "; dumpStack();}); + + // With the stack layout fixed, rewrite the FP registers. + 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) + continue; + + unsigned FPReg = getFPReg(Op); + + if (FRegIdx.count(i)) + // Operand with constraint "f". + Op.setReg(getSTReg(FPReg)); + else + // Operand with a single register class constraint ("t" or "u"). + Op.setReg(X86::ST0 + FPReg); + } + + // Simulate the inline asm popping its inputs and pushing its outputs. + StackTop -= NumSTPopped; + + for (unsigned i = 0; i < NumSTDefs; ++i) + pushReg(NumSTDefs - i - 1); + // If this asm kills any FP registers (is the last use of them) we must // explicitly emit pop instructions for them. Do this now after the asm has // executed so that the ST(x) numbers are not off (which would happen if we @@ -1445,18 +1509,46 @@ void FPS::handleSpecialFP(MachineBasicBlock::iterator &I) { // // Note: this might be a non-optimal pop sequence. We might be able to do // better by trying to pop in stack order or something. - MachineBasicBlock::iterator InsertPt = MI; - while (Kills) { - unsigned FPReg = CountTrailingZeros_32(Kills); - freeStackSlotAfter(InsertPt, FPReg); - Kills &= ~(1U << FPReg); + while (FPKills) { + unsigned FPReg = countTrailingZeros(FPKills); + if (isLive(FPReg)) + freeStackSlotAfter(Inst, FPReg); + FPKills &= ~(1U << FPReg); } + // Don't delete the inline asm! return; } - - case X86::RET: - case X86::RETI: + + case X86::WIN_FTOL_32: + case X86::WIN_FTOL_64: { + // Push the operand into ST0. + MachineOperand &Op = MI->getOperand(0); + assert(Op.isUse() && Op.isReg() && + Op.getReg() >= X86::FP0 && Op.getReg() <= X86::FP6); + unsigned FPReg = getFPReg(Op); + if (Op.isKill()) + moveToTop(FPReg, Inst); + else + duplicateToTop(FPReg, FPReg, Inst); + + // Emit the call. This will pop the operand. + BuildMI(*MBB, Inst, MI->getDebugLoc(), TII->get(X86::CALLpcrel32)) + .addExternalSymbol("_ftol2") + .addReg(X86::ST0, RegState::ImplicitKill) + .addReg(X86::ECX, RegState::ImplicitDefine) + .addReg(X86::EAX, RegState::Define | RegState::Implicit) + .addReg(X86::EDX, RegState::Define | RegState::Implicit) + .addReg(X86::EFLAGS, RegState::Define | RegState::Implicit); + --StackTop; + + break; + } + + case X86::RETQ: + case X86::RETL: + case X86::RETIL: + case X86::RETIQ: // If RET has an FP register use operand, pass the first one in ST(0) and // the second one in ST(1). @@ -1502,38 +1594,38 @@ void FPS::handleSpecialFP(MachineBasicBlock::iterator &I) { // Assert that the top of stack contains the right FP register. assert(StackTop == 1 && FirstFPRegOp == getStackEntry(0) && "Top of stack not the right register for RET!"); - + // Ok, everything is good, mark the value as not being on the stack // anymore so that our assertion about the stack being empty at end of // block doesn't fire. StackTop = 0; return; } - + // Otherwise, we are returning two values: // 2) If returning the same value for both, we only have one thing in the FP // stack. Consider: RET FP1, FP1 if (StackTop == 1) { assert(FirstFPRegOp == SecondFPRegOp && FirstFPRegOp == getStackEntry(0)&& "Stack misconfiguration for RET!"); - + // Duplicate the TOS so that we return it twice. Just pick some other FPx // register to hold it. - unsigned NewReg = getScratchReg(); + unsigned NewReg = ScratchFPReg; duplicateToTop(FirstFPRegOp, NewReg, MI); FirstFPRegOp = NewReg; } - + /// Okay we know we have two different FPx operands now: assert(StackTop == 2 && "Must have two values live!"); - + /// 3) If SecondFPRegOp is currently in ST(0) and FirstFPRegOp is currently /// in ST(1). In this case, emit an fxch. if (getStackEntry(0) == SecondFPRegOp) { assert(getStackEntry(1) == FirstFPRegOp && "Unknown regs live"); moveToTop(FirstFPRegOp, MI); } - + /// 4) Finally, FirstFPRegOp must be in ST(0) and SecondFPRegOp must be in /// ST(1). Just remove both from our understanding of the stack and return. assert(getStackEntry(0) == FirstFPRegOp && "Unknown regs live"); @@ -1542,43 +1634,54 @@ void FPS::handleSpecialFP(MachineBasicBlock::iterator &I) { return; } - I = MBB->erase(I); // Remove the pseudo instruction + Inst = MBB->erase(Inst); // Remove the pseudo instruction // We want to leave I pointing to the previous instruction, but what if we // just erased the first instruction? - if (I == MBB->begin()) { + if (Inst == MBB->begin()) { DEBUG(dbgs() << "Inserting dummy KILL\n"); - I = BuildMI(*MBB, I, DebugLoc(), TII->get(TargetOpcode::KILL)); + Inst = BuildMI(*MBB, Inst, DebugLoc(), TII->get(TargetOpcode::KILL)); } else - --I; + --Inst; } -// 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(); +void FPS::setKillFlags(MachineBasicBlock &MBB) const { + const TargetRegisterInfo *TRI = + MBB.getParent()->getSubtarget().getRegisterInfo(); + LivePhysRegs LPR(TRI); - 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; + LPR.addLiveOuts(&MBB); + + for (MachineBasicBlock::reverse_iterator I = MBB.rbegin(), E = MBB.rend(); + I != E; ++I) { + if (I->isDebugValue()) + continue; + + std::bitset<8> Defs; + SmallVector Uses; + MachineInstr &MI = *I; + + for (auto &MO : I->operands()) { + if (!MO.isReg()) + continue; + + unsigned Reg = MO.getReg() - X86::FP0; + + if (Reg >= 8) + continue; + + if (MO.isDef()) { + Defs.set(Reg); + if (!LPR.contains(MO.getReg())) + MO.setIsDead(); + } else + Uses.push_back(&MO); + } + + for (auto *MO : Uses) + if (Defs.test(getFPReg(*MO)) || !LPR.contains(MO->getReg())) + MO->setIsKill(); + + LPR.stepBackward(MI); } - return false; }