1 files changed, 136 insertions, 105 deletions

diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp
index 3185c88..06cf053 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp
@@ -59,7 +59,11 @@ SUnit *ScheduleDAGSDNodes::NewSUnit(SDNode *N) {
   SUnits.back().OrigNode = &SUnits.back();
   SUnit *SU = &SUnits.back();
   const TargetLowering &TLI = DAG->getTargetLoweringInfo();
-  SU->SchedulingPref = TLI.getSchedulingPreference(N);
+  if (N->isMachineOpcode() &&
+      N->getMachineOpcode() == TargetOpcode::IMPLICIT_DEF)
+    SU->SchedulingPref = Sched::None;
+  else
+    SU->SchedulingPref = TLI.getSchedulingPreference(N);
   return SU;
 }
 
@@ -97,7 +101,7 @@ static void CheckForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op,
         II.ImplicitDefs[ResNo - II.getNumDefs()] == Reg) {
       PhysReg = Reg;
       const TargetRegisterClass *RC =
-        TRI->getPhysicalRegisterRegClass(Reg, Def->getValueType(ResNo));
+        TRI->getMinimalPhysRegClass(Reg, Def->getValueType(ResNo));
       Cost = RC->getCopyCost();
     }
   }
@@ -106,17 +110,42 @@ static void CheckForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op,
 static void AddFlags(SDNode *N, SDValue Flag, bool AddFlag,
                      SelectionDAG *DAG) {
   SmallVector<EVT, 4> VTs;
-  for (unsigned i = 0, e = N->getNumValues(); i != e; ++i)
-    VTs.push_back(N->getValueType(i));
+  SDNode *FlagDestNode = Flag.getNode();
+
+  // Don't add a flag from a node to itself.
+  if (FlagDestNode == N) return;
+
+  // Don't add a flag to something which already has a flag.
+  if (N->getValueType(N->getNumValues() - 1) == MVT::Flag) return;
+
+  for (unsigned I = 0, E = N->getNumValues(); I != E; ++I)
+    VTs.push_back(N->getValueType(I));
+
   if (AddFlag)
     VTs.push_back(MVT::Flag);
+
   SmallVector<SDValue, 4> Ops;
-  for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
-    Ops.push_back(N->getOperand(i));
-  if (Flag.getNode())
+  for (unsigned I = 0, E = N->getNumOperands(); I != E; ++I)
+    Ops.push_back(N->getOperand(I));
+
+  if (FlagDestNode)
     Ops.push_back(Flag);
+
   SDVTList VTList = DAG->getVTList(&VTs[0], VTs.size());
+  MachineSDNode::mmo_iterator Begin = 0, End = 0;
+  MachineSDNode *MN = dyn_cast<MachineSDNode>(N);
+
+  // Store memory references.
+  if (MN) {
+    Begin = MN->memoperands_begin();
+    End = MN->memoperands_end();
+  }
+
   DAG->MorphNodeTo(N, N->getOpcode(), VTList, &Ops[0], Ops.size());
+
+  // Reset the memory references
+  if (MN)
+    MN->setMemRefs(Begin, End);
 }
 
 /// ClusterNeighboringLoads - Force nearby loads together by "flagging" them.
