am 2d4629c5: Merge branch \'upstream\' into merge_2013_03_18

* commit '2d4629c5d7dcc6582fa7b85a517744f1a3654eba': (424 commits)
  Change NULL to 0.
  Register the flush function for each compile unit.
  Remove trailing spaces.
  Fix PPC unaligned 64-bit loads and stores
  ARM cost model: Make some vector integer to float casts cheaper
  ARM cost model: Correct cost for some cheap float to integer conversions
  Extend global merge pass to optionally consider global constant variables. Also add some checks to not merge globals used within landing pad instructions or marked as "used".
  Change test cases to handle unaligned references.
  Remove unnecessary leading comment characters in lit-only file
  Add SchedRW annotations to most of X86InstrSSE.td.
  Annotate X86 arithmetic instructions with SchedRW lists.
  Check whether a pointer is non-null (isKnownNonNull) in isKnownNonZero.
  TableGen fix for the new machine model.
  Include '.test' suffix in target specific lit configs that need it
  Make the fields in the diagram match the descriptive text above them.
  Update
  Fix 80-col. violations in PPCCTRLoops
  Fix large count and negative constant count handling in PPCCTRLoops
  Cleanup initial-value constants in PPCCTRLoops
  Fix integer comparison in DIEInteger::BestForm.
  ...

14 files changed, 84 insertions, 54 deletions

diff --git a/include/llvm/CodeGen/FastISel.h b/include/llvm/CodeGen/FastISel.h
index 57273d8..705db7e 100644
--- a/include/llvm/CodeGen/FastISel.h
+++ b/include/llvm/CodeGen/FastISel.h
@@ -372,11 +372,6 @@ protected:
     return 0;
   }
 
-  /// Whether we should skip target-independent fast-isel
-  virtual bool SkipTargetIndependentFastISel() {
-    return false;
-  }
-
 private:
   bool SelectBinaryOp(const User *I, unsigned ISDOpcode);
 
