X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FTarget%2FSparcV9%2FInstrSelection%2FInstrSelection.cpp;h=32dc65e6e1e9196e0b558d4984784c789b463bba;hp=85725920f4ee20668658b63ff25ace43e53e8991;hb=b576c94c15af9a440f69d9d03c2afead7971118c;hpb=89df1ae2c3243a8af03da57d4edf626bf4a6e597 diff --git a/lib/Target/SparcV9/InstrSelection/InstrSelection.cpp b/lib/Target/SparcV9/InstrSelection/InstrSelection.cpp index 85725920f4e..32dc65e6e1e 100644 --- a/lib/Target/SparcV9/InstrSelection/InstrSelection.cpp +++ b/lib/Target/SparcV9/InstrSelection/InstrSelection.cpp @@ -1,178 +1,270 @@ -// $Id$ -*-c++-*- -//*************************************************************************** -// File: -// InstrSelection.cpp +//===- InstrSelection.cpp - Machine Independent Inst Selection Driver -----===// // -// Purpose: +// The LLVM Compiler Infrastructure +// +// This file was developed by the LLVM research group and is distributed under +// the University of Illinois Open Source License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Machine-independent driver file for instruction selection. This file +// constructs a forest of BURG instruction trees and then uses the +// BURG-generated tree grammar (BURM) to find the optimal instruction sequences +// for a given machine. // -// History: -// 7/02/01 - Vikram Adve - Created -//**************************************************************************/ - - -//************************** System Include Files ***************************/ +//===----------------------------------------------------------------------===// - -//*************************** User Include Files ***************************/ - -#include "llvm/Support/CommandLine.h" -#include "llvm/Type.h" -#include "llvm/iMemory.h" -#include "llvm/Instruction.h" -#include "llvm/BasicBlock.h" -#include "llvm/Method.h" -#include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/InstrSelection.h" +#include "llvm/CodeGen/InstrSelectionSupport.h" +#include "llvm/CodeGen/InstrForest.h" +#include "llvm/CodeGen/MachineCodeForInstruction.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/Target/TargetRegInfo.h" +#include "llvm/Target/TargetMachine.h" +#include "llvm/Function.h" +#include "llvm/iPHINode.h" +#include "llvm/Pass.h" +#include "Support/CommandLine.h" +#include "Support/LeakDetector.h" +using std::vector; +std::vector +FixConstantOperandsForInstr(Instruction* vmInstr, MachineInstr* minstr, + TargetMachine& target); -//************************* Forward Declarations ***************************/ +namespace { + //===--------------------------------------------------------------------===// + // SelectDebugLevel - Allow command line control over debugging. + // + enum SelectDebugLevel_t { + Select_NoDebugInfo, + Select_PrintMachineCode, + Select_DebugInstTrees, + Select_DebugBurgTrees, + }; + + // Enable Debug Options to be specified on the command line + cl::opt + SelectDebugLevel("dselect", cl::Hidden, + cl::desc("enable instruction selection debug information"), + cl::values( + clEnumValN(Select_NoDebugInfo, "n", "disable debug output"), + clEnumValN(Select_PrintMachineCode, "y", "print generated machine code"), + clEnumValN(Select_DebugInstTrees, "i", + "print debugging info for instruction selection"), + clEnumValN(Select_DebugBurgTrees, "b", "print burg trees"), + 0)); -static bool SelectInstructionsForTree(BasicTreeNode* treeRoot, - int goalnt, - TargetMachine &Target); + //===--------------------------------------------------------------------===// + // InstructionSelection Pass + // + // This is the actual pass object that drives the instruction selection + // process. + // + class InstructionSelection : public FunctionPass { + TargetMachine &Target; + void InsertCodeForPhis(Function &F); + void InsertPhiElimInstructions(BasicBlock *BB, + const vector& CpVec); + void SelectInstructionsForTree(InstrTreeNode* treeRoot, int goalnt); + void PostprocessMachineCodeForTree(InstructionNode* instrNode, + int ruleForNode, short* nts); + public: + InstructionSelection(TargetMachine &T) : Target(T) {} -//************************* Internal Data Types *****************************/ + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesCFG(); + } + + bool runOnFunction(Function &F); + virtual const char *getPassName() const { return "Instruction Selection"; } + }; +} -enum SelectDebugLevel_t { - Select_NoDebugInfo, - Select_PrintMachineCode, - Select_DebugInstTrees, - Select_DebugBurgTrees, -}; +TmpInstruction::TmpInstruction(MachineCodeForInstruction& mcfi, + Value *s1, Value *s2, const std::string &name) + : Instruction(s1->getType(), Instruction::UserOp1, name) +{ + mcfi.addTemp(this); -// Enable Debug Options to be specified on the command line -cl::Enum SelectDebugLevel("dselect", cl::NoFlags, // cl::Hidden - "enable instruction selection debugging information", - clEnumValN(Select_NoDebugInfo, "n", "disable debug output"), - clEnumValN(Select_PrintMachineCode, "y", "print generated machine code"), - clEnumValN(Select_DebugInstTrees, "i", "print instr. selection debugging info"), - clEnumValN(Select_DebugBurgTrees, "b", "print burg trees"), 0); + Operands.push_back(Use(s1, this)); // s1 must be non-null + if (s2) { + Operands.push_back(Use(s2, this)); + } + // TmpInstructions should not be garbage checked. + LeakDetector::removeGarbageObject(this); +} + +// Constructor that requires the type of the temporary to be specified. +// Both S1 and S2 may be NULL.( +TmpInstruction::TmpInstruction(MachineCodeForInstruction& mcfi, + const Type *Ty, Value *s1, Value* s2, + const std::string &name) + : Instruction(Ty, Instruction::UserOp1, name) +{ + mcfi.addTemp(this); -//************************** External Functions ****************************/ + if (s1) { Operands.push_back(Use(s1, this)); } + if (s2) { Operands.push_back(Use(s2, this)); } + // TmpInstructions should not be garbage checked. + LeakDetector::removeGarbageObject(this); +} -//--------------------------------------------------------------------------- -// Entry point for instruction selection using BURG. -// Returns true if instruction selection failed, false otherwise. -//--------------------------------------------------------------------------- -bool -SelectInstructionsForMethod(Method* method, - TargetMachine &Target) +bool InstructionSelection::runOnFunction(Function &F) { - bool failed = false; - // // Build the instruction trees to be given as inputs to BURG. // - InstrForest instrForest; - instrForest.buildTreesForMethod(method); + InstrForest instrForest(&F); if (SelectDebugLevel >= Select_DebugInstTrees) { - cout << "\n\n*** Instruction trees for method " - << (method->hasName()? method->getName() : "") - << endl << endl; + std::cerr << "\n\n*** Input to instruction selection for function " + << F.getName() << "\n\n" << F + << "\n\n*** Instruction trees for function " + << F.getName() << "\n\n"; instrForest.dump(); } // // Invoke BURG instruction selection for each tree // - const hash_set &treeRoots = instrForest.getRootSet(); - for (hash_set::const_iterator - treeRootIter = treeRoots.begin(); - treeRootIter != treeRoots.end(); - ++treeRootIter) + for (InstrForest::const_root_iterator RI = instrForest.roots_begin(); + RI != instrForest.roots_end(); ++RI) { - BasicTreeNode* basicNode = (*treeRootIter)->getBasicNode(); + InstructionNode* basicNode = *RI; + assert(basicNode->parent() == NULL && "A `root' node has a parent?"); // Invoke BURM to label each tree node with a state - (void) burm_label(basicNode); + burm_label(basicNode); if (SelectDebugLevel >= Select_DebugBurgTrees) { printcover(basicNode, 1, 0); - cerr << "\nCover cost == " << treecost(basicNode, 1, 0) << "\n\n"; + std::cerr << "\nCover cost == " << treecost(basicNode, 1, 0) <<"\n\n"; printMatches(basicNode); } // Then recursively walk the tree to select instructions - if (SelectInstructionsForTree(basicNode, /*goalnt*/1, Target)) - { - failed = true; - break; - } + SelectInstructionsForTree(basicNode, /*goalnt*/1); } // - // Record instructions in the vector for each basic block + // Create the MachineBasicBlock records and add all of the MachineInstrs + // defined in the MachineCodeForInstruction objects to also live in the + // MachineBasicBlock objects. // - for (Method::iterator BI = method->begin(); BI != method->end(); ++BI) - { - MachineCodeForBasicBlock& bbMvec = (*BI)->getMachineInstrVec(); - for (BasicBlock::iterator II = (*BI)->begin(); II != (*BI)->end(); ++II) - { - MachineCodeForVMInstr& mvec = (*II)->getMachineInstrVec(); - for (unsigned i=0; i < mvec.size(); i++) - bbMvec.push_back(mvec[i]); - } + MachineFunction &MF = MachineFunction::get(&F); + for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; ++BI) { + MachineBasicBlock *MCBB = new MachineBasicBlock(BI); + MF.getBasicBlockList().push_back(MCBB); + + for (BasicBlock::iterator II = BI->begin(); II != BI->end(); ++II) { + MachineCodeForInstruction &mvec = MachineCodeForInstruction::get(II); + MCBB->insert(MCBB->end(), mvec.begin(), mvec.end()); } + } + + // Insert phi elimination code + InsertCodeForPhis(F); if (SelectDebugLevel >= Select_PrintMachineCode) { - cout << endl << "*** Machine instructions after INSTRUCTION SELECTION" << endl; - PrintMachineInstructions(method); + std::cerr << "\n*** Machine instructions after INSTRUCTION SELECTION\n"; + MachineFunction::get(&F).dump(); } - return false; + return true; } -//--------------------------------------------------------------------------- -// Function: FoldGetElemChain -// -// Purpose: -// Fold a chain of GetElementPtr instructions into an equivalent -// (Pointer, IndexVector) pair. Returns the pointer Value, and -// stores the resulting IndexVector in argument chainIdxVec. -//--------------------------------------------------------------------------- +//------------------------------------------------------------------------- +// This method inserts phi elimination code for all BBs in a method +//------------------------------------------------------------------------- -Value* -FoldGetElemChain(const InstructionNode* getElemInstrNode, - vector& chainIdxVec) +void +InstructionSelection::InsertCodeForPhis(Function &F) { - MemAccessInst* getElemInst = (MemAccessInst*) - getElemInstrNode->getInstruction(); - - // Initialize return values from the incoming instruction - Value* ptrVal = getElemInst->getPtrOperand(); - chainIdxVec = getElemInst->getIndexVec(); // copies index vector values - - // Now chase the chain of getElementInstr instructions, if any - InstrTreeNode* ptrChild = getElemInstrNode->leftChild(); - while (ptrChild->getOpLabel() == Instruction::GetElementPtr || - ptrChild->getOpLabel() == GetElemPtrIdx) - { - // Child is a GetElemPtr instruction - getElemInst = (MemAccessInst*) - ((InstructionNode*) ptrChild)->getInstruction(); - const vector& idxVec = getElemInst->getIndexVec(); - - // Get the pointer value out of ptrChild and *prepend* its index vector - ptrVal = getElemInst->getPtrOperand(); - chainIdxVec.insert(chainIdxVec.begin(), idxVec.begin(), idxVec.end()); + // for all basic blocks in function + // + MachineFunction &MF = MachineFunction::get(&F); + for (MachineFunction::iterator BB = MF.begin(); BB != MF.end(); ++BB) { + for (BasicBlock::const_iterator IIt = BB->getBasicBlock()->begin(); + const PHINode *PN = dyn_cast(IIt); ++IIt) { + // FIXME: This is probably wrong... + Value *PhiCpRes = new PHINode(PN->getType(), "PhiCp:"); + + // The leak detector shouldn't track these nodes. They are not garbage, + // even though their parent field is never filled in. + // + LeakDetector::removeGarbageObject(PhiCpRes); + + // for each incoming value of the phi, insert phi elimination + // + for (unsigned i = 0; i < PN->getNumIncomingValues(); ++i) { + // insert the copy instruction to the predecessor BB + vector mvec, CpVec; + Target.getRegInfo().cpValue2Value(PN->getIncomingValue(i), PhiCpRes, + mvec); + for (vector::iterator MI=mvec.begin(); + MI != mvec.end(); ++MI) { + vector CpVec2 = + FixConstantOperandsForInstr(const_cast(PN), *MI, Target); + CpVec2.push_back(*MI); + CpVec.insert(CpVec.end(), CpVec2.begin(), CpVec2.end()); + } + + InsertPhiElimInstructions(PN->getIncomingBlock(i), CpVec); + } - ptrChild = ptrChild->leftChild(); - } - - return ptrVal; + vector mvec; + Target.getRegInfo().cpValue2Value(PhiCpRes, const_cast(PN), + mvec); + BB->insert(BB->begin(), mvec.begin(), mvec.end()); + } // for each Phi Instr in BB + } // for all BBs in function } +//------------------------------------------------------------------------- +// Thid method inserts a copy instruction to a predecessor BB as a result +// of phi elimination. +//------------------------------------------------------------------------- + +void +InstructionSelection::InsertPhiElimInstructions(BasicBlock *BB, + const vector& CpVec) +{ + Instruction *TermInst = (Instruction*)BB->getTerminator(); + MachineCodeForInstruction &MC4Term = MachineCodeForInstruction::get(TermInst); + MachineInstr *FirstMIOfTerm = MC4Term.front(); + assert (FirstMIOfTerm && "No Machine Instrs for terminator"); + + MachineFunction &MF = MachineFunction::get(BB->getParent()); -//*********************** Private Functions *****************************/ + // FIXME: if PHI instructions existed in the machine code, this would be + // unnecessary. + MachineBasicBlock *MBB = 0; + for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) + if (I->getBasicBlock() == BB) { + MBB = I; + break; + } + + // find the position of first machine instruction generated by the + // terminator of this BB + MachineBasicBlock::iterator MCIt = + std::find(MBB->begin(), MBB->end(), FirstMIOfTerm); + + assert(MCIt != MBB->end() && "Start inst of terminator not found"); + + // insert the copy instructions just before the first machine instruction + // generated for the terminator + MBB->insert(MCIt, CpVec.begin(), CpVec.end()); +} //--------------------------------------------------------------------------- @@ -191,57 +283,49 @@ FoldGetElemChain(const InstructionNode* getElemInstrNode, // may be used by multiple instructions). //--------------------------------------------------------------------------- -bool -SelectInstructionsForTree(BasicTreeNode* treeRoot, - int goalnt, - TargetMachine &Target) +void +InstructionSelection::SelectInstructionsForTree(InstrTreeNode* treeRoot, + int goalnt) { - // Use a static vector to avoid allocating a new one per VM instruction - static MachineInstr* minstrVec[MAX_INSTR_PER_VMINSTR]; - // Get the rule that matches this node. // int ruleForNode = burm_rule(treeRoot->state, goalnt); - if (ruleForNode == 0) - { - cerr << "Could not match instruction tree for instr selection" << endl; - return true; - } + if (ruleForNode == 0) { + std::cerr << "Could not match instruction tree for instr selection\n"; + abort(); + } // Get this rule's non-terminals and the corresponding child nodes (if any) // short *nts = burm_nts[ruleForNode]; - // First, select instructions for the current node and rule. // (If this is a list node, not an instruction, then skip this step). // This function is specific to the target architecture. // if (treeRoot->opLabel != VRegListOp) { - InstructionNode* instrNode = (InstructionNode*) MainTreeNode(treeRoot); + vector minstrVec; + + InstructionNode* instrNode = (InstructionNode*)treeRoot; assert(instrNode->getNodeType() == InstrTreeNode::NTInstructionNode); - unsigned N = GetInstructionsByRule(instrNode, ruleForNode, nts, Target, - minstrVec); - assert(N <= MAX_INSTR_PER_VMINSTR); - for (unsigned i=0; i < N; i++) - { - assert(minstrVec[i] != NULL); - instrNode->getInstruction()->addMachineInstruction(minstrVec[i]); - } + GetInstructionsByRule(instrNode, ruleForNode, nts, Target, minstrVec); + + MachineCodeForInstruction &mvec = + MachineCodeForInstruction::get(instrNode->getInstruction()); + mvec.insert(mvec.end(), minstrVec.begin(), minstrVec.end()); } // Then, recursively compile the child nodes, if any. // if (nts[0]) { // i.e., there is at least one kid - - BasicTreeNode* kids[2]; + InstrTreeNode* kids[2]; int currentRule = ruleForNode; burm_kids(treeRoot, currentRule, kids); - + // First skip over any chain rules so that we don't visit // the current node again. // @@ -255,20 +339,55 @@ SelectInstructionsForTree(BasicTreeNode* treeRoot, // Now we have the first non-chain rule so we have found // the actual child nodes. Recursively compile them. // - for (int i = 0; nts[i]; i++) + for (unsigned i = 0; nts[i]; i++) { assert(i < 2); - InstrTreeNode::InstrTreeNodeType - nodeType = MainTreeNode(kids[i])->getNodeType(); + InstrTreeNode::InstrTreeNodeType nodeType = kids[i]->getNodeType(); if (nodeType == InstrTreeNode::NTVRegListNode || nodeType == InstrTreeNode::NTInstructionNode) - { - if (SelectInstructionsForTree(kids[i], nts[i], Target)) - return true; // failure - } + SelectInstructionsForTree(kids[i], nts[i]); } } - return false; // success + // Finally, do any post-processing on this node after its children + // have been translated + // + if (treeRoot->opLabel != VRegListOp) + PostprocessMachineCodeForTree((InstructionNode*)treeRoot, ruleForNode, nts); +} + +//--------------------------------------------------------------------------- +// Function PostprocessMachineCodeForTree +// +// Apply any final cleanups to machine code for the root of a subtree +// after selection for all its children has been completed. +// +void +InstructionSelection::PostprocessMachineCodeForTree(InstructionNode* instrNode, + int ruleForNode, + short* nts) +{ + // Fix up any constant operands in the machine instructions to either + // use an immediate field or to load the constant into a register + // Walk backwards and use direct indexes to allow insertion before current + // + Instruction* vmInstr = instrNode->getInstruction(); + MachineCodeForInstruction &mvec = MachineCodeForInstruction::get(vmInstr); + for (unsigned i = mvec.size(); i != 0; --i) + { + vector loadConstVec = + FixConstantOperandsForInstr(vmInstr, mvec[i-1], Target); + + mvec.insert(mvec.begin()+i-1, loadConstVec.begin(), loadConstVec.end()); + } } + + +//===----------------------------------------------------------------------===// +// createInstructionSelectionPass - Public entrypoint for instruction selection +// and this file as a whole... +// +FunctionPass *createInstructionSelectionPass(TargetMachine &T) { + return new InstructionSelection(T); +}