llvm.org GIT mirror llvm / cf0db29 include / llvm / CodeGen / MachineBasicBlock.h
cf0db29

Tree @cf0db29 (Download .tar.gz)

MachineBasicBlock.h @cf0db29raw · history · blame

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
//===-- llvm/CodeGen/MachineBasicBlock.h ------------------------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// Collect the sequence of machine instructions for a basic block.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_CODEGEN_MACHINEBASICBLOCK_H
#define LLVM_CODEGEN_MACHINEBASICBLOCK_H

#include "llvm/ADT/GraphTraits.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/Support/DataTypes.h"
#include <functional>

namespace llvm {

class Pass;
class BasicBlock;
class MachineFunction;
class MCSymbol;
class SlotIndexes;
class StringRef;
class raw_ostream;
class MachineBranchProbabilityInfo;

template <>
struct ilist_traits<MachineInstr> : public ilist_default_traits<MachineInstr> {
private:
  mutable ilist_half_node<MachineInstr> Sentinel;

  // this is only set by the MachineBasicBlock owning the LiveList
  friend class MachineBasicBlock;
  MachineBasicBlock* Parent;

public:
  MachineInstr *createSentinel() const {
    return static_cast<MachineInstr*>(&Sentinel);
  }
  void destroySentinel(MachineInstr *) const {}

  MachineInstr *provideInitialHead() const { return createSentinel(); }
  MachineInstr *ensureHead(MachineInstr*) const { return createSentinel(); }
  static void noteHead(MachineInstr*, MachineInstr*) {}

  void addNodeToList(MachineInstr* N);
  void removeNodeFromList(MachineInstr* N);
  void transferNodesFromList(ilist_traits &SrcTraits,
                             ilist_iterator<MachineInstr> first,
                             ilist_iterator<MachineInstr> last);
  void deleteNode(MachineInstr *N);
private:
  void createNode(const MachineInstr &);
};

class MachineBasicBlock : public ilist_node<MachineBasicBlock> {
  typedef ilist<MachineInstr> Instructions;
  Instructions Insts;
  const BasicBlock *BB;
  int Number;
  MachineFunction *xParent;

  /// Predecessors/Successors - Keep track of the predecessor / successor
  /// basicblocks.
  std::vector<MachineBasicBlock *> Predecessors;
  std::vector<MachineBasicBlock *> Successors;

  /// Weights - Keep track of the weights to the successors. This vector
  /// has the same order as Successors, or it is empty if we don't use it
  /// (disable optimization).
  std::vector<uint32_t> Weights;
  typedef std::vector<uint32_t>::iterator weight_iterator;
  typedef std::vector<uint32_t>::const_iterator const_weight_iterator;

  /// LiveIns - Keep track of the physical registers that are livein of
  /// the basicblock.
  std::vector<unsigned> LiveIns;

  /// Alignment - Alignment of the basic block. Zero if the basic block does
  /// not need to be aligned.
  /// The alignment is specified as log2(bytes).
  unsigned Alignment;

  /// IsLandingPad - Indicate that this basic block is entered via an
  /// exception handler.
  bool IsLandingPad;

  /// AddressTaken - Indicate that this basic block is potentially the
  /// target of an indirect branch.
  bool AddressTaken;

  /// \brief since getSymbol is a relatively heavy-weight operation, the symbol
  /// is only computed once and is cached.
  mutable MCSymbol *CachedMCSymbol;

  // Intrusive list support
  MachineBasicBlock() {}

  explicit MachineBasicBlock(MachineFunction &mf, const BasicBlock *bb);

  ~MachineBasicBlock();

  // MachineBasicBlocks are allocated and owned by MachineFunction.
  friend class MachineFunction;

public:
  /// getBasicBlock - Return the LLVM basic block that this instance
  /// corresponded to originally. Note that this may be NULL if this instance
  /// does not correspond directly to an LLVM basic block.
  ///
  const BasicBlock *getBasicBlock() const { return BB; }

