| Message ID | alpine.DEB.2.10.1407051342330.2225@laptop-mg.saclay.inria.fr |
|---|---|
| State | New |
| Headers | show |
> On Jul 6, 2014, at 7:23 AM, Marc Glisse <marc.glisse@inria.fr> wrote: > >> On Mon, 30 Jun 2014, Jeff Law wrote: >> >>> On 06/28/14 16:33, Marc Glisse wrote: >>> In an earlier version of the patch, I was using >>> get_or_create_ssa_default_def (cfun, sym); >>> (I was reusing the same variable). This passed bootstrap+testsuite on >>> all languages except for ada. Indeed, the compiler wanted to coalesce >>> several SSA_NAMEs, including those new ones, in out-of-ssa, but >>> couldn't. >> And that's what you need to delve deeper into. Why did it refuse to coalesce? >> >> As long as the lifetimes do not overlap, then coalescing should have worked. > > What is the lifetime of an SSA_NAME with a default definition? The way we handle it now, we start from the uses and go back to all blocks that can reach one of the uses, since there is no defining statement where we could stop (intuitively we should stop where the clobber was, if not earlier). This huge lifetime makes it very likely for such an SSA_NAME to conflict with others. And if an abnormal phi is involved, and thus we must coalesce, there is a problem. > > The patch attached (it should probably use ssa_undefined_value_p with a new extra argument to say whether we care about partially-undefined) makes the lifetime of undefined local variables empty and lets the original patch work with: > def = get_or_create_ssa_default_def (cfun, sym); > instead of creating a new variable. > > However, I am not convinced reusing the same variable is necessarily the best thing. For warnings, we can create a new variable with the same name (with .1 added by gcc at the end) and copy the location info (I am not doing that yet), so little is lost. A new variable expresses more clearly that the value it holds is random crap. If I reuse the same variable, the SRA patch doesn't warn because SRA explicitly sets TREE_NO_WARNING (this can probably be changed, but that's starting to be a lot of changes). Creating a new variable is also more general. When reading *ssa_name after *ssa_name={v}{CLOBBER}; or after free(ssa_name); we have no variable to reuse so we will need to create a new undefined variable, and if a variable is global or a PARM_DECL, its default definition is not an undefined value (though it will probably happen in a different pass, so it doesn't have to behave the same). > > (Side note: we don't seem to have any code to notice that: > a=phi<undef,b> > b=phi<undef,a> > means both phis can be replaced with undefined variables.) > > Do you have any advice on the right direction? The below patch won't work for parameters. Thanks, Andrew > > -- > Marc Glisse > Index: gcc/tree-ssa-live.c > =================================================================== > --- gcc/tree-ssa-live.c (revision 212306) > +++ gcc/tree-ssa-live.c (working copy) > @@ -1086,20 +1086,28 @@ set_var_live_on_entry (tree ssa_name, tr > if (stmt) > { > def_bb = gimple_bb (stmt); > /* Mark defs in liveout bitmap temporarily. */ > if (def_bb) > bitmap_set_bit (&live->liveout[def_bb->index], p); > } > else > def_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun); > > + /* An undefined local variable does not need to be very alive. */ > + if (SSA_NAME_IS_DEFAULT_DEF (ssa_name)) > + { > + tree var = SSA_NAME_VAR (ssa_name); > + if (var && TREE_CODE (var) == VAR_DECL && !is_global_var (var)) > + return; > + } > + > /* Visit each use of SSA_NAME and if it isn't in the same block as the def, > add it to the list of live on entry blocks. */ > FOR_EACH_IMM_USE_FAST (use, imm_iter, ssa_name) > { > gimple use_stmt = USE_STMT (use); > basic_block add_block = NULL; > > if (gimple_code (use_stmt) == GIMPLE_PHI) > { > /* Uses in PHI's are considered to be live at exit of the SRC block > @@ -1422,20 +1430,27 @@ verify_live_on_entry (tree_live_info_p l > fprintf (stderr, "\n"); > } > else > fprintf (stderr, " and there is no default def.\n"); > } > } > } > else > if (d == var) > { > + /* An undefined local variable does not need to be very > + alive. */ > + tree real_var = SSA_NAME_VAR (var); > + if (real_var && TREE_CODE (real_var) == VAR_DECL > + && !is_global_var (real_var)) > + continue; > + > /* The only way this var shouldn't be marked live on entry is > if it occurs in a PHI argument of the block. */ > size_t z; > bool ok = false; > gimple_stmt_iterator gsi; > for (gsi = gsi_start_phis (e->dest); > !gsi_end_p (gsi) && !ok; > gsi_next (&gsi)) > { > gimple phi = gsi_stmt (gsi);
On Sun, 6 Jul 2014, pinskia@gmail.com wrote:
> The below patch won't work for parameters.
Er, that's why I am testing: TREE_CODE (var) == VAR_DECL
(and the patch passed the testsuite with all languages)
Could you be more specific about what won't work?
On Sun, Jul 6, 2014 at 4:23 PM, Marc Glisse <marc.glisse@inria.fr> wrote: > On Mon, 30 Jun 2014, Jeff Law wrote: > >> On 06/28/14 16:33, Marc Glisse wrote: >>> >>> In an earlier version of the patch, I was using >>> get_or_create_ssa_default_def (cfun, sym); >>> (I was reusing the same variable). This passed bootstrap+testsuite on >>> all languages except for ada. Indeed, the compiler wanted to coalesce >>> several SSA_NAMEs, including those new ones, in out-of-ssa, but >>> couldn't. >> >> And that's what you need to delve deeper into. Why did it refuse to >> coalesce? >> >> As long as the lifetimes do not overlap, then coalescing should have >> worked. > > > What is the lifetime of an SSA_NAME with a default definition? The way we > handle it now, we start from the uses and go back to all blocks that can > reach one of the uses, since there is no defining statement where we could > stop (intuitively we should stop where the clobber was, if not earlier). > This huge lifetime makes it very likely for such an SSA_NAME to conflict > with others. And if an abnormal phi is involved, and thus we must coalesce, > there is a problem. > > The patch attached (it should probably use ssa_undefined_value_p with a new > extra argument to say whether we care about partially-undefined) makes the > lifetime of undefined local variables empty and lets the original patch work > with: > def = get_or_create_ssa_default_def (cfun, sym); > instead of creating a new variable. > > However, I am not convinced reusing the same variable is necessarily the > best thing. For warnings, we can create a new variable with the same name > (with .1 added by gcc at the end) and copy the location info (I am not doing > that yet), so little is lost. A new variable expresses more clearly that the > value it holds is random crap. If I reuse the same variable, the SRA patch > doesn't warn because SRA explicitly sets TREE_NO_WARNING (this can probably > be changed, but that's starting to be a lot of changes). Creating a new > variable is also more general. When reading *ssa_name after > *ssa_name={v}{CLOBBER}; or after free(ssa_name); we have no variable to > reuse so we will need to create a new undefined variable, and if a variable > is global or a PARM_DECL, its default definition is not an undefined value > (though it will probably happen in a different pass, so it doesn't have to > behave the same). > > (Side note: we don't seem to have any code to notice that: > a=phi<undef,b> > b=phi<undef,a> > means both phis can be replaced with undefined variables.) Propagators will never replace sth with unefined but they will exploit the undefinedness. Constant propagation is even a bit more aggressive. > Do you have any advice on the right direction? The patch below would work (btw, please use ssa_undefined_value_p), but I wonder if it's the conflict code that should get adjustments rather than the lifeness computation (lifeness of undefined values shouldn't be needed at all). Also depends on how we expand an undefined value of course. Richard. > -- > Marc Glisse > Index: gcc/tree-ssa-live.c > =================================================================== > --- gcc/tree-ssa-live.c (revision 212306) > +++ gcc/tree-ssa-live.c (working copy) > @@ -1086,20 +1086,28 @@ set_var_live_on_entry (tree ssa_name, tr > if (stmt) > { > def_bb = gimple_bb (stmt); > /* Mark defs in liveout bitmap temporarily. */ > if (def_bb) > bitmap_set_bit (&live->liveout[def_bb->index], p); > } > else > def_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun); > > + /* An undefined local variable does not need to be very alive. */ > + if (SSA_NAME_IS_DEFAULT_DEF (ssa_name)) > + { > + tree var = SSA_NAME_VAR (ssa_name); > + if (var && TREE_CODE (var) == VAR_DECL && !is_global_var (var)) > + return; > + } > + > /* Visit each use of SSA_NAME and if it isn't in the same block as the > def, > add it to the list of live on entry blocks. */ > FOR_EACH_IMM_USE_FAST (use, imm_iter, ssa_name) > { > gimple use_stmt = USE_STMT (use); > basic_block add_block = NULL; > > if (gimple_code (use_stmt) == GIMPLE_PHI) > { > /* Uses in PHI's are considered to be live at exit of the SRC > block > @@ -1422,20 +1430,27 @@ verify_live_on_entry (tree_live_info_p l > fprintf (stderr, "\n"); > } > else > fprintf (stderr, " and there is no default def.\n"); > } > } > } > else > if (d == var) > { > + /* An undefined local variable does not need to be very > + alive. */ > + tree real_var = SSA_NAME_VAR (var); > + if (real_var && TREE_CODE (real_var) == VAR_DECL > + && !is_global_var (real_var)) > + continue; > + > /* The only way this var shouldn't be marked live on entry > is > if it occurs in a PHI argument of the block. */ > size_t z; > bool ok = false; > gimple_stmt_iterator gsi; > for (gsi = gsi_start_phis (e->dest); > !gsi_end_p (gsi) && !ok; > gsi_next (&gsi)) > { > gimple phi = gsi_stmt (gsi); >
On 07/06/14 08:23, Marc Glisse wrote: > What is the lifetime of an SSA_NAME with a default definition? The way > we handle it now, we start from the uses and go back to all blocks that > can reach one of the uses, since there is no defining statement where we > could stop Right, that's exactly what I would expect given the typical definition of liveness. (intuitively we should stop where the clobber was, if not > earlier). This huge lifetime makes it very likely for such an SSA_NAME > to conflict with others. And if an abnormal phi is involved, and thus we > must coalesce, there is a problem. So this suggests another approach. Could we just assume that it's always safe to coalesce with a default definition? > > The patch attached (it should probably use ssa_undefined_value_p with a > new extra argument to say whether we care about partially-undefined) > makes the lifetime of undefined local variables empty and lets the > original patch work with: > def = get_or_create_ssa_default_def (cfun, sym); > instead of creating a new variable. Not a terrible suggestion either and accomplishes the same thing as the mental model I had of special casing this stuff in the coalescing code. I guess this is the first thing we probably should sort out. Do we want to handle this is the conflict, coalescing or lifetime analysis. We've certainly had similar hacks in the code which built the conflict matrix for the register allocator in the past (old local-alloc/global variant, pre IRA). By not recoding those conflicts, coalescing just magically works. By handling it when we build the lifetimes, they'll magically coalesce because there's no conflicts as well. It may help other code which utilizes lifetimes as well. But a part of me doesn't like it because it is different than the traditionally formulated life analysis. The question I havent thought much about is would the coalescing code do the right thing if we have one of these undefined SSA_NAMEs that coalesce into two different partitions. ie, let's say we have two PHI nodes in different blocks. Each PHI has one or more source/dest operations that are marked as SSA_NAME_OCCURS_IN_ABNORMAL_PHI. Furthermore, they all reference a single RHS undefined SSA_NAME. When we coalesce the undefined SSA_NAME with all the others in the first PHI, doesn't that mean that we then have to coalesce all the SSA_NAMES in both PHIs together (because that undefined SSA_NAME appears on the RHS on the 2nd PHI too). Does this then argue that each use of an undefined SSA_NAME should be a unique SSA_NAME? Ugh, I wonder if I just opened a can of worms here... > > However, I am not convinced reusing the same variable is necessarily the > best thing. For warnings, we can create a new variable with the same > name (with .1 added by gcc at the end) and copy the location info (I am > not doing that yet), so little is lost. A new variable expresses more > clearly that the value it holds is random crap. If I reuse the same > variable, the SRA patch doesn't warn because SRA explicitly sets > TREE_NO_WARNING (this can probably be changed, but that's starting to be > a lot of changes). Creating a new variable is also more general. When > reading *ssa_name after *ssa_name={v}{CLOBBER}; or after free(ssa_name); > we have no variable to reuse so we will need to create a new undefined > variable, and if a variable is global or a PARM_DECL, its default > definition is not an undefined value (though it will probably happen in > a different pass, so it doesn't have to behave the same). My concern about using another variable was primarily that it was being used to hide a deeper issue. > > (Side note: we don't seem to have any code to notice that: > a=phi<undef,b> > b=phi<undef,a> > means both phis can be replaced with undefined variables.) Various passes will consider the undef value to be whatever value is convenient for optimization. So for the first, we'd consider the undef value to be the same as "b" because that allows the PHI to be propagated away. Obviously when there are many different values in the RHS, it's a lot less likely that we'll be able to propagate away the PHI. Jeff
On Mon, 7 Jul 2014, Jeff Law wrote: > On 07/06/14 08:23, Marc Glisse wrote: >> What is the lifetime of an SSA_NAME with a default definition? The way >> we handle it now, we start from the uses and go back to all blocks that >> can reach one of the uses, since there is no defining statement where we >> could stop > Right, that's exactly what I would expect given the typical definition of > liveness. > > >> (intuitively we should stop where the clobber was, if not >> earlier). This huge lifetime makes it very likely for such an SSA_NAME >> to conflict with others. And if an abnormal phi is involved, and thus we >> must coalesce, there is a problem. > So this suggests another approach. Could we just assume that it's always > safe to coalesce with a default definition? > > >> The patch attached (it should probably use ssa_undefined_value_p with a >> new extra argument to say whether we care about partially-undefined) >> makes the lifetime of undefined local variables empty and lets the >> original patch work with: >> def = get_or_create_ssa_default_def (cfun, sym); >> instead of creating a new variable. > Not a terrible suggestion either and accomplishes the same thing as the > mental model I had of special casing this stuff in the coalescing code. > > I guess this is the first thing we probably should sort out. Do we want to > handle this is the conflict, coalescing or lifetime analysis. > > We've certainly had similar hacks in the code which built the conflict matrix > for the register allocator in the past (old local-alloc/global variant, pre > IRA). By not recoding those conflicts, coalescing just magically works. > > By handling it when we build the lifetimes, they'll magically coalesce > because there's no conflicts as well. It may help other code which utilizes > lifetimes as well. But a part of me doesn't like it because it is different > than the traditionally formulated life analysis. Those variables don't have a birth time so their lifetime is quite ill-defined in any case. I first tried to force coalesce for those variables, but it is not very convenient. We do want to consider them for coalescing, we can't just ignore them. But when we coalesce them with a first variable, we want to mark it somehow so we don't later coalesce them with a second variable that conflicts with the first. The way we do that normally is by computing the union of the lifetimes, but if we ignore the lifetime for this variable... It isn't just a matter of adding || ssa_undefined_value_p (var) in the conflict test. Giving them an empty lifetime to begin with seems to do the right thing. If we don't modify the lifetime computation, we would have in coalesce to pass only the "defined" variables to calculate_live_ranges and re-add the undefined variables afterwards with an empty range. > The question I havent thought much about is would the coalescing code > do the right thing if we have one of these undefined SSA_NAMEs that > coalesce into two different partitions. > > ie, let's say we have two PHI nodes in different blocks. Each PHI has > one or more source/dest operations that are marked as > SSA_NAME_OCCURS_IN_ABNORMAL_PHI. Furthermore, they all reference a > single RHS undefined SSA_NAME. > > When we coalesce the undefined SSA_NAME with all the others in the > first PHI, doesn't that mean that we then have to coalesce all the > SSA_NAMES in both PHIs together (because that undefined SSA_NAME > appears on the RHS on the 2nd PHI too). > > Does this then argue that each use of an undefined SSA_NAME should be > a unique SSA_NAME? I did wonder about the same thing. But without the patch, there were only 2 files in the whole gcc+testsuite that had an issue (in the ada front-end), and with the patch they were fine, so if the situation you describe is possible, at least it is very uncommon. Creating a new variable instead of reusing the old one may be less likely to cause this kind of trouble. At least at creation time we know there is no conflict since it is coming from a variable by an operation that is the reverse of coalescing. > Ugh, I wonder if I just opened a can of worms here... > >> >> However, I am not convinced reusing the same variable is necessarily the >> best thing. For warnings, we can create a new variable with the same >> name (with .1 added by gcc at the end) and copy the location info (I am >> not doing that yet), so little is lost. A new variable expresses more >> clearly that the value it holds is random crap. If I reuse the same >> variable, the SRA patch doesn't warn because SRA explicitly sets >> TREE_NO_WARNING (this can probably be changed, but that's starting to be >> a lot of changes). Creating a new variable is also more general. When >> reading *ssa_name after *ssa_name={v}{CLOBBER}; or after free(ssa_name); >> we have no variable to reuse so we will need to create a new undefined >> variable, and if a variable is global or a PARM_DECL, its default >> definition is not an undefined value (though it will probably happen in >> a different pass, so it doesn't have to behave the same). > My concern about using another variable was primarily that it was being used > to hide a deeper issue. > > >> >> (Side note: we don't seem to have any code to notice that: >> a=phi<undef,b> >> b=phi<undef,a> >> means both phis can be replaced with undefined variables.) > Various passes will consider the undef value to be whatever value is > convenient for optimization. So for the first, we'd consider the undef value > to be the same as "b" because that allows the PHI to be propagated away. Considering that a is the same as b and b is the same as a is not as good as knowing that a and b are both undefined. I don't know if CCP is clever enough to still optimize if b is used in a further PHI, but it would have an easier time (and coalesce and the uninit warning as well) if a=undef; b=undef; were forwarded into their uses instead. Not a priority though. > Obviously when there are many different values in the RHS, it's a lot less > likely that we'll be able to propagate away the PHI. On Mon, 7 Jul 2014, Richard Biener wrote: > On Sun, Jul 6, 2014 at 4:23 PM, Marc Glisse <marc.glisse@inria.fr> wrote: >> On Mon, 30 Jun 2014, Jeff Law wrote: >> >>> On 06/28/14 16:33, Marc Glisse wrote: >>>> >>>> In an earlier version of the patch, I was using >>>> get_or_create_ssa_default_def (cfun, sym); >>>> (I was reusing the same variable). This passed bootstrap+testsuite on >>>> all languages except for ada. Indeed, the compiler wanted to coalesce >>>> several SSA_NAMEs, including those new ones, in out-of-ssa, but >>>> couldn't. >>> >>> And that's what you need to delve deeper into. Why did it refuse to >>> coalesce? >>> >>> As long as the lifetimes do not overlap, then coalescing should have >>> worked. >> >> >> What is the lifetime of an SSA_NAME with a default definition? The way we >> handle it now, we start from the uses and go back to all blocks that can >> reach one of the uses, since there is no defining statement where we could >> stop (intuitively we should stop where the clobber was, if not earlier). >> This huge lifetime makes it very likely for such an SSA_NAME to conflict >> with others. And if an abnormal phi is involved, and thus we must coalesce, >> there is a problem. >> >> The patch attached (it should probably use ssa_undefined_value_p with a new >> extra argument to say whether we care about partially-undefined) makes the >> lifetime of undefined local variables empty and lets the original patch work >> with: >> def = get_or_create_ssa_default_def (cfun, sym); >> instead of creating a new variable. >> >> However, I am not convinced reusing the same variable is necessarily the >> best thing. For warnings, we can create a new variable with the same name >> (with .1 added by gcc at the end) and copy the location info (I am not doing >> that yet), so little is lost. A new variable expresses more clearly that the >> value it holds is random crap. If I reuse the same variable, the SRA patch >> doesn't warn because SRA explicitly sets TREE_NO_WARNING (this can probably >> be changed, but that's starting to be a lot of changes). Creating a new >> variable is also more general. When reading *ssa_name after >> *ssa_name={v}{CLOBBER}; or after free(ssa_name); we have no variable to >> reuse so we will need to create a new undefined variable, and if a variable >> is global or a PARM_DECL, its default definition is not an undefined value >> (though it will probably happen in a different pass, so it doesn't have to >> behave the same). >> >> (Side note: we don't seem to have any code to notice that: >> a=phi<undef,b> >> b=phi<undef,a> >> means both phis can be replaced with undefined variables.) > > Propagators will never replace sth with unefined but they will exploit > the undefinedness. Constant propagation is even a bit more aggressive. > >> Do you have any advice on the right direction? > > The patch below would work (btw, please use ssa_undefined_value_p), > but I wonder if it's the conflict code that should get adjustments > rather than the lifeness computation (lifeness of undefined values > shouldn't be needed at all). > > Also depends on how we expand an undefined value of course. I didn't really look at the expansion part.
Index: gcc/tree-ssa-live.c =================================================================== --- gcc/tree-ssa-live.c (revision 212306) +++ gcc/tree-ssa-live.c (working copy) @@ -1086,20 +1086,28 @@ set_var_live_on_entry (tree ssa_name, tr if (stmt) { def_bb = gimple_bb (stmt); /* Mark defs in liveout bitmap temporarily. */ if (def_bb) bitmap_set_bit (&live->liveout[def_bb->index], p); } else def_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun); + /* An undefined local variable does not need to be very alive. */ + if (SSA_NAME_IS_DEFAULT_DEF (ssa_name)) + { + tree var = SSA_NAME_VAR (ssa_name); + if (var && TREE_CODE (var) == VAR_DECL && !is_global_var (var)) + return; + } + /* Visit each use of SSA_NAME and if it isn't in the same block as the def, add it to the list of live on entry blocks. */ FOR_EACH_IMM_USE_FAST (use, imm_iter, ssa_name) { gimple use_stmt = USE_STMT (use); basic_block add_block = NULL; if (gimple_code (use_stmt) == GIMPLE_PHI) { /* Uses in PHI's are considered to be live at exit of the SRC block @@ -1422,20 +1430,27 @@ verify_live_on_entry (tree_live_info_p l fprintf (stderr, "\n"); } else fprintf (stderr, " and there is no default def.\n"); } } } else if (d == var) { + /* An undefined local variable does not need to be very + alive. */ + tree real_var = SSA_NAME_VAR (var); + if (real_var && TREE_CODE (real_var) == VAR_DECL + && !is_global_var (real_var)) + continue; + /* The only way this var shouldn't be marked live on entry is if it occurs in a PHI argument of the block. */ size_t z; bool ok = false; gimple_stmt_iterator gsi; for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi) && !ok; gsi_next (&gsi)) { gimple phi = gsi_stmt (gsi);