LLVM API Documentation
00001 //===-- MSchedGraphSB.cpp - Scheduling Graph ----------------------*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // A graph class for dependencies. This graph only contains true, anti, and 00011 // output data dependencies for a given MachineBasicBlock. Dependencies 00012 // across iterations are also computed. Unless data dependence analysis 00013 // is provided, a conservative approach of adding dependencies between all 00014 // loads and stores is taken. 00015 //===----------------------------------------------------------------------===// 00016 00017 #define DEBUG_TYPE "ModuloSchedSB" 00018 #include "MSchedGraphSB.h" 00019 #include "../SparcV9RegisterInfo.h" 00020 #include "../MachineCodeForInstruction.h" 00021 #include "llvm/BasicBlock.h" 00022 #include "llvm/Constants.h" 00023 #include "llvm/Instructions.h" 00024 #include "llvm/Type.h" 00025 #include "llvm/CodeGen/MachineBasicBlock.h" 00026 #include "llvm/Target/TargetInstrInfo.h" 00027 #include "llvm/Support/Debug.h" 00028 #include <cstdlib> 00029 #include <algorithm> 00030 #include <set> 00031 #include "llvm/Target/TargetSchedInfo.h" 00032 #include "../SparcV9Internals.h" 00033 #include <iostream> 00034 using namespace llvm; 00035 00036 //MSchedGraphSBNode constructor 00037 MSchedGraphSBNode::MSchedGraphSBNode(const MachineInstr* inst, 00038 MSchedGraphSB *graph, unsigned idx, 00039 unsigned late, bool isBranch) 00040 : Inst(inst), Parent(graph), index(idx), latency(late), 00041 isBranchInstr(isBranch) { 00042 00043 //Add to the graph 00044 graph->addNode(inst, this); 00045 } 00046 00047 //MSchedGraphSBNode constructor 00048 MSchedGraphSBNode::MSchedGraphSBNode(const MachineInstr* inst, 00049 std::vector<const MachineInstr*> &other, 00050 MSchedGraphSB *graph, unsigned idx, 00051 unsigned late, bool isPNode) 00052 : Inst(inst), otherInstrs(other), Parent(graph), index(idx), latency(late), isPredicateNode(isPNode) { 00053 00054 00055 isBranchInstr = false; 00056 00057 //Add to the graph 00058 graph->addNode(inst, this); 00059 } 00060 00061 //MSchedGraphSBNode copy constructor 00062 MSchedGraphSBNode::MSchedGraphSBNode(const MSchedGraphSBNode &N) 00063 : Predecessors(N.Predecessors), Successors(N.Successors) { 00064 00065 Inst = N.Inst; 00066 Parent = N.Parent; 00067 index = N.index; 00068 latency = N.latency; 00069 isBranchInstr = N.isBranchInstr; 00070 otherInstrs = N.otherInstrs; 00071 } 00072 00073 //Print the node (instruction and latency) 00074 void MSchedGraphSBNode::print(std::ostream &os) const { 00075 if(!isPredicate()) 00076 os << "MSchedGraphSBNode: Inst=" << *Inst << ", latency= " << latency << "\n"; 00077 else 00078 os << "Pred Node\n"; 00079 } 00080 00081 00082 //Get the edge from a predecessor to this node 00083 MSchedGraphSBEdge MSchedGraphSBNode::getInEdge(MSchedGraphSBNode *pred) { 00084 //Loop over all the successors of our predecessor 00085 //return the edge the corresponds to this in edge 00086 for (MSchedGraphSBNode::succ_iterator I = pred->succ_begin(), 00087 E = pred->succ_end(); I != E; ++I) { 00088 if (*I == this) 00089 return I.getEdge(); 00090 } 00091 assert(0 && "Should have found edge between this node and its predecessor!"); 00092 abort(); 00093 } 00094 00095 //Get the iteration difference for the edge from this node to its successor 00096 unsigned MSchedGraphSBNode::getIteDiff(MSchedGraphSBNode *succ) { 00097 for(std::vector<MSchedGraphSBEdge>::iterator I = Successors.begin(), 00098 E = Successors.end(); 00099 I != E; ++I) { 00100 if(I->getDest() == succ) 00101 return I->getIteDiff(); 00102 } 00103 return 0; 00104 } 00105 00106 //Get the index into the vector of edges for the edge from pred to this node 00107 unsigned MSchedGraphSBNode::getInEdgeNum(MSchedGraphSBNode *pred) { 00108 //Loop over all the successors of our predecessor 00109 //return the edge the corresponds to this in edge 00110 int count = 0; 00111 for(MSchedGraphSBNode::succ_iterator I = pred->succ_begin(), 00112 E = pred->succ_end(); 00113 I != E; ++I) { 00114 if(*I == this) 00115 return count; 00116 count++; 00117 } 00118 assert(0 && "Should have found edge between this node and its predecessor!"); 00119 abort(); 00120 } 00121 00122 //Determine if succ is a successor of this node 00123 bool MSchedGraphSBNode::isSuccessor(MSchedGraphSBNode *succ) { 00124 for(succ_iterator I = succ_begin(), E = succ_end(); I != E; ++I) 00125 if(*I == succ) 00126 return true; 00127 return false; 00128 } 00129 00130 //Dtermine if pred is a predecessor of this node 00131 bool MSchedGraphSBNode::isPredecessor(MSchedGraphSBNode *pred) { 00132 if(std::find( Predecessors.begin(), Predecessors.end(), 00133 pred) != Predecessors.end()) 00134 return true; 00135 else 00136 return false; 00137 } 00138 00139 //Add a node to the graph 00140 void MSchedGraphSB::addNode(const MachineInstr* MI, 00141 MSchedGraphSBNode *node) { 00142 00143 //Make sure node does not already exist 00144 assert(GraphMap.find(MI) == GraphMap.end() 00145 && "New MSchedGraphSBNode already exists for this instruction"); 00146 00147 GraphMap[MI] = node; 00148 } 00149 00150 //Delete a node to the graph 00151 void MSchedGraphSB::deleteNode(MSchedGraphSBNode *node) { 00152 00153 //Delete the edge to this node from all predecessors 00154 while(node->pred_size() > 0) { 00155 //DEBUG(std::cerr << "Delete edge from: " << **P << " to " << *node << "\n"); 00156 MSchedGraphSBNode *pred = *(node->pred_begin()); 00157 pred->deleteSuccessor(node); 00158 } 00159 00160 //Remove this node from the graph 00161 GraphMap.erase(node->getInst()); 00162 00163 } 00164 00165 00166 //Create a graph for a machine block. The ignoreInstrs map is so that 00167 //we ignore instructions associated to the index variable since this 00168 //is a special case in Modulo Scheduling. We only want to deal with 00169 //the body of the loop. 00170 MSchedGraphSB::MSchedGraphSB(std::vector<const MachineBasicBlock*> &bbs, 00171 const TargetMachine &targ, 00172 std::map<const MachineInstr*, unsigned> &ignoreInstrs, 00173 DependenceAnalyzer &DA, 00174 std::map<MachineInstr*, Instruction*> &machineTollvm) 00175 : BBs(bbs), Target(targ) { 00176 00177 //Make sure there is at least one BB and it is not null, 00178 assert(((bbs.size() >= 1) && bbs[1] != NULL) && "Basic Block is null"); 00179 00180 std::map<MSchedGraphSBNode*, std::set<MachineInstr*> > liveOutsideTrace; 00181 std::set<const BasicBlock*> llvmBBs; 00182 00183 for(std::vector<const MachineBasicBlock*>::iterator MBB = bbs.begin(), ME = bbs.end()-1; 00184 MBB != ME; ++MBB) 00185 llvmBBs.insert((*MBB)->getBasicBlock()); 00186 00187 //create predicate nodes 00188 DEBUG(std::cerr << "Create predicate nodes\n"); 00189 for(std::vector<const MachineBasicBlock*>::iterator MBB = bbs.begin(), ME = bbs.end()-1; 00190 MBB != ME; ++MBB) { 00191 //Get LLVM basic block 00192 BasicBlock *BB = (BasicBlock*) (*MBB)->getBasicBlock(); 00193 00194 //Get Terminator 00195 BranchInst *b = dyn_cast<BranchInst>(BB->getTerminator()); 00196 00197 std::vector<const MachineInstr*> otherInstrs; 00198 MachineInstr *instr = 0; 00199 00200 //Get the condition for the branch (we already checked if it was conditional) 00201 if(b->isConditional()) { 00202 00203 Value *cond = b->getCondition(); 00204 00205 DEBUG(std::cerr << "Condition: " << *cond << "\n"); 00206 00207 assert(cond && "Condition must not be null!"); 00208 00209 if(Instruction *I = dyn_cast<Instruction>(cond)) { 00210 MachineCodeForInstruction & tempMvec = MachineCodeForInstruction::get(I); 00211 if(tempMvec.size() > 0) { 00212 DEBUG(std::cerr << *(tempMvec[tempMvec.size()-1]) << "\n");; 00213 instr = (MachineInstr*) tempMvec[tempMvec.size()-1]; 00214 } 00215 } 00216 } 00217 00218 //Get Machine target information for calculating latency 00219 const TargetInstrInfo *MTI = Target.getInstrInfo(); 00220 00221 MachineCodeForInstruction & tempMvec = MachineCodeForInstruction::get(b); 00222 int offset = tempMvec.size(); 00223 for (unsigned j = 0; j < tempMvec.size(); j++) { 00224 MachineInstr *mi = tempMvec[j]; 00225 if(MTI->isNop(mi->getOpcode())) 00226 continue; 00227 00228 if(!instr) { 00229 instr = mi; 00230 DEBUG(std::cerr << "No Cond MI: " << *mi << "\n"); 00231 } 00232 else { 00233 DEBUG(std::cerr << *mi << "\n");; 00234 otherInstrs.push_back(mi); 00235 } 00236 } 00237 00238 //Node is created and added to the graph automatically 00239 MSchedGraphSBNode *node = new MSchedGraphSBNode(instr, otherInstrs, this, (*MBB)->size()-offset-1, 3, true); 00240 00241 DEBUG(std::cerr << "Created Node: " << *node << "\n"); 00242 00243 //Now loop over all instructions and see if their def is live outside the trace 00244 MachineBasicBlock *mb = (MachineBasicBlock*) *MBB; 00245 for(MachineBasicBlock::iterator I = mb->begin(), E = mb->end(); I != E; ++I) { 00246 MachineInstr *instr = I; 00247 if(MTI->isNop(instr->getOpcode()) || MTI->isBranch(instr->getOpcode())) 00248 continue; 00249 if(node->getInst() == instr) 00250 continue; 00251 00252 for(unsigned i=0; i < instr->getNumOperands(); ++i) { 00253 MachineOperand &mOp = instr->getOperand(i); 00254 if(mOp.isDef() && mOp.getType() == MachineOperand::MO_VirtualRegister) { 00255 Value *val = mOp.getVRegValue(); 00256 //Check if there is a use not in the trace 00257 for(Value::use_iterator V = val->use_begin(), VE = val->use_end(); V != VE; ++V) { 00258 if (Instruction *Inst = dyn_cast<Instruction>(*V)) { 00259 if(llvmBBs.count(Inst->getParent())) 00260 liveOutsideTrace[node].insert(instr); 00261 } 00262 } 00263 } 00264 } 00265 } 00266 00267 00268 } 00269 00270 //Create nodes and edges for this BB 00271 buildNodesAndEdges(ignoreInstrs, DA, machineTollvm, liveOutsideTrace); 00272 00273 } 00274 00275 00276 //Copies the graph and keeps a map from old to new nodes 00277 MSchedGraphSB::MSchedGraphSB(const MSchedGraphSB &G, 00278 std::map<MSchedGraphSBNode*, MSchedGraphSBNode*> &newNodes) 00279 : Target(G.Target) { 00280 00281 BBs = G.BBs; 00282 00283 std::map<MSchedGraphSBNode*, MSchedGraphSBNode*> oldToNew; 00284 //Copy all nodes 00285 for(MSchedGraphSB::const_iterator N = G.GraphMap.begin(), 00286 NE = G.GraphMap.end(); N != NE; ++N) { 00287 00288 MSchedGraphSBNode *newNode = new MSchedGraphSBNode(*(N->second)); 00289 oldToNew[&*(N->second)] = newNode; 00290 newNodes[newNode] = &*(N->second); 00291 GraphMap[&*(N->first)] = newNode; 00292 } 00293 00294 //Loop over nodes and update edges to point to new nodes 00295 for(MSchedGraphSB::iterator N = GraphMap.begin(), NE = GraphMap.end(); 00296 N != NE; ++N) { 00297 00298 //Get the node we are dealing with 00299 MSchedGraphSBNode *node = &*(N->second); 00300 00301 node->setParent(this); 00302 00303 //Loop over nodes successors and predecessors and update to the new nodes 00304 for(unsigned i = 0; i < node->pred_size(); ++i) { 00305 node->setPredecessor(i, oldToNew[node->getPredecessor(i)]); 00306 } 00307 00308 for(unsigned i = 0; i < node->succ_size(); ++i) { 00309 MSchedGraphSBEdge *edge = node->getSuccessor(i); 00310 MSchedGraphSBNode *oldDest = edge->getDest(); 00311 edge->setDest(oldToNew[oldDest]); 00312 } 00313 } 00314 } 00315 00316 //Deconstructor, deletes all nodes in the graph 00317 MSchedGraphSB::~MSchedGraphSB () { 00318 for(MSchedGraphSB::iterator I = GraphMap.begin(), E = GraphMap.end(); 00319 I != E; ++I) 00320 delete I->second; 00321 } 00322 00323 //Print out graph 00324 void MSchedGraphSB::print(std::ostream &os) const { 00325 for(MSchedGraphSB::const_iterator N = GraphMap.begin(), NE = GraphMap.end(); 00326 N != NE; ++N) { 00327 00328 //Get the node we are dealing with 00329 MSchedGraphSBNode *node = &*(N->second); 00330 00331 os << "Node Start\n"; 00332 node->print(os); 00333 os << "Successors:\n"; 00334 //print successors 00335 for(unsigned i = 0; i < node->succ_size(); ++i) { 00336 MSchedGraphSBEdge *edge = node->getSuccessor(i); 00337 MSchedGraphSBNode *oldDest = edge->getDest(); 00338 oldDest->print(os); 00339 } 00340 os << "Node End\n"; 00341 } 00342 } 00343 00344 //Calculate total delay 00345 int MSchedGraphSB::totalDelay() { 00346 int sum = 0; 00347 00348 for(MSchedGraphSB::const_iterator N = GraphMap.begin(), NE = GraphMap.end(); 00349 N != NE; ++N) { 00350 00351 //Get the node we are dealing with 00352 MSchedGraphSBNode *node = &*(N->second); 00353 sum += node->getLatency(); 00354 } 00355 return sum; 00356 } 00357 00358 bool MSchedGraphSB::instrCauseException(MachineOpCode opCode) { 00359 //Check for integer divide 00360 if(opCode == V9::SDIVXr || opCode == V9::SDIVXi 00361 || opCode == V9::UDIVXr || opCode == V9::UDIVXi) 00362 return true; 00363 00364 //Check for loads or stores 00365 const TargetInstrInfo *MTI = Target.getInstrInfo(); 00366 //if( MTI->isLoad(opCode) || 00367 if(MTI->isStore(opCode)) 00368 return true; 00369 00370 //Check for any floating point operation 00371 const TargetSchedInfo *msi = Target.getSchedInfo(); 00372 InstrSchedClass sc = msi->getSchedClass(opCode); 00373 00374 //FIXME: Should check for floating point instructions! 00375 //if(sc == SPARC_FGA || sc == SPARC_FGM) 00376 //return true; 00377 00378 return false; 00379 } 00380 00381 00382 //Add edges between the nodes 00383 void MSchedGraphSB::buildNodesAndEdges(std::map<const MachineInstr*, unsigned> &ignoreInstrs, 00384 DependenceAnalyzer &DA, 00385 std::map<MachineInstr*, Instruction*> &machineTollvm, 00386 std::map<MSchedGraphSBNode*, std::set<MachineInstr*> > &liveOutsideTrace) { 00387 00388 00389 //Get Machine target information for calculating latency 00390 const TargetInstrInfo *MTI = Target.getInstrInfo(); 00391 00392 std::vector<MSchedGraphSBNode*> memInstructions; 00393 std::map<int, std::vector<OpIndexNodePair> > regNumtoNodeMap; 00394 std::map<const Value*, std::vector<OpIndexNodePair> > valuetoNodeMap; 00395 00396 //Save PHI instructions to deal with later 00397 std::vector<const MachineInstr*> phiInstrs; 00398 unsigned index = 0; 00399 00400 MSchedGraphSBNode *lastPred = 0; 00401 00402 00403 for(std::vector<const MachineBasicBlock*>::iterator B = BBs.begin(), 00404 BE = BBs.end(); B != BE; ++B) { 00405 00406 const MachineBasicBlock *BB = *B; 00407 00408 00409 //Loop over instructions in MBB and add nodes and edges 00410 for (MachineBasicBlock::const_iterator MI = BB->begin(), e = BB->end(); 00411 MI != e; ++MI) { 00412 00413 //Ignore indvar instructions 00414 if(ignoreInstrs.count(MI)) { 00415 ++index; 00416 continue; 00417 } 00418 00419 //Get each instruction of machine basic block, get the delay 00420 //using the op code, create a new node for it, and add to the 00421 //graph. 00422 00423 MachineOpCode opCode = MI->getOpcode(); 00424 int delay; 00425 00426 //Get delay 00427 delay = MTI->maxLatency(opCode); 00428 00429 //Create new node for this machine instruction and add to the graph. 00430 //Create only if not a nop 00431 if(MTI->isNop(opCode)) 00432 continue; 00433 00434 //Sparc BE does not use PHI opcode, so assert on this case 00435 assert(opCode != TargetInstrInfo::PHI && "Did not expect PHI opcode"); 00436 00437 bool isBranch = false; 00438 00439 //Skip branches 00440 if(MTI->isBranch(opCode)) 00441 continue; 00442 00443 //Node is created and added to the graph automatically 00444 MSchedGraphSBNode *node = 0; 00445 if(!GraphMap.count(MI)){ 00446 node = new MSchedGraphSBNode(MI, this, index, delay); 00447 DEBUG(std::cerr << "Created Node: " << *node << "\n"); 00448 } 00449 else { 00450 node = GraphMap[MI]; 00451 if(node->isPredicate()) { 00452 //Create edge between this node and last pred, then switch to new pred 00453 if(lastPred) { 00454 lastPred->addOutEdge(node, MSchedGraphSBEdge::PredDep, 00455 MSchedGraphSBEdge::NonDataDep, 0); 00456 00457 if(liveOutsideTrace.count(lastPred)) { 00458 for(std::set<MachineInstr*>::iterator L = liveOutsideTrace[lastPred].begin(), LE = liveOutsideTrace[lastPred].end(); L != LE; ++L) 00459 lastPred->addOutEdge(GraphMap[*L], MSchedGraphSBEdge::PredDep, 00460 MSchedGraphSBEdge::NonDataDep, 1); 00461 } 00462 00463 } 00464 00465 lastPred = node; 00466 } 00467 } 00468 00469 //Add dependencies to instructions that cause exceptions 00470 if(lastPred) 00471 lastPred->print(std::cerr); 00472 00473 if(!node->isPredicate() && instrCauseException(opCode)) { 00474 if(lastPred) { 00475 lastPred->addOutEdge(node, MSchedGraphSBEdge::PredDep, 00476 MSchedGraphSBEdge::NonDataDep, 0); 00477 } 00478 } 00479 00480 00481 //Check OpCode to keep track of memory operations to add memory 00482 //dependencies later. 00483 if(MTI->isLoad(opCode) || MTI->isStore(opCode)) 00484 memInstructions.push_back(node); 00485 00486 //Loop over all operands, and put them into the register number to 00487 //graph node map for determining dependencies 00488 //If an operands is a use/def, we have an anti dependence to itself 00489 for(unsigned i=0; i < MI->getNumOperands(); ++i) { 00490 //Get Operand 00491 const MachineOperand &mOp = MI->getOperand(i); 00492 00493 //Check if it has an allocated register 00494 if(mOp.hasAllocatedReg()) { 00495 int regNum = mOp.getReg(); 00496 00497 if(regNum != SparcV9::g0) { 00498 //Put into our map 00499 regNumtoNodeMap[regNum].push_back(std::make_pair(i, node)); 00500 } 00501 continue; 00502 } 00503 00504 00505 //Add virtual registers dependencies 00506 //Check if any exist in the value map already and create dependencies 00507 //between them. 00508 if(mOp.getType() == MachineOperand::MO_VirtualRegister 00509 || mOp.getType() == MachineOperand::MO_CCRegister) { 00510 00511 //Make sure virtual register value is not null 00512 assert((mOp.getVRegValue() != NULL) && "Null value is defined"); 00513 00514 //Check if this is a read operation in a phi node, if so DO NOT PROCESS 00515 if(mOp.isUse() && (opCode == TargetInstrInfo::PHI)) { 00516 DEBUG(std::cerr << "Read Operation in a PHI node\n"); 00517 continue; 00518 } 00519 00520 if (const Value* srcI = mOp.getVRegValue()) { 00521 00522 //Find value in the map 00523 std::map<const Value*, std::vector<OpIndexNodePair> >::iterator V 00524 = valuetoNodeMap.find(srcI); 00525 00526 //If there is something in the map already, add edges from 00527 //those instructions 00528 //to this one we are processing 00529 if(V != valuetoNodeMap.end()) { 00530 addValueEdges(V->second, node, mOp.isUse(), mOp.isDef(), phiInstrs); 00531 00532 //Add to value map 00533 V->second.push_back(std::make_pair(i,node)); 00534 } 00535 //Otherwise put it in the map 00536 else 00537 //Put into value map 00538 valuetoNodeMap[mOp.getVRegValue()].push_back(std::make_pair(i, node)); 00539 } 00540 } 00541 } 00542 ++index; 00543 } 00544 00545 //Loop over LLVM BB, examine phi instructions, and add them to our 00546 //phiInstr list to process 00547 const BasicBlock *llvm_bb = BB->getBasicBlock(); 00548 for(BasicBlock::const_iterator I = llvm_bb->begin(), E = llvm_bb->end(); 00549 I != E; ++I) { 00550 if(const PHINode *PN = dyn_cast<PHINode>(I)) { 00551 MachineCodeForInstruction & tempMvec = MachineCodeForInstruction::get(PN); 00552 for (unsigned j = 0; j < tempMvec.size(); j++) { 00553 if(!ignoreInstrs.count(tempMvec[j])) { 00554 DEBUG(std::cerr << "Inserting phi instr into map: " << *tempMvec[j] << "\n"); 00555 phiInstrs.push_back((MachineInstr*) tempMvec[j]); 00556 } 00557 } 00558 } 00559 00560 } 00561 00562 addMemEdges(memInstructions, DA, machineTollvm); 00563 addMachRegEdges(regNumtoNodeMap); 00564 00565 //Finally deal with PHI Nodes and Value* 00566 for(std::vector<const MachineInstr*>::iterator I = phiInstrs.begin(), 00567 E = phiInstrs.end(); I != E; ++I) { 00568 00569 //Get Node for this instruction 00570 std::map<const MachineInstr*, MSchedGraphSBNode*>::iterator X; 00571 X = find(*I); 00572 00573 if(X == GraphMap.end()) 00574 continue; 00575 00576 MSchedGraphSBNode *node = X->second; 00577 00578 DEBUG(std::cerr << "Adding ite diff edges for node: " << *node << "\n"); 00579 00580 //Loop over operands for this instruction and add value edges 00581 for(unsigned i=0; i < (*I)->getNumOperands(); ++i) { 00582 //Get Operand 00583 const MachineOperand &mOp = (*I)->getOperand(i); 00584 if((mOp.getType() == MachineOperand::MO_VirtualRegister 00585 || mOp.getType() == MachineOperand::MO_CCRegister) && mOp.isUse()) { 00586 00587 //find the value in the map 00588 if (const Value* srcI = mOp.getVRegValue()) { 00589 00590 //Find value in the map 00591 std::map<const Value*, std::vector<OpIndexNodePair> >::iterator V 00592 = valuetoNodeMap.find(srcI); 00593 00594 //If there is something in the map already, add edges from 00595 //those instructions 00596 //to this one we are processing 00597 if(V != valuetoNodeMap.end()) { 00598 addValueEdges(V->second, node, mOp.isUse(), mOp.isDef(), 00599 phiInstrs, 1); 00600 } 00601 } 00602 } 00603 } 00604 } 00605 } 00606 } 00607 //Add dependencies for Value*s 00608 void MSchedGraphSB::addValueEdges(std::vector<OpIndexNodePair> &NodesInMap, 00609 MSchedGraphSBNode *destNode, bool nodeIsUse, 00610 bool nodeIsDef, std::vector<const MachineInstr*> &phiInstrs, int diff) { 00611 00612 for(std::vector<OpIndexNodePair>::iterator I = NodesInMap.begin(), 00613 E = NodesInMap.end(); I != E; ++I) { 00614 00615 //Get node in vectors machine operand that is the same value as node 00616 MSchedGraphSBNode *srcNode = I->second; 00617 MachineOperand mOp = srcNode->getInst()->getOperand(I->first); 00618 00619 if(diff > 0) 00620 if(std::find(phiInstrs.begin(), phiInstrs.end(), srcNode->getInst()) == phiInstrs.end()) 00621 continue; 00622 00623 //Node is a Def, so add output dep. 00624 if(nodeIsDef) { 00625 if(mOp.isUse()) { 00626 DEBUG(std::cerr << "Edge from " << *srcNode << " to " << *destNode << " (itediff=" << diff << ", type=anti)\n"); 00627 srcNode->addOutEdge(destNode, MSchedGraphSBEdge::ValueDep, 00628 MSchedGraphSBEdge::AntiDep, diff); 00629 } 00630 if(mOp.isDef()) { 00631 DEBUG(std::cerr << "Edge from " << *srcNode << " to " << *destNode << " (itediff=" << diff << ", type=output)\n"); 00632 srcNode->addOutEdge(destNode, MSchedGraphSBEdge::ValueDep, 00633 MSchedGraphSBEdge::OutputDep, diff); 00634 } 00635 } 00636 if(nodeIsUse) { 00637 if(mOp.isDef()) { 00638 DEBUG(std::cerr << "Edge from " << *srcNode << " to " << *destNode << " (itediff=" << diff << ", type=true)\n"); 00639 srcNode->addOutEdge(destNode, MSchedGraphSBEdge::ValueDep, 00640 MSchedGraphSBEdge::TrueDep, diff); 00641 } 00642 } 00643 } 00644 } 00645 00646 //Add dependencies for machine registers across iterations 00647 void MSchedGraphSB::addMachRegEdges(std::map<int, std::vector<OpIndexNodePair> >& regNumtoNodeMap) { 00648 //Loop over all machine registers in the map, and add dependencies 00649 //between the instructions that use it 00650 typedef std::map<int, std::vector<OpIndexNodePair> > regNodeMap; 00651 for(regNodeMap::iterator I = regNumtoNodeMap.begin(); 00652 I != regNumtoNodeMap.end(); ++I) { 00653 //Get the register number 00654 int regNum = (*I).first; 00655 00656 //Get Vector of nodes that use this register 00657 std::vector<OpIndexNodePair> Nodes = (*I).second; 00658 00659 //Loop over nodes and determine the dependence between the other 00660 //nodes in the vector 00661 for(unsigned i =0; i < Nodes.size(); ++i) { 00662 00663 //Get src node operator index that uses this machine register 00664 int srcOpIndex = Nodes[i].first; 00665 00666 //Get the actual src Node 00667 MSchedGraphSBNode *srcNode = Nodes[i].second; 00668 00669 //Get Operand 00670 const MachineOperand &srcMOp = srcNode->getInst()->getOperand(srcOpIndex); 00671 00672 bool srcIsUseandDef = srcMOp.isDef() && srcMOp.isUse(); 00673 bool srcIsUse = srcMOp.isUse() && !srcMOp.isDef(); 00674 00675 00676 //Look at all instructions after this in execution order 00677 for(unsigned j=i+1; j < Nodes.size(); ++j) { 00678 00679 //Sink node is a write 00680 if(Nodes[j].second->getInst()->getOperand(Nodes[j].first).isDef()) { 00681 //Src only uses the register (read) 00682 if(srcIsUse) 00683 srcNode->addOutEdge(Nodes[j].second, 00684 MSchedGraphSBEdge::MachineRegister, 00685 MSchedGraphSBEdge::AntiDep); 00686 00687 else if(srcIsUseandDef) { 00688 srcNode->addOutEdge(Nodes[j].second, 00689 MSchedGraphSBEdge::MachineRegister, 00690 MSchedGraphSBEdge::AntiDep); 00691 00692 srcNode->addOutEdge(Nodes[j].second, 00693 MSchedGraphSBEdge::MachineRegister, 00694 MSchedGraphSBEdge::OutputDep); 00695 } 00696 else 00697 srcNode->addOutEdge(Nodes[j].second, 00698 MSchedGraphSBEdge::MachineRegister, 00699 MSchedGraphSBEdge::OutputDep); 00700 } 00701 //Dest node is a read 00702 else { 00703 if(!srcIsUse || srcIsUseandDef) 00704 srcNode->addOutEdge(Nodes[j].second, 00705 MSchedGraphSBEdge::MachineRegister, 00706 MSchedGraphSBEdge::TrueDep); 00707 } 00708 00709 } 00710 00711 //Look at all the instructions before this one since machine registers 00712 //could live across iterations. 00713 for(unsigned j = 0; j < i; ++j) { 00714 //Sink node is a write 00715 if(Nodes[j].second->getInst()->getOperand(Nodes[j].first).isDef()) { 00716 //Src only uses the register (read) 00717 if(srcIsUse) 00718 srcNode->addOutEdge(Nodes[j].second, 00719 MSchedGraphSBEdge::MachineRegister, 00720 MSchedGraphSBEdge::AntiDep, 1); 00721 else if(srcIsUseandDef) { 00722 srcNode->addOutEdge(Nodes[j].second, 00723 MSchedGraphSBEdge::MachineRegister, 00724 MSchedGraphSBEdge::AntiDep, 1); 00725 00726 srcNode->addOutEdge(Nodes[j].second, 00727 MSchedGraphSBEdge::MachineRegister, 00728 MSchedGraphSBEdge::OutputDep, 1); 00729 } 00730 else 00731 srcNode->addOutEdge(Nodes[j].second, 00732 MSchedGraphSBEdge::MachineRegister, 00733 MSchedGraphSBEdge::OutputDep, 1); 00734 } 00735 //Dest node is a read 00736 else { 00737 if(!srcIsUse || srcIsUseandDef) 00738 srcNode->addOutEdge(Nodes[j].second, 00739 MSchedGraphSBEdge::MachineRegister, 00740 MSchedGraphSBEdge::TrueDep,1 ); 00741 } 00742 00743 00744 } 00745 00746 } 00747 00748 } 00749 00750 } 00751 00752 //Add edges between all loads and stores 00753 //Can be less strict with alias analysis and data dependence analysis. 00754 void MSchedGraphSB::addMemEdges(const std::vector<MSchedGraphSBNode*>& memInst, 00755 DependenceAnalyzer &DA, 00756 std::map<MachineInstr*, Instruction*> &machineTollvm) { 00757 00758 //Get Target machine instruction info 00759 const TargetInstrInfo *TMI = Target.getInstrInfo(); 00760 00761 //Loop over all memory instructions in the vector 00762 //Knowing that they are in execution, add true, anti, and output dependencies 00763 for (unsigned srcIndex = 0; srcIndex < memInst.size(); ++srcIndex) { 00764 00765 MachineInstr *srcInst = (MachineInstr*) memInst[srcIndex]->getInst(); 00766 00767 //Get the machine opCode to determine type of memory instruction 00768 MachineOpCode srcNodeOpCode = srcInst->getOpcode(); 00769 00770 //All instructions after this one in execution order have an 00771 //iteration delay of 0 00772 for(unsigned destIndex = 0; destIndex < memInst.size(); ++destIndex) { 00773 00774 //No self loops 00775 if(destIndex == srcIndex) 00776 continue; 00777 00778 MachineInstr *destInst = (MachineInstr*) memInst[destIndex]->getInst(); 00779 00780 DEBUG(std::cerr << "MInst1: " << *srcInst << "\n"); 00781 DEBUG(std::cerr << "MInst2: " << *destInst << "\n"); 00782 00783 //Assuming instructions without corresponding llvm instructions 00784 //are from constant pools. 00785 if (!machineTollvm.count(srcInst) || !machineTollvm.count(destInst)) 00786 continue; 00787 00788 bool useDepAnalyzer = true; 00789 00790 //Some machine loads and stores are generated by casts, so be 00791 //conservative and always add deps 00792 Instruction *srcLLVM = machineTollvm[srcInst]; 00793 Instruction *destLLVM = machineTollvm[destInst]; 00794 if(!isa<LoadInst>(srcLLVM) 00795 && !isa<StoreInst>(srcLLVM)) { 00796 if(isa<BinaryOperator>(srcLLVM)) { 00797 if(isa<ConstantFP>(srcLLVM->getOperand(0)) || isa<ConstantFP>(srcLLVM->getOperand(1))) 00798 continue; 00799 } 00800 useDepAnalyzer = false; 00801 } 00802 if(!isa<LoadInst>(destLLVM) 00803 && !isa<StoreInst>(destLLVM)) { 00804 if(isa<BinaryOperator>(destLLVM)) { 00805 if(isa<ConstantFP>(destLLVM->getOperand(0)) || isa<ConstantFP>(destLLVM->getOperand(1))) 00806 continue; 00807 } 00808 useDepAnalyzer = false; 00809 } 00810 00811 //Use dep analysis when we have corresponding llvm loads/stores 00812 if(useDepAnalyzer) { 00813 bool srcBeforeDest = true; 00814 if(destIndex < srcIndex) 00815 srcBeforeDest = false; 00816 00817 DependenceResult dr = DA.getDependenceInfo(machineTollvm[srcInst], 00818 machineTollvm[destInst], 00819 srcBeforeDest); 00820 00821 for(std::vector<Dependence>::iterator d = dr.dependences.begin(), 00822 de = dr.dependences.end(); d != de; ++d) { 00823 //Add edge from load to store 00824 memInst[srcIndex]->addOutEdge(memInst[destIndex], 00825 MSchedGraphSBEdge::MemoryDep, 00826 d->getDepType(), d->getIteDiff()); 00827 00828 } 00829 } 00830 //Otherwise, we can not do any further analysis and must make a dependence 00831 else { 00832 00833 //Get the machine opCode to determine type of memory instruction 00834 MachineOpCode destNodeOpCode = destInst->getOpcode(); 00835 00836 //Get the Value* that we are reading from the load, always the first op 00837 const MachineOperand &mOp = srcInst->getOperand(0); 00838 const MachineOperand &mOp2 = destInst->getOperand(0); 00839 00840 if(mOp.hasAllocatedReg()) 00841 if(mOp.getReg() == SparcV9::g0) 00842 continue; 00843 if(mOp2.hasAllocatedReg()) 00844 if(mOp2.getReg() == SparcV9::g0) 00845 continue; 00846 00847 DEBUG(std::cerr << "Adding dependence for machine instructions\n"); 00848 //Load-Store deps 00849 if(TMI->isLoad(srcNodeOpCode)) { 00850 00851 if(TMI->isStore(destNodeOpCode)) 00852 memInst[srcIndex]->addOutEdge(memInst[destIndex], 00853 MSchedGraphSBEdge::MemoryDep, 00854 MSchedGraphSBEdge::AntiDep, 0); 00855 } 00856 else if(TMI->isStore(srcNodeOpCode)) { 00857 if(TMI->isStore(destNodeOpCode)) 00858 memInst[srcIndex]->addOutEdge(memInst[destIndex], 00859 MSchedGraphSBEdge::MemoryDep, 00860 MSchedGraphSBEdge::OutputDep, 0); 00861 00862 else 00863 memInst[srcIndex]->addOutEdge(memInst[destIndex], 00864 MSchedGraphSBEdge::MemoryDep, 00865 MSchedGraphSBEdge::TrueDep, 0); 00866 } 00867 } 00868 } 00869 } 00870 }