LLVM API Documentation
00001 //===- Dominators.cpp - Dominator Calculation -----------------------------===// 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 // This file implements simple dominator construction algorithms for finding 00011 // forward dominators. Postdominators are available in libanalysis, but are not 00012 // included in libvmcore, because it's not needed. Forward dominators are 00013 // needed to support the Verifier pass. 00014 // 00015 //===----------------------------------------------------------------------===// 00016 00017 #include "llvm/Analysis/Dominators.h" 00018 #include "llvm/Support/CFG.h" 00019 #include "llvm/Assembly/Writer.h" 00020 #include "llvm/ADT/DepthFirstIterator.h" 00021 #include "llvm/ADT/SetOperations.h" 00022 #include <algorithm> 00023 #include <iostream> 00024 using namespace llvm; 00025 00026 //===----------------------------------------------------------------------===// 00027 // ImmediateDominators Implementation 00028 //===----------------------------------------------------------------------===// 00029 // 00030 // Immediate Dominators construction - This pass constructs immediate dominator 00031 // information for a flow-graph based on the algorithm described in this 00032 // document: 00033 // 00034 // A Fast Algorithm for Finding Dominators in a Flowgraph 00035 // T. Lengauer & R. Tarjan, ACM TOPLAS July 1979, pgs 121-141. 00036 // 00037 // This implements both the O(n*ack(n)) and the O(n*log(n)) versions of EVAL and 00038 // LINK, but it turns out that the theoretically slower O(n*log(n)) 00039 // implementation is actually faster than the "efficient" algorithm (even for 00040 // large CFGs) because the constant overheads are substantially smaller. The 00041 // lower-complexity version can be enabled with the following #define: 00042 // 00043 #define BALANCE_IDOM_TREE 0 00044 // 00045 //===----------------------------------------------------------------------===// 00046 00047 static RegisterAnalysis<ImmediateDominators> 00048 C("idom", "Immediate Dominators Construction", true); 00049 00050 unsigned ImmediateDominators::DFSPass(BasicBlock *V, InfoRec &VInfo, 00051 unsigned N) { 00052 VInfo.Semi = ++N; 00053 VInfo.Label = V; 00054 00055 Vertex.push_back(V); // Vertex[n] = V; 00056 //Info[V].Ancestor = 0; // Ancestor[n] = 0 00057 //Child[V] = 0; // Child[v] = 0 00058 VInfo.Size = 1; // Size[v] = 1 00059 00060 for (succ_iterator SI = succ_begin(V), E = succ_end(V); SI != E; ++SI) { 00061 InfoRec &SuccVInfo = Info[*SI]; 00062 if (SuccVInfo.Semi == 0) { 00063 SuccVInfo.Parent = V; 00064 N = DFSPass(*SI, SuccVInfo, N); 00065 } 00066 } 00067 return N; 00068 } 00069 00070 void ImmediateDominators::Compress(BasicBlock *V, InfoRec &VInfo) { 00071 BasicBlock *VAncestor = VInfo.Ancestor; 00072 InfoRec &VAInfo = Info[VAncestor]; 00073 if (VAInfo.Ancestor == 0) 00074 return; 00075 00076 Compress(VAncestor, VAInfo); 00077 00078 BasicBlock *VAncestorLabel = VAInfo.Label; 00079 BasicBlock *VLabel = VInfo.Label; 00080 if (Info[VAncestorLabel].Semi < Info[VLabel].Semi) 00081 VInfo.Label = VAncestorLabel; 00082 00083 VInfo.Ancestor = VAInfo.Ancestor; 00084 } 00085 00086 BasicBlock *ImmediateDominators::Eval(BasicBlock *V) { 00087 InfoRec &VInfo = Info[V]; 00088 #if !BALANCE_IDOM_TREE 00089 // Higher-complexity but faster implementation 00090 if (VInfo.Ancestor == 0) 00091 return V; 00092 Compress(V, VInfo); 00093 return VInfo.Label; 00094 #else 00095 // Lower-complexity but slower implementation 00096 if (VInfo.Ancestor == 0) 00097 return VInfo.Label; 00098 Compress(V, VInfo); 00099 BasicBlock *VLabel = VInfo.Label; 00100 00101 BasicBlock *VAncestorLabel = Info[VInfo.Ancestor].Label; 00102 if (Info[VAncestorLabel].Semi >= Info[VLabel].Semi) 00103 return VLabel; 00104 else 00105 return VAncestorLabel; 00106 #endif 00107 } 00108 00109 void ImmediateDominators::Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo){ 00110 #if !BALANCE_IDOM_TREE 00111 // Higher-complexity but faster implementation 00112 WInfo.Ancestor = V; 00113 #else 00114 // Lower-complexity but slower implementation 00115 BasicBlock *WLabel = WInfo.Label; 00116 unsigned WLabelSemi = Info[WLabel].Semi; 00117 BasicBlock *S = W; 00118 InfoRec *SInfo = &Info[S]; 00119 00120 BasicBlock *SChild = SInfo->Child; 00121 InfoRec *SChildInfo = &Info[SChild]; 00122 00123 while (WLabelSemi < Info[SChildInfo->Label].Semi) { 00124 BasicBlock *SChildChild = SChildInfo->Child; 00125 if (SInfo->Size+Info[SChildChild].Size >= 2*SChildInfo->Size) { 00126 SChildInfo->Ancestor = S; 00127 SInfo->Child = SChild = SChildChild; 00128 SChildInfo = &Info[SChild]; 00129 } else { 00130 SChildInfo->Size = SInfo->Size; 00131 S = SInfo->Ancestor = SChild; 00132 SInfo = SChildInfo; 00133 SChild = SChildChild; 00134 SChildInfo = &Info[SChild]; 00135 } 00136 } 00137 00138 InfoRec &VInfo = Info[V]; 00139 SInfo->Label = WLabel; 00140 00141 assert(V != W && "The optimization here will not work in this case!"); 00142 unsigned WSize = WInfo.Size; 00143 unsigned VSize = (VInfo.Size += WSize); 00144 00145 if (VSize < 2*WSize) 00146 std::swap(S, VInfo.Child); 00147 00148 while (S) { 00149 SInfo = &Info[S]; 00150 SInfo->Ancestor = V; 00151 S = SInfo->Child; 00152 } 00153 #endif 00154 } 00155 00156 00157 00158 bool ImmediateDominators::runOnFunction(Function &F) { 00159 IDoms.clear(); // Reset from the last time we were run... 00160 BasicBlock *Root = &F.getEntryBlock(); 00161 Roots.clear(); 00162 Roots.push_back(Root); 00163 00164 Vertex.push_back(0); 00165 00166 // Step #1: Number blocks in depth-first order and initialize variables used 00167 // in later stages of the algorithm. 00168 unsigned N = 0; 00169 for (unsigned i = 0, e = Roots.size(); i != e; ++i) 00170 N = DFSPass(Roots[i], Info[Roots[i]], 0); 00171 00172 for (unsigned i = N; i >= 2; --i) { 00173 BasicBlock *W = Vertex[i]; 00174 InfoRec &WInfo = Info[W]; 00175 00176 // Step #2: Calculate the semidominators of all vertices 00177 for (pred_iterator PI = pred_begin(W), E = pred_end(W); PI != E; ++PI) 00178 if (Info.count(*PI)) { // Only if this predecessor is reachable! 00179 unsigned SemiU = Info[Eval(*PI)].Semi; 00180 if (SemiU < WInfo.Semi) 00181 WInfo.Semi = SemiU; 00182 } 00183 00184 Info[Vertex[WInfo.Semi]].Bucket.push_back(W); 00185 00186 BasicBlock *WParent = WInfo.Parent; 00187 Link(WParent, W, WInfo); 00188 00189 // Step #3: Implicitly define the immediate dominator of vertices 00190 std::vector<BasicBlock*> &WParentBucket = Info[WParent].Bucket; 00191 while (!WParentBucket.empty()) { 00192 BasicBlock *V = WParentBucket.back(); 00193 WParentBucket.pop_back(); 00194 BasicBlock *U = Eval(V); 00195 IDoms[V] = Info[U].Semi < Info[V].Semi ? U : WParent; 00196 } 00197 } 00198 00199 // Step #4: Explicitly define the immediate dominator of each vertex 00200 for (unsigned i = 2; i <= N; ++i) { 00201 BasicBlock *W = Vertex[i]; 00202 BasicBlock *&WIDom = IDoms[W]; 00203 if (WIDom != Vertex[Info[W].Semi]) 00204 WIDom = IDoms[WIDom]; 00205 } 00206 00207 // Free temporary memory used to construct idom's 00208 Info.clear(); 00209 std::vector<BasicBlock*>().swap(Vertex); 00210 00211 return false; 00212 } 00213 00214 void ImmediateDominatorsBase::print(std::ostream &o, const Module* ) const { 00215 Function *F = getRoots()[0]->getParent(); 00216 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) { 00217 o << " Immediate Dominator For Basic Block:"; 00218 WriteAsOperand(o, I, false); 00219 o << " is:"; 00220 if (BasicBlock *ID = get(I)) 00221 WriteAsOperand(o, ID, false); 00222 else 00223 o << " <<exit node>>"; 00224 o << "\n"; 00225 } 00226 o << "\n"; 00227 } 00228 00229 00230 00231 //===----------------------------------------------------------------------===// 00232 // DominatorSet Implementation 00233 //===----------------------------------------------------------------------===// 00234 00235 static RegisterAnalysis<DominatorSet> 00236 B("domset", "Dominator Set Construction", true); 00237 00238 // dominates - Return true if A dominates B. This performs the special checks 00239 // necessary if A and B are in the same basic block. 00240 // 00241 bool DominatorSetBase::dominates(Instruction *A, Instruction *B) const { 00242 BasicBlock *BBA = A->getParent(), *BBB = B->getParent(); 00243 if (BBA != BBB) return dominates(BBA, BBB); 00244 00245 // Loop through the basic block until we find A or B. 00246 BasicBlock::iterator I = BBA->begin(); 00247 for (; &*I != A && &*I != B; ++I) /*empty*/; 00248 00249 if(!IsPostDominators) { 00250 // A dominates B if it is found first in the basic block. 00251 return &*I == A; 00252 } else { 00253 // A post-dominates B if B is found first in the basic block. 00254 return &*I == B; 00255 } 00256 } 00257 00258 00259 // runOnFunction - This method calculates the forward dominator sets for the 00260 // specified function. 00261 // 00262 bool DominatorSet::runOnFunction(Function &F) { 00263 BasicBlock *Root = &F.getEntryBlock(); 00264 Roots.clear(); 00265 Roots.push_back(Root); 00266 assert(pred_begin(Root) == pred_end(Root) && 00267 "Root node has predecessors in function!"); 00268 00269 ImmediateDominators &ID = getAnalysis<ImmediateDominators>(); 00270 Doms.clear(); 00271 if (Roots.empty()) return false; 00272 00273 // Root nodes only dominate themselves. 00274 for (unsigned i = 0, e = Roots.size(); i != e; ++i) 00275 Doms[Roots[i]].insert(Roots[i]); 00276 00277 // Loop over all of the blocks in the function, calculating dominator sets for 00278 // each function. 00279 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 00280 if (BasicBlock *IDom = ID[I]) { // Get idom if block is reachable 00281 DomSetType &DS = Doms[I]; 00282 assert(DS.empty() && "Domset already filled in for this block?"); 00283 DS.insert(I); // Blocks always dominate themselves 00284 00285 // Insert all dominators into the set... 00286 while (IDom) { 00287 // If we have already computed the dominator sets for our immediate 00288 // dominator, just use it instead of walking all the way up to the root. 00289 DomSetType &IDS = Doms[IDom]; 00290 if (!IDS.empty()) { 00291 DS.insert(IDS.begin(), IDS.end()); 00292 break; 00293 } else { 00294 DS.insert(IDom); 00295 IDom = ID[IDom]; 00296 } 00297 } 00298 } else { 00299 // Ensure that every basic block has at least an empty set of nodes. This 00300 // is important for the case when there is unreachable blocks. 00301 Doms[I]; 00302 } 00303 00304 return false; 00305 } 00306 00307 void DominatorSet::stub() {} 00308 00309 namespace llvm { 00310 static std::ostream &operator<<(std::ostream &o, 00311 const std::set<BasicBlock*> &BBs) { 00312 for (std::set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end(); 00313 I != E; ++I) 00314 if (*I) 00315 WriteAsOperand(o, *I, false); 00316 else 00317 o << " <<exit node>>"; 00318 return o; 00319 } 00320 } 00321 00322 void DominatorSetBase::print(std::ostream &o, const Module* ) const { 00323 for (const_iterator I = begin(), E = end(); I != E; ++I) { 00324 o << " DomSet For BB: "; 00325 if (I->first) 00326 WriteAsOperand(o, I->first, false); 00327 else 00328 o << " <<exit node>>"; 00329 o << " is:\t" << I->second << "\n"; 00330 } 00331 } 00332 00333 //===----------------------------------------------------------------------===// 00334 // DominatorTree Implementation 00335 //===----------------------------------------------------------------------===// 00336 00337 static RegisterAnalysis<DominatorTree> 00338 E("domtree", "Dominator Tree Construction", true); 00339 00340 // DominatorTreeBase::reset - Free all of the tree node memory. 00341 // 00342 void DominatorTreeBase::reset() { 00343 for (NodeMapType::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) 00344 delete I->second; 00345 Nodes.clear(); 00346 RootNode = 0; 00347 } 00348 00349 void DominatorTreeBase::Node::setIDom(Node *NewIDom) { 00350 assert(IDom && "No immediate dominator?"); 00351 if (IDom != NewIDom) { 00352 std::vector<Node*>::iterator I = 00353 std::find(IDom->Children.begin(), IDom->Children.end(), this); 00354 assert(I != IDom->Children.end() && 00355 "Not in immediate dominator children set!"); 00356 // I am no longer your child... 00357 IDom->Children.erase(I); 00358 00359 // Switch to new dominator 00360 IDom = NewIDom; 00361 IDom->Children.push_back(this); 00362 } 00363 } 00364 00365 DominatorTreeBase::Node *DominatorTree::getNodeForBlock(BasicBlock *BB) { 00366 Node *&BBNode = Nodes[BB]; 00367 if (BBNode) return BBNode; 00368 00369 // Haven't calculated this node yet? Get or calculate the node for the 00370 // immediate dominator. 00371 BasicBlock *IDom = getAnalysis<ImmediateDominators>()[BB]; 00372 Node *IDomNode = getNodeForBlock(IDom); 00373 00374 // Add a new tree node for this BasicBlock, and link it as a child of 00375 // IDomNode 00376 return BBNode = IDomNode->addChild(new Node(BB, IDomNode)); 00377 } 00378 00379 void DominatorTree::calculate(const ImmediateDominators &ID) { 00380 assert(Roots.size() == 1 && "DominatorTree should have 1 root block!"); 00381 BasicBlock *Root = Roots[0]; 00382 Nodes[Root] = RootNode = new Node(Root, 0); // Add a node for the root... 00383 00384 Function *F = Root->getParent(); 00385 // Loop over all of the reachable blocks in the function... 00386 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) 00387 if (BasicBlock *ImmDom = ID.get(I)) { // Reachable block. 00388 Node *&BBNode = Nodes[I]; 00389 if (!BBNode) { // Haven't calculated this node yet? 00390 // Get or calculate the node for the immediate dominator 00391 Node *IDomNode = getNodeForBlock(ImmDom); 00392 00393 // Add a new tree node for this BasicBlock, and link it as a child of 00394 // IDomNode 00395 BBNode = IDomNode->addChild(new Node(I, IDomNode)); 00396 } 00397 } 00398 } 00399 00400 static std::ostream &operator<<(std::ostream &o, 00401 const DominatorTreeBase::Node *Node) { 00402 if (Node->getBlock()) 00403 WriteAsOperand(o, Node->getBlock(), false); 00404 else 00405 o << " <<exit node>>"; 00406 return o << "\n"; 00407 } 00408 00409 static void PrintDomTree(const DominatorTreeBase::Node *N, std::ostream &o, 00410 unsigned Lev) { 00411 o << std::string(2*Lev, ' ') << "[" << Lev << "] " << N; 00412 for (DominatorTreeBase::Node::const_iterator I = N->begin(), E = N->end(); 00413 I != E; ++I) 00414 PrintDomTree(*I, o, Lev+1); 00415 } 00416 00417 void DominatorTreeBase::print(std::ostream &o, const Module* ) const { 00418 o << "=============================--------------------------------\n" 00419 << "Inorder Dominator Tree:\n"; 00420 PrintDomTree(getRootNode(), o, 1); 00421 } 00422 00423 00424 //===----------------------------------------------------------------------===// 00425 // DominanceFrontier Implementation 00426 //===----------------------------------------------------------------------===// 00427 00428 static RegisterAnalysis<DominanceFrontier> 00429 G("domfrontier", "Dominance Frontier Construction", true); 00430 00431 const DominanceFrontier::DomSetType & 00432 DominanceFrontier::calculate(const DominatorTree &DT, 00433 const DominatorTree::Node *Node) { 00434 // Loop over CFG successors to calculate DFlocal[Node] 00435 BasicBlock *BB = Node->getBlock(); 00436 DomSetType &S = Frontiers[BB]; // The new set to fill in... 00437 00438 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); 00439 SI != SE; ++SI) { 00440 // Does Node immediately dominate this successor? 00441 if (DT[*SI]->getIDom() != Node) 00442 S.insert(*SI); 00443 } 00444 00445 // At this point, S is DFlocal. Now we union in DFup's of our children... 00446 // Loop through and visit the nodes that Node immediately dominates (Node's 00447 // children in the IDomTree) 00448 // 00449 for (DominatorTree::Node::const_iterator NI = Node->begin(), NE = Node->end(); 00450 NI != NE; ++NI) { 00451 DominatorTree::Node *IDominee = *NI; 00452 const DomSetType &ChildDF = calculate(DT, IDominee); 00453 00454 DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end(); 00455 for (; CDFI != CDFE; ++CDFI) { 00456 if (!Node->properlyDominates(DT[*CDFI])) 00457 S.insert(*CDFI); 00458 } 00459 } 00460 00461 return S; 00462 } 00463 00464 void DominanceFrontierBase::print(std::ostream &o, const Module* ) const { 00465 for (const_iterator I = begin(), E = end(); I != E; ++I) { 00466 o << " DomFrontier for BB"; 00467 if (I->first) 00468 WriteAsOperand(o, I->first, false); 00469 else 00470 o << " <<exit node>>"; 00471 o << " is:\t" << I->second << "\n"; 00472 } 00473 } 00474 00475 //===----------------------------------------------------------------------===// 00476 // ETOccurrence Implementation 00477 //===----------------------------------------------------------------------===// 00478 00479 void ETOccurrence::Splay() { 00480 ETOccurrence *father; 00481 ETOccurrence *grandfather; 00482 int occdepth; 00483 int fatherdepth; 00484 00485 while (Parent) { 00486 occdepth = Depth; 00487 00488 father = Parent; 00489 fatherdepth = Parent->Depth; 00490 grandfather = father->Parent; 00491 00492 // If we have no grandparent, a single zig or zag will do. 00493 if (!grandfather) { 00494 setDepthAdd(fatherdepth); 00495 MinOccurrence = father->MinOccurrence; 00496 Min = father->Min; 00497 00498 // See what we have to rotate 00499 if (father->Left == this) { 00500 // Zig 00501 father->setLeft(Right); 00502 setRight(father); 00503 if (father->Left) 00504 father->Left->setDepthAdd(occdepth); 00505 } else { 00506 // Zag 00507 father->setRight(Left); 00508 setLeft(father); 00509 if (father->Right) 00510 father->Right->setDepthAdd(occdepth); 00511 } 00512 father->setDepth(-occdepth); 00513 Parent = NULL; 00514 00515 father->recomputeMin(); 00516 return; 00517 } 00518 00519 // If we have a grandfather, we need to do some 00520 // combination of zig and zag. 00521 int grandfatherdepth = grandfather->Depth; 00522 00523 setDepthAdd(fatherdepth + grandfatherdepth); 00524 MinOccurrence = grandfather->MinOccurrence; 00525 Min = grandfather->Min; 00526 00527 ETOccurrence *greatgrandfather = grandfather->Parent; 00528 00529 if (grandfather->Left == father) { 00530 if (father->Left == this) { 00531 // Zig zig 00532 grandfather->setLeft(father->Right); 00533 father->setLeft(Right); 00534 setRight(father); 00535 father->setRight(grandfather); 00536 00537 father->setDepth(-occdepth); 00538 00539 if (father->Left) 00540 father->Left->setDepthAdd(occdepth); 00541 00542 grandfather->setDepth(-fatherdepth); 00543 if (grandfather->Left) 00544 grandfather->Left->setDepthAdd(fatherdepth); 00545 } else { 00546 // Zag zig 00547 grandfather->setLeft(Right); 00548 father->setRight(Left); 00549 setLeft(father); 00550 setRight(grandfather); 00551 00552 father->setDepth(-occdepth); 00553 if (father->Right) 00554 father->Right->setDepthAdd(occdepth); 00555 grandfather->setDepth(-occdepth - fatherdepth); 00556 if (grandfather->Left) 00557 grandfather->Left->setDepthAdd(occdepth + fatherdepth); 00558 } 00559 } else { 00560 if (father->Left == this) { 00561 // Zig zag 00562 grandfather->setRight(Left); 00563 father->setLeft(Right); 00564 setLeft(grandfather); 00565 setRight(father); 00566 00567 father->setDepth(-occdepth); 00568 if (father->Left) 00569 father->Left->setDepthAdd(occdepth); 00570 grandfather->setDepth(-occdepth - fatherdepth); 00571 if (grandfather->Right) 00572 grandfather->Right->setDepthAdd(occdepth + fatherdepth); 00573 } else { // Zag Zag 00574 grandfather->setRight(father->Left); 00575 father->setRight(Left); 00576 setLeft(father); 00577 father->setLeft(grandfather); 00578 00579 father->setDepth(-occdepth); 00580 if (father->Right) 00581 father->Right->setDepthAdd(occdepth); 00582 grandfather->setDepth(-fatherdepth); 00583 if (grandfather->Right) 00584 grandfather->Right->setDepthAdd(fatherdepth); 00585 } 00586 } 00587 00588 // Might need one more rotate depending on greatgrandfather. 00589 setParent(greatgrandfather); 00590 if (greatgrandfather) { 00591 if (greatgrandfather->Left == grandfather) 00592 greatgrandfather->Left = this; 00593 else 00594 greatgrandfather->Right = this; 00595 00596 } 00597 grandfather->recomputeMin(); 00598 father->recomputeMin(); 00599 } 00600 } 00601 00602 //===----------------------------------------------------------------------===// 00603 // ETNode implementation 00604 //===----------------------------------------------------------------------===// 00605 00606 void ETNode::Split() { 00607 ETOccurrence *right, *left; 00608 ETOccurrence *rightmost = RightmostOcc; 00609 ETOccurrence *parent; 00610 00611 // Update the occurrence tree first. 00612 RightmostOcc->Splay(); 00613 00614 // Find the leftmost occurrence in the rightmost subtree, then splay 00615 // around it. 00616 for (right = rightmost->Right; right->Left; right = right->Left); 00617 00618 right->Splay(); 00619 00620 // Start splitting 00621 right->Left->Parent = NULL; 00622 parent = ParentOcc; 00623 parent->Splay(); 00624 ParentOcc = NULL; 00625 00626 left = parent->Left; 00627 parent->Right->Parent = NULL; 00628 00629 right->setLeft(left); 00630 00631 right->recomputeMin(); 00632 00633 rightmost->Splay(); 00634 rightmost->Depth = 0; 00635 rightmost->Min = 0; 00636 00637 delete parent; 00638 00639 // Now update *our* tree 00640 00641 if (Father->Son == this) 00642 Father->Son = Right; 00643 00644 if (Father->Son == this) 00645 Father->Son = NULL; 00646 else { 00647 Left->Right = Right; 00648 Right->Left = Left; 00649 } 00650 Left = Right = NULL; 00651 Father = NULL; 00652 } 00653 00654 void ETNode::setFather(ETNode *NewFather) { 00655 ETOccurrence *rightmost; 00656 ETOccurrence *leftpart; 00657 ETOccurrence *NewFatherOcc; 00658 ETOccurrence *temp; 00659 00660 // First update the path in the splay tree 00661 NewFatherOcc = new ETOccurrence(NewFather); 00662 00663 rightmost = NewFather->RightmostOcc; 00664 rightmost->Splay(); 00665 00666 leftpart = rightmost->Left; 00667 00668 temp = RightmostOcc; 00669 temp->Splay(); 00670 00671 NewFatherOcc->setLeft(leftpart); 00672 NewFatherOcc->setRight(temp); 00673 00674 temp->Depth++; 00675 temp->Min++; 00676 NewFatherOcc->recomputeMin(); 00677 00678 rightmost->setLeft(NewFatherOcc); 00679 00680 if (NewFatherOcc->Min + rightmost->Depth < rightmost->Min) { 00681 rightmost->Min = NewFatherOcc->Min + rightmost->Depth; 00682 rightmost->MinOccurrence = NewFatherOcc->MinOccurrence; 00683 } 00684 00685 delete ParentOcc; 00686 ParentOcc = NewFatherOcc; 00687 00688 // Update *our* tree 00689 ETNode *left; 00690 ETNode *right; 00691 00692 Father = NewFather; 00693 right = Father->Son; 00694 00695 if (right) 00696 left = right->Left; 00697 else 00698 left = right = this; 00699 00700 left->Right = this; 00701 right->Left = this; 00702 Left = left; 00703 Right = right; 00704 00705 Father->Son = this; 00706 } 00707 00708 bool ETNode::Below(ETNode *other) { 00709 ETOccurrence *up = other->RightmostOcc; 00710 ETOccurrence *down = RightmostOcc; 00711 00712 if (this == other) 00713 return true; 00714 00715 up->Splay(); 00716 00717 ETOccurrence *left, *right; 00718 left = up->Left; 00719 right = up->Right; 00720 00721 if (!left) 00722 return false; 00723 00724 left->Parent = NULL; 00725 00726 if (right) 00727 right->Parent = NULL; 00728 00729 down->Splay(); 00730 00731 if (left == down || left->Parent != NULL) { 00732 if (right) 00733 right->Parent = up; 00734 up->setLeft(down); 00735 } else { 00736 left->Parent = up; 00737 00738 // If the two occurrences are in different trees, put things 00739 // back the way they were. 00740 if (right && right->Parent != NULL) 00741 up->setRight(down); 00742 else 00743 up->setRight(right); 00744 return false; 00745 } 00746 00747 if (down->Depth <= 0) 00748 return false; 00749 00750 return !down->Right || down->Right->Min + down->Depth >= 0; 00751 } 00752 00753 ETNode *ETNode::NCA(ETNode *other) { 00754 ETOccurrence *occ1 = RightmostOcc; 00755 ETOccurrence *occ2 = other->RightmostOcc; 00756 00757 ETOccurrence *left, *right, *ret; 00758 ETOccurrence *occmin; 00759 int mindepth; 00760 00761 if (this == other) 00762 return this; 00763 00764 occ1->Splay(); 00765 left = occ1->Left; 00766 right = occ1->Right; 00767 00768 if (left) 00769 left->Parent = NULL; 00770 00771 if (right) 00772 right->Parent = NULL; 00773 occ2->Splay(); 00774 00775 if (left == occ2 || (left && left->Parent != NULL)) { 00776 ret = occ2->Right; 00777 00778 occ1->setLeft(occ2); 00779 if (right) 00780 right->Parent = occ1; 00781 } else { 00782 ret = occ2->Left; 00783 00784 occ1->setRight(occ2); 00785 if (left) 00786 left->Parent = occ1; 00787 } 00788 00789 if (occ2->Depth > 0) { 00790 occmin = occ1; 00791 mindepth = occ1->Depth; 00792 } else { 00793 occmin = occ2; 00794 mindepth = occ2->Depth + occ1->Depth; 00795 } 00796 00797 if (ret && ret->Min + occ1->Depth + occ2->Depth < mindepth) 00798 return ret->MinOccurrence->OccFor; 00799 else 00800 return occmin->OccFor; 00801 } 00802 00803 //===----------------------------------------------------------------------===// 00804 // ETForest implementation 00805 //===----------------------------------------------------------------------===// 00806 00807 static RegisterAnalysis<ETForest> 00808 D("etforest", "ET Forest Construction", true); 00809 00810 void ETForestBase::reset() { 00811 for (ETMapType::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) 00812 delete I->second; 00813 Nodes.clear(); 00814 } 00815 00816 void ETForestBase::updateDFSNumbers() 00817 { 00818 int dfsnum = 0; 00819 // Iterate over all nodes in depth first order. 00820 for (unsigned i = 0, e = Roots.size(); i != e; ++i) 00821 for (df_iterator<BasicBlock*> I = df_begin(Roots[i]), 00822 E = df_end(Roots[i]); I != E; ++I) { 00823 BasicBlock *BB = *I; 00824 if (!getNode(BB)->hasFather()) 00825 getNode(BB)->assignDFSNumber(dfsnum); 00826 } 00827 SlowQueries = 0; 00828 DFSInfoValid = true; 00829 } 00830 00831 ETNode *ETForest::getNodeForBlock(BasicBlock *BB) { 00832 ETNode *&BBNode = Nodes[BB]; 00833 if (BBNode) return BBNode; 00834 00835 // Haven't calculated this node yet? Get or calculate the node for the 00836 // immediate dominator. 00837 BasicBlock *IDom = getAnalysis<ImmediateDominators>()[BB]; 00838 00839 // If we are unreachable, we may not have an immediate dominator. 00840 if (!IDom) 00841 return BBNode = new ETNode(BB); 00842 else { 00843 ETNode *IDomNode = getNodeForBlock(IDom); 00844 00845 // Add a new tree node for this BasicBlock, and link it as a child of 00846 // IDomNode 00847 BBNode = new ETNode(BB); 00848 BBNode->setFather(IDomNode); 00849 return BBNode; 00850 } 00851 } 00852 00853 void ETForest::calculate(const ImmediateDominators &ID) { 00854 assert(Roots.size() == 1 && "ETForest should have 1 root block!"); 00855 BasicBlock *Root = Roots[0]; 00856 Nodes[Root] = new ETNode(Root); // Add a node for the root 00857 00858 Function *F = Root->getParent(); 00859 // Loop over all of the reachable blocks in the function... 00860 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) 00861 if (BasicBlock *ImmDom = ID.get(I)) { // Reachable block. 00862 ETNode *&BBNode = Nodes[I]; 00863 if (!BBNode) { // Haven't calculated this node yet? 00864 // Get or calculate the node for the immediate dominator 00865 ETNode *IDomNode = getNodeForBlock(ImmDom); 00866 00867 // Add a new ETNode for this BasicBlock, and set it's parent 00868 // to it's immediate dominator. 00869 BBNode = new ETNode(I); 00870 BBNode->setFather(IDomNode); 00871 } 00872 } 00873 00874 // Make sure we've got nodes around for every block 00875 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) { 00876 ETNode *&BBNode = Nodes[I]; 00877 if (!BBNode) 00878 BBNode = new ETNode(I); 00879 } 00880 00881 updateDFSNumbers (); 00882 } 00883 00884 //===----------------------------------------------------------------------===// 00885 // ETForestBase Implementation 00886 //===----------------------------------------------------------------------===// 00887 00888 void ETForestBase::addNewBlock(BasicBlock *BB, BasicBlock *IDom) { 00889 ETNode *&BBNode = Nodes[BB]; 00890 assert(!BBNode && "BasicBlock already in ET-Forest"); 00891 00892 BBNode = new ETNode(BB); 00893 BBNode->setFather(getNode(IDom)); 00894 DFSInfoValid = false; 00895 } 00896 00897 void ETForestBase::setImmediateDominator(BasicBlock *BB, BasicBlock *newIDom) { 00898 assert(getNode(BB) && "BasicBlock not in ET-Forest"); 00899 assert(getNode(newIDom) && "IDom not in ET-Forest"); 00900 00901 ETNode *Node = getNode(BB); 00902 if (Node->hasFather()) { 00903 if (Node->getFather()->getData<BasicBlock>() == newIDom) 00904 return; 00905 Node->Split(); 00906 } 00907 Node->setFather(getNode(newIDom)); 00908 DFSInfoValid= false; 00909 } 00910 00911 void ETForestBase::print(std::ostream &o, const Module *) const { 00912 o << "=============================--------------------------------\n"; 00913 o << "ET Forest:\n"; 00914 o << "DFS Info "; 00915 if (DFSInfoValid) 00916 o << "is"; 00917 else 00918 o << "is not"; 00919 o << " up to date\n"; 00920 00921 Function *F = getRoots()[0]->getParent(); 00922 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) { 00923 o << " DFS Numbers For Basic Block:"; 00924 WriteAsOperand(o, I, false); 00925 o << " are:"; 00926 if (ETNode *EN = getNode(I)) { 00927 o << "In: " << EN->getDFSNumIn(); 00928 o << " Out: " << EN->getDFSNumOut() << "\n"; 00929 } else { 00930 o << "No associated ETNode"; 00931 } 00932 o << "\n"; 00933 } 00934 o << "\n"; 00935 }