# New Ticket Created by Angel Faus
# Please include the string: [perl #819]
# in the subject line of all future correspondence about this issue.
# <URL: http://bugs6.perl.org/rt2/Ticket/Display.html?id=819 >
Hi Melvin,
This patch does the following things:
- It includes patch #813 from Sean O'Rourke
- It fixes another bug in spill(), who was generating bad code
- It adds a bunch of work using the control-flow graph, analyzing the
exact places of the code where a variable is alive, and using this in
order to improve the interference analysis.
Incidentally, while tracking a memory bug, I added code to check the
results of all malloc calls. I've left it there, since it shouldn't
hurt.
I am sending you this through bugs-parrot, as people on the IRC
channel suggested.
Best,
-àngel
[EMAIL PROTECTED]
-- attachment 1 ------------------------------------------------------
url: http://bugs6.perl.org/rt2/attach/3858/3565/a26fc6/patch_cfg.diff
-- attachment 2 ------------------------------------------------------
url: http://bugs6.perl.org/rt2/attach/3858/3566/337423/test_cfg.imc
RCS file: /cvs/public/parrot/languages/imcc/cfg.c,v
retrieving revision 1.1
diff -r1.1 cfg.c
28c28
<
---
>
30a31
> ins = NULL;
41,42c42,45
< bb->end = ins;
< bb = make_basic_block(next);
---
> if (ins != NULL) {
> bb->end = ins;
> bb = make_basic_block(next);
> }
121a125,128
> if (e==NULL) {
> fprintf(stderr, "Memory error at bb_add_edge\n");
> abort();
> }
131a139,310
>
> void life_analysis() {
> int i;
>
> for(i = 0; i < HASH_SIZE; i++) {
> SymReg * r = hash[i];
> for(; r; r = r->next) {
> if (r->type == VTIDENTIFIER)
> analyse_life_symbol(r);
> }
> }
> }
>
> void analyse_life_symbol(SymReg* r) {
> int i;
>
> r->life_info = calloc(n_basic_blocks, sizeof(Life_range*));
> if (r->life_info == NULL) {
> fprintf(stderr, "Memory error at analyse_life_symbol");
> abort();
> }
>
> /* First we make a pass to each block to gather the information
> * that can be obtained locally */
>
> for (i=0; i < n_basic_blocks; i++) {
> analyse_life_block(bb_list[i], r);
> }
>
> /* Now we need to consider the relations between blocks */
>
> for (i=0; i < n_basic_blocks; i++) {
> if (r->life_info[i]->flags & LF_use) {
>
> /* This block uses r, so it must be live at
> the beggining */
> r->life_info[i]->flags |= LF_lv_in;
>
> /* propagate this info to every predecessor */
> propagate_need (bb_list[i], r);
> }
> }
> }
>
> /* analyse_life_block studies the state of the var r
> * in the block bb.
> *
> * Its job is to set the flags LF_use, or LF_read,
> * and record the intervals inside the block where
> * the var is alive.
> */
>
> void analyse_life_block(Basic_block* bb, SymReg* r) {
> int i, write_pos, read_pos;
> Instruction* ins;
> Life_range* l;
>
> l = make_life_range(r, bb->index);
> write_pos = -1;
> read_pos = -1;
>
> for (i=bb->start->index; i < bb->end->index; i++) {
> ins = instructions[i];
> if (ins==NULL) {
> fprintf(stderr, "Index %i of %i has NULL instruction\n",
> i, bb->end->index);
> fprintf(stderr, "Total numb. of instructions = %li\n",
> n_instructions);
> abort();
> }
> if (instruction_reads(ins, r)) {
> if (l->flags != LF_def) {
>
> /* we read before having written before, so the var was
> * live at the beggining of the block */
> write_pos = bb->start->index;
> l->flags = LF_use;
> }
> read_pos = i;
> }
>
> if (instruction_writes(ins, r)) {
> if (write_pos < 0) {
> l->flags = LF_def;
> write_pos = i;
> }
> else if (read_pos < 0) {
> /* there has not been any read until here, so the previous write
> * is irrelevant */
> write_pos = i;
> }
> else {
> /* this is new writing, after some reading */
> add_life_interval(l, write_pos, read_pos);
> read_pos = -1;
> write_pos = i;
> }
> }
> }
>
> /* At the end, we need to add the last range */
> if (read_pos < 0) read_pos = write_pos;
>
> if (write_pos >= 0)
> add_life_interval(l, write_pos, read_pos);
>
>
> /* The read_pos can latter be extended if it turns out
> * that another block needs the value resulting of this
> * computation */
> }
>
> /* add_life_interval records a new range of use of the var
> * and set the LF_lv_inside flag
> */
>
> void add_life_interval(Life_range *l, int from, int to) {
> int length = l->n_intervals;
>
> l->intervals = realloc(l->intervals, (length + 2) * sizeof(int) + 1);
> if (l->intervals == NULL) {
> fprintf(stderr, "Memory error at add_life_interval\n");
> abort();
> }
>
> l->intervals[length*2] = from;
> l->intervals[length*2 + 1] = to;
>
> l->n_intervals = length + 1;
>
> l->flags |= LF_lv_inside;
>
> }
>
>
> void propagate_need(Basic_block *bb, SymReg* r) {
> Edge *edge;
> Basic_block *pred;
> Life_range *l;
>
> /* every predecessor of a LF_lv_in block must be in LF_lv_out
> and, unless itself is LV_def, this should be propagated to
> its predecessors themselves */
>
> for (edge=bb->pred_list; edge!=NULL; edge=edge->pred_next) {
> pred = edge->from;
> l = r->life_info[pred->index];
>
> if (l->flags & LF_lv_out) {
> /* this node has already been visited. Ignore it */
> }
> else {
> l->flags |= LF_lv_out;
>
> if (l->flags & LF_lv_inside) {
> /* we expand the last interval to the end */
> l->intervals[l->n_intervals * 2 - 1] = pred->end->index;
> }
>
> if (! (l->flags & LF_def) ) {
> l->flags |= LF_lv_in;
> if (! (l->flags & LF_lv_inside) ) {
> l->flags |= LF_lv_all | LF_lv_inside;
> }
>
> propagate_need(pred, r);
> }
> }
> }
> }
>
>
136,137c315,316
< if (bb_list == NULL) {
< free(bb_list);
---
> if (bb_list != NULL) {
> free(bb_list);
157a337,340
> if (bb==NULL) {
> fprintf(stderr, "Memory error at make_basic_block\n");
> abort();
> }
171a355,370
> Life_range* make_life_range(SymReg *r, int index) {
> Life_range *l;
>
> l = malloc(sizeof(Life_range));
> if (l==NULL) {
> fprintf(stderr, "Memory Error at make_life_range\n");
> abort();
> }
>
> l->flags = 0;
> l->n_intervals = 0;
> l->intervals = NULL;
>
> r->life_info[index] = l;
> return l;
> }
Index: cfg.h
===================================================================
RCS file: /cvs/public/parrot/languages/imcc/cfg.h,v
retrieving revision 1.1
diff -r1.1 cfg.h
23d22
<
35a35,40
> void life_analysis();
> void analyse_life_symbol(SymReg*);
> void analyse_life_block(Basic_block*, SymReg*);
> void add_life_interval(Life_range*, int, int);
> void propagate_need(Basic_block*, SymReg*);
>
38a44
> Life_range* make_life_range(SymReg*, int);
Index: debug.c
===================================================================
RCS file: /cvs/public/parrot/languages/imcc/debug.c,v
retrieving revision 1.1
diff -r1.1 debug.c
15c15
< fprintf(stderr, "%d\t", bb->index);
---
> fprintf(stderr, "%i\t%d\t", ins->index, bb->index);
60a61,104
> dump_liveness_status();
>
> }
>
> void dump_liveness_status() {
> int i;
>
> fprintf(stderr, "\nSymbols:\n--------------------------------------\n");
> for(i = 0; i < HASH_SIZE; i++) {
> SymReg * r = hash[i];
> for(; r; r = r->next) {
> if (r->type == VTIDENTIFIER) dump_liveness_status_var(r);
> }
> }
> fprintf(stderr, "\n");
>
> }
>
>
> void dump_liveness_status_var(SymReg* r) {
> int i, j;
> Life_range *l;
>
> fprintf(stderr, "\nSymbol %s:", r->name);
> if (r->life_info==NULL) return;
> for (i=0; i<n_basic_blocks; i++) {
> l = r->life_info[i];
>
> if (l->flags & LF_lv_all) {
> fprintf(stderr, "\n\t%i:ALL\t", i);
> }
> else if (l->flags & LF_lv_inside) {
> fprintf(stderr, "\n\t%i:", i);
>
> if (l->flags & LF_lv_in) fprintf(stderr, "IN\t");
> if (l->flags & LF_lv_out) fprintf(stderr, "OUT\t");
>
> for (j=0; j < l->n_intervals; j++) {
> fprintf(stderr, "[%d,%d]\t",
> l->intervals[2*j], l->intervals[2*j+1] );
> }
> }
> }
> fprintf(stderr, "\n");
64c108
< int x, y, cnt;
---
> int x, y, cnt;
Index: debug.h
===================================================================
RCS file: /cvs/public/parrot/languages/imcc/debug.h,v
retrieving revision 1.1
diff -r1.1 debug.h
5a6,7
> void dump_liveness_status();
> void dump_liveness_status_var();
Index: imc.c
===================================================================
RCS file: /cvs/public/parrot/languages/imcc/imc.c,v
retrieving revision 1.9
diff -r1.9 imc.c
41c41
< /*life_analysis();*/
---
> life_analysis();
98c98,103
< for(i = 0; i < HASH_SIZE; i++) {
---
> if (interference_graph == NULL) {
> fprintf(stderr, "Memory error at build_interference_graph\n");
> abort();
> }
>
> for(i = 0; i < HASH_SIZE; i++) {
123c128
< dump_interference_graph();
---
> /*dump_interference_graph();*/
149a155,159
> /* We currently decide that two vars interfere if they are both alive
> * at any point. This could be improved, requiring that one is alive
> * at the point of _definition_ of the other.
> */
>
150a161,162
> int i;
>
170a183,211
> /* Now: */
>
> for (i=0; i <n_basic_blocks; i++) {
> Life_range *l0, *l1;
>
> if ( (l0->flags & LF_lv_all && l1->flags & LF_lv_inside)
> || (l0->flags & LF_lv_inside && l1->flags & LF_lv_all)
> || (l0->flags & LF_lv_in && l1->flags & LF_lv_in)
> || (l0->flags & LF_lv_out && l1->flags & LF_lv_out)
> )
> return 1;
>
> if (l0->flags & LF_lv_inside && l1->flags & LF_lv_inside) {
> /* we need to compare the intervals */
> int i, j;
> for (i=0; i < l0->n_intervals; i++) {
> for (j=0; j < l1->n_intervals; j++) {
> if (l0->intervals[i] >= l1->intervals[j+1] )
> continue;
>
> if (l0->intervals[i+1] <= l1->intervals[j] )
> continue;
>
> return 1;
> }
> }
> }
> }
>
183c224
< int simplify (SymReg **g){
---
> int simplify (){
185a227
> SymReg **g;
186a229,230
> g = interference_graph;
>
191c235
<
---
>
345,346c389,390
< Instruction ** new_instructions;
<
---
> Instruction ** old_instructions;
> int old_n_instructions;
348,349c392,394
< int i, j, needs_fetch, needs_store, needs_spilling, after_spilled, after_needs_store;
< SymReg *new_symbol, *old_symbol;
---
> int i, j;
> int needs_fetch, needs_store, needs_spilling, after_spilled, after_needs_store;
> SymReg *new_symbol, *old_symbol;
352d396
< SymReg **g = interference_graph;
353a398,401
> if (buf == NULL) {
> fprintf(stderr, "Memory error at spill\n");
> abort();
> }
356c404
< fprintf(stderr, "#Spilling [%s]:\n", g[spilled]->name);
---
> fprintf(stderr, "#Spilling [%s]:\n", interference_graph[spilled]->name);
358c406,409
< old_symbol = g[spilled];
---
> old_symbol = interference_graph[spilled];
> old_instructions = instructions;
> old_n_instructions = n_instructions;
> instructions = NULL;
362d412
< new_instructions = calloc(4096, sizeof(Instruction *));
369,370c419,420
< for(i = 0; i < n_instructions; i++) {
< tmp = instructions[i];
---
> for(i = 0; i < old_n_instructions; i++) {
> tmp = old_instructions[i];
375,403c425,426
< if (tmp->r0 == old_symbol) {
< if (tmp->flags & IF_r0_read) needs_fetch = 1;
< if (tmp->flags & IF_r0_write) needs_store = 1;
<
< tmp->r0 = new_symbol;
< }
<
< if (tmp->r1 == old_symbol) {
< if (tmp->flags & IF_r1_read) needs_fetch = 1;
< if (tmp->flags & IF_r1_write) needs_store = 1;
<
< tmp->r1 = new_symbol;
< }
<
<
< if (tmp->r2 == old_symbol) {
< if (tmp->flags & IF_r2_read) needs_fetch = 1;
< if (tmp->flags & IF_r2_write) needs_store = 1;
<
< tmp->r2 = new_symbol;
< }
<
<
< if (tmp->r3 == old_symbol) {
< if (tmp->flags & IF_r3_read) needs_fetch = 1;
< if (tmp->flags & IF_r3_write) needs_store = 1;
<
< tmp->r3 = new_symbol;
< }
---
> if (instruction_reads (tmp, old_symbol) )
> needs_fetch = 1;
404a428,430
> if (instruction_writes (tmp, old_symbol) )
> needs_store = 1;
>
409,413c435,436
< sprintf(buf, "set %s, P31, %d #FETCH", "%s", n_spilled); /*ouch*/
<
< new_instructions[j++] = mk_instruction(
< buf, new_symbol, NULL, NULL, NULL, IF_r1_write);
<
---
> sprintf(buf, "set %s, P31[%d], #FETCH", "%s", n_spilled); /*ouch*/
> emitb( mk_instruction(buf, new_symbol, NULL, NULL, NULL, IF_r1_write));
418,421c441,442
< sprintf(buf, "set P31, %d, %s #STORE", n_spilled, "%s"); /*ouch, ouch*/
<
< new_instructions[j++] = mk_instruction(
< buf, new_symbol, NULL, NULL, NULL, IF_r1_write);
---
> sprintf(buf, "set P31[%d], %s #STORE", n_spilled, "%s"); /*ouch, ouch*/
> emitb ( mk_instruction(buf, new_symbol, NULL, NULL, NULL, IF_r1_read));
424c445
< new_symbol = mk_symreg(buf, old_symbol->set);
---
> new_symbol = mk_ident(buf, old_symbol->set);
427c448,463
< new_instructions[j++] = tmp;
---
> /* Emit the old instruction, with the symbol changed */
> {
> SymReg *r0, *r1, *r2, *r3;
>
> r0 = tmp->r0;
> r1 = tmp->r1;
> r2 = tmp->r2;
> r3 = tmp->r3;
>
> if (r0==old_symbol) r0=new_symbol;
> if (r1==old_symbol) r1=new_symbol;
> if (r2==old_symbol) r2=new_symbol;
> if (r3==old_symbol) r3=new_symbol;
>
> emitb( mk_instruction(tmp->fmt, r0, r1, r2, r3, tmp->flags) );
> }
432,434c468
< free(instructions);
< instructions = new_instructions;
< n_instructions = j;
---
> free(old_instructions);
441a476,477
>
> dump_instructions();
467a504,507
> if (copy == NULL) {
> fprintf(stderr, "Memory error at str_dup\n");
> abort();
> }
474a515,518
> if (s3 == NULL) {
> fprintf(stderr, "Memory error at str_cat\n");
> abort();
> }
Index: imc.h
===================================================================
RCS file: /cvs/public/parrot/languages/imcc/imc.h,v
retrieving revision 1.8
diff -r1.8 imc.h
39c39
< int n_spill;
---
> int n_spilled;
Index: instructions.c
===================================================================
RCS file: /cvs/public/parrot/languages/imcc/instructions.c,v
retrieving revision 1.1
diff -r1.1 instructions.c
31a32,35
> if (i == NULL) {
> fprintf(stderr, "Memory error at mk_instruction\n");
> abort();
> }
51a56,92
> int instruction_reads(Instruction* ins, SymReg* r) {
> int f;
>
> if (ins == NULL) {
> fprintf(stderr, "Internal error: instruction_reads called with NULL argument\n");
> abort();
> }
>
> f = ins->flags;
>
> if ((ins->r0 == r) && f & IF_r0_read) return 1;
> if ((ins->r1 == r) && f & IF_r1_read) return 1;
> if ((ins->r2 == r) && f & IF_r2_read) return 1;
> if ((ins->r3 == r) && f & IF_r3_read) return 1;
>
> return 0;
> }
>
> int instruction_writes(Instruction* ins, SymReg* r) {
> int f;
>
> if (ins == NULL) {
> fprintf(stderr, "Internal error: instruction_reads called with NULL argument\n");
> abort();
> }
>
> f = ins->flags;
>
> if ((ins->r0 == r) && f & IF_r0_write) return 1;
> if ((ins->r1 == r) && f & IF_r1_write) return 1;
> if ((ins->r2 == r) && f & IF_r2_write) return 1;
> if ((ins->r3 == r) && f & IF_r3_write) return 1;
>
> return 0;
> }
>
>
55a97,99
> if (i == NULL) {
> fprintf(stderr, "Memory error at resize_instructions\n");
> }
67a112,115
> if (instructions == NULL) {
> fprintf(stderr, "Memory error at emitb\n");
> abort();
> }
70a119
> i->index = n_instructions;
73d121
< i->basic_block = NULL;
85c133
< if (n_spill > 0) {
---
> if (n_spilled > 0) {
Index: instructions.h
===================================================================
RCS file: /cvs/public/parrot/languages/imcc/instructions.h,v
retrieving revision 1.1
diff -r1.1 instructions.h
17c17
< long flags; /* how the instruction affects each of the values */
---
> long flags; /* how the instruction affects each of the values */
19c19,20
< void * basic_block; /* basic block */
---
> void * basic_block; /* basic block */
> int index; /* index on instructions[] */
50a52,53
> int instruction_reads(Instruction *, SymReg *);
> int instruction_writes(Instruction *, SymReg *);
Index: symreg.c
===================================================================
RCS file: /cvs/public/parrot/languages/imcc/symreg.c,v
retrieving revision 1.1
diff -r1.1 symreg.c
19a20,23
> if (r==NULL) {
> fprintf(stderr, "Memory error at mk_symreg\n");
> abort();
> }
31a36
> r->life_info = NULL;
50a56,59
> if (r==NULL) {
> fprintf(stderr, "Memory error at mk_const\n");
> abort();
> }
58a68
> r->life_info = NULL;
69a80,83
> if (r==NULL) {
> fprintf(stderr, "Memory error at mk_address\n");
> abort();
> }
75a90
> r->life_info = NULL;
Index: symreg.h
===================================================================
RCS file: /cvs/public/parrot/languages/imcc/symreg.h,v
retrieving revision 1.1
diff -r1.1 symreg.h
15a16,33
> enum LIFEFLAG { /* The status of a var inside a basic block can be */
> LF_use = 1 << 0, /* block uses the the var before defining it */
> LF_def = 1 << 1, /* block defines the variable */
> LF_lv_in = 1 << 2, /* variable is alive at the beggining of the block */
> LF_lv_out = 1 << 3, /* variable is alive at the end of the block */
> LF_lv_inside = 1 << 4, /* variable is alive at some momement in the block */
> LF_lv_all = 1 << 5 /* alive during all the block */
> };
>
> /* Liveness represents the usage of a var inside a basic block
> This is represented by pairs of [definition, usage] in *intervals:
> */
> typedef struct _Life_range {
> int flags;
> int n_intervals;
> int *intervals;
> } Life_range;
>
27a46
> Life_range **life_info; /* Each block has its Life_range status */
30d48
<
## COMPUTES the m-th Fibonacci number.
..sub _MAIN
.local int f0
.local int f1
.local int f2
.local int m
.local int i
f0 = 1
f1 = 1
m = 30
if m <= 1 goto LBL3
i = 2
LBL1:
if i > m goto LBL2
f2 = f0 + f1
f0 = f1
f1 = f2
i = i + 1
goto LBL1
LBL3:
print m
goto RET
LBL2:
print f2
goto RET
RET:
print "\n"
end
ret
