#364 Generalized constant propagation

[Philipp Klaus Krause]

sdcc currently lacks generalized constant propagation. Analyzing the set of possible values (exact, or using intervals or whatever complete lattice seems appropriate) would give additional information for optimization: It would help in replacing types by cheaper types (e.g. using a cheap unsigned char where the programmer used int), or allow simpler code to be generated for singed comparisons, etc.

Philipp

[Philipp Klaus Krause]

This would make regression test gcc-torture-execute-960302-1.c fit into memory on pdk14.

[Philipp Klaus Krause]

A first proof-of-concept can now be found in the genconstprop branch.
There still are quite some bugs (some regression tests fail), and a lot of missing functionality.

As an example (actually the one I used for testing during development yesterday, so the optimization will surely perform particularly well here), a function from Dhrystone:

int Func_2 (char *Str_1_Par_Ref, char *Str_2_Par_Ref)
{
  int Int_Loc;
  char Ch_Loc;

  Int_Loc = 2;
  while (Int_Loc <= 2) /* loop body executed once */
    if (Func_1 (Str_1_Par_Ref[Int_Loc],
                Str_2_Par_Ref[Int_Loc+1]) == Ident_1)
      /* then, executed */
    {
      Ch_Loc = 'A';
      Int_Loc += 1;
    } /* if, while */
  if (Ch_Loc >= 'W' && Ch_Loc < 'Z')
    /* then, not executed */
    Int_Loc = 7;
  if (Ch_Loc == 'R')
    /* then, not executed */
    return (true);
  else /* executed */
  {
    if (strcmp (Str_1_Par_Ref, Str_2_Par_Ref) > 0)
      /* then, not executed */
    {
      Int_Loc += 7;
      Int_Glob = Int_Loc;
      return (true);
    }
    else /* executed */
      return (false);
  } /* if Ch_Loc */
} /* Func_2 */

Gets essentially optimized to:

int Func_2 (char *Str_1_Par_Ref, char *Str_2_Par_Ref)
{
  int Int_Loc;
  char Ch_Loc;

  Int_Loc = 2;
  while (Int_Loc <= 2) /* loop body executed once */
    if (Func_1 (Str_1_Par_Ref[2],
                Str_2_Par_Ref[3]) == Ident_1)
      /* then, executed */
    {
      Int_Loc = 3;
    } /* if, while */
    if (strcmp (Str_1_Par_Ref, Str_2_Par_Ref) > 0)
      /* then, not executed */
    {
      Int_Glob = 10;
      return (true);
    }
    else /* executed */
      return (false);
} /* Func_2 */

Once the optimizations are fully implemented, it would also change the type of Int_Loc to unsigned _BitInt(8).

Typical functions most likely won't profit as much as this one, though.

[Philipp Klaus Krause]

As of [r14149], this has now been improved to the point were it starts being useful. E.g. it will now replace a long long addition by an unsigned _BitInt(40) one in strtoul.c from the standard library.

However, the genconstprop branch is still quite experimental. A lot falls apart for ports other than stm8 (I did nearly all my testing with stm8), and there are surely lots of bugs that the regression tests are bad at detecting (such as bug in volatile accesses).

[Philipp Klaus Krause]

As of [r14179], in the genconstprop branch, generalized constant propagation can also handle some information on operand bits, and z80 codegen can make some use of it. An example:

unsigned int f(unsigned int i)
{
    return ((i & 0x005a) | (i & 0xa500));
}

With sufficiently high optimization settings now compiles (for z80) to:

_f::
    ld  a, l
    and a, #0x5a
    ld  e, a
    ld  a, h
    and a, #0xa5
    ld  d, a
    ret

[Philipp Klaus Krause]

By now, this is essentially working in the genconstprop branch. The analysis does okay on typical code, and the information is used both in machine-independent optimizations and in code generation.

There is still potential for future improvement (relatively low-hanging fruit) though:

• Negative values could be handled better in analyis.
• And backwards pass could gather some extra information (need to be careful, as this is essentially optimization based on the assumption that the code does not exhibit undefined behaviour).
• C2X _Unreachable could be used for analysis.
• The two-way information echchange between the interval and bitmask could be improved in valinfoUpdate.
• Code generation for individual backends could make more use of the information obtained.

Still, it feels like the best way forward is to get some testing results in first, once what is now in the genconstprop branch has made it to trunk.

[Philipp Klaus Krause]

Basic support for intrinsic named address spaces has been added by now for pdk and mcs51.

I am also starting to see the impact on Dhrystone: For mcs51, score increased by 3.5% and code size went down by 0.2% (trunk vs. genconstprop branch). For other ports, such a change would be very little. But mcs51 hasn't seen much change in a long time. For mcs51, this means that genconstprop Dhrystone scores are higher than ever recorded before (records start just before 3.6.0), and code size hasn't been that low since before 3.9.0.