//===----------------------------------------------------------------------===//
//
// This file defines the pass which converts floating point instructions from
-// virtual registers into register stack instructions.
+// virtual 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).
+//
+// 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.
//
//===----------------------------------------------------------------------===//
#include "llvm/CodeGen/Passes.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
+#include "llvm/Function.h" // FIXME: remove when using MBB CFG!
+#include "llvm/Support/CFG.h" // FIXME: remove when using MBB CFG!
#include "Support/Debug.h"
+#include "Support/DepthFirstIterator.h"
#include "Support/Statistic.h"
#include <algorithm>
-#include <iostream>
-
-namespace llvm {
+#include <set>
+using namespace llvm;
namespace {
Statistic<> NumFXCH("x86-codegen", "Number of fxch instructions inserted");
return StackTop - 1 - getSlot(RegNo) + llvm::X86::ST0;
}
- // pushReg - Push the specifiex FP<n> register onto the stack
+ // pushReg - Push the specified FP<n> register onto the stack
void pushReg(unsigned Reg) {
assert(Reg < 8 && "Register number out of range!");
assert(StackTop < 8 && "Stack overflow!");
void handleZeroArgFP(MachineBasicBlock::iterator &I);
void handleOneArgFP(MachineBasicBlock::iterator &I);
+ void handleOneArgFPRW(MachineBasicBlock::iterator &I);
void handleTwoArgFP(MachineBasicBlock::iterator &I);
void handleSpecialFP(MachineBasicBlock::iterator &I);
};
}
-FunctionPass *createX86FloatingPointStackifierPass() { return new FPS(); }
+FunctionPass *llvm::createX86FloatingPointStackifierPass() { return new FPS(); }
/// runOnMachineFunction - Loop over all of the basic blocks, transforming FP
/// register references into FP stack references.
LV = &getAnalysis<LiveVariables>();
StackTop = 0;
- bool Changed = false;
+ // Figure out the mapping of MBB's to BB's.
+ //
+ // FIXME: Eventually we should be able to traverse the MBB CFG directly, and
+ // we will need to extend this when one llvm basic block can codegen to
+ // multiple MBBs.
+ //
+ // FIXME again: Just use the mapping established by LiveVariables!
+ //
+ std::map<const BasicBlock*, MachineBasicBlock *> MBBMap;
for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
- Changed |= processBasicBlock(MF, *I);
+ MBBMap[I->getBasicBlock()] = I;
+
+ // Process the function in depth first order so that we process at least one
+ // of the predecessors for every reachable block in the function.
+ std::set<const BasicBlock*> Processed;
+ const BasicBlock *Entry = MF.getFunction()->begin();
+
+ bool Changed = false;
+ for (df_ext_iterator<const BasicBlock*, std::set<const BasicBlock*> >
+ I = df_ext_begin(Entry, Processed), E = df_ext_end(Entry, Processed);
+ I != E; ++I)
+ Changed |= processBasicBlock(MF, *MBBMap[*I]);
+
+ assert(MBBMap.size() == Processed.size() &&
+ "Doesn't handle unreachable code yet!");
+
return Changed;
}
for (MachineBasicBlock::iterator I = BB.begin(); I != BB.end(); ++I) {
MachineInstr *MI = *I;
- MachineInstr *PrevMI = I == BB.begin() ? 0 : *(I-1);
unsigned Flags = TII.get(MI->getOpcode()).TSFlags;
+ if ((Flags & X86II::FPTypeMask) == X86II::NotFP)
+ continue; // Efficiently ignore non-fp insts!
- if ((Flags & X86II::FPTypeMask) == 0) continue; // Ignore non-fp insts!
+ MachineInstr *PrevMI = I == BB.begin() ? 0 : *(I-1);
++NumFP; // Keep track of # of pseudo instrs
DEBUG(std::cerr << "\nFPInst:\t";
});
switch (Flags & X86II::FPTypeMask) {
- case X86II::ZeroArgFP: handleZeroArgFP(I); break;
- case X86II::OneArgFP: handleOneArgFP(I); break;
-
- case X86II::OneArgFPRW: // ST(0) = fsqrt(ST(0))
- assert(0 && "FP instr type not handled yet!");
-
- case X86II::TwoArgFP: handleTwoArgFP(I); break;
- case X86II::SpecialFP: handleSpecialFP(I); break;
+ case X86II::ZeroArgFP: handleZeroArgFP(I); break;
+ case X86II::OneArgFP: handleOneArgFP(I); break; // fstp ST(0)
+ case X86II::OneArgFPRW: handleOneArgFPRW(I); break; // ST(0) = fsqrt(ST(0))
+ case X86II::TwoArgFP: handleTwoArgFP(I); break;
+ case X86II::SpecialFP: handleSpecialFP(I); break;
default: assert(0 && "Unknown FP Type!");
}
// Efficient Lookup Table Support
//===----------------------------------------------------------------------===//
-struct TableEntry {
- unsigned from;
- unsigned to;
- bool operator<(const TableEntry &TE) const { return from < TE.from; }
- bool operator<(unsigned V) const { return from < V; }
-};
+namespace {
+ struct TableEntry {
+ unsigned from;
+ unsigned to;
+ bool operator<(const TableEntry &TE) const { return from < TE.from; }
+ bool operator<(unsigned V) const { return from < V; }
+ };
+}
static bool TableIsSorted(const TableEntry *Table, unsigned NumEntries) {
for (unsigned i = 0; i != NumEntries-1; ++i)
//===----------------------------------------------------------------------===//
/// handleZeroArgFP - ST(0) = fld0 ST(0) = flds <mem>
-//
+///
void FPS::handleZeroArgFP(MachineBasicBlock::iterator &I) {
MachineInstr *MI = *I;
unsigned DestReg = getFPReg(MI->getOperand(0));
pushReg(DestReg);
}
-/// handleOneArgFP - fst ST(0), <mem>
-//
+/// handleOneArgFP - fst <mem>, ST(0)
+///
void FPS::handleOneArgFP(MachineBasicBlock::iterator &I) {
MachineInstr *MI = *I;
assert(MI->getNumOperands() == 5 && "Can only handle fst* instructions!");
+ // Is this the last use of the source register?
unsigned Reg = getFPReg(MI->getOperand(4));
bool KillsSrc = false;
for (LiveVariables::killed_iterator KI = LV->killed_begin(MI),
}
}
+
+/// handleOneArgFPRW - fchs - ST(0) = -ST(0)
+///
+void FPS::handleOneArgFPRW(MachineBasicBlock::iterator &I) {
+ MachineInstr *MI = *I;
+ assert(MI->getNumOperands() == 2 && "Can only handle fst* instructions!");
+
+ // Is this the last use of the source register?
+ unsigned Reg = getFPReg(MI->getOperand(1));
+ bool KillsSrc = false;
+ for (LiveVariables::killed_iterator KI = LV->killed_begin(MI),
+ E = LV->killed_end(MI); KI != E; ++KI)
+ KillsSrc |= KI->second == X86::FP0+Reg;
+
+ if (KillsSrc) {
+ // 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!");
+ --StackTop;
+ pushReg(getFPReg(MI->getOperand(0)));
+ } else {
+ // If this is not the last use of the source register, _copy_ it to the top
+ // of the stack.
+ duplicateToTop(Reg, getFPReg(MI->getOperand(0)), I);
+ }
+
+ MI->RemoveOperand(1); // Drop the source operand.
+ MI->RemoveOperand(0); // Drop the destination operand.
+}
+
+
//===----------------------------------------------------------------------===//
// Define tables of various ways to map pseudo instructions
//
}
I = MBB->erase(I)-1; // Remove the pseudo instruction
+ delete MI;
}
-
-namespace {
-
- struct FPK : public MachineFunctionPass {
- virtual const char *getPassName() const { return "X86 FP Killer"; }
- virtual bool runOnMachineFunction(MachineFunction &MF);
- virtual void getAnalysisUsage(AnalysisUsage &AU) const {
- AU.setPreservesAll();
- AU.addRequired<LiveVariables>();
- AU.addRequiredID(PHIEliminationID);
- MachineFunctionPass::getAnalysisUsage(AU);
- }
- };
-}
-
-FunctionPass * createX86FloatingPointKillerPass() { return new FPK(); }
-
-bool FPK::runOnMachineFunction(MachineFunction &MF)
-{
- const TargetInstrInfo& tii = MF.getTarget().getInstrInfo();;
-
- for (MachineFunction::iterator
- mbbi = MF.begin(), mbbe = MF.end(); mbbi != mbbe; ++mbbi) {
- MachineBasicBlock& mbb = *mbbi;
- MachineBasicBlock::reverse_iterator mii = mbb.rbegin();
- // rewind to the last non terminating instruction
- while (mii != mbb.rend() && tii.isTerminatorInstr((*mii)->getOpcode())) {
- ++mii;
- }
- // add implicit def for all virtual floating point registers so that
- // they are spilled at the end of each basic block, since our
- // register stackifier doesn't handle them otherwise.
- MachineInstr* instr = BuildMI(X86::IMPLICIT_DEF, 7)
- .addReg(X86::FP6, MOTy::Def)
- .addReg(X86::FP5, MOTy::Def)
- .addReg(X86::FP4, MOTy::Def)
- .addReg(X86::FP3, MOTy::Def)
- .addReg(X86::FP2, MOTy::Def)
- .addReg(X86::FP1, MOTy::Def)
- .addReg(X86::FP0, MOTy::Def);
-
- mbb.insert(mii.base(), instr);
- LiveVariables& lv = getAnalysis<LiveVariables>();
- for (unsigned i = 0; i < instr->getNumOperands(); ++i) {
- lv.HandlePhysRegDef(instr->getOperand(i).getAllocatedRegNum(), instr);
- // force live variables to compute that these registers are dead
- lv.HandlePhysRegDef(instr->getOperand(i).getAllocatedRegNum(), 0);
- }
- }
- return true;
-}
-
-} // End llvm namespace