Update LLVM to 97654.

14 files changed, 254 insertions, 472 deletions

diff --git a/include/llvm/CodeGen/AsmPrinter.h b/include/llvm/CodeGen/AsmPrinter.h
index 28a1a3e..8ade1bd 100644
--- a/include/llvm/CodeGen/AsmPrinter.h
+++ b/include/llvm/CodeGen/AsmPrinter.h
@@ -223,7 +223,7 @@ namespace llvm {
     void EmitFunctionBody();
 
     /// EmitInstruction - Targets should implement this to emit instructions.
-    virtual void EmitInstruction(const MachineInstr *MI) {
+    virtual void EmitInstruction(const MachineInstr *) {
       assert(0 && "EmitInstruction not implemented");
     }
     
@@ -356,6 +356,11 @@ namespace llvm {
     /// printOffset - This is just convenient handler for printing offsets.
     void printOffset(int64_t Offset) const;
 
+    /// isBlockOnlyReachableByFallthough - Return true if the basic block has
+    /// exactly one predecessor and the control transfer mechanism between
+    /// the predecessor and this block is a fall-through.
+    virtual bool isBlockOnlyReachableByFallthrough(const MachineBasicBlock *MBB) const;
+
   private:
 
     /// processDebugLoc - Processes the debug information of each machine
diff --git a/include/llvm/CodeGen/DAGISelHeader.h b/include/llvm/CodeGen/DAGISelHeader.h
deleted file mode 100644
index 7fda6f7..0000000
--- a/include/llvm/CodeGen/DAGISelHeader.h
+++ /dev/null
@@ -1,414 +0,0 @@
-//==-llvm/CodeGen/DAGISelHeader.h - Common DAG ISel definitions  -*- C++ -*-==//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This file provides definitions of the common, target-independent methods and 
-// data, which is used by SelectionDAG-based instruction selectors.
-//
-// *** NOTE: This file is #included into the middle of the target
-// instruction selector class.  These functions are really methods.
-// This is a little awkward, but it allows this code to be shared
-// by all the targets while still being able to call into
-// target-specific code without using a virtual function call.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_CODEGEN_DAGISEL_HEADER_H
-#define LLVM_CODEGEN_DAGISEL_HEADER_H
-
-/// ISelPosition - Node iterator marking the current position of
-/// instruction selection as it procedes through the topologically-sorted
-/// node list.
-SelectionDAG::allnodes_iterator ISelPosition;
-
-/// IsChainCompatible - Returns true if Chain is Op or Chain does
-/// not reach Op.
-static bool IsChainCompatible(SDNode *Chain, SDNode *Op) {
-  if (Chain->getOpcode() == ISD::EntryToken)
-    return true;
-  if (Chain->getOpcode() == ISD::TokenFactor)
-    return false;
-  if (Chain->getNumOperands() > 0) {
-    SDValue C0 = Chain->getOperand(0);
-    if (C0.getValueType() == MVT::Other)
-      return C0.getNode() != Op && IsChainCompatible(C0.getNode(), Op);
-  }
-  return true;
-}
-
-/// ISelUpdater - helper class to handle updates of the 
-/// instruciton selection graph.
-class VISIBILITY_HIDDEN ISelUpdater : public SelectionDAG::DAGUpdateListener {
-  SelectionDAG::allnodes_iterator &ISelPosition;
-public:
-  explicit ISelUpdater(SelectionDAG::allnodes_iterator &isp)
-    : ISelPosition(isp) {}
-  
-  /// NodeDeleted - Handle nodes deleted from the graph. If the
-  /// node being deleted is the current ISelPosition node, update
-  /// ISelPosition.
-  ///
-  virtual void NodeDeleted(SDNode *N, SDNode *E) {
-    if (ISelPosition == SelectionDAG::allnodes_iterator(N))
-      ++ISelPosition;
-  }
-
-  /// NodeUpdated - Ignore updates for now.
-  virtual void NodeUpdated(SDNode *N) {}
-};
-
-/// ReplaceUses - replace all uses of the old node F with the use
-/// of the new node T.
-DISABLE_INLINE void ReplaceUses(SDValue F, SDValue T) {
-  ISelUpdater ISU(ISelPosition);
-  CurDAG->ReplaceAllUsesOfValueWith(F, T, &ISU);
-}
-
-/// ReplaceUses - replace all uses of the old nodes F with the use
-/// of the new nodes T.
-DISABLE_INLINE void ReplaceUses(const SDValue *F, const SDValue *T,
-                                unsigned Num) {
-  ISelUpdater ISU(ISelPosition);
-  CurDAG->ReplaceAllUsesOfValuesWith(F, T, Num, &ISU);
-}
-
-/// ReplaceUses - replace all uses of the old node F with the use
-/// of the new node T.
-DISABLE_INLINE void ReplaceUses(SDNode *F, SDNode *T) {
-  ISelUpdater ISU(ISelPosition);
-  CurDAG->ReplaceAllUsesWith(F, T, &ISU);
-}
-
-/// SelectRoot - Top level entry to DAG instruction selector.
-/// Selects instructions starting at the root of the current DAG.
-void SelectRoot(SelectionDAG &DAG) {
-  SelectRootInit();
-
-  // Create a dummy node (which is not added to allnodes), that adds
-  // a reference to the root node, preventing it from being deleted,
-  // and tracking any changes of the root.
-  HandleSDNode Dummy(CurDAG->getRoot());
-  ISelPosition = llvm::next(SelectionDAG::allnodes_iterator(CurDAG->getRoot().getNode()));
-
-  // The AllNodes list is now topological-sorted. Visit the
-  // nodes by starting at the end of the list (the root of the
-  // graph) and preceding back toward the beginning (the entry
-  // node).
-  while (ISelPosition != CurDAG->allnodes_begin()) {
-    SDNode *Node = --ISelPosition;
-    // Skip dead nodes. DAGCombiner is expected to eliminate all dead nodes,
-    // but there are currently some corner cases that it misses. Also, this
-    // makes it theoretically possible to disable the DAGCombiner.
-    if (Node->use_empty())
-      continue;
-#if 0
-    DAG.setSubgraphColor(Node, "red");
-#endif
-    SDNode *ResNode = Select(Node);
-    // If node should not be replaced, continue with the next one.
-    if (ResNode == Node)
-      continue;
-    // Replace node.
-    if (ResNode) {
-#if 0
-      DAG.setSubgraphColor(ResNode, "yellow");
-      DAG.setSubgraphColor(ResNode, "black");
-#endif
-      ReplaceUses(Node, ResNode);
-    }
-    // If after the replacement this node is not used any more,
-    // remove this dead node.
-    if (Node->use_empty()) { // Don't delete EntryToken, etc.
-      ISelUpdater ISU(ISelPosition);
-      CurDAG->RemoveDeadNode(Node, &ISU);
-    }
-  }
-
-  CurDAG->setRoot(Dummy.getValue());
-}
-
-
-/// CheckInteger - Return true if the specified node is not a ConstantSDNode or
-/// if it doesn't have the specified value.
-static bool CheckInteger(SDValue V, int64_t Val) {
-  ConstantSDNode *C = dyn_cast<ConstantSDNode>(V);
-  return C == 0 || C->getSExtValue() != Val;
-}
-
-/// CheckAndImmediate - Check to see if the specified node is an and with an
-/// immediate returning true on failure.
-///
-/// FIXME: Inline this gunk into CheckAndMask.
-bool CheckAndImmediate(SDValue V, int64_t Val) {
-  if (V->getOpcode() == ISD::AND)
-    if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(V->getOperand(1)))
-      if (CheckAndMask(V.getOperand(0), C, Val))
-        return false;
-  return true;
-}
-
-/// CheckOrImmediate - Check to see if the specified node is an or with an
-/// immediate returning true on failure.
-///
-/// FIXME: Inline this gunk into CheckOrMask.
-bool CheckOrImmediate(SDValue V, int64_t Val) {
-  if (V->getOpcode() == ISD::OR)
-    if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(V->getOperand(1)))
-      if (CheckOrMask(V.getOperand(0), C, Val))
-        return false;
-  return true;
-}
-
-// These functions are marked always inline so that Idx doesn't get pinned to
-// the stack.
-ALWAYS_INLINE static int8_t
-GetInt1(const unsigned char *MatcherTable, unsigned &Idx) {
-  return MatcherTable[Idx++];
-}
-
-ALWAYS_INLINE static int16_t
-GetInt2(const unsigned char *MatcherTable, unsigned &Idx) {
-  int16_t Val = GetInt1(MatcherTable, Idx);
-  Val |= int16_t(GetInt1(MatcherTable, Idx)) << 8;
-  return Val;
-}
-
-ALWAYS_INLINE static int32_t
-GetInt4(const unsigned char *MatcherTable, unsigned &Idx) {
-  int32_t Val = GetInt2(MatcherTable, Idx);
-  Val |= int32_t(GetInt2(MatcherTable, Idx)) << 16;
-  return Val;
-}
-
-ALWAYS_INLINE static int64_t
-GetInt8(const unsigned char *MatcherTable, unsigned &Idx) {
-  int64_t Val = GetInt4(MatcherTable, Idx);
-  Val |= int64_t(GetInt4(MatcherTable, Idx)) << 32;
-  return Val;
-}
-
-enum BuiltinOpcodes {
-  OPC_Emit,
-  OPC_Push,
-  OPC_Record,
-  OPC_MoveChild,
-  OPC_MoveParent,
-  OPC_CheckSame,
-  OPC_CheckPatternPredicate,
-  OPC_CheckPredicate,
-  OPC_CheckOpcode,
-  OPC_CheckType,
-  OPC_CheckInteger1, OPC_CheckInteger2, OPC_CheckInteger4, OPC_CheckInteger8,
-  OPC_CheckCondCode,
-  OPC_CheckValueType,
-  OPC_CheckComplexPat,
-  OPC_CheckAndImm1, OPC_CheckAndImm2, OPC_CheckAndImm4, OPC_CheckAndImm8,
-  OPC_CheckOrImm1, OPC_CheckOrImm2, OPC_CheckOrImm4, OPC_CheckOrImm8,
-  OPC_IsProfitableToFold,
-  OPC_IsLegalToFold
-};
-
-struct MatchScope {
-  /// FailIndex - If this match fails, this is the index to continue with.
-  unsigned FailIndex;
-  
-  /// NodeStackSize - The size of the node stack when the scope was formed.
-  unsigned NodeStackSize;
-  
-  /// NumRecordedNodes - The number of recorded nodes when the scope was formed.
-  unsigned NumRecordedNodes;
-};
-
-SDNode *SelectCodeCommon(SDNode *NodeToMatch, const unsigned char *MatcherTable,
-                         unsigned TableSize) {
-  switch (NodeToMatch->getOpcode()) {
-  default:
-    break;
-  case ISD::EntryToken:       // These nodes remain the same.
-  case ISD::BasicBlock:
-  case ISD::Register:
-  case ISD::HANDLENODE:
-  case ISD::TargetConstant:
-  case ISD::TargetConstantFP:
-  case ISD::TargetConstantPool:
-  case ISD::TargetFrameIndex:
-  case ISD::TargetExternalSymbol:
-  case ISD::TargetBlockAddress:
-  case ISD::TargetJumpTable:
-  case ISD::TargetGlobalTLSAddress:
-  case ISD::TargetGlobalAddress:
-  case ISD::TokenFactor:
-  case ISD::CopyFromReg:
-  case ISD::CopyToReg:
-    return 0;
-  case ISD::AssertSext:
-  case ISD::AssertZext:
-    ReplaceUses(SDValue(NodeToMatch, 0), NodeToMatch->getOperand(0));
-    return 0;
-  case ISD::INLINEASM: return Select_INLINEASM(NodeToMatch);
-  case ISD::EH_LABEL:  return Select_EH_LABEL(NodeToMatch);
-  case ISD::UNDEF:     return Select_UNDEF(NodeToMatch);
-  }
-  
-  assert(!NodeToMatch->isMachineOpcode() && "Node already selected!");
-  
-  SmallVector<MatchScope, 8> MatchScopes;
-  
-  // RecordedNodes - This is the set of nodes that have been recorded by the
-  // state machine.
-  SmallVector<SDValue, 8> RecordedNodes;
-  
-  // Set up the node stack with NodeToMatch as the only node on the stack.
-  SmallVector<SDValue, 8> NodeStack;
-  SDValue N = SDValue(NodeToMatch, 0);
-  NodeStack.push_back(N);
-  
-  // Interpreter starts at opcode #0.
-  unsigned MatcherIndex = 0;
-  while (1) {
-    assert(MatcherIndex < TableSize && "Invalid index");
-    switch ((BuiltinOpcodes)MatcherTable[MatcherIndex++]) {
-    case OPC_Emit: {
-      errs() << "EMIT NODE\n";
-      return 0;
-    }
-    case OPC_Push: {
-      unsigned NumToSkip = MatcherTable[MatcherIndex++];
-      MatchScope NewEntry;
-      NewEntry.FailIndex = MatcherIndex+NumToSkip;
-      NewEntry.NodeStackSize = NodeStack.size();
-      NewEntry.NumRecordedNodes = RecordedNodes.size();
-      MatchScopes.push_back(NewEntry);
-      continue;
-    }
-    case OPC_Record:
-      // Remember this node, it may end up being an operand in the pattern.
-      RecordedNodes.push_back(N);
-      continue;
-        
-    case OPC_MoveChild: {
-      unsigned Child = MatcherTable[MatcherIndex++];
-      if (Child >= N.getNumOperands())
-        break;  // Match fails if out of range child #.
-      N = N.getOperand(Child);
-      NodeStack.push_back(N);
-      continue;
-    }
-        
-    case OPC_MoveParent:
-      // Pop the current node off the NodeStack.
-      NodeStack.pop_back();
-      assert(!NodeStack.empty() && "Node stack imbalance!");
-      N = NodeStack.back();  
-      continue;
-     
-    case OPC_CheckSame: {
-      // Accept if it is exactly the same as a previously recorded node.
-      unsigned RecNo = MatcherTable[MatcherIndex++];
-      assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
-      if (N != RecordedNodes[RecNo]) break;
-      continue;
-    }
-    case OPC_CheckPatternPredicate:
-      if (!CheckPatternPredicate(MatcherTable[MatcherIndex++])) break;
-      continue;
-    case OPC_CheckPredicate:
-      if (!CheckNodePredicate(N.getNode(), MatcherTable[MatcherIndex++])) break;
-      continue;
-    case OPC_CheckComplexPat: {
-      unsigned PatNo = MatcherTable[MatcherIndex++];
-      (void)PatNo;
-      // FIXME: CHECK IT.
-      continue;
-    }
-        
-    case OPC_CheckOpcode:
-      if (N->getOpcode() != MatcherTable[MatcherIndex++]) break;
-      continue;
-    case OPC_CheckType:
-      if (N.getValueType() !=
-          (MVT::SimpleValueType)MatcherTable[MatcherIndex++]) break;
-      continue;
-    case OPC_CheckCondCode:
-      if (cast<CondCodeSDNode>(N)->get() !=
-          (ISD::CondCode)MatcherTable[MatcherIndex++]) break;
-      continue;
-    case OPC_CheckValueType:
-      if (cast<VTSDNode>(N)->getVT() !=
-          (MVT::SimpleValueType)MatcherTable[MatcherIndex++]) break;
-      continue;
-
-    case OPC_CheckInteger1:
-      if (CheckInteger(N, GetInt1(MatcherTable, MatcherIndex))) break;
-      continue;
-    case OPC_CheckInteger2:
-      if (CheckInteger(N, GetInt2(MatcherTable, MatcherIndex))) break;
-      continue;
-    case OPC_CheckInteger4:
-      if (CheckInteger(N, GetInt4(MatcherTable, MatcherIndex))) break;
-      continue;
-    case OPC_CheckInteger8:
-      if (CheckInteger(N, GetInt8(MatcherTable, MatcherIndex))) break;
-      continue;
-        
-    case OPC_CheckAndImm1:
-      if (CheckAndImmediate(N, GetInt1(MatcherTable, MatcherIndex))) break;
-      continue;
-    case OPC_CheckAndImm2:
-      if (CheckAndImmediate(N, GetInt2(MatcherTable, MatcherIndex))) break;
-      continue;
-    case OPC_CheckAndImm4:
-      if (CheckAndImmediate(N, GetInt4(MatcherTable, MatcherIndex))) break;
-      continue;
-    case OPC_CheckAndImm8:
-      if (CheckAndImmediate(N, GetInt8(MatcherTable, MatcherIndex))) break;
-      continue;
-
-    case OPC_CheckOrImm1:
-      if (CheckOrImmediate(N, GetInt1(MatcherTable, MatcherIndex))) break;
-      continue;
-    case OPC_CheckOrImm2:
-      if (CheckOrImmediate(N, GetInt2(MatcherTable, MatcherIndex))) break;
-      continue;
-    case OPC_CheckOrImm4:
-      if (CheckOrImmediate(N, GetInt4(MatcherTable, MatcherIndex))) break;
-      continue;
-    case OPC_CheckOrImm8:
-      if (CheckOrImmediate(N, GetInt8(MatcherTable, MatcherIndex))) break;
-      continue;
-        
-    case OPC_IsProfitableToFold:
-      assert(!NodeStack.size() == 1 && "No parent node");
-      if (!IsProfitableToFold(N, NodeStack[NodeStack.size()-2].getNode(),
-                              NodeToMatch))
-        break;
-      continue;
-    case OPC_IsLegalToFold:
-      assert(!NodeStack.size() == 1 && "No parent node");
-      if (!IsLegalToFold(N, NodeStack[NodeStack.size()-2].getNode(),
-                         NodeToMatch))
-        break;
-      continue;
-    }
-    
-    // If the code reached this point, then the match failed pop out to the next
-    // match scope.
-    if (MatchScopes.empty()) {
-      CannotYetSelect(NodeToMatch);
-      return 0;
-    }
-    
-    RecordedNodes.resize(MatchScopes.back().NumRecordedNodes);
-    NodeStack.resize(MatchScopes.back().NodeStackSize);
-    MatcherIndex = MatchScopes.back().FailIndex;
-    MatchScopes.pop_back();
-  }
-}
-    
-
-#endif /* LLVM_CODEGEN_DAGISEL_HEADER_H */
diff --git a/include/llvm/CodeGen/LiveInterval.h b/include/llvm/CodeGen/LiveInterval.h
index 512c94d..eb5901c 100644
--- a/include/llvm/CodeGen/LiveInterval.h
+++ b/include/llvm/CodeGen/LiveInterval.h
@@ -569,6 +569,16 @@ namespace llvm {
     ///
     unsigned getSize() const;
 
+    /// isSpillable - Can this interval be spilled?
+    bool isSpillable() const {
+      return weight != HUGE_VALF;
+    }
+
+    /// markNotSpillable - Mark interval as not spillable
+    void markNotSpillable() {
+      weight = HUGE_VALF;
+    }
+
     /// ComputeJoinedWeight - Set the weight of a live interval after
     /// Other has been merged into it.
     void ComputeJoinedWeight(const LiveInterval &Other);
diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h
index d7ff8da..e8856ac 100644
--- a/include/llvm/CodeGen/LiveIntervalAnalysis.h
+++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h
@@ -70,8 +70,15 @@ namespace llvm {
     static char ID; // Pass identification, replacement for typeid
     LiveIntervals() : MachineFunctionPass(&ID) {}
 
-    static float getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) {
-      return (isDef + isUse) * powf(10.0F, (float)loopDepth);
+    // Calculate the spill weight to assign to a single instruction.
+    static float getSpillWeight(bool isDef, bool isUse, unsigned loopDepth);
+
+    // After summing the spill weights of all defs and uses, the final weight
+    // should be normalized, dividing the weight of the interval by its size.
+    // This encourages spilling of intervals that are large and have few uses,
+    // and discourages spilling of small intervals with many uses.
+    void normalizeSpillWeight(LiveInterval &li) {
+      li.weight /= getApproximateInstructionCount(li) + 25;
     }
 
     typedef Reg2IntervalMap::iterator iterator;
@@ -409,6 +416,9 @@ namespace llvm {
         DenseMap<unsigned,unsigned> &MBBVRegsMap,
         std::vector<LiveInterval*> &NewLIs);
 
+    // Normalize the spill weight of all the intervals in NewLIs.
+    void normalizeSpillWeights(std::vector<LiveInterval*> &NewLIs);
+
     static LiveInterval* createInterval(unsigned Reg);
 
     void printInstrs(raw_ostream &O) const;
diff --git a/include/llvm/CodeGen/LiveVariables.h b/include/llvm/CodeGen/LiveVariables.h
index a7bf600..fc5ea6f 100644
--- a/include/llvm/CodeGen/LiveVariables.h
+++ b/include/llvm/CodeGen/LiveVariables.h
@@ -124,6 +124,11 @@ private:
   ///
   std::vector<VarInfo> VirtRegInfo;
 
+  /// PHIJoins - list of virtual registers that are PHI joins. These registers
+  /// may have multiple definitions, and they require special handling when
+  /// building live intervals.
+  SparseBitVector<> PHIJoins;
+
   /// ReservedRegisters - This vector keeps track of which registers
   /// are reserved register which are not allocatable by the target machine.
   /// We can not track liveness for values that are in this set.
@@ -295,6 +300,12 @@ public:
   void addNewBlock(MachineBasicBlock *BB,
                    MachineBasicBlock *DomBB,
                    MachineBasicBlock *SuccBB);
+
+  /// isPHIJoin - Return true if Reg is a phi join register.
+  bool isPHIJoin(unsigned Reg) { return PHIJoins.test(Reg); }
+
+  /// setPHIJoin - Mark Reg as a phi join register.
+  void setPHIJoin(unsigned Reg) { PHIJoins.set(Reg); }
 };
 
 } // End llvm namespace
diff --git a/include/llvm/CodeGen/MachineBasicBlock.h b/include/llvm/CodeGen/MachineBasicBlock.h
index db82ba5..d92650b4 100644
--- a/include/llvm/CodeGen/MachineBasicBlock.h
+++ b/include/llvm/CodeGen/MachineBasicBlock.h
@@ -285,11 +285,6 @@ public:
   /// it returns end()
   iterator getFirstTerminator();
 
-  /// isOnlyReachableViaFallthough - Return true if this basic block has
-  /// exactly one predecessor and the control transfer mechanism between
-  /// the predecessor and this block is a fall-through.
-  bool isOnlyReachableByFallthrough() const;
-
   void pop_front() { Insts.pop_front(); }
   void pop_back() { Insts.pop_back(); }
   void push_back(MachineInstr *MI) { Insts.push_back(MI); }
diff --git a/include/llvm/CodeGen/MachineInstr.h b/include/llvm/CodeGen/MachineInstr.h
index 6e33fb3..66be26c 100644
--- a/include/llvm/CodeGen/MachineInstr.h
+++ b/include/llvm/CodeGen/MachineInstr.h
@@ -179,17 +179,16 @@ public:
     return MemRefsEnd - MemRefs == 1;
   }
 