diff --git a/include/llvm/CodeGen/GCMetadata.h b/include/llvm/CodeGen/GCMetadata.h
index fa40049..1070d29 100644
--- a/include/llvm/CodeGen/GCMetadata.h
+++ b/include/llvm/CodeGen/GCMetadata.h
@@ -180,7 +180,8 @@ namespace llvm {
     GCModuleInfo();
     ~GCModuleInfo();
 
-    /// clear - Resets the pass. The metadata deleter pass calls this.
+    /// clear - Resets the pass. Any pass, which uses GCModuleInfo, should
+    /// call it in doFinalization().
     ///
     void clear();
 
diff --git a/include/llvm/CodeGen/ISDOpcodes.h b/include/llvm/CodeGen/ISDOpcodes.h
index 092fa5a..442729b 100644
--- a/include/llvm/CodeGen/ISDOpcodes.h
+++ b/include/llvm/CodeGen/ISDOpcodes.h
@@ -311,8 +311,10 @@ namespace ISD {
     /// the shift amount can be any type, but care must be taken to ensure it is
     /// large enough.  TLI.getShiftAmountTy() is i8 on some targets, but before
     /// legalization, types like i1024 can occur and i8 doesn't have enough bits
-    /// to represent the shift amount.  By convention, DAGCombine and
-    /// SelectionDAGBuilder forces these shift amounts to i32 for simplicity.
+    /// to represent the shift amount.
+    /// When the 1st operand is a vector, the shift amount must be in the same
+    /// type. (TLI.getShiftAmountTy() will return the same type when the input
+    /// type is a vector.)
     SHL, SRA, SRL, ROTL, ROTR,
 
     /// Byte Swap and Counting operators.
diff --git a/include/llvm/CodeGen/MachineFrameInfo.h b/include/llvm/CodeGen/MachineFrameInfo.h
index 93d7728..cdec7e6 100644
--- a/include/llvm/CodeGen/MachineFrameInfo.h
+++ b/include/llvm/CodeGen/MachineFrameInfo.h
@@ -419,6 +419,9 @@ public:
   ///
   void setStackSize(uint64_t Size) { StackSize = Size; }
 
+  /// Estimate and return the size of the stack frame.
+  unsigned estimateStackSize(const MachineFunction &MF) const;
+
   /// getOffsetAdjustment - Return the correction for frame offsets.
   ///
   int getOffsetAdjustment() const { return OffsetAdjustment; }
diff --git a/include/llvm/CodeGen/MachinePostDominators.h b/include/llvm/CodeGen/MachinePostDominators.h
index 00a60cb..ca09aef 100644
--- a/include/llvm/CodeGen/MachinePostDominators.h
+++ b/include/llvm/CodeGen/MachinePostDominators.h
@@ -15,7 +15,6 @@
 #ifndef LLVM_CODEGEN_MACHINEPOSTDOMINATORS_H
 #define LLVM_CODEGEN_MACHINEPOSTDOMINATORS_H
 
-#include "llvm/Analysis/DominatorInternals.h"
 #include "llvm/Analysis/Dominators.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
@@ -55,26 +54,27 @@ public:
     return DT->getNode(BB);
   }
 
-  bool dominates(MachineDomTreeNode *A, MachineDomTreeNode *B) const {
+  bool dominates(const MachineDomTreeNode *A,
+                 const MachineDomTreeNode *B) const {
     return DT->dominates(A, B);
   }
 
-  bool dominates(MachineBasicBlock *A, MachineBasicBlock *B) const {
+  bool dominates(const MachineBasicBlock *A, const MachineBasicBlock *B) const {
     return DT->dominates(A, B);
   }
 
-  bool
-  properlyDominates(const MachineDomTreeNode *A, MachineDomTreeNode *B) const {
+  bool properlyDominates(const MachineDomTreeNode *A,
+                         const MachineDomTreeNode *B) const {
     return DT->properlyDominates(A, B);
   }
 
-  bool
-  properlyDominates(MachineBasicBlock *A, MachineBasicBlock *B) const {
+  bool properlyDominates(const MachineBasicBlock *A,
+                         const MachineBasicBlock *B) const {
     return DT->properlyDominates(A, B);
   }
 
   MachineBasicBlock *findNearestCommonDominator(MachineBasicBlock *A,
-                                                       MachineBasicBlock *B) {
+                                                MachineBasicBlock *B) {
     return DT->findNearestCommonDominator(A, B);
   }
 
diff --git a/include/llvm/CodeGen/MachineRegisterInfo.h b/include/llvm/CodeGen/MachineRegisterInfo.h
index 875285b..4b43cc1 100644
--- a/include/llvm/CodeGen/MachineRegisterInfo.h
+++ b/include/llvm/CodeGen/MachineRegisterInfo.h
@@ -100,9 +100,9 @@ class MachineRegisterInfo {
   BitVector ReservedRegs;
 
   /// Keep track of the physical registers that are live in to the function.
-  /// Live in values are typically arguments in registers, live out values are
-  /// typically return values in registers. LiveIn values are allowed to have
-  /// virtual registers associated with them, stored in the second element.
+  /// Live in values are typically arguments in registers.  LiveIn values are
+  /// allowed to have virtual registers associated with them, stored in the
+  /// second element.
   std::vector<std::pair<unsigned, unsigned> > LiveIns;
 
   MachineRegisterInfo(const MachineRegisterInfo&) LLVM_DELETED_FUNCTION;
@@ -464,20 +464,19 @@ public:
   }
 
   //===--------------------------------------------------------------------===//
-  // LiveIn/LiveOut Management
+  // LiveIn Management
   //===--------------------------------------------------------------------===//
 
-  /// addLiveIn/Out - Add the specified register as a live in/out.  Note that it
+  /// addLiveIn - Add 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.
   void addLiveIn(unsigned Reg, unsigned vreg = 0) {
     LiveIns.push_back(std::make_pair(Reg, vreg));
   }
 
-  // Iteration support for live in/out sets.  These sets are kept in sorted
-  // order by their register number.
+  // Iteration support for the live-ins set.  It's kept in sorted order
+  // by register number.
   typedef std::vector<std::pair<unsigned,unsigned> >::const_iterator
   livein_iterator;
-  typedef std::vector<unsigned>::const_iterator liveout_iterator;
   livein_iterator livein_begin() const { return LiveIns.begin(); }
   livein_iterator livein_end()   const { return LiveIns.end(); }
   bool            livein_empty() const { return LiveIns.empty(); }
diff --git a/include/llvm/CodeGen/MachineTraceMetrics.h b/include/llvm/CodeGen/MachineTraceMetrics.h
index 460730b..eaaa70a 100644
--- a/include/llvm/CodeGen/MachineTraceMetrics.h
+++ b/include/llvm/CodeGen/MachineTraceMetrics.h
@@ -165,12 +165,25 @@ public:
     /// Invalidate height resources when a block below this one has changed.
     void invalidateHeight() { InstrHeight = ~0u; HasValidInstrHeights = false; }
 
-    /// Determine if this block belongs to the same trace as TBI and comes
-    /// before it in the trace.
+    /// Assuming that this is a dominator of TBI, determine if it contains
+    /// useful instruction depths. A dominating block can be above the current
+    /// trace head, and any dependencies from such a far away dominator are not
+    /// expected to affect the critical path.
+    ///
     /// Also returns true when TBI == this.
-    bool isEarlierInSameTrace(const TraceBlockInfo &TBI) const {
-      return hasValidDepth() && TBI.hasValidDepth() &&
-        Head == TBI.Head && InstrDepth <= TBI.InstrDepth;
+    bool isUsefulDominator(const TraceBlockInfo &TBI) const {
+      // The trace for TBI may not even be calculated yet.
+      if (!hasValidDepth() || !TBI.hasValidDepth())
+        return false;
+      // Instruction depths are only comparable if the traces share a head.
+      if (Head != TBI.Head)
+        return false;
+      // It is almost always the case that TBI belongs to the same trace as
+      // this block, but rare convoluted cases involving irreducible control
+      // flow, a dominator may share a trace head without actually being on the
+      // same trace as TBI. This is not a big problem as long as it doesn't
+      // increase the instruction depth.
+      return HasValidInstrDepths && InstrDepth <= TBI.InstrDepth;
     }
 
     // Data-dependency-related information. Per-instruction depth and height
diff --git a/include/llvm/CodeGen/Passes.h b/include/llvm/CodeGen/Passes.h
index 5f710e6..4d559b5 100644
--- a/include/llvm/CodeGen/Passes.h
+++ b/include/llvm/CodeGen/Passes.h
@@ -459,10 +459,6 @@ namespace llvm {
   /// branch folding).
   extern char &GCMachineCodeAnalysisID;
 
-  /// Deleter Pass - Releases GC metadata.
-  ///
-  FunctionPass *createGCInfoDeleter();
-
   /// Creates a pass to print GC metadata.
   ///
   FunctionPass *createGCInfoPrinter(raw_ostream &OS);
diff --git a/include/llvm/CodeGen/ScheduleDAG.h b/include/llvm/CodeGen/ScheduleDAG.h
index d80bdf8..8c959da 100644
--- a/include/llvm/CodeGen/ScheduleDAG.h
+++ b/include/llvm/CodeGen/ScheduleDAG.h
@@ -52,11 +52,21 @@ namespace llvm {
       Order        ///< Any other ordering dependency.
     };
 
+    // Strong dependencies must be respected by the scheduler. Artificial
+    // dependencies may be removed only if they are redundant with another
+    // strong depedence.
+    //
+    // Weak dependencies may be violated by the scheduling strategy, but only if
+    // the strategy can prove it is correct to do so.
+    //
+    // Strong OrderKinds must occur before "Weak".
+    // Weak OrderKinds must occur after "Weak".
     enum OrderKind {
       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 strong DAG edge (no real dependence).
+      Weak,         ///< Arbitrary weak DAG edge.
       Cluster       ///< Weak DAG edge linking a chain of clustered instrs.
     };
 
@@ -205,7 +215,7 @@ namespace llvm {
     /// 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;
+      return getKind() == Order && Contents.OrdKind >= Weak;
     }
 
     /// isArtificial - Test if this is an Order dependence that is marked
diff --git a/include/llvm/CodeGen/ScheduleDAGInstrs.h b/include/llvm/CodeGen/ScheduleDAGInstrs.h
index 94abec2..2219520 100644
--- a/include/llvm/CodeGen/ScheduleDAGInstrs.h
+++ b/include/llvm/CodeGen/ScheduleDAGInstrs.h
@@ -15,18 +15,15 @@
 #ifndef LLVM_CODEGEN_SCHEDULEDAGINSTRS_H
 #define LLVM_CODEGEN_SCHEDULEDAGINSTRS_H
 
-#include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SparseSet.h"
 #include "llvm/ADT/SparseMultiSet.h"
-#include "llvm/CodeGen/MachineDominators.h"
-#include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/ScheduleDAG.h"
 #include "llvm/CodeGen/TargetSchedule.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Target/TargetRegisterInfo.h"
-#include <map>
 
 namespace llvm {
+  class MachineFrameInfo;
   class MachineLoopInfo;
   class MachineDominatorTree;
   class LiveIntervals;
diff --git a/include/llvm/CodeGen/SelectionDAG.h b/include/llvm/CodeGen/SelectionDAG.h
index c25497a..e5adf67 100644
--- a/include/llvm/CodeGen/SelectionDAG.h
+++ b/include/llvm/CodeGen/SelectionDAG.h
@@ -567,7 +567,7 @@ public:
   SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
                   const SDValue *Ops, unsigned NumOps);
   SDValue getNode(unsigned Opcode, DebugLoc DL,
-                  const std::vector<EVT> &ResultTys,
+                  ArrayRef<EVT> ResultTys,
                   const SDValue *Ops, unsigned NumOps);
   SDValue getNode(unsigned Opcode, DebugLoc DL, const EVT *VTs, unsigned NumVTs,
                   const SDValue *Ops, unsigned NumOps);
@@ -831,7 +831,7 @@ public:
   MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
                          EVT VT3, EVT VT4, const SDValue *Ops, unsigned NumOps);
   MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl,
-                         const std::vector<EVT> &ResultTys, const SDValue *Ops,
+                         ArrayRef<EVT> ResultTys, const SDValue *Ops,
                          unsigned NumOps);
   MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, SDVTList VTs,
                          const SDValue *Ops, unsigned NumOps);
diff --git a/include/llvm/CodeGen/SelectionDAGISel.h b/include/llvm/CodeGen/SelectionDAGISel.h
index af7993f..5f503de 100644
--- a/include/llvm/CodeGen/SelectionDAGISel.h
+++ b/include/llvm/CodeGen/SelectionDAGISel.h
@@ -249,16 +249,26 @@ private:
                     const SDValue *Ops, unsigned NumOps, unsigned EmitNodeInfo);
 
   void PrepareEHLandingPad();
+
+  /// \brief Perform instruction selection on all basic blocks in the function.
   void SelectAllBasicBlocks(const Function &Fn);
-  bool TryToFoldFastISelLoad(const LoadInst *LI, const Instruction *FoldInst,
-                             FastISel *FastIS);
-  void FinishBasicBlock();
 
+  /// \brief Perform instruction selection on a single basic block, for
+  /// instructions between \p Begin and \p End.  \p HadTailCall will be set
+  /// to true if a call in the block was translated as a tail call.
   void SelectBasicBlock(BasicBlock::const_iterator Begin,
                         BasicBlock::const_iterator End,
                         bool &HadTailCall);
+
+  bool TryToFoldFastISelLoad(const LoadInst *LI, const Instruction *FoldInst,
+                             FastISel *FastIS);
+  void FinishBasicBlock();
+
   void CodeGenAndEmitDAG();
-  void LowerArguments(const BasicBlock *BB);
+
+  /// \brief Generate instructions for lowering the incoming arguments of the
+  /// given function.
+  void LowerArguments(const Function &F);
 
   void ComputeLiveOutVRegInfo();
 
diff --git a/include/llvm/CodeGen/SelectionDAGNodes.h b/include/llvm/CodeGen/SelectionDAGNodes.h
index 2c34b4f..05f3b14 100644
--- a/include/llvm/CodeGen/SelectionDAGNodes.h
+++ b/include/llvm/CodeGen/SelectionDAGNodes.h
@@ -1298,7 +1298,7 @@ class ConstantPoolSDNode : public SDNode {
     : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool,
              DebugLoc(),
              getSDVTList(VT)), Offset(o), Alignment(Align), TargetFlags(TF) {
-    assert((int)Offset >= 0 && "Offset is too large");
+    assert(Offset >= 0 && "Offset is too large");
     Val.ConstVal = c;
   }
   ConstantPoolSDNode(bool isTarget, MachineConstantPoolValue *v,
@@ -1306,7 +1306,7 @@ class ConstantPoolSDNode : public SDNode {
     : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool,
              DebugLoc(),
              getSDVTList(VT)), Offset(o), Alignment(Align), TargetFlags(TF) {
-    assert((int)Offset >= 0 && "Offset is too large");
+    assert(Offset >= 0 && "Offset is too large");
     Val.MachineCPVal = v;
     Offset |= 1 << (sizeof(unsigned)*CHAR_BIT-1);
   }
@@ -1314,7 +1314,7 @@ public:
   
 
   bool isMachineConstantPoolEntry() const {
-    return (int)Offset < 0;
+    return Offset < 0;
   }
 
   const Constant *getConstVal() const {
diff --git a/include/llvm/CodeGen/SlotIndexes.h b/include/llvm/CodeGen/SlotIndexes.h
index 78fb233..a277080 100644
--- a/include/llvm/CodeGen/SlotIndexes.h
+++ b/include/llvm/CodeGen/SlotIndexes.h
@@ -396,12 +396,16 @@ namespace llvm {
       return index.isValid() ? index.listEntry()->getInstr() : 0;
     }
 
-    /// Returns the next non-null index.
-    SlotIndex getNextNonNullIndex(SlotIndex index) {
-      IndexList::iterator itr(index.listEntry());
-      ++itr;
-      while (itr != indexList.end() && itr->getInstr() == 0) { ++itr; }
-      return SlotIndex(itr, index.getSlot());
+    /// Returns the next non-null index, if one exists.
+    /// Otherwise returns getLastIndex().
+    SlotIndex getNextNonNullIndex(SlotIndex Index) {
+      IndexList::iterator I = Index.listEntry();
+      IndexList::iterator E = indexList.end();
+      while (++I != E)
+        if (I->getInstr())
+          return SlotIndex(I, Index.getSlot());
+      // We reached the end of the function.
+      return getLastIndex();
     }
 
     /// getIndexBefore - Returns the index of the last indexed instruction