  /// getName - Return the name of the corresponding LLVM basic block, or
  /// "(null)".
  StringRef getName() const;

  /// getFullName - Return a formatted string to identify this block and its
  /// parent function.
  std::string getFullName() const;

  /// hasAddressTaken - Test whether this block is potentially the target
  /// of an indirect branch.
  bool hasAddressTaken() const { return AddressTaken; }

  /// setHasAddressTaken - Set this block to reflect that it potentially
  /// is the target of an indirect branch.
  void setHasAddressTaken() { AddressTaken = true; }

  /// getParent - Return the MachineFunction containing this basic block.
  ///
  const MachineFunction *getParent() const { return xParent; }
  MachineFunction *getParent() { return xParent; }


  /// bundle_iterator - MachineBasicBlock iterator that automatically skips over
  /// MIs that are inside bundles (i.e. walk top level MIs only).
  template<typename Ty, typename IterTy>
  class bundle_iterator
    : public std::iterator<std::bidirectional_iterator_tag, Ty, ptrdiff_t> {
    IterTy MII;

  public:
    bundle_iterator(IterTy mii) : MII(mii) {}

    bundle_iterator(Ty &mi) : MII(mi) {
      assert(!mi.isBundledWithPred() &&
             "It's not legal to initialize bundle_iterator with a bundled MI");
    }
    bundle_iterator(Ty *mi) : MII(mi) {
      assert((!mi || !mi->isBundledWithPred()) &&
             "It's not legal to initialize bundle_iterator with a bundled MI");
    }
    // Template allows conversion from const to nonconst.
    template<class OtherTy, class OtherIterTy>
    bundle_iterator(const bundle_iterator<OtherTy, OtherIterTy> &I)
      : MII(I.getInstrIterator()) {}
    bundle_iterator() : MII(nullptr) {}

    Ty &operator*() const { return *MII; }
    Ty *operator->() const { return &operator*(); }

    operator Ty*() const { return MII; }

    bool operator==(const bundle_iterator &x) const {
      return MII == x.MII;
    }
    bool operator!=(const bundle_iterator &x) const {
      return !operator==(x);
    }

    // Increment and decrement operators...
    bundle_iterator &operator--() {      // predecrement - Back up
      do --MII;
      while (MII->isBundledWithPred());
      return *this;
    }
    bundle_iterator &operator++() {      // preincrement - Advance
      while (MII->isBundledWithSucc())
        ++MII;
      ++MII;
      return *this;
    }
    bundle_iterator operator--(int) {    // postdecrement operators...
      bundle_iterator tmp = *this;
      --*this;
      return tmp;
    }
    bundle_iterator operator++(int) {    // postincrement operators...
      bundle_iterator tmp = *this;
      ++*this;
      return tmp;
    }

    IterTy getInstrIterator() const {
      return MII;
    }
  };

  typedef Instructions::iterator                                 instr_iterator;
  typedef Instructions::const_iterator                     const_instr_iterator;
  typedef std::reverse_iterator<instr_iterator>          reverse_instr_iterator;
  typedef
  std::reverse_iterator<const_instr_iterator>      const_reverse_instr_iterator;

  typedef
  bundle_iterator<MachineInstr,instr_iterator>                         iterator;
  typedef
  bundle_iterator<const MachineInstr,const_instr_iterator>       const_iterator;
  typedef std::reverse_iterator<const_iterator>          const_reverse_iterator;
  typedef std::reverse_iterator<iterator>                      reverse_iterator;


  unsigned size() const { return (unsigned)Insts.size(); }
  bool empty() const { return Insts.empty(); }

  MachineInstr       &instr_front()       { return Insts.front(); }
  MachineInstr       &instr_back()        { return Insts.back();  }
  const MachineInstr &instr_front() const { return Insts.front(); }
  const MachineInstr &instr_back()  const { return Insts.back();  }

  MachineInstr       &front()             { return Insts.front(); }
  MachineInstr       &back()              { return *--end();      }
  const MachineInstr &front()       const { return Insts.front(); }
  const MachineInstr &back()        const { return *--end();      }

