Skip to content

Commit 88e6e1b

Browse files
author
Gavin Barraclough
committed
Bug 58705 - DFG JIT Add support for flow control (branch, jump).
Reviewed by Geoff Garen. Add support for control flow by breaking the CodeBlock up into multiple basic blocks, generating code for each basic block in turn through the speculative JIT & then the non-speculative JIT. * dfg/DFGByteCodeParser.cpp: (JSC::DFG::ByteCodeParser::setTemporary): (JSC::DFG::ByteCodeParser::addToGraph): (JSC::DFG::ByteCodeParser::parseBlock): (JSC::DFG::ByteCodeParser::parse): * dfg/DFGGraph.cpp: (JSC::DFG::Graph::dump): * dfg/DFGGraph.h: (JSC::DFG::BasicBlock::BasicBlock): (JSC::DFG::BasicBlock::getBytecodeOffset): (JSC::DFG::Graph::blockIndexForBytecodeOffset): * dfg/DFGJITCodeGenerator.h: (JSC::DFG::JITCodeGenerator::JITCodeGenerator): (JSC::DFG::JITCodeGenerator::addBranch): (JSC::DFG::JITCodeGenerator::linkBranches): (JSC::DFG::JITCodeGenerator::BranchRecord::BranchRecord): * dfg/DFGNode.h: (JSC::DFG::Node::Node): (JSC::DFG::Node::isJump): (JSC::DFG::Node::isBranch): (JSC::DFG::Node::takenBytecodeOffset): (JSC::DFG::Node::notTakenBytecodeOffset): * dfg/DFGNonSpeculativeJIT.cpp: (JSC::DFG::NonSpeculativeJIT::compile): * dfg/DFGNonSpeculativeJIT.h: * dfg/DFGSpeculativeJIT.cpp: (JSC::DFG::SpeculativeJIT::compile): * dfg/DFGSpeculativeJIT.h: Canonical link: https://commits.webkit.org/73786@main git-svn-id: https://svn.webkit.org/repository/webkit/trunk@84045 268f45cc-cd09-0410-ab3c-d52691b4dbfc
1 parent fd0be49 commit 88e6e1b

10 files changed

Lines changed: 414 additions & 18 deletions

‎Source/JavaScriptCore/ChangeLog‎

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,42 @@
1+
2011-04-15 Gavin Barraclough <barraclough@apple.com>
2+
3+
Reviewed by Geoff Garen.
4+
5+
Bug 58705 - DFG JIT Add support for flow control (branch, jump).
6+
7+
Add support for control flow by breaking the CodeBlock up into multiple
8+
basic blocks, generating code for each basic block in turn through the
9+
speculative JIT & then the non-speculative JIT.
10+
11+
* dfg/DFGByteCodeParser.cpp:
12+
(JSC::DFG::ByteCodeParser::setTemporary):
13+
(JSC::DFG::ByteCodeParser::addToGraph):
14+
(JSC::DFG::ByteCodeParser::parseBlock):
15+
(JSC::DFG::ByteCodeParser::parse):
16+
* dfg/DFGGraph.cpp:
17+
(JSC::DFG::Graph::dump):
18+
* dfg/DFGGraph.h:
19+
(JSC::DFG::BasicBlock::BasicBlock):
20+
(JSC::DFG::BasicBlock::getBytecodeOffset):
21+
(JSC::DFG::Graph::blockIndexForBytecodeOffset):
22+
* dfg/DFGJITCodeGenerator.h:
23+
(JSC::DFG::JITCodeGenerator::JITCodeGenerator):
24+
(JSC::DFG::JITCodeGenerator::addBranch):
25+
(JSC::DFG::JITCodeGenerator::linkBranches):
26+
(JSC::DFG::JITCodeGenerator::BranchRecord::BranchRecord):
27+
* dfg/DFGNode.h:
28+
(JSC::DFG::Node::Node):
29+
(JSC::DFG::Node::isJump):
30+
(JSC::DFG::Node::isBranch):
31+
(JSC::DFG::Node::takenBytecodeOffset):
32+
(JSC::DFG::Node::notTakenBytecodeOffset):
33+
* dfg/DFGNonSpeculativeJIT.cpp:
34+
(JSC::DFG::NonSpeculativeJIT::compile):
35+
* dfg/DFGNonSpeculativeJIT.h:
36+
* dfg/DFGSpeculativeJIT.cpp:
37+
(JSC::DFG::SpeculativeJIT::compile):
38+
* dfg/DFGSpeculativeJIT.h:
39+
140
2011-04-15 Gavin Barraclough <barraclough@apple.com>
241

