Bizarre results of mandelbrot_opt.sac

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.