  instr_iterator                instr_begin()       { return Insts.begin();  }
  const_instr_iterator          instr_begin() const { return Insts.begin();  }
  instr_iterator                  instr_end()       { return Insts.end();    }
  const_instr_iterator            instr_end() const { return Insts.end();    }
  reverse_instr_iterator       instr_rbegin()       { return Insts.rbegin(); }
  const_reverse_instr_iterator instr_rbegin() const { return Insts.rbegin(); }
  reverse_instr_iterator       instr_rend  ()       { return Insts.rend();   }
  const_reverse_instr_iterator instr_rend  () const { return Insts.rend();   }

  iterator                begin()       { return instr_begin();  }
  const_iterator          begin() const { return instr_begin();  }
  iterator                end  ()       { return instr_end();    }
  const_iterator          end  () const { return instr_end();    }
  reverse_iterator       rbegin()       { return instr_rbegin(); }
  const_reverse_iterator rbegin() const { return instr_rbegin(); }
  reverse_iterator       rend  ()       { return instr_rend();   }
  const_reverse_iterator rend  () const { return instr_rend();   }

  inline iterator_range<iterator> terminators() {
    return iterator_range<iterator>(getFirstTerminator(), end());
  }
  inline iterator_range<const_iterator> terminators() const {
    return iterator_range<const_iterator>(getFirstTerminator(), end());
  }

  // Machine-CFG iterators
  typedef std::vector<MachineBasicBlock *>::iterator       pred_iterator;
  typedef std::vector<MachineBasicBlock *>::const_iterator const_pred_iterator;
  typedef std::vector<MachineBasicBlock *>::iterator       succ_iterator;
  typedef std::vector<MachineBasicBlock *>::const_iterator const_succ_iterator;
  typedef std::vector<MachineBasicBlock *>::reverse_iterator
                                                         pred_reverse_iterator;
  typedef std::vector<MachineBasicBlock *>::const_reverse_iterator
                                                   const_pred_reverse_iterator;
  typedef std::vector<MachineBasicBlock *>::reverse_iterator
                                                         succ_reverse_iterator;
  typedef std::vector<MachineBasicBlock *>::const_reverse_iterator
                                                   const_succ_reverse_iterator;
  pred_iterator        pred_begin()       { return Predecessors.begin(); }
  const_pred_iterator  pred_begin() const { return Predecessors.begin(); }
  pred_iterator        pred_end()         { return Predecessors.end();   }
  const_pred_iterator  pred_end()   const { return Predecessors.end();   }
  pred_reverse_iterator        pred_rbegin()
                                          { return Predecessors.rbegin();}
  const_pred_reverse_iterator  pred_rbegin() const
                                          { return Predecessors.rbegin();}
  pred_reverse_iterator        pred_rend()
                                          { return Predecessors.rend();  }
  const_pred_reverse_iterator  pred_rend()   const
                                          { return Predecessors.rend();  }
  unsigned             pred_size()  const {
    return (unsigned)Predecessors.size();
  }
  bool                 pred_empty() const { return Predecessors.empty(); }
  succ_iterator        succ_begin()       { return Successors.begin();   }
  const_succ_iterator  succ_begin() const { return Successors.begin();   }
  succ_iterator        succ_end()         { return Successors.end();     }
  const_succ_iterator  succ_end()   const { return Successors.end();     }
  succ_reverse_iterator        succ_rbegin()
                                          { return Successors.rbegin();  }
  const_succ_reverse_iterator  succ_rbegin() const
                                          { return Successors.rbegin();  }
  succ_reverse_iterator        succ_rend()
                                          { return Successors.rend();    }
  const_succ_reverse_iterator  succ_rend()   const
                                          { return Successors.rend();    }
  unsigned             succ_size()  const {
    return (unsigned)Successors.size();
  }
  bool                 succ_empty() const { return Successors.empty();   }

