1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
|
//===-- ScheduleDAG.cpp - Implement a trivial DAG scheduler ---------------===//
//
// The LLVM Compiler Infrastructure
//
// This file was developed by Chris Lattner and is distributed under the
// University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This implements a simple code linearizer for DAGs. This is not a very good
// way to emit code, but gets working code quickly.
//
//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "sched"
#include "llvm/CodeGen/SelectionDAGISel.h"
#include "llvm/CodeGen/SelectionDAG.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Support/CommandLine.h"
using namespace llvm;
#ifndef _NDEBUG
static cl::opt<bool>
ViewDAGs("view-sched-dags", cl::Hidden,
cl::desc("Pop up a window to show sched dags as they are processed"));
#else
static const bool ViewDAGS = 0;
#endif
namespace {
class SimpleSched {
SelectionDAG &DAG;
MachineBasicBlock *BB;
const TargetMachine &TM;
const TargetInstrInfo &TII;
std::map<SDNode *, unsigned> EmittedOps;
public:
SimpleSched(SelectionDAG &D, MachineBasicBlock *bb)
: DAG(D), BB(bb), TM(D.getTarget()), TII(*TM.getInstrInfo()) {
assert(&TII && "Target doesn't provide instr info?");
}
void Run() {
Emit(DAG.getRoot());
}
private:
unsigned Emit(SDOperand Op);
};
}
unsigned SimpleSched::Emit(SDOperand Op) {
// Check to see if we have already emitted this. If so, return the value
// already emitted. Note that if a node has a single use it cannot be
// revisited, so don't bother putting it in the map.
unsigned *OpSlot;
if (Op.Val->hasOneUse()) {
OpSlot = 0; // No reuse possible.
} else {
std::map<SDNode *, unsigned>::iterator OpI = EmittedOps.lower_bound(Op.Val);
if (OpI != EmittedOps.end() && OpI->first == Op.Val)
return OpI->second + Op.ResNo;
OpSlot = &EmittedOps.insert(OpI, std::make_pair(Op.Val, 0))->second;
}
unsigned ResultReg = 0;
if (Op.isTargetOpcode()) {
unsigned Opc = Op.getTargetOpcode();
const TargetInstrDescriptor &II = TII.get(Opc);
// Target nodes have any register or immediate operands before any chain
// nodes. Check that the DAG matches the TD files's expectation of #
// operands.
#ifndef _NDEBUG
unsigned Operands = Op.getNumOperands();
if (Operands && Op.getOperand(Operands-1).getValueType() == MVT::Other)
--Operands;
unsigned Results = Op.Val->getNumValues();
if (Results && Op.getOperand(Results-1).getValueType() == MVT::Other)
--Results;
assert(unsigned(II.numOperands) == Operands+Results &&
"#operands for dag node doesn't match .td file!");
#endif
// Create the new machine instruction.
MachineInstr *MI = new MachineInstr(Opc, II.numOperands, true, true);
// Add result register values for things that are defined by this
// instruction.
assert(Op.Val->getNumValues() == 1 &&
Op.getValue(0).getValueType() == MVT::Other &&
"Return values not implemented yet");
// Emit all of the operands of this instruction, adding them to the
// instruction as appropriate.
for (unsigned i = 0, e = Op.getNumOperands(); i != e; ++i) {
if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(i))) {
MI->addZeroExtImm64Operand(C->getValue());
} else if (RegisterSDNode*R =dyn_cast<RegisterSDNode>(Op.getOperand(i))) {
MI->addRegOperand(R->getReg(), MachineOperand::Use);
} else {
unsigned R = Emit(Op.getOperand(i));
// Add an operand, unless this corresponds to a chain node.
if (Op.getOperand(i).getValueType() != MVT::Other)
MI->addRegOperand(R, MachineOperand::Use);
}
}
// Now that we have emitted all operands, emit this instruction itself.
BB->insert(BB->end(), MI);
} else {
switch (Op.getOpcode()) {
default:
Op.Val->dump();
assert(0 && "This target-independent node should have been selected!");
case ISD::EntryToken: break;
case ISD::CopyToReg: {
unsigned Val = Emit(Op.getOperand(2));
// FIXME: DO THE COPY NOW.
break;
}
}
}
if (OpSlot) *OpSlot = ResultReg;
return ResultReg+Op.ResNo;
}
/// Pick a safe ordering and emit instructions for each target node in the
/// graph.
void SelectionDAGISel::ScheduleAndEmitDAG(SelectionDAG &SD) {
if (ViewDAGs) SD.viewGraph();
SimpleSched(SD, BB).Run();
}
|
