| Message ID | 1295901084-4644-1-git-send-email-sebpop@gmail.com |
|---|---|
| State | New |
| Headers | show |
On Mon, Jan 24, 2011 at 02:31:24PM -0600, Sebastian Pop wrote: > @@ -774,6 +788,14 @@ if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb) > return false; > } > > + if (EDGE_COUNT (bb->preds) > 2) > + return false; > + The above 3 lines are redundant with the start of the function: if (EDGE_COUNT (bb->preds) > 2 || EDGE_COUNT (bb->succs) > 2) return false; > + if (EDGE_COUNT (bb->preds) == 2 > + && bb != loop->header > + && !bb_postdominates_preds (bb)) > + return false; > + > return true; > } Jakub
On Mon, Jan 24, 2011 at 14:39, Jakub Jelinek <jakub@redhat.com> wrote: > On Mon, Jan 24, 2011 at 02:31:24PM -0600, Sebastian Pop wrote: >> @@ -774,6 +788,14 @@ if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb) >> return false; >> } >> >> + if (EDGE_COUNT (bb->preds) > 2) >> + return false; >> + > > The above 3 lines are redundant with the start of the function: > > if (EDGE_COUNT (bb->preds) > 2 > || EDGE_COUNT (bb->succs) > 2) > return false; Fixed, thanks.
On 24.01.2011 21:31, Sebastian Pop wrote: > Hi, > > The following patch filters out before if-conversion all the loops > containing basic blocks with more than 2 predecessors or containing > basic blocks that have exactly 2 predecessors not post-dominated by > the basic block: these basic blocks may contain phi nodes that are not > full writes. The current code generation for the tree-if-conversion > does not handle these cases. > > I am regstrapping this patch on amd64-linux. Ok for trunk? on ix86-linux-gnu, r169142 with the proposed patch applied on top, fails to build in libgo, but builds without the proposed patch. /bin/bash ./libtool --tag GO --mode=compile /scratch/packages/gcc/4.6/gcc-4.6-4.6-20110123/build/./gcc/gccgo -B/scratch/packages/gcc/4.6/gcc-4.6-4.6-20110123/build/./gcc/ -B/usr/i486-linux-gnu/bin/ -B/usr/i486-linux-gnu/lib/ -isystem /usr/i486-linux-gnu/include -isystem /usr/i486-linux-gnu/sys-include -minline-all-stringops -O2 -g -c -o bytes/bytes.o -fgo-prefix=libgo_bytes ../../../src/libgo/go/bytes/buffer.go ../../../src/libgo/go/bytes/bytes.go ../../../src/libgo/go/bytes/bytes_decl.go libtool: compile: /scratch/packages/gcc/4.6/gcc-4.6-4.6-20110123/build/./gcc/gccgo -B/scratch/packages/gcc/4.6/gcc-4.6-4.6-20110123/build/./gcc/ -B/usr/i486-linux-gnu/bin/ -B/usr/i486-linux-gnu/lib/ -isystem /usr/i486-linux-gnu/include -isystem /usr/i486-linux-gnu/sys-include -minline-all-stringops -O2 -g -c -fgo-prefix=libgo_bytes ../../../src/libgo/go/bytes/buffer.go ../../../src/libgo/go/bytes/bytes.go ../../../src/libgo/go/bytes/bytes_decl.go -fPIC -o bytes/.libs/bytes.o ../../../src/libgo/go/bytes/buffer.go:193:33: error: argument 1 has incompatible type ../../../src/libgo/go/bytes/buffer.go:193:39: error: argument 2 has incompatible type ../../../src/libgo/go/bytes/bytes.go:350:31: error: argument 1 has incompatible type ../../../src/libgo/go/bytes/bytes.go:350:50: error: argument 2 has incompatible type make[6]: *** [bytes/libbytes.a] Error 1 make[6]: Leaving directory `/scratch/packages/gcc/4.6/gcc-4.6-4.6-20110123/build/i486-linux-gnu/libgo' make[5]: *** [all-recursive] Error 1
Matthias Klose <doko@ubuntu.com> writes: > On 24.01.2011 21:31, Sebastian Pop wrote: >> Hi, >> >> The following patch filters out before if-conversion all the loops >> containing basic blocks with more than 2 predecessors or containing >> basic blocks that have exactly 2 predecessors not post-dominated by >> the basic block: these basic blocks may contain phi nodes that are not >> full writes. The current code generation for the tree-if-conversion >> does not handle these cases. >> >> I am regstrapping this patch on amd64-linux. Ok for trunk? > > on ix86-linux-gnu, r169142 with the proposed patch applied on top, > fails to build in libgo, but builds without the proposed patch. I'm not sure what the issue here, but I'm sure it doesn't have anything to do with Sebastian's patch. > ../../../src/libgo/go/bytes/buffer.go:193:33: error: argument 1 has > incompatible type > ../../../src/libgo/go/bytes/buffer.go:193:39: error: argument 2 has > incompatible type > ../../../src/libgo/go/bytes/bytes.go:350:31: error: argument 1 has incompatible type > ../../../src/libgo/go/bytes/bytes.go:350:50: error: argument 2 has incompatible type > make[6]: *** [bytes/libbytes.a] Error 1 Since the function declaration changed, this looks like the build is somehow picking up an old installed utf8.gox when it should be picking up the newly built one. That is of course not supposed to happen, and I don't see any way that it could happen. Ian
On 25.01.2011 00:54, Ian Lance Taylor wrote: > Matthias Klose<doko@ubuntu.com> writes: > >> On 24.01.2011 21:31, Sebastian Pop wrote: >>> Hi, >>> >>> The following patch filters out before if-conversion all the loops >>> containing basic blocks with more than 2 predecessors or containing >>> basic blocks that have exactly 2 predecessors not post-dominated by >>> the basic block: these basic blocks may contain phi nodes that are not >>> full writes. The current code generation for the tree-if-conversion >>> does not handle these cases. >>> >>> I am regstrapping this patch on amd64-linux. Ok for trunk? >> >> on ix86-linux-gnu, r169142 with the proposed patch applied on top, >> fails to build in libgo, but builds without the proposed patch. > > I'm not sure what the issue here, but I'm sure it doesn't have anything > to do with Sebastian's patch. > > >> ../../../src/libgo/go/bytes/buffer.go:193:33: error: argument 1 has >> incompatible type >> ../../../src/libgo/go/bytes/buffer.go:193:39: error: argument 2 has >> incompatible type >> ../../../src/libgo/go/bytes/bytes.go:350:31: error: argument 1 has incompatible type >> ../../../src/libgo/go/bytes/bytes.go:350:50: error: argument 2 has incompatible type >> make[6]: *** [bytes/libbytes.a] Error 1 > > Since the function declaration changed, this looks like the build is > somehow picking up an old installed utf8.gox when it should be picking > up the newly built one. That is of course not supposed to happen, and I > don't see any way that it could happen. you are right. I had a week old version of libgo installed in /usr/lib, which apparently was picked up during the build (which was configured with --prefix=/usr too)? Matthias
Matthias Klose <doko@ubuntu.com> writes: > you are right. I had a week old version of libgo installed in > /usr/lib, which apparently was picked up during the build (which was > configured with --prefix=/usr too)? I think I figured out the problem, and the libgo patch I just committed should fix it. Sorry about that. Anyhow this is still independent of Sebastian's patch. Ian
On 25.01.2011 06:48, Ian Lance Taylor wrote: > Matthias Klose<doko@ubuntu.com> writes: > >> you are right. I had a week old version of libgo installed in >> /usr/lib, which apparently was picked up during the build (which was >> configured with --prefix=/usr too)? > > I think I figured out the problem, and the libgo patch I just committed > should fix it. Sorry about that. > > Anyhow this is still independent of Sebastian's patch. confirmed, testsuite runs without regressions without the installed libgo.
On Mon, 24 Jan 2011, Sebastian Pop wrote: > Hi, > > The following patch filters out before if-conversion all the loops > containing basic blocks with more than 2 predecessors or containing > basic blocks that have exactly 2 predecessors not post-dominated by > the basic block: these basic blocks may contain phi nodes that are not > full writes. The current code generation for the tree-if-conversion > does not handle these cases. > > I am regstrapping this patch on amd64-linux. Ok for trunk? > > Thanks, > Sebastian > > 2011-01-24 Sebastian Pop <sebastian.pop@amd.com> > Jakub Jelinek <jakub@redhat.com> > > PR tree-optimization/47271 > * tree-if-conv.c (bb_postdominates_preds): New. > (if_convertible_bb_p): Return false when bb has more than 2 > predecessors. Call bb_postdominates_preds. > (if_convertible_loop_p_1): Compute CDI_POST_DOMINATORS. > (predicate_scalar_phi): Call bb_postdominates_preds. > > * gcc.dg/tree-ssa/ifc-pr47271.c: New. > --- > gcc/ChangeLog | 10 +++++ > gcc/testsuite/ChangeLog | 6 +++ > gcc/testsuite/gcc.dg/tree-ssa/ifc-pr47271.c | 49 +++++++++++++++++++++++++++ > gcc/tree-if-conv.c | 26 ++++++++++++++ > 4 files changed, 91 insertions(+), 0 deletions(-) > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ifc-pr47271.c > > diff --git a/gcc/ChangeLog b/gcc/ChangeLog > index 7f3148a..84fb592 100644 > --- a/gcc/ChangeLog > +++ b/gcc/ChangeLog > @@ -1,3 +1,13 @@ > +2011-01-24 Sebastian Pop <sebastian.pop@amd.com> > + Jakub Jelinek <jakub@redhat.com> > + > + PR tree-optimization/47271 > + * tree-if-conv.c (bb_postdominates_preds): New. > + (if_convertible_bb_p): Return false when bb has more than 2 > + predecessors. Call bb_postdominates_preds. > + (if_convertible_loop_p_1): Compute CDI_POST_DOMINATORS. > + (predicate_scalar_phi): Call bb_postdominates_preds. > + > 2011-01-23 Bernd Schmidt <bernds@codesourcery.com> > Richard Sandiford <rdsandiford@googlemail.com> > > diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog > index 33d1cda..3238e3a 100644 > --- a/gcc/testsuite/ChangeLog > +++ b/gcc/testsuite/ChangeLog > @@ -1,3 +1,9 @@ > +2011-01-24 Sebastian Pop <sebastian.pop@amd.com> > + Jakub Jelinek <jakub@redhat.com> > + > + PR tree-optimization/47271 > + * gcc.dg/tree-ssa/ifc-pr47271.c: New. > + > 2011-01-24 Rainer Orth <ro@CeBiTec.Uni-Bielefeld.DE> > > * lib/scanasm.exp (dg-function-on-line): Handle mips-sgi-irix*. > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ifc-pr47271.c b/gcc/testsuite/gcc.dg/tree-ssa/ifc-pr47271.c > new file mode 100644 > index 0000000..bf36079 > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/tree-ssa/ifc-pr47271.c > @@ -0,0 +1,49 @@ > +/* { dg-options "-O3" } */ > +/* { dg-do run } */ > + > +extern void abort (void); > + > +void func (void) > +{ > + int i; > + int nops; > + char *codestr = > + "|\000\000Ee\000\000Z\001\000d\000\000Z\002\000d\025\000Z\003\000" > + "\t\t\t\t\t\t\t\t\t\t\t\td\026\000Z\004\000d\005\000\204\000\000Z" > + "\005\000e\006\000e\a\000j\005\000e\b\000d\006\000\204\002\000\203" > + "\001\000Z\t\000d\a\000\204\000\000Z\n\000d\b\000\204\000\000Z\v\000d" > + "\t\000\204\000\000Z\f\000d\n\000\204\000\000Z\r\000e\016\000e\017\000d" > + "\v\000\203\001\000d\f\000d\r\000\203\001\001Z\020\000e\016\000e\017" > + "\000d\016\000\203\001\000d\f\000d\017\000\203\001\001Z\021\000e\016" > + "\000e\017\000d\020\000\203\001\000d\f\000d\021\000\203\001\001Z\022" > + "\000e\016\000e\017\000d\022\000\203\001\000d\f\000d\023\000\203\001" > + "\001Z\023\000d\024\000S"; > + int codelen = 209; > + int addrmap[500]; > + > + for (i=0, nops=0 ; i<codelen ; i += ((codestr[i] >= 90) ? 3 : 1)) > + { > + addrmap[i] = i - nops; > + if (codestr[i] == 9) > + nops++; > + } > + > + if (addrmap[0] != 0 > + || addrmap[3] != 3 > + || addrmap[4] != 4 > + || addrmap[7] != 7 > + || addrmap[10] != 10 > + || addrmap[13] != 13 > + || addrmap[16] != 16 > + || addrmap[19] != 19 > + || addrmap[22] != 22 > + || addrmap[23] != 22 > + || addrmap[24] != 22) > + abort (); > +} > + > +int main () > +{ > + func (); > + return 0; > +} > diff --git a/gcc/tree-if-conv.c b/gcc/tree-if-conv.c > index 46b20c2..269bad9 100644 > --- a/gcc/tree-if-conv.c > +++ b/gcc/tree-if-conv.c > @@ -716,6 +716,20 @@ if_convertible_stmt_p (gimple stmt, VEC (data_reference_p, heap) *refs) > return true; > } > > +/* Return true when BB post-dominates all its predecessors. */ > + > +static bool > +bb_postdominates_preds (basic_block bb) > +{ > + unsigned i; > + > + for (i = 0; i < EDGE_COUNT (bb->preds); i++) > + if (!dominated_by_p (CDI_POST_DOMINATORS, EDGE_PRED (bb, i)->src, bb)) > + return false; Isn't this an expensive way to do for (i = 0; i < EDGE_COUNT (bb->preds); i++) if (EDGE_COUNT (EDGE_PRED (bb, i)->src->succs) > 1) return false; ? That way you don't need post-dominators. Richard. > + > + return true; > +} > + > /* Return true when BB is if-convertible. This routine does not check > basic block's statements and phis. > > @@ -774,6 +788,14 @@ if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb) > return false; > } > > + if (EDGE_COUNT (bb->preds) > 2) > + return false; > + > + if (EDGE_COUNT (bb->preds) == 2 > + && bb != loop->header > + && !bb_postdominates_preds (bb)) > + return false; > + > return true; > } > > @@ -992,6 +1014,7 @@ if_convertible_loop_p_1 (struct loop *loop, > return false; > > calculate_dominance_info (CDI_DOMINATORS); > + calculate_dominance_info (CDI_POST_DOMINATORS); > > /* Allow statements that can be handled during if-conversion. */ > ifc_bbs = get_loop_body_in_if_conv_order (loop); > @@ -1262,6 +1285,9 @@ predicate_scalar_phi (gimple phi, tree cond, > arg_1 = gimple_phi_arg_def (phi, 1); > } > > + gcc_checking_assert (bb == bb->loop_father->header > + || bb_postdominates_preds (bb)); > + > /* Build new RHS using selected condition and arguments. */ > rhs = build3 (COND_EXPR, TREE_TYPE (res), > unshare_expr (cond), arg_0, arg_1); >
Hi, On Tue, 25 Jan 2011, Richard Guenther wrote: > > + for (i = 0; i < EDGE_COUNT (bb->preds); i++) > > + if (!dominated_by_p (CDI_POST_DOMINATORS, EDGE_PRED (bb, i)->src, bb)) > > + return false; > > Isn't this an expensive way to do > > for (i = 0; i < EDGE_COUNT (bb->preds); i++) > if (EDGE_COUNT (EDGE_PRED (bb, i)->src->succs) > 1) > return false; Nope: A-->B | / | / vv C C postdoms A and B, despite the predecessor A having more than one successor. Ciao, Michael.
On Tue, 25 Jan 2011, Michael Matz wrote: > Hi, > > On Tue, 25 Jan 2011, Richard Guenther wrote: > > > > + for (i = 0; i < EDGE_COUNT (bb->preds); i++) > > > + if (!dominated_by_p (CDI_POST_DOMINATORS, EDGE_PRED (bb, i)->src, bb)) > > > + return false; > > > > Isn't this an expensive way to do > > > > for (i = 0; i < EDGE_COUNT (bb->preds); i++) > > if (EDGE_COUNT (EDGE_PRED (bb, i)->src->succs) > 1) > > return false; > > Nope: A-->B > | / > | / > vv > C > > C postdoms A and B, despite the predecessor A having more than one > successor. Ah indeed. Lack of coffee might explain that. Patch is ok with Jakubs suggestion. Thanks, Richard.
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 7f3148a..84fb592 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,13 @@ +2011-01-24 Sebastian Pop <sebastian.pop@amd.com> + Jakub Jelinek <jakub@redhat.com> + + PR tree-optimization/47271 + * tree-if-conv.c (bb_postdominates_preds): New. + (if_convertible_bb_p): Return false when bb has more than 2 + predecessors. Call bb_postdominates_preds. + (if_convertible_loop_p_1): Compute CDI_POST_DOMINATORS. + (predicate_scalar_phi): Call bb_postdominates_preds. + 2011-01-23 Bernd Schmidt <bernds@codesourcery.com> Richard Sandiford <rdsandiford@googlemail.com> diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 33d1cda..3238e3a 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,9 @@ +2011-01-24 Sebastian Pop <sebastian.pop@amd.com> + Jakub Jelinek <jakub@redhat.com> + + PR tree-optimization/47271 + * gcc.dg/tree-ssa/ifc-pr47271.c: New. + 2011-01-24 Rainer Orth <ro@CeBiTec.Uni-Bielefeld.DE> * lib/scanasm.exp (dg-function-on-line): Handle mips-sgi-irix*. diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ifc-pr47271.c b/gcc/testsuite/gcc.dg/tree-ssa/ifc-pr47271.c new file mode 100644 index 0000000..bf36079 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ifc-pr47271.c @@ -0,0 +1,49 @@ +/* { dg-options "-O3" } */ +/* { dg-do run } */ + +extern void abort (void); + +void func (void) +{ + int i; + int nops; + char *codestr = + "|\000\000Ee\000\000Z\001\000d\000\000Z\002\000d\025\000Z\003\000" + "\t\t\t\t\t\t\t\t\t\t\t\td\026\000Z\004\000d\005\000\204\000\000Z" + "\005\000e\006\000e\a\000j\005\000e\b\000d\006\000\204\002\000\203" + "\001\000Z\t\000d\a\000\204\000\000Z\n\000d\b\000\204\000\000Z\v\000d" + "\t\000\204\000\000Z\f\000d\n\000\204\000\000Z\r\000e\016\000e\017\000d" + "\v\000\203\001\000d\f\000d\r\000\203\001\001Z\020\000e\016\000e\017" + "\000d\016\000\203\001\000d\f\000d\017\000\203\001\001Z\021\000e\016" + "\000e\017\000d\020\000\203\001\000d\f\000d\021\000\203\001\001Z\022" + "\000e\016\000e\017\000d\022\000\203\001\000d\f\000d\023\000\203\001" + "\001Z\023\000d\024\000S"; + int codelen = 209; + int addrmap[500]; + + for (i=0, nops=0 ; i<codelen ; i += ((codestr[i] >= 90) ? 3 : 1)) + { + addrmap[i] = i - nops; + if (codestr[i] == 9) + nops++; + } + + if (addrmap[0] != 0 + || addrmap[3] != 3 + || addrmap[4] != 4 + || addrmap[7] != 7 + || addrmap[10] != 10 + || addrmap[13] != 13 + || addrmap[16] != 16 + || addrmap[19] != 19 + || addrmap[22] != 22 + || addrmap[23] != 22 + || addrmap[24] != 22) + abort (); +} + +int main () +{ + func (); + return 0; +} diff --git a/gcc/tree-if-conv.c b/gcc/tree-if-conv.c index 46b20c2..269bad9 100644 --- a/gcc/tree-if-conv.c +++ b/gcc/tree-if-conv.c @@ -716,6 +716,20 @@ if_convertible_stmt_p (gimple stmt, VEC (data_reference_p, heap) *refs) return true; } +/* Return true when BB post-dominates all its predecessors. */ + +static bool +bb_postdominates_preds (basic_block bb) +{ + unsigned i; + + for (i = 0; i < EDGE_COUNT (bb->preds); i++) + if (!dominated_by_p (CDI_POST_DOMINATORS, EDGE_PRED (bb, i)->src, bb)) + return false; + + return true; +} + /* Return true when BB is if-convertible. This routine does not check basic block's statements and phis. @@ -774,6 +788,14 @@ if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb) return false; } + if (EDGE_COUNT (bb->preds) > 2) + return false; + + if (EDGE_COUNT (bb->preds) == 2 + && bb != loop->header + && !bb_postdominates_preds (bb)) + return false; + return true; } @@ -992,6 +1014,7 @@ if_convertible_loop_p_1 (struct loop *loop, return false; calculate_dominance_info (CDI_DOMINATORS); + calculate_dominance_info (CDI_POST_DOMINATORS); /* Allow statements that can be handled during if-conversion. */ ifc_bbs = get_loop_body_in_if_conv_order (loop); @@ -1262,6 +1285,9 @@ predicate_scalar_phi (gimple phi, tree cond, arg_1 = gimple_phi_arg_def (phi, 1); } + gcc_checking_assert (bb == bb->loop_father->header + || bb_postdominates_preds (bb)); + /* Build new RHS using selected condition and arguments. */ rhs = build3 (COND_EXPR, TREE_TYPE (res), unshare_expr (cond), arg_0, arg_1);