cvsuser 03/03/05 08:08:52
Modified: . MANIFEST
languages/imcc cfg.c cfg.h debug.c imc.h imcc.y main.c
languages/imcc/docs operation.pod
Added: languages/imcc/docs calling_conventions.pod
Log:
docu update; uninitialized warning
Revision Changes Path
1.322 +1 -0 parrot/MANIFEST
Index: MANIFEST
===================================================================
RCS file: /cvs/public/parrot/MANIFEST,v
retrieving revision 1.321
retrieving revision 1.322
diff -u -w -r1.321 -r1.322
--- MANIFEST 4 Mar 2003 10:46:43 -0000 1.321
+++ MANIFEST 5 Mar 2003 16:08:48 -0000 1.322
@@ -1369,6 +1369,7 @@
languages/imcc/cfg.h
languages/imcc/debug.c
languages/imcc/debug.h
+languages/imcc/docs/calling_conventions.pod
languages/imcc/docs/imcc.pod
languages/imcc/docs/macros.pod
languages/imcc/docs/operation.pod
1.24 +31 -4 parrot/languages/imcc/cfg.c
Index: cfg.c
===================================================================
RCS file: /cvs/public/parrot/languages/imcc/cfg.c,v
retrieving revision 1.23
retrieving revision 1.24
diff -u -w -r1.23 -r1.24
--- cfg.c 3 Mar 2003 09:11:02 -0000 1.23
+++ cfg.c 5 Mar 2003 16:08:49 -0000 1.24
@@ -15,6 +15,7 @@
*/
static void add_instruc_reads(Instruction *ins, SymReg *r0);
+static void propagate_need(Basic_block *bb, SymReg* r, int i);
/* Code: */
@@ -313,6 +314,8 @@
/* this gets read */
ins->flags |= (1<<i);
}
+
+#ifdef ALIAS
/*
* set P1, P0
*
@@ -320,6 +323,8 @@
*
* set P1, 4 sets P0 value
* as long as P1 is used (not overwritten, by new or clone)
+ *
+ * XXX currently turned off, this extends life ranges too much
*/
static void propagate_alias(void)
@@ -331,7 +336,7 @@
for (ins = instructions ; ins ; ins = ins->next) {
if (ins->type & ITALIAS) {
/* make r1 live in each instruction
- * where r0 lifes, until r0 is written
+ * where r0 lives, until r0 is written
*/
curr = ins;
r0 = ins->r[0];
@@ -359,12 +364,15 @@
dump_instructions();
}
}
+#endif
void life_analysis() {
int i;
info(2, "life_analysis\n");
+#ifdef ALIAS
propagate_alias();
+#endif
for(i = 0; i < n_symbols; i++)
analyse_life_symbol(reglist[i]);
}
@@ -396,7 +404,7 @@
r->life_info[i]->flags |= LF_lv_in;
/* propagate this info to every predecessor */
- propagate_need (bb_list[i], r);
+ propagate_need (bb_list[i], r, i);
}
}
}
@@ -483,7 +491,8 @@
}
-void propagate_need(Basic_block *bb, SymReg* r) {
+static void
+propagate_need(Basic_block *bb, SymReg* r, int i) {
Edge *edge;
Basic_block *pred;
Life_range *l;
@@ -510,8 +519,26 @@
l->flags |= LF_lv_in;
l->first_ins = pred->start;
l->last_ins = pred->end;
+ /* we arrived at block 0
+ *
+ * emit a warning if -w
+ * looking at some perl6 examples, where this warning
+ * is emitted, there seems always to be a code path
+ * where the var is not initialized, so this might
+ * even be correct :)
+ */
+ if (pred->index == 0) {
+ Instruction *ins = r->life_info[i]->first_ins;
+ int bbi = ins->bbindex;
+ for ( ; ins && ins->bbindex == bbi; ins = ins->next)
+ if (instruction_reads(ins, r))
+ break;
+ warning("propagate_need",
+ "'%s' might be used uninitialized in %s:%d\n",
+ r->name, function, ins->line);
+ }
- propagate_need(pred, r);
+ propagate_need(pred, r, i);
}
}
}
1.8 +0 -1 parrot/languages/imcc/cfg.h
Index: cfg.h
===================================================================
RCS file: /cvs/public/parrot/languages/imcc/cfg.h,v
retrieving revision 1.7
retrieving revision 1.8
diff -u -w -r1.7 -r1.8
--- cfg.h 28 Feb 2003 14:21:43 -0000 1.7
+++ cfg.h 5 Mar 2003 16:08:50 -0000 1.8
@@ -58,7 +58,6 @@
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*);
void init_basic_blocks(void);
Basic_block* make_basic_block(Instruction*);
1.15 +12 -3 parrot/languages/imcc/debug.c
Index: debug.c
===================================================================
RCS file: /cvs/public/parrot/languages/imcc/debug.c,v
retrieving revision 1.14
retrieving revision 1.15
diff -u -w -r1.14 -r1.15
--- debug.c 4 Mar 2003 15:01:14 -0000 1.14
+++ debug.c 5 Mar 2003 16:08:50 -0000 1.15
@@ -34,6 +34,8 @@
void warning(const char *func, const char *fmt, ...)
{
va_list ap;
+ if (!IMCC_WARN)
+ return;
va_start(ap, fmt);
fprintf(stderr, "warning:imcc:%s: ", func);
@@ -71,13 +73,14 @@
int pc;
fprintf(stderr, "\nDumping the instructions
status:\n-------------------------------\n");
- fprintf(stderr, "nins blck deep flags\t type opnr size pc X ins\n");
+ fprintf(stderr,
+ "nins line blck deep flags\t type opnr size pc X ins\n");
for (pc = 0, ins = instructions; ins; ins = ins->next) {
bb = bb_list[ins->bbindex];
if (bb) {
- fprintf(stderr, "%4i %4d %4d\t%x\t%8x %4d %4d %4d %c ",
- ins->index, bb->index, bb->loop_depth,
+ fprintf(stderr, "%4i %4d %4d %4d\t%x\t%8x %4d %4d %4d %c ",
+ ins->index, ins->line, bb->index, bb->loop_depth,
ins->flags, (ins->type & ~ITEXT), ins->opnum,
ins->opsize, pc, ins->type & ITEXT ? 'X' : ' ');
}
@@ -224,6 +227,12 @@
fprintf(stderr, "\n\t%i: OUT\t", i);
else if (l->first_ins)
fprintf(stderr, "\n\t%i: INS\t", i);
+ if (l->flags & LF_use)
+ fprintf(stderr, "u ");
+ else if (l->flags & LF_def)
+ fprintf(stderr, "d ");
+ else
+ fprintf(stderr, " ");
if(l->first_ins) {
fprintf(stderr, "[%d,%d]\t", l->first_ins->index,
1.31 +1 -0 parrot/languages/imcc/imc.h
Index: imc.h
===================================================================
RCS file: /cvs/public/parrot/languages/imcc/imc.h,v
retrieving revision 1.30
retrieving revision 1.31
diff -u -w -r1.30 -r1.31
--- imc.h 25 Feb 2003 10:25:45 -0000 1.30
+++ imc.h 5 Mar 2003 16:08:50 -0000 1.31
@@ -70,6 +70,7 @@
EXTERN int IMCC_DEBUG;
EXTERN int IMCC_VERBOSE;
+EXTERN int IMCC_WARN;
EXTERN int n_spilled;
EXTERN SymReg** interference_graph;
1.53 +5 -1 parrot/languages/imcc/imcc.y
Index: imcc.y
===================================================================
RCS file: /cvs/public/parrot/languages/imcc/imcc.y,v
retrieving revision 1.52
retrieving revision 1.53
diff -u -w -r1.52 -r1.53
--- imcc.y 4 Mar 2003 15:01:14 -0000 1.52
+++ imcc.y 5 Mar 2003 16:08:50 -0000 1.53
@@ -123,14 +123,18 @@
i->type = ITLABEL;
r0->first_ins = i;
i = emitb(i);
+ i->line = line;
clear_state();
return i;
}
static Instruction * iSUBROUTINE(SymReg * r0) {
+ Instruction *i;
function = r0->name;
- return iLABEL(r0); /* XXX mark label global */
+ i = iLABEL(r0); /* XXX mark label global */
+ i->line = line - 1;
+ return i;
}
1.20 +1 -0 parrot/languages/imcc/main.c
Index: main.c
===================================================================
RCS file: /cvs/public/parrot/languages/imcc/main.c,v
retrieving revision 1.19
retrieving revision 1.20
diff -u -w -r1.19 -r1.20
--- main.c 25 Feb 2003 10:25:45 -0000 1.19
+++ main.c 5 Mar 2003 16:08:50 -0000 1.20
@@ -104,6 +104,7 @@
break;
case 'w':
Parrot_setwarnings(interp, PARROT_WARNINGS_ALL_FLAG);
+ IMCC_WARN = 1;
break;
case 'G':
gc_off = 1;
1.3 +85 -11 parrot/languages/imcc/docs/operation.pod
Index: operation.pod
===================================================================
RCS file: /cvs/public/parrot/languages/imcc/docs/operation.pod,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -w -r1.2 -r1.3
--- operation.pod 7 Feb 2003 17:04:15 -0000 1.2
+++ operation.pod 5 Mar 2003 16:08:52 -0000 1.3
@@ -8,6 +8,8 @@
=item 0.1 intital
+=item 0.2 uninitialized warning; optimizations
+
=back
=head1 OVERVIEW
@@ -30,14 +32,14 @@
=head1 Source file parsing
-S. F<parsing.pod> and F<syntax.pod> for more.
+S. F<parsing.pod>, F<macros.pod> and F<syntax.pod> for more.
=head1 Register allocation
Register allocation is done per I<compilation unit>.
Imcc I<identifiers> and I<temporary variables> e.g. $I0 are assigned a
-phsyical parrot register depending on the life range of these
+physical parrot register depending on the life range of these
variables. If the life range of one variable doesn't overlap the range
of another variable, these might get the same parrot register.
@@ -94,9 +96,43 @@
Variables used as B<IN> parameters must keep their parrot register
over their usage range.
-Note: imcc does currently not know, that certain register operations do
-globber registers: mainly B<restoreall> and friends, which have no hint
-in core.ops, that they do what they do.
+When F<imcc> detects a register usage, where the first operation is
+using (reading) a register (and warnings are enabled), F<imcc> emits
+an appropriate message.
+
+Consider these to code snippets (block numbers are attached):
+
+ .sub _main
+ 0 $I0 = 0 # initialized
+ 0 if $I0 goto l1
+ 1 $I1 = 1 # init in block 1
+ 1 goto l2
+ 2 l1:
+ 2 $I1 = 2 # init in block 2
+ 3 l2:
+ 3 print $I0
+ 3 print $I1 # all paths leading here do init
+ 3 print "\n"
+ 3 end
+ .end
+
+and:
+
+ .sub _main
+ 0 $I0 = 0 # initialized
+ 0 if $I0 goto l1 # branch to bb 1 or 2
+ 1 $I1 = 1 # init only in block 1
+ 2 l1:
+ 2 print $I0
+ 2 print $I1 # no init in code path from block 0
+ 2 print "\n"
+ 2 end
+ .end
+
+The latter of these emits the warning:
+
+ warning:imcc:propagate_need: '$I1' might be used \
+ uninitialized in _main:7
=head2 Interference graph
@@ -104,10 +140,17 @@
variable does interfer with which other. Non interfering variables can
be given the same parrot register.
+=head2 Register allocation
+
+F<imcc> then starts allocating registers according to a variables
+score. Variables deeply nested inside loops have the highest score and
+get a parrot register first. Variables with a long life range (i.e.
+with many interferences) get allocated last.
+
=head2 Spilling
When there are too many interferences, so that not all variables can be
-allocated to a parrot register, the least used variables are spilled,
+allocated to a parrot register, variables with lowest score are spilled,
or stored in a B<PerlArray> when they are not used.
set $I1,1
@@ -116,9 +159,10 @@
set $I33, 33
...
print $I1
+ ...
+ print $I33
-and usage of all these variables after this point makes it necessary,
-to spill.
+The usage of all these variables makes it necessary, to spill.
new P31, .PerlArray
...
@@ -131,12 +175,25 @@
print I0
When $I1 or $I2 are accessed then, code is generated to fetch the
-value from the spill array.
-
+value from the spill array. The life range of such a spilled variable
+is then only one fetch and/or store operation and the actual usage.
+Therefore the variable has minimal interferences with other variables.
=head1 Optimization
-Currently not much is done.
+Optimizations are only done, when enabled with the B<-O> switch. Please
+consult F<t/imcpasm/*.t> for examples. They occur between various
+stages and may be repeatedly done: E.g. after converting a conditional
+branch to an absolute one, unreachable code will be removed then,
+which might cause unused labels ...
+
+=head1 Optimizations with -O1
+
+=head2 Constants substitution
+
+Constant arguments to many ops are evaluated. Conditional branches
+with constant conditions are converted to unconditional branches.
+Integer arguments to float operations are converted to float operands.
=head2 If branch optimization
@@ -157,10 +214,24 @@
The same is done for other conditional branches B<gt>, B<ge>, B<eq>
and their reverse meanings.
+=head2 Branches to branches
+
+Unconditional branch sequences get optimized to jump to the final label.
+
=head2 Unused labels
Labels not referenced somewhere get deleted.
+=head2 Dead code removal
+
+Code not reachable after an unconditional branch instruction and basic
+blocks, that are not entered from somewhere get removed.
+
+=head1 Optimizations with -O2
+
+Note: These are currently experimental and might not do the Right
+Thing.
+
=head2 Used LHS once
For a sequence of code
@@ -173,7 +244,10 @@
set I0, 20
+=head2 Loop optimization.
+Instructions which are invariant to a loop are pulled out of the loop
+and inserted in front of the loop entry.
=head1 Code generation
1.1 parrot/languages/imcc/docs/calling_conventions.pod
Index: calling_conventions.pod
===================================================================
=head1 NAME
IMCC - calling conventions
=head1 VERSION
=over 4
=item 0.1 initial proposal
=item 0.2 initial, checked in
=back
=head1 OVERVIEW
This document describes subroutine calling conventions.
=head1 DESCRIPTION
A imcc does register allocation, it has to track the life span of
variables. This includes the (possible) data flow in and out of
subroutines.
=head1 Stack calling conventions
Arguments are B<save>d in reverse order onto the user stack:
.arg y # save args in reversed order
.arg x
call _foo #(r, s) = _foo(x,y)
.local int r
.local int s
.result s # restore results in reversed order
.result r # [1]
and return values are B<restore>d in reversed order from there.
The subroutine is responsible for preserving registers.
.sub _foo # sub foo(int a, int b)
saveall
.param int a
.param int b
...
.return pl # return (pl, mi)
.return mi # [1]
restoreall
ret
.end
[1] or vice versa?
=head2 Status
Implemented. When the subroutine is in the same compilation unit, the
callee can B<saveall> registers, when the subroutine is in a different
compilation unit, the callee must preserve all used registers.
=head1 Parrot calling conventions (NCI)
Proposed syntax:
$P0 = load_lib "libname"
$P1 = dlfunc $P0, "funcname", "signature"
.nciarg z # I5
.nciarg y # I6
.nciarg x # I7
ncicall $P1 # r = funcname(x, y, z)
.local int r
.nciresult r
This prepares parameters like described in
F<pdd03_calling_conventions.pod>, saves the registers and invokes the
function.
The B<.nciarg> pseudo ops put the given argument into increasing
registers of the appropriate type. They have to be in reversed
argument order.
=head2 Status
Unimplemented.
=head1 Continuations
TBD.
=head1 Coroutines
TBD.
=head1 Exception handlers
TBD.
=head1 Parrot calling conventions (Method calls)
TBD.
=head1 Namespaces and lexicals
- Should imcc keep track of pad opcodes?
- Should imcc even emit such opcodes from e.g. .local directives?
=head1 FILES
F<imcc.y>, F<t/syn/bsr.t>
=head1 AUTHOR
Leopold Toetsch <[EMAIL PROTECTED]>
=cut
# vim: expandtab shiftwidth=4 tw=70:
