← Back to branch summary

~ubuntu-branches/ubuntu/trusty/llvm-toolchain-snapshot/trusty-201310232150

« back to all changes in this revision

Viewing changes to lib/CodeGen/MachineScheduler.cpp

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2013-05-27 15:01:57 UTC
  • mfrom: (0.10.1) (0.9.1) (0.8.1) (0.7.1) (0.6.1) (0.5.2)
  • Revision ID: package-import@ubuntu.com-20130527150157-tdkrsjpuvht7v0qx
Tags: 1:3.4~svn182733-1~exp1
http://bugs.debian.org/708677
* New snapshot release (3.4 release)
* Add a symlink of libLLVM-3.4.so.1 to usr/lib/llvm-3.4/lib/libLLVM-3.4.so
    to fix make the llvm-config-3.4 --libdir work (Closes: #708677)
  * Various packages rename to allow co installations:
    * libclang1 => libclang1-3.4
    * libclang1-dbg => libclang1-3.4-dbg
    * libclang-dev => libclang-3.4-dev
    * libclang-common-dev => libclang-common-3.4-dev

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/CodeGen/MachineScheduler.cpp
51
51
static bool ViewMISchedDAGs = false;
52
52
#endif // NDEBUG
53
53
 
54
 
// Experimental heuristics
 
54
// FIXME: remove this flag after initial testing. It should always be a good
 
55
// thing.
 
56
static cl::opt<bool> EnableCopyConstrain("misched-vcopy", cl::Hidden,
 
57
    cl::desc("Constrain vreg copies."), cl::init(true));
 
58
 
55
59
static cl::opt<bool> EnableLoadCluster("misched-cluster", cl::Hidden,
56
60
  cl::desc("Enable load clustering."), cl::init(true));
57
61
 
323
327
  delete SchedImpl;
324
328
}
325
329
 
 
330
bool ScheduleDAGMI::canAddEdge(SUnit *SuccSU, SUnit *PredSU) {
 
331
  return SuccSU == &ExitSU || !Topo.IsReachable(PredSU, SuccSU);
 
332
}
 
333
 
326
334
bool ScheduleDAGMI::addEdge(SUnit *SuccSU, const SDep &PredDep) {
327
335
  if (SuccSU != &ExitSU) {
328
336
    // Do not use WillCreateCycle, it assumes SD scheduling.
507
515
    if ((int)NewMaxPressure[ID] > MaxUnits)
508
516
      MaxUnits = NewMaxPressure[ID];
509
517
  }
 
518
  DEBUG(
 
519
    for (unsigned i = 0, e = NewMaxPressure.size(); i < e; ++i) {
 
520
      unsigned Limit = TRI->getRegPressureSetLimit(i);
 
521
      if (NewMaxPressure[i] > Limit ) {
 
522
        dbgs() << "  " << TRI->getRegPressureSetName(i) << ": "
 
523
               << NewMaxPressure[i] << " > " << Limit << "\n";
 
524
      }
 
525
    });
510
526
}
511
527
 
512
528
/// schedule - Called back from MachineScheduler::runOnMachineFunction
907
923
}
908
924
 
909
925
//===----------------------------------------------------------------------===//
 
926
// CopyConstrain - DAG post-processing to encourage copy elimination.
 
927
//===----------------------------------------------------------------------===//
 
928
 
 
929
namespace {
 
930
/// \brief Post-process the DAG to create weak edges from all uses of a copy to
 
931
/// the one use that defines the copy's source vreg, most likely an induction
 
932
/// variable increment.
 
933
class CopyConstrain : public ScheduleDAGMutation {
 
934
  // Transient state.
 
935
  SlotIndex RegionBeginIdx;
 
936
  // RegionEndIdx is the slot index of the last non-debug instruction in the
 
937
  // scheduling region. So we may have RegionBeginIdx == RegionEndIdx.
 
938
  SlotIndex RegionEndIdx;
 
939
public:
 
940
  CopyConstrain(const TargetInstrInfo *, const TargetRegisterInfo *) {}
 
941
 
 
942
  virtual void apply(ScheduleDAGMI *DAG);
 
943
 
 
944
protected:
 
945
  void constrainLocalCopy(SUnit *CopySU, ScheduleDAGMI *DAG);
 
946
};
 
947
} // anonymous
 
