RFC PRE-ing REFERENCE expressions

[Richard Guenther]

On Fri, Oct 30, 2009 at 3:22 PM, Rahul Kharche <rahul@icerasemi.com> wrote:
> Hi Richi,
>
> Following up your suggestion on PR41488, I am continuing to test with
> loop header copy before FRE in GCC 4.4.1. One regression I am trying
> to tackle is from the test case below.
>
> typedef struct {
>  int degree;
>  int c[(256)];
> } swbcht_Polynomial;
>
>
> typedef struct {
>  int m;
>  int n;
>  const swbcht_Polynomial *primPoly;
>  unsigned short alpha[(1 << (13))];
> } swbcht_GF;
>
>
> typedef struct {
>  swbcht_GF gf;
> } swbcht_Handle;
>
>
> static const swbcht_Polynomial _primPoly13;
>
> void _ComputeGFLookupTables (swbcht_Handle *bchH, int m)
> {
>  int i, j;
>
>  swbcht_GF *gf = &bchH->gf;
>
>  gf->m = m;
>  gf->n = (1 << m) - 1;
>
>  gf->primPoly = &_primPoly13;
>
>  for (i = 0; i < gf->m; i++) {
>    gf->alpha[gf->m] ^= (gf->primPoly->c[i] * gf->alpha[i]);
>  }
> }
>
>
> The dump after CH - FRE looks like
>
> _ComputeGFLookupTables (struct swbcht_Handle * bchH, int m)
> {
>  int i;
>  short unsigned int D.1241;
>  short int D.1240;
>  short int D.1239;
>  short unsigned int D.1238;
>  short unsigned int D.1237;
>  short unsigned int D.1236;
>  const int D.1235;
>  const struct swbcht_Polynomial * D.1233;
>  short int D.1232;
>  short unsigned int D.1231;
>  int D.1230;
>  int D.1229;
>  int D.1228;
>
> <bb 2>:
>  bchH_2(D)->gf.m = m_4(D);
>  D.1228_5 = 1 << m_4(D);
>  D.1229_6 = D.1228_5 + -1;
>  bchH_2(D)->gf.n = D.1229_6;
>  bchH_2(D)->gf.primPoly = &_primPoly13;
>  if (m_4(D) > 0)
>    goto <bb 5>;
>  else
>    goto <bb 6>;
>
> <bb 6>:
>  goto <bb 4>;
>
> <bb 5>:
>
> <bb 3>:
>  # i_35 = PHI <0(5), i_23(7)>
>  D.1230_10 = bchH_2(D)->gf.m;
>  D.1231_11 = bchH_2(D)->gf.alpha[D.1230_10];
>  D.1232_12 = (short int) D.1231_11;
>  D.1233_13 = bchH_2(D)->gf.primPoly;
>  D.1235_15 = D.1233_13->c[i_35];
>  D.1236_16 = (short unsigned int) D.1235_15;
>  D.1237_18 = bchH_2(D)->gf.alpha[i_35];
>  D.1238_19 = D.1236_16 * D.1237_18;
>  D.1239_20 = (short int) D.1238_19;
>  D.1240_21 = D.1239_20 ^ D.1232_12;
>  D.1241_22 = (short unsigned int) D.1240_21;
>  bchH_2(D)->gf.alpha[D.1230_10] = D.1241_22;
>  i_23 = i_35 + 1;
>  D.1230_8 = bchH_2(D)->gf.m;
>  if (i_23 < D.1230_8)
>    goto <bb 7>;
>  else
>    goto <bb 8>;
>
> <bb 7>:
>  goto <bb 3>;
>
> <bb 8>:
>
> <bb 4>:
>  return;
>
> }
>
> 1. Why does FRE miss eliminating expression bchH_2(D)->gf.primPoly in
> bb 3 with &_primPoly13. This is normally the case if we ran FRE then
> CH.
>
> Further PRE identifies bchH_2(D)->gf.primPoly as a partially redundant
> expression and hoists it into predecessor bb 7 and we get
>
> <bb 3>:
>  # i_35 = PHI <0(5), i_23(7)>
>  # prephitmp.25_49 = PHI <m_4(D)(5), D.1230_8(7)>
>  # prephitmp.27_51 = PHI <&_primPoly13(5), pretmp.26_50(7)>
>  D.1230_10 = prephitmp.25_49;
>  D.1231_11 = bchH_2(D)->gf.alpha[D.1230_10];
>  D.1232_12 = (short int) D.1231_11;
>  D.1233_13 = prephitmp.27_51;
>  D.1235_15 = D.1233_13->c[i_35];
>  D.1236_16 = (short unsigned int) D.1235_15;
>  D.1237_18 = bchH_2(D)->gf.alpha[i_35];
>  D.1238_19 = D.1236_16 * D.1237_18;
>  D.1239_20 = (short int) D.1238_19;
>  D.1240_21 = D.1239_20 ^ D.1232_12;
>  D.1241_22 = (short unsigned int) D.1240_21;
>  bchH_2(D)->gf.alpha[D.1230_10] = D.1241_22;
>  i_23 = i_35 + 1;
>  D.1230_8 = bchH_2(D)->gf.m;
>  if (D.1230_8 > i_23)
>    goto <bb 7>;
>  else
>    goto <bb 8>;
>
> <bb 7>:
>  pretmp.26_50 = bchH_2(D)->gf.primPoly;
>  goto <bb 3>;
>
>
> Clearly prephitmp.27_51 will make a redundant induction variable.
> Stepping through the insert_into_preds_of_block in tree-ssa-pre.c
> I can see the value numbers for expression bchH_2(D)->gf.primPoly
> available through bb 3 and through bb 2 are different.
>
> 2. Is this because alias analysis cannot determine bchH_2(D)->gf
> has a unique target?

You should move to GCC 4.5 - the alias-oracle in GCC 4.4 is too weak
to discover all this and virtual operands are not helpful because these
are all indirect accesses through pointers without points-to information.

Richard.

>
> Many Thanks,
> Rahul
>
>