+  enum MICheckType {
+    CheckDefs,      // Check all operands for equality
+    IgnoreDefs,     // Ignore all definitions
+    IgnoreVRegDefs  // Ignore virtual register definitions
+  };
+
   /// isIdenticalTo - Return true if this instruction is identical to (same
   /// opcode and same operands as) the specified instruction.
-  bool isIdenticalTo(const MachineInstr *Other) const {
-    if (Other->getOpcode() != getOpcode() ||
-        Other->getNumOperands() != getNumOperands())
-      return false;
-    for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
-      if (!getOperand(i).isIdenticalTo(Other->getOperand(i)))
-        return false;
-    return true;
-  }
+  bool isIdenticalTo(const MachineInstr *Other,
+                     MICheckType Check = CheckDefs) const;
 
   /// removeFromParent - This method unlinks 'this' from the containing basic
   /// block, and returns it, but does not delete it.
@@ -331,13 +330,13 @@ public:
   /// isSafeToMove - Return true if it is safe to move this instruction. If
   /// SawStore is set to true, it means that there is a store (or call) between
   /// the instruction's location and its intended destination.
-  bool isSafeToMove(const TargetInstrInfo *TII, bool &SawStore,
-                    AliasAnalysis *AA) const;
+  bool isSafeToMove(const TargetInstrInfo *TII, AliasAnalysis *AA,
+                    bool &SawStore) const;
 
   /// isSafeToReMat - Return true if it's safe to rematerialize the specified
   /// instruction which defined the specified register instead of copying it.