948
 
 
949
/// constrainLocalCopy handles two possibilities:
 
950
/// 1) Local src:
 
951
/// I0:     = dst
 
952
/// I1: src = ...
 
953
/// I2:     = dst
 
954
/// I3: dst = src (copy)
 
955
/// (create pred->succ edges I0->I1, I2->I1)
 
956
///
 
957
/// 2) Local copy:
 
958
/// I0: dst = src (copy)
 
959
/// I1:     = dst
 
960
/// I2: src = ...
 
961
/// I3:     = dst
 
962
/// (create pred->succ edges I1->I2, I3->I2)
 
963
///
 
964
/// Although the MachineScheduler is currently constrained to single blocks,
 
965
/// this algorithm should handle extended blocks. An EBB is a set of
 
966
/// contiguously numbered blocks such that the previous block in the EBB is
 
967
/// always the single predecessor.
 
968
void CopyConstrain::constrainLocalCopy(SUnit *CopySU, ScheduleDAGMI *DAG) {
 
969
  LiveIntervals *LIS = DAG->getLIS();
 
970
  MachineInstr *Copy = CopySU->getInstr();
 
971
 
 
972
  // Check for pure vreg copies.
 
973
  unsigned SrcReg = Copy->getOperand(1).getReg();
 
974
  if (!TargetRegisterInfo::isVirtualRegister(SrcReg))
 
975
    return;
 
976
 
 
977
  unsigned DstReg = Copy->getOperand(0).getReg();
 
978
  if (!TargetRegisterInfo::isVirtualRegister(DstReg))
 
979
    return;
 
980
 
 
981
  // Check if either the dest or source is local. If it's live across a back
 
982
  // edge, it's not local. Note that if both vregs are live across the back
 
983
  // edge, we cannot successfully contrain the copy without cyclic scheduling.
 
984
  unsigned LocalReg = DstReg;
 
985
  unsigned GlobalReg = SrcReg;
 
986
  LiveInterval *LocalLI = &LIS->getInterval(LocalReg);
 
987
  if (!LocalLI->isLocal(RegionBeginIdx, RegionEndIdx)) {
 
988
    LocalReg = SrcReg;
 
989
    GlobalReg = DstReg;
 
990
    LocalLI = &LIS->getInterval(LocalReg);
 
991
    if (!LocalLI->isLocal(RegionBeginIdx, RegionEndIdx))
 
992
      return;
 
993
  }
 
994
  LiveInterval *GlobalLI = &LIS->getInterval(GlobalReg);
 
995
 
 
996
  // Find the global segment after the start of the local LI.
 
997
  LiveInterval::iterator GlobalSegment = GlobalLI->find(LocalLI->beginIndex());
 
998
  // If GlobalLI does not overlap LocalLI->start, then a copy directly feeds a
 
999
  // local live range. We could create edges from other global uses to the local
 
1000
  // start, but the coalescer should have already eliminated these cases, so
 
1001
  // don't bother dealing with it.
 
1002
  if (GlobalSegment == GlobalLI->end())
 
1003
    return;
 
1004
 
 
1005
  // If GlobalSegment is killed at the LocalLI->start, the call to find()
 
1006
  // returned the next global segment. But if GlobalSegment overlaps with
 
1007
  // LocalLI->start, then advance to the next segement. If a hole in GlobalLI
 
1008
  // exists in LocalLI's vicinity, GlobalSegment will be the end of the hole.
 
1009
  if (GlobalSegment->contains(LocalLI->beginIndex()))
 
1010
    ++GlobalSegment;
 
1011
 
 
1012
  if (GlobalSegment == GlobalLI->end())
 
1013
    return;
 
1014
 
 
1015
  // Check if GlobalLI contains a hole in the vicinity of LocalLI.
 
1016
  if (GlobalSegment != GlobalLI->begin()) {
 
1017
    // Two address defs have no hole.
 
1018
    if (SlotIndex::isSameInstr(llvm::prior(GlobalSegment)->end,
 
1019
                               GlobalSegment->start)) {
 
1020
      return;
 
1021
    }
 
1022
    // If GlobalLI has a prior segment, it must be live into the EBB. Otherwise
 
1023
    // it would be a disconnected component in the live range.
 
1024
    assert(llvm::prior(GlobalSegment)->start < LocalLI->beginIndex() &&
 
1025
           "Disconnected LRG within the scheduling region.");
 
1026
  }
 
1027
  MachineInstr *GlobalDef = LIS->getInstructionFromIndex(GlobalSegment->start);
 
1028
  if (!GlobalDef)
 
1029
    return;
 
1030
 
 
1031
  SUnit *GlobalSU = DAG->getSUnit(GlobalDef);
 
1032
  if (!GlobalSU)
 
1033
    return;
 
1034
 
 
1035
  // GlobalDef is the bottom of the GlobalLI hole. Open the hole by
 
1036
  // constraining the uses of the last local def to precede GlobalDef.
 
1037
  SmallVector<SUnit*,8> LocalUses;
 
1038
  const VNInfo *LastLocalVN = LocalLI->getVNInfoBefore(LocalLI->endIndex());
 
1039
  MachineInstr *LastLocalDef = LIS->getInstructionFromIndex(LastLocalVN->def);
 
1040
  SUnit *LastLocalSU = DAG->getSUnit(LastLocalDef);
 
1041
  for (SUnit::const_succ_iterator
 
1042
         I = LastLocalSU->Succs.begin(), E = LastLocalSU->Succs.end();
 
1043
       I != E; ++I) {
 
1044
    if (I->getKind() != SDep::Data || I->getReg() != LocalReg)
 
1045
      continue;
 
1046
    if (I->getSUnit() == GlobalSU)
 
1047
      continue;
 
1048
    if (!DAG->canAddEdge(GlobalSU, I->getSUnit()))
 
1049
      return;
 
1050
    LocalUses.push_back(I->getSUnit());
 
1051
  }
 
1052
  // Open the top of the GlobalLI hole by constraining any earlier global uses
 
1053
  // to precede the start of LocalLI.
 
1054
  SmallVector<SUnit*,8> GlobalUses;
 
1055
  MachineInstr *FirstLocalDef =
 
1056
    LIS->getInstructionFromIndex(LocalLI->beginIndex());
 
1057
  SUnit *FirstLocalSU = DAG->getSUnit(FirstLocalDef);
 
1058
  for (SUnit::const_pred_iterator
 
1059
         I = GlobalSU->Preds.begin(), E = GlobalSU->Preds.end(); I != E; ++I) {
 
1060
    if (I->getKind() != SDep::Anti || I->getReg() != GlobalReg)
 
1061
      continue;
 
1062
    if (I->getSUnit() == FirstLocalSU)
 
1063
      continue;
 
1064
    if (!DAG->canAddEdge(FirstLocalSU, I->getSUnit()))
 
1065
      return;
 
1066
    GlobalUses.push_back(I->getSUnit());
 
1067
  }
 
1068
  DEBUG(dbgs() << "Constraining copy SU(" << CopySU->NodeNum << ")\n");
 
1069
  // Add the weak edges.
 
1070
  for (SmallVectorImpl<SUnit*>::const_iterator
 
1071
         I = LocalUses.begin(), E = LocalUses.end(); I != E; ++I) {
 
1072
    DEBUG(dbgs() << "  Local use SU(" << (*I)->NodeNum << ") -> SU("
 
1073
          << GlobalSU->NodeNum << ")\n");
 
1074
    DAG->addEdge(GlobalSU, SDep(*I, SDep::Weak));
 
1075
  }
 
1076
  for (SmallVectorImpl<SUnit*>::const_iterator
 
1077
         I = GlobalUses.begin(), E = GlobalUses.end(); I != E; ++I) {
 
1078
    DEBUG(dbgs() << "  Global use SU(" << (*I)->NodeNum << ") -> SU("
 
1079
          << FirstLocalSU->NodeNum << ")\n");
 
1080
    DAG->addEdge(FirstLocalSU, SDep(*I, SDep::Weak));
 
1081
  }
 
1082
}
 
