Merge commit '8d20b5f9ff609e70fae5c865931ab0f29e639d9c'

Conflicts:
	lib/CodeGen/AsmPrinter/DwarfDebug.cpp
	lib/CodeGen/AsmPrinter/DwarfDebug.h
	lib/Target/ARM/MCTargetDesc/ARMAsmBackend.cpp
	lib/Target/Mips/MipsISelDAGToDAG.cpp
	lib/Target/Mips/MipsInstrFPU.td
	lib/Target/Mips/MipsSubtarget.cpp
	lib/Target/Mips/MipsSubtarget.h
	lib/Target/X86/X86MCInstLower.cpp
	tools/Makefile
	tools/llc/llc.cpp

8 files changed, 84 insertions, 47 deletions

diff --git a/include/llvm/CodeGen/AsmPrinter.h b/include/llvm/CodeGen/AsmPrinter.h
index 02c5f422ce..2ee7d4a79e 100644
--- a/include/llvm/CodeGen/AsmPrinter.h
+++ b/include/llvm/CodeGen/AsmPrinter.h
@@ -408,10 +408,8 @@ namespace llvm {
     /// GetSizeOfEncodedValue - Return the size of the encoding in bytes.
     unsigned GetSizeOfEncodedValue(unsigned Encoding) const;
 
-    /// EmitReference - Emit a reference to a label with a specified encoding.
-    ///
-    void EmitReference(const MCSymbol *Sym, unsigned Encoding) const;
-    void EmitReference(const GlobalValue *GV, unsigned Encoding) const;
+    /// EmitReference - Emit reference to a ttype global with a specified encoding.
+    void EmitTTypeReference(const GlobalValue *GV, unsigned Encoding) const;
 
     /// EmitSectionOffset - Emit the 4-byte offset of Label from the start of
     /// its section.  This can be done with a special directive if the target
diff --git a/include/llvm/CodeGen/DFAPacketizer.h b/include/llvm/CodeGen/DFAPacketizer.h
index 2d2db78144..e4386fc8e2 100644
--- a/include/llvm/CodeGen/DFAPacketizer.h
+++ b/include/llvm/CodeGen/DFAPacketizer.h
@@ -135,7 +135,7 @@ public:
   // initPacketizerState - perform initialization before packetizing
   // an instruction. This function is supposed to be overrided by
   // the target dependent packetizer.
-  virtual void initPacketizerState(void) { return; }
+  virtual void initPacketizerState() { return; }
 
   // ignorePseudoInstruction - Ignore bundling of pseudo instructions.
   virtual bool ignorePseudoInstruction(MachineInstr *I,
diff --git a/include/llvm/CodeGen/MachineInstrBundle.h b/include/llvm/CodeGen/MachineInstrBundle.h
index 854ba06209..3c60ad1f29 100644
--- a/include/llvm/CodeGen/MachineInstrBundle.h
+++ b/include/llvm/CodeGen/MachineInstrBundle.h
@@ -149,16 +149,13 @@ public:
   /// PhysRegInfo - Information about a physical register used by a set of
   /// operands.
   struct PhysRegInfo {
-    /// Clobbers - Reg or an overlapping register is defined, or a regmask 
+    /// Clobbers - Reg or an overlapping register is defined, or a regmask
     /// clobbers Reg.
     bool Clobbers;
 
     /// Defines - Reg or a super-register is defined.
     bool Defines;
 
-    /// DefinesOverlap - Reg or an overlapping register is defined.
-    bool DefinesOverlap;
-
     /// Reads - Read or a super-register is read.
     bool Reads;
 
diff --git a/include/llvm/CodeGen/MachineModuleInfo.h b/include/llvm/CodeGen/MachineModuleInfo.h
index 6b88d4a949..fc73a3d609 100644
--- a/include/llvm/CodeGen/MachineModuleInfo.h
+++ b/include/llvm/CodeGen/MachineModuleInfo.h
@@ -372,7 +372,7 @@ public:
 
   /// getCurrentCallSite - Get the call site currently being processed, if any.
   /// return zero if none.
-  unsigned getCurrentCallSite(void) { return CurCallSite; }
+  unsigned getCurrentCallSite() { return CurCallSite; }
 
   /// getTypeInfos - Return a reference to the C++ typeinfo for the current
   /// function.
diff --git a/include/llvm/CodeGen/MachineScheduler.h b/include/llvm/CodeGen/MachineScheduler.h
index 31bd606f93..88f347e4b5 100644
--- a/include/llvm/CodeGen/MachineScheduler.h
+++ b/include/llvm/CodeGen/MachineScheduler.h
@@ -181,7 +181,7 @@ public:
     return Queue.begin() + idx;
   }
 
-#ifndef NDEBUG
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   void dump();
 #endif
 };
@@ -202,6 +202,10 @@ protected:
   RegisterClassInfo *RegClassInfo;
   MachineSchedStrategy *SchedImpl;
 
+  /// Topo - A topological ordering for SUnits which permits fast IsReachable
+  /// and similar queries.
+  ScheduleDAGTopologicalSort Topo;
+
   /// Ordered list of DAG postprocessing steps.
   std::vector<ScheduleDAGMutation*> Mutations;
 
@@ -226,6 +230,10 @@ protected:
   IntervalPressure BotPressure;
   RegPressureTracker BotRPTracker;
 
+  /// Record the next node in a scheduled cluster.
+  const SUnit *NextClusterPred;
+  const SUnit *NextClusterSucc;
+
 #ifndef NDEBUG
   /// The number of instructions scheduled so far. Used to cut off the
   /// scheduler at the point determined by misched-cutoff.
@@ -236,24 +244,35 @@ public:
   ScheduleDAGMI(MachineSchedContext *C, MachineSchedStrategy *S):
     ScheduleDAGInstrs(*C->MF, *C->MLI, *C->MDT, /*IsPostRA=*/false, C->LIS),
     AA(C->AA), RegClassInfo(C->RegClassInfo), SchedImpl(S),
-    RPTracker(RegPressure), CurrentTop(), TopRPTracker(TopPressure),
-    CurrentBottom(), BotRPTracker(BotPressure) {
+    Topo(SUnits, &ExitSU), RPTracker(RegPressure), CurrentTop(),
+    TopRPTracker(TopPressure), CurrentBottom(), BotRPTracker(BotPressure),
+    NextClusterPred(NULL), NextClusterSucc(NULL) {
 #ifndef NDEBUG
     NumInstrsScheduled = 0;
 #endif
   }
 
   virtual ~ScheduleDAGMI() {
+    DeleteContainerPointers(Mutations);
     delete SchedImpl;
   }
 
   /// Add a postprocessing step to the DAG builder.
   /// Mutations are applied in the order that they are added after normal DAG
   /// building and before MachineSchedStrategy initialization.
+  ///
+  /// ScheduleDAGMI takes ownership of the Mutation object.
   void addMutation(ScheduleDAGMutation *Mutation) {
     Mutations.push_back(Mutation);
   }
 
+  /// \brief Add a DAG edge to the given SU with the given predecessor
+  /// dependence data.
+  ///
+  /// \returns true if the edge may be added without creating a cycle OR if an
+  /// equivalent edge already existed (false indicates failure).
+  bool addEdge(SUnit *SuccSU, const SDep &PredDep);
+
   MachineBasicBlock::iterator top() const { return CurrentTop; }
   MachineBasicBlock::iterator bottom() const { return CurrentBottom; }
 
@@ -285,6 +304,10 @@ public:
     return RegionCriticalPSets;
   }
 
+  const SUnit *getNextClusterPred() const { return NextClusterPred; }
+
+  const SUnit *getNextClusterSucc() const { return NextClusterSucc; }
+
 protected:
   // Top-Level entry points for the schedule() driver...
 
diff --git a/include/llvm/CodeGen/RegisterScavenging.h b/include/llvm/CodeGen/RegisterScavenging.h
index 08d316992e..8752e67a79 100644
--- a/include/llvm/CodeGen/RegisterScavenging.h
+++ b/include/llvm/CodeGen/RegisterScavenging.h
@@ -129,10 +129,12 @@ private:
   /// isReserved - Returns true if a register is reserved. It is never "unused".
   bool isReserved(unsigned Reg) const { return MRI->isReserved(Reg); }
 
-  /// isUsed / isUnused - Test if a register is currently being used.
+  /// isUsed - Test if a register is currently being used.  When called by the
+  /// isAliasUsed function, we only check isReserved if this is the original
+  /// register, not an alias register.
   ///
-  bool isUsed(unsigned Reg) const   {
-    return !RegsAvailable.test(Reg) || isReserved(Reg);
+  bool isUsed(unsigned Reg, bool CheckReserved = true) const   {
+    return !RegsAvailable.test(Reg) || (CheckReserved && isReserved(Reg));
   }
 
   /// isAliasUsed - Is Reg or an alias currently in use?
diff --git a/include/llvm/CodeGen/ScheduleDAG.h b/include/llvm/CodeGen/ScheduleDAG.h
index 7e0ca1478e..016722e7f4 100644
--- a/include/llvm/CodeGen/ScheduleDAG.h
+++ b/include/llvm/CodeGen/ScheduleDAG.h
@@ -57,7 +57,8 @@ namespace llvm {
       Barrier,      ///< An unknown scheduling barrier.
       MayAliasMem,  ///< Nonvolatile load/Store instructions that may alias.
       MustAliasMem, ///< Nonvolatile load/Store instructions that must alias.
-      Artificial    ///< Arbitrary weak DAG edge (no actual dependence).
+      Artificial,   ///< Arbitrary weak DAG edge (no actual dependence).
+      Cluster       ///< Weak DAG edge linking a chain of clustered instrs.
     };
 
   private:
@@ -200,12 +201,26 @@ namespace llvm {
       return getKind() == Order && Contents.OrdKind == MustAliasMem;
     }
 
+    /// isWeak - Test if this a weak dependence. Weak dependencies are
+    /// considered DAG edges for height computation and other heuristics, but do
+    /// not force ordering. Breaking a weak edge may require the scheduler to
+    /// compensate, for example by inserting a copy.
+    bool isWeak() const {
+      return getKind() == Order && Contents.OrdKind == Cluster;
+    }
+
     /// isArtificial - Test if this is an Order dependence that is marked
     /// as "artificial", meaning it isn't necessary for correctness.
     bool isArtificial() const {
       return getKind() == Order && Contents.OrdKind == Artificial;
     }
 
+    /// isCluster - Test if this is an Order dependence that is marked
+    /// as "cluster", meaning it is artificial and wants to be adjacent.
+    bool isCluster() const {
+      return getKind() == Order && Contents.OrdKind == Cluster;
+    }
+
     /// isAssignedRegDep - Test if this is a Data dependence that is
     /// associated with a register.
     bool isAssignedRegDep() const {
@@ -267,6 +282,8 @@ namespace llvm {
     unsigned NumSuccs;                  // # of SDep::Data sucss.
     unsigned NumPredsLeft;              // # of preds not scheduled.
     unsigned NumSuccsLeft;              // # of succs not scheduled.
+    unsigned WeakPredsLeft;             // # of weak preds not scheduled.
+    unsigned WeakSuccsLeft;             // # of weak succs not scheduled.
     unsigned short NumRegDefsLeft;      // # of reg defs with no scheduled use.
     unsigned short Latency;             // Node latency.
     bool isVRegCycle      : 1;          // May use and def the same vreg.
@@ -301,12 +318,12 @@ namespace llvm {
     SUnit(SDNode *node, unsigned nodenum)
       : Node(node), Instr(0), OrigNode(0), SchedClass(0), NodeNum(nodenum),
         NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0),
-        NumSuccsLeft(0), NumRegDefsLeft(0), Latency(0),
-        isVRegCycle(false), isCall(false), isCallOp(false), isTwoAddress(false),
-        isCommutable(false), hasPhysRegDefs(false), hasPhysRegClobbers(false),
-        isPending(false), isAvailable(false), isScheduled(false),
-        isScheduleHigh(false), isScheduleLow(false), isCloned(false),
-        SchedulingPref(Sched::None),
+        NumSuccsLeft(0), WeakPredsLeft(0), WeakSuccsLeft(0), NumRegDefsLeft(0),
+        Latency(0), isVRegCycle(false), isCall(false), isCallOp(false),
+        isTwoAddress(false), isCommutable(false), hasPhysRegDefs(false),
+        hasPhysRegClobbers(false), isPending(false), isAvailable(false),
+        isScheduled(false), isScheduleHigh(false), isScheduleLow(false),
+        isCloned(false), SchedulingPref(Sched::None),
         isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0),
         TopReadyCycle(0), BotReadyCycle(0), CopyDstRC(NULL), CopySrcRC(NULL) {}
 
@@ -315,12 +332,12 @@ namespace llvm {
     SUnit(MachineInstr *instr, unsigned nodenum)
       : Node(0), Instr(instr), OrigNode(0), SchedClass(0), NodeNum(nodenum),
         NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0),
-        NumSuccsLeft(0), NumRegDefsLeft(0), Latency(0),
-        isVRegCycle(false), isCall(false), isCallOp(false), isTwoAddress(false),
-        isCommutable(false), hasPhysRegDefs(false), hasPhysRegClobbers(false),
-        isPending(false), isAvailable(false), isScheduled(false),
-        isScheduleHigh(false), isScheduleLow(false), isCloned(false),
-        SchedulingPref(Sched::None),
+        NumSuccsLeft(0), WeakPredsLeft(0), WeakSuccsLeft(0), NumRegDefsLeft(0),
+        Latency(0), isVRegCycle(false), isCall(false), isCallOp(false),
+        isTwoAddress(false), isCommutable(false), hasPhysRegDefs(false),
+        hasPhysRegClobbers(false), isPending(false), isAvailable(false),
+        isScheduled(false), isScheduleHigh(false), isScheduleLow(false),
+        isCloned(false), SchedulingPref(Sched::None),
         isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0),
         TopReadyCycle(0), BotReadyCycle(0), CopyDstRC(NULL), CopySrcRC(NULL) {}
 
@@ -328,12 +345,12 @@ namespace llvm {
     SUnit()
       : Node(0), Instr(0), OrigNode(0), SchedClass(0), NodeNum(~0u),
         NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0),
-        NumSuccsLeft(0), NumRegDefsLeft(0), Latency(0),
-        isVRegCycle(false), isCall(false), isCallOp(false), isTwoAddress(false),
-        isCommutable(false), hasPhysRegDefs(false), hasPhysRegClobbers(false),
-        isPending(false), isAvailable(false), isScheduled(false),
-        isScheduleHigh(false), isScheduleLow(false), isCloned(false),
-        SchedulingPref(Sched::None),
+        NumSuccsLeft(0), WeakPredsLeft(0), WeakSuccsLeft(0), NumRegDefsLeft(0),
+        Latency(0), isVRegCycle(false), isCall(false), isCallOp(false),
+        isTwoAddress(false), isCommutable(false), hasPhysRegDefs(false),
+        hasPhysRegClobbers(false), isPending(false), isAvailable(false),
+        isScheduled(false), isScheduleHigh(false), isScheduleLow(false),
+        isCloned(false), SchedulingPref(Sched::None),
         isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0),
         TopReadyCycle(0), BotReadyCycle(0), CopyDstRC(NULL), CopySrcRC(NULL) {}
 
@@ -372,7 +389,7 @@ namespace llvm {
     /// addPred - This adds the specified edge as a pred of the current node if
     /// not already.  It also adds the current node as a successor of the
     /// specified node.
-    bool addPred(const SDep &D);
+    bool addPred(const SDep &D, bool Required = true);
 
     /// removePred - This removes the specified edge as a pred of the current
     /// node if it exists.  It also removes the current node as a successor of
@@ -654,6 +671,7 @@ namespace llvm {
   class ScheduleDAGTopologicalSort {
     /// SUnits - A reference to the ScheduleDAG's SUnits.
     std::vector<SUnit> &SUnits;
+    SUnit *ExitSU;
 
     /// Index2Node - Maps topological index to the node number.
     std::vector<int> Index2Node;
@@ -675,7 +693,7 @@ namespace llvm {
     void Allocate(int n, int index);
 
   public:
-    explicit ScheduleDAGTopologicalSort(std::vector<SUnit> &SUnits);
+    ScheduleDAGTopologicalSort(std::vector<SUnit> &SUnits, SUnit *ExitSU);
 
     /// InitDAGTopologicalSorting - create the initial topological
     /// ordering from the DAG to be scheduled.
diff --git a/include/llvm/CodeGen/TargetLoweringObjectFileImpl.h b/include/llvm/CodeGen/TargetLoweringObjectFileImpl.h
index 9849e92f7d..f1b3065e7c 100644
--- a/include/llvm/CodeGen/TargetLoweringObjectFileImpl.h
+++ b/include/llvm/CodeGen/TargetLoweringObjectFileImpl.h
@@ -55,13 +55,12 @@ public:
   SelectSectionForGlobal(const GlobalValue *GV, SectionKind Kind,
                          Mangler *Mang, const TargetMachine &TM) const;
 
-  /// getExprForDwarfGlobalReference - Return an MCExpr to use for a reference
-  /// to the specified global variable from exception handling information.
-  ///
+  /// getTTypeGlobalReference - Return an MCExpr to use for a reference to the
+  /// specified type info global variable from exception handling information.
   virtual const MCExpr *
-  getExprForDwarfGlobalReference(const GlobalValue *GV, Mangler *Mang,
-                                 MachineModuleInfo *MMI, unsigned Encoding,
-                                 MCStreamer &Streamer) const;
+  getTTypeGlobalReference(const GlobalValue *GV, Mangler *Mang,
+                          MachineModuleInfo *MMI, unsigned Encoding,
+                          MCStreamer &Streamer) const;
 
   // getCFIPersonalitySymbol - The symbol that gets passed to .cfi_personality.
   virtual MCSymbol *
@@ -103,12 +102,12 @@ public:
   virtual bool shouldEmitUsedDirectiveFor(const GlobalValue *GV,
                                           Mangler *) const;
 
-  /// getExprForDwarfGlobalReference - The mach-o version of this method
+  /// getTTypeGlobalReference - The mach-o version of this method
   /// defaults to returning a stub reference.
   virtual const MCExpr *
-  getExprForDwarfGlobalReference(const GlobalValue *GV, Mangler *Mang,
-                                 MachineModuleInfo *MMI, unsigned Encoding,
-                                 MCStreamer &Streamer) const;
+  getTTypeGlobalReference(const GlobalValue *GV, Mangler *Mang,
+                          MachineModuleInfo *MMI, unsigned Encoding,
+                          MCStreamer &Streamer) const;
 
   // getCFIPersonalitySymbol - The symbol that gets passed to .cfi_personality.
   virtual MCSymbol *