MachineBasicBlock.h revision 8c741b8064f1116d8d8dc435b60b75abdf5c4d57
1//===-- llvm/CodeGen/MachineBasicBlock.h ------------------------*- 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#ifndef LLVM_CODEGEN_MACHINEBASICBLOCK_H 15#define LLVM_CODEGEN_MACHINEBASICBLOCK_H 16 17#include "llvm/CodeGen/MachineInstr.h" 18#include "llvm/ADT/GraphTraits.h" 19#include "llvm/Support/DataTypes.h" 20#include <functional> 21 22namespace llvm { 23 24class Pass; 25class BasicBlock; 26class MachineFunction; 27class MCSymbol; 28class SlotIndexes; 29class StringRef; 30class raw_ostream; 31class MachineBranchProbabilityInfo; 32 33template <> 34struct ilist_traits<MachineInstr> : public ilist_default_traits<MachineInstr> { 35private: 36 mutable ilist_half_node<MachineInstr> Sentinel; 37 38 // this is only set by the MachineBasicBlock owning the LiveList 39 friend class MachineBasicBlock; 40 MachineBasicBlock* Parent; 41 42public: 43 MachineInstr *createSentinel() const { 44 return static_cast<MachineInstr*>(&Sentinel); 45 } 46 void destroySentinel(MachineInstr *) const {} 47 48 MachineInstr *provideInitialHead() const { return createSentinel(); } 49 MachineInstr *ensureHead(MachineInstr*) const { return createSentinel(); } 50 static void noteHead(MachineInstr*, MachineInstr*) {} 51 52 void addNodeToList(MachineInstr* N); 53 void removeNodeFromList(MachineInstr* N); 54 void transferNodesFromList(ilist_traits &SrcTraits, 55 ilist_iterator<MachineInstr> first, 56 ilist_iterator<MachineInstr> last); 57 void deleteNode(MachineInstr *N); 58private: 59 void createNode(const MachineInstr &); 60}; 61 62class MachineBasicBlock : public ilist_node<MachineBasicBlock> { 63 typedef ilist<MachineInstr> Instructions; 64 Instructions Insts; 65 const BasicBlock *BB; 66 int Number; 67 MachineFunction *xParent; 68 69 /// Predecessors/Successors - Keep track of the predecessor / successor 70 /// basicblocks. 71 std::vector<MachineBasicBlock *> Predecessors; 72 std::vector<MachineBasicBlock *> Successors; 73 74 75 /// Weights - Keep track of the weights to the successors. This vector 76 /// has the same order as Successors, or it is empty if we don't use it 77 /// (disable optimization). 78 std::vector<uint32_t> Weights; 79 typedef std::vector<uint32_t>::iterator weight_iterator; 80 81 /// LiveIns - Keep track of the physical registers that are livein of 82 /// the basicblock. 83 std::vector<unsigned> LiveIns; 84 85 /// Alignment - Alignment of the basic block. Zero if the basic block does 86 /// not need to be aligned. 87 /// The alignment is specified as log2(bytes). 88 unsigned Alignment; 89 90 /// IsLandingPad - Indicate that this basic block is entered via an 91 /// exception handler. 92 bool IsLandingPad; 93 94 /// AddressTaken - Indicate that this basic block is potentially the 95 /// target of an indirect branch. 96 bool AddressTaken; 97 98 // Intrusive list support 99 MachineBasicBlock() {} 100 101 explicit MachineBasicBlock(MachineFunction &mf, const BasicBlock *bb); 102 103 ~MachineBasicBlock(); 104 105 // MachineBasicBlocks are allocated and owned by MachineFunction. 106 friend class MachineFunction; 107 108public: 109 /// getBasicBlock - Return the LLVM basic block that this instance 110 /// corresponded to originally. Note that this may be NULL if this instance 111 /// does not correspond directly to an LLVM basic block. 112 /// 113 const BasicBlock *getBasicBlock() const { return BB; } 114 115 /// getName - Return the name of the corresponding LLVM basic block, or 116 /// "(null)". 117 StringRef getName() const; 118 119 /// hasAddressTaken - Test whether this block is potentially the target 120 /// of an indirect branch. 121 bool hasAddressTaken() const { return AddressTaken; } 122 123 /// setHasAddressTaken - Set this block to reflect that it potentially 124 /// is the target of an indirect branch. 125 void setHasAddressTaken() { AddressTaken = true; } 126 127 /// getParent - Return the MachineFunction containing this basic block. 128 /// 129 const MachineFunction *getParent() const { return xParent; } 130 MachineFunction *getParent() { return xParent; } 131 132 typedef Instructions::iterator iterator; 133 typedef Instructions::const_iterator const_iterator; 134 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 135 typedef std::reverse_iterator<iterator> reverse_iterator; 136 137 unsigned size() const { return (unsigned)Insts.size(); } 138 bool empty() const { return Insts.empty(); } 139 140 MachineInstr& front() { return Insts.front(); } 141 MachineInstr& back() { return Insts.back(); } 142 const MachineInstr& front() const { return Insts.front(); } 143 const MachineInstr& back() const { return Insts.back(); } 144 145 iterator begin() { return Insts.begin(); } 146 const_iterator begin() const { return Insts.begin(); } 147 iterator end() { return Insts.end(); } 148 const_iterator end() const { return Insts.end(); } 149 reverse_iterator rbegin() { return Insts.rbegin(); } 150 const_reverse_iterator rbegin() const { return Insts.rbegin(); } 151 reverse_iterator rend () { return Insts.rend(); } 152 const_reverse_iterator rend () const { return Insts.rend(); } 153 154 // Machine-CFG iterators 155 typedef std::vector<MachineBasicBlock *>::iterator pred_iterator; 156 typedef std::vector<MachineBasicBlock *>::const_iterator const_pred_iterator; 157 typedef std::vector<MachineBasicBlock *>::iterator succ_iterator; 158 typedef std::vector<MachineBasicBlock *>::const_iterator const_succ_iterator; 159 typedef std::vector<MachineBasicBlock *>::reverse_iterator 160 pred_reverse_iterator; 161 typedef std::vector<MachineBasicBlock *>::const_reverse_iterator 162 const_pred_reverse_iterator; 163 typedef std::vector<MachineBasicBlock *>::reverse_iterator 164 succ_reverse_iterator; 165 typedef std::vector<MachineBasicBlock *>::const_reverse_iterator 166 const_succ_reverse_iterator; 167 168 pred_iterator pred_begin() { return Predecessors.begin(); } 169 const_pred_iterator pred_begin() const { return Predecessors.begin(); } 170 pred_iterator pred_end() { return Predecessors.end(); } 171 const_pred_iterator pred_end() const { return Predecessors.end(); } 172 pred_reverse_iterator pred_rbegin() 173 { return Predecessors.rbegin();} 174 const_pred_reverse_iterator pred_rbegin() const 175 { return Predecessors.rbegin();} 176 pred_reverse_iterator pred_rend() 177 { return Predecessors.rend(); } 178 const_pred_reverse_iterator pred_rend() const 179 { return Predecessors.rend(); } 180 unsigned pred_size() const { 181 return (unsigned)Predecessors.size(); 182 } 183 bool pred_empty() const { return Predecessors.empty(); } 184 succ_iterator succ_begin() { return Successors.begin(); } 185 const_succ_iterator succ_begin() const { return Successors.begin(); } 186 succ_iterator succ_end() { return Successors.end(); } 187 const_succ_iterator succ_end() const { return Successors.end(); } 188 succ_reverse_iterator succ_rbegin() 189 { return Successors.rbegin(); } 190 const_succ_reverse_iterator succ_rbegin() const 191 { return Successors.rbegin(); } 192 succ_reverse_iterator succ_rend() 193 { return Successors.rend(); } 194 const_succ_reverse_iterator succ_rend() const 195 { return Successors.rend(); } 196 unsigned succ_size() const { 197 return (unsigned)Successors.size(); 198 } 199 bool succ_empty() const { return Successors.empty(); } 200 201 // LiveIn management methods. 202 203 /// addLiveIn - Add the specified register as a live in. Note that it 204 /// is an error to add the same register to the same set more than once. 205 void addLiveIn(unsigned Reg) { LiveIns.push_back(Reg); } 206 207 /// removeLiveIn - Remove the specified register from the live in set. 208 /// 209 void removeLiveIn(unsigned Reg); 210 211 /// isLiveIn - Return true if the specified register is in the live in set. 212 /// 213 bool isLiveIn(unsigned Reg) const; 214 215 // Iteration support for live in sets. These sets are kept in sorted 216 // order by their register number. 217 typedef std::vector<unsigned>::const_iterator livein_iterator; 218 livein_iterator livein_begin() const { return LiveIns.begin(); } 219 livein_iterator livein_end() const { return LiveIns.end(); } 220 bool livein_empty() const { return LiveIns.empty(); } 221 222 /// getAlignment - Return alignment of the basic block. 223 /// The alignment is specified as log2(bytes). 224 /// 225 unsigned getAlignment() const { return Alignment; } 226 227 /// setAlignment - Set alignment of the basic block. 228 /// The alignment is specified as log2(bytes). 229 /// 230 void setAlignment(unsigned Align) { Alignment = Align; } 231 232 /// isLandingPad - Returns true if the block is a landing pad. That is 233 /// this basic block is entered via an exception handler. 234 bool isLandingPad() const { return IsLandingPad; } 235 236 /// setIsLandingPad - Indicates the block is a landing pad. That is 237 /// this basic block is entered via an exception handler. 238 void setIsLandingPad(bool V = true) { IsLandingPad = V; } 239 240 /// getLandingPadSuccessor - If this block has a successor that is a landing 241 /// pad, return it. Otherwise return NULL. 242 const MachineBasicBlock *getLandingPadSuccessor() const; 243 244 // Code Layout methods. 245 246 /// moveBefore/moveAfter - move 'this' block before or after the specified 247 /// block. This only moves the block, it does not modify the CFG or adjust 248 /// potential fall-throughs at the end of the block. 249 void moveBefore(MachineBasicBlock *NewAfter); 250 void moveAfter(MachineBasicBlock *NewBefore); 251 252 /// updateTerminator - Update the terminator instructions in block to account 253 /// for changes to the layout. If the block previously used a fallthrough, 254 /// it may now need a branch, and if it previously used branching it may now 255 /// be able to use a fallthrough. 256 void updateTerminator(); 257 258 // Machine-CFG mutators 259 260 /// addSuccessor - Add succ as a successor of this MachineBasicBlock. 261 /// The Predecessors list of succ is automatically updated. WEIGHT 262 /// parameter is stored in Weights list and it may be used by 263 /// MachineBranchProbabilityInfo analysis to calculate branch probability. 264 /// 265 void addSuccessor(MachineBasicBlock *succ, uint32_t weight = 0); 266 267 /// removeSuccessor - Remove successor from the successors list of this 268 /// MachineBasicBlock. The Predecessors list of succ is automatically updated. 269 /// 270 void removeSuccessor(MachineBasicBlock *succ); 271 272 /// removeSuccessor - Remove specified successor from the successors list of 273 /// this MachineBasicBlock. The Predecessors list of succ is automatically 274 /// updated. Return the iterator to the element after the one removed. 275 /// 276 succ_iterator removeSuccessor(succ_iterator I); 277 278 /// replaceSuccessor - Replace successor OLD with NEW and update weight info. 279 /// 280 void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New); 281 282 283 /// transferSuccessors - Transfers all the successors from MBB to this 284 /// machine basic block (i.e., copies all the successors fromMBB and 285 /// remove all the successors from fromMBB). 286 void transferSuccessors(MachineBasicBlock *fromMBB); 287 288 /// transferSuccessorsAndUpdatePHIs - Transfers all the successors, as 289 /// in transferSuccessors, and update PHI operands in the successor blocks 290 /// which refer to fromMBB to refer to this. 291 void transferSuccessorsAndUpdatePHIs(MachineBasicBlock *fromMBB); 292 293 /// isSuccessor - Return true if the specified MBB is a successor of this 294 /// block. 295 bool isSuccessor(const MachineBasicBlock *MBB) const; 296 297 /// isLayoutSuccessor - Return true if the specified MBB will be emitted 298 /// immediately after this block, such that if this block exits by 299 /// falling through, control will transfer to the specified MBB. Note 300 /// that MBB need not be a successor at all, for example if this block 301 /// ends with an unconditional branch to some other block. 302 bool isLayoutSuccessor(const MachineBasicBlock *MBB) const; 303 304 /// canFallThrough - Return true if the block can implicitly transfer 305 /// control to the block after it by falling off the end of it. This should 306 /// return false if it can reach the block after it, but it uses an explicit 307 /// branch to do so (e.g., a table jump). True is a conservative answer. 308 bool canFallThrough(); 309 310 /// Returns a pointer to the first instructon in this block that is not a 311 /// PHINode instruction. When adding instruction to the beginning of the 312 /// basic block, they should be added before the returned value, not before 313 /// the first instruction, which might be PHI. 314 /// Returns end() is there's no non-PHI instruction. 315 iterator getFirstNonPHI(); 316 317 /// SkipPHIsAndLabels - Return the first instruction in MBB after I that is 318 /// not a PHI or a label. This is the correct point to insert copies at the 319 /// beginning of a basic block. 320 iterator SkipPHIsAndLabels(iterator I); 321 322 /// getFirstTerminator - returns an iterator to the first terminator 323 /// instruction of this basic block. If a terminator does not exist, 324 /// it returns end() 325 iterator getFirstTerminator(); 326 327 const_iterator getFirstTerminator() const { 328 return const_cast<MachineBasicBlock*>(this)->getFirstTerminator(); 329 } 330 331 /// getLastNonDebugInstr - returns an iterator to the last non-debug 332 /// instruction in the basic block, or end() 333 iterator getLastNonDebugInstr(); 334 335 const_iterator getLastNonDebugInstr() const { 336 return const_cast<MachineBasicBlock*>(this)->getLastNonDebugInstr(); 337 } 338 339 /// SplitCriticalEdge - Split the critical edge from this block to the 340 /// given successor block, and return the newly created block, or null 341 /// if splitting is not possible. 342 /// 343 /// This function updates LiveVariables, MachineDominatorTree, and 344 /// MachineLoopInfo, as applicable. 345 MachineBasicBlock *SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P); 346 347 void pop_front() { Insts.pop_front(); } 348 void pop_back() { Insts.pop_back(); } 349 void push_back(MachineInstr *MI) { Insts.push_back(MI); } 350 template<typename IT> 351 void insert(iterator I, IT S, IT E) { Insts.insert(I, S, E); } 352 iterator insert(iterator I, MachineInstr *M) { return Insts.insert(I, M); } 353 iterator insertAfter(iterator I, MachineInstr *M) { 354 return Insts.insertAfter(I, M); 355 } 356 357 // erase - Remove the specified element or range from the instruction list. 358 // These functions delete any instructions removed. 359 // 360 iterator erase(iterator I) { return Insts.erase(I); } 361 iterator erase(iterator I, iterator E) { return Insts.erase(I, E); } 362 MachineInstr *remove(MachineInstr *I) { return Insts.remove(I); } 363 void clear() { Insts.clear(); } 364 365 /// splice - Take an instruction from MBB 'Other' at the position From, 366 /// and insert it into this MBB right before 'where'. 367 void splice(iterator where, MachineBasicBlock *Other, iterator From) { 368 Insts.splice(where, Other->Insts, From); 369 } 370 371 /// splice - Take a block of instructions from MBB 'Other' in the range [From, 372 /// To), and insert them into this MBB right before 'where'. 373 void splice(iterator where, MachineBasicBlock *Other, iterator From, 374 iterator To) { 375 Insts.splice(where, Other->Insts, From, To); 376 } 377 378 /// removeFromParent - This method unlinks 'this' from the containing 379 /// function, and returns it, but does not delete it. 380 MachineBasicBlock *removeFromParent(); 381 382 /// eraseFromParent - This method unlinks 'this' from the containing 383 /// function and deletes it. 384 void eraseFromParent(); 385 386 /// ReplaceUsesOfBlockWith - Given a machine basic block that branched to 387 /// 'Old', change the code and CFG so that it branches to 'New' instead. 388 void ReplaceUsesOfBlockWith(MachineBasicBlock *Old, MachineBasicBlock *New); 389 390 /// CorrectExtraCFGEdges - Various pieces of code can cause excess edges in 391 /// the CFG to be inserted. If we have proven that MBB can only branch to 392 /// DestA and DestB, remove any other MBB successors from the CFG. DestA and 393 /// DestB can be null. Besides DestA and DestB, retain other edges leading 394 /// to LandingPads (currently there can be only one; we don't check or require 395 /// that here). Note it is possible that DestA and/or DestB are LandingPads. 396 bool CorrectExtraCFGEdges(MachineBasicBlock *DestA, 397 MachineBasicBlock *DestB, 398 bool isCond); 399 400 /// findDebugLoc - find the next valid DebugLoc starting at MBBI, skipping 401 /// any DBG_VALUE instructions. Return UnknownLoc if there is none. 402 DebugLoc findDebugLoc(MachineBasicBlock::iterator &MBBI); 403 404 // Debugging methods. 405 void dump() const; 406 void print(raw_ostream &OS, SlotIndexes* = 0) const; 407 408 /// getNumber - MachineBasicBlocks are uniquely numbered at the function 409 /// level, unless they're not in a MachineFunction yet, in which case this 410 /// will return -1. 411 /// 412 int getNumber() const { return Number; } 413 void setNumber(int N) { Number = N; } 414 415 /// getSymbol - Return the MCSymbol for this basic block. 416 /// 417 MCSymbol *getSymbol() const; 418 419 420private: 421 /// getWeightIterator - Return weight iterator corresponding to the I 422 /// successor iterator. 423 weight_iterator getWeightIterator(succ_iterator I); 424 425 friend class MachineBranchProbabilityInfo; 426 427 /// getSuccWeight - Return weight of the edge from this block to MBB. This 428 /// method should NOT be called directly, but by using getEdgeWeight method 429 /// from MachineBranchProbabilityInfo class. 430 uint32_t getSuccWeight(MachineBasicBlock *succ); 431 432 433 // Methods used to maintain doubly linked list of blocks... 434 friend struct ilist_traits<MachineBasicBlock>; 435 436 // Machine-CFG mutators 437 438 /// addPredecessor - Remove pred as a predecessor of this MachineBasicBlock. 439 /// Don't do this unless you know what you're doing, because it doesn't 440 /// update pred's successors list. Use pred->addSuccessor instead. 441 /// 442 void addPredecessor(MachineBasicBlock *pred); 443 444 /// removePredecessor - Remove pred as a predecessor of this 445 /// MachineBasicBlock. Don't do this unless you know what you're 446 /// doing, because it doesn't update pred's successors list. Use 447 /// pred->removeSuccessor instead. 448 /// 449 void removePredecessor(MachineBasicBlock *pred); 450}; 451 452raw_ostream& operator<<(raw_ostream &OS, const MachineBasicBlock &MBB); 453 454void WriteAsOperand(raw_ostream &, const MachineBasicBlock*, bool t); 455 456// This is useful when building IndexedMaps keyed on basic block pointers. 457struct MBB2NumberFunctor : 458 public std::unary_function<const MachineBasicBlock*, unsigned> { 459 unsigned operator()(const MachineBasicBlock *MBB) const { 460 return MBB->getNumber(); 461 } 462}; 463 464//===--------------------------------------------------------------------===// 465// GraphTraits specializations for machine basic block graphs (machine-CFGs) 466//===--------------------------------------------------------------------===// 467 468// Provide specializations of GraphTraits to be able to treat a 469// MachineFunction as a graph of MachineBasicBlocks... 470// 471 472template <> struct GraphTraits<MachineBasicBlock *> { 473 typedef MachineBasicBlock NodeType; 474 typedef MachineBasicBlock::succ_iterator ChildIteratorType; 475 476 static NodeType *getEntryNode(MachineBasicBlock *BB) { return BB; } 477 static inline ChildIteratorType child_begin(NodeType *N) { 478 return N->succ_begin(); 479 } 480 static inline ChildIteratorType child_end(NodeType *N) { 481 return N->succ_end(); 482 } 483}; 484 485template <> struct GraphTraits<const MachineBasicBlock *> { 486 typedef const MachineBasicBlock NodeType; 487 typedef MachineBasicBlock::const_succ_iterator ChildIteratorType; 488 489 static NodeType *getEntryNode(const MachineBasicBlock *BB) { return BB; } 490 static inline ChildIteratorType child_begin(NodeType *N) { 491 return N->succ_begin(); 492 } 493 static inline ChildIteratorType child_end(NodeType *N) { 494 return N->succ_end(); 495 } 496}; 497 498// Provide specializations of GraphTraits to be able to treat a 499// MachineFunction as a graph of MachineBasicBlocks... and to walk it 500// in inverse order. Inverse order for a function is considered 501// to be when traversing the predecessor edges of a MBB 502// instead of the successor edges. 503// 504template <> struct GraphTraits<Inverse<MachineBasicBlock*> > { 505 typedef MachineBasicBlock NodeType; 506 typedef MachineBasicBlock::pred_iterator ChildIteratorType; 507 static NodeType *getEntryNode(Inverse<MachineBasicBlock *> G) { 508 return G.Graph; 509 } 510 static inline ChildIteratorType child_begin(NodeType *N) { 511 return N->pred_begin(); 512 } 513 static inline ChildIteratorType child_end(NodeType *N) { 514 return N->pred_end(); 515 } 516}; 517 518template <> struct GraphTraits<Inverse<const MachineBasicBlock*> > { 519 typedef const MachineBasicBlock NodeType; 520 typedef MachineBasicBlock::const_pred_iterator ChildIteratorType; 521 static NodeType *getEntryNode(Inverse<const MachineBasicBlock*> G) { 522 return G.Graph; 523 } 524 static inline ChildIteratorType child_begin(NodeType *N) { 525 return N->pred_begin(); 526 } 527 static inline ChildIteratorType child_end(NodeType *N) { 528 return N->pred_end(); 529 } 530}; 531 532} // End llvm namespace 533 534#endif 535