Skip to content

Commit 09e5897

Browse files
maximecbmaximecb
authored
Merge pull request ruby#146 from Shopify/ir
Get some tests passing with the new backend
2 parents 5d290a0 + 13253b8 commit 09e5897

File tree

1 file changed

+201
-67
lines changed

1 file changed

+201
-67
lines changed

‎yjit_backend.c‎

Lines changed: 201 additions & 67 deletions
Original file line numberDiff line numberDiff line change
@@ -39,11 +39,13 @@ ir_opnd_t ir_mem(uint8_t num_bits, ir_opnd_t base, int32_t disp)
3939
};
4040
}
4141

42+
typedef rb_darray(int32_t) live_ranges_t;
43+
4244
// Fake/temporaty JIT state object for testing/experimenting
4345
typedef struct yjit_jit_state
4446
{
4547
insn_array_t insns;
46-
48+
live_ranges_t live_ranges;
4749
} jitstate_t;
4850

4951
ir_opnd_t push_insn_variadic(jitstate_t* jit, ...)
@@ -57,14 +59,18 @@ ir_opnd_t push_insn_variadic(jitstate_t* jit, ...)
5759
RUBY_ASSERT(op >= 0);
5860
RUBY_ASSERT(op < OP_MAX);
5961

60-
ir_insn_t insn = (ir_insn_t){
61-
.op = op
62-
};
62+
ir_insn_t insn = (ir_insn_t){ .op = op };
63+
int32_t insn_index = rb_darray_size(jit->insns);
6364

6465
// For each operand
6566
for (size_t opnd_idx = 0;; ++opnd_idx) {
6667
ir_opnd_t opnd = va_arg(args, ir_opnd_t);
6768

69+
// If this operand is the output of a previous instruction, then update
70+
// the end of the live range
71+
if (opnd.kind == EIR_INSN_OUT)
72+
rb_darray_set(jit->live_ranges, opnd.as.idx, insn_index);
73+
6874
// End of the operand list
6975
if (opnd.kind == EIR_VOID)
7076
break;
@@ -79,29 +85,18 @@ ir_opnd_t push_insn_variadic(jitstate_t* jit, ...)
7985

8086
rb_darray_append(&jit->insns, insn);
8187

88+
// Set the initial lifetime of the output of this instruction to just be the
89+
// current index (as we haven't seen it live beyond that).
90+
rb_darray_append(&jit->live_ranges, insn_index);
91+
8292
// Return an operand which is the output of this instruction
83-
return (ir_opnd_t) {
84-
.kind = EIR_INSN_OUT,
85-
.as.idx = rb_darray_size(jit->insns) - 1
86-
};
93+
return (ir_opnd_t) { .kind = EIR_INSN_OUT, .as.idx = insn_index };
8794
}
8895

8996
// We use a dummy IR_VOID argument to signal the end of the operands
9097
// Not super safe, but it's the best way I found to deal with the limitations of C99
9198
#define push_insn(jit, ...) push_insn_variadic(jit, __VA_ARGS__, IR_VOID)
9299

93-
const char* ir_op_name(int op)
94-
{
95-
switch (op)
96-
{
97-
case OP_ADD: return "add";
98-
case OP_MOV: return "mov";
99-
100-
default:
101-
rb_bug("unknown opnd type");
102-
}
103-
}
104-
105100
bool ir_opnd_eq(ir_opnd_t opnd0, ir_opnd_t opnd1)
106101
{
107102
if (opnd0.num_bits != opnd1.num_bits)
@@ -115,7 +110,11 @@ bool ir_opnd_eq(ir_opnd_t opnd0, ir_opnd_t opnd1)
115110
return true;
116111
}
117112