  inline iterator_range<pred_iterator> predecessors() {
    return iterator_range<pred_iterator>(pred_begin(), pred_end());
  }
  inline iterator_range<const_pred_iterator> predecessors() const {
    return iterator_range<const_pred_iterator>(pred_begin(), pred_end());
  }
  inline iterator_range<succ_iterator> successors() {
    return iterator_range<succ_iterator>(succ_begin(), succ_end());
  }
  inline iterator_range<const_succ_iterator> successors() const {
    return iterator_range<const_succ_iterator>(succ_begin(), succ_end());
  }

  // LiveIn management methods.

  /// Adds the specified register as a live in. Note that it is an error to add
  /// the same register to the same set more than once unless the intention is
  /// to call sortUniqueLiveIns after all registers are added.
  void addLiveIn(unsigned Reg) { LiveIns.push_back(Reg); }

  /// Sorts and uniques the LiveIns vector. It can be significantly faster to do
  /// this than repeatedly calling isLiveIn before calling addLiveIn for every
  /// LiveIn insertion.
  void sortUniqueLiveIns() {
    std::sort(LiveIns.begin(), LiveIns.end());
    LiveIns.erase(std::unique(LiveIns.begin(), LiveIns.end()), LiveIns.end());
  }

  /// Add PhysReg as live in to this block, and ensure that there is a copy of
  /// PhysReg to a virtual register of class RC. Return the virtual register
  /// that is a copy of the live in PhysReg.
  unsigned addLiveIn(unsigned PhysReg, const TargetRegisterClass *RC);

  /// removeLiveIn - Remove the specified register from the live in set.
  ///
  void removeLiveIn(unsigned Reg);

  /// isLiveIn - Return true if the specified register is in the live in set.
  ///
  bool isLiveIn(unsigned Reg) const;

  // Iteration support for live in sets.  These sets are kept in sorted
  // order by their register number.
  typedef std::vector<unsigned>::const_iterator livein_iterator;
  livein_iterator livein_begin() const { return LiveIns.begin(); }
  livein_iterator livein_end()   const { return LiveIns.end(); }
  bool            livein_empty() const { return LiveIns.empty(); }

  /// getAlignment - Return alignment of the basic block.
  /// The alignment is specified as log2(bytes).
  ///
  unsigned getAlignment() const { return Alignment; }

  /// setAlignment - Set alignment of the basic block.
  /// The alignment is specified as log2(bytes).
  ///
  void setAlignment(unsigned Align) { Alignment = Align; }

  /// isLandingPad - Returns true if the block is a landing pad. That is
  /// this basic block is entered via an exception handler.
  bool isLandingPad() const { return IsLandingPad; }

  /// setIsLandingPad - Indicates the block is a landing pad.  That is
  /// this basic block is entered via an exception handler.
  void setIsLandingPad(bool V = true) { IsLandingPad = V; }

  /// getLandingPadSuccessor - If this block has a successor that is a landing
  /// pad, return it. Otherwise return NULL.
  const MachineBasicBlock *getLandingPadSuccessor() const;

  // Code Layout methods.

  /// moveBefore/moveAfter - move 'this' block before or after the specified
  /// block.  This only moves the block, it does not modify the CFG or adjust
  /// potential fall-throughs at the end of the block.
  void moveBefore(MachineBasicBlock *NewAfter);
  void moveAfter(MachineBasicBlock *NewBefore);

  /// updateTerminator - Update the terminator instructions in block to account
  /// for changes to the layout. If the block previously used a fallthrough,
  /// it may now need a branch, and if it previously used branching it may now
  /// be able to use a fallthrough.
  void updateTerminator();

  // Machine-CFG mutators

  /// addSuccessor - Add succ as a successor of this MachineBasicBlock.
  /// The Predecessors list of succ is automatically updated. WEIGHT
  /// parameter is stored in Weights list and it may be used by
  /// MachineBranchProbabilityInfo analysis to calculate branch probability.
  ///
  /// Note that duplicate Machine CFG edges are not allowed.
  ///
  void addSuccessor(MachineBasicBlock *succ, uint32_t weight = 0);