@@ -124,98 +153,98 @@ static void AddFlags(SDNode *N, SDValue Flag, bool AddFlag,
 /// offsets are not far apart (target specific), it add MVT::Flag inputs and
 /// outputs to ensure they are scheduled together and in order. This
 /// optimization may benefit some targets by improving cache locality.
-void ScheduleDAGSDNodes::ClusterNeighboringLoads() {
+void ScheduleDAGSDNodes::ClusterNeighboringLoads(SDNode *Node) {
+  SDNode *Chain = 0;
+  unsigned NumOps = Node->getNumOperands();
+  if (Node->getOperand(NumOps-1).getValueType() == MVT::Other)
+    Chain = Node->getOperand(NumOps-1).getNode();
+  if (!Chain)
+    return;
+
+  // Look for other loads of the same chain. Find loads that are loading from
+  // the same base pointer and different offsets.
   SmallPtrSet<SDNode*, 16> Visited;
   SmallVector<int64_t, 4> Offsets;
   DenseMap<long long, SDNode*> O2SMap;  // Map from offset to SDNode.
-  for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(),
-       E = DAG->allnodes_end(); NI != E; ++NI) {
-    SDNode *Node = &*NI;
-    if (!Node || !Node->isMachineOpcode())
+  bool Cluster = false;
+  SDNode *Base = Node;
+  for (SDNode::use_iterator I = Chain->use_begin(), E = Chain->use_end();
+       I != E; ++I) {
+    SDNode *User = *I;
+    if (User == Node || !Visited.insert(User))
       continue;
-
-    unsigned Opc = Node->getMachineOpcode();
-    const TargetInstrDesc &TID = TII->get(Opc);
-    if (!TID.mayLoad())
+    int64_t Offset1, Offset2;
+    if (!TII->areLoadsFromSameBasePtr(Base, User, Offset1, Offset2) ||
+        Offset1 == Offset2)
+      // FIXME: Should be ok if they addresses are identical. But earlier
+      // optimizations really should have eliminated one of the loads.
       continue;
+    if (O2SMap.insert(std::make_pair(Offset1, Base)).second)
+      Offsets.push_back(Offset1);
+    O2SMap.insert(std::make_pair(Offset2, User));
+    Offsets.push_back(Offset2);
+    if (Offset2 < Offset1)
+      Base = User;
+    Cluster = true;
+  }
 
-    SDNode *Chain = 0;
-    unsigned NumOps = Node->getNumOperands();
-    if (Node->getOperand(NumOps-1).getValueType() == MVT::Other)
-      Chain = Node->getOperand(NumOps-1).getNode();
-    if (!Chain)
-      continue;
+  if (!Cluster)
+    return;
 
-    // Look for other loads of the same chain. Find loads that are loading from
-    // the same base pointer and different offsets.
-    Visited.clear();
-    Offsets.clear();
-    O2SMap.clear();
-    bool Cluster = false;
-    SDNode *Base = Node;
-    int64_t BaseOffset;
-    for (SDNode::use_iterator I = Chain->use_begin(), E = Chain->use_end();
-         I != E; ++I) {
-      SDNode *User = *I;
-      if (User == Node || !Visited.insert(User))
-        continue;
-      int64_t Offset1, Offset2;
-      if (!TII->areLoadsFromSameBasePtr(Base, User, Offset1, Offset2) ||
-          Offset1 == Offset2)
-        // FIXME: Should be ok if they addresses are identical. But earlier
-        // optimizations really should have eliminated one of the loads.
-        continue;
-      if (O2SMap.insert(std::make_pair(Offset1, Base)).second)
-        Offsets.push_back(Offset1);
-      O2SMap.insert(std::make_pair(Offset2, User));
-      Offsets.push_back(Offset2);
-      if (Offset2 < Offset1) {
-        Base = User;
-        BaseOffset = Offset2;
-      } else {
-        BaseOffset = Offset1;
-      }
-      Cluster = true;
-    }
+  // Sort them in increasing order.
+  std::sort(Offsets.begin(), Offsets.end());
+
+  // Check if the loads are close enough.
+  SmallVector<SDNode*, 4> Loads;
+  unsigned NumLoads = 0;
+  int64_t BaseOff = Offsets[0];
+  SDNode *BaseLoad = O2SMap[BaseOff];
+  Loads.push_back(BaseLoad);
+  for (unsigned i = 1, e = Offsets.size(); i != e; ++i) {
+    int64_t Offset = Offsets[i];
+    SDNode *Load = O2SMap[Offset];
+    if (!TII->shouldScheduleLoadsNear(BaseLoad, Load, BaseOff, Offset,NumLoads))
+      break; // Stop right here. Ignore loads that are further away.
+    Loads.push_back(Load);
+    ++NumLoads;
+  }
 
-    if (!Cluster)
-      continue;
+  if (NumLoads == 0)
+    return;
 
-    // Sort them in increasing order.
-    std::sort(Offsets.begin(), Offsets.end());
-
-    // Check if the loads are close enough.
-    SmallVector<SDNode*, 4> Loads;
-    unsigned NumLoads = 0;
-    int64_t BaseOff = Offsets[0];
-    SDNode *BaseLoad = O2SMap[BaseOff];
-    Loads.push_back(BaseLoad);
-    for (unsigned i = 1, e = Offsets.size(); i != e; ++i) {
-      int64_t Offset = Offsets[i];
-      SDNode *Load = O2SMap[Offset];
-      if (!TII->shouldScheduleLoadsNear(BaseLoad, Load, BaseOff, Offset,
-                                        NumLoads))
-        break; // Stop right here. Ignore loads that are further away.
-      Loads.push_back(Load);
-      ++NumLoads;
-    }
+  // Cluster loads by adding MVT::Flag outputs and inputs. This also
+  // ensure they are scheduled in order of increasing addresses.
+  SDNode *Lead = Loads[0];
+  AddFlags(Lead, SDValue(0, 0), true, DAG);
+
+  SDValue InFlag = SDValue(Lead, Lead->getNumValues() - 1);
+  for (unsigned I = 1, E = Loads.size(); I != E; ++I) {
+    bool OutFlag = I < E - 1;
+    SDNode *Load = Loads[I];
+
+    AddFlags(Load, InFlag, OutFlag, DAG);
+
+    if (OutFlag)
+      InFlag = SDValue(Load, Load->getNumValues() - 1);
+
+    ++LoadsClustered;
+  }
+}
 
-    if (NumLoads == 0)
+/// ClusterNodes - Cluster certain nodes which should be scheduled together.
+///
+void ScheduleDAGSDNodes::ClusterNodes() {
+  for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(),
+       E = DAG->allnodes_end(); NI != E; ++NI) {
+    SDNode *Node = &*NI;
+    if (!Node || !Node->isMachineOpcode())
       continue;
 
-    // Cluster loads by adding MVT::Flag outputs and inputs. This also
-    // ensure they are scheduled in order of increasing addresses.
-    SDNode *Lead = Loads[0];
-    AddFlags(Lead, SDValue(0,0), true, DAG);
-    SDValue InFlag = SDValue(Lead, Lead->getNumValues()-1);
-    for (unsigned i = 1, e = Loads.size(); i != e; ++i) {
-      bool OutFlag = i < e-1;
-      SDNode *Load = Loads[i];
-      AddFlags(Load, InFlag, OutFlag, DAG);
-      if (OutFlag)
-        InFlag = SDValue(Load, Load->getNumValues()-1);
-      ++LoadsClustered;
-    }
+    unsigned Opc = Node->getMachineOpcode();
+    const TargetInstrDesc &TID = TII->get(Opc);
+    if (TID.mayLoad())
+      // Cluster loads from "near" addresses into combined SUnits.
+      ClusterNeighboringLoads(Node);
   }
 }
 
@@ -364,8 +393,10 @@ void ScheduleDAGSDNodes::AddSchedEdges() {
         if (Cost >= 0)
           PhysReg = 0;
 
-        const SDep& dep = SDep(OpSU, isChain ? SDep::Order : SDep::Data,
-                               OpSU->Latency, PhysReg);
+        // If this is a ctrl dep, latency is 1.
+        unsigned OpLatency = isChain ? 1 : OpSU->Latency;
+        const SDep &dep = SDep(OpSU, isChain ? SDep::Order : SDep::Data,
+                               OpLatency, PhysReg);
         if (!isChain && !UnitLatencies) {
           ComputeOperandLatency(OpN, N, i, const_cast<SDep &>(dep));
           ST.adjustSchedDependency(OpSU, SU, const_cast<SDep &>(dep));
@@ -382,8 +413,8 @@ void ScheduleDAGSDNodes::AddSchedEdges() {
 /// excludes nodes that aren't interesting to scheduling, and represents
 /// flagged together nodes with a single SUnit.
 void ScheduleDAGSDNodes::BuildSchedGraph(AliasAnalysis *AA) {
-  // Cluster loads from "near" addresses into combined SUnits.
-  ClusterNeighboringLoads();
+  // Cluster certain nodes which should be scheduled together.
+  ClusterNodes();
   // Populate the SUnits array.
   BuildSchedUnits();
   // Compute all the scheduling dependencies between nodes.
@@ -427,15 +458,18 @@ void ScheduleDAGSDNodes::ComputeOperandLatency(SDNode *Def, SDNode *Use,
     return;
 
   unsigned DefIdx = Use->getOperand(OpIdx).getResNo();
-  if (Def->isMachineOpcode() && Use->isMachineOpcode()) {
+  if (Def->isMachineOpcode()) {
     const TargetInstrDesc &II = TII->get(Def->getMachineOpcode());
     if (DefIdx >= II.getNumDefs())
       return;
     int DefCycle = InstrItins.getOperandCycle(II.getSchedClass(), DefIdx);
     if (DefCycle < 0)
       return;
-    const unsigned UseClass = TII->get(Use->getMachineOpcode()).getSchedClass();
-    int UseCycle = InstrItins.getOperandCycle(UseClass, OpIdx);
+    int UseCycle = 1;
+    if (Use->isMachineOpcode()) {
+      const unsigned UseClass = TII->get(Use->getMachineOpcode()).getSchedClass();
+      UseCycle = InstrItins.getOperandCycle(UseClass, OpIdx);
+    }
     if (UseCycle >= 0) {
       int Latency = DefCycle - UseCycle + 1;
       if (Latency >= 0)
@@ -473,7 +507,7 @@ namespace {
 }
 
 // ProcessSourceNode - Process nodes with source order numbers. These are added
-// to a vector which EmitSchedule use to determine how to insert dbg_value
+// to a vector which EmitSchedule uses to determine how to insert dbg_value
 // instructions in the right order.
 static void ProcessSourceNode(SDNode *N, SelectionDAG *DAG,
                            InstrEmitter &Emitter,
@@ -485,13 +519,13 @@ static void ProcessSourceNode(SDNode *N, SelectionDAG *DAG,
     return;
 
   MachineBasicBlock *BB = Emitter.getBlock();
-  if (BB->empty() || BB->back().isPHI()) {
+  if (Emitter.getInsertPos() == BB->begin() || BB->back().isPHI()) {
     // Did not insert any instruction.
     Orders.push_back(std::make_pair(Order, (MachineInstr*)0));
     return;
   }
 
-  Orders.push_back(std::make_pair(Order, &BB->back()));
+  Orders.push_back(std::make_pair(Order, prior(Emitter.getInsertPos())));
   if (!N->getHasDebugValue())
     return;
   // Opportunistically insert immediate dbg_value uses, i.e. those with source
@@ -530,7 +564,7 @@ MachineBasicBlock *ScheduleDAGSDNodes::EmitSchedule() {
     for (; PDI != PDE; ++PDI) {
       MachineInstr *DbgMI= Emitter.EmitDbgValue(*PDI, VRBaseMap);
       if (DbgMI)
-        BB->insert(BB->end(), DbgMI);
+        BB->insert(InsertPos, DbgMI);
     }
   }
 
@@ -574,9 +608,7 @@ MachineBasicBlock *ScheduleDAGSDNodes::EmitSchedule() {
   // Insert all the dbg_values which have not already been inserted in source
   // order sequence.
   if (HasDbg) {
-    MachineBasicBlock::iterator BBBegin = BB->empty() ? BB->end() : BB->begin();
-    while (BBBegin != BB->end() && BBBegin->isPHI())
-      ++BBBegin;
+    MachineBasicBlock::iterator BBBegin = BB->getFirstNonPHI();
 
     // Sort the source order instructions and use the order to insert debug
     // values.
@@ -586,14 +618,12 @@ MachineBasicBlock *ScheduleDAGSDNodes::EmitSchedule() {
     SDDbgInfo::DbgIterator DE = DAG->DbgEnd();
     // Now emit the rest according to source order.
     unsigned LastOrder = 0;
-    MachineInstr *LastMI = 0;
     for (unsigned i = 0, e = Orders.size(); i != e && DI != DE; ++i) {
       unsigned Order = Orders[i].first;
       MachineInstr *MI = Orders[i].second;
       // Insert all SDDbgValue's whose order(s) are before "Order".
       if (!MI)
         continue;
-      MachineBasicBlock *MIBB = MI->getParent();
 #ifndef NDEBUG
       unsigned LastDIOrder = 0;
 #endif
@@ -612,13 +642,14 @@ MachineBasicBlock *ScheduleDAGSDNodes::EmitSchedule() {
             // Insert to start of the BB (after PHIs).
             BB->insert(BBBegin, DbgMI);
           else {
+            // Insert at the instruction, which may be in a different
+            // block, if the block was split by a custom inserter.
             MachineBasicBlock::iterator Pos = MI;
-            MIBB->insert(llvm::next(Pos), DbgMI);
+            MI->getParent()->insert(llvm::next(Pos), DbgMI);
           }
         }
       }
       LastOrder = Order;
-      LastMI = MI;
     }
     // Add trailing DbgValue's before the terminator. FIXME: May want to add
     // some of them before one or more conditional branches?