|
|
Bugzilla Link |
128 |
Created on |
Oct 07, 2005 18:04 |
Resolution |
FIXED |
Resolved on |
Oct 11, 2005 11:35 |
Version |
1.00beta |
OS |
Linux |
Architecture |
PC |
Extended Description
int bug128(double ci, double cr)
{
do {
ocr = cr;
cr = cr - ci;
ci = ocr + ci;
} while ( cr <= 4d);
return( toi( cr));
}
int main()
{
res = bug128( 0.5d, 0.5d);
return(res);
}
The loop is eventually transformed into:
goto _dup_512__f2l_483;
do
{
{
free( _pinl_507__emal_461__pinl_457___flat_32);
}
_dup_512__f2l_483:
{
_pinl_506__emal_463__pinl_458_cr__SSA0_4 = alloc( 1, 0, []);
_pinl_506__emal_463__pinl_458_cr__SSA0_4 = (_pinl_505____cr -
_pinl_504____ci);
_pinl_505____cr = (_pinl_505____cr + _pinl_504____ci);
free( _pinl_504____ci);
_pinl_507__emal_461__pinl_457___flat_32 = alloc( 1, 0, []);
_pinl_507__emal_461__pinl_457___flat_32 =
(_pinl_506__emal_463__pinl_458_cr__SSA0_4 <= 4.0);
_pinl_511__cr__SSA0_4__SSA1_2 = _pinl_506__emal_463__pinl_458_cr__SSA0_4;
!!! _pinl_505____cr = _pinl_506__emal_463__pinl_458_cr__SSA0_4; !!!
!!! _pinl_504____ci = _pinl_505____cr; !!!
}
}
while (_pinl_507__emal_461__pinl_457___flat_32);
The problem arises from the lines marked with !!!.
Here, clearly both arguments to the recursive application of the loop are equal,
which must not happen.
A simplified version of the intermediate loop reads:
int loop( int cr, int ci) {
ncr' = alloc(0,[]);
ncr = fill( cr-ci, ncr');
nci' = alloc_or_reuse( 0, [], cr, ci);
nci = fill( cr+ci, nci');
...
if ( c) {
res = loop( ncr, nci);
}
res2 = c ? res : ncr;
return( res2);
}
cr is reused STATICALLY. This is possible because ncr does not have aliases in
the recursive application.
int loop( int cr, int ci) {
ncr' = alloc(0,[]);
ncr = fill( cr-ci, ncr');
nci' = reuse( cr);
nci = fill( cr+ci, nci');
...
if ( c) {
res = loop( ncr, nci);
}
res2 = c ? res : ncr;
return( res2);
}
Reuseelimination completely removes the reuse assignment in order to avoid
unnecessary variable cluttering.
int loop( int cr, int ci) {
ncr' = alloc(0,[]);
ncr = fill( cr-ci, ncr');
nci = fill( cr+ci, cr);
...
if ( c) {
res = loop( ncr, nci);
}
res2 = c ? res : ncr;
return( res2);
}
The final application of fun2lac now applies the clever stategy outlined in the
commentary of BuildRenamingAssignsForDo as the conditions in question are met!
int loop( int cr, ci) {
goto label;
do {
free( c);
label:
ncr' = alloc(0,[]);
ncr = fill( cr-ci, ncr');
nci = fill( cr+ci, cr);
...
res = ncr;
cr = ncr;
ci = nci;
} while( c);
free( c);
free(nci);
return(res);
}
Finally, MarkMemVals eliminates all artificial memory variables and the problem
arises again.
int loop( int cr, ci) {
goto label;
do {
free( c);
label:
ncr' = alloc(0,[]);
ncr' = cr-ci;
cr = cr+ci;
...
res = ncr';
!!! cr = ncr'; !!!
!!! ci = cr; !!!
} while( c);
free( c);
free(cr);
return(res);
}
Solutions:
The problem arises as MMV replaces variables that fun2lac made very specific
assumptions about. It can be tackled in many ways.
1) ReuseElimination should not remove the line nci' = reuse( cr). Instead, the
implementation of reuse (which does not yet exist) should result in nci' = cr.
2) Reuseelimination could transform it into a assignment nci' = cr on its own.
3) Fun2Lac must not apply its smart transformation in the imperative setting
after MM.
All solutions introduce additional variables and which might introduce a runtime
and space overhead if not removed by the C compiler.
However, 1) and 2) affect all reuse situations whereas 3) does only affect loops.
Therefore, I will make a quick implementation of 3). Maybe, one can come up with
a smarter solution later on.