118-
void print_ir_reg(ir_reg_t reg)
113+
/*************************************************/
114+
/* Methods for disassembling the instructions. */
115+
/*************************************************/
116+
117+
void ir_print_reg(ir_reg_t reg)
119118
{
120119
if (reg.special)
121120
{
@@ -137,41 +136,59 @@ void print_ir_reg(ir_reg_t reg)
137136
}
138137

139138
// Print an IR operand
140-
void print_ir_opnd(ir_opnd_t opnd)
139+
void ir_print_opnd(ir_opnd_t opnd)
141140
{
142141
switch (opnd.kind)
143142
{
144143
case EIR_REG:
145-
print_ir_reg(opnd.as.reg);
146-
return;
144+
ir_print_reg(opnd.as.reg);
145+
return;
147146

148147
case EIR_MEM:
149-
printf("%db[", (int)opnd.num_bits);
150-
print_ir_reg(opnd.as.mem.base);
151-
if (opnd.as.mem.disp > 0)
152-
printf(" + %d]", opnd.as.mem.disp);
153-
else
154-
printf("]");
155-
return;
148+
printf("%db[", (int)opnd.num_bits);
149+
ir_print_reg(opnd.as.mem.base);
150+
if (opnd.as.mem.disp > 0)
151+
printf(" + %d]", opnd.as.mem.disp);
152+
else
153+
printf("]");
154+
return;
156155

157156
case EIR_IMM:
158-
printf("%lld", (long long)opnd.as.imm);
159-
return;
157+
printf("%lld", (long long)opnd.as.imm);
158+
return;
159+
160+
case EIR_INSN_OUT:
161+
printf("[%d]", opnd.as.idx);
162+
return;
163+
164+
default:
165+
RUBY_ASSERT(false && "unknown opnd type");
166+
}
167+
}
168+
169+
const char* ir_op_name(int op)
170+
{
171+
switch (op)
172+
{
173+
case OP_ADD: return "add";
174+
case OP_MOV: return "mov";
175+
case OP_RET: return "ret";
160176

161177
default:
162-
RUBY_ASSERT(false && "unknown opnd type");
178+
RUBY_ASSERT(false && "unknown opnd type");
163179
}
164180
}
165181

166182
// Print a list of instructions to stdout for debugging
167-
void print_ir_insns(insn_array_t insns)
183+
void ir_print_insns(jitstate_t *jit)
168184
{
169185
// For each instruction
170-
rb_darray_for(insns, insn_idx)
186+
rb_darray_for(jit->insns, insn_idx)
171187
{
172-
ir_insn_t insn = rb_darray_get(insns, insn_idx);
188+
ir_insn_t insn = rb_darray_get(jit->insns, insn_idx);
189+
int32_t live_range = rb_darray_get(jit->live_ranges, insn_idx);
173190

174-
printf("%s", ir_op_name(insn.op));
191+
printf("[%d] %s", insn_idx, ir_op_name(insn.op));
175192

176193
// For each operand
177194
rb_darray_for(insn.opnds, opnd_idx)
@@ -182,60 +199,177 @@ void print_ir_insns(insn_array_t insns)
182199
printf(",");
183200
printf(" ");
184201

185-
print_ir_opnd(opnd);
202+
ir_print_opnd(opnd);
186203
}
187204

188-
printf(";\n");
189-
}
190-
}
191-
192-
// Test code
193-
void test_backend()
194-
{
195-
// Object we generate code into, holds a list of IR instructions
196-
jitstate_t jit_struct = (jitstate_t){ 0 };
197-
jitstate_t* jit = &jit_struct;
198-
199-
200-
201-
202-
// This is going to need scratch register allocation
203-
ir_opnd_t opnd0 = push_insn(jit, OP_MOV, IR_REG(RAX), ir_imm(1));
204-
ir_opnd_t opnd1 = push_insn(jit, OP_MOV, IR_REG(RCX), ir_imm(2));
205-
ir_opnd_t add0 = push_insn(jit, OP_ADD, opnd0, opnd1);
206-
push_insn(jit, OP_RET, add0);
207-
208-
209-
//print_ir_insns(jit->insns);
210-
211-
212-
213-
214-
215-
205+
printf(";");
216206

207+
// If the output of this instruction lives beyond it, then output how
208+
// long it will stay alive.
209+
if (live_range != insn_idx)
210+
printf(" (live until [%d])", live_range);
217211

212+
printf("\n");
213+
}
214+
}
218215

216+
/*************************************************/
217+
/* Convenience methods for pushing instructions. */
218+
/*************************************************/
219219

220+
ir_opnd_t ir_add(jitstate_t *jit, ir_opnd_t dest, ir_opnd_t src)
221+
{
222+
return push_insn(jit, OP_ADD, dest, src);
223+
}
220224

225+
ir_opnd_t ir_mov(jitstate_t *jit, ir_opnd_t dest, ir_opnd_t src)
226+
{
227+
return push_insn(jit, OP_MOV, dest, src);
228+
}
221229

230+
void ir_ret(jitstate_t *jit)
231+
{
232+
push_insn(jit, OP_RET);
233+
}
222234

235+
/*************************************************/
236+
/* Generate x86 code from the IR. */
237+
/*************************************************/
223238

239+
x86opnd_t ir_x86_opnd(insn_array_t insns, ir_opnd_t opnd)
240+
{
241+
switch (opnd.kind)
242+
{
243+
case EIR_REG:
244+
return (x86opnd_t){ OPND_REG, 64, .as.reg = { REG_GP, opnd.as.reg.idx } };
245+
case EIR_IMM:
246+
return (x86opnd_t){ OPND_IMM, opnd.num_bits, .as.imm = opnd.as.imm };
247+
case EIR_INSN_OUT: {
248+
// Temporary cheating way of handling register allocation that will
249+
// only work for certain instructions.
250+
ir_insn_t insn = rb_darray_get(insns, opnd.as.idx);
251+
return ir_x86_opnd(insns, rb_darray_get(insn.opnds, 0));
252+
}
253+
default:
254+
RUBY_ASSERT(false && "unknown opnd kind");
255+
}
256+
}
224257

258+
// Fetch a free scratch register and mark it as active.
259+
int32_t ir_next_scratch(bool active[NUM_SCR_REGS])
260+
{
261+
for (int32_t index = 0; index < NUM_SCR_REGS; index++) {
262+
if (!active[index]) {
263+
return index;
264+
}
265+
}
266+
RUBY_ASSERT(false && "out of free registers");
267+
}
225268

269+
// Write out x86 instructions into the codeblock for the given IR instructions
270+
void ir_x86_insns(codeblock_t *cb, insn_array_t insns)
271+
{
272+
// Initialize a list of booleans that corresponds to whether or not the
273+
// register at that given index is currently active.
274+
// bool active[NUM_SCR_REGS];
275+
// for (int32_t index = 0; index < NUM_SCR_REGS; index++)
276+
// active[index] = false;
226277

278+
cb_set_pos(cb, 0);
227279

280+
rb_darray_for(insns, insn_idx)
281+
{
282+
ir_insn_t insn = rb_darray_get(insns, insn_idx);
228283

284+
switch (insn.op) {
285+
case OP_ADD:
286+
add(cb, ir_x86_opnd(insns, rb_darray_get(insn.opnds, 0)), ir_x86_opnd(insns, rb_darray_get(insn.opnds, 1)));
287+
break;
288+
case OP_MOV:
289+
mov(cb, ir_x86_opnd(insns, rb_darray_get(insn.opnds, 0)), ir_x86_opnd(insns, rb_darray_get(insn.opnds, 1)));
290+
break;
291+
case OP_RET:
292+
ret(cb);
293+
break;
294+
default:
295+
RUBY_ASSERT(false && "unsupported insn op");
296+
}
297+
}
298+
}
229299

300+
void ir_print_to_dot(insn_array_t insns)
301+
{
302+
printf("digraph {\n");
230303

304+
rb_darray_for(insns, insn_idx)
305+
{
306+
ir_insn_t insn = rb_darray_get(insns, insn_idx);
307+
printf(" %d [label=\"[%d] %s\"];\n", insn_idx, insn_idx, ir_op_name(insn.op));
231308

309+
rb_darray_for(insn.opnds, opnd_idx)
310+
{
311+
ir_opnd_t opnd = rb_darray_get(insn.opnds, opnd_idx);
312+
if (opnd.kind == EIR_INSN_OUT) {
313+
printf(" %d -> %d\n", opnd.as.idx, insn_idx);
314+
}
315+
}
316+
}
232317

318+
printf("}\n");
319+
}
233320

321+
/*************************************************/
322+
/* Tests for the backend. */
323+
/*************************************************/
234324

325+
void test_backend()
326+
{
327+
jitstate_t jitstate;
328+
jitstate_t* jit = &jitstate;
329+
330+
codeblock_t codeblock;
331+
codeblock_t* cb = &codeblock;
332+
333+
uint8_t* mem_block = alloc_exec_mem(4096);
334+
cb_init(cb, mem_block, 4096);
335+
336+
int (*function)(void);
337+
function = (int (*)(void))mem_block;
338+
339+
printf("Running backend tests\n");
340+
341+
// Used by the tests to compare function outputs.
342+
int64_t expected, actual;
343+
344+
// A macro for defining test cases. Will set up a jitstate, execute the body
345+
// which should create the IR, generate x86 from the IR, and execute it.
346+
#define TEST(NAME, EXPECTED, BODY) \
347+
jitstate = (jitstate_t){ 0 }; \
348+
BODY \
349+
ir_x86_insns(cb, jit->insns); \
350+
expected = EXPECTED; \
351+
actual = function(); \
352+
if (expected != actual) { \
353+
fprintf(stderr, "%s failed: expected %lld, got %lld\n", NAME, expected, actual); \
354+
exit(-1); \
355+
}
235356

357+
TEST("adding with registers", 7, {
358+
ir_opnd_t opnd0 = ir_mov(jit, IR_REG(RAX), ir_imm(3));
359+
ir_opnd_t opnd1 = ir_mov(jit, IR_REG(RCX), ir_imm(4));
360+
ir_mov(jit, IR_REG(RAX), ir_add(jit, opnd0, opnd1));
361+
ir_ret(jit);
362+
})
236363

364+
TEST("adding with a register and an immediate", 7, {
365+
ir_opnd_t opnd0 = ir_mov(jit, IR_REG(RAX), ir_imm(3));
366+
ir_mov(jit, IR_REG(RAX), ir_add(jit, opnd0, ir_imm(4)));
367+
ir_ret(jit);
368+
})
237369

370+
#undef TEST
238371

372+
printf("Backend tests done\n");
239373

240374
// This is a rough sketch of what codegen could look like, you can ignore/delete it
241375
/*

0 commit comments

Comments
 (0)