RFC PRE-ing REFERENCE expressions
|
View:
New views
4 Messages
—
Rating Filter:
Alert me
|
 |
RFC PRE-ing REFERENCE expressions
by Rahul Kharche
::
Rate this Message:
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? Many Thanks, Rahul |
|
|
Re: RFC PRE-ing REFERENCE expressions
by Richard Guenther-2
::
Rate this Message:
On Fri, Oct 30, 2009 at 3:22 PM, Rahul Kharche <rahul@...> 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 > > |
|
|
RE: RFC PRE-ing REFERENCE expressions
by Rahul Kharche
::
Rate this Message:
Hi Richard,
We would like to hang on to 4.4 for a little while. I was hoping I could grab only the alias analysis improvements from the trunk. Do you suspect this would be troublesome? Cheers, Rahul -----Original Message----- From: Richard Guenther [mailto:richard.guenther@...] Sent: 30 October 2009 14:50 To: Rahul Kharche Cc: rguenth@...; gcc@...; sdkteam-gnu Subject: Re: RFC PRE-ing REFERENCE expressions On Fri, Oct 30, 2009 at 3:22 PM, Rahul Kharche <rahul@...> 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 > > |
|
|
RE: RFC PRE-ing REFERENCE expressions
by Richard Guenther-3
::
Rate this Message:
On Mon, 2 Nov 2009, Rahul Kharche wrote:
> Hi Richard, > > We would like to hang on to 4.4 for a little while. I was hoping I could > grab only the alias analysis improvements from the trunk. Do you suspect > this would be troublesome? Uh, definitely - it's not easy to grab them in isolation. Richard. > Cheers, > Rahul > > -----Original Message----- > From: Richard Guenther [mailto:richard.guenther@...] > Sent: 30 October 2009 14:50 > To: Rahul Kharche > Cc: rguenth@...; gcc@...; sdkteam-gnu > Subject: Re: RFC PRE-ing REFERENCE expressions > > On Fri, Oct 30, 2009 at 3:22 PM, Rahul Kharche <rahul@...> 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 > > > > > > Richard Guenther <rguenther@...> Novell / SUSE Labs SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746 - GF: Markus Rex |
| Free embeddable forum powered by Nabble | Forum Help |