342
Reviewed by Geoff Garen.

‎Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp‎

Lines changed: 165 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -69,7 +69,7 @@ class ByteCodeParser {
6969

7070
private:
7171
// Parse a single basic block of bytecode instructions.
72-
bool parseBlock();
72+
bool parseBlock(unsigned limit);
7373

7474
// Get/Set the operands/result of a bytecode instruction.
7575
NodeIndex get(int operand)
@@ -150,7 +150,7 @@ class ByteCodeParser {
150150
m_parseFailed = true;
151151
return constantUndefined();
152152
}
153-
void setTemporary(int operand, NodeIndex value)
153+
void setTemporary(unsigned operand, NodeIndex value)
154154
{
155155
m_temporaries[operand] = value;
156156
}
@@ -447,6 +447,15 @@ class ByteCodeParser {
447447
m_graph.ref(resultIndex);
448448
return resultIndex;
449449
}
450+
NodeIndex addToGraph(NodeType op, OpInfo info1, OpInfo info2, NodeIndex child1 = NoNode, NodeIndex child2 = NoNode, NodeIndex child3 = NoNode)
451+
{
452+
NodeIndex resultIndex = (NodeIndex)m_graph.size();
453+
m_graph.append(Node(op, m_currentIndex, info1, info2, child1, child2, child3));
454+
455+
if (op & NodeMustGenerate)
456+
m_graph.ref(resultIndex);
457+
return resultIndex;
458+
}
450459

451460
JSGlobalData* m_globalData;
452461
CodeBlock* m_codeBlock;
@@ -517,13 +526,31 @@ class ByteCodeParser {
517526
m_currentIndex += OPCODE_LENGTH(name); \
518527
return !m_parseFailed
519528

520-
bool ByteCodeParser::parseBlock()
529+
bool ByteCodeParser::parseBlock(unsigned limit)
521530
{
531+
// No need to reset state initially, since it has been set by the constructor.
532+
if (m_currentIndex) {
533+
for (unsigned i = 0; i < m_constants.size(); ++i)
534+
m_constants[i] = ConstantRecord();
535+
for (unsigned i = 0; i < m_variables.size(); ++i)
536+
m_variables[i] = VariableRecord();
537+
for (unsigned i = 0; i < m_arguments.size(); ++i)
538+
m_arguments[i] = VariableRecord();
539+
for (unsigned i = 0; i < m_temporaries.size(); ++i)
540+
m_temporaries[i] = NoNode;
541+
}
542+
522543
AliasTracker aliases(m_graph);
523544

524545
Interpreter* interpreter = m_globalData->interpreter;
525546
Instruction* instructionsBegin = m_codeBlock->instructions().begin();
526547
while (true) {
548+
// Don't extend over jump destinations.
549+
if (m_currentIndex == limit) {
550+
addToGraph(Jump, OpInfo(m_currentIndex));
551+
return !m_parseFailed;
552+
}
553+
527554
// Switch on the current bytecode opcode.
528555
Instruction* currentInstruction = instructionsBegin + m_currentIndex;
529556
switch (interpreter->getOpcodeID(currentInstruction->u.opcode)) {
@@ -843,6 +870,116 @@ bool ByteCodeParser::parseBlock()
843870

844871
// === Block terminators. ===
845872

873+
case op_jmp: {
874+
unsigned relativeOffset = currentInstruction[1].u.operand;
875+
addToGraph(Jump, OpInfo(m_currentIndex + relativeOffset));
876+
LAST_OPCODE(op_jmp);
877+
}
878+
879+
case op_loop: {
880+
unsigned relativeOffset = currentInstruction[1].u.operand;
881+
addToGraph(Jump, OpInfo(m_currentIndex + relativeOffset));
882+
LAST_OPCODE(op_loop);
883+
}
884+
885+
case op_jtrue: {
886+
unsigned relativeOffset = currentInstruction[2].u.operand;
887+
NodeIndex condition = get(currentInstruction[1].u.operand);
888+
addToGraph(Branch, OpInfo(m_currentIndex + relativeOffset), OpInfo(m_currentIndex + OPCODE_LENGTH(op_jtrue)), condition);
889+
LAST_OPCODE(op_jtrue);
890+
}
891+
892+
case op_jfalse: {
893+
unsigned relativeOffset = currentInstruction[2].u.operand;
894+
NodeIndex condition = get(currentInstruction[1].u.operand);
895+
addToGraph(Branch, OpInfo(m_currentIndex + OPCODE_LENGTH(op_jfalse)), OpInfo(m_currentIndex + relativeOffset), condition);
896+
LAST_OPCODE(op_jfalse);
897+
}
898+
899+
case op_loop_if_true: {
900+
unsigned relativeOffset = currentInstruction[2].u.operand;
901+
NodeIndex condition = get(currentInstruction[1].u.operand);
902+
addToGraph(Branch, OpInfo(m_currentIndex + relativeOffset), OpInfo(m_currentIndex + OPCODE_LENGTH(op_loop_if_true)), condition);
903+
LAST_OPCODE(op_loop_if_true);
904+
}
905+
906+
case op_loop_if_false: {
907+
unsigned relativeOffset = currentInstruction[2].u.operand;
908+
NodeIndex condition = get(currentInstruction[1].u.operand);
909+
addToGraph(Branch, OpInfo(m_currentIndex + OPCODE_LENGTH(op_loop_if_false)), OpInfo(m_currentIndex + relativeOffset), condition);
910+
LAST_OPCODE(op_loop_if_false);
911+
}
912+
913+
case op_jeq_null: {
914+
unsigned relativeOffset = currentInstruction[2].u.operand;
915+
NodeIndex value = get(currentInstruction[1].u.operand);
916+
NodeIndex condition = addToGraph(CompareEq, value, constantNull());
917+
addToGraph(Branch, OpInfo(m_currentIndex + relativeOffset), OpInfo(m_currentIndex + OPCODE_LENGTH(op_jeq_null)), condition);
918+
LAST_OPCODE(op_jeq_null);
919+
}
920+
921+
case op_jneq_null: {
922+
unsigned relativeOffset = currentInstruction[2].u.operand;
923+
NodeIndex value = get(currentInstruction[1].u.operand);
924+
NodeIndex condition = addToGraph(CompareEq, value, constantNull());
925+
addToGraph(Branch, OpInfo(m_currentIndex + OPCODE_LENGTH(op_jneq_null)), OpInfo(m_currentIndex + relativeOffset), condition);
926+
LAST_OPCODE(op_jneq_null);
927+
}
928+
929+
case op_jnless: {
930+
unsigned relativeOffset = currentInstruction[3].u.operand;
931+
NodeIndex op1 = get(currentInstruction[1].u.operand);
932+
NodeIndex op2 = get(currentInstruction[2].u.operand);
933+
NodeIndex condition = addToGraph(CompareLess, op1, op2);
934+
addToGraph(Branch, OpInfo(m_currentIndex + OPCODE_LENGTH(op_jnless)), OpInfo(m_currentIndex + relativeOffset), condition);
935+
LAST_OPCODE(op_jnless);
936+
}
937+
938+
case op_jnlesseq: {
939+
unsigned relativeOffset = currentInstruction[3].u.operand;
940+
NodeIndex op1 = get(currentInstruction[1].u.operand);
941+
NodeIndex op2 = get(currentInstruction[2].u.operand);
942+
NodeIndex condition = addToGraph(CompareLessEq, op1, op2);
943+
addToGraph(Branch, OpInfo(m_currentIndex + OPCODE_LENGTH(op_jnlesseq)), OpInfo(m_currentIndex + relativeOffset), condition);
944+
LAST_OPCODE(op_jnlesseq);
945+
}
946+
947+
case op_jless: {
948+
unsigned relativeOffset = currentInstruction[3].u.operand;
949+
NodeIndex op1 = get(currentInstruction[1].u.operand);
950+
NodeIndex op2 = get(currentInstruction[2].u.operand);
951+
NodeIndex condition = addToGraph(CompareLess, op1, op2);
952+
addToGraph(Branch, OpInfo(m_currentIndex + relativeOffset), OpInfo(m_currentIndex + OPCODE_LENGTH(op_jless)), condition);
953+
LAST_OPCODE(op_jless);
954+
}
955+
956+
case op_jlesseq: {
957+
unsigned relativeOffset = currentInstruction[3].u.operand;
958+
NodeIndex op1 = get(currentInstruction[1].u.operand);
959+
NodeIndex op2 = get(currentInstruction[2].u.operand);
960+
NodeIndex condition = addToGraph(CompareLessEq, op1, op2);
961+
addToGraph(Branch, OpInfo(m_currentIndex + relativeOffset), OpInfo(m_currentIndex + OPCODE_LENGTH(op_jlesseq)), condition);
962+
LAST_OPCODE(op_jlesseq);
963+
}
964+
965+
case op_loop_if_less: {
966+
unsigned relativeOffset = currentInstruction[3].u.operand;
967+
NodeIndex op1 = get(currentInstruction[1].u.operand);
968+
NodeIndex op2 = get(currentInstruction[2].u.operand);
969+
NodeIndex condition = addToGraph(CompareLess, op1, op2);
970+
addToGraph(Branch, OpInfo(m_currentIndex + relativeOffset), OpInfo(m_currentIndex + OPCODE_LENGTH(op_loop_if_less)), condition);
971+
LAST_OPCODE(op_loop_if_less);
972+
}
973+
974+
case op_loop_if_lesseq: {
975+
unsigned relativeOffset = currentInstruction[3].u.operand;
976+
NodeIndex op1 = get(currentInstruction[1].u.operand);
977+
NodeIndex op2 = get(currentInstruction[2].u.operand);
978+
NodeIndex condition = addToGraph(CompareLessEq, op1, op2);
979+
addToGraph(Branch, OpInfo(m_currentIndex + relativeOffset), OpInfo(m_currentIndex + OPCODE_LENGTH(op_loop_if_lesseq)), condition);
980+
LAST_OPCODE(op_loop_if_lesseq);
981+
}
982+
846983
case op_ret: {
847984
addToGraph(Return, get(currentInstruction[1].u.operand));
848985

@@ -866,8 +1003,31 @@ bool ByteCodeParser::parseBlock()
8661003

8671004
bool ByteCodeParser::parse()
8681005
{
869-
if (!parseBlock())
870-
return false;
1006+
// Set during construction.
1007+
ASSERT(!m_currentIndex);
1008+
1009+
for (unsigned jumpTargetIndex = 0; jumpTargetIndex <= m_codeBlock->numberOfJumpTargets(); ++jumpTargetIndex) {
1010+
// The maximum bytecode offset to go into the current basicblock is either the next jump target, or the end of the instructions.
1011+
unsigned limit = jumpTargetIndex < m_codeBlock->numberOfJumpTargets() ? m_codeBlock->jumpTarget(jumpTargetIndex) : m_codeBlock->instructions().size();
1012+
ASSERT(m_currentIndex < limit);
1013+
1014+
// Loop until we reach the current limit (i.e. next jump target).
1015+
do {
1016+
unsigned bytecodeBegin = m_currentIndex;
1017+
NodeIndex begin = m_graph.size();
1018+
1019+
if (!parseBlock(limit))
1020+
return false;
1021+
// We should not have gone beyond the limit.
1022+
ASSERT(m_currentIndex <= limit);
1023+
1024+
NodeIndex end = m_graph.size();
1025+
m_graph.m_blocks.append(BasicBlock(bytecodeBegin, begin, end));
1026+
} while (m_currentIndex < limit);
1027+
}
1028+
1029+
// Should have reached the end of the instructions.
1030+
ASSERT(m_currentIndex == m_codeBlock->instructions().size());
8711031

8721032
// Assign VirtualRegisters.
8731033
ScoreBoard scoreBoard(m_graph, m_variables.size());

‎Source/JavaScriptCore/dfg/DFGGraph.cpp‎

Lines changed: 14 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -110,14 +110,26 @@ void Graph::dump(NodeIndex nodeIndex, CodeBlock* codeBlock)
110110
printf("%s$%u", hasPrinted ? ", " : "", node.constantNumber());
111111
hasPrinted = true;
112112
}
113+
if (node.isBranch() || node.isJump()) {
114+
printf("%sT:#%u", hasPrinted ? ", " : "", blockIndexForBytecodeOffset(node.takenBytecodeOffset()));
115+
hasPrinted = true;
116+
}
117+
if (node.isBranch()) {
118+
printf("%sF:#%u", hasPrinted ? ", " : "", blockIndexForBytecodeOffset(node.notTakenBytecodeOffset()));
119+
hasPrinted = true;
120+
}
113121

114122
printf(")\n");
115123
}
116124

117125
void Graph::dump(CodeBlock* codeBlock)
118126
{
119-
for (size_t i = 0; i < size(); ++i)
120-
dump(i, codeBlock);
127+
for (size_t b = 0; b < m_blocks.size(); ++b) {
128+
printf("Block #%u:\n", (int)b);
129+
BasicBlock& block = m_blocks[b];
130+
for (size_t i = block.begin; i < block.end; ++i)
131+
dump(i, codeBlock);
132+
}
121133
}
122134

123135
#endif

‎Source/JavaScriptCore/dfg/DFGGraph.h‎

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -30,13 +30,34 @@
3030

3131
#include <dfg/DFGNode.h>
3232
#include <wtf/Vector.h>
33+
#include <wtf/StdLibExtras.h>
3334

3435
namespace JSC {
3536

3637
class CodeBlock;
3738

3839
namespace DFG {
3940

41+
typedef uint32_t BlockIndex;
42+
43+
struct BasicBlock {
44+
BasicBlock(unsigned bytecodeBegin, NodeIndex begin, NodeIndex end)
45+
: bytecodeBegin(bytecodeBegin)
46+
, begin(begin)
47+
, end(end)
48+
{
49+
}
50+
51+
static inline BlockIndex getBytecodeBegin(BasicBlock* block)
52+
{
53+
return block->bytecodeBegin;
54+
}
55+
56+
unsigned bytecodeBegin;
57+
NodeIndex begin;
58+
NodeIndex end;
59+
};
60+
4061
//
4162
// === Graph ===
4263
//
@@ -68,6 +89,16 @@ class Graph : public Vector<Node, 64> {
6889
void dump(NodeIndex, CodeBlock* = 0);
6990
#endif
7091

92+
Vector<BasicBlock> m_blocks;
93+
94+
BlockIndex blockIndexForBytecodeOffset(unsigned bytecodeBegin)
95+
{
96+
BasicBlock* begin = m_blocks.begin();
97+
BasicBlock* block = binarySearch<BasicBlock, unsigned, BasicBlock::getBytecodeBegin>(begin, m_blocks.size(), bytecodeBegin);
98+
ASSERT(block >= m_blocks.begin() && block < m_blocks.end());
99+
return static_cast<BlockIndex>(block - begin);
100+
}
101+
71102
private:
72103
// When a node's refCount goes from 0 to 1, it must (logically) recursively ref all of its children, and vice versa.
73104
void refChildren(NodeIndex);

‎Source/JavaScriptCore/dfg/DFGJITCodeGenerator.h‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -151,6 +151,7 @@ class JITCodeGenerator {
151151
, m_isSpeculative(isSpeculative)
152152
, m_compileIndex(0)
153153
, m_generationInfo(m_jit.codeBlock()->m_numCalleeRegisters)
154+
, m_blockHeads(jit.graph().m_blocks.size())
154155
{
155156
}
156157

@@ -670,6 +671,19 @@ class JITCodeGenerator {
670671
m_jit.appendCallWithExceptionCheck(function, m_jit.graph()[m_compileIndex].exceptionInfo);
671672
}
672673

674+
void addBranch(const MacroAssembler::Jump& jump, BlockIndex destination)
675+
{
676+
m_branches.append(BranchRecord(jump, destination));
677+
}
678+
679+
void linkBranches()
680+
{
681+
for (size_t i = 0; i < m_branches.size(); ++i) {
682+
BranchRecord& branch = m_branches[i];
683+
branch.jump.linkTo(m_blockHeads[branch.destination], &m_jit);
684+
}
685+
}
686+
673687
#ifndef NDEBUG
674688
void dump(const char* label = 0);
675689
#endif
@@ -694,11 +708,25 @@ class JITCodeGenerator {
694708
// the value may have been boxed differently on the two paths.
695709
bool m_isSpeculative;
696710
// The current node being generated.
711+
BlockIndex m_block;
697712
NodeIndex m_compileIndex;
698713
// Virtual and physical register maps.
699714
Vector<GenerationInfo, 32> m_generationInfo;
700715
RegisterBank<GPRReg, numberOfGPRs, SpillOrder, SpillOrderNone, SpillOrderMax> m_gprs;
701716
RegisterBank<FPRReg, numberOfFPRs, SpillOrder, SpillOrderNone, SpillOrderMax> m_fprs;
717+
718+
Vector<MacroAssembler::Label> m_blockHeads;
719+
struct BranchRecord {
720+
BranchRecord(MacroAssembler::Jump jump, BlockIndex destination)
721+
: jump(jump)
722+
, destination(destination)
723+
{
724+
}
725+
726+
MacroAssembler::Jump jump;
727+
BlockIndex destination;
728+
};
729+
Vector<BranchRecord, 8> m_branches;
702730
};
703731

704732
// === Operand types ===

0 commit comments

Comments
 (0)