  /// Set successor weight of a given iterator.
  void setSuccWeight(succ_iterator I, uint32_t weight);

  /// removeSuccessor - Remove successor from the successors list of this
  /// MachineBasicBlock. The Predecessors list of succ is automatically updated.
  ///
  void removeSuccessor(MachineBasicBlock *succ);

  /// removeSuccessor - Remove specified successor from the successors list of
  /// this MachineBasicBlock. The Predecessors list of succ is automatically
  /// updated.  Return the iterator to the element after the one removed.
  ///
  succ_iterator removeSuccessor(succ_iterator I);

  /// replaceSuccessor - Replace successor OLD with NEW and update weight info.
  ///
  void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New);


  /// transferSuccessors - Transfers all the successors from MBB to this
  /// machine basic block (i.e., copies all the successors fromMBB and
  /// remove all the successors from fromMBB).
  void transferSuccessors(MachineBasicBlock *fromMBB);

  /// transferSuccessorsAndUpdatePHIs - Transfers all the successors, as
  /// in transferSuccessors, and update PHI operands in the successor blocks
  /// which refer to fromMBB to refer to this.
  void transferSuccessorsAndUpdatePHIs(MachineBasicBlock *fromMBB);

  /// isPredecessor - Return true if the specified MBB is a predecessor of this
  /// block.
  bool isPredecessor(const MachineBasicBlock *MBB) const;

  /// isSuccessor - Return true if the specified MBB is a successor of this
  /// block.
  bool isSuccessor(const MachineBasicBlock *MBB) const;

  /// isLayoutSuccessor - Return true if the specified MBB will be emitted
  /// immediately after this block, such that if this block exits by
  /// falling through, control will transfer to the specified MBB. Note
  /// that MBB need not be a successor at all, for example if this block
  /// ends with an unconditional branch to some other block.
  bool isLayoutSuccessor(const MachineBasicBlock *MBB) const;

  /// canFallThrough - Return true if the block can implicitly transfer
  /// control to the block after it by falling off the end of it.  This should
  /// return false if it can reach the block after it, but it uses an explicit
  /// branch to do so (e.g., a table jump).  True is a conservative answer.
  bool canFallThrough();

  /// Returns a pointer to the first instruction in this block that is not a
  /// PHINode instruction. When adding instructions to the beginning of the
  /// basic block, they should be added before the returned value, not before
  /// the first instruction, which might be PHI.
  /// Returns end() is there's no non-PHI instruction.
  iterator getFirstNonPHI();

  /// SkipPHIsAndLabels - Return the first instruction in MBB after I that is
  /// not a PHI or a label. This is the correct point to insert copies at the
  /// beginning of a basic block.
  iterator SkipPHIsAndLabels(iterator I);

  /// getFirstTerminator - returns an iterator to the first terminator
  /// instruction of this basic block. If a terminator does not exist,
  /// it returns end()
  iterator getFirstTerminator();
  const_iterator getFirstTerminator() const;

  /// getFirstInstrTerminator - Same getFirstTerminator but it ignores bundles
  /// and return an instr_iterator instead.
  instr_iterator getFirstInstrTerminator();

  /// getLastNonDebugInstr - returns an iterator to the last non-debug
  /// instruction in the basic block, or end()
  iterator getLastNonDebugInstr();
  const_iterator getLastNonDebugInstr() const;

