-ETNode *ETNode::NCA(ETNode *other) {
- ETOccurrence *occ1 = RightmostOcc;
- ETOccurrence *occ2 = other->RightmostOcc;
-
- ETOccurrence *left, *right, *ret;
- ETOccurrence *occmin;
- int mindepth;
-
- if (this == other)
- return this;
-
- occ1->Splay();
- left = occ1->Left;
- right = occ1->Right;
-
- if (left)
- left->Parent = NULL;
-
- if (right)
- right->Parent = NULL;
- occ2->Splay();
-
- if (left == occ2 || (left && left->Parent != NULL)) {
- ret = occ2->Right;
-
- occ1->setLeft(occ2);
- if (right)
- right->Parent = occ1;
- } else {
- ret = occ2->Left;
-
- occ1->setRight(occ2);
- if (left)
- left->Parent = occ1;
- }
-
- if (occ2->Depth > 0) {
- occmin = occ1;
- mindepth = occ1->Depth;
- } else {
- occmin = occ2;
- mindepth = occ2->Depth + occ1->Depth;
- }
-
- if (ret && ret->Min + occ1->Depth + occ2->Depth < mindepth)
- return ret->MinOccurrence->OccFor;
- else
- return occmin->OccFor;
-}
-
-void ETNode::assignDFSNumber(int num) {
- std::vector<ETNode *> workStack;
- std::set<ETNode *> visitedNodes;
-
- workStack.push_back(this);
- visitedNodes.insert(this);
- this->DFSNumIn = num++;
-
- while (!workStack.empty()) {
- ETNode *Node = workStack.back();
-
- // If this is leaf node then set DFSNumOut and pop the stack
- if (!Node->Son) {
- Node->DFSNumOut = num++;
- workStack.pop_back();
- continue;
- }
-
- ETNode *son = Node->Son;
-
- // Visit Node->Son first
- if (visitedNodes.count(son) == 0) {
- son->DFSNumIn = num++;
- workStack.push_back(son);
- visitedNodes.insert(son);
- continue;
- }
-
- bool visitChild = false;
- // Visit remaining children
- for (ETNode *s = son->Right; s != son && !visitChild; s = s->Right) {
- if (visitedNodes.count(s) == 0) {
- visitChild = true;
- s->DFSNumIn = num++;
- workStack.push_back(s);
- visitedNodes.insert(s);
- }
- }
-
- if (!visitChild) {
- // If we reach here means all children are visited
- Node->DFSNumOut = num++;
- workStack.pop_back();
- }
- }
-}
-
-//===----------------------------------------------------------------------===//
-// ETForest implementation
-//===----------------------------------------------------------------------===//
-
-static RegisterPass<ETForest>
-D("etforest", "ET Forest Construction", true);
-
-void ETForestBase::reset() {
- for (ETMapType::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I)
- delete I->second;
- Nodes.clear();
-}
-
-void ETForestBase::updateDFSNumbers()
-{
- int dfsnum = 0;
- // Iterate over all nodes in depth first order.
- for (unsigned i = 0, e = Roots.size(); i != e; ++i)
- for (df_iterator<BasicBlock*> I = df_begin(Roots[i]),
- E = df_end(Roots[i]); I != E; ++I) {
- BasicBlock *BB = *I;
- if (!getNode(BB)->hasFather())
- getNode(BB)->assignDFSNumber(dfsnum);
- }
- SlowQueries = 0;
- DFSInfoValid = true;
-}
-
-// dominates - Return true if A dominates B. THis performs the
-// special checks necessary if A and B are in the same basic block.
-bool ETForestBase::dominates(Instruction *A, Instruction *B) {
- BasicBlock *BBA = A->getParent(), *BBB = B->getParent();
- if (BBA != BBB) return dominates(BBA, BBB);
-
- // Loop through the basic block until we find A or B.
- BasicBlock::iterator I = BBA->begin();
- for (; &*I != A && &*I != B; ++I) /*empty*/;
-
- if(!IsPostDominators) {
- // A dominates B if it is found first in the basic block.
- return &*I == A;
- } else {
- // A post-dominates B if B is found first in the basic block.
- return &*I == B;
- }
-}
-
-ETNode *ETForest::getNodeForBlock(BasicBlock *BB) {
- ETNode *&BBNode = Nodes[BB];
- if (BBNode) return BBNode;
-
- // Haven't calculated this node yet? Get or calculate the node for the
- // immediate dominator.
- BasicBlock *IDom = getAnalysis<ImmediateDominators>()[BB];
-
- // If we are unreachable, we may not have an immediate dominator.
- if (!IDom)
- return BBNode = new ETNode(BB);
- else {
- ETNode *IDomNode = getNodeForBlock(IDom);
-
- // Add a new tree node for this BasicBlock, and link it as a child of
- // IDomNode
- BBNode = new ETNode(BB);
- BBNode->setFather(IDomNode);
- return BBNode;
- }
-}
-
-void ETForest::calculate(const ImmediateDominators &ID) {
- assert(Roots.size() == 1 && "ETForest should have 1 root block!");
- BasicBlock *Root = Roots[0];
- Nodes[Root] = new ETNode(Root); // Add a node for the root
-
- Function *F = Root->getParent();
- // Loop over all of the reachable blocks in the function...
- for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
- if (BasicBlock *ImmDom = ID.get(I)) { // Reachable block.
- ETNode *&BBNode = Nodes[I];
- if (!BBNode) { // Haven't calculated this node yet?
- // Get or calculate the node for the immediate dominator
- ETNode *IDomNode = getNodeForBlock(ImmDom);
-
- // Add a new ETNode for this BasicBlock, and set it's parent
- // to it's immediate dominator.
- BBNode = new ETNode(I);
- BBNode->setFather(IDomNode);
- }
- }
-
- // Make sure we've got nodes around for every block
- for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) {
- ETNode *&BBNode = Nodes[I];
- if (!BBNode)
- BBNode = new ETNode(I);
- }
-
- updateDFSNumbers ();
-}
-
-//===----------------------------------------------------------------------===//
-// ETForestBase Implementation
-//===----------------------------------------------------------------------===//
-
-void ETForestBase::addNewBlock(BasicBlock *BB, BasicBlock *IDom) {
- ETNode *&BBNode = Nodes[BB];
- assert(!BBNode && "BasicBlock already in ET-Forest");
-
- BBNode = new ETNode(BB);
- BBNode->setFather(getNode(IDom));
- DFSInfoValid = false;
-}
-
-void ETForestBase::setImmediateDominator(BasicBlock *BB, BasicBlock *newIDom) {
- assert(getNode(BB) && "BasicBlock not in ET-Forest");
- assert(getNode(newIDom) && "IDom not in ET-Forest");
-
- ETNode *Node = getNode(BB);
- if (Node->hasFather()) {
- if (Node->getFather()->getData<BasicBlock>() == newIDom)
- return;
- Node->Split();
- }
- Node->setFather(getNode(newIDom));
- DFSInfoValid= false;
-}
-
-void ETForestBase::print(std::ostream &o, const Module *) const {
- o << "=============================--------------------------------\n";
- o << "ET Forest:\n";
- o << "DFS Info ";
- if (DFSInfoValid)
- o << "is";
- else
- o << "is not";
- o << " up to date\n";
-
- Function *F = getRoots()[0]->getParent();
- for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) {
- o << " DFS Numbers For Basic Block:";
- WriteAsOperand(o, I, false);
- o << " are:";
- if (ETNode *EN = getNode(I)) {
- o << "In: " << EN->getDFSNumIn();
- o << " Out: " << EN->getDFSNumOut() << "\n";
- } else {
- o << "No associated ETNode";
- }
- o << "\n";
- }
- o << "\n";