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 namespace llvm { 00308 static std::ostream &operator<<(std::ostream &o, 00309 const std::set<BasicBlock*> &BBs) { 00310 for (std::set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end(); 00311 I != E; ++I) 00312 if (*I) 00313 WriteAsOperand(o, *I, false); 00314 else 00315 o << " <<exit node>>"; 00316 return o; 00317 } 00318 } 00319 00320 void DominatorSetBase::print(std::ostream &o, const Module* ) const { 00321 for (const_iterator I = begin(), E = end(); I != E; ++I) { 00322 o << " DomSet For BB: "; 00323 if (I->first) 00324 WriteAsOperand(o, I->first, false); 00325 else 00326 o << " <<exit node>>"; 00327 o << " is:\t" << I->second << "\n"; 00328 } 00329 } 00330 00331 //===----------------------------------------------------------------------===// 00332 // DominatorTree Implementation 00333 //===----------------------------------------------------------------------===// 00334 00335 static RegisterAnalysis<DominatorTree> 00336 E("domtree", "Dominator Tree Construction", true); 00337 00338 // DominatorTreeBase::reset - Free all of the tree node memory. 00339 // 00340 void DominatorTreeBase::reset() { 00341 for (NodeMapType::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) 00342 delete I->second; 00343 Nodes.clear(); 00344 RootNode = 0; 00345 } 00346 00347 void DominatorTreeBase::Node::setIDom(Node *NewIDom) { 00348 assert(IDom && "No immediate dominator?"); 00349 if (IDom != NewIDom) { 00350 std::vector<Node*>::iterator I = 00351 std::find(IDom->Children.begin(), IDom->Children.end(), this); 00352 assert(I != IDom->Children.end() && 00353 "Not in immediate dominator children set!"); 00354 // I am no longer your child... 00355 IDom->Children.erase(I); 00356 00357 // Switch to new dominator 00358 IDom = NewIDom; 00359 IDom->Children.push_back(this); 00360 } 00361 } 00362 00363 DominatorTreeBase::Node *DominatorTree::getNodeForBlock(BasicBlock *BB) { 00364 Node *&BBNode = Nodes[BB]; 00365 if (BBNode) return BBNode; 00366 00367 // Haven't calculated this node yet? Get or calculate the node for the 00368 // immediate dominator. 00369 BasicBlock *IDom = getAnalysis<ImmediateDominators>()[BB]; 00370 Node *IDomNode = getNodeForBlock(IDom); 00371 00372 // Add a new tree node for this BasicBlock, and link it as a child of 00373 // IDomNode 00374 return BBNode = IDomNode->addChild(new Node(BB, IDomNode)); 00375 } 00376 00377 void DominatorTree::calculate(const ImmediateDominators &ID) { 00378 assert(Roots.size() == 1 && "DominatorTree should have 1 root block!"); 00379 BasicBlock *Root = Roots[0]; 00380 Nodes[Root] = RootNode = new Node(Root, 0); // Add a node for the root... 00381 00382 Function *F = Root->getParent(); 00383 // Loop over all of the reachable blocks in the function... 00384 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) 00385 if (BasicBlock *ImmDom = ID.get(I)) { // Reachable block. 00386 Node *&BBNode = Nodes[I]; 00387 if (!BBNode) { // Haven't calculated this node yet? 00388 // Get or calculate the node for the immediate dominator 00389 Node *IDomNode = getNodeForBlock(ImmDom); 00390 00391 // Add a new tree node for this BasicBlock, and link it as a child of 00392 // IDomNode 00393 BBNode = IDomNode->addChild(new Node(I, IDomNode)); 00394 } 00395 } 00396 } 00397 00398 static std::ostream &operator<<(std::ostream &o, 00399 const DominatorTreeBase::Node *Node) { 00400 if (Node->getBlock()) 00401 WriteAsOperand(o, Node->getBlock(), false); 00402 else 00403 o << " <<exit node>>"; 00404 return o << "\n"; 00405 } 00406 00407 static void PrintDomTree(const DominatorTreeBase::Node *N, std::ostream &o, 00408 unsigned Lev) { 00409 o << std::string(2*Lev, ' ') << "[" << Lev << "] " << N; 00410 for (DominatorTreeBase::Node::const_iterator I = N->begin(), E = N->end(); 00411 I != E; ++I) 00412 PrintDomTree(*I, o, Lev+1); 00413 } 00414 00415 void DominatorTreeBase::print(std::ostream &o, const Module* ) const { 00416 o << "=============================--------------------------------\n" 00417 << "Inorder Dominator Tree:\n"; 00418 PrintDomTree(getRootNode(), o, 1); 00419 } 00420 00421 00422 //===----------------------------------------------------------------------===// 00423 // DominanceFrontier Implementation 00424 //===----------------------------------------------------------------------===// 00425 00426 static RegisterAnalysis<DominanceFrontier> 00427 G("domfrontier", "Dominance Frontier Construction", true); 00428 00429 const DominanceFrontier::DomSetType & 00430 DominanceFrontier::calculate(const DominatorTree &DT, 00431 const DominatorTree::Node *Node) { 00432 // Loop over CFG successors to calculate DFlocal[Node] 00433 BasicBlock *BB = Node->getBlock(); 00434 DomSetType &S = Frontiers[BB]; // The new set to fill in... 00435 00436 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); 00437 SI != SE; ++SI) { 00438 // Does Node immediately dominate this successor? 00439 if (DT[*SI]->getIDom() != Node) 00440 S.insert(*SI); 00441 } 00442 00443 // At this point, S is DFlocal. Now we union in DFup's of our children... 00444 // Loop through and visit the nodes that Node immediately dominates (Node's 00445 // children in the IDomTree) 00446 // 00447 for (DominatorTree::Node::const_iterator NI = Node->begin(), NE = Node->end(); 00448 NI != NE; ++NI) { 00449 DominatorTree::Node *IDominee = *NI; 00450 const DomSetType &ChildDF = calculate(DT, IDominee); 00451 00452 DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end(); 00453 for (; CDFI != CDFE; ++CDFI) { 00454 if (!Node->properlyDominates(DT[*CDFI])) 00455 S.insert(*CDFI); 00456 } 00457 } 00458 00459 return S; 00460 } 00461 00462 void DominanceFrontierBase::print(std::ostream &o, const Module* ) const { 00463 for (const_iterator I = begin(), E = end(); I != E; ++I) { 00464 o << " DomFrontier for BB"; 00465 if (I->first) 00466 WriteAsOperand(o, I->first, false); 00467 else 00468 o << " <<exit node>>"; 00469 o << " is:\t" << I->second << "\n"; 00470 } 00471 } 00472 00473 //===----------------------------------------------------------------------===// 00474 // ETOccurrence Implementation 00475 //===----------------------------------------------------------------------===// 00476 00477 void ETOccurrence::Splay() { 00478 ETOccurrence *father; 00479 ETOccurrence *grandfather; 00480 int occdepth; 00481 int fatherdepth; 00482 00483 while (Parent) { 00484 occdepth = Depth; 00485 00486 father = Parent; 00487 fatherdepth = Parent->Depth; 00488 grandfather = father->Parent; 00489 00490 // If we have no grandparent, a single zig or zag will do. 00491 if (!grandfather) { 00492 setDepthAdd(fatherdepth); 00493 MinOccurrence = father->MinOccurrence; 00494 Min = father->Min; 00495 00496 // See what we have to rotate 00497 if (father->Left == this) { 00498 // Zig 00499 father->setLeft(Right); 00500 setRight(father); 00501 if (father->Left) 00502 father->Left->setDepthAdd(occdepth); 00503 } else { 00504 // Zag 00505 father->setRight(Left); 00506 setLeft(father); 00507 if (father->Right) 00508 father->Right->setDepthAdd(occdepth); 00509 } 00510 father->setDepth(-occdepth); 00511 Parent = NULL; 00512 00513 father->recomputeMin(); 00514 return; 00515 } 00516 00517 // If we have a grandfather, we need to do some 00518 // combination of zig and zag. 00519 int grandfatherdepth = grandfather->Depth; 00520 00521 setDepthAdd(fatherdepth + grandfatherdepth); 00522 MinOccurrence = grandfather->MinOccurrence; 00523 Min = grandfather->Min; 00524 00525 ETOccurrence *greatgrandfather = grandfather->Parent; 00526 00527 if (grandfather->Left == father) { 00528 if (father->Left == this) { 00529 // Zig zig 00530 grandfather->setLeft(father->Right); 00531 father->setLeft(Right); 00532 setRight(father); 00533 father->setRight(grandfather); 00534 00535 father->setDepth(-occdepth); 00536 00537 if (father->Left) 00538 father->Left->setDepthAdd(occdepth); 00539 00540 grandfather->setDepth(-fatherdepth); 00541 if (grandfather->Left) 00542 grandfather->Left->setDepthAdd(fatherdepth); 00543 } else { 00544 // Zag zig 00545 grandfather->setLeft(Right); 00546 father->setRight(Left); 00547 setLeft(father); 00548 setRight(grandfather); 00549 00550 father->setDepth(-occdepth); 00551 if (father->Right) 00552 father->Right->setDepthAdd(occdepth); 00553 grandfather->setDepth(-occdepth - fatherdepth); 00554 if (grandfather->Left) 00555 grandfather->Left->setDepthAdd(occdepth + fatherdepth); 00556 } 00557 } else { 00558 if (father->Left == this) { 00559 // Zig zag 00560 grandfather->setRight(Left); 00561 father->setLeft(Right); 00562 setLeft(grandfather); 00563 setRight(father); 00564 00565 father->setDepth(-occdepth); 00566 if (father->Left) 00567 father->Left->setDepthAdd(occdepth); 00568 grandfather->setDepth(-occdepth - fatherdepth); 00569 if (grandfather->Right) 00570 grandfather->Right->setDepthAdd(occdepth + fatherdepth); 00571 } else { // Zag Zag 00572 grandfather->setRight(father->Left); 00573 father->setRight(Left); 00574 setLeft(father); 00575 father->setLeft(grandfather); 00576 00577 father->setDepth(-occdepth); 00578 if (father->Right) 00579 father->Right->setDepthAdd(occdepth); 00580 grandfather->setDepth(-fatherdepth); 00581 if (grandfather->Right) 00582 grandfather->Right->setDepthAdd(fatherdepth); 00583 } 00584 } 00585 00586 // Might need one more rotate depending on greatgrandfather. 00587 setParent(greatgrandfather); 00588 if (greatgrandfather) { 00589 if (greatgrandfather->Left == grandfather) 00590 greatgrandfather->Left = this; 00591 else 00592 greatgrandfather->Right = this; 00593 00594 } 00595 grandfather->recomputeMin(); 00596 father->recomputeMin(); 00597 } 00598 } 00599 00600 //===----------------------------------------------------------------------===// 00601 // ETNode implementation 00602 //===----------------------------------------------------------------------===// 00603 00604 void ETNode::Split() { 00605 ETOccurrence *right, *left; 00606 ETOccurrence *rightmost = RightmostOcc; 00607 ETOccurrence *parent; 00608 00609 // Update the occurrence tree first. 00610 RightmostOcc->Splay(); 00611 00612 // Find the leftmost occurrence in the rightmost subtree, then splay 00613 // around it. 00614 for (right = rightmost->Right; right->Left; right = right->Left); 00615 00616 right->Splay(); 00617 00618 // Start splitting 00619 right->Left->Parent = NULL; 00620 parent = ParentOcc; 00621 parent->Splay(); 00622 ParentOcc = NULL; 00623 00624 left = parent->Left; 00625 parent->Right->Parent = NULL; 00626 00627 right->setLeft(left); 00628 00629 right->recomputeMin(); 00630 00631 rightmost->Splay(); 00632 rightmost->Depth = 0; 00633 rightmost->Min = 0; 00634 00635 delete parent; 00636 00637 // Now update *our* tree 00638 00639 if (Father->Son == this) 00640 Father->Son = Right; 00641 00642 if (Father->Son == this) 00643 Father->Son = NULL; 00644 else { 00645 Left->Right = Right; 00646 Right->Left = Left; 00647 } 00648 Left = Right = NULL; 00649 Father = NULL; 00650 } 00651 00652 void ETNode::setFather(ETNode *NewFather) { 00653 ETOccurrence *rightmost; 00654 ETOccurrence *leftpart; 00655 ETOccurrence *NewFatherOcc; 00656 ETOccurrence *temp; 00657 00658 // First update the path in the splay tree 00659 NewFatherOcc = new ETOccurrence(NewFather); 00660 00661 rightmost = NewFather->RightmostOcc; 00662 rightmost->Splay(); 00663 00664 leftpart = rightmost->Left; 00665 00666 temp = RightmostOcc; 00667 temp->Splay(); 00668 00669 NewFatherOcc->setLeft(leftpart); 00670 NewFatherOcc->setRight(temp); 00671 00672 temp->Depth++; 00673 temp->Min++; 00674 NewFatherOcc->recomputeMin(); 00675 00676 rightmost->setLeft(NewFatherOcc); 00677 00678 if (NewFatherOcc->Min + rightmost->Depth < rightmost->Min) { 00679 rightmost->Min = NewFatherOcc->Min + rightmost->Depth; 00680 rightmost->MinOccurrence = NewFatherOcc->MinOccurrence; 00681 } 00682 00683 delete ParentOcc; 00684 ParentOcc = NewFatherOcc; 00685 00686 // Update *our* tree 00687 ETNode *left; 00688 ETNode *right; 00689 00690 Father = NewFather; 00691 right = Father->Son; 00692 00693 if (right) 00694 left = right->Left; 00695 else 00696 left = right = this; 00697 00698 left->Right = this; 00699 right->Left = this; 00700 Left = left; 00701 Right = right; 00702 00703 Father->Son = this; 00704 } 00705 00706 bool ETNode::Below(ETNode *other) { 00707 ETOccurrence *up = other->RightmostOcc; 00708 ETOccurrence *down = RightmostOcc; 00709 00710 if (this == other) 00711 return true; 00712 00713 up->Splay(); 00714 00715 ETOccurrence *left, *right; 00716 left = up->Left; 00717 right = up->Right; 00718 00719 if (!left) 00720 return false; 00721 00722 left->Parent = NULL; 00723 00724 if (right) 00725 right->Parent = NULL; 00726 00727 down->Splay(); 00728 00729 if (left == down || left->Parent != NULL) { 00730 if (right) 00731 right->Parent = up; 00732 up->setLeft(down); 00733 } else { 00734 left->Parent = up; 00735 00736 // If the two occurrences are in different trees, put things 00737 // back the way they were. 00738 if (right && right->Parent != NULL) 00739 up->setRight(down); 00740 else 00741 up->setRight(right); 00742 return false; 00743 } 00744 00745 if (down->Depth <= 0) 00746 return false; 00747 00748 return !down->Right || down->Right->Min + down->Depth >= 0; 00749 } 00750 00751 ETNode *ETNode::NCA(ETNode *other) { 00752 ETOccurrence *occ1 = RightmostOcc; 00753 ETOccurrence *occ2 = other->RightmostOcc; 00754 00755 ETOccurrence *left, *right, *ret; 00756 ETOccurrence *occmin; 00757 int mindepth; 00758 00759 if (this == other) 00760 return this; 00761 00762 occ1->Splay(); 00763 left = occ1->Left; 00764 right = occ1->Right; 00765 00766 if (left) 00767 left->Parent = NULL; 00768 00769 if (right) 00770 right->Parent = NULL; 00771 occ2->Splay(); 00772 00773 if (left == occ2 || (left && left->Parent != NULL)) { 00774 ret = occ2->Right; 00775 00776 occ1->setLeft(occ2); 00777 if (right) 00778 right->Parent = occ1; 00779 } else { 00780 ret = occ2->Left; 00781 00782 occ1->setRight(occ2); 00783 if (left) 00784 left->Parent = occ1; 00785 } 00786 00787 if (occ2->Depth > 0) { 00788 occmin = occ1; 00789 mindepth = occ1->Depth; 00790 } else { 00791 occmin = occ2; 00792 mindepth = occ2->Depth + occ1->Depth; 00793 } 00794 00795 if (ret && ret->Min + occ1->Depth + occ2->Depth < mindepth) 00796 return ret->MinOccurrence->OccFor; 00797 else 00798 return occmin->OccFor; 00799 } 00800 00801 //===----------------------------------------------------------------------===// 00802 // ETForest implementation 00803 //===----------------------------------------------------------------------===// 00804 00805 static RegisterAnalysis<ETForest> 00806 D("etforest", "ET Forest Construction", true); 00807 00808 void ETForestBase::reset() { 00809 for (ETMapType::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) 00810 delete I->second; 00811 Nodes.clear(); 00812 } 00813 00814 void ETForestBase::updateDFSNumbers() 00815 { 00816 int dfsnum = 0; 00817 // Iterate over all nodes in depth first order. 00818 for (unsigned i = 0, e = Roots.size(); i != e; ++i) 00819 for (df_iterator<BasicBlock*> I = df_begin(Roots[i]), 00820 E = df_end(Roots[i]); I != E; ++I) { 00821 BasicBlock *BB = *I; 00822 if (!getNode(BB)->hasFather()) 00823 getNode(BB)->assignDFSNumber(dfsnum); 00824 } 00825 SlowQueries = 0; 00826 DFSInfoValid = true; 00827 } 00828 00829 ETNode *ETForest::getNodeForBlock(BasicBlock *BB) { 00830 ETNode *&BBNode = Nodes[BB]; 00831 if (BBNode) return BBNode; 00832 00833 // Haven't calculated this node yet? Get or calculate the node for the 00834 // immediate dominator. 00835 BasicBlock *IDom = getAnalysis<ImmediateDominators>()[BB]; 00836 00837 // If we are unreachable, we may not have an immediate dominator. 00838 if (!IDom) 00839 return BBNode = new ETNode(BB); 00840 else { 00841 ETNode *IDomNode = getNodeForBlock(IDom); 00842 00843 // Add a new tree node for this BasicBlock, and link it as a child of 00844 // IDomNode 00845 BBNode = new ETNode(BB); 00846 BBNode->setFather(IDomNode); 00847 return BBNode; 00848 } 00849 } 00850 00851 void ETForest::calculate(const ImmediateDominators &ID) { 00852 assert(Roots.size() == 1 && "ETForest should have 1 root block!"); 00853 BasicBlock *Root = Roots[0]; 00854 Nodes[Root] = new ETNode(Root); // Add a node for the root 00855 00856 Function *F = Root->getParent(); 00857 // Loop over all of the reachable blocks in the function... 00858 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) 00859 if (BasicBlock *ImmDom = ID.get(I)) { // Reachable block. 00860 ETNode *&BBNode = Nodes[I]; 00861 if (!BBNode) { // Haven't calculated this node yet? 00862 // Get or calculate the node for the immediate dominator 00863 ETNode *IDomNode = getNodeForBlock(ImmDom); 00864 00865 // Add a new ETNode for this BasicBlock, and set it's parent 00866 // to it's immediate dominator. 00867 BBNode = new ETNode(I); 00868 BBNode->setFather(IDomNode); 00869 } 00870 } 00871 00872 // Make sure we've got nodes around for every block 00873 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) { 00874 ETNode *&BBNode = Nodes[I]; 00875 if (!BBNode) 00876 BBNode = new ETNode(I); 00877 } 00878 00879 updateDFSNumbers (); 00880 } 00881 00882 //===----------------------------------------------------------------------===// 00883 // ETForestBase Implementation 00884 //===----------------------------------------------------------------------===// 00885 00886 void ETForestBase::addNewBlock(BasicBlock *BB, BasicBlock *IDom) { 00887 ETNode *&BBNode = Nodes[BB]; 00888 assert(!BBNode && "BasicBlock already in ET-Forest"); 00889 00890 BBNode = new ETNode(BB); 00891 BBNode->setFather(getNode(IDom)); 00892 DFSInfoValid = false; 00893 } 00894 00895 void ETForestBase::setImmediateDominator(BasicBlock *BB, BasicBlock *newIDom) { 00896 assert(getNode(BB) && "BasicBlock not in ET-Forest"); 00897 assert(getNode(newIDom) && "IDom not in ET-Forest"); 00898 00899 ETNode *Node = getNode(BB); 00900 if (Node->hasFather()) { 00901 if (Node->getFather()->getData<BasicBlock>() == newIDom) 00902 return; 00903 Node->Split(); 00904 } 00905 Node->setFather(getNode(newIDom)); 00906 DFSInfoValid= false; 00907 } 00908 00909 void ETForestBase::print(std::ostream &o, const Module *) const { 00910 o << "=============================--------------------------------\n"; 00911 o << "ET Forest:\n"; 00912 o << "DFS Info "; 00913 if (DFSInfoValid) 00914 o << "is"; 00915 else 00916 o << "is not"; 00917 o << " up to date\n"; 00918 00919 Function *F = getRoots()[0]->getParent(); 00920 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) { 00921 o << " DFS Numbers For Basic Block:"; 00922 WriteAsOperand(o, I, false); 00923 o << " are:"; 00924 if (ETNode *EN = getNode(I)) { 00925 o << "In: " << EN->getDFSNumIn(); 00926 o << " Out: " << EN->getDFSNumOut() << "\n"; 00927 } else { 00928 o << "No associated ETNode"; 00929 } 00930 o << "\n"; 00931 } 00932 o << "\n"; 00933 } 00934 00935 DEFINING_FILE_FOR(DominatorSet)