Logo Search packages:      
Sourcecode: llvm version File versions  Download package

bool llvm::SplitCriticalEdge ( TerminatorInst TI,
unsigned  SuccNum,
Pass P = 0,
bool  MergeIdenticalEdges = false 
)

SplitCriticalEdge - If this edge is a critical edge, insert a new node to split the critical edge. This will update DominatorTree, and DominatorFrontier information if it is available, thus calling this pass will not invalidate either of them. This returns true if the edge was split, false otherwise. If MergeIdenticalEdges is true (the default), *all* edges from TI to the specified successor will be merged into the same critical edge block. This is most commonly interesting with switch instructions, which may have many edges to any one destination. This ensures that all edges to that dest go to one block instead of each going to a different block, but isn't the standard definition of a "critical edge".

Definition at line 118 of file BreakCriticalEdges.cpp.

References llvm::MachineDominatorTree::addNewBlock(), llvm::SmallVectorImpl< T >::back(), llvm::BasicBlock::begin(), llvm::MachineDominatorTree::changeImmediateDominator(), llvm::SmallVectorImpl< T >::clear(), llvm::MachineDominatorTree::dominates(), llvm::SmallVectorImpl< T >::empty(), llvm::Pass::getAnalysisToUpdate(), llvm::Value::getName(), llvm::MachineDominatorTree::getNode(), llvm::TerminatorInst::getNumSuccessors(), llvm::BasicBlock::getParent(), llvm::TerminatorInst::getSuccessor(), isCriticalEdge(), llvm::SmallVectorImpl< T >::pop_back(), pred_begin(), llvm::SmallVectorImpl< T >::push_back(), llvm::BasicBlock::removePredecessor(), and llvm::TerminatorInst::setSuccessor().

