X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FMachineBasicBlock.h;h=81912742fae161168fb464401116aae1d2a47477;hb=69261a644298bff1497d46c8cd38d688670f307b;hp=1ec89eefad99410b02def73fd8ed838f83e28980;hpb=7c2a4a30e0e16762c75adacebd05ec9fcbccf16b;p=oota-llvm.git

diff --git a/include/llvm/CodeGen/MachineBasicBlock.h b/include/llvm/CodeGen/MachineBasicBlock.h
index 1ec89eefad9..81912742fae 100644
--- a/include/llvm/CodeGen/MachineBasicBlock.h
+++ b/include/llvm/CodeGen/MachineBasicBlock.h
@@ -14,8 +14,8 @@
 #ifndef LLVM_CODEGEN_MACHINEBASICBLOCK_H
 #define LLVM_CODEGEN_MACHINEBASICBLOCK_H
 
-#include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/ADT/GraphTraits.h"
+#include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/Support/DataTypes.h"
 #include <functional>
 
@@ -77,6 +77,7 @@ class MachineBasicBlock : public ilist_node<MachineBasicBlock> {
   /// (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.
@@ -116,6 +117,10 @@ public:
   /// "(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; }
@@ -138,10 +143,7 @@ public:
     IterTy MII;
 
   public:
-    bundle_iterator(IterTy mii) : MII(mii) {
-      assert(!MII->isInsideBundle() &&
-             "It's not legal to initialize bundle_iterator with a bundled MI");
-    }
+    bundle_iterator(IterTy mii) : MII(mii) {}
 
     bundle_iterator(Ty &mi) : MII(mi) {
       assert(!mi.isInsideBundle() &&
@@ -151,7 +153,10 @@ public:
       assert((!mi || !mi->isInsideBundle()) &&
              "It's not legal to initialize bundle_iterator with a bundled MI");
     }
-    bundle_iterator(const bundle_iterator &I) : MII(I.MII) {}
+    // 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(0) {}
 
     Ty &operator*() const { return *MII; }
@@ -165,50 +170,45 @@ public:
     bool operator!=(const bundle_iterator &x) const {
       return !operator==(x);
     }
-    
+
     // Increment and decrement operators...
     bundle_iterator &operator--() {      // predecrement - Back up
-      do {
-        --MII;
-      } while (MII->isInsideBundle());
+      do --MII;
+      while (MII->isInsideBundle());
       return *this;
     }
     bundle_iterator &operator++() {      // preincrement - Advance
-      do {
-        ++MII;
-      } while (MII->isInsideBundle());
+      IterTy E = MII->getParent()->instr_end();
+      do ++MII;
+      while (MII != E && MII->isInsideBundle());
       return *this;
     }
     bundle_iterator operator--(int) {    // postdecrement operators...
       bundle_iterator tmp = *this;
-      do {
-        --MII;
-      } while (MII->isInsideBundle());
+      --*this;
       return tmp;
     }
     bundle_iterator operator++(int) {    // postincrement operators...
       bundle_iterator tmp = *this;
-      do {
-        ++MII;
-      } while (MII->isInsideBundle());
+      ++*this;
       return tmp;
     }
 
-    IterTy getInsnIterator() const {
+    IterTy getInstrIterator() const {
       return MII;
-    }    
+    }
   };
 
-  typedef Instructions::iterator                                  insn_iterator;
-  typedef Instructions::const_iterator                      const_insn_iterator;
-  typedef std::reverse_iterator<insn_iterator>            reverse_insn_iterator;
+  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_insn_iterator>        const_reverse_insn_iterator;
+  std::reverse_iterator<const_instr_iterator>      const_reverse_instr_iterator;
 
   typedef
-  bundle_iterator<MachineInstr,insn_iterator>                          iterator;
+  bundle_iterator<MachineInstr,instr_iterator>                         iterator;
   typedef
-  bundle_iterator<const MachineInstr,const_insn_iterator>        const_iterator;
+  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;
 
@@ -221,51 +221,23 @@ public:
   const MachineInstr& front() const { return Insts.front(); }
   const MachineInstr& back()  const { return Insts.back(); }
 
-  insn_iterator                insn_begin()       { return Insts.begin();  }
-  const_insn_iterator          insn_begin() const { return Insts.begin();  }
-  insn_iterator                  insn_end()       { return Insts.end();    }
-  const_insn_iterator            insn_end() const { return Insts.end();    }
-  reverse_insn_iterator       insn_rbegin()       { return Insts.rbegin(); }
-  const_reverse_insn_iterator insn_rbegin() const { return Insts.rbegin(); }
-  reverse_insn_iterator       insn_rend  ()       { return Insts.rend();   }
-  const_reverse_insn_iterator insn_rend  () const { return Insts.rend();   }
-
-  iterator                begin()       { return Insts.begin();  }
-  const_iterator          begin() const { return Insts.begin();  }
-  iterator                  end()       {
-    insn_iterator II = insn_end();
-    if (II != insn_begin()) {
-      while (II->isInsideBundle())
-        --II;
-    }
-    return II;
-  }
-  const_iterator            end() const {
-    const_insn_iterator II = insn_end();
-    if (II != insn_begin()) {
-      while (II->isInsideBundle())
-        --II;
-    }
-    return II;
-  }
-  reverse_iterator       rbegin()       {
-    reverse_insn_iterator II = insn_rbegin();
-    if (II != insn_rend()) {
-      while (II->isInsideBundle())
-        ++II;
-    }
-    return II;
-  }
-  const_reverse_iterator rbegin() const {
-    const_reverse_insn_iterator II = insn_rbegin();
-    if (II != insn_rend()) {
-      while (II->isInsideBundle())
-        ++II;
-    }
-    return II;
-  }
-  reverse_iterator       rend  ()       { return Insts.rend();   }
-  const_reverse_iterator rend  () const { return Insts.rend();   }
+  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();   }
 
 
   // Machine-CFG iterators
