BasicBlock.cpp revision b63933975f7d7381bc4310925ce2a7ceb6095a88
1//===-- BasicBlock.cpp - Implement BasicBlock related functions --*- C++ -*--=//
2//
3// This file implements the Method class for the VMCore library.
4//
5//===----------------------------------------------------------------------===//
6
7#include "llvm/ValueHolderImpl.h"
8#include "llvm/BasicBlock.h"
9#include "llvm/iTerminators.h"
10#include "llvm/Module.h"
11#include "llvm/Method.h"
12#include "llvm/SymbolTable.h"
13#include "llvm/Type.h"
14#include "llvm/CFG.h"
15#include "llvm/iOther.h"
16#include "llvm/CodeGen/MachineInstr.h"
17
18// Instantiate Templates - This ugliness is the price we have to pay
19// for having a ValueHolderImpl.h file seperate from ValueHolder.h!  :(
20//
21template class ValueHolder<Instruction, BasicBlock, Method>;
22
23BasicBlock::BasicBlock(const string &name, Method *Parent)
24  : Value(Type::LabelTy, Value::BasicBlockVal, name),
25    InstList(this, 0),
26    machineInstrVec(new MachineCodeForBasicBlock)
27{
28  if (Parent)
29    Parent->getBasicBlocks().push_back(this);
30}
31
32BasicBlock::~BasicBlock() {
33  dropAllReferences();
34  InstList.delete_all();
35  delete machineInstrVec;
36}
37
38// Specialize setName to take care of symbol table majik
39void BasicBlock::setName(const string &name) {
40  Method *P;
41  if ((P = getParent()) && hasName()) P->getSymbolTable()->remove(this);
42  Value::setName(name);
43  if (P && hasName()) P->getSymbolTable()->insert(this);
44}
45
46void BasicBlock::setParent(Method *parent) {
47  if (getParent() && hasName())
48    getParent()->getSymbolTable()->remove(this);
49
50  InstList.setParent(parent);
51
52  if (getParent() && hasName())
53    getParent()->getSymbolTableSure()->insert(this);
54}
55
56TerminatorInst *BasicBlock::getTerminator() {
57  if (InstList.empty()) return 0;
58  Instruction *T = InstList.back();
59  if (T->isTerminator()) return (TerminatorInst*)T;
60  return 0;
61}
62
63const TerminatorInst *const BasicBlock::getTerminator() const {
64  if (InstList.empty()) return 0;
65  const Instruction *T = InstList.back();
66  if (T->isTerminator()) return (TerminatorInst*)T;
67  return 0;
68}
69
70void BasicBlock::dropAllReferences() {
71  for_each(InstList.begin(), InstList.end(),
72	   std::mem_fun(&Instruction::dropAllReferences));
73}
74
75// hasConstantPoolReferences() - This predicate is true if there is a
76// reference to this basic block in the constant pool for this method.  For
77// example, if a block is reached through a switch table, that table resides
78// in the constant pool, and the basic block is reference from it.
79//
80bool BasicBlock::hasConstantPoolReferences() const {
81  for (use_const_iterator I = use_begin(), E = use_end(); I != E; ++I)
82    if ((*I)->isConstant())
83      return true;
84
85  return false;
86}
87
88// removePredecessor - This method is used to notify a BasicBlock that the
89// specified Predecessor of the block is no longer able to reach it.  This is
90// actually not used to update the Predecessor list, but is actually used to
91// update the PHI nodes that reside in the block.  Note that this should be
92// called while the predecessor still refers to this block.
93//
94void BasicBlock::removePredecessor(BasicBlock *Pred) {
95  using cfg::pred_begin; using cfg::pred_end; using cfg::pred_iterator;
96  assert(find(pred_begin(this), pred_end(this), Pred) != pred_end(this) &&
97	 "removePredecessor: BB is not a predecessor!");
98  if (!front()->isPHINode()) return;   // Quick exit.
99
100  pred_iterator PI(pred_begin(this)), EI(pred_end(this));
101  unsigned max_idx;
102
103  // Loop over the rest of the predecessors until we run out, or until we find
104  // out that there are more than 2 predecessors.
105  for (max_idx = 0; PI != EI && max_idx < 3; ++PI, ++max_idx) /*empty*/;
106
107  // If there are exactly two predecessors, then we want to nuke the PHI nodes
108  // altogether.
109  assert(max_idx != 0 && "PHI Node in block with 0 predecessors!?!?!");
110  if (max_idx <= 2) {                // <= Two predecessors BEFORE I remove one?
111    while (front()->isPHINode()) {   // Yup, loop through and nuke the PHI nodes
112      PHINode *PN = (PHINode*)front();
113      PN->removeIncomingValue(Pred); // Remove the predecessor first...
114
115      assert(PN->getNumIncomingValues() == max_idx-1 &&
116	     "PHI node shouldn't have this many values!!!");
117
118      // If the PHI _HAD_ two uses, replace PHI node with its now *single* value
119      if (max_idx == 2)
120	PN->replaceAllUsesWith(PN->getOperand(0));
121      delete getInstList().remove(begin());  // Remove the PHI node
122    }
123  } else {
124    // Okay, now we know that we need to remove predecessor #pred_idx from all
125    // PHI nodes.  Iterate over each PHI node fixing them up
126    iterator II(begin());
127    for (; (*II)->isPHINode(); ++II) {
128      PHINode *PN = (PHINode*)*II;
129      PN->removeIncomingValue(Pred);
130    }
131  }
132}
133
134
135// splitBasicBlock - This splits a basic block into two at the specified
136// instruction.  Note that all instructions BEFORE the specified iterator stay
137// as part of the original basic block, an unconditional branch is added to
138// the new BB, and the rest of the instructions in the BB are moved to the new
139// BB, including the old terminator.  This invalidates the iterator.
140//
141// Note that this only works on well formed basic blocks (must have a
142// terminator), and 'I' must not be the end of instruction list (which would
143// cause a degenerate basic block to be formed, having a terminator inside of
144// the basic block).
145//
146BasicBlock *BasicBlock::splitBasicBlock(iterator I) {
147  assert(getTerminator() && "Can't use splitBasicBlock on degenerate BB!");
148  assert(I != InstList.end() &&
149	 "Trying to get me to create degenerate basic block!");
150
151  BasicBlock *New = new BasicBlock("", getParent());
152
153  // Go from the end of the basic block through to the iterator pointer, moving
154  // to the new basic block...
155  Instruction *Inst = 0;
156  do {
157    iterator EndIt = end();
158    Inst = InstList.remove(--EndIt);                  // Remove from end
159    New->InstList.push_front(Inst);                   // Add to front
160  } while (Inst != *I);   // Loop until we move the specified instruction.
161
162  // Add a branch instruction to the newly formed basic block.
163  InstList.push_back(new BranchInst(New));
164  return New;
165}
166