MachineBasicBlock.cpp revision 6232760ee0d566bcf09b2f20bae65c1d6e73946c
1//===-- llvm/CodeGen/MachineBasicBlock.cpp ----------------------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// Collect the sequence of machine instructions for a basic block. 11// 12//===----------------------------------------------------------------------===// 13 14#include "llvm/CodeGen/MachineBasicBlock.h" 15#include "llvm/BasicBlock.h" 16#include "llvm/CodeGen/MachineFunction.h" 17#include "llvm/Target/MRegisterInfo.h" 18#include "llvm/Target/TargetData.h" 19#include "llvm/Target/TargetInstrInfo.h" 20#include "llvm/Target/TargetMachine.h" 21#include "llvm/Support/LeakDetector.h" 22#include <algorithm> 23using namespace llvm; 24 25MachineBasicBlock::~MachineBasicBlock() { 26 LeakDetector::removeGarbageObject(this); 27} 28 29std::ostream& llvm::operator<<(std::ostream &OS, const MachineBasicBlock &MBB) { 30 MBB.print(OS); 31 return OS; 32} 33 34/// addNodeToList (MBB) - When an MBB is added to an MF, we need to update the 35/// parent pointer of the MBB, the MBB numbering, and any instructions in the 36/// MBB to be on the right operand list for registers. 37/// 38/// MBBs start out as #-1. When a MBB is added to a MachineFunction, it 39/// gets the next available unique MBB number. If it is removed from a 40/// MachineFunction, it goes back to being #-1. 41void ilist_traits<MachineBasicBlock>::addNodeToList(MachineBasicBlock* N) { 42 assert(N->getParent() == 0 && "machine instruction already in a basic block"); 43 N->setParent(Parent); 44 N->Number = Parent->addToMBBNumbering(N); 45 46 // Make sure the instructions have their operands in the reginfo lists. 47 MachineRegisterInfo &RegInfo = Parent->getRegInfo(); 48 for (MachineBasicBlock::iterator I = N->begin(), E = N->end(); I != E; ++I) 49 I->AddRegOperandsToUseLists(RegInfo); 50 51 LeakDetector::removeGarbageObject(N); 52} 53 54void ilist_traits<MachineBasicBlock>::removeNodeFromList(MachineBasicBlock* N) { 55 assert(N->getParent() != 0 && "machine instruction not in a basic block"); 56 N->getParent()->removeFromMBBNumbering(N->Number); 57 N->Number = -1; 58 N->setParent(0); 59 60 // Make sure the instructions have their operands removed from the reginfo 61 // lists. 62 for (MachineBasicBlock::iterator I = N->begin(), E = N->end(); I != E; ++I) 63 I->RemoveRegOperandsFromUseLists(); 64 65 LeakDetector::addGarbageObject(N); 66} 67 68 69MachineInstr* ilist_traits<MachineInstr>::createSentinel() { 70 MachineInstr* dummy = new MachineInstr(); 71 LeakDetector::removeGarbageObject(dummy); 72 return dummy; 73} 74 75/// addNodeToList (MI) - When we add an instruction to a basic block 76/// list, we update its parent pointer and add its operands from reg use/def 77/// lists if appropriate. 78void ilist_traits<MachineInstr>::addNodeToList(MachineInstr* N) { 79 assert(N->getParent() == 0 && "machine instruction already in a basic block"); 80 N->setParent(parent); 81 LeakDetector::removeGarbageObject(N); 82 83 // If the block is in a function, add the instruction's register operands to 84 // their corresponding use/def lists. 85 if (MachineFunction *MF = parent->getParent()) 86 N->AddRegOperandsToUseLists(MF->getRegInfo()); 87} 88 89/// removeNodeFromList (MI) - When we remove an instruction from a basic block 90/// list, we update its parent pointer and remove its operands from reg use/def 91/// lists if appropriate. 92void ilist_traits<MachineInstr>::removeNodeFromList(MachineInstr* N) { 93 assert(N->getParent() != 0 && "machine instruction not in a basic block"); 94 // If this block is in a function, remove from the use/def lists. 95 if (parent->getParent() != 0) 96 N->RemoveRegOperandsFromUseLists(); 97 98 N->setParent(0); 99 LeakDetector::addGarbageObject(N); 100} 101 102/// transferNodesFromList (MI) - When moving a range of instructions from one 103/// MBB list to another, we need to update the parent pointers and the use/def 104/// lists. 105void ilist_traits<MachineInstr>::transferNodesFromList( 106 iplist<MachineInstr, ilist_traits<MachineInstr> >& fromList, 107 ilist_iterator<MachineInstr> first, 108 ilist_iterator<MachineInstr> last) { 109 // Splice within the same MBB -> no change. 110 if (parent == fromList.parent) return; 111 112 // If splicing between two blocks within the same function, just update the 113 // parent pointers. 114 if (parent->getParent() == fromList.parent->getParent()) { 115 for (; first != last; ++first) 116 first->setParent(parent); 117 return; 118 } 119 120 // Otherwise, we have to update the parent and the use/def lists. The common 121 // case when this occurs is if we're splicing from a block in a MF to a block 122 // that is not in an MF. 123 bool HasOldMF = fromList.parent->getParent() != 0; 124 MachineFunction *NewMF = parent->getParent(); 125 126 for (; first != last; ++first) { 127 if (HasOldMF) first->RemoveRegOperandsFromUseLists(); 128 first->setParent(parent); 129 if (NewMF) first->AddRegOperandsToUseLists(NewMF->getRegInfo()); 130 } 131} 132 133MachineBasicBlock::iterator MachineBasicBlock::getFirstTerminator() { 134 iterator I = end(); 135 while (I != begin() && (--I)->getDesc()->isTerminator()) 136 ; /*noop */ 137 if (I != end() && !I->getDesc()->isTerminator()) ++I; 138 return I; 139} 140 141void MachineBasicBlock::dump() const { 142 print(*cerr.stream()); 143} 144 145static inline void OutputReg(std::ostream &os, unsigned RegNo, 146 const MRegisterInfo *MRI = 0) { 147 if (!RegNo || MRegisterInfo::isPhysicalRegister(RegNo)) { 148 if (MRI) 149 os << " %" << MRI->get(RegNo).Name; 150 else 151 os << " %mreg(" << RegNo << ")"; 152 } else 153 os << " %reg" << RegNo; 154} 155 156void MachineBasicBlock::print(std::ostream &OS) const { 157 const MachineFunction *MF = getParent(); 158 if(!MF) { 159 OS << "Can't print out MachineBasicBlock because parent MachineFunction" 160 << " is null\n"; 161 return; 162 } 163 164 const BasicBlock *LBB = getBasicBlock(); 165 OS << "\n"; 166 if (LBB) OS << LBB->getName() << ": "; 167 OS << (const void*)this 168 << ", LLVM BB @" << (const void*) LBB << ", ID#" << getNumber(); 169 if (isLandingPad()) OS << ", EH LANDING PAD"; 170 OS << ":\n"; 171 172 const MRegisterInfo *MRI = MF->getTarget().getRegisterInfo(); 173 if (!livein_empty()) { 174 OS << "Live Ins:"; 175 for (const_livein_iterator I = livein_begin(),E = livein_end(); I != E; ++I) 176 OutputReg(OS, *I, MRI); 177 OS << "\n"; 178 } 179 // Print the preds of this block according to the CFG. 180 if (!pred_empty()) { 181 OS << " Predecessors according to CFG:"; 182 for (const_pred_iterator PI = pred_begin(), E = pred_end(); PI != E; ++PI) 183 OS << " " << *PI << " (#" << (*PI)->getNumber() << ")"; 184 OS << "\n"; 185 } 186 187 for (const_iterator I = begin(); I != end(); ++I) { 188 OS << "\t"; 189 I->print(OS, &getParent()->getTarget()); 190 } 191 192 // Print the successors of this block according to the CFG. 193 if (!succ_empty()) { 194 OS << " Successors according to CFG:"; 195 for (const_succ_iterator SI = succ_begin(), E = succ_end(); SI != E; ++SI) 196 OS << " " << *SI << " (#" << (*SI)->getNumber() << ")"; 197 OS << "\n"; 198 } 199} 200 201void MachineBasicBlock::removeLiveIn(unsigned Reg) { 202 livein_iterator I = std::find(livein_begin(), livein_end(), Reg); 203 assert(I != livein_end() && "Not a live in!"); 204 LiveIns.erase(I); 205} 206 207void MachineBasicBlock::moveBefore(MachineBasicBlock *NewAfter) { 208 MachineFunction::BasicBlockListType &BBList =getParent()->getBasicBlockList(); 209 getParent()->getBasicBlockList().splice(NewAfter, BBList, this); 210} 211 212void MachineBasicBlock::moveAfter(MachineBasicBlock *NewBefore) { 213 MachineFunction::BasicBlockListType &BBList =getParent()->getBasicBlockList(); 214 MachineFunction::iterator BBI = NewBefore; 215 getParent()->getBasicBlockList().splice(++BBI, BBList, this); 216} 217 218 219void MachineBasicBlock::addSuccessor(MachineBasicBlock *succ) { 220 Successors.push_back(succ); 221 succ->addPredecessor(this); 222} 223 224void MachineBasicBlock::removeSuccessor(MachineBasicBlock *succ) { 225 succ->removePredecessor(this); 226 succ_iterator I = std::find(Successors.begin(), Successors.end(), succ); 227 assert(I != Successors.end() && "Not a current successor!"); 228 Successors.erase(I); 229} 230 231MachineBasicBlock::succ_iterator 232MachineBasicBlock::removeSuccessor(succ_iterator I) { 233 assert(I != Successors.end() && "Not a current successor!"); 234 (*I)->removePredecessor(this); 235 return(Successors.erase(I)); 236} 237 238void MachineBasicBlock::addPredecessor(MachineBasicBlock *pred) { 239 Predecessors.push_back(pred); 240} 241 242void MachineBasicBlock::removePredecessor(MachineBasicBlock *pred) { 243 std::vector<MachineBasicBlock *>::iterator I = 244 std::find(Predecessors.begin(), Predecessors.end(), pred); 245 assert(I != Predecessors.end() && "Pred is not a predecessor of this block!"); 246 Predecessors.erase(I); 247} 248 249bool MachineBasicBlock::isSuccessor(MachineBasicBlock *MBB) const { 250 std::vector<MachineBasicBlock *>::const_iterator I = 251 std::find(Successors.begin(), Successors.end(), MBB); 252 return I != Successors.end(); 253} 254 255/// ReplaceUsesOfBlockWith - Given a machine basic block that branched to 256/// 'Old', change the code and CFG so that it branches to 'New' instead. 257void MachineBasicBlock::ReplaceUsesOfBlockWith(MachineBasicBlock *Old, 258 MachineBasicBlock *New) { 259 assert(Old != New && "Cannot replace self with self!"); 260 261 MachineBasicBlock::iterator I = end(); 262 while (I != begin()) { 263 --I; 264 if (!I->getDesc()->isTerminator()) break; 265 266 // Scan the operands of this machine instruction, replacing any uses of Old 267 // with New. 268 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 269 if (I->getOperand(i).isMBB() && I->getOperand(i).getMBB() == Old) 270 I->getOperand(i).setMBB(New); 271 } 272 273 // Update the successor information. If New was already a successor, just 274 // remove the link to Old instead of creating another one. PR 1444. 275 removeSuccessor(Old); 276 if (!isSuccessor(New)) 277 addSuccessor(New); 278} 279 280/// CorrectExtraCFGEdges - Various pieces of code can cause excess edges in the 281/// CFG to be inserted. If we have proven that MBB can only branch to DestA and 282/// DestB, remove any other MBB successors from the CFG. DestA and DestB can 283/// be null. 284/// Besides DestA and DestB, retain other edges leading to LandingPads 285/// (currently there can be only one; we don't check or require that here). 286/// Note it is possible that DestA and/or DestB are LandingPads. 287bool MachineBasicBlock::CorrectExtraCFGEdges(MachineBasicBlock *DestA, 288 MachineBasicBlock *DestB, 289 bool isCond) { 290 bool MadeChange = false; 291 bool AddedFallThrough = false; 292 293 MachineBasicBlock *FallThru = getNext(); 294 295 // If this block ends with a conditional branch that falls through to its 296 // successor, set DestB as the successor. 297 if (isCond) { 298 if (DestB == 0 && FallThru != getParent()->end()) { 299 DestB = FallThru; 300 AddedFallThrough = true; 301 } 302 } else { 303 // If this is an unconditional branch with no explicit dest, it must just be 304 // a fallthrough into DestB. 305 if (DestA == 0 && FallThru != getParent()->end()) { 306 DestA = FallThru; 307 AddedFallThrough = true; 308 } 309 } 310 311 MachineBasicBlock::succ_iterator SI = succ_begin(); 312 MachineBasicBlock *OrigDestA = DestA, *OrigDestB = DestB; 313 while (SI != succ_end()) { 314 if (*SI == DestA && DestA == DestB) { 315 DestA = DestB = 0; 316 ++SI; 317 } else if (*SI == DestA) { 318 DestA = 0; 319 ++SI; 320 } else if (*SI == DestB) { 321 DestB = 0; 322 ++SI; 323 } else if ((*SI)->isLandingPad() && 324 *SI!=OrigDestA && *SI!=OrigDestB) { 325 ++SI; 326 } else { 327 // Otherwise, this is a superfluous edge, remove it. 328 SI = removeSuccessor(SI); 329 MadeChange = true; 330 } 331 } 332 if (!AddedFallThrough) { 333 assert(DestA == 0 && DestB == 0 && 334 "MachineCFG is missing edges!"); 335 } else if (isCond) { 336 assert(DestA == 0 && "MachineCFG is missing edges!"); 337 } 338 return MadeChange; 339} 340