  /// SplitCriticalEdge - Split the critical edge from this block to the
  /// given successor block, and return the newly created block, or null
  /// if splitting is not possible.
  ///
  /// This function updates LiveVariables, MachineDominatorTree, and
  /// MachineLoopInfo, as applicable.
  MachineBasicBlock *SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P);

  void pop_front() { Insts.pop_front(); }
  void pop_back() { Insts.pop_back(); }
  void push_back(MachineInstr *MI) { Insts.push_back(MI); }

  /// Insert MI into the instruction list before I, possibly inside a bundle.
  ///
  /// If the insertion point is inside a bundle, MI will be added to the bundle,
  /// otherwise MI will not be added to any bundle. That means this function
  /// alone can't be used to prepend or append instructions to bundles. See
  /// MIBundleBuilder::insert() for a more reliable way of doing that.
  instr_iterator insert(instr_iterator I, MachineInstr *M);

  /// Insert a range of instructions into the instruction list before I.
  template<typename IT>
  void insert(iterator I, IT S, IT E) {
    assert((I == end() || I->getParent() == this) &&
           "iterator points outside of basic block");
    Insts.insert(I.getInstrIterator(), S, E);
  }

  /// Insert MI into the instruction list before I.
  iterator insert(iterator I, MachineInstr *MI) {
    assert((I == end() || I->getParent() == this) &&
           "iterator points outside of basic block");
    assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
           "Cannot insert instruction with bundle flags");
    return Insts.insert(I.getInstrIterator(), MI);
  }

  /// Insert MI into the instruction list after I.
  iterator insertAfter(iterator I, MachineInstr *MI) {
    assert((I == end() || I->getParent() == this) &&
           "iterator points outside of basic block");
    assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
           "Cannot insert instruction with bundle flags");
    return Insts.insertAfter(I.getInstrIterator(), MI);
  }

  /// Remove an instruction from the instruction list and delete it.
  ///
  /// If the instruction is part of a bundle, the other instructions in the
  /// bundle will still be bundled after removing the single instruction.
  instr_iterator erase(instr_iterator I);

  /// Remove an instruction from the instruction list and delete it.
  ///
  /// If the instruction is part of a bundle, the other instructions in the
  /// bundle will still be bundled after removing the single instruction.
  instr_iterator erase_instr(MachineInstr *I) {
    return erase(instr_iterator(I));
  }

  /// Remove a range of instructions from the instruction list and delete them.
  iterator erase(iterator I, iterator E) {
    return Insts.erase(I.getInstrIterator(), E.getInstrIterator());
  }

  /// Remove an instruction or bundle from the instruction list and delete it.
  ///
  /// If I points to a bundle of instructions, they are all erased.
  iterator erase(iterator I) {
    return erase(I, std::next(I));
  }

  /// Remove an instruction from the instruction list and delete it.
  ///
  /// If I is the head of a bundle of instructions, the whole bundle will be
  /// erased.
  iterator erase(MachineInstr *I) {
    return erase(iterator(I));
  }

  /// Remove the unbundled instruction from the instruction list without
  /// deleting it.
  ///
  /// This function can not be used to remove bundled instructions, use
  /// remove_instr to remove individual instructions from a bundle.
  MachineInstr *remove(MachineInstr *I) {
    assert(!I->isBundled() && "Cannot remove bundled instructions");
    return Insts.remove(I);
  }

  /// Remove the possibly bundled instruction from the instruction list
  /// without deleting it.
  ///
  /// If the instruction is part of a bundle, the other instructions in the
  /// bundle will still be bundled after removing the single instruction.
  MachineInstr *remove_instr(MachineInstr *I);

  void clear() {
    Insts.clear();
  }

  /// Take an instruction from MBB 'Other' at the position From, and insert it
  /// into this MBB right before 'Where'.
  ///
  /// If From points to a bundle of instructions, the whole bundle is moved.
  void splice(iterator Where, MachineBasicBlock *Other, iterator From) {
    // The range splice() doesn't allow noop moves, but this one does.
    if (Where != From)
      splice(Where, Other, From, std::next(From));
  }

  /// Take a block of instructions from MBB 'Other' in the range [From, To),
  /// and insert them into this MBB right before 'Where'.
  ///
  /// The instruction at 'Where' must not be included in the range of
  /// instructions to move.
  void splice(iterator Where, MachineBasicBlock *Other,
              iterator From, iterator To) {
    Insts.splice(Where.getInstrIterator(), Other->Insts,
                 From.getInstrIterator(), To.getInstrIterator());
  }

  /// removeFromParent - This method unlinks 'this' from the containing
  /// function, and returns it, but does not delete it.
  MachineBasicBlock *removeFromParent();

  /// eraseFromParent - This method unlinks 'this' from the containing
  /// function and deletes it.
  void eraseFromParent();

  /// ReplaceUsesOfBlockWith - Given a machine basic block that branched to
  /// 'Old', change the code and CFG so that it branches to 'New' instead.
  void ReplaceUsesOfBlockWith(MachineBasicBlock *Old, MachineBasicBlock *New);

  /// CorrectExtraCFGEdges - Various pieces of code can cause excess edges in
  /// the CFG to be inserted.  If we have proven that MBB can only branch to
  /// DestA and DestB, remove any other MBB successors from the CFG. DestA and
  /// DestB can be null. Besides DestA and DestB, retain other edges leading
  /// to LandingPads (currently there can be only one; we don't check or require
  /// that here). Note it is possible that DestA and/or DestB are LandingPads.
  bool CorrectExtraCFGEdges(MachineBasicBlock *DestA,
                            MachineBasicBlock *DestB,
                            bool isCond);

  /// findDebugLoc - find the next valid DebugLoc starting at MBBI, skipping
  /// any DBG_VALUE instructions.  Return UnknownLoc if there is none.
  DebugLoc findDebugLoc(instr_iterator MBBI);
  DebugLoc findDebugLoc(iterator MBBI) {
    return findDebugLoc(MBBI.getInstrIterator());
  }

  /// Possible outcome of a register liveness query to computeRegisterLiveness()
  enum LivenessQueryResult {
    LQR_Live,            ///< Register is known to be live.
    LQR_OverlappingLive, ///< Register itself is not live, but some overlapping
                         ///< register is.
    LQR_Dead,            ///< Register is known to be dead.
    LQR_Unknown          ///< Register liveness not decidable from local
                         ///< neighborhood.
  };

  /// Return whether (physical) register \p Reg has been <def>ined and not
  /// <kill>ed as of just before \p Before.
  ///
  /// Search is localised to a neighborhood of \p Neighborhood instructions
  /// before (searching for defs or kills) and \p Neighborhood instructions
  /// after (searching just for defs) \p Before.
  ///
  /// \p Reg must be a physical register.
  LivenessQueryResult computeRegisterLiveness(const TargetRegisterInfo *TRI,
                                              unsigned Reg,
                                              const_iterator Before,
                                              unsigned Neighborhood=10) const;

  // Debugging methods.
  void dump() const;
  void print(raw_ostream &OS, SlotIndexes* = nullptr) const;

  // Printing method used by LoopInfo.
  void printAsOperand(raw_ostream &OS, bool PrintType = true) const;

  /// getNumber - MachineBasicBlocks are uniquely numbered at the function
  /// level, unless they're not in a MachineFunction yet, in which case this
  /// will return -1.
  ///
  int getNumber() const { return Number; }
  void setNumber(int N) { Number = N; }

  /// getSymbol - Return the MCSymbol for this basic block.
  ///
  MCSymbol *getSymbol() const;


