[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp ScheduleDAGRRList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.71 -> 1.72
ScheduleDAGRRList.cpp updated: 1.26 -> 1.27
---
Log message:
switch the sched unit map over to use a DenseMap instead of std::map. This
speeds up isel as a whole time by 2.6%.
---
Diffs of the changes: (+6 -6)
ScheduleDAGList.cpp |2 +-
ScheduleDAGRRList.cpp | 10 +-
2 files changed, 6 insertions(+), 6 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.71
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.72
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.71 Tue Dec 19
16:41:21 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Fri Feb 2 19:34:13 2007
@@ -328,7 +328,7 @@
LatencyPriorityQueue() : Queue(latency_sort(this)) {
}
-void initNodes(std::map &sumap,
+void initNodes(DenseMap &sumap,
std::vector &sunits) {
SUnits = &sunits;
// Calculate node priorities.
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp:1.26
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp:1.27
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp:1.26Wed Jan 31
22:55:59 2007
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp Fri Feb 2 19:34:13 2007
@@ -430,7 +430,7 @@
RegReductionPriorityQueue() :
Queue(SF(this)) {}
-virtual void initNodes(std::map &sumap,
+virtual void initNodes(DenseMap &sumap,
std::vector &sunits) {}
virtual void releaseState() {}
@@ -464,7 +464,7 @@
class VISIBILITY_HIDDEN BURegReductionPriorityQueue
: public RegReductionPriorityQueue {
// SUnitMap SDNode to SUnit mapping (n -> 1).
-std::map *SUnitMap;
+DenseMap *SUnitMap;
// SUnits - The SUnits for the current graph.
const std::vector *SUnits;
@@ -477,7 +477,7 @@
BURegReductionPriorityQueue(const TargetInstrInfo *tii)
: TII(tii) {}
-void initNodes(std::map &sumap,
+void initNodes(DenseMap &sumap,
std::vector &sunits) {
SUnitMap = &sumap;
SUnits = &sunits;
@@ -541,7 +541,7 @@
template
class TDRegReductionPriorityQueue : public RegReductionPriorityQueue {
// SUnitMap SDNode to SUnit mapping (n -> 1).
-std::map *SUnitMap;
+DenseMap *SUnitMap;
// SUnits - The SUnits for the current graph.
const std::vector *SUnits;
@@ -552,7 +552,7 @@
public:
TDRegReductionPriorityQueue() {}
-void initNodes(std::map &sumap,
+void initNodes(DenseMap &sumap,
std::vector &sunits) {
SUnitMap = &sumap;
SUnits = &sunits;
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp ScheduleDAGRRList.cpp ScheduleDAGSimple.cpp SelectionDAGISel.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.64 -> 1.65
ScheduleDAGRRList.cpp updated: 1.11 -> 1.12
ScheduleDAGSimple.cpp updated: 1.15 -> 1.16
SelectionDAGISel.cpp updated: 1.265 -> 1.266
---
Log message:
Final polish on machine pass registries.
---
Diffs of the changes: (+22 -11)
ScheduleDAGList.cpp |2 +-
ScheduleDAGRRList.cpp |2 +-
ScheduleDAGSimple.cpp |2 +-
SelectionDAGISel.cpp | 27 +++
4 files changed, 22 insertions(+), 11 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.64
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.65
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.64 Tue Aug 1
13:29:48 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Wed Aug 2 07:30:23 2006
@@ -19,8 +19,8 @@
//===--===//
#define DEBUG_TYPE "sched"
-#include "llvm/CodeGen/MachinePassRegistry.h"
#include "llvm/CodeGen/ScheduleDAG.h"
+#include "llvm/CodeGen/SchedulerRegistry.h"
#include "llvm/CodeGen/SelectionDAGISel.h"
#include "llvm/CodeGen/SSARegMap.h"
#include "llvm/Target/MRegisterInfo.h"
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp:1.11
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp:1.12
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp:1.11Tue Aug 1
13:29:48 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp Wed Aug 2 07:30:23 2006
@@ -16,8 +16,8 @@
//===--===//
#define DEBUG_TYPE "sched"
-#include "llvm/CodeGen/MachinePassRegistry.h"
#include "llvm/CodeGen/ScheduleDAG.h"
+#include "llvm/CodeGen/SchedulerRegistry.h"
#include "llvm/CodeGen/SSARegMap.h"
#include "llvm/Target/MRegisterInfo.h"
#include "llvm/Target/TargetData.h"
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGSimple.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGSimple.cpp:1.15
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGSimple.cpp:1.16
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGSimple.cpp:1.15Tue Aug 1
13:29:48 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGSimple.cpp Wed Aug 2 07:30:23 2006
@@ -14,8 +14,8 @@
//===--===//
#define DEBUG_TYPE "sched"
-#include "llvm/CodeGen/MachinePassRegistry.h"
#include "llvm/CodeGen/ScheduleDAG.h"
+#include "llvm/CodeGen/SchedulerRegistry.h"
#include "llvm/CodeGen/SelectionDAG.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Target/TargetMachine.h"
Index: llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:1.265
llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:1.266
--- llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:1.265Tue Aug 1
14:14:14 2006
+++ llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp Wed Aug 2 07:30:23 2006
@@ -29,7 +29,7 @@
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineJumpTableInfo.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
-#include "llvm/CodeGen/MachinePassRegistry.h"
+#include "llvm/CodeGen/SchedulerRegistry.h"
#include "llvm/CodeGen/SelectionDAG.h"
#include "llvm/CodeGen/SSARegMap.h"
#include "llvm/Target/MRegisterInfo.h"
@@ -40,7 +40,6 @@
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetOptions.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
-#include "llvm/Support/CommandLine.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/Visibility.h"
@@ -61,10 +60,24 @@
static const bool ViewISelDAGs = 0, ViewSchedDAGs = 0;
#endif
+
+//===-===//
+///
+/// RegisterScheduler class - Track the registration of instruction schedulers.
+///
+//===-===//
+MachinePassRegistry RegisterScheduler::Registry;
+
+//===-===//
+///
+/// ISHeuristic command line option for instruction schedulers.
+///
+//===-===//
namespace {
- cl::opt >
+ cl::opt >
ISHeuristic("sched",
- cl::init("default"),
+ cl::init(createDefaultScheduler),
cl::desc("Instruction schedulers available:"));
static RegisterScheduler
@@ -3629,15 +3642,13 @@
void SelectionDAGISel::ScheduleAndEmitDAG(SelectionDAG &DAG) {
if (ViewSchedDAGs) DAG.viewGraph();
- static RegisterScheduler::FunctionPassCtor Ctor =
-
RegisterScheduler::getDefault();
+ RegisterScheduler::FunctionPassCtor Ctor = RegisterScheduler::getDefault();
if (!Ctor) {
-Ctor =
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp ScheduleDAGRRList.cpp ScheduleDAGSimple.cpp SelectionDAGISel.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.63 -> 1.64
ScheduleDAGRRList.cpp updated: 1.10 -> 1.11
ScheduleDAGSimple.cpp updated: 1.14 -> 1.15
SelectionDAGISel.cpp updated: 1.263 -> 1.264
---
Log message:
1. Change use of "Cache" to "Default".
2. Added argument to instruction scheduler creators so the creators can do
special things.
3. Repaired target hazard code.
4. Misc.
More to follow.
---
Diffs of the changes: (+23 -11)
ScheduleDAGList.cpp |6 --
ScheduleDAGRRList.cpp |6 --
ScheduleDAGSimple.cpp |9 ++---
SelectionDAGISel.cpp | 13 +
4 files changed, 23 insertions(+), 11 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.63
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.64
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.63 Tue Aug 1
09:21:23 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Tue Aug 1 13:29:48 2006
@@ -21,6 +21,7 @@
#define DEBUG_TYPE "sched"
#include "llvm/CodeGen/MachinePassRegistry.h"
#include "llvm/CodeGen/ScheduleDAG.h"
+#include "llvm/CodeGen/SelectionDAGISel.h"
#include "llvm/CodeGen/SSARegMap.h"
#include "llvm/Target/MRegisterInfo.h"
#include "llvm/Target/TargetData.h"
@@ -519,9 +520,10 @@
/// createTDListDAGScheduler - This creates a top-down list scheduler with a
/// new hazard recognizer. This scheduler takes ownership of the hazard
/// recognizer and deletes it when done.
-ScheduleDAG* llvm::createTDListDAGScheduler(SelectionDAG *DAG,
+ScheduleDAG* llvm::createTDListDAGScheduler(SelectionDAGISel *IS,
+SelectionDAG *DAG,
MachineBasicBlock *BB) {
return new ScheduleDAGList(*DAG, BB, DAG->getTarget(),
new LatencyPriorityQueue(),
- new HazardRecognizer());
+ IS->CreateTargetHazardRecognizer());
}
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp:1.10
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp:1.11
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp:1.10Tue Aug 1
09:21:23 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp Tue Aug 1 13:29:48 2006
@@ -886,13 +886,15 @@
// Public Constructor Functions
//===--===//
-llvm::ScheduleDAG* llvm::createBURRListDAGScheduler(SelectionDAG *DAG,
+llvm::ScheduleDAG* llvm::createBURRListDAGScheduler(SelectionDAGISel *IS,
+SelectionDAG *DAG,
MachineBasicBlock *BB) {
return new ScheduleDAGRRList(*DAG, BB, DAG->getTarget(), true,
new
BURegReductionPriorityQueue());
}
-llvm::ScheduleDAG* llvm::createTDRRListDAGScheduler(SelectionDAG *DAG,
+llvm::ScheduleDAG* llvm::createTDRRListDAGScheduler(SelectionDAGISel *IS,
+SelectionDAG *DAG,
MachineBasicBlock *BB) {
return new ScheduleDAGRRList(*DAG, BB, DAG->getTarget(), false,
new
TDRegReductionPriorityQueue());
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGSimple.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGSimple.cpp:1.14
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGSimple.cpp:1.15
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGSimple.cpp:1.14Tue Aug 1
09:21:23 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGSimple.cpp Tue Aug 1 13:29:48 2006
@@ -1120,21 +1120,24 @@
/// createSimpleDAGScheduler - This creates a simple two pass instruction
/// scheduler using instruction itinerary.
-llvm::ScheduleDAG* llvm::createSimpleDAGScheduler(SelectionDAG *DAG,
+llvm::ScheduleDAG* llvm::createSimpleDAGScheduler(SelectionDAGISel *IS,
+ SelectionDAG *DAG,
MachineBasicBlock *BB) {
return new ScheduleDAGSimple(false, false, *DAG, BB, DAG->getTarget());
}
/// createNoItinsDAGScheduler - This creates a simple two pass instruction
/// scheduler without using instruction itinerary.
-llvm::ScheduleDAG* llvm::createNoItinsDAGScheduler(SelectionDAG *DAG,
+llvm::ScheduleDAG* llvm::createNoItinsDAGScheduler(SelectionDAGISel *IS,
+ SelectionDAG *DAG,
MachineBasicBlock *BB) {
return new ScheduleDAGSimple(false, true, *DAG, BB, DAG->getTarget());
}
/// createBFS_DAGScheduler - This creates a simple breadth first instruction
/// scheduler.
-llvm::ScheduleDAG* llvm::createBFS_DAGScheduler(SelectionDAG *DAG,
+llvm::ScheduleDAG* llvm::createBF
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp ScheduleDAGRRList.cpp ScheduleDAGSimple.cpp SelectionDAGISel.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.62 -> 1.63
ScheduleDAGRRList.cpp updated: 1.9 -> 1.10
ScheduleDAGSimple.cpp updated: 1.13 -> 1.14
SelectionDAGISel.cpp updated: 1.262 -> 1.263
---
Log message:
Introducing plugable register allocators and instruction schedulers.
---
Diffs of the changes: (+87 -82)
ScheduleDAGList.cpp | 19 ++
ScheduleDAGRRList.cpp | 18 +++--
ScheduleDAGSimple.cpp | 37 ---
SelectionDAGISel.cpp | 95 +++---
4 files changed, 87 insertions(+), 82 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.62
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.63
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.62 Thu Jul 20
12:28:38 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Tue Aug 1 09:21:23 2006
@@ -19,6 +19,7 @@
//===--===//
#define DEBUG_TYPE "sched"
+#include "llvm/CodeGen/MachinePassRegistry.h"
#include "llvm/CodeGen/ScheduleDAG.h"
#include "llvm/CodeGen/SSARegMap.h"
#include "llvm/Target/MRegisterInfo.h"
@@ -38,6 +39,10 @@
static Statistic<> NumStalls("scheduler", "Number of pipeline stalls");
}
+static RegisterScheduler
+ tdListDAGScheduler("list-td", " Top-down list scheduler",
+ createTDListDAGScheduler);
+
namespace {
//===--===//
/// ScheduleDAGList - The actual list scheduler implementation. This supports
@@ -511,12 +516,12 @@
// Public Constructor Functions
//===--===//
-/// createTDListDAGScheduler - This creates a top-down list scheduler with the
-/// specified hazard recognizer.
-ScheduleDAG* llvm::createTDListDAGScheduler(SelectionDAG &DAG,
-MachineBasicBlock *BB,
-HazardRecognizer *HR) {
- return new ScheduleDAGList(DAG, BB, DAG.getTarget(),
+/// createTDListDAGScheduler - This creates a top-down list scheduler with a
+/// new hazard recognizer. This scheduler takes ownership of the hazard
+/// recognizer and deletes it when done.
+ScheduleDAG* llvm::createTDListDAGScheduler(SelectionDAG *DAG,
+MachineBasicBlock *BB) {
+ return new ScheduleDAGList(*DAG, BB, DAG->getTarget(),
new LatencyPriorityQueue(),
- HR);
+ new HazardRecognizer());
}
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp:1.9
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp:1.10
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp:1.9 Fri Jul 21
15:57:35 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp Tue Aug 1 09:21:23 2006
@@ -16,6 +16,7 @@
//===--===//
#define DEBUG_TYPE "sched"
+#include "llvm/CodeGen/MachinePassRegistry.h"
#include "llvm/CodeGen/ScheduleDAG.h"
#include "llvm/CodeGen/SSARegMap.h"
#include "llvm/Target/MRegisterInfo.h"
@@ -31,6 +32,15 @@
#include "llvm/Support/CommandLine.h"
using namespace llvm;
+static RegisterScheduler
+ burrListDAGScheduler("list-burr",
+ " Bottom-up register reduction list scheduling",
+ createBURRListDAGScheduler);
+static RegisterScheduler
+ tdrListrDAGScheduler("list-tdrr",
+ " Top-down register reduction list scheduling",
+ createTDRRListDAGScheduler);
+
namespace {
//===--===//
/// ScheduleDAGRRList - The actual register reduction list scheduler
@@ -876,15 +886,15 @@
// Public Constructor Functions
//===--===//
-llvm::ScheduleDAG* llvm::createBURRListDAGScheduler(SelectionDAG &DAG,
+llvm::ScheduleDAG* llvm::createBURRListDAGScheduler(SelectionDAG *DAG,
MachineBasicBlock *BB) {
- return new ScheduleDAGRRList(DAG, BB, DAG.getTarget(), true,
+ return new ScheduleDAGRRList(*DAG, BB, DAG->getTarget(), true,
new
BURegReductionPriorityQueue());
}
-llvm::ScheduleDAG* llvm::createTDRRListDAGScheduler(SelectionDAG &DAG,
+llvm::ScheduleDAG* llvm::createTDRRListDAGScheduler(SelectionDAG *DAG,
MachineBasicBlock *BB) {
- return new ScheduleDAGRRList(DAG, BB, DAG.getTarget(), false,
+ return new ScheduleDAGRRList(*DAG, BB, DAG->getTarget(), false,
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp ScheduleDAGRRList.cpp ScheduleDAGSimple.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.60 -> 1.61
ScheduleDAGRRList.cpp updated: 1.6 -> 1.7
ScheduleDAGSimple.cpp updated: 1.12 -> 1.13
---
Log message:
Shave another 27K off libllvmgcc.dylib with visibility hidden
---
Diffs of the changes: (+6 -3)
ScheduleDAGList.cpp |3 ++-
ScheduleDAGRRList.cpp |3 ++-
ScheduleDAGSimple.cpp |3 ++-
3 files changed, 6 insertions(+), 3 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.60
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.61
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.60 Tue May 30
13:04:34 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Wed Jun 28 17:17:39 2006
@@ -26,6 +26,7 @@
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Support/Debug.h"
+#include "llvm/Support/Visibility.h"
#include "llvm/ADT/Statistic.h"
#include
#include
@@ -42,7 +43,7 @@
/// ScheduleDAGList - The actual list scheduler implementation. This supports
/// top-down scheduling.
///
-class ScheduleDAGList : public ScheduleDAG {
+class VISIBILITY_HIDDEN ScheduleDAGList : public ScheduleDAG {
private:
/// AvailableQueue - The priority queue to use for the available SUnits.
///
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp:1.6
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp:1.7
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp:1.6 Tue May 30
13:05:39 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp Wed Jun 28 17:17:39 2006
@@ -23,6 +23,7 @@
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Support/Debug.h"
+#include "llvm/Support/Visibility.h"
#include "llvm/ADT/Statistic.h"
#include
#include
@@ -36,7 +37,7 @@
/// implementation. This supports both top-down and bottom-up scheduling.
///
-class ScheduleDAGRRList : public ScheduleDAG {
+class VISIBILITY_HIDDEN ScheduleDAGRRList : public ScheduleDAG {
private:
/// isBottomUp - This is true if the scheduling problem is bottom-up, false
if
/// it is top-down.
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGSimple.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGSimple.cpp:1.12
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGSimple.cpp:1.13
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGSimple.cpp:1.12Fri May 12
01:33:48 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGSimple.cpp Wed Jun 28 17:17:39 2006
@@ -20,6 +20,7 @@
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Support/Debug.h"
+#include "llvm/Support/Visibility.h"
#include
#include
using namespace llvm;
@@ -389,7 +390,7 @@
///
/// ScheduleDAGSimple - Simple two pass scheduler.
///
-class ScheduleDAGSimple : public ScheduleDAG {
+class VISIBILITY_HIDDEN ScheduleDAGSimple : public ScheduleDAG {
private:
bool NoSched; // Just do a BFS schedule, nothing
fancy
bool NoItins; // Don't use itineraries?
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.59 -> 1.60
---
Log message:
When a priority_queue is empty, the behavior of top() operator is
non-deterministic. Returns NULL when it's empty!
---
Diffs of the changes: (+1 -0)
ScheduleDAGList.cpp |1 +
1 files changed, 1 insertion(+)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.59
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.60
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.59 Fri May 12
01:33:48 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Tue May 30 13:04:34 2006
@@ -356,6 +356,7 @@
}
SUnit *pop() {
+ if (empty()) return NULL;
SUnit *V = Queue.top();
Queue.pop();
return V;
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.56 -> 1.57
---
Log message:
Templatify RegReductionPriorityQueue
---
Diffs of the changes: (+12 -7)
ScheduleDAGList.cpp | 19 ---
1 files changed, 12 insertions(+), 7 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.56
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.57
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.56 Tue May 9
02:13:34 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Wed May 10 01:16:44 2006
@@ -892,12 +892,13 @@
// to reduce register pressure.
//
namespace {
+ template
class RegReductionPriorityQueue;
/// Sorting functions for the Available queue.
struct ls_rr_sort : public std::binary_function {
-RegReductionPriorityQueue *SPQ;
-ls_rr_sort(RegReductionPriorityQueue *spq) : SPQ(spq) {}
+RegReductionPriorityQueue *SPQ;
+ls_rr_sort(RegReductionPriorityQueue *spq) : SPQ(spq) {}
ls_rr_sort(const ls_rr_sort &RHS) : SPQ(RHS.SPQ) {}
bool operator()(const SUnit* left, const SUnit* right) const;
@@ -905,6 +906,7 @@
} // end anonymous namespace
namespace {
+ template
class RegReductionPriorityQueue : public SchedulingPriorityQueue {
// SUnits - The SUnits for the current graph.
const std::vector *SUnits;
@@ -912,7 +914,7 @@
// SethiUllmanNumbers - The SethiUllman number for each node.
std::vector SethiUllmanNumbers;
-std::priority_queue, ls_rr_sort> Queue;
+std::priority_queue, SF> Queue;
public:
RegReductionPriorityQueue() :
Queue(ls_rr_sort(this)) {}
@@ -1079,7 +1081,8 @@
/// it as a def&use operand. Add a pseudo control edge from it to the other
/// node (if it won't create a cycle) so the two-address one will be scheduled
/// first (lower in the schedule).
-void RegReductionPriorityQueue::AddPseudoTwoAddrDeps() {
+template
+void RegReductionPriorityQueue::AddPseudoTwoAddrDeps() {
for (unsigned i = 0, e = SUnits->size(); i != e; ++i) {
SUnit *SU = (SUnit *)&((*SUnits)[i]);
SDNode *Node = SU->Node;
@@ -1112,7 +1115,8 @@
/// CalcNodePriority - Priority is the Sethi Ullman number.
/// Smaller number is the higher priority.
-int RegReductionPriorityQueue::CalcNodePriority(const SUnit *SU) {
+template
+int RegReductionPriorityQueue::CalcNodePriority(const SUnit *SU) {
int &SethiUllmanNumber = SethiUllmanNumbers[SU->NodeNum];
if (SethiUllmanNumber != 0)
return SethiUllmanNumber;
@@ -1150,7 +1154,8 @@
}
/// CalculatePriorities - Calculate priorities of all scheduling units.
-void RegReductionPriorityQueue::CalculatePriorities() {
+template
+void RegReductionPriorityQueue::CalculatePriorities() {
SethiUllmanNumbers.assign(SUnits->size(), 0);
for (unsigned i = 0, e = SUnits->size(); i != e; ++i)
@@ -1386,7 +1391,7 @@
llvm::ScheduleDAG* llvm::createBURRListDAGScheduler(SelectionDAG &DAG,
MachineBasicBlock *BB) {
return new ScheduleDAGList(DAG, BB, DAG.getTarget(), true,
- new RegReductionPriorityQueue(),
+ new RegReductionPriorityQueue(),
new HazardRecognizer());
}
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.55 -> 1.56
---
Log message:
Add pseudo dependency to force a def&use operand to be scheduled last (unless
the distance between the def and another use is much longer). This is under
option control for now "-sched-lower-defnuse".
---
Diffs of the changes: (+108 -17)
ScheduleDAGList.cpp | 125
1 files changed, 108 insertions(+), 17 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.55
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.56
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.55 Thu May 4
20:47:05 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Tue May 9 02:13:34 2006
@@ -35,8 +35,8 @@
using namespace llvm;
namespace {
- cl::opt
- SchedVertically("sched-vertically", cl::Hidden);
+ cl::opt SchedVertically("sched-vertically", cl::Hidden);
+ cl::opt SchedLowerDefNUse("sched-lower-defnuse", cl::Hidden);
}
namespace {
@@ -198,6 +198,8 @@
/// of scheduled nodes which are not themselves scheduled.
std::map > OpenNodes;
+ /// RegPressureLimits - Keep track of upper limit of register pressure for
+ /// each register class that allows the scheduler to go into vertical mode.
std::map RegPressureLimits;
public:
@@ -418,7 +420,7 @@
// Build scheduling units.
BuildSchedUnits();
-
+
AvailableQueue->initNodes(SUnits);
// Execute the actual scheduling loop Top-Down or Bottom-Up as appropriate.
@@ -917,6 +919,9 @@
void initNodes(const std::vector &sunits) {
SUnits = &sunits;
+ // Add pseudo dependency edges for two-address nodes.
+ if (SchedLowerDefNUse)
+AddPseudoTwoAddrDeps();
// Calculate node priorities.
CalculatePriorities();
}
@@ -968,6 +973,7 @@
}
private:
+void AddPseudoTwoAddrDeps();
void CalculatePriorities();
int CalcNodePriority(const SUnit *SU);
};
@@ -993,18 +999,20 @@
if (RIsFloater)
RBonus += 2;
- // Special tie breaker: if two nodes share a operand, the one that use it
- // as a def&use operand is preferred.
- if (LIsTarget && RIsTarget) {
-if (left->isTwoAddress && !right->isTwoAddress) {
- SDNode *DUNode = left->Node->getOperand(0).Val;
- if (DUNode->isOperand(right->Node))
-LBonus += 2;
-}
-if (!left->isTwoAddress && right->isTwoAddress) {
- SDNode *DUNode = right->Node->getOperand(0).Val;
- if (DUNode->isOperand(left->Node))
-RBonus += 2;
+ if (!SchedLowerDefNUse) {
+// Special tie breaker: if two nodes share a operand, the one that use it
+// as a def&use operand is preferred.
+if (LIsTarget && RIsTarget) {
+ if (left->isTwoAddress && !right->isTwoAddress) {
+SDNode *DUNode = left->Node->getOperand(0).Val;
+if (DUNode->isOperand(right->Node))
+ LBonus += 2;
+ }
+ if (!left->isTwoAddress && right->isTwoAddress) {
+SDNode *DUNode = right->Node->getOperand(0).Val;
+if (DUNode->isOperand(left->Node))
+ RBonus += 2;
+ }
}
}
@@ -1019,6 +1027,88 @@
return false;
}
+static inline bool isCopyFromLiveIn(const SUnit *SU) {
+ SDNode *N = SU->Node;
+ return N->getOpcode() == ISD::CopyFromReg &&
+N->getOperand(N->getNumOperands()-1).getValueType() != MVT::Flag;
+}
+
+// FIXME: This is probably too slow!
+static void isReachable(SUnit *SU, SUnit *TargetSU,
+std::set &Visited, bool &Reached) {
+ if (Reached) return;
+ if (SU == TargetSU) {
+Reached = true;
+return;
+ }
+ if (!Visited.insert(SU).second) return;
+
+ for (std::set >::iterator I = SU->Preds.begin(),
+ E = SU->Preds.end(); I != E; ++I)
+isReachable(I->first, TargetSU, Visited, Reached);
+}
+
+static bool isReachable(SUnit *SU, SUnit *TargetSU) {
+ std::set Visited;
+ bool Reached = false;
+ isReachable(SU, TargetSU, Visited, Reached);
+ return Reached;
+}
+
+static SUnit *getDefUsePredecessor(SUnit *SU) {
+ SDNode *DU = SU->Node->getOperand(0).Val;
+ for (std::set >::iterator
+ I = SU->Preds.begin(), E = SU->Preds.end(); I != E; ++I) {
+if (I->second) continue; // ignore chain preds
+SUnit *PredSU = I->first;
+if (PredSU->Node == DU)
+ return PredSU;
+ }
+
+ // Must be flagged.
+ return NULL;
+}
+
+static bool canClobber(SUnit *SU, SUnit *Op) {
+ if (SU->isTwoAddress)
+return Op == getDefUsePredecessor(SU);
+ return false;
+}
+
+/// AddPseudoTwoAddrDeps - If two nodes share an operand and one of them uses
+/// it as a def&use operand. Add a pseudo control edge from it to the other
+/// node (if it won't create a cycle) so the two-address one will be scheduled
+/// first (lower in the schedule).
+void RegReductionPriorityQueue::AddPseudoTwoAddrDeps() {
+ for (unsigned i = 0, e = SUnits->size(); i != e; ++i) {
+S
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.54 -> 1.55
---
Log message:
Fix VC++ compilation error.
---
Diffs of the changes: (+1 -1)
ScheduleDAGList.cpp |2 +-
1 files changed, 1 insertion(+), 1 deletion(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.54
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.55
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.54 Thu May 4
14:16:39 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Thu May 4 20:47:05 2006
@@ -541,7 +541,7 @@
static bool isSimpleFloaterUse(const SUnit *SU) {
unsigned NumOps = 0;
- for (std::set >::iterator I = SU->Preds.begin(),
+ for (std::set >::const_iterator I =
SU->Preds.begin(),
E = SU->Preds.end(); I != E; ++I) {
if (I->second) continue;
if (++NumOps > 1)
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.53 -> 1.54
---
Log message:
Initial support for register pressure aware scheduling. The register reduction
scheduler can go into a "vertical mode" (i.e. traversing up the two-address
chain, etc.) when the register pressure is low.
This does seem to reduce the number of spills in the cases I've looked at. But
with x86, it's no guarantee the performance of the code improves.
It can be turned on with -sched-vertically option.
---
Diffs of the changes: (+238 -50)
ScheduleDAGList.cpp | 288 ++--
1 files changed, 238 insertions(+), 50 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.53
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.54
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.53 Tue May 2
21:10:45 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Thu May 4 14:16:39 2006
@@ -20,6 +20,8 @@
#define DEBUG_TYPE "sched"
#include "llvm/CodeGen/ScheduleDAG.h"
+#include "llvm/CodeGen/SSARegMap.h"
+#include "llvm/Target/MRegisterInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Support/Debug.h"
@@ -33,6 +35,11 @@
using namespace llvm;
namespace {
+ cl::opt
+ SchedVertically("sched-vertically", cl::Hidden);
+}
+
+namespace {
Statistic<> NumNoops ("scheduler", "Number of noops inserted");
Statistic<> NumStalls("scheduler", "Number of pipeline stalls");
@@ -63,10 +70,10 @@
SUnit(SDNode *node, unsigned nodenum)
: Node(node), NumPredsLeft(0), NumSuccsLeft(0),
- NumChainPredsLeft(0), NumChainSuccsLeft(0),
-isTwoAddress(false), isDefNUseOperand(false), isPending(false),
- isAvailable(false), isScheduled(false),
- Latency(0), CycleBound(0), Cycle(0), NodeNum(nodenum) {}
+NumChainPredsLeft(0), NumChainSuccsLeft(0),
+isTwoAddress(false), isDefNUseOperand(false),
+isPending(false), isAvailable(false), isScheduled(false),
+Latency(0), CycleBound(0), Cycle(0), NodeNum(nodenum) {}
void dump(const SelectionDAG *G) const;
void dumpAll(const SelectionDAG *G) const;
@@ -141,6 +148,8 @@
virtual void push_all(const std::vector &Nodes) = 0;
virtual SUnit *pop() = 0;
+
+ virtual void RemoveFromPriorityQueue(SUnit *SU) = 0;
/// ScheduledNode - As each node is scheduled, this method is invoked. This
/// allows the priority function to adjust the priority of node that have
@@ -160,6 +169,7 @@
private:
// SDNode to SUnit mapping (many to one).
std::map SUnitMap;
+
// The schedule. Null SUnit*'s represent noop instructions.
std::vector Sequence;
@@ -180,10 +190,16 @@
/// added to the AvailableQueue. This keeps track of each SUnit and the
/// number of cycles left to execute before the operation is available.
std::vector > PendingQueue;
-
+
/// HazardRec - The hazard recognizer to use.
HazardRecognizer *HazardRec;
-
+
+ /// OpenNodes - Nodes with open live ranges, i.e. predecessors or successors
+ /// of scheduled nodes which are not themselves scheduled.
+ std::map > OpenNodes;
+
+ std::map RegPressureLimits;
+
public:
ScheduleDAGList(SelectionDAG &dag, MachineBasicBlock *bb,
const TargetMachine &tm, bool isbottomup,
@@ -206,7 +222,8 @@
SUnit *NewSUnit(SDNode *N);
void ReleasePred(SUnit *PredSU, bool isChain, unsigned CurCycle);
void ReleaseSucc(SUnit *SuccSU, bool isChain);
- void ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle);
+ void ScheduleNodeBottomUp(SUnit *SU, unsigned& CurCycle, bool
Veritical=true);
+ void ScheduleVertically(SUnit *SU, unsigned& CurCycle);
void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle);
void ListScheduleTopDown();
void ListScheduleBottomUp();
@@ -424,6 +441,41 @@
// Bottom-Up Scheduling
//===--===//
+static const TargetRegisterClass *getRegClass(SUnit *SU,
+ const TargetInstrInfo *TII,
+ const MRegisterInfo *MRI,
+ SSARegMap *RegMap) {
+ if (SU->Node->isTargetOpcode()) {
+unsigned Opc = SU->Node->getTargetOpcode();
+const TargetInstrDescriptor &II = TII->get(Opc);
+return II.OpInfo->RegClass;
+ } else {
+assert(SU->Node->getOpcode() == ISD::CopyFromReg);
+unsigned SrcReg = cast(SU->Node->getOperand(1))->getReg();
+if (MRegisterInfo::isVirtualRegister(SrcReg))
+ return RegMap->getRegClass(SrcReg);
+else {
+ for (MRegisterInfo::regclass_iterator I = MRI->regclass_begin(),
+ E = MRI->regclass_end(); I != E; ++I)
+if ((*I)->hasType(SU->Node->getValueType(0)) &&
+(*I)->contains(SrcReg))
+ return *I;
+
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.52 -> 1.53
---
Log message:
Bottom up register pressure reduction work: clean up some hacks and enhanced
the heuristic to further reduce spills for several test cases. (Note, it may
not necessarily translate to runtime win!)
---
Diffs of the changes: (+72 -75)
ScheduleDAGList.cpp | 147 +---
1 files changed, 72 insertions(+), 75 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.52
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.53
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.52 Mon May 1
04:20:44 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Tue May 2 21:10:45 2006
@@ -33,13 +33,6 @@
using namespace llvm;
namespace {
- // TEMPORARY option to test a fix.
- cl::opt
- SchedIgnorStore("sched-ignore-store", cl::Hidden);
-
-}
-
-namespace {
Statistic<> NumNoops ("scheduler", "Number of noops inserted");
Statistic<> NumStalls("scheduler", "Number of pipeline stalls");
@@ -58,7 +51,6 @@
short NumSuccsLeft; // # of succs not scheduled.
short NumChainPredsLeft;// # of chain preds not scheduled.
short NumChainSuccsLeft;// # of chain succs not scheduled.
-bool isStore : 1; // Is a store.
bool isTwoAddress : 1; // Is a two-address instruction.
bool isDefNUseOperand : 1; // Is a def&use operand.
bool isPending: 1; // True once pending.
@@ -71,9 +63,9 @@
SUnit(SDNode *node, unsigned nodenum)
: Node(node), NumPredsLeft(0), NumSuccsLeft(0),
- NumChainPredsLeft(0), NumChainSuccsLeft(0), isStore(false),
- isTwoAddress(false), isDefNUseOperand(false),
- isPending(false), isAvailable(false), isScheduled(false),
+ NumChainPredsLeft(0), NumChainSuccsLeft(0),
+isTwoAddress(false), isDefNUseOperand(false), isPending(false),
+ isAvailable(false), isScheduled(false),
Latency(0), CycleBound(0), Cycle(0), NodeNum(nodenum) {}
void dump(const SelectionDAG *G) const;
@@ -82,7 +74,7 @@
}
void SUnit::dump(const SelectionDAG *G) const {
- std::cerr << "SU: ";
+ std::cerr << "SU(" << NodeNum << "): ";
Node->dump(G);
std::cerr << "\n";
if (FlaggedNodes.size() != 0) {
@@ -325,11 +317,13 @@
if (MainNode->isTargetOpcode()) {
unsigned Opc = MainNode->getTargetOpcode();
- if (TII->isTwoAddrInstr(Opc))
+ if (TII->isTwoAddrInstr(Opc)) {
SU->isTwoAddress = true;
- if (TII->isStore(Opc))
-if (!SchedIgnorStore)
- SU->isStore = true;
+SDNode *OpN = MainNode->getOperand(0).Val;
+SUnit *OpSU = SUnitMap[OpN];
+if (OpSU)
+ OpSU->isDefNUseOperand = true;
+ }
}
// Find all predecessors and successors of the group.
@@ -345,7 +339,7 @@
SUnit *OpSU = SUnitMap[OpN];
assert(OpSU && "Node has no SUnit!");
if (OpSU == SU) continue; // In the same group.
-
+
MVT::ValueType OpVT = N->getOperand(i).getValueType();
assert(OpVT != MVT::Flag && "Flagged nodes should be in same sunit!");
bool isChain = OpVT == MVT::Other;
@@ -470,6 +464,7 @@
DEBUG(SU->dump(&DAG));
SU->Cycle = CurCycle;
+ AvailableQueue->ScheduledNode(SU);
Sequence.push_back(SU);
// Bottom up: release predecessors
@@ -480,6 +475,8 @@
// calculate directly.
if (!I->second)
SU->NumPredsLeft--;
+else
+ SU->NumChainPredsLeft--;
}
}
@@ -499,9 +496,9 @@
// While Available queue is not empty, grab the node with the highest
// priority. If it is not ready put it back. Schedule the node.
std::vector NotReady;
+ SUnit *CurrNode = NULL;
while (!AvailableQueue->empty()) {
SUnit *CurrNode = AvailableQueue->pop();
-
while (!isReady(CurrNode, CurrCycle)) {
NotReady.push_back(CurrNode);
CurrNode = AvailableQueue->pop();
@@ -514,7 +511,6 @@
ScheduleNodeBottomUp(CurrNode, CurrCycle);
CurrCycle++;
CurrNode->isScheduled = true;
-AvailableQueue->ScheduledNode(CurrNode);
}
// Add entry node last
@@ -748,12 +744,12 @@
const std::vector *SUnits;
// SethiUllmanNumbers - The SethiUllman number for each node.
-std::vector SethiUllmanNumbers;
+std::vector SethiUllmanNumbers;
std::priority_queue, ls_rr_sort> Queue;
public:
-RegReductionPriorityQueue() : Queue(ls_rr_sort(this)) {
-}
+RegReductionPriorityQueue() :
+Queue(ls_rr_sort(this)) {}
void initNodes(const std::vector &sunits) {
SUnits = &sunits;
@@ -765,7 +761,7 @@
SethiUllmanNumbers.clear();
}
-unsigned getSethiUllmanNumber(unsigned NodeNum) const {
+int getSethiUllmanNumber(unsigned NodeNum) const {
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG: ScheduleDAGList.cpp updated: 1.51 -> 1.52 --- Log message: Dis-favor stores more --- Diffs of the changes: (+2 -2) ScheduleDAGList.cpp |4 ++-- 1 files changed, 2 insertions(+), 2 deletions(-) Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.51 llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.52 --- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.51 Mon May 1 04:14:40 2006 +++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Mon May 1 04:20:44 2006 @@ -821,9 +821,9 @@ // This would make sure the scheduled code completed all computations and // the stores before the next series of computation starts. if (!left->isStore && right->isStore) -LBonus += 2; +LBonus += 4; if (left->isStore && !right->isStore) -RBonus += 2; +RBonus += 4; // Priority1 is just the number of live range genned. int LPriority1 = left ->NumPredsLeft - LBonus; ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.50 -> 1.51
---
Log message:
Bottom up register-pressure reduction scheduler now pushes store operations
up the schedule. This helps code that looks like this:
loads ...
computations (first set) ...
stores (first set) ...
loads
computations (seccond set) ...
stores (seccond set) ...
Without this change, the stores and computations are more likely to
interleave:
loads ...
loads ...
computations (first set) ...
computations (second set) ...
computations (first set) ...
stores (first set) ...
computations (second set) ...
stores (stores set) ...
This can increase the number of spills if we are unlucky.
---
Diffs of the changes: (+41 -17)
ScheduleDAGList.cpp | 58
1 files changed, 41 insertions(+), 17 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.50
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.51
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.50 Mon May 1
03:56:34 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Mon May 1 04:14:40 2006
@@ -33,6 +33,13 @@
using namespace llvm;
namespace {
+ // TEMPORARY option to test a fix.
+ cl::opt
+ SchedIgnorStore("sched-ignore-store", cl::Hidden);
+
+}
+
+namespace {
Statistic<> NumNoops ("scheduler", "Number of noops inserted");
Statistic<> NumStalls("scheduler", "Number of pipeline stalls");
@@ -51,6 +58,7 @@
short NumSuccsLeft; // # of succs not scheduled.
short NumChainPredsLeft;// # of chain preds not scheduled.
short NumChainSuccsLeft;// # of chain succs not scheduled.
+bool isStore : 1; // Is a store.
bool isTwoAddress : 1; // Is a two-address instruction.
bool isDefNUseOperand : 1; // Is a def&use operand.
bool isPending: 1; // True once pending.
@@ -63,7 +71,7 @@
SUnit(SDNode *node, unsigned nodenum)
: Node(node), NumPredsLeft(0), NumSuccsLeft(0),
- NumChainPredsLeft(0), NumChainSuccsLeft(0),
+ NumChainPredsLeft(0), NumChainSuccsLeft(0), isStore(false),
isTwoAddress(false), isDefNUseOperand(false),
isPending(false), isAvailable(false), isScheduled(false),
Latency(0), CycleBound(0), Cycle(0), NodeNum(nodenum) {}
@@ -315,9 +323,14 @@
SUnit *SU = &SUnits[su];
SDNode *MainNode = SU->Node;
-if (MainNode->isTargetOpcode() &&
-TII->isTwoAddrInstr(MainNode->getTargetOpcode()))
- SU->isTwoAddress = true;
+if (MainNode->isTargetOpcode()) {
+ unsigned Opc = MainNode->getTargetOpcode();
+ if (TII->isTwoAddrInstr(Opc))
+SU->isTwoAddress = true;
+ if (TII->isStore(Opc))
+if (!SchedIgnorStore)
+ SU->isStore = true;
+}
// Find all predecessors and successors of the group.
// Temporarily add N to make code simpler.
@@ -358,9 +371,9 @@
SU->FlaggedNodes.pop_back();
}
- return;
DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
SUnits[su].dumpAll(&DAG));
+ return;
}
/// EmitSchedule - Emit the machine code in scheduled order.
@@ -735,7 +748,7 @@
const std::vector *SUnits;
// SethiUllmanNumbers - The SethiUllman number for each node.
-std::vector SethiUllmanNumbers;
+std::vector SethiUllmanNumbers;
std::priority_queue, ls_rr_sort> Queue;
public:
@@ -774,7 +787,7 @@
}
private:
void CalculatePriorities();
-int CalcNodePriority(const SUnit *SU);
+unsigned CalcNodePriority(const SUnit *SU);
};
}
@@ -784,7 +797,7 @@
int LBonus = (int)left ->isDefNUseOperand;
int RBonus = (int)right->isDefNUseOperand;
-
+
// Special tie breaker: if two nodes share a operand, the one that
// use it as a def&use operand is preferred.
if (left->isTwoAddress && !right->isTwoAddress) {
@@ -798,6 +811,20 @@
RBonus++;
}
+ // Push stores up as much as possible. This really help code like this:
+ // load
+ // compute
+ // store
+ // load
+ // compute
+ // store
+ // This would make sure the scheduled code completed all computations and
+ // the stores before the next series of computation starts.
+ if (!left->isStore && right->isStore)
+LBonus += 2;
+ if (left->isStore && !right->isStore)
+RBonus += 2;
+
// Priority1 is just the number of live range genned.
int LPriority1 = left ->NumPredsLeft - LBonus;
int RPriority1 = right->NumPredsLeft - RBonus;
@@ -819,9 +846,9 @@
/// CalcNodePriority - Priority is the Sethi Ullman number.
/// Smaller number is the higher priority.
-int RegReductionPriorityQueue::CalcNodePriority(const SUnit *SU) {
- int &SethiUllmanNumber = SethiUllmanNumbers[SU->NodeNum];
- if (SethiUllmanNumber != INT_MIN)
+unsigned RegReductionPriorityQueue::CalcNode
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.49 -> 1.50
---
Log message:
Didn't mean ScheduleDAGList.cpp to make the last checkin.
---
Diffs of the changes: (+17 -33)
ScheduleDAGList.cpp | 50 +-
1 files changed, 17 insertions(+), 33 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.49
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.50
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.49 Mon May 1
03:54:57 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Mon May 1 03:56:34 2006
@@ -51,7 +51,6 @@
short NumSuccsLeft; // # of succs not scheduled.
short NumChainPredsLeft;// # of chain preds not scheduled.
short NumChainSuccsLeft;// # of chain succs not scheduled.
-bool isStore : 1; // Is a store.
bool isTwoAddress : 1; // Is a two-address instruction.
bool isDefNUseOperand : 1; // Is a def&use operand.
bool isPending: 1; // True once pending.
@@ -64,7 +63,7 @@
SUnit(SDNode *node, unsigned nodenum)
: Node(node), NumPredsLeft(0), NumSuccsLeft(0),
- NumChainPredsLeft(0), NumChainSuccsLeft(0), isStore(false),
+ NumChainPredsLeft(0), NumChainSuccsLeft(0),
isTwoAddress(false), isDefNUseOperand(false),
isPending(false), isAvailable(false), isScheduled(false),
Latency(0), CycleBound(0), Cycle(0), NodeNum(nodenum) {}
@@ -316,13 +315,9 @@
SUnit *SU = &SUnits[su];
SDNode *MainNode = SU->Node;
-if (MainNode->isTargetOpcode()) {
- unsigned Opc = MainNode->getTargetOpcode();
- if (TII->isTwoAddrInstr(Opc))
-SU->isTwoAddress = true;
- if (TII->isStore(Opc))
-SU->isStore = true;
-}
+if (MainNode->isTargetOpcode() &&
+TII->isTwoAddrInstr(MainNode->getTargetOpcode()))
+ SU->isTwoAddress = true;
// Find all predecessors and successors of the group.
// Temporarily add N to make code simpler.
@@ -363,9 +358,9 @@
SU->FlaggedNodes.pop_back();
}
+ return;
DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
SUnits[su].dumpAll(&DAG));
- return;
}
/// EmitSchedule - Emit the machine code in scheduled order.
@@ -740,7 +735,7 @@
const std::vector *SUnits;
// SethiUllmanNumbers - The SethiUllman number for each node.
-std::vector SethiUllmanNumbers;
+std::vector SethiUllmanNumbers;
std::priority_queue, ls_rr_sort> Queue;
public:
@@ -779,7 +774,7 @@
}
private:
void CalculatePriorities();
-unsigned CalcNodePriority(const SUnit *SU);
+int CalcNodePriority(const SUnit *SU);
};
}
@@ -789,7 +784,7 @@
int LBonus = (int)left ->isDefNUseOperand;
int RBonus = (int)right->isDefNUseOperand;
-
+
// Special tie breaker: if two nodes share a operand, the one that
// use it as a def&use operand is preferred.
if (left->isTwoAddress && !right->isTwoAddress) {
@@ -803,20 +798,6 @@
RBonus++;
}
- // Push stores up as much as possible. This really help code like this:
- // load
- // compute
- // store
- // load
- // compute
- // store
- // This would make sure the scheduled code completed all computations and
- // the stores before the next series of computation starts.
- if (!left->isStore && right->isStore)
-LBonus += 2;
- if (left->isStore && !right->isStore)
-RBonus += 2;
-
// Priority1 is just the number of live range genned.
int LPriority1 = left ->NumPredsLeft - LBonus;
int RPriority1 = right->NumPredsLeft - RBonus;
@@ -838,9 +819,9 @@
/// CalcNodePriority - Priority is the Sethi Ullman number.
/// Smaller number is the higher priority.
-unsigned RegReductionPriorityQueue::CalcNodePriority(const SUnit *SU) {
- unsigned &SethiUllmanNumber = SethiUllmanNumbers[SU->NodeNum];
- if (SethiUllmanNumber != 0)
+int RegReductionPriorityQueue::CalcNodePriority(const SUnit *SU) {
+ int &SethiUllmanNumber = SethiUllmanNumbers[SU->NodeNum];
+ if (SethiUllmanNumber != INT_MIN)
return SethiUllmanNumber;
if (SU->Preds.size() == 0) {
@@ -851,7 +832,7 @@
I = SU->Preds.begin(), E = SU->Preds.end(); I != E; ++I) {
if (I->second) continue; // ignore chain preds.
SUnit *PredSU = I->first;
- unsigned PredSethiUllman = CalcNodePriority(PredSU);
+ int PredSethiUllman = CalcNodePriority(PredSU);
if (PredSethiUllman > SethiUllmanNumber) {
SethiUllmanNumber = PredSethiUllman;
Extra = 0;
@@ -859,7 +840,10 @@
Extra++;
}
-SethiUllmanNumber += Extra;
+if (SU->Node->getOpcode() != ISD::TokenFactor)
+ SethiUllmanNumber += Extra;
+else
+ SethiUllmanNumber = (Extra == 1) ? 0 : Extra-1;
}
return SethiUllmanNumber;
@
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.48 -> 1.49
---
Log message:
Remove temp. option -spiller-check-liveout, it didn't cause any failure nor
performance regressions.
---
Diffs of the changes: (+33 -17)
ScheduleDAGList.cpp | 50 +-
1 files changed, 33 insertions(+), 17 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.48
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.49
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.48 Sun Mar 12
03:01:41 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Mon May 1 03:54:57 2006
@@ -51,6 +51,7 @@
short NumSuccsLeft; // # of succs not scheduled.
short NumChainPredsLeft;// # of chain preds not scheduled.
short NumChainSuccsLeft;// # of chain succs not scheduled.
+bool isStore : 1; // Is a store.
bool isTwoAddress : 1; // Is a two-address instruction.
bool isDefNUseOperand : 1; // Is a def&use operand.
bool isPending: 1; // True once pending.
@@ -63,7 +64,7 @@
SUnit(SDNode *node, unsigned nodenum)
: Node(node), NumPredsLeft(0), NumSuccsLeft(0),
- NumChainPredsLeft(0), NumChainSuccsLeft(0),
+ NumChainPredsLeft(0), NumChainSuccsLeft(0), isStore(false),
isTwoAddress(false), isDefNUseOperand(false),
isPending(false), isAvailable(false), isScheduled(false),
Latency(0), CycleBound(0), Cycle(0), NodeNum(nodenum) {}
@@ -315,9 +316,13 @@
SUnit *SU = &SUnits[su];
SDNode *MainNode = SU->Node;
-if (MainNode->isTargetOpcode() &&
-TII->isTwoAddrInstr(MainNode->getTargetOpcode()))
- SU->isTwoAddress = true;
+if (MainNode->isTargetOpcode()) {
+ unsigned Opc = MainNode->getTargetOpcode();
+ if (TII->isTwoAddrInstr(Opc))
+SU->isTwoAddress = true;
+ if (TII->isStore(Opc))
+SU->isStore = true;
+}
// Find all predecessors and successors of the group.
// Temporarily add N to make code simpler.
@@ -358,9 +363,9 @@
SU->FlaggedNodes.pop_back();
}
- return;
DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
SUnits[su].dumpAll(&DAG));
+ return;
}
/// EmitSchedule - Emit the machine code in scheduled order.
@@ -735,7 +740,7 @@
const std::vector *SUnits;
// SethiUllmanNumbers - The SethiUllman number for each node.
-std::vector SethiUllmanNumbers;
+std::vector SethiUllmanNumbers;
std::priority_queue, ls_rr_sort> Queue;
public:
@@ -774,7 +779,7 @@
}
private:
void CalculatePriorities();
-int CalcNodePriority(const SUnit *SU);
+unsigned CalcNodePriority(const SUnit *SU);
};
}
@@ -784,7 +789,7 @@
int LBonus = (int)left ->isDefNUseOperand;
int RBonus = (int)right->isDefNUseOperand;
-
+
// Special tie breaker: if two nodes share a operand, the one that
// use it as a def&use operand is preferred.
if (left->isTwoAddress && !right->isTwoAddress) {
@@ -798,6 +803,20 @@
RBonus++;
}
+ // Push stores up as much as possible. This really help code like this:
+ // load
+ // compute
+ // store
+ // load
+ // compute
+ // store
+ // This would make sure the scheduled code completed all computations and
+ // the stores before the next series of computation starts.
+ if (!left->isStore && right->isStore)
+LBonus += 2;
+ if (left->isStore && !right->isStore)
+RBonus += 2;
+
// Priority1 is just the number of live range genned.
int LPriority1 = left ->NumPredsLeft - LBonus;
int RPriority1 = right->NumPredsLeft - RBonus;
@@ -819,9 +838,9 @@
/// CalcNodePriority - Priority is the Sethi Ullman number.
/// Smaller number is the higher priority.
-int RegReductionPriorityQueue::CalcNodePriority(const SUnit *SU) {
- int &SethiUllmanNumber = SethiUllmanNumbers[SU->NodeNum];
- if (SethiUllmanNumber != INT_MIN)
+unsigned RegReductionPriorityQueue::CalcNodePriority(const SUnit *SU) {
+ unsigned &SethiUllmanNumber = SethiUllmanNumbers[SU->NodeNum];
+ if (SethiUllmanNumber != 0)
return SethiUllmanNumber;
if (SU->Preds.size() == 0) {
@@ -832,7 +851,7 @@
I = SU->Preds.begin(), E = SU->Preds.end(); I != E; ++I) {
if (I->second) continue; // ignore chain preds.
SUnit *PredSU = I->first;
- int PredSethiUllman = CalcNodePriority(PredSU);
+ unsigned PredSethiUllman = CalcNodePriority(PredSU);
if (PredSethiUllman > SethiUllmanNumber) {
SethiUllmanNumber = PredSethiUllman;
Extra = 0;
@@ -840,10 +859,7 @@
Extra++;
}
-if (SU->Node->getOpcode() != ISD::TokenFactor)
- SethiUllmanNumber += Extra;
-else
- SethiUllmanNumber = (Extra == 1) ? 0 : Extra-1;
+SethiUllmanNumber += Ex
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.47 -> 1.48
---
Log message:
Don't advance the hazard recognizer when there are no hazards and no
instructions
to be emitted.
Don't add one to the latency of a completed instruction if the latency of the
op is 0.
---
Diffs of the changes: (+40 -25)
ScheduleDAGList.cpp | 65
1 files changed, 40 insertions(+), 25 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.47
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.48
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.47 Sat Mar 11
21:52:09 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Sun Mar 12 03:01:41 2006
@@ -357,6 +357,8 @@
// Remove MainNode from FlaggedNodes again.
SU->FlaggedNodes.pop_back();
}
+
+ return;
DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
SUnits[su].dumpAll(&DAG));
}
@@ -550,14 +552,14 @@
unsigned AvailableCycle = 0;
for (std::set >::iterator I =
SuccSU->Preds.begin(),
E = SuccSU->Preds.end(); I != E; ++I) {
- // If this is a token edge, we don't need to wait for the full latency of
- // the preceeding instruction (e.g. a long-latency load) unless there is
- // also some other data dependence.
+ // If this is a token edge, we don't need to wait for the latency of the
+ // preceeding instruction (e.g. a long-latency load) unless there is also
+ // some other data dependence.
unsigned PredDoneCycle = I->first->Cycle;
if (!I->second)
PredDoneCycle += I->first->Latency;
- else
-PredDoneCycle += 1;
+ else if (I->first->Latency)
+PredDoneCycle += 1;
AvailableCycle = std::max(AvailableCycle, PredDoneCycle);
}
@@ -608,7 +610,7 @@
while (!AvailableQueue->empty() || !PendingQueue.empty()) {
// Check to see if any of the pending instructions are ready to issue. If
// so, add them to the available queue.
-for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i)
+for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) {
if (PendingQueue[i].first == CurCycle) {
AvailableQueue->push(PendingQueue[i].second);
PendingQueue[i].second->isAvailable = true;
@@ -618,54 +620,67 @@
} else {
assert(PendingQueue[i].first > CurCycle && "Negative latency?");
}
+}
-SUnit *FoundNode = 0;
+// If there are no instructions available, don't try to issue anything, and
+// don't advance the hazard recognizer.
+if (AvailableQueue->empty()) {
+ ++CurCycle;
+ continue;
+}
+SUnit *FoundSUnit = 0;
+SDNode *FoundNode = 0;
+
bool HasNoopHazards = false;
while (!AvailableQueue->empty()) {
- SUnit *CurNode = AvailableQueue->pop();
+ SUnit *CurSUnit = AvailableQueue->pop();
// Get the node represented by this SUnit.
- SDNode *N = CurNode->Node;
+ FoundNode = CurSUnit->Node;
+
// If this is a pseudo op, like copyfromreg, look to see if there is a
// real target node flagged to it. If so, use the target node.
- for (unsigned i = 0, e = CurNode->FlaggedNodes.size();
- N->getOpcode() < ISD::BUILTIN_OP_END && i != e; ++i)
-N = CurNode->FlaggedNodes[i];
+ for (unsigned i = 0, e = CurSUnit->FlaggedNodes.size();
+ FoundNode->getOpcode() < ISD::BUILTIN_OP_END && i != e; ++i)
+FoundNode = CurSUnit->FlaggedNodes[i];
- HazardRecognizer::HazardType HT = HazardRec->getHazardType(N);
+ HazardRecognizer::HazardType HT = HazardRec->getHazardType(FoundNode);
if (HT == HazardRecognizer::NoHazard) {
-FoundNode = CurNode;
+FoundSUnit = CurSUnit;
break;
}
// Remember if this is a noop hazard.
HasNoopHazards |= HT == HazardRecognizer::NoopHazard;
- NotReady.push_back(CurNode);
+ NotReady.push_back(CurSUnit);
}
// Add the nodes that aren't ready back onto the available list.
-AvailableQueue->push_all(NotReady);
-NotReady.clear();
+if (!NotReady.empty()) {
+ AvailableQueue->push_all(NotReady);
+ NotReady.clear();
+}
// If we found a node to schedule, do it now.
-if (FoundNode) {
- ScheduleNodeTopDown(FoundNode, CurCycle);
- HazardRec->EmitInstruction(FoundNode->Node);
- FoundNode->isScheduled = true;
- AvailableQueue->ScheduledNode(FoundNode);
+if (FoundSUnit) {
+ ScheduleNodeTopDown(FoundSUnit, CurCycle);
+ HazardRec->EmitInstruction(FoundNode);
+ FoundSUnit->isScheduled = true;
+ AvailableQueue->ScheduledNode(FoundSUnit);
// If this is a pseudo-op node, we don't want to increment the current
// cycle.
- if (FoundNode->Latency == 0)
-cont
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.46 -> 1.47
---
Log message:
Chain operands aren't real uses: they don't require the full latency of the
predecessor to finish before they can start.
---
Diffs of the changes: (+10 -4)
ScheduleDAGList.cpp | 14 ++
1 files changed, 10 insertions(+), 4 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.46
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.47
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.46 Sat Mar 11
18:38:57 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Sat Mar 11 21:52:09 2006
@@ -387,8 +387,6 @@
}
/// Schedule - Schedule the DAG using list scheduling.
-/// FIXME: Right now it only supports the burr (bottom up register reducing)
-/// heuristic.
void ScheduleDAGList::Schedule() {
DEBUG(std::cerr << "** List Scheduling **\n");
@@ -552,8 +550,16 @@
unsigned AvailableCycle = 0;
for (std::set >::iterator I =
SuccSU->Preds.begin(),
E = SuccSU->Preds.end(); I != E; ++I) {
- AvailableCycle = std::max(AvailableCycle,
-I->first->Cycle + I->first->Latency);
+ // If this is a token edge, we don't need to wait for the full latency of
+ // the preceeding instruction (e.g. a long-latency load) unless there is
+ // also some other data dependence.
+ unsigned PredDoneCycle = I->first->Cycle;
+ if (!I->second)
+PredDoneCycle += I->first->Latency;
+ else
+PredDoneCycle += 1;
+
+ AvailableCycle = std::max(AvailableCycle, PredDoneCycle);
}
PendingQueue.push_back(std::make_pair(AvailableCycle, SuccSU));
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.45 -> 1.46
---
Log message:
As a pending queue data structure to keep track of instructions whose
operands have all issued, but whose results are not yet available. This
allows us to compile:
int G;
int test(int A, int B, int* P) {
return (G+A)*(B+1);
}
to:
_test:
lis r2, ha16(L_G$non_lazy_ptr)
addi r4, r4, 1
lwz r2, lo16(L_G$non_lazy_ptr)(r2)
lwz r2, 0(r2)
add r2, r2, r3
mullw r3, r2, r4
blr
instead of this, which has a stall between the lis/lwz:
_test:
lis r2, ha16(L_G$non_lazy_ptr)
lwz r2, lo16(L_G$non_lazy_ptr)(r2)
addi r4, r4, 1
lwz r2, 0(r2)
add r2, r2, r3
mullw r3, r2, r4
blr
---
Diffs of the changes: (+62 -36)
ScheduleDAGList.cpp | 98
1 files changed, 62 insertions(+), 36 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.45
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.46
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.45 Sat Mar 11
16:44:37 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Sat Mar 11 18:38:57 2006
@@ -53,6 +53,7 @@
short NumChainSuccsLeft;// # of chain succs not scheduled.
bool isTwoAddress : 1; // Is a two-address instruction.
bool isDefNUseOperand : 1; // Is a def&use operand.
+bool isPending: 1; // True once pending.
bool isAvailable : 1; // True once available.
bool isScheduled : 1; // True once scheduled.
unsigned short Latency; // Node latency.
@@ -64,7 +65,7 @@
: Node(node), NumPredsLeft(0), NumSuccsLeft(0),
NumChainPredsLeft(0), NumChainSuccsLeft(0),
isTwoAddress(false), isDefNUseOperand(false),
- isAvailable(false), isScheduled(false),
+ isPending(false), isAvailable(false), isScheduled(false),
Latency(0), CycleBound(0), Cycle(0), NodeNum(nodenum) {}
void dump(const SelectionDAG *G) const;
@@ -173,6 +174,13 @@
///
SchedulingPriorityQueue *AvailableQueue;
+ /// PendingQueue - This contains all of the instructions whose operands have
+ /// been issued, but their results are not ready yet (due to the latency of
+ /// the operation). Once the operands becomes available, the instruction is
+ /// added to the AvailableQueue. This keeps track of each SUnit and the
+ /// number of cycles left to execute before the operation is available.
+ std::vector > PendingQueue;
+
/// HazardRec - The hazard recognizer to use.
HazardRecognizer *HazardRec;
@@ -197,7 +205,7 @@
private:
SUnit *NewSUnit(SDNode *N);
void ReleasePred(SUnit *PredSU, bool isChain, unsigned CurCycle);
- void ReleaseSucc(SUnit *SuccSU, bool isChain, unsigned CurCycle);
+ void ReleaseSucc(SUnit *SuccSU, bool isChain);
void ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle);
void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle);
void ListScheduleTopDown();
@@ -445,7 +453,7 @@
/// count of its predecessors. If a predecessor pending count is zero, add it
to
/// the Available queue.
void ScheduleDAGList::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) {
- DEBUG(std::cerr << "*** Scheduling: ");
+ DEBUG(std::cerr << "*** Scheduling [" << CurCycle << "]: ");
DEBUG(SU->dump(&DAG));
SU->Cycle = CurCycle;
@@ -527,32 +535,29 @@
//===--===//
/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
-/// the Available queue is the count reaches zero. Also update its cycle bound.
-void ScheduleDAGList::ReleaseSucc(SUnit *SuccSU, bool isChain,
- unsigned CurCycle) {
- // FIXME: the distance between two nodes is not always == the predecessor's
- // latency. For example, the reader can very well read the register written
- // by the predecessor later than the issue cycle. It also depends on the
- // interrupt model (drain vs. freeze).
- SuccSU->CycleBound = std::max(SuccSU->CycleBound, CurCycle +
SuccSU->Latency);
-
+/// the PendingQueue if the count reaches zero.
+void ScheduleDAGList::ReleaseSucc(SUnit *SuccSU, bool isChain) {
if (!isChain)
SuccSU->NumPredsLeft--;
else
SuccSU->NumChainPredsLeft--;
-#ifndef NDEBUG
- if (SuccSU->NumPredsLeft < 0 || SuccSU->NumChainPredsLeft < 0) {
-std::cerr << "*** List scheduling failed! ***\n";
-SuccSU->dump(&DAG);
-std::cerr << " has been released too many times!\n";
-abort();
- }
-#endif
+ assert(SuccSU->NumPredsLeft >= 0 && SuccSU->NumChainPredsLeft >= 0 &&
+ "List scheduling internal error");
if ((SuccSU->NumPredsLeft + SuccSU->NumChainPredsLeft) == 0) {
-SuccSU->isAvailable = true;
-Avail
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.44 -> 1.45
---
Log message:
rename priorityqueue -> availablequeue. When a node is scheduled, remember
which cycle it lands on.
---
Diffs of the changes: (+37 -34)
ScheduleDAGList.cpp | 71 +++-
1 files changed, 37 insertions(+), 34 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.44
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.45
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.44 Sat Mar 11
16:34:41 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Sat Mar 11 16:44:37 2006
@@ -57,6 +57,7 @@
bool isScheduled : 1; // True once scheduled.
unsigned short Latency; // Node latency.
unsigned CycleBound;// Upper/lower cycle to be scheduled
at.
+unsigned Cycle; // Once scheduled, the cycle of the op.
unsigned NodeNum; // Entry # of node in the node vector.
SUnit(SDNode *node, unsigned nodenum)
@@ -64,7 +65,7 @@
NumChainPredsLeft(0), NumChainSuccsLeft(0),
isTwoAddress(false), isDefNUseOperand(false),
isAvailable(false), isScheduled(false),
- Latency(0), CycleBound(0), NodeNum(nodenum) {}
+ Latency(0), CycleBound(0), Cycle(0), NodeNum(nodenum) {}
void dump(const SelectionDAG *G) const;
void dumpAll(const SelectionDAG *G) const;
@@ -168,8 +169,9 @@
/// it is top-down.
bool isBottomUp;
- /// PriorityQueue - The priority queue to use.
- SchedulingPriorityQueue *PriorityQueue;
+ /// AvailableQueue - The priority queue to use for the available SUnits.
+ ///
+ SchedulingPriorityQueue *AvailableQueue;
/// HazardRec - The hazard recognizer to use.
HazardRecognizer *HazardRec;
@@ -177,15 +179,15 @@
public:
ScheduleDAGList(SelectionDAG &dag, MachineBasicBlock *bb,
const TargetMachine &tm, bool isbottomup,
- SchedulingPriorityQueue *priorityqueue,
+ SchedulingPriorityQueue *availqueue,
HazardRecognizer *HR)
: ScheduleDAG(dag, bb, tm), isBottomUp(isbottomup),
- PriorityQueue(priorityqueue), HazardRec(HR) {
+ AvailableQueue(availqueue), HazardRec(HR) {
}
~ScheduleDAGList() {
delete HazardRec;
-delete PriorityQueue;
+delete AvailableQueue;
}
void Schedule();
@@ -385,7 +387,7 @@
// Build scheduling units.
BuildSchedUnits();
- PriorityQueue->initNodes(SUnits);
+ AvailableQueue->initNodes(SUnits);
// Execute the actual scheduling loop Top-Down or Bottom-Up as appropriate.
if (isBottomUp)
@@ -393,7 +395,7 @@
else
ListScheduleTopDown();
- PriorityQueue->releaseState();
+ AvailableQueue->releaseState();
DEBUG(std::cerr << "*** Final schedule ***\n");
DEBUG(dumpSchedule());
@@ -410,12 +412,12 @@
/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to
/// the Available queue is the count reaches zero. Also update its cycle bound.
void ScheduleDAGList::ReleasePred(SUnit *PredSU, bool isChain,
- unsigned CurrCycle) {
+ unsigned CurCycle) {
// FIXME: the distance between two nodes is not always == the predecessor's
// latency. For example, the reader can very well read the register written
// by the predecessor later than the issue cycle. It also depends on the
// interrupt model (drain vs. freeze).
- PredSU->CycleBound = std::max(PredSU->CycleBound,CurrCycle +
PredSU->Latency);
+ PredSU->CycleBound = std::max(PredSU->CycleBound, CurCycle +
PredSU->Latency);
if (!isChain)
PredSU->NumSuccsLeft--;
@@ -435,23 +437,26 @@
// EntryToken has to go last! Special case it here.
if (PredSU->Node->getOpcode() != ISD::EntryToken) {
PredSU->isAvailable = true;
- PriorityQueue->push(PredSU);
+ AvailableQueue->push(PredSU);
}
}
}
/// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending
/// count of its predecessors. If a predecessor pending count is zero, add it
to
/// the Available queue.
-void ScheduleDAGList::ScheduleNodeBottomUp(SUnit *SU, unsigned CurrCycle) {
+void ScheduleDAGList::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) {
DEBUG(std::cerr << "*** Scheduling: ");
DEBUG(SU->dump(&DAG));
+ SU->Cycle = CurCycle;
Sequence.push_back(SU);
// Bottom up: release predecessors
for (std::set >::iterator I = SU->Preds.begin(),
E = SU->Preds.end(); I != E; ++I) {
-ReleasePred(I->first, I->second, CurrCycle);
+ReleasePred(I->first, I->second, CurCycle);
+// FIXME: This is something used by the priority function that it should
+// calculate directly.
if (!I->second)
SU->NumPredsLeft--;
}
@@ -468,27 +473,27 @@
v
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.43 -> 1.44
---
Log message:
Make CurrCycle a local var instead of an instance var
---
Diffs of the changes: (+20 -19)
ScheduleDAGList.cpp | 39 ---
1 files changed, 20 insertions(+), 19 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.43
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.44
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.43 Sat Mar 11
16:28:35 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Sat Mar 11 16:34:41 2006
@@ -160,8 +160,6 @@
std::map SUnitMap;
// The schedule. Null SUnit*'s represent noop instructions.
std::vector Sequence;
- // Current scheduling cycle.
- unsigned CurrCycle;
// The scheduling units.
std::vector SUnits;
@@ -181,8 +179,7 @@
const TargetMachine &tm, bool isbottomup,
SchedulingPriorityQueue *priorityqueue,
HazardRecognizer *HR)
-: ScheduleDAG(dag, bb, tm),
- CurrCycle(0), isBottomUp(isbottomup),
+: ScheduleDAG(dag, bb, tm), isBottomUp(isbottomup),
PriorityQueue(priorityqueue), HazardRec(HR) {
}
@@ -197,10 +194,10 @@
private:
SUnit *NewSUnit(SDNode *N);
- void ReleasePred(SUnit *PredSU, bool isChain);
- void ReleaseSucc(SUnit *SuccSU, bool isChain);
- void ScheduleNodeBottomUp(SUnit *SU);
- void ScheduleNodeTopDown(SUnit *SU);
+ void ReleasePred(SUnit *PredSU, bool isChain, unsigned CurCycle);
+ void ReleaseSucc(SUnit *SuccSU, bool isChain, unsigned CurCycle);
+ void ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle);
+ void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle);
void ListScheduleTopDown();
void ListScheduleBottomUp();
void BuildSchedUnits();
@@ -412,7 +409,8 @@
/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to
/// the Available queue is the count reaches zero. Also update its cycle bound.
-void ScheduleDAGList::ReleasePred(SUnit *PredSU, bool isChain) {
+void ScheduleDAGList::ReleasePred(SUnit *PredSU, bool isChain,
+ unsigned CurrCycle) {
// FIXME: the distance between two nodes is not always == the predecessor's
// latency. For example, the reader can very well read the register written
// by the predecessor later than the issue cycle. It also depends on the
@@ -444,7 +442,7 @@
/// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending
/// count of its predecessors. If a predecessor pending count is zero, add it
to
/// the Available queue.
-void ScheduleDAGList::ScheduleNodeBottomUp(SUnit *SU) {
+void ScheduleDAGList::ScheduleNodeBottomUp(SUnit *SU, unsigned CurrCycle) {
DEBUG(std::cerr << "*** Scheduling: ");
DEBUG(SU->dump(&DAG));
@@ -453,11 +451,10 @@
// Bottom up: release predecessors
for (std::set >::iterator I = SU->Preds.begin(),
E = SU->Preds.end(); I != E; ++I) {
-ReleasePred(I->first, I->second);
+ReleasePred(I->first, I->second, CurrCycle);
if (!I->second)
SU->NumPredsLeft--;
}
- CurrCycle++;
}
/// isReady - True if node's lower cycle bound is less or equal to the current
@@ -469,6 +466,7 @@
/// ListScheduleBottomUp - The main loop of list scheduling for bottom-up
/// schedulers.
void ScheduleDAGList::ListScheduleBottomUp() {
+ unsigned CurrCycle = 0;
// Add root to Available queue.
PriorityQueue->push(SUnitMap[DAG.getRoot().Val]);
@@ -487,7 +485,8 @@
PriorityQueue->push_all(NotReady);
NotReady.clear();
-ScheduleNodeBottomUp(CurrNode);
+ScheduleNodeBottomUp(CurrNode, CurrCycle);
+CurrCycle++;
CurrNode->isScheduled = true;
PriorityQueue->ScheduledNode(CurrNode);
}
@@ -524,7 +523,8 @@
/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
/// the Available queue is the count reaches zero. Also update its cycle bound.
-void ScheduleDAGList::ReleaseSucc(SUnit *SuccSU, bool isChain) {
+void ScheduleDAGList::ReleaseSucc(SUnit *SuccSU, bool isChain,
+ unsigned CurrCycle) {
// FIXME: the distance between two nodes is not always == the predecessor's
// latency. For example, the reader can very well read the register written
// by the predecessor later than the issue cycle. It also depends on the
@@ -554,7 +554,7 @@
/// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending
/// count of its successors. If a successor pending count is zero, add it to
/// the Available queue.
-void ScheduleDAGList::ScheduleNodeTopDown(SUnit *SU) {
+void ScheduleDAGList::ScheduleNodeTopDown(SUnit *SU, unsigned CurrCycle) {
DEBUG(std::cerr << "*** Scheduling: ");
DEBUG(SU->dump(&DAG));
@@ -563,19 +563,19 @@
// Bottom up: release successors.
for (std::set >::iterator I = SU->Succs.begin(),
E = SU->
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.42 -> 1.43
---
Log message:
Move some methods around so that BU specific code is together, TD specific code
is together, and direction independent code is together.
---
Diffs of the changes: (+245 -236)
ScheduleDAGList.cpp | 481 ++--
1 files changed, 245 insertions(+), 236 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.42
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.43
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.42 Sat Mar 11
16:24:20 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Sat Mar 11 16:28:35 2006
@@ -217,6 +217,199 @@
return &SUnits.back();
}
+/// BuildSchedUnits - Build SUnits from the selection dag that we are input.
+/// This SUnit graph is similar to the SelectionDAG, but represents flagged
+/// together nodes with a single SUnit.
+void ScheduleDAGList::BuildSchedUnits() {
+ // Reserve entries in the vector for each of the SUnits we are creating.
This
+ // ensure that reallocation of the vector won't happen, so SUnit*'s won't get
+ // invalidated.
+ SUnits.reserve(std::distance(DAG.allnodes_begin(), DAG.allnodes_end()));
+
+ const InstrItineraryData &InstrItins = TM.getInstrItineraryData();
+
+ for (SelectionDAG::allnodes_iterator NI = DAG.allnodes_begin(),
+ E = DAG.allnodes_end(); NI != E; ++NI) {
+if (isPassiveNode(NI)) // Leaf node, e.g. a TargetImmediate.
+ continue;
+
+// If this node has already been processed, stop now.
+if (SUnitMap[NI]) continue;
+
+SUnit *NodeSUnit = NewSUnit(NI);
+
+// See if anything is flagged to this node, if so, add them to flagged
+// nodes. Nodes can have at most one flag input and one flag output.
Flags
+// are required the be the last operand and result of a node.
+
+// Scan up, adding flagged preds to FlaggedNodes.
+SDNode *N = NI;
+while (N->getNumOperands() &&
+ N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Flag) {
+ N = N->getOperand(N->getNumOperands()-1).Val;
+ NodeSUnit->FlaggedNodes.push_back(N);
+ SUnitMap[N] = NodeSUnit;
+}
+
+// Scan down, adding this node and any flagged succs to FlaggedNodes if
they
+// have a user of the flag operand.
+N = NI;
+while (N->getValueType(N->getNumValues()-1) == MVT::Flag) {
+ SDOperand FlagVal(N, N->getNumValues()-1);
+
+ // There are either zero or one users of the Flag result.
+ bool HasFlagUse = false;
+ for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end();
+ UI != E; ++UI)
+if (FlagVal.isOperand(*UI)) {
+ HasFlagUse = true;
+ NodeSUnit->FlaggedNodes.push_back(N);
+ SUnitMap[N] = NodeSUnit;
+ N = *UI;
+ break;
+}
+ if (!HasFlagUse) break;
+}
+
+// Now all flagged nodes are in FlaggedNodes and N is the bottom-most node.
+// Update the SUnit
+NodeSUnit->Node = N;
+SUnitMap[N] = NodeSUnit;
+
+// Compute the latency for the node. We use the sum of the latencies for
+// all nodes flagged together into this SUnit.
+if (InstrItins.isEmpty()) {
+ // No latency information.
+ NodeSUnit->Latency = 1;
+} else {
+ NodeSUnit->Latency = 0;
+ if (N->isTargetOpcode()) {
+unsigned SchedClass = TII->getSchedClass(N->getTargetOpcode());
+InstrStage *S = InstrItins.begin(SchedClass);
+InstrStage *E = InstrItins.end(SchedClass);
+for (; S != E; ++S)
+ NodeSUnit->Latency += S->Cycles;
+ }
+ for (unsigned i = 0, e = NodeSUnit->FlaggedNodes.size(); i != e; ++i) {
+SDNode *FNode = NodeSUnit->FlaggedNodes[i];
+if (FNode->isTargetOpcode()) {
+ unsigned SchedClass = TII->getSchedClass(FNode->getTargetOpcode());
+ InstrStage *S = InstrItins.begin(SchedClass);
+ InstrStage *E = InstrItins.end(SchedClass);
+ for (; S != E; ++S)
+NodeSUnit->Latency += S->Cycles;
+}
+ }
+}
+ }
+
+ // Pass 2: add the preds, succs, etc.
+ for (unsigned su = 0, e = SUnits.size(); su != e; ++su) {
+SUnit *SU = &SUnits[su];
+SDNode *MainNode = SU->Node;
+
+if (MainNode->isTargetOpcode() &&
+TII->isTwoAddrInstr(MainNode->getTargetOpcode()))
+ SU->isTwoAddress = true;
+
+// Find all predecessors and successors of the group.
+// Temporarily add N to make code simpler.
+SU->FlaggedNodes.push_back(MainNode);
+
+for (unsigned n = 0, e = SU->FlaggedNodes.size(); n != e; ++n) {
+ SDNode *N = SU->FlaggedNodes[n];
+
+ for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
+SDNode *OpN = N->getOperand(i).Val;
+if (isPassiveNode(OpN)) continue; // Not schedule
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.41 -> 1.42
---
Log message:
merge preds/chainpreds -> preds set
merge succs/chainsuccs -> succs set
This has no functionality change, simplifies the code, and reduces the size
of sunits.
---
Diffs of the changes: (+63 -95)
ScheduleDAGList.cpp | 158
1 files changed, 63 insertions(+), 95 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.41
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.42
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.41 Fri Mar 10
01:42:02 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Sat Mar 11 16:24:20 2006
@@ -41,10 +41,12 @@
struct SUnit {
SDNode *Node; // Representative node.
std::vector FlaggedNodes; // All nodes flagged to Node.
-std::set Preds; // All real predecessors.
-std::set ChainPreds;// All chain predecessors.
-std::set Succs; // All real successors.
-std::set ChainSuccs;// All chain successors.
+
+// Preds/Succs - The SUnits before/after us in the graph. The boolean
value
+// is true if the edge is a token chain edge, false if it is a value edge.
+std::set > Preds; // All sunit predecessors.
+std::set > Succs; // All sunit successors.
+
short NumPredsLeft; // # of preds not scheduled.
short NumSuccsLeft; // # of succs not scheduled.
short NumChainPredsLeft;// # of chain preds not scheduled.
@@ -93,34 +95,24 @@
if (Preds.size() != 0) {
std::cerr << " Predecessors:\n";
-for (std::set::const_iterator I = Preds.begin(),
+for (std::set >::const_iterator I = Preds.begin(),
E = Preds.end(); I != E; ++I) {
- std::cerr << "";
- (*I)->dump(G);
-}
- }
- if (ChainPreds.size() != 0) {
-std::cerr << " Chained Preds:\n";
-for (std::set::const_iterator I = ChainPreds.begin(),
- E = ChainPreds.end(); I != E; ++I) {
- std::cerr << "";
- (*I)->dump(G);
+ if (I->second)
+std::cerr << " ch ";
+ else
+std::cerr << " val ";
+ I->first->dump(G);
}
}
if (Succs.size() != 0) {
std::cerr << " Successors:\n";
-for (std::set::const_iterator I = Succs.begin(),
+for (std::set >::const_iterator I = Succs.begin(),
E = Succs.end(); I != E; ++I) {
- std::cerr << "";
- (*I)->dump(G);
-}
- }
- if (ChainSuccs.size() != 0) {
-std::cerr << " Chained succs:\n";
-for (std::set::const_iterator I = ChainSuccs.begin(),
- E = ChainSuccs.end(); I != E; ++I) {
- std::cerr << "";
- (*I)->dump(G);
+ if (I->second)
+std::cerr << " ch ";
+ else
+std::cerr << " val ";
+ I->first->dump(G);
}
}
std::cerr << "\n";
@@ -205,8 +197,8 @@
private:
SUnit *NewSUnit(SDNode *N);
- void ReleasePred(SUnit *PredSU, bool isChain = false);
- void ReleaseSucc(SUnit *SuccSU, bool isChain = false);
+ void ReleasePred(SUnit *PredSU, bool isChain);
+ void ReleaseSucc(SUnit *SuccSU, bool isChain);
void ScheduleNodeBottomUp(SUnit *SU);
void ScheduleNodeTopDown(SUnit *SU);
void ListScheduleTopDown();
@@ -296,15 +288,12 @@
Sequence.push_back(SU);
// Bottom up: release predecessors
- for (std::set::iterator I1 = SU->Preds.begin(),
- E1 = SU->Preds.end(); I1 != E1; ++I1) {
-ReleasePred(*I1);
-SU->NumPredsLeft--;
- }
- for (std::set::iterator I2 = SU->ChainPreds.begin(),
- E2 = SU->ChainPreds.end(); I2 != E2; ++I2)
-ReleasePred(*I2, true);
-
+ for (std::set >::iterator I = SU->Preds.begin(),
+ E = SU->Preds.end(); I != E; ++I) {
+ReleasePred(I->first, I->second);
+if (!I->second)
+ SU->NumPredsLeft--;
+ }
CurrCycle++;
}
@@ -318,15 +307,12 @@
Sequence.push_back(SU);
// Bottom up: release successors.
- for (std::set::iterator I1 = SU->Succs.begin(),
- E1 = SU->Succs.end(); I1 != E1; ++I1) {
-ReleaseSucc(*I1);
-SU->NumSuccsLeft--;
- }
- for (std::set::iterator I2 = SU->ChainSuccs.begin(),
- E2 = SU->ChainSuccs.end(); I2 != E2; ++I2)
-ReleaseSucc(*I2, true);
-
+ for (std::set >::iterator I = SU->Succs.begin(),
+ E = SU->Succs.end(); I != E; ++I) {
+ReleaseSucc(I->first, I->second);
+if (!I->second)
+ SU->NumSuccsLeft--;
+ }
CurrCycle++;
}
@@ -399,8 +385,7 @@
// All leaves to Available queue.
for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
// It is available if it has no predecessors.
-if ((SUnits[i].Preds.size() + SUnits[i].ChainPreds.size()) == 0 &&
-&SUnits[i] != Entry)
+if (SUnits[i].Preds.size() == 0 && &SUnits[i] != Entry)
PriorityQueue->push(&SUnits[i]);
}
@@ -586,26 +571
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG: ScheduleDAGList.cpp updated: 1.37 -> 1.38 --- Log message: no need to build groups anymore --- Diffs of the changes: (+0 -2) ScheduleDAGList.cpp |2 -- 1 files changed, 2 deletions(-) Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.37 llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.38 --- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.37 Fri Mar 10 01:13:32 2006 +++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Fri Mar 10 01:15:58 2006 @@ -642,8 +642,6 @@ // Set up minimum info for scheduling PrepareNodeInfo(); - // Construct node groups for flagged nodes - IdentifyGroups(); // Build scheduling units. BuildSchedUnits(); ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.36 -> 1.37
---
Log message:
Create SUnits directly from the SelectionDAG.
---
Diffs of the changes: (+87 -87)
ScheduleDAGList.cpp | 174 ++--
1 files changed, 87 insertions(+), 87 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.36
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.37
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.36 Fri Mar 10
00:34:51 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Fri Mar 10 01:13:32 2006
@@ -482,128 +482,128 @@
// Reserve entries in the vector for each of the SUnits we are creating.
This
// ensure that reallocation of the vector won't happen, so SUnit*'s won't get
// invalidated.
- SUnits.reserve(NodeCount);
+ SUnits.reserve(std::distance(DAG.allnodes_begin(), DAG.allnodes_end()));
const InstrItineraryData &InstrItins = TM.getInstrItineraryData();
- // Pass 1: create the SUnit's.
- for (unsigned i = 0, NC = NodeCount; i < NC; i++) {
-NodeInfo *NI = &Info[i];
-SDNode *N = NI->Node;
-if (isPassiveNode(N))
+ for (SelectionDAG::allnodes_iterator NI = DAG.allnodes_begin(),
+ E = DAG.allnodes_end(); NI != E; ++NI) {
+if (isPassiveNode(NI)) // Leaf node, e.g. a TargetImmediate.
continue;
+
+// If this node has already been processed, stop now.
+if (SUnitMap[NI]) continue;
+
+SUnit *NodeSUnit = NewSUnit(NI);
-SUnit *SU;
-if (NI->isInGroup()) {
- if (NI != NI->Group->getBottom()) // Bottom up, so only look at bottom
-continue;// node of the NodeGroup
-
- SU = NewSUnit(N);
- // Find the flagged nodes.
- SDOperand FlagOp = N->getOperand(N->getNumOperands() - 1);
- SDNode*Flag = FlagOp.Val;
- unsigned ResNo = FlagOp.ResNo;
- while (Flag->getValueType(ResNo) == MVT::Flag) {
-NodeInfo *FNI = getNI(Flag);
-assert(FNI->Group == NI->Group);
-SU->FlaggedNodes.insert(SU->FlaggedNodes.begin(), Flag);
-SUnitMap[Flag] = SU;
-
-FlagOp = Flag->getOperand(Flag->getNumOperands() - 1);
-Flag = FlagOp.Val;
-ResNo = FlagOp.ResNo;
- }
-} else {
- SU = NewSUnit(N);
+// See if anything is flagged to this node, if so, add them to flagged
+// nodes. Nodes can have at most one flag input and one flag output.
Flags
+// are required the be the last operand and result of a node.
+
+// Scan up, adding flagged preds to FlaggedNodes.
+SDNode *N = NI;
+while (N->getNumOperands() &&
+ N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Flag) {
+ N = N->getOperand(N->getNumOperands()-1).Val;
+ NodeSUnit->FlaggedNodes.push_back(N);
+ SUnitMap[N] = NodeSUnit;
+}
+
+// Scan down, adding this node and any flagged succs to FlaggedNodes if
they
+// have a user of the flag operand.
+N = NI;
+while (N->getValueType(N->getNumValues()-1) == MVT::Flag) {
+ SDOperand FlagVal(N, N->getNumValues()-1);
+
+ // There are either zero or one users of the Flag result.
+ bool HasFlagUse = false;
+ for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end();
+ UI != E; ++UI)
+if (FlagVal.isOperand(*UI)) {
+ HasFlagUse = true;
+ NodeSUnit->FlaggedNodes.push_back(N);
+ SUnitMap[N] = NodeSUnit;
+ N = *UI;
+ break;
+}
+ if (!HasFlagUse) break;
}
-SUnitMap[N] = SU;
-
+
+// Now all flagged nodes are in FlaggedNodes and N is the bottom-most node.
+// Update the SUnit
+NodeSUnit->Node = N;
+SUnitMap[N] = NodeSUnit;
+
// Compute the latency for the node. We use the sum of the latencies for
// all nodes flagged together into this SUnit.
if (InstrItins.isEmpty()) {
// No latency information.
- SU->Latency = 1;
+ NodeSUnit->Latency = 1;
} else {
- SU->Latency = 0;
+ NodeSUnit->Latency = 0;
if (N->isTargetOpcode()) {
unsigned SchedClass = TII->getSchedClass(N->getTargetOpcode());
InstrStage *S = InstrItins.begin(SchedClass);
InstrStage *E = InstrItins.end(SchedClass);
for (; S != E; ++S)
- SU->Latency += S->Cycles;
+ NodeSUnit->Latency += S->Cycles;
}
- for (unsigned i = 0, e = SU->FlaggedNodes.size(); i != e; ++i) {
-SDNode *FNode = SU->FlaggedNodes[i];
+ for (unsigned i = 0, e = NodeSUnit->FlaggedNodes.size(); i != e; ++i) {
+SDNode *FNode = NodeSUnit->FlaggedNodes[i];
if (FNode->isTargetOpcode()) {
unsigned SchedClass = TII->getSchedClass(FNode->getTargetOpcode());
InstrStage *S = InstrItins.begin(SchedClass);
InstrStage *E = InstrItins.end(SchedClass);
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.34 -> 1.35
---
Log message:
Teach the latency scheduler some new tricks. In particular, to break ties,
keep track of a sense of "mobility", i.e. how many other nodes scheduling one
node will free up. For something like this:
float testadd(float *X, float *Y, float *Z, float *W, float *V) {
return (*X+*Y)*(*Z+*W)+*V;
}
For example, this makes us schedule *X then *Y, not *X then *Z. The former
allows us to issue the add, the later only lets us issue other loads.
This turns the above code from this:
_testadd:
lfs f0, 0(r3)
lfs f1, 0(r6)
lfs f2, 0(r4)
lfs f3, 0(r5)
fadds f0, f0, f2
fadds f1, f3, f1
lfs f2, 0(r7)
fmadds f1, f0, f1, f2
blr
into this:
_testadd:
lfs f0, 0(r6)
lfs f1, 0(r5)
fadds f0, f1, f0
lfs f1, 0(r4)
lfs f2, 0(r3)
fadds f1, f2, f1
lfs f2, 0(r7)
fmadds f1, f1, f0, f2
blr
---
Diffs of the changes: (+157 -10)
ScheduleDAGList.cpp | 167
1 files changed, 157 insertions(+), 10 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.34
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.35
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.34 Thu Mar 9
22:32:49 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Thu Mar 9 23:51:05 2006
@@ -51,6 +51,8 @@
short NumChainSuccsLeft;// # of chain succs not scheduled.
bool isTwoAddress : 1; // Is a two-address instruction.
bool isDefNUseOperand : 1; // Is a def&use operand.
+bool isAvailable : 1; // True once available.
+bool isScheduled : 1; // True once scheduled.
unsigned short Latency; // Node latency.
unsigned CycleBound;// Upper/lower cycle to be scheduled
at.
unsigned NodeNum; // Entry # of node in the node vector.
@@ -59,6 +61,7 @@
: Node(node), NumPredsLeft(0), NumSuccsLeft(0),
NumChainPredsLeft(0), NumChainSuccsLeft(0),
isTwoAddress(false), isDefNUseOperand(false),
+ isAvailable(false), isScheduled(false),
Latency(0), CycleBound(0), NodeNum(nodenum) {}
void dump(const SelectionDAG *G) const;
@@ -247,8 +250,10 @@
if ((PredSU->NumSuccsLeft + PredSU->NumChainSuccsLeft) == 0) {
// EntryToken has to go last! Special case it here.
-if (PredSU->Node->getOpcode() != ISD::EntryToken)
+if (PredSU->Node->getOpcode() != ISD::EntryToken) {
+ PredSU->isAvailable = true;
PriorityQueue->push(PredSU);
+}
}
}
@@ -275,8 +280,10 @@
}
#endif
- if ((SuccSU->NumPredsLeft + SuccSU->NumChainPredsLeft) == 0)
+ if ((SuccSU->NumPredsLeft + SuccSU->NumChainPredsLeft) == 0) {
+SuccSU->isAvailable = true;
PriorityQueue->push(SuccSU);
+ }
}
/// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending
@@ -350,8 +357,9 @@
PriorityQueue->push_all(NotReady);
NotReady.clear();
-PriorityQueue->ScheduledNode(CurrNode);
ScheduleNodeBottomUp(CurrNode);
+CurrNode->isScheduled = true;
+PriorityQueue->ScheduledNode(CurrNode);
}
// Add entry node last
@@ -432,9 +440,10 @@
// If we found a node to schedule, do it now.
if (FoundNode) {
- PriorityQueue->ScheduledNode(FoundNode);
ScheduleNodeTopDown(FoundNode);
HazardRec->EmitInstruction(FoundNode->Node);
+ FoundNode->isScheduled = true;
+ PriorityQueue->ScheduledNode(FoundNode);
} else if (!HasNoopHazards) {
// Otherwise, we have a pipeline stall, but no other problem, just
advance
// the current cycle and try again.
@@ -827,7 +836,13 @@
// Latencies - The latency (max of latency from this node to the bb exit)
// for each node.
std::vector Latencies;
-
+
+/// NumNodesSolelyBlocking - This vector contains, for every node in the
+/// Queue, the number of nodes that the node is the sole unscheduled
+/// predecessor for. This is used as a tie-breaker heuristic for better
+/// mobility.
+std::vector NumNodesSolelyBlocking;
+
std::priority_queue, latency_sort> Queue;
public:
LatencyPriorityQueue() : Queue(latency_sort(this)) {
@@ -848,14 +863,21 @@
return Latencies[NodeNum];
}
+unsigned getNumSolelyBlockNodes(unsigned NodeNum) const {
+ assert(NodeNum < NumNodesSolelyBlocking.size());
+ return NumNodesSolelyBlocking[NodeNum];
+}
+
bool empty() const { return Queue.empty(); }
-void push(SUnit *U) {
- Queue.push(U);
+virtual void push(SUnit *U) {
+ push_impl(U);
}
+void push_impl(SUnit *U);
+
void push_all(const std::vector &Nodes) {
for (unsigned i
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.33 -> 1.34
---
Log message:
add an aggregate method for reinserting scheduled nodes, add a callback for
priority impls that want to be notified when a node is scheduled
---
Diffs of the changes: (+23 -8)
ScheduleDAGList.cpp | 31 +++
1 files changed, 23 insertions(+), 8 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.33
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.34
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.33 Thu Mar 9
21:57:45 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Thu Mar 9 22:32:49 2006
@@ -141,7 +141,14 @@
virtual bool empty() const = 0;
virtual void push(SUnit *U) = 0;
+
+ virtual void push_all(const std::vector &Nodes) = 0;
virtual SUnit *pop() = 0;
+
+ /// ScheduledNode - As each node is scheduled, this method is invoked. This
+ /// allows the priority function to adjust the priority of node that have
+ /// already been emitted.
+ virtual void ScheduledNode(SUnit *Node) {}
};
}
@@ -340,11 +347,10 @@
}
// Add the nodes that aren't ready back onto the available list.
-while (!NotReady.empty()) {
- PriorityQueue->push(NotReady.back());
- NotReady.pop_back();
-}
+PriorityQueue->push_all(NotReady);
+NotReady.clear();
+PriorityQueue->ScheduledNode(CurrNode);
ScheduleNodeBottomUp(CurrNode);
}
@@ -421,13 +427,12 @@
} while (!PriorityQueue->empty());
// Add the nodes that aren't ready back onto the available list.
-while (!NotReady.empty()) {
- PriorityQueue->push(NotReady.back());
- NotReady.pop_back();
-}
+PriorityQueue->push_all(NotReady);
+NotReady.clear();
// If we found a node to schedule, do it now.
if (FoundNode) {
+ PriorityQueue->ScheduledNode(FoundNode);
ScheduleNodeTopDown(FoundNode);
HazardRec->EmitInstruction(FoundNode->Node);
} else if (!HasNoopHazards) {
@@ -700,6 +705,11 @@
void push(SUnit *U) {
Queue.push(U);
}
+void push_all(const std::vector &Nodes) {
+ for (unsigned i = 0, e = Nodes.size(); i != e; ++i)
+Queue.push(Nodes[i]);
+}
+
SUnit *pop() {
SUnit *V = Queue.top();
Queue.pop();
@@ -843,6 +853,11 @@
void push(SUnit *U) {
Queue.push(U);
}
+void push_all(const std::vector &Nodes) {
+ for (unsigned i = 0, e = Nodes.size(); i != e; ++i)
+Queue.push(Nodes[i]);
+}
+
SUnit *pop() {
SUnit *V = Queue.top();
Queue.pop();
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.32 -> 1.33
---
Log message:
Fix VC++ build breakage.
---
Diffs of the changes: (+3 -3)
ScheduleDAGList.cpp |6 +++---
1 files changed, 3 insertions(+), 3 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.32
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.33
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.32 Thu Mar 9
11:31:22 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Thu Mar 9 21:57:45 2006
@@ -761,7 +761,7 @@
SethiUllmanNumber = 1;
} else {
int Extra = 0;
-for (std::set::iterator I = SU->Preds.begin(),
+for (std::set::const_iterator I = SU->Preds.begin(),
E = SU->Preds.end(); I != E; ++I) {
SUnit *PredSU = *I;
int PredSethiUllman = CalcNodePriority(PredSU);
@@ -870,11 +870,11 @@
return Latency;
int MaxSuccLatency = 0;
- for (std::set::iterator I = SU.Succs.begin(),
+ for (std::set::const_iterator I = SU.Succs.begin(),
E = SU.Succs.end(); I != E; ++I)
MaxSuccLatency = std::max(MaxSuccLatency, CalcLatency(**I));
- for (std::set::iterator I = SU.ChainSuccs.begin(),
+ for (std::set::const_iterator I = SU.ChainSuccs.begin(),
E = SU.ChainSuccs.end(); I != E; ++I)
MaxSuccLatency = std::max(MaxSuccLatency, CalcLatency(**I));
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.31 -> 1.32
---
Log message:
remove temporary option
---
Diffs of the changes: (+1 -3)
ScheduleDAGList.cpp |4 +---
1 files changed, 1 insertion(+), 3 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.31
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.32
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.31 Thu Mar 9
01:39:25 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Thu Mar 9 11:31:22 2006
@@ -33,8 +33,6 @@
using namespace llvm;
namespace {
- // FIXME: UseLatencies is temporary.
- cl::opt UseLatencies("use-sched-latencies");
Statistic<> NumNoops ("scheduler", "Number of noops inserted");
Statistic<> NumStalls("scheduler", "Number of pipeline stalls");
@@ -508,7 +506,7 @@
// Compute the latency for the node. We use the sum of the latencies for
// all nodes flagged together into this SUnit.
-if (InstrItins.isEmpty() || !UseLatencies) {
+if (InstrItins.isEmpty()) {
// No latency information.
SU->Latency = 1;
} else {
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.29 -> 1.30
---
Log message:
switch the t-d scheduler to use a really dumb and trivial critical path
latency priority function.
---
Diffs of the changes: (+104 -1)
ScheduleDAGList.cpp | 105 +++-
1 files changed, 104 insertions(+), 1 deletion(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.29
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.30
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.29 Thu Mar 9
01:15:18 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Thu Mar 9 01:38:27 2006
@@ -791,6 +791,109 @@
CalcNodePriority(&(*SUnits)[i]);
}
+//===--===//
+//LatencyPriorityQueue Implementation
+//===--===//
+//
+// This is a SchedulingPriorityQueue that schedules using latency information
to
+// reduce the length of the critical path through the basic block.
+//
+namespace {
+ class LatencyPriorityQueue;
+
+ /// Sorting functions for the Available queue.
+ struct latency_sort : public std::binary_function {
+LatencyPriorityQueue *PQ;
+latency_sort(LatencyPriorityQueue *pq) : PQ(pq) {}
+latency_sort(const latency_sort &RHS) : PQ(RHS.PQ) {}
+
+bool operator()(const SUnit* left, const SUnit* right) const;
+ };
+} // end anonymous namespace
+
+namespace {
+ class LatencyPriorityQueue : public SchedulingPriorityQueue {
+// SUnits - The SUnits for the current graph.
+const std::vector *SUnits;
+
+// Latencies - The latency (max of latency from this node to the bb exit)
+// for each node.
+std::vector Latencies;
+
+std::priority_queue, latency_sort> Queue;
+public:
+LatencyPriorityQueue() : Queue(latency_sort(this)) {
+}
+
+void initNodes(const std::vector &sunits) {
+ SUnits = &sunits;
+ // Calculate node priorities.
+ CalculatePriorities();
+}
+void releaseState() {
+ SUnits = 0;
+ Latencies.clear();
+}
+
+unsigned getLatency(unsigned NodeNum) const {
+ assert(NodeNum < Latencies.size());
+ return Latencies[NodeNum];
+}
+
+bool empty() const { return Queue.empty(); }
+
+void push(SUnit *U) {
+ Queue.push(U);
+}
+SUnit *pop() {
+ SUnit *V = Queue.top();
+ Queue.pop();
+
+ std::cerr << "Got node. Latency: " << getLatency(V->NodeNum)
+<< " \n";
+ return V;
+}
+private:
+void CalculatePriorities();
+int CalcLatency(const SUnit &SU);
+ };
+}
+
+bool latency_sort::operator()(const SUnit *LHS, const SUnit *RHS) const {
+ unsigned LHSNum = LHS->NodeNum;
+ unsigned RHSNum = RHS->NodeNum;
+
+ return PQ->getLatency(LHSNum) < PQ->getLatency(RHSNum);
+}
+
+
+/// CalcNodePriority - Calculate the maximal path from the node to the exit.
+///
+int LatencyPriorityQueue::CalcLatency(const SUnit &SU) {
+ int &Latency = Latencies[SU.NodeNum];
+ if (Latency != -1)
+return Latency;
+
+ int MaxSuccLatency = 0;
+ for (std::set::iterator I = SU.Succs.begin(),
+ E = SU.Succs.end(); I != E; ++I)
+MaxSuccLatency = std::max(MaxSuccLatency, CalcLatency(**I));
+
+ for (std::set::iterator I = SU.ChainSuccs.begin(),
+ E = SU.ChainSuccs.end(); I != E; ++I)
+MaxSuccLatency = std::max(MaxSuccLatency, CalcLatency(**I));
+
+ return Latency = MaxSuccLatency + SU.Latency;
+}
+
+/// CalculatePriorities - Calculate priorities of all scheduling units.
+void LatencyPriorityQueue::CalculatePriorities() {
+ Latencies.assign(SUnits->size(), -1);
+
+ for (unsigned i = 0, e = SUnits->size(); i != e; ++i)
+CalcLatency((*SUnits)[i]);
+}
+
//===--===//
// Public Constructor Functions
@@ -809,6 +912,6 @@
MachineBasicBlock *BB,
HazardRecognizer *HR) {
return new ScheduleDAGList(DAG, BB, DAG.getTarget(), false,
- new RegReductionPriorityQueue(),
+ new LatencyPriorityQueue(),
HR);
}
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.30 -> 1.31
---
Log message:
yes yes, enabled debug output is bad
---
Diffs of the changes: (+0 -3)
ScheduleDAGList.cpp |3 ---
1 files changed, 3 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.30
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.31
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.30 Thu Mar 9
01:38:27 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Thu Mar 9 01:39:25 2006
@@ -848,9 +848,6 @@
SUnit *pop() {
SUnit *V = Queue.top();
Queue.pop();
-
- std::cerr << "Got node. Latency: " << getLatency(V->NodeNum)
-<< " \n";
return V;
}
private:
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.28 -> 1.29
---
Log message:
Pull latency information for target instructions out of the latency tables. :)
Only enable this with -use-sched-latencies, I'll enable it by default with a
clean nightly tester run tonight.
PPC is the only target that provides latency info currently.
---
Diffs of the changes: (+80 -46)
ScheduleDAGList.cpp | 126 +---
1 files changed, 80 insertions(+), 46 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.28
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.29
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.28 Thu Mar 9
00:48:37 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Thu Mar 9 01:15:18 2006
@@ -29,9 +29,12 @@
#include
#include
#include
+#include "llvm/Support/CommandLine.h"
using namespace llvm;
namespace {
+ // FIXME: UseLatencies is temporary.
+ cl::opt UseLatencies("use-sched-latencies");
Statistic<> NumNoops ("scheduler", "Number of noops inserted");
Statistic<> NumStalls("scheduler", "Number of pipeline stalls");
@@ -60,11 +63,12 @@
isTwoAddress(false), isDefNUseOperand(false),
Latency(0), CycleBound(0), NodeNum(nodenum) {}
-void dump(const SelectionDAG *G, bool All=true) const;
+void dump(const SelectionDAG *G) const;
+void dumpAll(const SelectionDAG *G) const;
};
}
-void SUnit::dump(const SelectionDAG *G, bool All) const {
+void SUnit::dump(const SelectionDAG *G) const {
std::cerr << "SU: ";
Node->dump(G);
std::cerr << "\n";
@@ -75,47 +79,50 @@
std::cerr << "\n";
}
}
+}
- if (All) {
-std::cerr << " # preds left : " << NumPredsLeft << "\n";
-std::cerr << " # succs left : " << NumSuccsLeft << "\n";
-std::cerr << " # chain preds left : " << NumChainPredsLeft << "\n";
-std::cerr << " # chain succs left : " << NumChainSuccsLeft << "\n";
-std::cerr << " Latency: " << Latency << "\n";
-
-if (Preds.size() != 0) {
- std::cerr << " Predecessors:\n";
- for (std::set::const_iterator I = Preds.begin(),
- E = Preds.end(); I != E; ++I) {
-std::cerr << "";
-(*I)->dump(G, false);
- }
+void SUnit::dumpAll(const SelectionDAG *G) const {
+ dump(G);
+
+ std::cerr << " # preds left : " << NumPredsLeft << "\n";
+ std::cerr << " # succs left : " << NumSuccsLeft << "\n";
+ std::cerr << " # chain preds left : " << NumChainPredsLeft << "\n";
+ std::cerr << " # chain succs left : " << NumChainSuccsLeft << "\n";
+ std::cerr << " Latency: " << Latency << "\n";
+
+ if (Preds.size() != 0) {
+std::cerr << " Predecessors:\n";
+for (std::set::const_iterator I = Preds.begin(),
+ E = Preds.end(); I != E; ++I) {
+ std::cerr << "";
+ (*I)->dump(G);
}
-if (ChainPreds.size() != 0) {
- std::cerr << " Chained Preds:\n";
- for (std::set::const_iterator I = ChainPreds.begin(),
- E = ChainPreds.end(); I != E; ++I) {
-std::cerr << "";
-(*I)->dump(G, false);
- }
+ }
+ if (ChainPreds.size() != 0) {
+std::cerr << " Chained Preds:\n";
+for (std::set::const_iterator I = ChainPreds.begin(),
+ E = ChainPreds.end(); I != E; ++I) {
+ std::cerr << "";
+ (*I)->dump(G);
}
-if (Succs.size() != 0) {
- std::cerr << " Successors:\n";
- for (std::set::const_iterator I = Succs.begin(),
- E = Succs.end(); I != E; ++I) {
-std::cerr << "";
-(*I)->dump(G, false);
- }
+ }
+ if (Succs.size() != 0) {
+std::cerr << " Successors:\n";
+for (std::set::const_iterator I = Succs.begin(),
+ E = Succs.end(); I != E; ++I) {
+ std::cerr << "";
+ (*I)->dump(G);
}
-if (ChainSuccs.size() != 0) {
- std::cerr << " Chained succs:\n";
- for (std::set::const_iterator I = ChainSuccs.begin(),
- E = ChainSuccs.end(); I != E; ++I) {
-std::cerr << "";
-(*I)->dump(G, false);
- }
+ }
+ if (ChainSuccs.size() != 0) {
+std::cerr << " Chained succs:\n";
+for (std::set::const_iterator I = ChainSuccs.begin(),
+ E = ChainSuccs.end(); I != E; ++I) {
+ std::cerr << "";
+ (*I)->dump(G);
}
}
+ std::cerr << "\n";
}
//===--===//
@@ -186,7 +193,7 @@
void Schedule();
- void dump() const;
+ void dumpSchedule() const;
private:
SUnit *NewSUnit(SDNode *N);
@@ -272,7 +279,7 @@
/// the Available queue.
void ScheduleDAGList::ScheduleNodeBottomUp(SUnit *SU) {
DEBUG(std::cerr << "*** Scheduling: ");
- DEBUG(SU->dump(&DAG, false));
+ DEBUG(SU->dump(&DAG));
Sequence.push_back(SU);
@@ -294,7 +301,7 @@
///
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.26 -> 1.27
---
Log message:
add some comments
---
Diffs of the changes: (+13 -8)
ScheduleDAGList.cpp | 21 +
1 files changed, 13 insertions(+), 8 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.26
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.27
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.26 Thu Mar 9
00:35:14 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Thu Mar 9 00:37:29 2006
@@ -119,13 +119,14 @@
}
//===--===//
-// SchedulingPriorityQueue - This interface is used to plug different
-// priorities computation algorithms into the list scheduler. It implements
the
-// interface of a standard priority queue, where nodes are inserted in
arbitrary
-// order and returned in priority order. The computation of the priority and
-// the representation of the queue are totally up to the implementation to
-// decide.
-//
+/// SchedulingPriorityQueue - This interface is used to plug different
+/// priorities computation algorithms into the list scheduler. It implements
the
+/// interface of a standard priority queue, where nodes are inserted in
+/// arbitrary order and returned in priority order. The computation of the
+/// priority and the representation of the queue are totally up to the
+/// implementation to decide.
+///
+namespace {
class SchedulingPriorityQueue {
public:
virtual ~SchedulingPriorityQueue() {}
@@ -137,11 +138,15 @@
virtual void push(SUnit *U) = 0;
virtual SUnit *pop() = 0;
};
+}
namespace {
-/// ScheduleDAGList - List scheduler.
+//===--===//
+/// ScheduleDAGList - The actual list scheduler implementation. This supports
+/// both top-down and bottom-up scheduling.
+///
class ScheduleDAGList : public ScheduleDAG {
private:
// SDNode to SUnit mapping (many to one).
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.27 -> 1.28
---
Log message:
PriorityQueue is an instance var, use it.
---
Diffs of the changes: (+33 -39)
ScheduleDAGList.cpp | 72 +++-
1 files changed, 33 insertions(+), 39 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.27
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.28
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.27 Thu Mar 9
00:37:29 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Thu Mar 9 00:48:37 2006
@@ -190,14 +190,12 @@
private:
SUnit *NewSUnit(SDNode *N);
- void ReleasePred(SchedulingPriorityQueue &Avail,
- SUnit *PredSU, bool isChain = false);
- void ReleaseSucc(SchedulingPriorityQueue &Avail,
- SUnit *SuccSU, bool isChain = false);
- void ScheduleNodeBottomUp(SchedulingPriorityQueue &Avail, SUnit *SU);
- void ScheduleNodeTopDown(SchedulingPriorityQueue &Avail, SUnit *SU);
- void ListScheduleTopDown(SchedulingPriorityQueue &Available);
- void ListScheduleBottomUp(SchedulingPriorityQueue &Available);
+ void ReleasePred(SUnit *PredSU, bool isChain = false);
+ void ReleaseSucc(SUnit *SuccSU, bool isChain = false);
+ void ScheduleNodeBottomUp(SUnit *SU);
+ void ScheduleNodeTopDown(SUnit *SU);
+ void ListScheduleTopDown();
+ void ListScheduleBottomUp();
void BuildSchedUnits();
void EmitSchedule();
};
@@ -214,8 +212,7 @@
/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to
/// the Available queue is the count reaches zero. Also update its cycle bound.
-void ScheduleDAGList::ReleasePred(SchedulingPriorityQueue &Available,
- SUnit *PredSU, bool isChain) {
+void ScheduleDAGList::ReleasePred(SUnit *PredSU, bool isChain) {
// FIXME: the distance between two nodes is not always == the predecessor's
// latency. For example, the reader can very well read the register written
// by the predecessor later than the issue cycle. It also depends on the
@@ -239,14 +236,13 @@
if ((PredSU->NumSuccsLeft + PredSU->NumChainSuccsLeft) == 0) {
// EntryToken has to go last! Special case it here.
if (PredSU->Node->getOpcode() != ISD::EntryToken)
- Available.push(PredSU);
+ PriorityQueue->push(PredSU);
}
}
/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
/// the Available queue is the count reaches zero. Also update its cycle bound.
-void ScheduleDAGList::ReleaseSucc(SchedulingPriorityQueue &Available,
- SUnit *SuccSU, bool isChain) {
+void ScheduleDAGList::ReleaseSucc(SUnit *SuccSU, bool isChain) {
// FIXME: the distance between two nodes is not always == the predecessor's
// latency. For example, the reader can very well read the register written
// by the predecessor later than the issue cycle. It also depends on the
@@ -268,14 +264,13 @@
#endif
if ((SuccSU->NumPredsLeft + SuccSU->NumChainPredsLeft) == 0)
-Available.push(SuccSU);
+PriorityQueue->push(SuccSU);
}
/// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending
/// count of its predecessors. If a predecessor pending count is zero, add it
to
/// the Available queue.
-void ScheduleDAGList::ScheduleNodeBottomUp(SchedulingPriorityQueue &Available,
- SUnit *SU) {
+void ScheduleDAGList::ScheduleNodeBottomUp(SUnit *SU) {
DEBUG(std::cerr << "*** Scheduling: ");
DEBUG(SU->dump(&DAG, false));
@@ -284,12 +279,12 @@
// Bottom up: release predecessors
for (std::set::iterator I1 = SU->Preds.begin(),
E1 = SU->Preds.end(); I1 != E1; ++I1) {
-ReleasePred(Available, *I1);
+ReleasePred(*I1);
SU->NumPredsLeft--;
}
for (std::set::iterator I2 = SU->ChainPreds.begin(),
E2 = SU->ChainPreds.end(); I2 != E2; ++I2)
-ReleasePred(Available, *I2, true);
+ReleasePred(*I2, true);
CurrCycle++;
}
@@ -297,8 +292,7 @@
/// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending
/// count of its successors. If a successor pending count is zero, add it to
/// the Available queue.
-void ScheduleDAGList::ScheduleNodeTopDown(SchedulingPriorityQueue &Available,
- SUnit *SU) {
+void ScheduleDAGList::ScheduleNodeTopDown(SUnit *SU) {
DEBUG(std::cerr << "*** Scheduling: ");
DEBUG(SU->dump(&DAG, false));
@@ -307,12 +301,12 @@
// Bottom up: release successors.
for (std::set::iterator I1 = SU->Succs.begin(),
E1 = SU->Succs.end(); I1 != E1; ++I1) {
-ReleaseSucc(Available, *I1);
+ReleaseSucc(*I1);
SU->NumSuccsLeft--;
}
for (std::set::iterator I2 = SU->ChainSuccs.begin(),
E2 = SU->ChainSuccs.end(); I2 != E2; ++I2)
-ReleaseSucc(Available, *I2, true);
+Re
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.25 -> 1.26
---
Log message:
Refactor the priority mechanism one step further: now that it is a separate
class, sever its implementation from the interface. Now we can provide new
implementations of the same interface (priority computation) without touching
the scheduler itself.
---
Diffs of the changes: (+185 -136)
ScheduleDAGList.cpp | 321 +---
1 files changed, 185 insertions(+), 136 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.25
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.26
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.25 Tue Mar 7
23:18:27 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Thu Mar 9 00:35:14 2006
@@ -118,137 +118,25 @@
}
}
-namespace {
- class SchedulingPriorityQueue;
-
- /// Sorting functions for the Available queue.
- struct ls_rr_sort : public std::binary_function {
-SchedulingPriorityQueue *SPQ;
-ls_rr_sort(SchedulingPriorityQueue *spq) : SPQ(spq) {}
-ls_rr_sort(const ls_rr_sort &RHS) : SPQ(RHS.SPQ) {}
-
-bool operator()(const SUnit* left, const SUnit* right) const;
- };
-} // end anonymous namespace
-
-namespace {
- class SchedulingPriorityQueue {
-// SUnits - The SUnits for the current graph.
-std::vector &SUnits;
-
-// SethiUllmanNumbers - The SethiUllman number for each node.
-std::vector SethiUllmanNumbers;
-
-std::priority_queue, ls_rr_sort> Queue;
- public:
-SchedulingPriorityQueue(std::vector &sunits)
- : SUnits(sunits), Queue(ls_rr_sort(this)) {
- // Calculate node priorities.
- CalculatePriorities();
-}
-
-unsigned getSethiUllmanNumber(unsigned NodeNum) const {
- assert(NodeNum < SethiUllmanNumbers.size());
- return SethiUllmanNumbers[NodeNum];
-}
-
-bool empty() const { return Queue.empty(); }
-
-void push(SUnit *U) {
- Queue.push(U);
-}
-SUnit *pop() {
- SUnit *V = Queue.top();
- Queue.pop();
- return V;
-}
- private:
-void CalculatePriorities();
-int CalcNodePriority(SUnit *SU);
- };
-}
-
-bool ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const {
- unsigned LeftNum = left->NodeNum;
- unsigned RightNum = right->NodeNum;
-
- int LBonus = (int)left ->isDefNUseOperand;
- int RBonus = (int)right->isDefNUseOperand;
-
- // Special tie breaker: if two nodes share a operand, the one that
- // use it as a def&use operand is preferred.
- if (left->isTwoAddress && !right->isTwoAddress) {
-SDNode *DUNode = left->Node->getOperand(0).Val;
-if (DUNode->isOperand(right->Node))
- LBonus++;
- }
- if (!left->isTwoAddress && right->isTwoAddress) {
-SDNode *DUNode = right->Node->getOperand(0).Val;
-if (DUNode->isOperand(left->Node))
- RBonus++;
- }
-
- // Priority1 is just the number of live range genned.
- int LPriority1 = left ->NumPredsLeft - LBonus;
- int RPriority1 = right->NumPredsLeft - RBonus;
- int LPriority2 = SPQ->getSethiUllmanNumber(LeftNum) + LBonus;
- int RPriority2 = SPQ->getSethiUllmanNumber(RightNum) + RBonus;
+//===--===//
+// SchedulingPriorityQueue - This interface is used to plug different
+// priorities computation algorithms into the list scheduler. It implements
the
+// interface of a standard priority queue, where nodes are inserted in
arbitrary
+// order and returned in priority order. The computation of the priority and
+// the representation of the queue are totally up to the implementation to
+// decide.
+//
+class SchedulingPriorityQueue {
+public:
+ virtual ~SchedulingPriorityQueue() {}
- if (LPriority1 > RPriority1)
-return true;
- else if (LPriority1 == RPriority1)
-if (LPriority2 < RPriority2)
- return true;
-else if (LPriority2 == RPriority2)
- if (left->CycleBound > right->CycleBound)
-return true;
+ virtual void initNodes(const std::vector &SUnits) = 0;
+ virtual void releaseState() = 0;
- return false;
-}
-
-
-/// CalcNodePriority - Priority is the Sethi Ullman number.
-/// Smaller number is the higher priority.
-int SchedulingPriorityQueue::CalcNodePriority(SUnit *SU) {
- int &SethiUllmanNumber = SethiUllmanNumbers[SU->NodeNum];
- if (SethiUllmanNumber != INT_MIN)
-return SethiUllmanNumber;
-
- if (SU->Preds.size() == 0) {
-SethiUllmanNumber = 1;
- } else {
-int Extra = 0;
-for (std::set::iterator I = SU->Preds.begin(),
- E = SU->Preds.end(); I != E; ++I) {
- SUnit *PredSU = *I;
- int PredSethiUllman = CalcNodePriority(PredSU);
- if (PredSethiUllman > SethiUllmanNumber) {
-SethiUllmanNumber = PredSethiUllman;
-Extra = 0;
- } else if (PredSethiUllman == SethiUllmanNumber)
-
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.24 -> 1.25
---
Log message:
Split the priority function computation and priority queue management out
of the ScheduleDAGList class into a new SchedulingPriorityQueue class.
---
Diffs of the changes: (+152 -115)
ScheduleDAGList.cpp | 267 +---
1 files changed, 152 insertions(+), 115 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.24
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.25
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.24 Tue Mar 7
22:54:34 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Tue Mar 7 23:18:27 2006
@@ -48,18 +48,17 @@
short NumSuccsLeft; // # of succs not scheduled.
short NumChainPredsLeft;// # of chain preds not scheduled.
short NumChainSuccsLeft;// # of chain succs not scheduled.
-int SethiUllman;// Sethi Ullman number.
bool isTwoAddress : 1; // Is a two-address instruction.
bool isDefNUseOperand : 1; // Is a def&use operand.
unsigned short Latency; // Node latency.
unsigned CycleBound;// Upper/lower cycle to be scheduled
at.
+unsigned NodeNum; // Entry # of node in the node vector.
-SUnit(SDNode *node)
+SUnit(SDNode *node, unsigned nodenum)
: Node(node), NumPredsLeft(0), NumSuccsLeft(0),
NumChainPredsLeft(0), NumChainSuccsLeft(0),
- SethiUllman(INT_MIN),
isTwoAddress(false), isDefNUseOperand(false),
- Latency(0), CycleBound(0) {}
+ Latency(0), CycleBound(0), NodeNum(nodenum) {}
void dump(const SelectionDAG *G, bool All=true) const;
};
@@ -83,7 +82,6 @@
std::cerr << " # chain preds left : " << NumChainPredsLeft << "\n";
std::cerr << " # chain succs left : " << NumChainSuccsLeft << "\n";
std::cerr << " Latency: " << Latency << "\n";
-std::cerr << " SethiUllman: " << SethiUllman << "\n";
if (Preds.size() != 0) {
std::cerr << " Predecessors:\n";
@@ -121,44 +119,137 @@
}
namespace {
-/// Sorting functions for the Available queue.
-struct ls_rr_sort : public std::binary_function {
- bool operator()(const SUnit* left, const SUnit* right) const {
-int LBonus = (int)left ->isDefNUseOperand;
-int RBonus = (int)right->isDefNUseOperand;
-
-// Special tie breaker: if two nodes share a operand, the one that
-// use it as a def&use operand is preferred.
-if (left->isTwoAddress && !right->isTwoAddress) {
- SDNode *DUNode = left->Node->getOperand(0).Val;
- if (DUNode->isOperand(right->Node))
-LBonus++;
-}
-if (!left->isTwoAddress && right->isTwoAddress) {
- SDNode *DUNode = right->Node->getOperand(0).Val;
- if (DUNode->isOperand(left->Node))
-RBonus++;
-}
-
-// Priority1 is just the number of live range genned.
-int LPriority1 = left ->NumPredsLeft - LBonus;
-int RPriority1 = right->NumPredsLeft - RBonus;
-int LPriority2 = left ->SethiUllman + LBonus;
-int RPriority2 = right->SethiUllman + RBonus;
+ class SchedulingPriorityQueue;
+
+ /// Sorting functions for the Available queue.
+ struct ls_rr_sort : public std::binary_function {
+SchedulingPriorityQueue *SPQ;
+ls_rr_sort(SchedulingPriorityQueue *spq) : SPQ(spq) {}
+ls_rr_sort(const ls_rr_sort &RHS) : SPQ(RHS.SPQ) {}
+
+bool operator()(const SUnit* left, const SUnit* right) const;
+ };
+} // end anonymous namespace
-if (LPriority1 > RPriority1)
+namespace {
+ class SchedulingPriorityQueue {
+// SUnits - The SUnits for the current graph.
+std::vector &SUnits;
+
+// SethiUllmanNumbers - The SethiUllman number for each node.
+std::vector SethiUllmanNumbers;
+
+std::priority_queue, ls_rr_sort> Queue;
+ public:
+SchedulingPriorityQueue(std::vector &sunits)
+ : SUnits(sunits), Queue(ls_rr_sort(this)) {
+ // Calculate node priorities.
+ CalculatePriorities();
+}
+
+unsigned getSethiUllmanNumber(unsigned NodeNum) const {
+ assert(NodeNum < SethiUllmanNumbers.size());
+ return SethiUllmanNumbers[NodeNum];
+}
+
+bool empty() const { return Queue.empty(); }
+
+void push(SUnit *U) {
+ Queue.push(U);
+}
+SUnit *pop() {
+ SUnit *V = Queue.top();
+ Queue.pop();
+ return V;
+}
+ private:
+void CalculatePriorities();
+int CalcNodePriority(SUnit *SU);
+ };
+}
+
+bool ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const {
+ unsigned LeftNum = left->NodeNum;
+ unsigned RightNum = right->NodeNum;
+
+ int LBonus = (int)left ->isDefNUseOperand;
+ int RBonus = (int)right->isDefNUseOperand;
+
+ // Special tie breaker: if two nodes share a operand, th
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.22 -> 1.23
---
Log message:
Shrinkify some fields, fit to 80 columns
---
Diffs of the changes: (+11 -11)
ScheduleDAGList.cpp | 22 +++---
1 files changed, 11 insertions(+), 11 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.22
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.23
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.22 Tue Mar 7
22:37:58 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Tue Mar 7 22:41:06 2006
@@ -35,8 +35,8 @@
Statistic<> NumNoops ("scheduler", "Number of noops inserted");
Statistic<> NumStalls("scheduler", "Number of pipeline stalls");
- /// SUnit - Scheduling unit. It's an wrapper around either a single SDNode
or a
- /// group of nodes flagged together.
+ /// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or
+ /// a group of nodes flagged together.
struct SUnit {
SDNode *Node; // Representative node.
std::vector FlaggedNodes; // All nodes flagged to Node.
@@ -44,14 +44,14 @@
std::set ChainPreds;// All chain predecessors.
std::set Succs; // All real successors.
std::set ChainSuccs;// All chain successors.
-int NumPredsLeft; // # of preds not scheduled.
-int NumSuccsLeft; // # of succs not scheduled.
-int NumChainPredsLeft; // # of chain preds not scheduled.
-int NumChainSuccsLeft; // # of chain succs not scheduled.
+short NumPredsLeft; // # of preds not scheduled.
+short NumSuccsLeft; // # of succs not scheduled.
+short NumChainPredsLeft;// # of chain preds not scheduled.
+short NumChainSuccsLeft;// # of chain succs not scheduled.
int SethiUllman;// Sethi Ullman number.
-bool isTwoAddress; // Is a two-address instruction.
-bool isDefNUseOperand; // Is a def&use operand.
-unsigned Latency; // Node latency.
+bool isTwoAddress : 1; // Is a two-address instruction.
+bool isDefNUseOperand : 1; // Is a def&use operand.
+unsigned short Latency; // Node latency.
unsigned CycleBound;// Upper/lower cycle to be scheduled
at.
SUnit *Next;
@@ -247,7 +247,7 @@
// latency. For example, the reader can very well read the register written
// by the predecessor later than the issue cycle. It also depends on the
// interrupt model (drain vs. freeze).
- PredSU->CycleBound = std::max(PredSU->CycleBound, CurrCycle +
PredSU->Latency);
+ PredSU->CycleBound = std::max(PredSU->CycleBound,CurrCycle +
PredSU->Latency);
if (!isChain)
PredSU->NumSuccsLeft--;
@@ -278,7 +278,7 @@
// latency. For example, the reader can very well read the register written
// by the predecessor later than the issue cycle. It also depends on the
// interrupt model (drain vs. freeze).
- SuccSU->CycleBound = std::max(SuccSU->CycleBound, CurrCycle +
SuccSU->Latency);
+ SuccSU->CycleBound = std::max(SuccSU->CycleBound,CurrCycle +
SuccSU->Latency);
if (!isChain)
SuccSU->NumPredsLeft--;
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.23 -> 1.24
---
Log message:
switch from an explicitly managed list of SUnits to a simple vector of sunits
---
Diffs of the changes: (+28 -35)
ScheduleDAGList.cpp | 63 +++-
1 files changed, 28 insertions(+), 35 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.23
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.24
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.23 Tue Mar 7
22:41:06 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Tue Mar 7 22:54:34 2006
@@ -53,14 +53,13 @@
bool isDefNUseOperand : 1; // Is a def&use operand.
unsigned short Latency; // Node latency.
unsigned CycleBound;// Upper/lower cycle to be scheduled
at.
-SUnit *Next;
SUnit(SDNode *node)
: Node(node), NumPredsLeft(0), NumSuccsLeft(0),
NumChainPredsLeft(0), NumChainSuccsLeft(0),
SethiUllman(INT_MIN),
isTwoAddress(false), isDefNUseOperand(false),
- Latency(0), CycleBound(0), Next(NULL) {}
+ Latency(0), CycleBound(0) {}
void dump(const SelectionDAG *G, bool All=true) const;
};
@@ -172,8 +171,9 @@
std::vector Sequence;
// Current scheduling cycle.
unsigned CurrCycle;
- // First and last SUnit created.
- SUnit *HeadSUnit, *TailSUnit;
+
+ // The scheduling units.
+ std::vector SUnits;
/// isBottomUp - This is true if the scheduling problem is bottom-up, false
if
/// it is top-down.
@@ -190,17 +190,10 @@
const TargetMachine &tm, bool isbottomup,
HazardRecognizer *HR)
: ScheduleDAG(listSchedulingBURR, dag, bb, tm),
- CurrCycle(0), HeadSUnit(NULL), TailSUnit(NULL), isBottomUp(isbottomup),
- HazardRec(HR) {
+ CurrCycle(0), isBottomUp(isbottomup), HazardRec(HR) {
}
~ScheduleDAGList() {
-SUnit *SU = HeadSUnit;
-while (SU) {
- SUnit *NextSU = SU->Next;
- delete SU;
- SU = NextSU;
-}
delete HazardRec;
}
@@ -228,15 +221,8 @@
/// NewSUnit - Creates a new SUnit and return a ptr to it.
SUnit *ScheduleDAGList::NewSUnit(SDNode *N) {
- SUnit *CurrSUnit = new SUnit(N);
-
- if (HeadSUnit == NULL)
-HeadSUnit = CurrSUnit;
- if (TailSUnit != NULL)
-TailSUnit->Next = CurrSUnit;
- TailSUnit = CurrSUnit;
-
- return CurrSUnit;
+ SUnits.push_back(N);
+ return &SUnits.back();
}
/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to
@@ -394,11 +380,11 @@
#ifndef NDEBUG
// Verify that all SUnits were scheduled.
bool AnyNotSched = false;
- for (SUnit *SU = HeadSUnit; SU != NULL; SU = SU->Next) {
-if (SU->NumSuccsLeft != 0 || SU->NumChainSuccsLeft != 0) {
+ for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
+if (SUnits[i].NumSuccsLeft != 0 || SUnits[i].NumChainSuccsLeft != 0) {
if (!AnyNotSched)
std::cerr << "*** List scheduling failed! ***\n";
- SU->dump(&DAG);
+ SUnits[i].dump(&DAG);
std::cerr << "has not been scheduled!\n";
AnyNotSched = true;
}
@@ -419,10 +405,11 @@
HazardRec->EmitInstruction(Entry->Node);
// All leaves to Available queue.
- for (SUnit *SU = HeadSUnit; SU != NULL; SU = SU->Next) {
+ for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
// It is available if it has no predecessors.
-if ((SU->Preds.size() + SU->ChainPreds.size()) == 0 && SU != Entry)
- Available.push(SU);
+if ((SUnits[i].Preds.size() + SUnits[i].ChainPreds.size()) == 0 &&
+&SUnits[i] != Entry)
+ Available.push(&SUnits[i]);
}
// While Available queue is not empty, grab the node with the highest
@@ -486,11 +473,11 @@
#ifndef NDEBUG
// Verify that all SUnits were scheduled.
bool AnyNotSched = false;
- for (SUnit *SU = HeadSUnit; SU != NULL; SU = SU->Next) {
-if (SU->NumPredsLeft != 0 || SU->NumChainPredsLeft != 0) {
+ for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
+if (SUnits[i].NumPredsLeft != 0 || SUnits[i].NumChainPredsLeft != 0) {
if (!AnyNotSched)
std::cerr << "*** List scheduling failed! ***\n";
- SU->dump(&DAG);
+ SUnits[i].dump(&DAG);
std::cerr << "has not been scheduled!\n";
AnyNotSched = true;
}
@@ -532,16 +519,21 @@
/// CalculatePriorities - Calculate priorities of all scheduling units.
void ScheduleDAGList::CalculatePriorities() {
- for (SUnit *SU = HeadSUnit; SU != NULL; SU = SU->Next) {
+ for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
// FIXME: assumes uniform latency for now.
-SU->Latency = 1;
-(void)CalcNodePriority(SU);
-DEBUG(SU->dump(&DAG));
+SUnits[i].Latency = 1;
+(void)CalcNodePriority(&SUnits[i]);
+DEBUG(SUnits[i].dump(&DAG));
DEBUG(std::cerr << "\n");
}
}
void Sch
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.19 -> 1.20
---
Log message:
Fix some formatting, when looking for hazards, prefer target nodes over
things like copyfromreg.
---
Diffs of the changes: (+15 -7)
ScheduleDAGList.cpp | 22 +++---
1 files changed, 15 insertions(+), 7 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.19
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.20
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.19 Mon Mar 6
11:58:04 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Mon Mar 6 23:40:43 2006
@@ -435,19 +435,27 @@
bool HasNoopHazards = false;
do {
- SUnit *CurrNode = Available.top();
+ SUnit *CurNode = Available.top();
Available.pop();
- HazardRecognizer::HazardType HT =
-HazardRec.getHazardType(CurrNode->Node);
+
+ // Get the node represented by this SUnit.
+ SDNode *N = CurNode->Node;
+ // If this is a pseudo op, like copyfromreg, look to see if there is a
+ // real target node flagged to it. If so, use the target node.
+ for (unsigned i = 0, e = CurNode->FlaggedNodes.size();
+ N->getOpcode() < ISD::BUILTIN_OP_END && i != e; ++i)
+N = CurNode->FlaggedNodes[i];
+
+ HazardRecognizer::HazardType HT = HazardRec.getHazardType(N);
if (HT == HazardRecognizer::NoHazard) {
-FoundNode = CurrNode;
+FoundNode = CurNode;
break;
}
// Remember if this is a noop hazard.
HasNoopHazards |= HT == HazardRecognizer::NoopHazard;
- NotReady.push_back(CurrNode);
+ NotReady.push_back(CurNode);
} while (!Available.empty());
// Add the nodes that aren't ready back onto the available list.
@@ -463,14 +471,14 @@
} else if (!HasNoopHazards) {
// Otherwise, we have a pipeline stall, but no other problem, just
advance
// the current cycle and try again.
- DEBUG(std::cerr << "*** Advancing cycle, no work to do");
+ DEBUG(std::cerr << "*** Advancing cycle, no work to do\n");
HazardRec.AdvanceCycle();
++NumStalls;
} else {
// Otherwise, we have no instructions to issue and we have instructions
// that will fault if we don't do this right. This is the case for
// processors without pipeline interlocks and other cases.
- DEBUG(std::cerr << "*** Emitting noop");
+ DEBUG(std::cerr << "*** Emitting noop\n");
HazardRec.EmitNoop();
Sequence.push_back(0); // NULL SUnit* -> noop
++NumNoops;
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG: ScheduleDAGList.cpp updated: 1.18 -> 1.19 --- Log message: update file comment --- Diffs of the changes: (+8 -3) ScheduleDAGList.cpp | 11 --- 1 files changed, 8 insertions(+), 3 deletions(-) Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.18 llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.19 --- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.18 Mon Mar 6 01:31:44 2006 +++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Mon Mar 6 11:58:04 2006 @@ -7,9 +7,14 @@ // //===--===// // -// This implements a simple two pass scheduler. The first pass attempts to push -// backward any lengthy instructions and critical paths. The second pass packs -// instructions into semi-optimal time slots. +// This implements bottom-up and top-down list schedulers, using standard +// algorithms. The basic approach uses a priority queue of available nodes to +// schedule. One at a time, nodes are taken from the priority queue (thus in +// priority order), checked for legality to schedule, and emitted if legal. +// +// Nodes may not be legal to schedule either due to structural hazards (e.g. +// pipeline or resource constraints) or because an input to the instruction has +// not completed execution. // //===--===// ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.17 -> 1.18
---
Log message:
Remove some code that doesn't make sense
---
Diffs of the changes: (+5 -12)
ScheduleDAGList.cpp | 17 +
1 files changed, 5 insertions(+), 12 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.17
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.18
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.17 Mon Mar 6
00:08:54 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Mon Mar 6 01:31:44 2006
@@ -120,8 +120,6 @@
/// Sorting functions for the Available queue.
struct ls_rr_sort : public std::binary_function {
bool operator()(const SUnit* left, const SUnit* right) const {
-bool LFloater = (left ->Preds.size() == 0);
-bool RFloater = (right->Preds.size() == 0);
int LBonus = (int)left ->isDefNUseOperand;
int RBonus = (int)right->isDefNUseOperand;
@@ -144,19 +142,14 @@
int LPriority2 = left ->SethiUllman + LBonus;
int RPriority2 = right->SethiUllman + RBonus;
-// Favor floaters (i.e. node with no non-passive predecessors):
-// e.g. MOV32ri.
-if (!LFloater && RFloater)
+if (LPriority1 > RPriority1)
return true;
-else if (LFloater == RFloater)
- if (LPriority1 > RPriority1)
+else if (LPriority1 == RPriority1)
+ if (LPriority2 < RPriority2)
return true;
- else if (LPriority1 == RPriority1)
-if (LPriority2 < RPriority2)
+ else if (LPriority2 == RPriority2)
+if (left->CycleBound > right->CycleBound)
return true;
-else if (LPriority2 == RPriority2)
- if (left->CycleBound > right->CycleBound)
-return true;
return false;
}
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.16 -> 1.17
---
Log message:
Remove SUnit::Priority1: it is re-calculated on demand as number of live
range to be generated.
---
Diffs of the changes: (+25 -35)
ScheduleDAGList.cpp | 60 +---
1 files changed, 25 insertions(+), 35 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.16
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.17
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.16 Sun Mar 5
18:22:00 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Mon Mar 6 00:08:54 2006
@@ -44,8 +44,7 @@
int NumSuccsLeft; // # of succs not scheduled.
int NumChainPredsLeft; // # of chain preds not scheduled.
int NumChainSuccsLeft; // # of chain succs not scheduled.
- int Priority1; // Scheduling priority 1.
- int Priority2; // Scheduling priority 2.
+ int SethiUllman;// Sethi Ullman number.
bool isTwoAddress; // Is a two-address instruction.
bool isDefNUseOperand; // Is a def&use operand.
unsigned Latency; // Node latency.
@@ -56,7 +55,7 @@
SUnit(SDNode *node)
: Node(node), NumPredsLeft(0), NumSuccsLeft(0),
NumChainPredsLeft(0), NumChainSuccsLeft(0),
- Priority1(INT_MIN), Priority2(INT_MIN),
+ SethiUllman(INT_MIN),
isTwoAddress(false), isDefNUseOperand(false),
Latency(0), CycleBound(0), Slot(0), Next(NULL) {}
@@ -81,8 +80,7 @@
std::cerr << " # chain preds left : " << NumChainPredsLeft << "\n";
std::cerr << " # chain succs left : " << NumChainSuccsLeft << "\n";
std::cerr << " Latency: " << Latency << "\n";
-std::cerr << " Priority : " << Priority1 << " , "
- << Priority2 << "\n";
+std::cerr << " SethiUllman: " << SethiUllman << "\n";
if (Preds.size() != 0) {
std::cerr << " Predecessors:\n";
@@ -140,10 +138,11 @@
RBonus++;
}
-int LPriority1 = left ->Priority1 - LBonus;
-int RPriority1 = right->Priority1 - RBonus;
-int LPriority2 = left ->Priority2 + LBonus;
-int RPriority2 = right->Priority2 + RBonus;
+// Priority1 is just the number of live range genned.
+int LPriority1 = left ->NumPredsLeft - LBonus;
+int RPriority1 = right->NumPredsLeft - RBonus;
+int LPriority2 = left ->SethiUllman + LBonus;
+int RPriority2 = right->SethiUllman + RBonus;
// Favor floaters (i.e. node with no non-passive predecessors):
// e.g. MOV32ri.
@@ -155,7 +154,7 @@
else if (LPriority1 == RPriority1)
if (LPriority2 < RPriority2)
return true;
-else if (LPriority1 == RPriority1)
+else if (LPriority2 == RPriority2)
if (left->CycleBound > right->CycleBound)
return true;
@@ -249,10 +248,9 @@
// interrupt model (drain vs. freeze).
PredSU->CycleBound = std::max(PredSU->CycleBound, CurrCycle +
PredSU->Latency);
- if (!isChain) {
+ if (!isChain)
PredSU->NumSuccsLeft--;
-PredSU->Priority1++;
- } else
+ else
PredSU->NumChainSuccsLeft--;
#ifndef NDEBUG
@@ -281,10 +279,9 @@
// interrupt model (drain vs. freeze).
SuccSU->CycleBound = std::max(SuccSU->CycleBound, CurrCycle +
SuccSU->Latency);
- if (!isChain) {
+ if (!isChain)
SuccSU->NumPredsLeft--;
-SuccSU->Priority1++; // FIXME: ??
- } else
+ else
SuccSU->NumChainPredsLeft--;
#ifndef NDEBUG
@@ -316,7 +313,6 @@
E1 = SU->Preds.end(); I1 != E1; ++I1) {
ReleasePred(Available, *I1);
SU->NumPredsLeft--;
-SU->Priority1--;
}
for (std::set::iterator I2 = SU->ChainPreds.begin(),
E2 = SU->ChainPreds.end(); I2 != E2; ++I2)
@@ -341,7 +337,6 @@
E1 = SU->Succs.end(); I1 != E1; ++I1) {
ReleaseSucc(Available, *I1);
SU->NumSuccsLeft--;
-SU->Priority1--; // FIXME: what is this??
}
for (std::set::iterator I2 = SU->ChainSuccs.begin(),
E2 = SU->ChainSuccs.end(); I2 != E2; ++I2)
@@ -501,39 +496,34 @@
}
-/// CalcNodePriority - Priority1 is just the number of live range genned -
-/// number of live range killed. Priority2 is the Sethi Ullman number. It
-/// returns Priority2 since it is calculated recursively.
-/// Smaller number is the higher priority for Priority2. Reverse is true for
-/// Priority1.
+/// CalcNodePriority - Priority is the Sethi Ullman number.
+/// Smaller number is the higher priority.
int ScheduleDAGList::CalcNodePriority(SUnit *SU) {
- if (SU->Priority2 != INT_MIN)
-return SU->Priority2;
-
- SU->Priority1 = SU->NumPredsLeft - SU->NumSuccsLeft;
+ if (SU->SethiUllman != INT_MIN)
+return SU->SethiUllman;
if (SU->Preds.size() == 0) {
-SU->Priority2 = 1;
+
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG: ScheduleDAGList.cpp updated: 1.14 -> 1.15 --- Log message: Comment fixes --- Diffs of the changes: (+2 -2) ScheduleDAGList.cpp |4 ++-- 1 files changed, 2 insertions(+), 2 deletions(-) Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.14 llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.15 --- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.14 Sun Mar 5 17:51:47 2006 +++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Sun Mar 5 17:59:20 2006 @@ -214,7 +214,7 @@ private: // SDNode to SUnit mapping (many to one). std::map SUnitMap; - // The schedule. Null SUnit*'s represend noop instructions. + // The schedule. Null SUnit*'s represent noop instructions. std::vector Sequence; // Current scheduling cycle. unsigned CurrCycle; @@ -523,7 +523,7 @@ // processors without pipeline interlocks and other cases. DEBUG(std::cerr << "*** Emitting noop"); HazardRec->EmitNoop(); - Sequence.push_back(0); // NULL SUnit -> noop + Sequence.push_back(0); // NULL SUnit* -> noop ++NumNoops; } } ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.12 -> 1.13
---
Log message:
Implement G5HazardRecognizer as a trivial thing that wants 5 cycles between
copyfromreg nodes. Clearly useful!
---
Diffs of the changes: (+42 -2)
ScheduleDAGList.cpp | 44 ++--
1 files changed, 42 insertions(+), 2 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.12
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.13
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.12 Sun Mar 5
16:45:01 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Sun Mar 5 17:13:56 2006
@@ -19,6 +19,7 @@
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Support/Debug.h"
+#include "llvm/ADT/Statistic.h"
#include
#include
#include
@@ -27,6 +28,8 @@
using namespace llvm;
namespace {
+ Statistic<> NumNoops ("scheduler", "Number of noops inserted");
+ Statistic<> NumStalls("scheduler", "Number of pipeline stalls");
/// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or a
/// group of nodes flagged together.
@@ -511,13 +514,17 @@
} else if (!HasNoopHazards) {
// Otherwise, we have a pipeline stall, but no other problem, just
advance
// the current cycle and try again.
+ DEBUG(std::cerr << "*** Advancing cycle, no work to do");
HazardRec->AdvanceCycle();
+ ++NumStalls;
} else {
// Otherwise, we have no instructions to issue and we have instructions
// that will fault if we don't do this right. This is the case for
// processors without pipeline interlocks and other cases.
+ DEBUG(std::cerr << "*** Emitting noop");
HazardRec->EmitNoop();
// FIXME: Add a noop to the schedule!!
+ ++NumNoops;
}
}
@@ -731,11 +738,44 @@
}
/// G5HazardRecognizer - A hazard recognizer for the PowerPC G5 processor.
-/// FIXME: Implement
/// FIXME: Move to the PowerPC backend.
class G5HazardRecognizer : public HazardRecognizer {
+ // Totally bogus hazard recognizer, used to test noop insertion. This
requires
+ // a noop between copyfromreg's.
+ unsigned EmittedCopyFromReg;
public:
- G5HazardRecognizer() {}
+ G5HazardRecognizer() {
+EmittedCopyFromReg = 0;
+ }
+
+ virtual HazardType getHazardType(SDNode *Node) {
+if (Node->getOpcode() == ISD::CopyFromReg && EmittedCopyFromReg)
+ return NoopHazard;
+return NoHazard;
+ }
+
+ /// EmitInstruction - This callback is invoked when an instruction is
+ /// emitted, to advance the hazard state.
+ virtual void EmitInstruction(SDNode *Node) {
+if (Node->getOpcode() == ISD::CopyFromReg) {
+ EmittedCopyFromReg = 5;
+} else if (EmittedCopyFromReg) {
+ --EmittedCopyFromReg;
+}
+ }
+
+ /// AdvanceCycle - This callback is invoked when no instructions can be
+ /// issued on this cycle without a hazard. This should increment the
+ /// internal state of the hazard recognizer so that previously "Hazard"
+ /// instructions will now not be hazards.
+ virtual void AdvanceCycle() {
+ }
+
+ /// EmitNoop - This callback is invoked when a noop was added to the
+ /// instruction stream.
+ virtual void EmitNoop() {
+--EmittedCopyFromReg;
+ }
};
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.11 -> 1.12
---
Log message:
Add basic hazard recognizer support. noop insertion isn't complete yet though.
---
Diffs of the changes: (+104 -15)
ScheduleDAGList.cpp | 119 +---
1 files changed, 104 insertions(+), 15 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.11
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.12
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.11 Sun Mar 5
15:10:33 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Sun Mar 5 16:45:01 2006
@@ -160,6 +160,52 @@
}
};
+
+/// HazardRecognizer - This determines whether or not an instruction can be
+/// issued this cycle, and whether or not a noop needs to be inserted to handle
+/// the hazard.
+namespace {
+ class HazardRecognizer {
+ public:
+virtual ~HazardRecognizer() {}
+
+enum HazardType {
+ NoHazard, // This instruction can be emitted at this cycle.
+ Hazard,// This instruction can't be emitted at this cycle.
+ NoopHazard,// This instruction can't be emitted, and needs noops.
+};
+
+/// getHazardType - Return the hazard type of emitting this node. There
are
+/// three possible results. Either:
+/// * NoHazard: it is legal to issue this instruction on this cycle.
+/// * Hazard: issuing this instruction would stall the machine. If some
+/// other instruction is available, issue it first.
+/// * NoopHazard: issuing this instruction would break the program. If
+/// some other instruction can be issued, do so, otherwise issue a
noop.
+virtual HazardType getHazardType(SDNode *Node) {
+ return NoHazard;
+}
+
+/// EmitInstruction - This callback is invoked when an instruction is
+/// emitted, to advance the hazard state.
+virtual void EmitInstruction(SDNode *Node) {
+}
+
+/// AdvanceCycle - This callback is invoked when no instructions can be
+/// issued on this cycle without a hazard. This should increment the
+/// internal state of the hazard recognizer so that previously "Hazard"
+/// instructions will now not be hazards.
+virtual void AdvanceCycle() {
+}
+
+/// EmitNoop - This callback is invoked when a noop was added to the
+/// instruction stream.
+virtual void EmitNoop() {
+}
+ };
+}
+
+
/// ScheduleDAGList - List scheduler.
class ScheduleDAGList : public ScheduleDAG {
private:
@@ -176,14 +222,21 @@
/// it is top-down.
bool isBottomUp;
+ /// HazardRec - The hazard recognizer to use.
+ HazardRecognizer *HazardRec;
+
typedef std::priority_queue, ls_rr_sort>
AvailableQueueTy;
public:
ScheduleDAGList(SelectionDAG &dag, MachineBasicBlock *bb,
- const TargetMachine &tm, bool isbottomup)
+ const TargetMachine &tm, bool isbottomup,
+ HazardRecognizer *HR = 0)
: ScheduleDAG(listSchedulingBURR, dag, bb, tm),
- CurrCycle(0), HeadSUnit(NULL), TailSUnit(NULL), isBottomUp(isbottomup) {}
+ CurrCycle(0), HeadSUnit(NULL), TailSUnit(NULL), isBottomUp(isbottomup) {
+ if (HR == 0) HR = new HazardRecognizer();
+HazardRec = HR;
+}
~ScheduleDAGList() {
SUnit *SU = HeadSUnit;
@@ -192,6 +245,8 @@
delete SU;
SU = NextSU;
}
+
+delete HazardRec;
}
void Schedule();
@@ -411,7 +466,8 @@
// Emit the entry node first.
SUnit *Entry = SUnitMap[DAG.getEntryNode().Val];
ScheduleNodeTopDown(Available, Entry);
-
+ HazardRec->EmitInstruction(Entry->Node);
+
// All leaves to Available queue.
for (SUnit *SU = HeadSUnit; SU != NULL; SU = SU->Next) {
// It is available if it has no predecessors.
@@ -423,23 +479,46 @@
// priority. If it is not ready put it back. Schedule the node.
std::vector NotReady;
while (!Available.empty()) {
-SUnit *CurrNode = Available.top();
-Available.pop();
-
-// FIXME: when priorities make sense, reenable this.
-while (0 && !isReady(CurrNode, CurrCycle)) {
- NotReady.push_back(CurrNode);
- CurrNode = Available.top();
- Available.pop();
-}
+SUnit *FoundNode = 0;
+bool HasNoopHazards = false;
+do {
+ SUnit *CurrNode = Available.top();
+ Available.pop();
+ HazardRecognizer::HazardType HT =
+HazardRec->getHazardType(CurrNode->Node);
+ if (HT == HazardRecognizer::NoHazard) {
+FoundNode = CurrNode;
+break;
+ }
+
+ // Remember if this is a noop hazard.
+ HasNoopHazards |= HT == HazardRecognizer::NoopHazard;
+
+ NotReady.push_back(CurrNode);
+} while (!Available.empty());
+
// Add the nodes that aren't ready back onto the available list.
while (!NotReady.empty()) {
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.9 -> 1.10
---
Log message:
Move the available queue to being inside the ListSchedule method, since it
bounds its lifetime.
---
Diffs of the changes: (+15 -10)
ScheduleDAGList.cpp | 25 +++--
1 files changed, 15 insertions(+), 10 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.9
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.10
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.9 Fri Mar 3
00:23:43 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Sun Mar 5 14:21:55 2006
@@ -164,8 +164,6 @@
private:
// SDNode to SUnit mapping (many to one).
std::map SUnitMap;
- // Available queue.
- std::priority_queue, ls_rr_sort> Available;
// The schedule.
std::vector Sequence;
// Current scheduling cycle.
@@ -173,6 +171,9 @@
// First and last SUnit created.
SUnit *HeadSUnit, *TailSUnit;
+ typedef std::priority_queue, ls_rr_sort>
+AvailableQueueTy;
+
public:
ScheduleDAGList(SelectionDAG &dag, MachineBasicBlock *bb,
const TargetMachine &tm)
@@ -194,8 +195,8 @@
private:
SUnit *NewSUnit(SDNode *N);
- void ReleasePred(SUnit *PredSU, bool isChain = false);
- void ScheduleNode(SUnit *SU);
+ void ReleasePred(AvailableQueueTy &Avail,SUnit *PredSU, bool isChain =
false);
+ void ScheduleNode(AvailableQueueTy &Avail, SUnit *SU);
int CalcNodePriority(SUnit *SU);
void CalculatePriorities();
void ListSchedule();
@@ -220,7 +221,8 @@
/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to
/// the Available queue is the count reaches zero. Also update its cycle bound.
-void ScheduleDAGList::ReleasePred(SUnit *PredSU, bool isChain) {
+void ScheduleDAGList::ReleasePred(AvailableQueueTy &Available,
+ SUnit *PredSU, bool isChain) {
SDNode *PredNode = PredSU->Node;
// FIXME: the distance between two nodes is not always == the predecessor's
@@ -251,7 +253,7 @@
/// ScheduleNode - Add the node to the schedule. Decrement the pending count of
/// its predecessors. If a predecessor pending count is zero, add it to the
/// Available queue.
-void ScheduleDAGList::ScheduleNode(SUnit *SU) {
+void ScheduleDAGList::ScheduleNode(AvailableQueueTy &Available, SUnit *SU) {
DEBUG(std::cerr << "*** Scheduling: ");
DEBUG(SU->dump(&DAG, false));
@@ -261,13 +263,13 @@
// Bottom up: release predecessors
for (std::set::iterator I1 = SU->Preds.begin(),
E1 = SU->Preds.end(); I1 != E1; ++I1) {
-ReleasePred(*I1);
+ReleasePred(Available, *I1);
SU->NumPredsLeft--;
SU->Priority1--;
}
for (std::set::iterator I2 = SU->ChainPreds.begin(),
E2 = SU->ChainPreds.end(); I2 != E2; ++I2)
-ReleasePred(*I2, true);
+ReleasePred(Available, *I2, true);
CurrCycle++;
}
@@ -280,7 +282,10 @@
/// ListSchedule - The main loop of list scheduling.
void ScheduleDAGList::ListSchedule() {
- // Add root to Available queue
+ // Available queue.
+ AvailableQueueTy Available;
+
+ // Add root to Available queue.
SUnit *Root = SUnitMap[DAG.getRoot().Val];
Available.push(Root);
@@ -300,7 +305,7 @@
for (unsigned i = 0, e = NotReady.size(); i != e; ++i)
Available.push(NotReady[i]);
-ScheduleNode(CurrNode);
+ScheduleNode(Available, CurrNode);
}
// Add entry node last
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.8 -> 1.9
---
Log message:
A bit more tweaking
---
Diffs of the changes: (+24 -6)
ScheduleDAGList.cpp | 30 --
1 files changed, 24 insertions(+), 6 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.8
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.9
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.8 Thu Mar 2
21:25:07 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Fri Mar 3 00:23:43 2006
@@ -43,6 +43,7 @@
int NumChainSuccsLeft; // # of chain succs not scheduled.
int Priority1; // Scheduling priority 1.
int Priority2; // Scheduling priority 2.
+ bool isTwoAddress; // Is a two-address instruction.
bool isDefNUseOperand; // Is a def&use operand.
unsigned Latency; // Node latency.
unsigned CycleBound;// Upper/lower cycle to be scheduled at.
@@ -52,7 +53,8 @@
SUnit(SDNode *node)
: Node(node), NumPredsLeft(0), NumSuccsLeft(0),
NumChainPredsLeft(0), NumChainSuccsLeft(0),
- Priority1(INT_MIN), Priority2(INT_MIN), isDefNUseOperand(false),
+ Priority1(INT_MIN), Priority2(INT_MIN),
+ isTwoAddress(false), isDefNUseOperand(false),
Latency(0), CycleBound(0), Slot(0), Next(NULL) {}
void dump(const SelectionDAG *G, bool All=true) const;
@@ -120,6 +122,20 @@
bool RFloater = (right->Preds.size() == 0);
int LBonus = (int)left ->isDefNUseOperand;
int RBonus = (int)right->isDefNUseOperand;
+
+// Special tie breaker: if two nodes share a operand, the one that
+// use it as a def&use operand is preferred.
+if (left->isTwoAddress && !right->isTwoAddress) {
+ SDNode *DUNode = left->Node->getOperand(0).Val;
+ if (DUNode->isOperand(right->Node))
+LBonus++;
+}
+if (!left->isTwoAddress && right->isTwoAddress) {
+ SDNode *DUNode = right->Node->getOperand(0).Val;
+ if (DUNode->isOperand(left->Node))
+RBonus++;
+}
+
int LPriority1 = left ->Priority1 - LBonus;
int RPriority1 = right->Priority1 - RBonus;
int LPriority2 = left ->Priority2 + LBonus;
@@ -138,8 +154,6 @@
else if (LPriority1 == RPriority1)
if (left->CycleBound > right->CycleBound)
return true;
- else
-return left->Node->getNodeDepth() < right->Node->getNodeDepth();
return false;
}
@@ -238,6 +252,9 @@
/// its predecessors. If a predecessor pending count is zero, add it to the
/// Available queue.
void ScheduleDAGList::ScheduleNode(SUnit *SU) {
+ DEBUG(std::cerr << "*** Scheduling: ");
+ DEBUG(SU->dump(&DAG, false));
+
Sequence.push_back(SU);
SU->Slot = CurrCycle;
@@ -283,8 +300,6 @@
for (unsigned i = 0, e = NotReady.size(); i != e; ++i)
Available.push(NotReady[i]);
-DEBUG(std::cerr << "*** Scheduling: ");
-DEBUG(CurrNode->dump(&DAG, false));
ScheduleNode(CurrNode);
}
@@ -402,6 +417,9 @@
for (SUnit *SU = HeadSUnit; SU != NULL; SU = SU->Next) {
SDNode *N = SU->Node;
NodeInfo *NI = getNI(N);
+
+if (N->isTargetOpcode() && TII->isTwoAddrInstr(N->getTargetOpcode()))
+ SU->isTwoAddress = true;
if (NI->isInGroup()) {
// Find all predecessors (of the group).
@@ -446,7 +464,7 @@
SU->NumPredsLeft++;
if (OpSU->Succs.insert(SU).second)
OpSU->NumSuccsLeft++;
-if (j == 0 && TII->isTwoAddrInstr(N->getTargetOpcode()))
+if (j == 0 && SU->isTwoAddress)
OpSU->isDefNUseOperand = true;
}
}
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.7 -> 1.8
---
Log message:
Fix VC++ compilation errors.
---
Diffs of the changes: (+4 -4)
ScheduleDAGList.cpp |8
1 files changed, 4 insertions(+), 4 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.7
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.8
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.7 Thu Mar 2
15:38:29 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Thu Mar 2 21:25:07 2006
@@ -80,7 +80,7 @@
if (Preds.size() != 0) {
std::cerr << "Predecessors :\n";
- for (std::set::iterator I = Preds.begin(),
+ for (std::set::const_iterator I = Preds.begin(),
E = Preds.end(); I != E; ++I) {
std::cerr << "";
(*I)->dump(G, false);
@@ -88,7 +88,7 @@
}
if (ChainPreds.size() != 0) {
std::cerr << "Chained Preds :\n";
- for (std::set::iterator I = ChainPreds.begin(),
+ for (std::set::const_iterator I = ChainPreds.begin(),
E = ChainPreds.end(); I != E; ++I) {
std::cerr << "";
(*I)->dump(G, false);
@@ -96,7 +96,7 @@
}
if (Succs.size() != 0) {
std::cerr << "Successors:\n";
- for (std::set::iterator I = Succs.begin(),
+ for (std::set::const_iterator I = Succs.begin(),
E = Succs.end(); I != E; ++I) {
std::cerr << "";
(*I)->dump(G, false);
@@ -104,7 +104,7 @@
}
if (ChainSuccs.size() != 0) {
std::cerr << "Chained succs :\n";
- for (std::set::iterator I = ChainSuccs.begin(),
+ for (std::set::const_iterator I = ChainSuccs.begin(),
E = ChainSuccs.end(); I != E; ++I) {
std::cerr << "";
(*I)->dump(G, false);
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.6 -> 1.7
---
Log message:
- Fixed some priority calculation bugs that were causing bug 478:
http://llvm.cs.uiuc.edu/PR478 . Among them:
a predecessor appearing more than once in the operand list was counted as
multiple predecessor; priority1 should be updated during scheduling;
CycleBound was updated after the node is inserted into priority queue; one
of the tie breaking condition was flipped.
- Take into consideration of two address opcodes. If a predecessor is a def&use
operand, it should have a higher priority.
- Scheduler should also favor floaters, i.e. nodes that do not have real
predecessors such as MOV32ri.
- The scheduling fixes / tweaks fixed bug 478: http://llvm.cs.uiuc.edu/PR478 :
.text
.align 4
.globl _f
_f:
movl 4(%esp), %eax
movl 8(%esp), %ecx
movl %eax, %edx
imull %ecx, %edx
imull %eax, %eax
imull %ecx, %ecx
addl %eax, %ecx
leal (%ecx,%edx,2), %eax
ret
It is also a slight performance win (1% - 3%) for most tests.
---
Diffs of the changes: (+98 -64)
ScheduleDAGList.cpp | 162 +++-
1 files changed, 98 insertions(+), 64 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.6
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.7
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.6 Wed Feb 1
18:38:08 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Thu Mar 2 15:38:29 2006
@@ -21,8 +21,9 @@
#include "llvm/Support/Debug.h"
#include
#include
-#include
#include
+#include
+#include
using namespace llvm;
namespace {
@@ -32,14 +33,17 @@
struct SUnit {
SDNode *Node; // Representative node.
std::vector FlaggedNodes; // All nodes flagged to Node.
- std::vector Preds; // All real predecessors.
- std::vector ChainPreds;// All chain predecessors.
- std::vector Succs; // All real successors.
- std::vector ChainSuccs;// All chain successors.
+ std::set Preds; // All real predecessors.
+ std::set ChainPreds;// All chain predecessors.
+ std::set Succs; // All real successors.
+ std::set ChainSuccs;// All chain successors.
int NumPredsLeft; // # of preds not scheduled.
int NumSuccsLeft; // # of succs not scheduled.
+ int NumChainPredsLeft; // # of chain preds not scheduled.
+ int NumChainSuccsLeft; // # of chain succs not scheduled.
int Priority1; // Scheduling priority 1.
int Priority2; // Scheduling priority 2.
+ bool isDefNUseOperand; // Is a def&use operand.
unsigned Latency; // Node latency.
unsigned CycleBound;// Upper/lower cycle to be scheduled at.
unsigned Slot; // Cycle node is scheduled at.
@@ -47,8 +51,9 @@
SUnit(SDNode *node)
: Node(node), NumPredsLeft(0), NumSuccsLeft(0),
- Priority1(INT_MIN), Priority2(INT_MIN), Latency(0),
- CycleBound(0), Slot(0), Next(NULL) {}
+ NumChainPredsLeft(0), NumChainSuccsLeft(0),
+ Priority1(INT_MIN), Priority2(INT_MIN), isDefNUseOperand(false),
+ Latency(0), CycleBound(0), Slot(0), Next(NULL) {}
void dump(const SelectionDAG *G, bool All=true) const;
};
@@ -66,37 +71,43 @@
}
if (All) {
-std::cerr << "# preds left : " << NumPredsLeft << "\n";
-std::cerr << "# succs left : " << NumSuccsLeft << "\n";
-std::cerr << "Latency : " << Latency << "\n";
-std::cerr << "Priority : " << Priority1 << " , " << Priority2 << "\n";
+std::cerr << "# preds left : " << NumPredsLeft << "\n";
+std::cerr << "# succs left : " << NumSuccsLeft << "\n";
+std::cerr << "# chain preds left : " << NumChainPredsLeft << "\n";
+std::cerr << "# chain succs left : " << NumChainSuccsLeft << "\n";
+std::cerr << "Latency: " << Latency << "\n";
+std::cerr << "Priority : " << Priority1 << " , " << Priority2 <<
"\n";
if (Preds.size() != 0) {
std::cerr << "Predecessors :\n";
- for (unsigned i = 0, e = Preds.size(); i != e; i++) {
+ for (std::set::iterator I = Preds.begin(),
+ E = Preds.end(); I != E; ++I) {
std::cerr << "";
-Preds[i]->dump(G, false);
+(*I)->dump(G, false);
}
}
if (ChainPreds.size() != 0) {
std::cerr << "Chained Preds :\n";
- for (unsigned i = 0, e = ChainPreds.size(); i != e; i++) {
+ for (std::set::iterator I = ChainPreds.begin(),
+ E = ChainPreds.end(); I != E; ++I) {
std::cerr << "";
-ChainPreds[i]->dump(G, false);
+(*I)->dump(G, false);
}
}
if
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG: ScheduleDAGList.cpp updated: 1.5 -> 1.6 --- Log message: make -debug output less newliney --- Diffs of the changes: (+1 -2) ScheduleDAGList.cpp |3 +-- 1 files changed, 1 insertion(+), 2 deletions(-) Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.5 llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.6 --- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.5 Wed Jan 25 18:30:29 2006 +++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Wed Feb 1 18:38:08 2006 @@ -257,9 +257,8 @@ for (unsigned i = 0, e = NotReady.size(); i != e; ++i) Available.push(NotReady[i]); -DEBUG(std::cerr << "\n*** Scheduling: "); +DEBUG(std::cerr << "*** Scheduling: "); DEBUG(CurrNode->dump(&DAG, false)); -DEBUG(std::cerr << "\n"); ScheduleNode(CurrNode); } ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.4 -> 1.5
---
Log message:
Clean up some code; improve efficiency; and fixed a potential bug involving
chain successors.
---
Diffs of the changes: (+126 -149)
ScheduleDAGList.cpp | 275 +++-
1 files changed, 126 insertions(+), 149 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.4
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.5
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.4 Wed Jan 25
15:49:13 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Wed Jan 25 18:30:29 2006
@@ -32,10 +32,10 @@
struct SUnit {
SDNode *Node; // Representative node.
std::vector FlaggedNodes; // All nodes flagged to Node.
- std::vector Preds; // All real predecessors.
- std::vector ChainPreds;// All chain predecessors.
- std::vector Succs; // All real successors.
- std::vector ChainSuccs;// All chain successors.
+ std::vector Preds; // All real predecessors.
+ std::vector ChainPreds;// All chain predecessors.
+ std::vector Succs; // All real successors.
+ std::vector ChainSuccs;// All chain successors.
int NumPredsLeft; // # of preds not scheduled.
int NumSuccsLeft; // # of succs not scheduled.
int Priority1; // Scheduling priority 1.
@@ -43,67 +43,60 @@
unsigned Latency; // Node latency.
unsigned CycleBound;// Upper/lower cycle to be scheduled at.
unsigned Slot; // Cycle node is scheduled at.
+ SUnit *Next;
SUnit(SDNode *node)
: Node(node), NumPredsLeft(0), NumSuccsLeft(0),
Priority1(INT_MIN), Priority2(INT_MIN), Latency(0),
- CycleBound(0), Slot(0) {}
+ CycleBound(0), Slot(0), Next(NULL) {}
void dump(const SelectionDAG *G, bool All=true) const;
};
void SUnit::dump(const SelectionDAG *G, bool All) const {
- std::cerr << "SU: ";
+ std::cerr << "SU: ";
Node->dump(G);
std::cerr << "\n";
- if (All) {
-std::cerr << "# preds left : " << NumPredsLeft << "\n";
-std::cerr << "# succs left : " << NumSuccsLeft << "\n";
-std::cerr << "Latency : " << Latency << "\n";
-std::cerr << "Priority : " << Priority1 << " , " << Priority2 << "\n";
- }
-
if (FlaggedNodes.size() != 0) {
-if (All)
- std::cerr << "Flagged nodes :\n";
for (unsigned i = 0, e = FlaggedNodes.size(); i != e; i++) {
- std::cerr << " ";
+ std::cerr << "";
FlaggedNodes[i]->dump(G);
std::cerr << "\n";
}
}
if (All) {
+std::cerr << "# preds left : " << NumPredsLeft << "\n";
+std::cerr << "# succs left : " << NumSuccsLeft << "\n";
+std::cerr << "Latency : " << Latency << "\n";
+std::cerr << "Priority : " << Priority1 << " , " << Priority2 << "\n";
+
if (Preds.size() != 0) {
std::cerr << "Predecessors :\n";
for (unsigned i = 0, e = Preds.size(); i != e; i++) {
std::cerr << "";
-Preds[i]->dump(G);
-std::cerr << "\n";
+Preds[i]->dump(G, false);
}
}
if (ChainPreds.size() != 0) {
std::cerr << "Chained Preds :\n";
for (unsigned i = 0, e = ChainPreds.size(); i != e; i++) {
std::cerr << "";
-ChainPreds[i]->dump(G);
-std::cerr << "\n";
+ChainPreds[i]->dump(G, false);
}
}
if (Succs.size() != 0) {
std::cerr << "Successors:\n";
for (unsigned i = 0, e = Succs.size(); i != e; i++) {
std::cerr << "";
-Succs[i]->dump(G);
-std::cerr << "\n";
+Succs[i]->dump(G, false);
}
}
if (ChainSuccs.size() != 0) {
std::cerr << "Chained succs :\n";
for (unsigned i = 0, e = ChainSuccs.size(); i != e; i++) {
std::cerr << "";
-ChainSuccs[i]->dump(G);
-std::cerr << "\n";
+ChainSuccs[i]->dump(G, false);
}
}
}
@@ -146,21 +139,21 @@
std::vector Sequence;
// Current scheduling cycle.
unsigned CurrCycle;
+ // First and last SUnit created.
+ SUnit *HeadSUnit, *TailSUnit;
public:
ScheduleDAGList(SelectionDAG &dag, MachineBasicBlock *bb,
const TargetMachine &tm)
-: ScheduleDAG(listSchedulingBURR, dag, bb, tm), CurrCycle(0) {};
+: ScheduleDAG(listSchedulingBURR, dag, bb, tm),
+ CurrCycle(0), HeadSUnit(NULL), TailSUnit(NULL) {};
~ScheduleDAGList() {
-for (std::map::iterator I = SUnitMap.begin(),
- E = SUnitMap.end(); I != E; ++I) {
- SUnit *SU = I->second;
- // Multiple SDNode* can point to one SUnit. Do ref counting, sort of.
- if (SU->FlaggedNodes.size() == 0)
-delete SU;
- else
-SU->FlaggedNodes.pop_back();
+SUnit *SU
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG: ScheduleDAGList.cpp updated: 1.3 -> 1.4 --- Log message: Don't break the optimized build (by incorrect placement of #endif) --- Diffs of the changes: (+1 -1) ScheduleDAGList.cpp |2 +- 1 files changed, 1 insertion(+), 1 deletion(-) Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.3 llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.4 --- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.3 Wed Jan 25 11:17:49 2006 +++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Wed Jan 25 15:49:13 2006 @@ -270,8 +270,8 @@ std::cerr << " has not been scheduled!\n"; assert(0); } -#endif } +#endif // Reverse the order if it is bottom up. ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.2 -> 1.3
---
Log message:
Fix VC++ compilation error.
---
Diffs of the changes: (+1 -1)
ScheduleDAGList.cpp |2 +-
1 files changed, 1 insertion(+), 1 deletion(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.2
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.3
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.2 Wed Jan 25
03:14:32 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Wed Jan 25 11:17:49 2006
@@ -341,7 +341,7 @@
}
void ScheduleDAGList::BuildSchedUnits() {
- for (unsigned i = 0, N = NodeCount; i < N; i++) {
+ for (unsigned i = 0, NC = NodeCount; i < NC; i++) {
NodeInfo *NI = &Info[i];
SDNode *N = NI->Node;
if (!isPassiveNode(N)) {
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp updated: 1.1 -> 1.2
---
Log message:
Bottom up register usage reducing list scheduler.
---
Diffs of the changes: (+451 -21)
ScheduleDAGList.cpp | 472 +---
1 files changed, 451 insertions(+), 21 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.1
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.2
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.1 Mon Jan 23
02:26:10 2006
+++ llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Wed Jan 25 03:14:32 2006
@@ -1,4 +1,4 @@
-//===-- ScheduleDAGSimple.cpp - Implement a list scheduler for isel DAG
---===//
+//=== ScheduleDAGList.cpp - Implement a list scheduler for isel DAG
---===//
//
// The LLVM Compiler Infrastructure
//
@@ -18,44 +18,474 @@
#include "llvm/CodeGen/SelectionDAG.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetInstrInfo.h"
-#include
+#include "llvm/Support/Debug.h"
+#include
+#include
+#include
#include
using namespace llvm;
+namespace {
-namespace llvm {
-/// Sorting functions for ready queue.
-struct LSSortPred : public std::binary_function {
- bool operator()(const SDOperand* left, const SDOperand* right) const {
-return true;
+/// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or a
+/// group of nodes flagged together.
+struct SUnit {
+ SDNode *Node; // Representative node.
+ std::vector FlaggedNodes; // All nodes flagged to Node.
+ std::vector Preds; // All real predecessors.
+ std::vector ChainPreds;// All chain predecessors.
+ std::vector Succs; // All real successors.
+ std::vector ChainSuccs;// All chain successors.
+ int NumPredsLeft; // # of preds not scheduled.
+ int NumSuccsLeft; // # of succs not scheduled.
+ int Priority1; // Scheduling priority 1.
+ int Priority2; // Scheduling priority 2.
+ unsigned Latency; // Node latency.
+ unsigned CycleBound;// Upper/lower cycle to be scheduled at.
+ unsigned Slot; // Cycle node is scheduled at.
+
+ SUnit(SDNode *node)
+: Node(node), NumPredsLeft(0), NumSuccsLeft(0),
+ Priority1(INT_MIN), Priority2(INT_MIN), Latency(0),
+ CycleBound(0), Slot(0) {}
+
+ void dump(const SelectionDAG *G, bool All=true) const;
+};
+
+void SUnit::dump(const SelectionDAG *G, bool All) const {
+ std::cerr << "SU: ";
+ Node->dump(G);
+ std::cerr << "\n";
+ if (All) {
+std::cerr << "# preds left : " << NumPredsLeft << "\n";
+std::cerr << "# succs left : " << NumSuccsLeft << "\n";
+std::cerr << "Latency : " << Latency << "\n";
+std::cerr << "Priority : " << Priority1 << " , " << Priority2 << "\n";
+ }
+
+ if (FlaggedNodes.size() != 0) {
+if (All)
+ std::cerr << "Flagged nodes :\n";
+for (unsigned i = 0, e = FlaggedNodes.size(); i != e; i++) {
+ std::cerr << " ";
+ FlaggedNodes[i]->dump(G);
+ std::cerr << "\n";
+}
+ }
+
+ if (All) {
+if (Preds.size() != 0) {
+ std::cerr << "Predecessors :\n";
+ for (unsigned i = 0, e = Preds.size(); i != e; i++) {
+std::cerr << "";
+Preds[i]->dump(G);
+std::cerr << "\n";
+ }
+}
+if (ChainPreds.size() != 0) {
+ std::cerr << "Chained Preds :\n";
+ for (unsigned i = 0, e = ChainPreds.size(); i != e; i++) {
+std::cerr << "";
+ChainPreds[i]->dump(G);
+std::cerr << "\n";
+ }
+}
+if (Succs.size() != 0) {
+ std::cerr << "Successors:\n";
+ for (unsigned i = 0, e = Succs.size(); i != e; i++) {
+std::cerr << "";
+Succs[i]->dump(G);
+std::cerr << "\n";
+ }
+}
+if (ChainSuccs.size() != 0) {
+ std::cerr << "Chained succs :\n";
+ for (unsigned i = 0, e = ChainSuccs.size(); i != e; i++) {
+std::cerr << "";
+ChainSuccs[i]->dump(G);
+std::cerr << "\n";
+ }
+}
+ }
+}
+
+/// Sorting functions for the Available queue.
+struct ls_rr_sort : public std::binary_function {
+ bool operator()(const SUnit* left, const SUnit* right) const {
+if (left->Priority1 > right->Priority1) {
+ return true;
+} else if (left->Priority1 == right->Priority1) {
+ unsigned lf = left->FlaggedNodes.size();
+ unsigned rf = right->FlaggedNodes.size();
+ if (lf > rf)
+return true;
+ else if (lf == rf) {
+if (left->Priority2 > right->Priority2)
+ return true;
+else if (left->Priority2 == right->Priority2) {
+ if (left->CycleBound > right->CycleBound)
+return true;
+ else
+return left->Node->getNodeDepth() < right->Node->getNodeDep
[llvm-commits] CVS: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp SelectionDAGISel.cpp
Changes in directory llvm/lib/CodeGen/SelectionDAG:
ScheduleDAGList.cpp added (r1.1)
SelectionDAGISel.cpp updated: 1.133 -> 1.134
---
Log message:
Skeleton of the list schedule.
---
Diffs of the changes: (+65 -0)
ScheduleDAGList.cpp | 61 +++
SelectionDAGISel.cpp |4 +++
2 files changed, 65 insertions(+)
Index: llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
diff -c /dev/null llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp:1.1
*** /dev/null Mon Jan 23 02:26:20 2006
--- llvm/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp Mon Jan 23 02:26:10 2006
***
*** 0
--- 1,61
+ //===-- ScheduleDAGSimple.cpp - Implement a list scheduler for isel DAG
---===//
+ //
+ // The LLVM Compiler Infrastructure
+ //
+ // This file was developed by Evan Cheng and is distributed under the
+ // University of Illinois Open Source License. See LICENSE.TXT for details.
+ //
+
//===--===//
+ //
+ // This implements a simple two pass scheduler. The first pass attempts to
push
+ // backward any lengthy instructions and critical paths. The second pass
packs
+ // instructions into semi-optimal time slots.
+ //
+
//===--===//
+
+ #define DEBUG_TYPE "sched"
+ #include "llvm/CodeGen/ScheduleDAG.h"
+ #include "llvm/CodeGen/SelectionDAG.h"
+ #include "llvm/Target/TargetMachine.h"
+ #include "llvm/Target/TargetInstrInfo.h"
+ #include
+ #include
+ using namespace llvm;
+
+
+ namespace llvm {
+ /// Sorting functions for ready queue.
+ struct LSSortPred : public std::binary_function {
+ bool operator()(const SDOperand* left, const SDOperand* right) const {
+ return true;
+ }
+ };
+
+ /// ScheduleDAGList - List scheduler.
+
+ class ScheduleDAGList : public ScheduleDAG {
+ private:
+ LSSortPred &Cmp;
+
+ // Ready queue
+ std::priority_queue, LSSortPred> Ready;
+
+ public:
+ ScheduleDAGList(SelectionDAG &dag, MachineBasicBlock *bb,
+ const TargetMachine &tm, LSSortPred cmp)
+ : ScheduleDAG(listSchedulingBURR, dag, bb, tm), Cmp(cmp), Ready(Cmp)
+ {};
+
+ void Schedule();
+ };
+ } // end namespace llvm
+
+ void ScheduleDAGList::Schedule() {
+ }
+
+
+ llvm::ScheduleDAG*
+ llvm::createBURRListDAGScheduler(SelectionDAG &DAG,
+ MachineBasicBlock *BB) {
+ return new ScheduleDAGList(DAG, BB, DAG.getTarget(), LSSortPred());
+ }
Index: llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:1.133
llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:1.134
--- llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:1.133Mon Jan 23
01:01:07 2006
+++ llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp Mon Jan 23 02:26:10 2006
@@ -69,6 +69,8 @@
clEnumValN(simpleNoItinScheduling, "simple-noitin",
"Simple two pass scheduling: Same as simple "
"except using generic latency"),
+ clEnumValN(listSchedulingBURR, "list-BURR",
+ "Bottom up register reduction list scheduling"),
clEnumValEnd));
} // namespace
@@ -1775,6 +1777,8 @@
case simpleNoItinScheduling:
SL = createSimpleDAGScheduler(ISHeuristic, DAG, BB);
break;
+ case listSchedulingBURR:
+SL = createBURRListDAGScheduler(DAG, BB);
}
BB = SL->Run();
}
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
