diff options
author | Guochun Shi <gshi1@uiuc.edu> | 2003-06-08 23:16:07 +0000 |
---|---|---|
committer | Guochun Shi <gshi1@uiuc.edu> | 2003-06-08 23:16:07 +0000 |
commit | 8f1d4ab409253e665a4cbd92401d345010bdc561 (patch) | |
tree | 63918bddbe36af1d6ecf6a23fcd0da12c48fe912 /lib/CodeGen | |
parent | 33280524f4882a3e6a7fa011a62595ba3a65c8ec (diff) | |
download | external_llvm-8f1d4ab409253e665a4cbd92401d345010bdc561.zip external_llvm-8f1d4ab409253e665a4cbd92401d345010bdc561.tar.gz external_llvm-8f1d4ab409253e665a4cbd92401d345010bdc561.tar.bz2 |
delete useless functions
add comment
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@6673 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/CodeGen')
-rw-r--r-- | lib/CodeGen/ModuloScheduling/ModuloSchedGraph.cpp | 338 | ||||
-rw-r--r-- | lib/CodeGen/ModuloScheduling/ModuloSchedGraph.h | 18 | ||||
-rw-r--r-- | lib/CodeGen/ModuloScheduling/ModuloScheduling.cpp | 42 | ||||
-rw-r--r-- | lib/CodeGen/ModuloScheduling/ModuloScheduling.h | 8 |
4 files changed, 190 insertions, 216 deletions
diff --git a/lib/CodeGen/ModuloScheduling/ModuloSchedGraph.cpp b/lib/CodeGen/ModuloScheduling/ModuloSchedGraph.cpp index 4f46a73..b25b65c 100644 --- a/lib/CodeGen/ModuloScheduling/ModuloSchedGraph.cpp +++ b/lib/CodeGen/ModuloScheduling/ModuloSchedGraph.cpp @@ -21,83 +21,42 @@ #include <vector> #include <math.h> + #define UNIDELAY 1 -//*********************** Internal Data Structures *************************/ +using std::cerr; +using std::endl; +using std::vector; -// The following two types need to be classes, not typedefs, so we can use -// opaque declarations in SchedGraph.h -// -struct RefVec:public std::vector<std::pair<ModuloSchedGraphNode*,int> > { - typedef std::vector<std::pair<ModuloSchedGraphNode*, - int> >::iterator iterator; - typedef std::vector<std::pair<ModuloSchedGraphNode*, - int> >::const_iterator const_iterator; -}; -struct RegToRefVecMap:public hash_map<int,RefVec> { - typedef hash_map<int,RefVec>::iterator iterator; - typedef hash_map<int,RefVec>::const_iterator const_iterator; -}; +/***********member functions for ModuloSchedGraphNode*********/ -struct ValueToDefVecMap:public hash_map<const Instruction*,RefVec> { - typedef hash_map<const Instruction*, RefVec>::iterator iterator; - typedef hash_map<const Instruction*, - RefVec>::const_iterator const_iterator; -}; - -// class Modulo SchedGraphNode ModuloSchedGraphNode::ModuloSchedGraphNode(unsigned int in_nodeId, const BasicBlock * in_bb, const Instruction * in_inst, int indexInBB, const TargetMachine & target) -:SchedGraphNodeCommon(in_nodeId, indexInBB), inst(in_inst) -{ + :SchedGraphNodeCommon(in_nodeId, indexInBB), inst(in_inst){ + if (inst) { //FIXME: find the latency - //currently setthe latency to zero + //currently set the latency to zero latency = 0; } } -//class ModuloScheGraph -void ModuloSchedGraph::addDummyEdges() -{ - assert(graphRoot->outEdges.size() == 0); - - for (const_iterator I = begin(); I != end(); ++I) { - ModuloSchedGraphNode *node = (ModuloSchedGraphNode *) ((*I).second); - assert(node != graphRoot && node != graphLeaf); - if (node->beginInEdges() == node->endInEdges()) - (void) new SchedGraphEdge(graphRoot, node, SchedGraphEdge::CtrlDep, - SchedGraphEdge::NonDataDep, 0); - if (node->beginOutEdges() == node->endOutEdges()) - (void) new SchedGraphEdge(node, graphLeaf, SchedGraphEdge::CtrlDep, - SchedGraphEdge::NonDataDep, 0); - } -} - -bool isDefinition(const Instruction *I) -{ - //if(TerminatorInst::classof(I)||FreeInst::classof(I) || StoreInst::classof(I) || CallInst::classof(I)) - if (!I->hasName()) - return false; - else - return true; -} +/***********member functions for ModuloSchedGraph*********/ -void ModuloSchedGraph::addDefUseEdges(const BasicBlock *bb) -{ +void +ModuloSchedGraph::addDefUseEdges(const BasicBlock *bb){ + //collect def instructions, store them in vector - // const TargetInstrInfo& mii = target.getInstrInfo(); const TargetInstrInfo & mii = target.getInstrInfo(); - - typedef std::vector < ModuloSchedGraphNode * >DefVec; - DefVec defVec; - + vector < ModuloSchedGraphNode * > defVec; + + //find those def instructions for (BasicBlock::const_iterator I = bb->begin(), E = bb->end(); I != E; ++I) { if (I->getType() != Type::VoidTy) { @@ -115,38 +74,40 @@ void ModuloSchedGraph::addDefUseEdges(const BasicBlock *bb) Instruction *inst = (Instruction *) (*I); ModuloSchedGraphNode *node = NULL; - for (BasicBlock::const_iterator I = bb->begin(), E = bb->end(); - I != E; ++I) - if ((const Instruction *) I == inst) { + for (BasicBlock::const_iterator ins = bb->begin(), E = bb->end(); + ins != E; ++ins) + if ((const Instruction *) ins == inst) { node = (*this)[inst]; break; } - assert(inst != NULL && " Use not an Instruction ?"); - if (node == NULL) //inst is not an instruction in this block - { + if (node == NULL){ + + //inst is not an instruction in this block + //do nothing + } else { // Add a flow edge from the def instruction to the ref instruction - + // This is a true dependence, so the delay is equal to the + //delay of the preceding node. + + int delay = 0; + // self loop will not happen in SSA form assert(defVec[i] != node && "same node?"); - // This is a true dependence, so the delay is equal to the delay of the - // pred node. - int delay = 0; MachineCodeForInstruction & tempMvec = MachineCodeForInstruction::get(value); for (unsigned j = 0; j < tempMvec.size(); j++) { MachineInstr *temp = tempMvec[j]; - //delay +=mii.minLatency(temp->getOpCode()); delay = std::max(delay, mii.minLatency(temp->getOpCode())); } SchedGraphEdge *trueEdge = - new SchedGraphEdge(defVec[i], node, value, + new SchedGraphEdge(defVec[i], node, value, SchedGraphEdge::TrueDep, delay); - + // if the ref instruction is before the def instrution // then the def instruction must be a phi instruction // add an anti-dependence edge to from the ref instruction to the def @@ -163,11 +124,14 @@ void ModuloSchedGraph::addDefUseEdges(const BasicBlock *bb) } } -void ModuloSchedGraph::addCDEdges(const BasicBlock * bb) { +void +ModuloSchedGraph::addCDEdges(const BasicBlock * bb) { + // find the last instruction in the basic block // see if it is an branch instruction. - // If yes, then add an edge from each node expcept the last node to the last - // node + // If yes, then add an edge from each node expcept the last node + //to the last node + const Instruction *inst = &(bb->back()); ModuloSchedGraphNode *lastNode = (*this)[inst]; if (TerminatorInst::classof(inst)) @@ -179,7 +143,7 @@ void ModuloSchedGraph::addCDEdges(const BasicBlock * bb) { (void) new SchedGraphEdge(node, lastNode, SchedGraphEdge::CtrlDep, SchedGraphEdge::NonDataDep, 0); } - + } } @@ -206,30 +170,46 @@ static const unsigned int SG_DepOrderArray[][3] = { // Use latency 1 just to ensure that memory operations are ordered; // latency does not otherwise matter (true dependences enforce that). // -void ModuloSchedGraph::addMemEdges(const BasicBlock * bb) { - - std::vector<ModuloSchedGraphNode*> memNodeVec; +void +ModuloSchedGraph::addMemEdges(const BasicBlock * bb) { + vector<ModuloSchedGraphNode*> memNodeVec; + //construct the memNodeVec - for (BasicBlock::const_iterator I = bb->begin(), E = bb->end(); I != E; ++I) { + for (BasicBlock::const_iterator I = bb->begin(), + E = bb->end(); I != E; ++I) { + if (LoadInst::classof(I) || StoreInst::classof(I) || CallInst::classof(I)) { + ModuloSchedGraphNode *node = (*this)[(const Instruction *) I]; memNodeVec.push_back(node); + } } - // Instructions in memNodeVec are in execution order within the basic block, - // so simply look at all pairs <memNodeVec[i], memNodeVec[j: j > i]>. - // + // Instructions in memNodeVec are in execution order within the + // basic block, so simply look at all pairs + // <memNodeVec[i], memNodeVec[j: j > i]>. + for (unsigned im = 0, NM = memNodeVec.size(); im < NM; im++) { - const Instruction *fromInst = memNodeVec[im]->getInst(); - int fromType = CallInst::classof(fromInst) ? SG_CALL_REF - : LoadInst::classof(fromInst) ? SG_LOAD_REF : SG_STORE_REF; + + const Instruction *fromInst,*toInst; + int toType, fromType; + + //get the first mem instruction and instruction type + fromInst = memNodeVec[im]->getInst(); + fromType = CallInst::classof(fromInst) ? SG_CALL_REF + : LoadInst::classof(fromInst) ? SG_LOAD_REF : SG_STORE_REF; + for (unsigned jm = im + 1; jm < NM; jm++) { - const Instruction *toInst = memNodeVec[jm]->getInst(); - int toType = CallInst::classof(toInst) ? SG_CALL_REF + + //get the second mem instruction and instruction type + toInst = memNodeVec[jm]->getInst(); + toType = CallInst::classof(toInst) ? SG_CALL_REF : LoadInst::classof(toInst) ? SG_LOAD_REF : SG_STORE_REF; + + //add two edges if not both of them are LOAD instructions if (fromType != SG_LOAD_REF || toType != SG_LOAD_REF) { (void) new SchedGraphEdge(memNodeVec[im], memNodeVec[jm], SchedGraphEdge::MemoryDep, @@ -239,8 +219,10 @@ void ModuloSchedGraph::addMemEdges(const BasicBlock * bb) { new SchedGraphEdge(memNodeVec[jm], memNodeVec[im], SchedGraphEdge::MemoryDep, SG_DepOrderArray[toType][fromType], 1); - edge->setIteDiff(1); + //set the iteration difference for this edge to 1. + edge->setIteDiff(1); + } } } @@ -248,36 +230,32 @@ void ModuloSchedGraph::addMemEdges(const BasicBlock * bb) { -void ModuloSchedGraph::buildNodesforBB(const TargetMachine &target, - const BasicBlock *bb, - std::vector<ModuloSchedGraphNode*> &memNode, - RegToRefVecMap ®ToRefVecMap, - ValueToDefVecMap &valueToDefVecMap) -{ - //const TargetInstrInfo& mii=target.getInstrInfo(); - - //Build graph nodes for each LLVM instruction and gather def/use info. - //Do both together in a single pass over all machine instructions. - +void +ModuloSchedGraph::buildNodesforBB(const TargetMachine &target, + const BasicBlock *bb){ + int i = 0; - for (BasicBlock::const_iterator I = bb->begin(), E = bb->end(); I != E; - ++I) { - ModuloSchedGraphNode *node = - new ModuloSchedGraphNode(getNumNodes(), bb, I, i, target); + ModuloSchedGraphNode *node; + + for (BasicBlock::const_iterator I = bb->begin(), E = bb->end(); + I != E; ++I) { + + node=new ModuloSchedGraphNode(getNumNodes(), bb, I, i, target); + i++; - this->noteModuloSchedGraphNodeForInst(I, node); + + this->addHash(I, node); } - //this function finds some info about instruction in basic block for later use - //findDefUseInfoAtInstr(target, node, - //memNode,regToRefVecMap,valueToDefVecMap); } -bool ModuloSchedGraph::isLoop(const BasicBlock *bb) { +bool +ModuloSchedGraph::isLoop(const BasicBlock *bb) { + //only if the last instruction in the basicblock is branch instruction and //there is at least an option to branch itself - + const Instruction *inst = &(bb->back()); if (BranchInst::classof(inst)) { for (unsigned i = 0; i < ((BranchInst *) inst)->getNumSuccessors(); @@ -292,24 +270,6 @@ bool ModuloSchedGraph::isLoop(const BasicBlock *bb) { } -bool ModuloSchedGraph::isLoop() { - //only if the last instruction in the basicblock is branch instruction and - //there is at least an option to branch itself - - assert(this->bb&& "the basicblock is not empty"); - const Instruction *inst = &(bb->back()); - if (BranchInst::classof(inst)) - for (unsigned i = 0; i < ((BranchInst *) inst)->getNumSuccessors(); - i++) { - BasicBlock *sb = ((BranchInst *) inst)->getSuccessor(i); - if (sb == bb) - return true; - } - - return false; - -} - void ModuloSchedGraph::computeNodeASAP(const BasicBlock *bb) { //FIXME: now assume the only backward edges come from the edges from other @@ -872,27 +832,6 @@ void ModuloSchedGraph::buildGraph(const TargetMachine & target) assert(this->bb && "The basicBlock is NULL?"); - // Use this data structure to note all machine operands that compute - // ordinary LLVM values. These must be computed defs (i.e., instructions). - // Note that there may be multiple machine instructions that define - // each Value. - ValueToDefVecMap valueToDefVecMap; - - // Use this data structure to note all memory instructions. - // We use this to add memory dependence edges without a second full walk. - // - // vector<const Instruction*> memVec; - std::vector<ModuloSchedGraphNode*> memNodeVec; - - // Use this data structure to note any uses or definitions of - // machine registers so we can add edges for those later without - // extra passes over the nodes. - // The vector holds an ordered list of references to the machine reg, - // ordered according to control-flow order. This only works for a - // single basic block, hence the assertion. Each reference is identified - // by the pair: <node, operand-number>. - // - RegToRefVecMap regToRefVecMap; // Make a dummy root node. We'll add edges to the real roots later. graphRoot = new ModuloSchedGraphNode(0, NULL, NULL, -1, target); @@ -913,21 +852,21 @@ void ModuloSchedGraph::buildGraph(const TargetMachine & target) if (ModuloScheduling::printScheduleProcess()) this->dump(bb); - - if (!isLoop(bb)) { - DEBUG_PRINT(std::cerr << " dumping non-loop BB:\n"); - dump(bb); - } + if (isLoop(bb)) { - buildNodesforBB(target, bb, memNodeVec, regToRefVecMap, - valueToDefVecMap); + DEBUG_PRINT(cerr << "building nodes for this BasicBlock\n"); + buildNodesforBB(target, bb); + + DEBUG_PRINT(cerr << "adding def-use edge to this basic block\n"); this->addDefUseEdges(bb); - this->addCDEdges(bb); - this->addMemEdges(bb); - //this->dump(); + DEBUG_PRINT(cerr << "adding CD edges to this basic block\n"); + this->addCDEdges(bb); + DEBUG_PRINT(cerr << "adding memory edges to this basicblock\n"); + this->addMemEdges(bb); + int ResII = this->computeResII(bb); if (ModuloScheduling::printScheduleProcess()) DEBUG_PRINT(std::cerr << "ResII is " << ResII << "\n"); @@ -942,11 +881,12 @@ void ModuloSchedGraph::buildGraph(const TargetMachine & target) this->dumpNodeProperty(); this->orderNodes(); - + if (ModuloScheduling::printScheduleProcess()) this->dump(); - //this->instrScheduling(); + //this->instrScheduling(); + //this->dumpScheduling(); } } @@ -1229,31 +1169,8 @@ int ModuloSchedGraph::computeResII(const BasicBlock * bb) return ResII; } -ModuloSchedGraphSet::ModuloSchedGraphSet(const Function *function, - const TargetMachine &target) -: method(function) -{ - buildGraphsForMethod(method, target); -} - - -ModuloSchedGraphSet::~ModuloSchedGraphSet() -{ - //delete all the graphs - for (iterator I = begin(), E = end(); I != E; ++I) - delete *I; -} -void ModuloSchedGraphSet::dump() const -{ - DEBUG_PRINT(std::cerr << " ====== ModuloSched graphs for function `" << - method->getName() << "' =========\n\n"); - for (const_iterator I = begin(); I != end(); ++I) - (*I)->dump(); - DEBUG_PRINT(std::cerr << "\n=========End graphs for function `" << method->getName() - << "' ==========\n\n"); -} void ModuloSchedGraph::dump(const BasicBlock * bb) { @@ -1308,16 +1225,69 @@ void ModuloSchedGraph::dumpNodeProperty() const } } -void ModuloSchedGraphSet::buildGraphsForMethod(const Function *F, - const TargetMachine &target) -{ + + + +/************member functions for ModuloSchedGraphSet**************/ + +ModuloSchedGraphSet::ModuloSchedGraphSet(const Function *function, + const TargetMachine &target) +: method(function){ + + buildGraphsForMethod(method, target); + +} + + +ModuloSchedGraphSet::~ModuloSchedGraphSet(){ + + //delete all the graphs + for (iterator I = begin(), E = end(); I != E; ++I) + delete *I; +} + + + +void +ModuloSchedGraphSet::buildGraphsForMethod(const Function *F, + const TargetMachine &target){ + for (Function::const_iterator BI = F->begin(); BI != F->end(); ++BI){ const BasicBlock* local_bb; + local_bb=BI; addGraph(new ModuloSchedGraph((BasicBlock*)local_bb, target)); } + +} + +void +ModuloSchedGraphSet::dump() const{ + + DEBUG_PRINT(std::cerr << " ====== ModuloSched graphs for function `" << + method->getName() << "' =========\n\n"); + for (const_iterator I = begin(); I != end(); ++I) + (*I)->dump(); + + DEBUG_PRINT(std::cerr << "\n=========End graphs for function `" << method->getName() + << "' ==========\n\n"); +} + + + + +/********************misc functions***************************/ + + +static void +dumpBasicBlock(const BasicBlock * bb){ + + DEBUG_PRINT(std::cerr << "dumping basic block:"); + DEBUG_PRINT(std::cerr << (bb->hasName()? bb->getName() : "block") + << " (" << bb << ")" << "\n"); } + std::ostream& operator<<(std::ostream &os, const ModuloSchedGraphNode &node) { diff --git a/lib/CodeGen/ModuloScheduling/ModuloSchedGraph.h b/lib/CodeGen/ModuloScheduling/ModuloSchedGraph.h index 7cdfdd9..db3a9a3 100644 --- a/lib/CodeGen/ModuloScheduling/ModuloSchedGraph.h +++ b/lib/CodeGen/ModuloScheduling/ModuloSchedGraph.h @@ -250,9 +250,6 @@ public: //return wether the BasicBlock 'bb' contains a loop bool isLoop(const BasicBlock *bb); - //return this basibBlock contains a loop - bool isLoop(); - //return the node for the input instruction ModuloSchedGraphNode *getGraphNodeForInst(const Instruction *inst) const { const_iterator onePair = this->find(inst); @@ -293,11 +290,12 @@ public: using map_base::begin; using map_base::end; - void noteModuloSchedGraphNodeForInst(const Instruction *inst, - ModuloSchedGraphNode *node) - { + void addHash(const Instruction *inst, + ModuloSchedGraphNode *node){ + assert((*this)[inst] == NULL); (*this)[inst] = node; + } // Graph builder @@ -308,10 +306,7 @@ public: // Build nodes for BasicBlock void buildNodesforBB(const TargetMachine &target, - const BasicBlock *bb, - NodeVec &memNode, - RegToRefVecMap ®ToRefVecMap, - ValueToDefVecMap &valueToDefVecMap); + const BasicBlock *bb); //find definitiona and use information for all nodes void findDefUseInfoAtInstr(const TargetMachine &target, @@ -329,9 +324,6 @@ public: //add memory dependence dges void addMemEdges(const BasicBlock *bb); - //add dummy edges - void addDummyEdges(); - //computer source restrictoin II int computeResII(const BasicBlock *bb); diff --git a/lib/CodeGen/ModuloScheduling/ModuloScheduling.cpp b/lib/CodeGen/ModuloScheduling/ModuloScheduling.cpp index 0acac3a..f7149ca 100644 --- a/lib/CodeGen/ModuloScheduling/ModuloScheduling.cpp +++ b/lib/CodeGen/ModuloScheduling/ModuloScheduling.cpp @@ -97,28 +97,34 @@ void ModuloScheduling::instrScheduling() graph.dump(bb); } //construction of prologue, kernel and epilogue + + /* BasicBlock *kernel = bb->splitBasicBlock(bb->begin()); BasicBlock *prologue = bb; BasicBlock *epilogue = kernel->splitBasicBlock(kernel->begin()); + */ // Construct prologue - constructPrologue(prologue); + /*constructPrologue(prologue);*/ // Construct kernel - constructKernel(prologue, kernel, epilogue); + + /*constructKernel(prologue, kernel, epilogue);*/ // Construct epilogue - constructEpilogue(epilogue, succ_bb); + /*constructEpilogue(epilogue, succ_bb);*/ + //print the BasicBlocks if necessary - if (ModuloScheduling::printSchedule()) { - DEBUG_PRINT(std::cerr << "dumping the prologue block:\n"); - graph.dump(prologue); - DEBUG_PRINT(std::cerr << "dumping the kernel block\n"); - graph.dump(kernel); - DEBUG_PRINT(std::cerr << "dumping the epilogue block\n"); - graph.dump(epilogue); - } +// if (0){ +// DEBUG_PRINT(std::cerr << "dumping the prologue block:\n"); +// graph.dump(prologue); +// DEBUG_PRINT(std::cerr << "dumping the kernel block\n"); +// graph.dump(kernel); +// DEBUG_PRINT(std::cerr << "dumping the epilogue block\n"); +// graph.dump(epilogue); +// } + } // Clear memory from the last round and initialize if necessary @@ -526,7 +532,7 @@ void ModuloScheduling::constructEpilogue(BasicBlock *epilogue, Instruction *ist = (Instruction *) coreSchedule[i][j]->getInst(); ist->getParent()->getInstList().erase(ist); } - //**************************************************************// + //finally, insert an unconditional branch instruction at the end @@ -900,23 +906,29 @@ namespace { } // getAnalysisUsage - We use LiveVarInfo... - virtual void getAnalysisUsage(AnalysisUsage &AU) const { + virtual void getAnalysisUsage(AnalysisUsage &AU) const { //AU.addRequired(FunctionLiveVarInfo::ID); - } bool runOnFunction(Function & F); + } + + bool runOnFunction(Function & F); }; } // end anonymous namespace bool ModuloSchedulingPass::runOnFunction(Function &F) { + ModuloSchedGraphSet *graphSet = new ModuloSchedGraphSet(&F, target); - ModuloSchedulingSet ModuloSchedulingSet(*graphSet); + //ModuloSchedulingSet ModuloSchedulingSet(*graphSet); + + printf("runOnFunction in ModuloSchedulingPass returns\n"); return false; } Pass *createModuloSchedulingPass(const TargetMachine & tgt) { + printf("creating modulo scheduling \n"); return new ModuloSchedulingPass(tgt); } diff --git a/lib/CodeGen/ModuloScheduling/ModuloScheduling.h b/lib/CodeGen/ModuloScheduling/ModuloScheduling.h index cbb8fea..499d8f3 100644 --- a/lib/CodeGen/ModuloScheduling/ModuloScheduling.h +++ b/lib/CodeGen/ModuloScheduling/ModuloScheduling.h @@ -79,15 +79,15 @@ public: printSchedule() { //return ModuloScheduling::DebugLevel >= DebugLevel_PrintSchedule; - return false; - + return true; + } static bool printScheduleProcess() { //return DebugLevel >= DebugLevel_PrintScheduleProcess; - return false; + return true; } @@ -180,7 +180,7 @@ public: ModuloSchedulingSet(ModuloSchedGraphSet _graphSet): graphSet(_graphSet) { for (unsigned i = 0; i < graphSet.size(); i++) { ModuloSchedGraph & graph = *(graphSet[i]); - if (graph.isLoop()) + if (graph.isLoop(graph.getBasicBlock())) ModuloScheduling ModuloScheduling(graph); } }; |