LLVM API Documentation
00001 //===-- llvm/CodeGen/MachineBasicBlock.cpp ----------------------*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // Collect the sequence of machine instructions for a basic block. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #include "llvm/CodeGen/MachineBasicBlock.h" 00015 #include "llvm/BasicBlock.h" 00016 #include "llvm/CodeGen/MachineFunction.h" 00017 #include "llvm/Target/TargetRegisterInfo.h" 00018 #include "llvm/Target/TargetData.h" 00019 #include "llvm/Target/TargetInstrDesc.h" 00020 #include "llvm/Target/TargetMachine.h" 00021 #include "llvm/Support/LeakDetector.h" 00022 #include "llvm/Support/raw_ostream.h" 00023 #include <algorithm> 00024 using namespace llvm; 00025 00026 MachineBasicBlock::MachineBasicBlock(MachineFunction &mf, const BasicBlock *bb) 00027 : BB(bb), Number(-1), xParent(&mf), Alignment(0), IsLandingPad(false) { 00028 Insts.Parent = this; 00029 } 00030 00031 MachineBasicBlock::~MachineBasicBlock() { 00032 LeakDetector::removeGarbageObject(this); 00033 } 00034 00035 std::ostream& llvm::operator<<(std::ostream &OS, const MachineBasicBlock &MBB) { 00036 MBB.print(OS); 00037 return OS; 00038 } 00039 raw_ostream& llvm::operator<<(raw_ostream &OS, const MachineBasicBlock &MBB) { 00040 MBB.print(OS); 00041 return OS; 00042 } 00043 00044 /// addNodeToList (MBB) - When an MBB is added to an MF, we need to update the 00045 /// parent pointer of the MBB, the MBB numbering, and any instructions in the 00046 /// MBB to be on the right operand list for registers. 00047 /// 00048 /// MBBs start out as #-1. When a MBB is added to a MachineFunction, it 00049 /// gets the next available unique MBB number. If it is removed from a 00050 /// MachineFunction, it goes back to being #-1. 00051 void ilist_traits<MachineBasicBlock>::addNodeToList(MachineBasicBlock* N) { 00052 MachineFunction &MF = *N->getParent(); 00053 N->Number = MF.addToMBBNumbering(N); 00054 00055 // Make sure the instructions have their operands in the reginfo lists. 00056 MachineRegisterInfo &RegInfo = MF.getRegInfo(); 00057 for (MachineBasicBlock::iterator I = N->begin(), E = N->end(); I != E; ++I) 00058 I->AddRegOperandsToUseLists(RegInfo); 00059 00060 LeakDetector::removeGarbageObject(N); 00061 } 00062 00063 void ilist_traits<MachineBasicBlock>::removeNodeFromList(MachineBasicBlock* N) { 00064 N->getParent()->removeFromMBBNumbering(N->Number); 00065 N->Number = -1; 00066 LeakDetector::addGarbageObject(N); 00067 } 00068 00069 00070 /// addNodeToList (MI) - When we add an instruction to a basic block 00071 /// list, we update its parent pointer and add its operands from reg use/def 00072 /// lists if appropriate. 00073 void ilist_traits<MachineInstr>::addNodeToList(MachineInstr* N) { 00074 assert(N->getParent() == 0 && "machine instruction already in a basic block"); 00075 N->setParent(Parent); 00076 00077 // Add the instruction's register operands to their corresponding 00078 // use/def lists. 00079 MachineFunction *MF = Parent->getParent(); 00080 N->AddRegOperandsToUseLists(MF->getRegInfo()); 00081 00082 LeakDetector::removeGarbageObject(N); 00083 } 00084 00085 /// removeNodeFromList (MI) - When we remove an instruction from a basic block 00086 /// list, we update its parent pointer and remove its operands from reg use/def 00087 /// lists if appropriate. 00088 void ilist_traits<MachineInstr>::removeNodeFromList(MachineInstr* N) { 00089 assert(N->getParent() != 0 && "machine instruction not in a basic block"); 00090 00091 // Remove from the use/def lists. 00092 N->RemoveRegOperandsFromUseLists(); 00093 00094 N->setParent(0); 00095 00096 LeakDetector::addGarbageObject(N); 00097 } 00098 00099 /// transferNodesFromList (MI) - When moving a range of instructions from one 00100 /// MBB list to another, we need to update the parent pointers and the use/def 00101 /// lists. 00102 void ilist_traits<MachineInstr>::transferNodesFromList( 00103 ilist_traits<MachineInstr>& fromList, 00104 MachineBasicBlock::iterator first, 00105 MachineBasicBlock::iterator last) { 00106 assert(Parent->getParent() == fromList.Parent->getParent() && 00107 "MachineInstr parent mismatch!"); 00108 00109 // Splice within the same MBB -> no change. 00110 if (Parent == fromList.Parent) return; 00111 00112 // If splicing between two blocks within the same function, just update the 00113 // parent pointers. 00114 for (; first != last; ++first) 00115 first->setParent(Parent); 00116 } 00117 00118 void ilist_traits<MachineInstr>::deleteNode(MachineInstr* MI) { 00119 assert(!MI->getParent() && "MI is still in a block!"); 00120 Parent->getParent()->DeleteMachineInstr(MI); 00121 } 00122 00123 MachineBasicBlock::iterator MachineBasicBlock::getFirstTerminator() { 00124 iterator I = end(); 00125 while (I != begin() && (--I)->getDesc().isTerminator()) 00126 ; /*noop */ 00127 if (I != end() && !I->getDesc().isTerminator()) ++I; 00128 return I; 00129 } 00130 00131 /// isOnlyReachableViaFallthough - Return true if this basic block has 00132 /// exactly one predecessor and the control transfer mechanism between 00133 /// the predecessor and this block is a fall-through. 00134 bool MachineBasicBlock::isOnlyReachableByFallthrough() const { 00135 // If this is a landing pad, it isn't a fall through. If it has no preds, 00136 // then nothing falls through to it. 00137 if (isLandingPad() || pred_empty()) 00138 return false; 00139 00140 // If there isn't exactly one predecessor, it can't be a fall through. 00141 const_pred_iterator PI = pred_begin(), PI2 = PI; 00142 ++PI2; 00143 if (PI2 != pred_end()) 00144 return false; 00145 00146 // The predecessor has to be immediately before this block. 00147 const MachineBasicBlock *Pred = *PI; 00148 00149 if (!Pred->isLayoutSuccessor(this)) 00150 return false; 00151 00152 // If the block is completely empty, then it definitely does fall through. 00153 if (Pred->empty()) 00154 return true; 00155 00156 // Otherwise, check the last instruction. 00157 const MachineInstr &LastInst = Pred->back(); 00158 return !LastInst.getDesc().isBarrier(); 00159 } 00160 00161 void MachineBasicBlock::dump() const { 00162 print(*cerr.stream()); 00163 } 00164 00165 static inline void OutputReg(raw_ostream &os, unsigned RegNo, 00166 const TargetRegisterInfo *TRI = 0) { 00167 if (!RegNo || TargetRegisterInfo::isPhysicalRegister(RegNo)) { 00168 if (TRI) 00169 os << " %" << TRI->get(RegNo).Name; 00170 else 00171 os << " %mreg(" << RegNo << ")"; 00172 } else 00173 os << " %reg" << RegNo; 00174 } 00175 00176 void MachineBasicBlock::print(std::ostream &OS, 00177 const PrefixPrinter &prefix) const { 00178 raw_os_ostream RawOS(OS); 00179 print(RawOS, prefix); 00180 } 00181 00182 void MachineBasicBlock::print(raw_ostream &OS, 00183 const PrefixPrinter &prefix) const { 00184 const MachineFunction *MF = getParent(); 00185 if(!MF) { 00186 OS << "Can't print out MachineBasicBlock because parent MachineFunction" 00187 << " is null\n"; 00188 return; 00189 } 00190 00191 const BasicBlock *LBB = getBasicBlock(); 00192 OS << "\n"; 00193 if (LBB) OS << LBB->getName() << ": "; 00194 OS << (const void*)this 00195 << ", LLVM BB @" << (const void*) LBB << ", ID#" << getNumber(); 00196 if (Alignment) OS << ", Alignment " << Alignment; 00197 if (isLandingPad()) OS << ", EH LANDING PAD"; 00198 OS << ":\n"; 00199 00200 const TargetRegisterInfo *TRI = MF->getTarget().getRegisterInfo(); 00201 if (!livein_empty()) { 00202 OS << "Live Ins:"; 00203 for (const_livein_iterator I = livein_begin(),E = livein_end(); I != E; ++I) 00204 OutputReg(OS, *I, TRI); 00205 OS << "\n"; 00206 } 00207 // Print the preds of this block according to the CFG. 00208 if (!pred_empty()) { 00209 OS << " Predecessors according to CFG:"; 00210 for (const_pred_iterator PI = pred_begin(), E = pred_end(); PI != E; ++PI) 00211 OS << " " << *PI << " (#" << (*PI)->getNumber() << ")"; 00212 OS << "\n"; 00213 } 00214 00215 for (const_iterator I = begin(); I != end(); ++I) { 00216 prefix(OS, *I) << "\t"; 00217 I->print(OS, &getParent()->getTarget()); 00218 } 00219 00220 // Print the successors of this block according to the CFG. 00221 if (!succ_empty()) { 00222 OS << " Successors according to CFG:"; 00223 for (const_succ_iterator SI = succ_begin(), E = succ_end(); SI != E; ++SI) 00224 OS << " " << *SI << " (#" << (*SI)->getNumber() << ")"; 00225 OS << "\n"; 00226 } 00227 } 00228 00229 void MachineBasicBlock::removeLiveIn(unsigned Reg) { 00230 livein_iterator I = std::find(livein_begin(), livein_end(), Reg); 00231 assert(I != livein_end() && "Not a live in!"); 00232 LiveIns.erase(I); 00233 } 00234 00235 bool MachineBasicBlock::isLiveIn(unsigned Reg) const { 00236 const_livein_iterator I = std::find(livein_begin(), livein_end(), Reg); 00237 return I != livein_end(); 00238 } 00239 00240 void MachineBasicBlock::moveBefore(MachineBasicBlock *NewAfter) { 00241 getParent()->splice(NewAfter, this); 00242 } 00243 00244 void MachineBasicBlock::moveAfter(MachineBasicBlock *NewBefore) { 00245 MachineFunction::iterator BBI = NewBefore; 00246 getParent()->splice(++BBI, this); 00247 } 00248 00249 00250 void MachineBasicBlock::addSuccessor(MachineBasicBlock *succ) { 00251 Successors.push_back(succ); 00252 succ->addPredecessor(this); 00253 } 00254 00255 void MachineBasicBlock::removeSuccessor(MachineBasicBlock *succ) { 00256 succ->removePredecessor(this); 00257 succ_iterator I = std::find(Successors.begin(), Successors.end(), succ); 00258 assert(I != Successors.end() && "Not a current successor!"); 00259 Successors.erase(I); 00260 } 00261 00262 MachineBasicBlock::succ_iterator 00263 MachineBasicBlock::removeSuccessor(succ_iterator I) { 00264 assert(I != Successors.end() && "Not a current successor!"); 00265 (*I)->removePredecessor(this); 00266 return Successors.erase(I); 00267 } 00268 00269 void MachineBasicBlock::addPredecessor(MachineBasicBlock *pred) { 00270 Predecessors.push_back(pred); 00271 } 00272 00273 void MachineBasicBlock::removePredecessor(MachineBasicBlock *pred) { 00274 std::vector<MachineBasicBlock *>::iterator I = 00275 std::find(Predecessors.begin(), Predecessors.end(), pred); 00276 assert(I != Predecessors.end() && "Pred is not a predecessor of this block!"); 00277 Predecessors.erase(I); 00278 } 00279 00280 void MachineBasicBlock::transferSuccessors(MachineBasicBlock *fromMBB) 00281 { 00282 if (this == fromMBB) 00283 return; 00284 00285 for(MachineBasicBlock::succ_iterator iter = fromMBB->succ_begin(), 00286 end = fromMBB->succ_end(); iter != end; ++iter) { 00287 addSuccessor(*iter); 00288 } 00289 while(!fromMBB->succ_empty()) 00290 fromMBB->removeSuccessor(fromMBB->succ_begin()); 00291 } 00292 00293 bool MachineBasicBlock::isSuccessor(const MachineBasicBlock *MBB) const { 00294 std::vector<MachineBasicBlock *>::const_iterator I = 00295 std::find(Successors.begin(), Successors.end(), MBB); 00296 return I != Successors.end(); 00297 } 00298 00299 bool MachineBasicBlock::isLayoutSuccessor(const MachineBasicBlock *MBB) const { 00300 MachineFunction::const_iterator I(this); 00301 return next(I) == MachineFunction::const_iterator(MBB); 00302 } 00303 00304 /// removeFromParent - This method unlinks 'this' from the containing function, 00305 /// and returns it, but does not delete it. 00306 MachineBasicBlock *MachineBasicBlock::removeFromParent() { 00307 assert(getParent() && "Not embedded in a function!"); 00308 getParent()->remove(this); 00309 return this; 00310 } 00311 00312 00313 /// eraseFromParent - This method unlinks 'this' from the containing function, 00314 /// and deletes it. 00315 void MachineBasicBlock::eraseFromParent() { 00316 assert(getParent() && "Not embedded in a function!"); 00317 getParent()->erase(this); 00318 } 00319 00320 00321 /// ReplaceUsesOfBlockWith - Given a machine basic block that branched to 00322 /// 'Old', change the code and CFG so that it branches to 'New' instead. 00323 void MachineBasicBlock::ReplaceUsesOfBlockWith(MachineBasicBlock *Old, 00324 MachineBasicBlock *New) { 00325 assert(Old != New && "Cannot replace self with self!"); 00326 00327 MachineBasicBlock::iterator I = end(); 00328 while (I != begin()) { 00329 --I; 00330 if (!I->getDesc().isTerminator()) break; 00331 00332 // Scan the operands of this machine instruction, replacing any uses of Old 00333 // with New. 00334 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 00335 if (I->getOperand(i).isMBB() && 00336 I->getOperand(i).getMBB() == Old) 00337 I->getOperand(i).setMBB(New); 00338 } 00339 00340 // Update the successor information. 00341 removeSuccessor(Old); 00342 addSuccessor(New); 00343 } 00344 00345 /// CorrectExtraCFGEdges - Various pieces of code can cause excess edges in the 00346 /// CFG to be inserted. If we have proven that MBB can only branch to DestA and 00347 /// DestB, remove any other MBB successors from the CFG. DestA and DestB can 00348 /// be null. 00349 /// Besides DestA and DestB, retain other edges leading to LandingPads 00350 /// (currently there can be only one; we don't check or require that here). 00351 /// Note it is possible that DestA and/or DestB are LandingPads. 00352 bool MachineBasicBlock::CorrectExtraCFGEdges(MachineBasicBlock *DestA, 00353 MachineBasicBlock *DestB, 00354 bool isCond) { 00355 bool MadeChange = false; 00356 bool AddedFallThrough = false; 00357 00358 MachineFunction::iterator FallThru = next(MachineFunction::iterator(this)); 00359 00360 // If this block ends with a conditional branch that falls through to its 00361 // successor, set DestB as the successor. 00362 if (isCond) { 00363 if (DestB == 0 && FallThru != getParent()->end()) { 00364 DestB = FallThru; 00365 AddedFallThrough = true; 00366 } 00367 } else { 00368 // If this is an unconditional branch with no explicit dest, it must just be 00369 // a fallthrough into DestB. 00370 if (DestA == 0 && FallThru != getParent()->end()) { 00371 DestA = FallThru; 00372 AddedFallThrough = true; 00373 } 00374 } 00375 00376 MachineBasicBlock::succ_iterator SI = succ_begin(); 00377 MachineBasicBlock *OrigDestA = DestA, *OrigDestB = DestB; 00378 while (SI != succ_end()) { 00379 if (*SI == DestA && DestA == DestB) { 00380 DestA = DestB = 0; 00381 ++SI; 00382 } else if (*SI == DestA) { 00383 DestA = 0; 00384 ++SI; 00385 } else if (*SI == DestB) { 00386 DestB = 0; 00387 ++SI; 00388 } else if ((*SI)->isLandingPad() && 00389 *SI!=OrigDestA && *SI!=OrigDestB) { 00390 ++SI; 00391 } else { 00392 // Otherwise, this is a superfluous edge, remove it. 00393 SI = removeSuccessor(SI); 00394 MadeChange = true; 00395 } 00396 } 00397 if (!AddedFallThrough) { 00398 assert(DestA == 0 && DestB == 0 && 00399 "MachineCFG is missing edges!"); 00400 } else if (isCond) { 00401 assert(DestA == 0 && "MachineCFG is missing edges!"); 00402 } 00403 return MadeChange; 00404 }