//===----------------------------------------------------------------------===//
//
// 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 "Support/STLExtras.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!");
// Emit an fxch to update the runtime processors version of the state
MachineInstr *MI = BuildMI(X86::FXCH, 1).addReg(STReg);
- I = 1+MBB->insert(I, MI);
+ MBB->insert(I, MI);
NumFXCH++;
}
}
pushReg(AsReg); // New register on top of stack
MachineInstr *MI = BuildMI(X86::FLDrr, 1).addReg(STReg);
- I = 1+MBB->insert(I, MI);
+ MBB->insert(I, MI);
}
// popStackAfter - Pop the current value off of the top of the FP stack
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;
}
MBB = &BB;
for (MachineBasicBlock::iterator I = BB.begin(); I != BB.end(); ++I) {
- MachineInstr *MI = *I;
- MachineInstr *PrevMI = I == BB.begin() ? 0 : *(I-1);
+ MachineInstr *MI = I;
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 = 0;
+ if (I != BB.begin())
+ PrevMI = prior(I);
++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!");
}
}
// Print out all of the instructions expanded to if -debug
- DEBUG(if (*I == PrevMI) {
- std::cerr<< "Just deleted pseudo instruction\n";
- } else {
- MachineBasicBlock::iterator Start = I;
- // Rewind to first instruction newly inserted.
- while (Start != BB.begin() && *(Start-1) != PrevMI) --Start;
- std::cerr << "Inserted instructions:\n\t";
- (*Start)->print(std::cerr, MF.getTarget());
- while (++Start != I+1);
- }
- dumpStack();
- );
+ DEBUG(
+ MachineBasicBlock::iterator PrevI(PrevMI);
+ if (I == PrevI) {
+ std::cerr<< "Just deleted pseudo instruction\n";
+ } else {
+ MachineBasicBlock::iterator Start = I;
+ // Rewind to first instruction newly inserted.
+ while (Start != BB.begin() && prior(Start) != PrevI) --Start;
+ std::cerr << "Inserted instructions:\n\t";
+ Start->print(std::cerr, MF.getTarget());
+ while (++Start != next(I));
+ }
+ dumpStack();
+ );
Changed = true;
}
// 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)
RegMap[Stack[--StackTop]] = ~0; // Update state
// Check to see if there is a popping version of this instruction...
- int Opcode = Lookup(PopTable, ARRAY_SIZE(PopTable), (*I)->getOpcode());
+ int Opcode = Lookup(PopTable, ARRAY_SIZE(PopTable), I->getOpcode());
if (Opcode != -1) {
- (*I)->setOpcode(Opcode);
+ I->setOpcode(Opcode);
if (Opcode == X86::FUCOMPPr)
- (*I)->RemoveOperand(0);
+ I->RemoveOperand(0);
} else { // Insert an explicit pop
MachineInstr *MI = BuildMI(X86::FSTPrr, 1).addReg(X86::ST0);
- I = MBB->insert(I+1, MI);
+ I = MBB->insert(++I, MI);
}
}
static unsigned getFPReg(const MachineOperand &MO) {
- assert(MO.isPhysicalRegister() && "Expected an FP register!");
+ assert(MO.isRegister() && "Expected an FP register!");
unsigned Reg = MO.getReg();
assert(Reg >= X86::FP0 && Reg <= X86::FP6 && "Expected FP register!");
return Reg - X86::FP0;
//===----------------------------------------------------------------------===//
/// handleZeroArgFP - ST(0) = fld0 ST(0) = flds <mem>
-//
+///
void FPS::handleZeroArgFP(MachineBasicBlock::iterator &I) {
- MachineInstr *MI = *I;
+ MachineInstr *MI = I;
unsigned DestReg = getFPReg(MI->getOperand(0));
MI->RemoveOperand(0); // Remove the explicit ST(0) operand
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!");
+ MachineInstr *MI = I;
+ assert((MI->getNumOperands() == 5 || MI->getNumOperands() == 1) &&
+ "Can only handle fst* & ftst instructions!");
- unsigned Reg = getFPReg(MI->getOperand(4));
+ // Is this the last use of the source register?
+ unsigned Reg = getFPReg(MI->getOperand(MI->getNumOperands()-1));
bool KillsSrc = false;
for (LiveVariables::killed_iterator KI = LV->killed_begin(MI),
E = LV->killed_end(MI); KI != E; ++KI)
} else {
moveToTop(Reg, I); // Move to the top of the stack...
}
- MI->RemoveOperand(4); // Remove explicit ST(0) operand
+ MI->RemoveOperand(MI->getNumOperands()-1); // Remove explicit ST(0) operand
if (MI->getOpcode() == X86::FSTPr80 || MI->getOpcode() == X86::FISTPr64) {
assert(StackTop > 0 && "Stack empty??");
}
}
+
+/// 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
//
void FPS::handleTwoArgFP(MachineBasicBlock::iterator &I) {
ASSERT_SORTED(ForwardST0Table); ASSERT_SORTED(ReverseST0Table);
ASSERT_SORTED(ForwardSTiTable); ASSERT_SORTED(ReverseSTiTable);
- MachineInstr *MI = *I;
+ MachineInstr *MI = I;
unsigned NumOperands = MI->getNumOperands();
assert(NumOperands == 3 ||
unsigned NotTOS = (TOS == Op0) ? Op1 : Op0;
// Replace the old instruction with a new instruction
- *I = BuildMI(Opcode, 1).addReg(getSTReg(NotTOS));
+ MBB->remove(I);
+ I = MBB->insert(I, BuildMI(Opcode, 1).addReg(getSTReg(NotTOS)));
// If both operands are killed, pop one off of the stack in addition to
// overwriting the other one.
Stack[--StackTop] = ~0;
MachineInstr *MI = BuildMI(X86::FSTPrr, 1).addReg(STReg);
- I = MBB->insert(I+1, MI);
+ I = MBB->insert(++I, MI);
}
}
}
/// instructions.
///
void FPS::handleSpecialFP(MachineBasicBlock::iterator &I) {
- MachineInstr *MI = *I;
+ MachineInstr *MI = I;
switch (MI->getOpcode()) {
default: assert(0 && "Unknown SpecialFP instruction!");
case X86::FpGETRESULT: // Appears immediately after a call returning FP type!
}
}
- I = MBB->erase(I)-1; // Remove the pseudo instruction
-}
-
-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.addPreserved<LiveVariables>();
- AU.addRequired<LiveVariables>();
- AU.addPreservedID(PHIEliminationID);
- 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;
+ I = MBB->erase(I); // Remove the pseudo instruction
+ --I;
}
-
-} // End llvm namespace