On Fri, Oct 30, 2009 at 3:22 PM, Rahul Kharche <ra...@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
>
>