private:
  /// getWeightIterator - Return weight iterator corresponding to the I
  /// successor iterator.
  weight_iterator getWeightIterator(succ_iterator I);
  const_weight_iterator getWeightIterator(const_succ_iterator I) const;

  friend class MachineBranchProbabilityInfo;

  /// getSuccWeight - Return weight of the edge from this block to MBB. This
  /// method should NOT be called directly, but by using getEdgeWeight method
  /// from MachineBranchProbabilityInfo class.
  uint32_t getSuccWeight(const_succ_iterator Succ) const;


  // Methods used to maintain doubly linked list of blocks...
  friend struct ilist_traits<MachineBasicBlock>;

  // Machine-CFG mutators

  /// addPredecessor - Remove pred as a predecessor of this MachineBasicBlock.
  /// Don't do this unless you know what you're doing, because it doesn't
  /// update pred's successors list. Use pred->addSuccessor instead.
  ///
  void addPredecessor(MachineBasicBlock *pred);

  /// removePredecessor - Remove pred as a predecessor of this
  /// MachineBasicBlock. Don't do this unless you know what you're
  /// doing, because it doesn't update pred's successors list. Use
  /// pred->removeSuccessor instead.
  ///
  void removePredecessor(MachineBasicBlock *pred);
};

raw_ostream& operator<<(raw_ostream &OS, const MachineBasicBlock &MBB);

