Use instruction itinerary to determine what instructions are 'cheap'.

[oota-llvm.git] / include / llvm / CodeGen / LiveInterval.h

diff --git a/include/llvm/CodeGen/LiveInterval.h b/include/llvm/CodeGen/LiveInterval.h
index aec21f8522ce36a1817e5377c3c7ff098edc11a5..57f0b624244fbd36ac2d22926520cfe93377175e 100644 (file)
--- a/include/llvm/CodeGen/LiveInterval.h
+++ b/include/llvm/CodeGen/LiveInterval.h
@@ -39,25 +39,13 @@ namespace llvm {
   /// This class holds information about a machine level values, including
   /// definition and use points.
   ///
-  /// Care must be taken in interpreting the def index of the value. The
-  /// following rules apply:
-  ///
-  /// If the isDefAccurate() method returns false then def does not contain the
-  /// index of the defining MachineInstr, or even (necessarily) to a
-  /// MachineInstr at all. In general such a def index is not meaningful
-  /// and should not be used. The exception is that, for values originally
-  /// defined by PHI instructions, after PHI elimination def will contain the
-  /// index of the MBB in which the PHI originally existed. This can be used
-  /// to insert code (spills or copies) which deals with the value, which will
-  /// be live in to the block.
   class VNInfo {
   private:
     enum {
       HAS_PHI_KILL    = 1,
       REDEF_BY_EC     = 1 << 1,
       IS_PHI_DEF      = 1 << 2,
-      IS_UNUSED       = 1 << 3,
-      IS_DEF_ACCURATE = 1 << 4
+      IS_UNUSED       = 1 << 3
     };
 
     MachineInstr *copy;
@@ -73,10 +61,8 @@ namespace llvm {
     SlotIndex def;
 
     /// VNInfo constructor.
-    /// d is presumed to point to the actual defining instr. If it doesn't
-    /// setIsDefAccurate(false) should be called after construction.
     VNInfo(unsigned i, SlotIndex d, MachineInstr *c)
-      : copy(c), flags(IS_DEF_ACCURATE), id(i), def(d)
+      : copy(c), flags(0), id(i), def(d)
     { }
 
     /// VNInfo construtor, copies values from orig, except for the value number.
@@ -95,6 +81,11 @@ namespace llvm {
     unsigned getFlags() const { return flags; }
     void setFlags(unsigned flags) { this->flags = flags; }
 
+    /// Merge flags from another VNInfo
+    void mergeFlags(const VNInfo *VNI) {
+      flags = (flags | VNI->flags) & ~IS_UNUSED;
+    }
+
     /// For a register interval, if this VN was definied by a copy instr
     /// getCopy() returns a pointer to it, otherwise returns 0.
     /// For a stack interval the behaviour of this method is undefined.
@@ -104,6 +95,10 @@ namespace llvm {
     /// undefined behavior.
     void setCopy(MachineInstr *c) { copy = c; }
 
+    /// isDefByCopy - Return true when this value was defined by a copy-like
+    /// instruction as determined by MachineInstr::isCopyLike.
+    bool isDefByCopy() const { return copy != 0; }
+
     /// Returns true if one or more kills are PHI nodes.
     bool hasPHIKill() const { return flags & HAS_PHI_KILL; }
     /// Set the PHI kill flag on this value.
@@ -145,16 +140,6 @@ namespace llvm {
       else
         flags &= ~IS_UNUSED;
     }
-
-    /// Returns true if the def is accurate.
-    bool isDefAccurate() const { return flags & IS_DEF_ACCURATE; }
-    /// Set the "is def accurate" flag on this value.
-    void setIsDefAccurate(bool defAccurate) {
-      if (defAccurate)
-        flags |= IS_DEF_ACCURATE;
-      else
-        flags &= ~IS_DEF_ACCURATE;
-    }
   };
 
   /// LiveRange structure - This represents a simple register range in the
@@ -320,10 +305,9 @@ namespace llvm {
     /// getNextValue - Create a new value number and return it.  MIIdx specifies
     /// the instruction that defines the value number.
     VNInfo *getNextValue(SlotIndex def, MachineInstr *CopyMI,
-                       bool isDefAccurate, VNInfo::Allocator &VNInfoAllocator) {
+                         VNInfo::Allocator &VNInfoAllocator) {
       VNInfo *VNI =
         new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), def, CopyMI);
-      VNI->setIsDefAccurate(isDefAccurate);
       valnos.push_back(VNI);
       return VNI;
     }
@@ -560,6 +544,45 @@ namespace llvm {
     LI.print(OS);
     return OS;
   }
-}
 
+  /// ConnectedVNInfoEqClasses - Helper class that can divide VNInfos in a
+  /// LiveInterval into equivalence clases of connected components. A
+  /// LiveInterval that has multiple connected components can be broken into
+  /// multiple LiveIntervals.
+  ///
+  /// Given a LiveInterval that may have multiple connected components, run:
+  ///
+  ///   unsigned numComps = ConEQ.Classify(LI);
+  ///   if (numComps > 1) {
+  ///     // allocate numComps-1 new LiveIntervals into LIS[1..]
+  ///     ConEQ.Distribute(LIS);
+  /// }
+
+  class ConnectedVNInfoEqClasses {
+    LiveIntervals &lis_;
+
+    // Map each value number to its equivalence class.
+    // The invariant is that EqClass[x] <= x.
+    // Two values are connected iff EqClass[x] == EqClass[b].
+    SmallVector<unsigned, 8> eqClass_;
+
+    // Note that values a and b are connected.
+    void Connect(unsigned a, unsigned b);
+
+    unsigned Renumber();
+
+  public:
+    explicit ConnectedVNInfoEqClasses(LiveIntervals &lis) : lis_(lis) {}
+
+    /// Classify - Classify the values in LI into connected components.
+    /// Return the number of connected components.
+    unsigned Classify(const LiveInterval *LI);
+
+    // Distribute values in LIV[0] into a separate LiveInterval for each connected
+    // component. LIV must have a LiveInterval for each connected component.
+    // The LiveIntervals in Liv[1..] must be empty.
+    void Distribute(LiveInterval *LIV[]);
+  };
+
+}
 #endif