1083
 
 
1084
/// \brief Callback from DAG postProcessing to create weak edges to encourage
 
1085
/// copy elimination.
 
1086
void CopyConstrain::apply(ScheduleDAGMI *DAG) {
 
1087
  MachineBasicBlock::iterator FirstPos = nextIfDebug(DAG->begin(), DAG->end());
 
1088
  if (FirstPos == DAG->end())
 
1089
    return;
 
1090
  RegionBeginIdx = DAG->getLIS()->getInstructionIndex(&*FirstPos);
 
1091
  RegionEndIdx = DAG->getLIS()->getInstructionIndex(
 
1092
    &*priorNonDebug(DAG->end(), DAG->begin()));
 
1093
 
 
1094
  for (unsigned Idx = 0, End = DAG->SUnits.size(); Idx != End; ++Idx) {
 
1095
    SUnit *SU = &DAG->SUnits[Idx];
 
1096
    if (!SU->getInstr()->isCopy())
 
1097
      continue;
 
1098
 
 
1099
    constrainLocalCopy(SU, DAG);
 
1100
  }
 
1101
}
 
1102
 
 
1103
//===----------------------------------------------------------------------===//
910
1104
// ConvergingScheduler - Implementation of the standard MachineSchedStrategy.
911
1105
//===----------------------------------------------------------------------===//
912
1106
 