@@ -359,7 +331,7 @@ public:
   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.
@@ -379,6 +351,8 @@ public:
   /// 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);
 
   /// removeSuccessor - Remove successor from the successors list of this
@@ -406,7 +380,11 @@ public:
   /// 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;
@@ -424,7 +402,7 @@ public:
   /// branch to do so (e.g., a table jump).  True is a conservative answer.
   bool canFallThrough();
 
-  /// Returns a pointer to the first instructon in this block that is not a 
+  /// Returns a pointer to the first instructon in this block that is not a
   /// PHINode instruction. When adding instruction to the beginning of the
   /// basic block, they should be added before the returned value, not before
   /// the first instruction, which might be PHI.
@@ -442,9 +420,9 @@ public:
   iterator getFirstTerminator();
   const_iterator getFirstTerminator() const;
 
-  /// getFirstInsnTerminator - Same getFirstTerminator but it ignores bundles
-  /// and return an insn_iterator instead.
-  insn_iterator getFirstInsnTerminator();
+  /// 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()
@@ -464,74 +442,86 @@ public:
   void push_back(MachineInstr *MI) { Insts.push_back(MI); }
 
   template<typename IT>
-  void insert(insn_iterator I, IT S, IT E) {
+  void insert(instr_iterator I, IT S, IT E) {
     Insts.insert(I, S, E);
   }
-  insn_iterator insert(insn_iterator I, MachineInstr *M) {
+  instr_iterator insert(instr_iterator I, MachineInstr *M) {
     return Insts.insert(I, M);
   }
-  insn_iterator insertAfter(insn_iterator I, MachineInstr *M) { 
-    return Insts.insertAfter(I, M); 
+  instr_iterator insertAfter(instr_iterator I, MachineInstr *M) {
+    return Insts.insertAfter(I, M);
   }
 
   template<typename IT>
   void insert(iterator I, IT S, IT E) {
-    Insts.insert(I.getInsnIterator(), S, E);
+    Insts.insert(I.getInstrIterator(), S, E);
   }
   iterator insert(iterator I, MachineInstr *M) {
-    return Insts.insert(I.getInsnIterator(), M);
+    return Insts.insert(I.getInstrIterator(), M);
   }
-  iterator insertAfter(iterator I, MachineInstr *M) { 
-    return Insts.insertAfter(I.getInsnIterator(), M); 
+  iterator insertAfter(iterator I, MachineInstr *M) {
+    return Insts.insertAfter(I.getInstrIterator(), M);
   }
 
-  // erase - Remove the specified element or range from the instruction list.
-  // These functions delete any instructions removed.
-  //
-  insn_iterator erase(insn_iterator I) {
+  /// erase - Remove the specified element or range from the instruction list.
+  /// These functions delete any instructions removed.
+  ///
+  instr_iterator erase(instr_iterator I) {
     return Insts.erase(I);
   }
-  insn_iterator erase(insn_iterator I, insn_iterator E) {
+  instr_iterator erase(instr_iterator I, instr_iterator E) {
     return Insts.erase(I, E);
   }
-
-  iterator erase(iterator I)             {
-    return Insts.erase(I.getInsnIterator());
+  instr_iterator erase_instr(MachineInstr *I) {
+    instr_iterator MII(I);
+    return erase(MII);
   }
+
+  iterator erase(iterator I);
   iterator erase(iterator I, iterator E) {
-    return Insts.erase(I.getInsnIterator(), E.getInsnIterator());
+    return Insts.erase(I.getInstrIterator(), E.getInstrIterator());
+  }
+  iterator erase(MachineInstr *I) {
+    iterator MII(I);
+    return erase(MII);
   }
 
-  iterator erase(MachineInstr *I)        { iterator MII(I); return erase(MII); }
-  MachineInstr *remove(MachineInstr *I)  { return Insts.remove(I); }
-  void clear()                           { Insts.clear(); }
+  /// remove - Remove the instruction from the instruction list. This function
+  /// does not delete the instruction. WARNING: Note, if the specified
+  /// instruction is a bundle this function will remove all the bundled
+  /// instructions as well. It is up to the caller to keep a list of the
+  /// bundled instructions and re-insert them if desired. This function is
+  /// *not recommended* for manipulating instructions with bundles. Use
+  /// splice instead.
+  MachineInstr *remove(MachineInstr *I);
+  void clear() {
+    Insts.clear();
+  }
 
   /// splice - Take an instruction from MBB 'Other' at the position From,
   /// and insert it into this MBB right before 'where'.
-  void splice(insn_iterator where, MachineBasicBlock *Other,
-              insn_iterator From) {
+  void splice(instr_iterator where, MachineBasicBlock *Other,
+              instr_iterator From) {
     Insts.splice(where, Other->Insts, From);
   }
-  void splice(iterator where, MachineBasicBlock *Other, iterator From) {
-    Insts.splice(where.getInsnIterator(), Other->Insts, From.getInsnIterator());
-  }
+  void splice(iterator where, MachineBasicBlock *Other, iterator From);
 
   /// splice - Take a block of instructions from MBB 'Other' in the range [From,
   /// To), and insert them into this MBB right before 'where'.
-  void splice(insn_iterator where, MachineBasicBlock *Other, insn_iterator From,
-              insn_iterator To) {
+  void splice(instr_iterator where, MachineBasicBlock *Other, instr_iterator From,
+              instr_iterator To) {
     Insts.splice(where, Other->Insts, From, To);
   }
   void splice(iterator where, MachineBasicBlock *Other, iterator From,
               iterator To) {
-    Insts.splice(where.getInsnIterator(), Other->Insts,
-                 From.getInsnIterator(), To.getInsnIterator());
+    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();
@@ -552,11 +542,33 @@ public:
 
   /// findDebugLoc - find the next valid DebugLoc starting at MBBI, skipping
   /// any DBG_VALUE instructions.  Return UnknownLoc if there is none.
-  DebugLoc findDebugLoc(insn_iterator MBBI);
+  DebugLoc findDebugLoc(instr_iterator MBBI);
   DebugLoc findDebugLoc(iterator MBBI) {
-    return findDebugLoc(MBBI.getInsnIterator());
+    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.
+  };
+
+  /// computeRegisterLiveness - Return whether (physical) register \c Reg
+  /// has been <def>ined and not <kill>ed as of just before \c MI.
+  /// 
+  /// Search is localised to a neighborhood of
+  /// \c Neighborhood instructions before (searching for defs or kills) and
+  /// Neighborhood instructions after (searching just for defs) MI.
+  ///
+  /// \c Reg must be a physical register.
+  LivenessQueryResult computeRegisterLiveness(const TargetRegisterInfo *TRI,
+                                              unsigned Reg, MachineInstr *MI,
+                                              unsigned Neighborhood=10);
+
   // Debugging methods.
   void dump() const;
   void print(raw_ostream &OS, SlotIndexes* = 0) const;
@@ -577,13 +589,14 @@ 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(MachineBasicBlock *succ);
+  uint32_t getSuccWeight(const_succ_iterator Succ) const;
 
 
   // Methods used to maintain doubly linked list of blocks...