-  bool isSafeToReMat(const TargetInstrInfo *TII, unsigned DstReg,
-                     AliasAnalysis *AA) const;
+  bool isSafeToReMat(const TargetInstrInfo *TII, AliasAnalysis *AA,
+                     unsigned DstReg) const;
 
   /// hasVolatileMemoryRef - Return true if this instruction may have a
   /// volatile memory reference, or if the information describing the
diff --git a/include/llvm/CodeGen/MachineInstrBuilder.h b/include/llvm/CodeGen/MachineInstrBuilder.h
index a263a97..47f7cf7 100644
--- a/include/llvm/CodeGen/MachineInstrBuilder.h
+++ b/include/llvm/CodeGen/MachineInstrBuilder.h
@@ -127,7 +127,7 @@ public:
     return *this;
   }
 
-  const MachineInstrBuilder &addMetadata(MDNode *MD) const {
+  const MachineInstrBuilder &addMetadata(const MDNode *MD) const {
     MI->addOperand(MachineOperand::CreateMetadata(MD));
     return *this;
   }
diff --git a/include/llvm/CodeGen/MachineOperand.h b/include/llvm/CodeGen/MachineOperand.h
index dac0092..0978057 100644
--- a/include/llvm/CodeGen/MachineOperand.h
+++ b/include/llvm/CodeGen/MachineOperand.h
@@ -19,14 +19,14 @@
 
 namespace llvm {
   
-class ConstantFP;
 class BlockAddress;
-class MachineBasicBlock;
+class ConstantFP;
 class GlobalValue;
+class MachineBasicBlock;
 class MachineInstr;
-class TargetMachine;
 class MachineRegisterInfo;
 class MDNode;
+class TargetMachine;
 class raw_ostream;
   
 /// MachineOperand class - Representation of each machine instruction operand.
@@ -100,7 +100,7 @@ private:
     MachineBasicBlock *MBB;   // For MO_MachineBasicBlock.
     const ConstantFP *CFP;    // For MO_FPImmediate.
     int64_t ImmVal;           // For MO_Immediate.
-    MDNode *MD;               // For MO_Metadata.
+    const MDNode *MD;         // For MO_Metadata.
 
     struct {                  // For MO_Register.
       unsigned RegNo;
@@ -467,7 +467,7 @@ public:
     Op.setTargetFlags(TargetFlags);
     return Op;
   }
-  static MachineOperand CreateMetadata(MDNode *Meta) {
+  static MachineOperand CreateMetadata(const MDNode *Meta) {
     MachineOperand Op(MachineOperand::MO_Metadata);
     Op.Contents.MD = Meta;
     return Op;
diff --git a/include/llvm/CodeGen/Passes.h b/include/llvm/CodeGen/Passes.h
index dbc73cb..911be22 100644
--- a/include/llvm/CodeGen/Passes.h
+++ b/include/llvm/CodeGen/Passes.h
@@ -162,6 +162,10 @@ namespace llvm {
   /// 
   FunctionPass *createGCInfoPrinter(raw_ostream &OS);
   
+  /// createMachineCSEPass - This pass performs global CSE on machine
+  /// instructions.
+  FunctionPass *createMachineCSEPass();
+
   /// createMachineLICMPass - This pass performs LICM on machine instructions.
   /// 
   FunctionPass *createMachineLICMPass();
@@ -187,7 +191,7 @@ namespace llvm {
   /// createMachineVerifierPass - This pass verifies cenerated machine code
   /// instructions for correctness.
   ///
-  /// @param allowPhysDoubleDefs ignore double definitions of
+  /// @param allowDoubleDefs ignore double definitions of
   ///        registers. Useful before LiveVariables has run.
   FunctionPass *createMachineVerifierPass(bool allowDoubleDefs);
 
diff --git a/include/llvm/CodeGen/SelectionDAG.h b/include/llvm/CodeGen/SelectionDAG.h
index e628603..ad01e89 100644
--- a/include/llvm/CodeGen/SelectionDAG.h
+++ b/include/llvm/CodeGen/SelectionDAG.h
@@ -668,27 +668,8 @@ public:
   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, SDVTList VTs,
                        const SDValue *Ops, unsigned NumOps);
 
-  /// MorphNodeTo - These *mutate* the specified node to have the specified
+  /// MorphNodeTo - This *mutates* the specified node to have the specified
   /// return type, opcode, and operands.
-  SDNode *MorphNodeTo(SDNode *N, unsigned Opc, EVT VT);
-  SDNode *MorphNodeTo(SDNode *N, unsigned Opc, EVT VT, SDValue Op1);
-  SDNode *MorphNodeTo(SDNode *N, unsigned Opc, EVT VT,
-                      SDValue Op1, SDValue Op2);
-  SDNode *MorphNodeTo(SDNode *N, unsigned Opc, EVT VT,
-                      SDValue Op1, SDValue Op2, SDValue Op3);
-  SDNode *MorphNodeTo(SDNode *N, unsigned Opc, EVT VT,
-                      const SDValue *Ops, unsigned NumOps);
-  SDNode *MorphNodeTo(SDNode *N, unsigned Opc, EVT VT1, EVT VT2);
-  SDNode *MorphNodeTo(SDNode *N, unsigned Opc, EVT VT1,
-                      EVT VT2, const SDValue *Ops, unsigned NumOps);
-  SDNode *MorphNodeTo(SDNode *N, unsigned Opc, EVT VT1,
-                      EVT VT2, EVT VT3, const SDValue *Ops, unsigned NumOps);
-  SDNode *MorphNodeTo(SDNode *N, unsigned Opc, EVT VT1,
-                      EVT VT2, SDValue Op1);
-  SDNode *MorphNodeTo(SDNode *N, unsigned Opc, EVT VT1,
-                      EVT VT2, SDValue Op1, SDValue Op2);
-  SDNode *MorphNodeTo(SDNode *N, unsigned Opc, EVT VT1,
-                      EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3);
   SDNode *MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs,
                       const SDValue *Ops, unsigned NumOps);
 
@@ -898,6 +879,15 @@ public:
   /// isKnownNeverNan - Test whether the given SDValue is known to never be NaN.
   bool isKnownNeverNaN(SDValue Op) const;
 
+  /// isKnownNeverZero - Test whether the given SDValue is known to never be
+  /// positive or negative Zero.
+  bool isKnownNeverZero(SDValue Op) const;
+
+  /// isEqualTo - Test whether two SDValues are known to compare equal. This
+  /// is true if they are the same value, or if one is negative zero and the
+  /// other positive zero.
+  bool isEqualTo(SDValue A, SDValue B) const;
+
   /// isVerifiedDebugInfoDesc - Returns true if the specified SDValue has
   /// been verified as a debug information descriptor.
   bool isVerifiedDebugInfoDesc(SDValue Op) const;
diff --git a/include/llvm/CodeGen/SelectionDAGISel.h b/include/llvm/CodeGen/SelectionDAGISel.h
index 0be91b4..23ff001 100644
--- a/include/llvm/CodeGen/SelectionDAGISel.h
+++ b/include/llvm/CodeGen/SelectionDAGISel.h
@@ -68,12 +68,18 @@ public:
   unsigned MakeReg(EVT VT);
 
   virtual void EmitFunctionEntryCode(Function &Fn, MachineFunction &MF) {}
-  virtual void InstructionSelect() = 0;
   
-  void SelectRootInit() {
-    DAGSize = CurDAG->AssignTopologicalOrder();
-  }
-
+  /// PreprocessISelDAG - This hook allows targets to hack on the graph before
+  /// instruction selection starts.
+  virtual void PreprocessISelDAG() {}
+  
+  /// PostprocessISelDAG() - This hook allows the target to hack on the graph
+  /// right after selection.
+  virtual void PostprocessISelDAG() {}
+  
+  /// Select - Main hook targets implement to select a node.
+  virtual SDNode *Select(SDNode *N) = 0;
+  
   /// SelectInlineAsmMemoryOperand - Select the specified address as a target
   /// addressing mode, according to the specified constraint code.  If this does
   /// not match or is not implemented, return true.  The resultant operands
@@ -91,21 +97,138 @@ public:
 
   /// IsLegalToFold - Returns true if the specific operand node N of
   /// U can be folded during instruction selection that starts at Root.
-  virtual bool IsLegalToFold(SDValue N, SDNode *U, SDNode *Root) const;
+  bool IsLegalToFold(SDValue N, SDNode *U, SDNode *Root,
+                     bool IgnoreChains = false) const;
 
   /// CreateTargetHazardRecognizer - Return a newly allocated hazard recognizer
   /// to use for this target when scheduling the DAG.
   virtual ScheduleHazardRecognizer *CreateTargetHazardRecognizer();
   
+  
+  // Opcodes used by the DAG state machine:
+  enum BuiltinOpcodes {
+    OPC_Scope,
+    OPC_RecordNode,
+    OPC_RecordChild0, OPC_RecordChild1, OPC_RecordChild2, OPC_RecordChild3, 
+    OPC_RecordChild4, OPC_RecordChild5, OPC_RecordChild6, OPC_RecordChild7,
+    OPC_RecordMemRef,
+    OPC_CaptureFlagInput,
+    OPC_MoveChild,
+    OPC_MoveParent,
+    OPC_CheckSame,
+    OPC_CheckPatternPredicate,
+    OPC_CheckPredicate,
+    OPC_CheckOpcode,
+    OPC_SwitchOpcode,
+    OPC_CheckType,
+    OPC_SwitchType,
+    OPC_CheckChild0Type, OPC_CheckChild1Type, OPC_CheckChild2Type,
+    OPC_CheckChild3Type, OPC_CheckChild4Type, OPC_CheckChild5Type,
+    OPC_CheckChild6Type, OPC_CheckChild7Type,
+    OPC_CheckInteger,
+    OPC_CheckCondCode,
+    OPC_CheckValueType,
+    OPC_CheckComplexPat,
+    OPC_CheckAndImm, OPC_CheckOrImm,
+    OPC_CheckFoldableChainNode,
+    
+    OPC_EmitInteger,
+    OPC_EmitRegister,
+    OPC_EmitConvertToTarget,
+    OPC_EmitMergeInputChains,
+    OPC_EmitCopyToReg,
+    OPC_EmitNodeXForm,
+    OPC_EmitNode,
+    OPC_MorphNodeTo,
+    OPC_MarkFlagResults,
+    OPC_CompleteMatch
+  };
+  
+  enum {
+    OPFL_None       = 0,     // Node has no chain or flag input and isn't variadic.
+    OPFL_Chain      = 1,     // Node has a chain input.
+    OPFL_FlagInput  = 2,     // Node has a flag input.
+    OPFL_FlagOutput = 4,     // Node has a flag output.
+    OPFL_MemRefs    = 8,     // Node gets accumulated MemRefs.
+    OPFL_Variadic0  = 1<<4,  // Node is variadic, root has 0 fixed inputs.
+    OPFL_Variadic1  = 2<<4,  // Node is variadic, root has 1 fixed inputs.
+    OPFL_Variadic2  = 3<<4,  // Node is variadic, root has 2 fixed inputs.
+    OPFL_Variadic3  = 4<<4,  // Node is variadic, root has 3 fixed inputs.
+    OPFL_Variadic4  = 5<<4,  // Node is variadic, root has 4 fixed inputs.
+    OPFL_Variadic5  = 6<<4,  // Node is variadic, root has 5 fixed inputs.
+    OPFL_Variadic6  = 7<<4,  // Node is variadic, root has 6 fixed inputs.
+    
+    OPFL_VariadicInfo = OPFL_Variadic6
+  };
+  
+  /// getNumFixedFromVariadicInfo - Transform an EmitNode flags word into the
+  /// number of fixed arity values that should be skipped when copying from the
+  /// root.
+  static inline int getNumFixedFromVariadicInfo(unsigned Flags) {
+    return ((Flags&OPFL_VariadicInfo) >> 4)-1;
+  }
+  
+  
 protected:
   /// DAGSize - Size of DAG being instruction selected.
   ///
   unsigned DAGSize;
+  
+  /// ISelPosition - Node iterator marking the current position of
+  /// instruction selection as it procedes through the topologically-sorted
+  /// node list.
+  SelectionDAG::allnodes_iterator ISelPosition;
+
+  
+  /// ISelUpdater - helper class to handle updates of the 
+  /// instruction selection graph.
+  class ISelUpdater : public SelectionDAG::DAGUpdateListener {
+    SelectionDAG::allnodes_iterator &ISelPosition;
+  public:
+    explicit ISelUpdater(SelectionDAG::allnodes_iterator &isp)
+      : ISelPosition(isp) {}
+    
+    /// NodeDeleted - Handle nodes deleted from the graph. If the
+    /// node being deleted is the current ISelPosition node, update
+    /// ISelPosition.
+    ///
+    virtual void NodeDeleted(SDNode *N, SDNode *E) {
+      if (ISelPosition == SelectionDAG::allnodes_iterator(N))
+        ++ISelPosition;
+    }
+    
+    /// NodeUpdated - Ignore updates for now.
+    virtual void NodeUpdated(SDNode *N) {}
+  };
+  
+  /// ReplaceUses - replace all uses of the old node F with the use
+  /// of the new node T.
+  void ReplaceUses(SDValue F, SDValue T) {
+    ISelUpdater ISU(ISelPosition);
+    CurDAG->ReplaceAllUsesOfValueWith(F, T, &ISU);
+  }
+  
+  /// ReplaceUses - replace all uses of the old nodes F with the use
+  /// of the new nodes T.
+  void ReplaceUses(const SDValue *F, const SDValue *T, unsigned Num) {
+    ISelUpdater ISU(ISelPosition);
+    CurDAG->ReplaceAllUsesOfValuesWith(F, T, Num, &ISU);
+  }
+  
+  /// ReplaceUses - replace all uses of the old node F with the use
+  /// of the new node T.
+  void ReplaceUses(SDNode *F, SDNode *T) {
+    ISelUpdater ISU(ISelPosition);
+    CurDAG->ReplaceAllUsesWith(F, T, &ISU);
+  }
+  
 
   /// SelectInlineAsmMemoryOperands - Calls to this are automatically generated
   /// by tblgen.  Others should not call it.
   void SelectInlineAsmMemoryOperands(std::vector<SDValue> &Ops);
 
+  
+public:
   // Calls to these predicates are generated by tblgen.
   bool CheckAndMask(SDValue LHS, ConstantSDNode *RHS,
                     int64_t DesiredMaskS) const;
@@ -122,8 +245,8 @@ protected:
     return 0;
   }
 
-  /// CheckNodePredicate - This function is generated by tblgen in the
-  /// target.  It runs node predicate #PredNo and returns true if it succeeds or
+  /// CheckNodePredicate - This function is generated by tblgen in the target.
+  /// It runs node predicate number PredNo and returns true if it succeeds or
   /// false if it fails.  The number is a private implementation
   /// detail to the code tblgen produces.
   virtual bool CheckNodePredicate(SDNode *N, unsigned PredNo) const {
@@ -131,6 +254,23 @@ protected:
     return 0;
   }
   
+  virtual bool CheckComplexPattern(SDNode *Root, SDValue N, unsigned PatternNo,
+                                   SmallVectorImpl<SDValue> &Result) {
+    assert(0 && "Tblgen should generate the implementation of this!");
+    return false;
+  }
+  
+  virtual SDValue RunSDNodeXForm(SDValue V, unsigned XFormNo) {
+    assert(0 && "Tblgen shoudl generate this!");
+    return SDValue();
+  }
+
+  SDNode *SelectCodeCommon(SDNode *NodeToMatch,
+                           const unsigned char *MatcherTable,
+                           unsigned TableSize);
+  
+private:
+  
   // Calls to these functions are generated by tblgen.
   SDNode *Select_INLINEASM(SDNode *N);
   SDNode *Select_UNDEF(SDNode *N);
@@ -139,6 +279,10 @@ protected:
   void CannotYetSelectIntrinsic(SDNode *N);
 
 private:
+  void DoInstructionSelection();
+  SDNode *MorphNode(SDNode *Node, unsigned TargetOpc, SDVTList VTs,
+                    const SDValue *Ops, unsigned NumOps, unsigned EmitNodeInfo);
+  
   void SelectAllBasicBlocks(Function &Fn, MachineFunction &MF,
                             MachineModuleInfo *MMI,
                             DwarfWriter *DW,
@@ -164,6 +308,16 @@ private:
   /// one preferred by the target.
   ///
   ScheduleDAGSDNodes *CreateScheduler();
+  
+  /// OpcodeOffset - This is a cache used to dispatch efficiently into isel
+  /// state machines that start with a OPC_SwitchOpcode node.
+  std::vector<unsigned> OpcodeOffset;
+  
+  void UpdateChainsAndFlags(SDNode *NodeToMatch, SDValue InputChain,
+                            const SmallVectorImpl<SDNode*> &ChainNodesMatched,
+                            SDValue InputFlag,const SmallVectorImpl<SDNode*> &F,
+                            bool isMorphNodeTo);
+    
 };
 
 }
diff --git a/include/llvm/CodeGen/SelectionDAGNodes.h b/include/llvm/CodeGen/SelectionDAGNodes.h
index df1f91b..950963e 100644
--- a/include/llvm/CodeGen/SelectionDAGNodes.h
+++ b/include/llvm/CodeGen/SelectionDAGNodes.h
@@ -1595,8 +1595,10 @@ public:
     return SubclassData;
   }
 
+  // We access subclass data here so that we can check consistency
+  // with MachineMemOperand information.
   bool isVolatile() const { return (SubclassData >> 5) & 1; }
-  bool isNonTemporal() const { return MMO->isNonTemporal(); }
+  bool isNonTemporal() const { return (SubclassData >> 6) & 1; }
 
   /// Returns the SrcValue and offset that describes the location of the access
   const Value *getSrcValue() const { return MMO->getValue(); }
@@ -1762,7 +1764,12 @@ public:
   bool isSplat() const { return isSplatMask(Mask, getValueType(0)); }
   int  getSplatIndex() const { 
     assert(isSplat() && "Cannot get splat index for non-splat!");
-    return Mask[0];
+    EVT VT = getValueType(0);
+    for (unsigned i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
+      if (Mask[i] != -1)
+        return Mask[i];
+    }
+    return -1;
   }
   static bool isSplatMask(const int *Mask, EVT VT);
 
@@ -1808,6 +1815,12 @@ public:
   const APFloat& getValueAPF() const { return Value->getValueAPF(); }
   const ConstantFP *getConstantFPValue() const { return Value; }
 
+  /// isZero - Return true if the value is positive or negative zero.
+  bool isZero() const { return Value->isZero(); }
+
+  /// isNaN - Return true if the value is a NaN.
+  bool isNaN() const { return Value->isNaN(); }
+
   /// isExactlyValue - We don't rely on operator== working on double values, as
   /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
   /// As such, this method can be used to do an exact bit-for-bit comparison of
diff --git a/include/llvm/CodeGen/TargetLoweringObjectFileImpl.h b/include/llvm/CodeGen/TargetLoweringObjectFileImpl.h
index c5aa626..3d99fa7 100644
--- a/include/llvm/CodeGen/TargetLoweringObjectFileImpl.h
+++ b/include/llvm/CodeGen/TargetLoweringObjectFileImpl.h
@@ -171,6 +171,11 @@ public:
   virtual const MCExpr *
   getSymbolForDwarfGlobalReference(const GlobalValue *GV, Mangler *Mang,
                               MachineModuleInfo *MMI, unsigned Encoding) const;
+
+  virtual unsigned getPersonalityEncoding() const;
+  virtual unsigned getLSDAEncoding() const;
+  virtual unsigned getFDEEncoding() const;
+  virtual unsigned getTTypeEncoding() const;
 };