// This is useful when building IndexedMaps keyed on basic block pointers.
struct MBB2NumberFunctor :
  public std::unary_function<const MachineBasicBlock*, unsigned> {
  unsigned operator()(const MachineBasicBlock *MBB) const {
    return MBB->getNumber();
  }
};

//===--------------------------------------------------------------------===//
// GraphTraits specializations for machine basic block graphs (machine-CFGs)
//===--------------------------------------------------------------------===//

// Provide specializations of GraphTraits to be able to treat a
// MachineFunction as a graph of MachineBasicBlocks...
//

template <> struct GraphTraits<MachineBasicBlock *> {
  typedef MachineBasicBlock NodeType;
  typedef MachineBasicBlock::succ_iterator ChildIteratorType;

  static NodeType *getEntryNode(MachineBasicBlock *BB) { return BB; }
  static inline ChildIteratorType child_begin(NodeType *N) {
    return N->succ_begin();
  }
  static inline ChildIteratorType child_end(NodeType *N) {
    return N->succ_end();
  }
};

template <> struct GraphTraits<const MachineBasicBlock *> {
  typedef const MachineBasicBlock NodeType;
  typedef MachineBasicBlock::const_succ_iterator ChildIteratorType;

  static NodeType *getEntryNode(const MachineBasicBlock *BB) { return BB; }
  static inline ChildIteratorType child_begin(NodeType *N) {
    return N->succ_begin();
  }
  static inline ChildIteratorType child_end(NodeType *N) {
    return N->succ_end();
  }
};

// Provide specializations of GraphTraits to be able to treat a
// MachineFunction as a graph of MachineBasicBlocks... and to walk it
// in inverse order.  Inverse order for a function is considered
// to be when traversing the predecessor edges of a MBB
// instead of the successor edges.
//
template <> struct GraphTraits<Inverse<MachineBasicBlock*> > {
  typedef MachineBasicBlock NodeType;
  typedef MachineBasicBlock::pred_iterator ChildIteratorType;
  static NodeType *getEntryNode(Inverse<MachineBasicBlock *> G) {
    return G.Graph;
  }
  static inline ChildIteratorType child_begin(NodeType *N) {
    return N->pred_begin();
  }
  static inline ChildIteratorType child_end(NodeType *N) {
    return N->pred_end();
  }
};

template <> struct GraphTraits<Inverse<const MachineBasicBlock*> > {
  typedef const MachineBasicBlock NodeType;
  typedef MachineBasicBlock::const_pred_iterator ChildIteratorType;
  static NodeType *getEntryNode(Inverse<const MachineBasicBlock*> G) {
    return G.Graph;
  }
  static inline ChildIteratorType child_begin(NodeType *N) {
    return N->pred_begin();
  }
  static inline ChildIteratorType child_end(NodeType *N) {
    return N->pred_end();
  }
};



/// MachineInstrSpan provides an interface to get an iteration range
/// containing the instruction it was initialized with, along with all
/// those instructions inserted prior to or following that instruction
/// at some point after the MachineInstrSpan is constructed.
class MachineInstrSpan {
  MachineBasicBlock &MBB;
  MachineBasicBlock::iterator I, B, E;
public:
  MachineInstrSpan(MachineBasicBlock::iterator I)
    : MBB(*I->getParent()),
      I(I),
      B(I == MBB.begin() ? MBB.end() : std::prev(I)),
      E(std::next(I)) {}

  MachineBasicBlock::iterator begin() {
    return B == MBB.end() ? MBB.begin() : std::next(B);
  }
  MachineBasicBlock::iterator end() { return E; }
  bool empty() { return begin() == end(); }

  MachineBasicBlock::iterator getInitial() { return I; }
};

} // namespace llvm

#endif