Referenced by SplitCriticalEdge(), and SplitEdge().

                                                       {
  if (!isCriticalEdge(TI, SuccNum, MergeIdenticalEdges)) return false;
  BasicBlock *TIBB = TI->getParent();
  BasicBlock *DestBB = TI->getSuccessor(SuccNum);

  // Create a new basic block, linking it into the CFG.
  BasicBlock *NewBB = new BasicBlock(TIBB->getName() + "." +
                                     DestBB->getName() + "_crit_edge");
  // Create our unconditional branch...
  new BranchInst(DestBB, NewBB);

  // Branch to the new block, breaking the edge.
  TI->setSuccessor(SuccNum, NewBB);

  // Insert the block into the function... right after the block TI lives in.
  Function &F = *TIBB->getParent();
  Function::iterator FBBI = TIBB;
  F.getBasicBlockList().insert(++FBBI, NewBB);
  
  // If there are any PHI nodes in DestBB, we need to update them so that they
  // merge incoming values from NewBB instead of from TIBB.
  //
  for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); ++I) {
    PHINode *PN = cast<PHINode>(I);
    // We no longer enter through TIBB, now we come in through NewBB.  Revector
    // exactly one entry in the PHI node that used to come from TIBB to come
    // from NewBB.
    int BBIdx = PN->getBasicBlockIndex(TIBB);
    PN->setIncomingBlock(BBIdx, NewBB);
  }
  
  // If there are any other edges from TIBB to DestBB, update those to go
  // through the split block, making those edges non-critical as well (and
  // reducing the number of phi entries in the DestBB if relevant).
  if (MergeIdenticalEdges) {
    for (unsigned i = SuccNum+1, e = TI->getNumSuccessors(); i != e; ++i) {
      if (TI->getSuccessor(i) != DestBB) continue;
      
      // Remove an entry for TIBB from DestBB phi nodes.
      DestBB->removePredecessor(TIBB);
      
      // We found another edge to DestBB, go to NewBB instead.
      TI->setSuccessor(i, NewBB);
    }
  }
  
  

  // If we don't have a pass object, we can't update anything...
  if (P == 0) return true;

  // Now update analysis information.  Since the only predecessor of NewBB is
  // the TIBB, TIBB clearly dominates NewBB.  TIBB usually doesn't dominate
  // anything, as there are other successors of DestBB.  However, if all other
  // predecessors of DestBB are already dominated by DestBB (e.g. DestBB is a
  // loop header) then NewBB dominates DestBB.
  SmallVector<BasicBlock*, 8> OtherPreds;

  for (pred_iterator I = pred_begin(DestBB), E = pred_end(DestBB); I != E; ++I)
    if (*I != NewBB)
      OtherPreds.push_back(*I);
  
  bool NewBBDominatesDestBB = true;
  
  // Should we update DominatorTree information?
  if (DominatorTree *DT = P->getAnalysisToUpdate<DominatorTree>()) {
    DomTreeNode *TINode = DT->getNode(TIBB);

    // The new block is not the immediate dominator for any other nodes, but
    // TINode is the immediate dominator for the new node.
    //
    if (TINode) {       // Don't break unreachable code!
      DomTreeNode *NewBBNode = DT->addNewBlock(NewBB, TIBB);
      DomTreeNode *DestBBNode = 0;
     
      // If NewBBDominatesDestBB hasn't been computed yet, do so with DT.
      if (!OtherPreds.empty()) {
        DestBBNode = DT->getNode(DestBB);
        while (!OtherPreds.empty() && NewBBDominatesDestBB) {
          if (DomTreeNode *OPNode = DT->getNode(OtherPreds.back()))
            NewBBDominatesDestBB = DT->dominates(DestBBNode, OPNode);
          OtherPreds.pop_back();
        }
        OtherPreds.clear();
      }
      
      // If NewBBDominatesDestBB, then NewBB dominates DestBB, otherwise it
      // doesn't dominate anything.
      if (NewBBDominatesDestBB) {
        if (!DestBBNode) DestBBNode = DT->getNode(DestBB);
        DT->changeImmediateDominator(DestBBNode, NewBBNode);
      }
    }
  }

  // Should we update DominanceFrontier information?
  if (DominanceFrontier *DF = P->getAnalysisToUpdate<DominanceFrontier>()) {
    // If NewBBDominatesDestBB hasn't been computed yet, do so with DF.
    if (!OtherPreds.empty()) {
      // FIXME: IMPLEMENT THIS!
      assert(0 && "Requiring domfrontiers but not idom/domtree/domset."
             " not implemented yet!");
    }
    
    // Since the new block is dominated by its only predecessor TIBB,
    // it cannot be in any block's dominance frontier.  If NewBB dominates
    // DestBB, its dominance frontier is the same as DestBB's, otherwise it is
    // just {DestBB}.
    DominanceFrontier::DomSetType NewDFSet;
    if (NewBBDominatesDestBB) {
      DominanceFrontier::iterator I = DF->find(DestBB);
      if (I != DF->end()) {
        DF->addBasicBlock(NewBB, I->second);
        // However NewBB's frontier does not include DestBB.
        DominanceFrontier::iterator NF = DF->find(NewBB);
        DF->removeFromFrontier(NF, DestBB);
      }
      else
        DF->addBasicBlock(NewBB, DominanceFrontier::DomSetType());
    } else {
      DominanceFrontier::DomSetType NewDFSet;
      NewDFSet.insert(DestBB);
      DF->addBasicBlock(NewBB, NewDFSet);
    }
  }
  
  // Update LoopInfo if it is around.
  if (LoopInfo *LI = P->getAnalysisToUpdate<LoopInfo>()) {
    // If one or the other blocks were not in a loop, the new block is not
    // either, and thus LI doesn't need to be updated.
    if (Loop *TIL = LI->getLoopFor(TIBB))
      if (Loop *DestLoop = LI->getLoopFor(DestBB)) {
        if (TIL == DestLoop) {
          // Both in the same loop, the NewBB joins loop.
          DestLoop->addBasicBlockToLoop(NewBB, LI->getBase());
        } else if (TIL->contains(DestLoop->getHeader())) {
          // Edge from an outer loop to an inner loop.  Add to the outer loop.
          TIL->addBasicBlockToLoop(NewBB, LI->getBase());
        } else if (DestLoop->contains(TIL->getHeader())) {
          // Edge from an inner loop to an outer loop.  Add to the outer loop.
          DestLoop->addBasicBlockToLoop(NewBB, LI->getBase());
        } else {
          // Edge from two loops with no containment relation.  Because these
          // are natural loops, we know that the destination block must be the
          // header of its loop (adding a branch into a loop elsewhere would
          // create an irreducible loop).
          assert(DestLoop->getHeader() == DestBB &&
                 "Should not create irreducible loops!");
          if (Loop *P = DestLoop->getParentLoop())
            P->addBasicBlockToLoop(NewBB, LI->getBase());
        }
      }
  }
  return true;
}


Generated by  Doxygen 1.6.0   Back to index