918
1112
  /// Represent the type of SchedCandidate found within a single queue.
919
1113
  /// pickNodeBidirectional depends on these listed by decreasing priority.
920
1114
  enum CandReason {
921
 
    NoCand, PhysRegCopy, SingleExcess, SingleCritical, Cluster,
 
1115
    NoCand, PhysRegCopy, SingleExcess, SingleCritical, Cluster, Weak,
922
1116
    ResourceReduce, ResourceDemand, BotHeightReduce, BotPathReduce,
923
1117
    TopDepthReduce, TopPathReduce, SingleMax, MultiPressure, NextDefUse,
924
1118
    NodeOrder};
1794
1988
  if (tryGreater(TryCand.SU == NextClusterSU, Cand.SU == NextClusterSU,
1795
1989
                 TryCand, Cand, Cluster))
1796
1990
    return;
1797
 
  // Currently, weak edges are for clustering, so we hard-code that reason.
1798
 
  // However, deferring the current TryCand will not change Cand's reason.
 
1991
 
 
1992
  // Weak edges are for clustering and other constraints.
 
1993
  //
 
1994
  // Deferring TryCand here does not change Cand's reason. This is good in the
 
1995
  // sense that a bad candidate shouldn't affect a previous candidate's
 
1996
  // goodness, but bad in that it is assymetric and depends on queue order.
1799
1997
  CandReason OrigReason = Cand.Reason;
1800
1998
  if (tryLess(getWeakLeft(TryCand.SU, Zone.isTop()),
1801
1999
              getWeakLeft(Cand.SU, Zone.isTop()),
1802
 
              TryCand, Cand, Cluster)) {
 
2000
              TryCand, Cand, Weak)) {
1803
2001
    Cand.Reason = OrigReason;
1804
2002
    return;
1805
2003
  }
1900
2098
  case SingleExcess:   return "REG-EXCESS";
1901
2099
  case SingleCritical: return "REG-CRIT  ";
1902
2100
  case Cluster:        return "CLUSTER   ";
 
2101
  case Weak:           return "WEAK      ";
1903
2102
  case SingleMax:      return "REG-MAX   ";
1904
2103
  case MultiPressure:  return "REG-MULTI ";
1905
2104
  case ResourceReduce: return "RES-REDUCE";
2169
2368
         "-misched-topdown incompatible with -misched-bottomup");
2170
2369
  ScheduleDAGMI *DAG = new ScheduleDAGMI(C, new ConvergingScheduler());
2171
2370
  // Register DAG post-processors.
 
2371
  //
 
2372
  // FIXME: extend the mutation API to allow earlier mutations to instantiate
 
2373
  // data and pass it to later mutations. Have a single mutation that gathers
 
2374
  // the interesting nodes in one pass.
 
2375
  if (EnableCopyConstrain)
 
2376
    DAG->addMutation(new CopyConstrain(DAG->TII, DAG->TRI));
2172
2377
  if (EnableLoadCluster)
2173
2378
    DAG->addMutation(new LoadClusterMutation(DAG->TII, DAG->TRI));
2174
2379
  if (EnableMacroFusion)