[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 Eric Botcazou changed: What|Removed |Added Status|NEW |RESOLVED Resolution|--- |FIXED Target Milestone|--- |6.0 --- Comment #45 from Eric Botcazou --- Fixed in GCC 6.
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 --- Comment #44 from pmderodat at gcc dot gnu.org --- Author: pmderodat Date: Mon Oct 19 23:47:35 2015 New Revision: 229008 URL: https://gcc.gnu.org/viewcvs?rev=229008=gcc=rev Log: REE: fix uninitialized registers handling gcc/ChangeLog: PR rtl-optimization/66790 * df.h (DF_MIR): New macro. (DF_LAST_PROBLEM_PLUS1): Update to be past DF_MIR (DF_MIR_INFO_BB): New macro. (DF_MIR_IN, DF_MIR_OUT): New macros. (struct df_mir_bb_info): New. (df_mir): New macro. (df_mir_add_problem, df_mir_simulate_one_insn): New forward declarations. (df_mir_get_bb_info): New. * df-problems.c (struct df_mir_problem_data): New. (df_mir_free_bb_info, df_mir_alloc, df_mir_reset, df_mir_bb_local_compute, df_mir_local_compute, df_mir_init, df_mir_confluence_0, df_mir_confluence_n, df_mir_transfer_function, df_mir_free, df_mir_top_dump, df_mir_bottom_dump, df_mir_verify_solution_start, df_mir_verify_solution_end): New. (problem_MIR): New. (df_mir_add_problem, df_mir_simulate_one_insn): New. * timevar.def (TV_DF_MIR): New. * ree.c: Include bitmap.h (add_removable_extension): Add an INIT_REGS parameter. Use it to skip zero-extensions that may get an uninitialized register. (find_removable_extensions): Compute must-initialized registers using the MIR dataflow problem. Update the call to add_removable_extension. (find_and_remove_re): Call df_mir_add_problem. gcc/testsuite/ChangeLog: * gnat.dg/opt50.adb: New test. * gnat.dg/opt50_pkg.adb: New helper. * gnat.dg/opt50_pkg.ads: New helper. Added: trunk/gcc/testsuite/gnat.dg/opt50.adb trunk/gcc/testsuite/gnat.dg/opt50_pkg.adb trunk/gcc/testsuite/gnat.dg/opt50_pkg.ads Modified: trunk/gcc/ChangeLog trunk/gcc/df-problems.c trunk/gcc/df.h trunk/gcc/ree.c trunk/gcc/testsuite/ChangeLog trunk/gcc/timevar.def
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 --- Comment #43 from Pierre-Marie de Rodat --- (In reply to Bernd Schmidt from comment #42) > I don't think that would actually help. Even if something is an actual > incoming argument register, it may still be uninitialized by the caller. Sure, but my understanding is that what matters in DF is what happens inside the function, so we can assume arguments are always initialized. Actually this makes sense in the context of REE as well: we have one (artificial) def for arguments so since this def has no corresponding instruction, REE will not be able to remove z-extensions reaching this def. That being said, I failed to get the “is it really used for incoming arguments” hard-reg predicate, so falling back to your proposal: I will followup on gcc-patches@. Thanks! :-)
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 --- Comment #42 from Bernd Schmidt --- I don't think that would actually help. Even if something is an actual incoming argument register, it may still be uninitialized by the caller. That's true for plain scalars, but even more likely for something like the partial struct initialization in comment #8.
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 --- Comment #41 from Pierre-Marie de Rodat --- Thank you again for spotting this! Yes, these artificial defs break the consevativeness for the MIR analysis. I guess your proposal would work: considering as uninintialized registers than aren’t is conservative although it will prevent more optimizations that one could expect in REE. I don’t know if it’s a problem in practice but your example shows that we have a lot of registers in this situation. At this point, though, I wonder why artificial defs do not describe what actually happens for this function. Shouldn’t we instead fix DF to emit artificial defs only for actual input registers? I’ll investigate this. … and then I will followup on gcc-patches as you suggested. Once more, thank you all for your help in this! :-)
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790
--- Comment #38 from Pierre-Marie de Rodat ---
(In reply to Paolo Bonzini from comment #35)
> Is this comment obsolete? The IN bitmap is all set at first.
Yes, indeed: I removed the part you quoted.
(In reply to Paolo Bonzini from comment #35)
> Otherwise looks good.
Thank you! Does this include the DF_LIVE fix?
(In reply to Bernd Schmidt from comment #36)
> This looks better. I still don't quite understand why you're treating
> MUST_CLOBBER and MAY_CLOBBER defs differently in simulate. It looks
> like a MUST_CLOBBER produces a bit in gen which I think is not what is
> wanted.
>
> Anything wrong with writing this simply as follows?
(In reply to Paolo Bonzini from comment #37)
> Bernd is right that you have a missing 'else'.
Pastos strike back! I updated df_mir_simulate_one_insn according to your
suggestion: thank you.
Besides, Eric told me live that instead of artificially clearing the
entry basic block’s IN set, we could use the confluence_0 for that. I
did this and took this opportunity to minimize code duplication: the
df_mir_init function now just calls df_mir_reset.
> And, not as a requirement for your patch, but as a point for
> discussion - do we want a special all_ones_bitmap that doesn't take up
> memory for purposes like this? It would add two additional tests to
> each bitmap_{and,ior} operation.
Good point, although what would the following yield, then?
bitmap_clear (res);
bitmap_set_bit (res, 1);
bitmap_and_into (res, all_ones_bitmap);
I mean: we would need to represent bitmaps will all bits set but one
(and by extension: all but several).
Anyway, here's the updated patch, bootstrapped and regtested again on
x86_64-linux (plus a new testcase in gnat.dg). By the way, there's still
the MIR name, as we did not reach a consensus about a better name.
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 Pierre-Marie de Rodat changed: What|Removed |Added Attachment #36377|0 |1 is obsolete|| --- Comment #39 from Pierre-Marie de Rodat --- Created attachment 36384 --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=36384=edit Updated candidate patch
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 --- Comment #40 from Bernd Schmidt --- (In reply to Pierre-Marie de Rodat from comment #38) > Besides, Eric told me live that instead of artificially clearing the > entry basic block’s IN set, we could use the confluence_0 for that. I > did this and took this opportunity to minimize code duplication: the > df_mir_init function now just calls df_mir_reset. Hmm, is that actually the right thing for the entry block? I notice that we simulate artificial defs, but it seems like that set is not conservatively correct. For a simple function taking a single integer argument: ;; entry block defs 0 [ax] 1 [dx] 2 [cx] 4 [si] 5 [di] 7 [sp] 21 [xmm0] 22 [xmm1] 23 [xmm2] 24 [xmm3] 25 [xmm4] 26 [xmm5] 27 [xmm6] 28 [xmm7] 37 [r8] 38 [r9] where it would appear that only regs 5 (DI) and 7 (SP) are actually reliably defined, but df_get_entry_block_def_set adds everything that's a FUNCTION_ARG_REGNO. But the entire set makes it through the mir in/out sets in the entire function. (gdb) p df_dump(stdout) [...] ; mir in 0 [ax] 1 [dx] 2 [cx] 4 [si] 5 [di] 7 [sp] 21 [xmm0] 22 [xmm1] 23 [xmm2] 24 [xmm3] 25 [xmm4] 26 [xmm5] 27 [xmm6] 28 [xmm7] 37 [r8] 38 [r9] [...] ;; mir out 0 [ax] 1 [dx] 2 [cx] 4 [si] 5 [di] 7 [sp] 17 [flags] 21 [xmm0] 22 [xmm1] 23 [xmm2] 24 [xmm3] 25 [xmm4] 26 [xmm5] 27 [xmm6] 28 [xmm7] 37 [r8] 38 [r9] Maybe it's best _not_ to include artificial defs, except for a subset of things that are known good - such as the stack pointer. Apart from that, starting to look good, thanks for the effort. Future versions should probably go to gcc-patches.
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790
--- Comment #36 from Bernd Schmidt ---
This looks better. I still don't quite understand why you're treating
MUST_CLOBBER and MAY_CLOBBER defs differently in simulate. It looks like a
MUST_CLOBBER produces a bit in gen which I think is not what is wanted.
Anything wrong with writing this simply as follows?
if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
{
bitmap_set_bit (kill, regno);
bitmap_clear_bit (gen, regno);
}
/* In the worst case, partial and conditional defs can leave bits
uninitialized, so assume they do not change anything. */
else if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
{
bitmap_set_bit (gen, regno);
bitmap_clear_bit (kill, regno);
}
And, not as a requirement for your patch, but as a point for discussion - do we
want a special all_ones_bitmap that doesn't take up memory for purposes like
this? It would add two additional tests to each bitmap_{and,ior} operation.
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 --- Comment #35 from Paolo Bonzini --- Comment on attachment 36377 --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=36377 Updated candidate patch > + This problem determines which registers may be uninitialized. It first > + assumes these are all initialized and then it eliminates the ones > reached > + by paths without crossing a definition. The IN bitmap is clear at first > + (i.e. all registers are assumed not to be initialized) so don't consider > + its value the first time. */ > + return bitmap_and_into (op1, op2); Is this comment obsolete? The IN bitmap is all set at first. Otherwise looks good.
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 --- Comment #32 from Pierre-Marie de Rodat --- (In reply to Bernd Schmidt from comment #28) > It is sufficient for OUT(3) to be all-zeros. And I don't think the > LAST_CHANGE_AGE mechanism does anything to prevent it. Please try it > out. I think you have to initialize your bitmaps correctly rather than > rely on "visited". Thank you very much for the reproducer: I confirm that the LAST_CHANGE_AGE mechanism does not have the effect I thought. I just updated my patch locally to initialize bitmaps to 1 for all registers and thus remove the visited field: this fixes the issue you found. > > (In reply to Bernd Schmidt from comment #14) > > > I do have to say that I am still uncomfortable with changing RRE to > > I did not write this. Indeed: Kenneth Zadeck said this in comment #20. I made a pasto, sorry for that! (In reply to Paolo Bonzini from comment #29) > BTW, are you sure that > > + if (DF_REF_FLAGS_IS_SET (def, > + DF_REF_PARTIAL | DF_REF_CONDITIONAL)) > + /* All partial or conditional def > + seen are included in the gen set. */ > + bitmap_set_bit (gen, regno); > > ? I would have thought they don't belong in any set, and on the > contrary I would have thought that may-clobber definitions count as > kills. For partial and conditional defs in the context of MIR: * if the register was initialized, then it is still initialized afterwards, whatever happens; * if the register was uninitialized, then in the case of partial def there will still be bits uninitialized and in the case of conditional def it is possible that the instruction leaves the register uninitialized: in both case there is a possibility to leave part of the register uninitialized. So I would agree with: they don't belong in any set. While thinking about this, I also realized with REE in mind that since we need a conservative computation for MIR, we must set KILL/clear GEN for register refs with DF_REF_MAY_CLOBBER: it may leave the register uninitialized. (In reply to Paolo Bonzini from comment #31) > Ah, I see now. I think you're right that the DF_REF_MUST_CLOBBER case > should also clear GEN in df_live_bb_local_compute. > > However, regarding the "BTW" I am fairly sure now that > df_live_bb_local_compute and the corresponding function for MIR should > handle may-clobber and may-sets differently. If you think of > may-clobber and may-set as a diamond-shaped CFG: > > […] > > Then at the join point you have an "OR" for LIVE (so the clobber's > KILL disappears and the set's GEN remains), and an "AND" for MIR. For > MIR the clobber's KILL remains and the set's GEN disappears. Agreed, thank you! I have updated both MIR and LIVE in the light of this. (bootstrapped and regtested on x86_64-linux)
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 --- Comment #37 from Paolo Bonzini --- Bernd is right that you have a missing 'else'.
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 Pierre-Marie de Rodat changed: What|Removed |Added Attachment #36098|0 |1 is obsolete|| --- Comment #33 from Pierre-Marie de Rodat --- Created attachment 36377 --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=36377=edit Updated candidate patch
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 --- Comment #34 from Pierre-Marie de Rodat --- Created attachment 36378 --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=36378=edit Fix for DF_LIVE local BB information
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 --- Comment #29 from Paolo Bonzini --- > While getting familiar with DF problems, I noticed that LIVE's ignores > the order of GENs and KILLs in basic blocks. In other words, the > transfer function for: GEN(r1); KILL(r1) is currently the same as for > KILL(r1); GEN(r1) whereas clearly the former leaves r1 unitialized > whereas the latter leaves it initialized. GEN and KILL are not the same for LR and MIR. 1) Sets and clobbers are handled differently. A set or clobber of r1 _kills_ liveness, while for MIR sets _generate_ "initialized-ness" and only clobbers kill it. 2) A use of r1 _creates_ liveness (which extends up, until it reaches the sets for all reaching definitions of that use), while uses of r1 are irrelevant for MIR. 3) For LR, GEN must override KILL if an insn has both a set and a use of r1. For MIR, you cannot have a GEN (set) and a KILL (clobber) in the same insn. BTW, are you sure that + if (DF_REF_FLAGS_IS_SET (def, + DF_REF_PARTIAL | DF_REF_CONDITIONAL)) + /* All partial or conditional def + seen are included in the gen set. */ + bitmap_set_bit (gen, regno); ? I would have thought they don't belong in any set, and on the contrary I would have thought that may-clobber definitions count as kills.
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 --- Comment #31 from Paolo Bonzini --- Ah, I see now. I think you're right that the DF_REF_MUST_CLOBBER case should also clear GEN in df_live_bb_local_compute. However, regarding the "BTW" I am fairly sure now that df_live_bb_local_compute and the corresponding function for MIR should handle may-clobber and may-sets differently. If you think of may-clobber and may-set as a diamond-shaped CFG: .. / \ / \ / \/ \ clobber | set | \/\/ \ / \ / \/\/ Then at the join point you have an "OR" for LIVE (so the clobber's KILL disappears and the set's GEN remains), and an "AND" for MIR. For MIR the clobber's KILL remains and the set's GEN disappears.
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 --- Comment #30 from Eric Botcazou --- > GEN and KILL are not the same for LR and MIR. > > 1) Sets and clobbers are handled differently. A set or clobber of r1 > _kills_ liveness, while for MIR sets _generate_ "initialized-ness" and only > clobbers kill it. > > 2) A use of r1 _creates_ liveness (which extends up, until it reaches the > sets for all reaching definitions of that use), while uses of r1 are > irrelevant for MIR. > > 3) For LR, GEN must override KILL if an insn has both a set and a use of r1. > For MIR, you cannot have a GEN (set) and a KILL (clobber) in the same insn. The issue is not LR vs MIR, it's the may-initialized part of LIVE vs MIR. It seem to me that the GEN and KILL of the may-initialized part of LIVE should be the same as those of MIR, since the difference between the 2 problems is only at the global level. Pierre-Marie's patch duplicates them, but ideally they should be factored and reused.
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790
--- Comment #28 from Bernd Schmidt ---
(In reply to Pierre-Marie de Rodat from comment #27)
> (In reply to Bernd Schmidt from comment #14)
> > It looks like your "visited" bit tries to avoid that, but I don't
> > think this works.
> (In reply to Paolo Bonzini from comment #19)
> > There's no code in GCC for must-initialized. Pierre's patch gets it right
> > (except that I'm not sure about the comment at line 2033).
> The "visited" bit I introduced is used to fake an "all bits set"
> initialization. The confluence_n method is meant to do:
>
> IN(dest) = OUT(src_0) AND OUT(src_1) AND ...
>
> ... by small increments of:
>
> IN(dest) := IN(dest) AND OUT(src_i)
>
> When it is executed for the first time, IN(dest) is all-zeros, so we do
> a copy because "a AND all_ones = a". Then we can do regular AND later
> on. In order to get rid of this "visited" bit, I guess we could instead
> pretend that IN/OUT sets are set of never-or-may-initialized registers,
> but this complicates other parts of the code, so...
I know this is what it's trying to do, but when I experimented with it that
wasn't working, due to the problem I described.
> If I understand correctly, the BB_LAST_CHANGE_AGE mechanism in df-core.h
> makes sure computations comply with this dependency (c. before b., b.
> before a.). So at the point the confluence_n function for the 3 -> 3
> edges is called for the first time, both IN(3) and OUT(3) can be not
> all-zeros.
It is sufficient for OUT(3) to be all-zeros. And I don't think the
LAST_CHANGE_AGE mechanism does anything to prevent it. Please try it out. I
think you have to initialize your bitmaps correctly rather than rely on
"visited".
I applied your patch and compiled the following with a breakpoint on
df_mir_confluence_n:
int foo (int n)
{
int sum = 0;
for (int i = 0; i < n; i++)
sum += i;
return sum;
}
and when it reaches the loop:
Breakpoint 5, df_mir_confluence_n (e= 4)>) at
../../trunk/gcc/df-problems.c:2040
(gdb) p debug_bitmap (op1)
first = 0x24bf418 current = 0x24bf418 indx = 0
0x24bf418 next = (nil) prev = (nil) indx = 0
bits = { 0 1 2 4 5 7 17 21 22 23 24 25
26 27 28 37 38 }
$2 = void
(gdb) p debug_bitmap (op2)
first = (nil) current = (nil) indx = 0
and
(gdb) p bb_info->visited
$5 = true
because the edge 3->4 was seen first.
> (In reply to Bernd Schmidt from comment #14)
> > I do have to say that I am still uncomfortable with changing RRE to
I did not write this.
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 --- Comment #27 from Pierre-Marie de Rodat --- Firstly, thanks everyone for your help! I'll try to address points that still are unresolved. (In reply to Bernd Schmidt from comment #14) > As you say, the df-live problem claims to compute a must-initialized > problem, so it would be very odd to add another problem with the same name. (In reply to Eric Botcazou from comment #21) > (In reply to Paolo Bonzini from comment #19) >> There's no code in GCC for must-initialized. Pierre's patch gets it right >> (except that I'm not sure about the comment at line 2033). The MIR name can >> indeed add to the confusion about may/must. Perhaps valid registers (VR)? > > Thanks for the comment. Yes, I agree that the MIR name ought to be improved. To me, "valid" register has the same meaning as "initialized" and thus does not carry the information about whether we can assume it is either always or sometimes valid/initialized. So what about "always initialized registers"? The acronym would be AIR. (In reply to Bernd Schmidt from comment #14) > I experimented with changing df_live_confluence_n to use and instead of ior, > followed by actually taking the confluence_n from your mir problem. However, > this does not work: ior enlarges the set while and shrinks it, so the > initialization of the bitmaps would have to be different. Yes: they both compute different information as discussed later in this thread. (In reply to Bernd Schmidt from comment #14) > It looks like your "visited" bit tries to avoid that, but I don't > think this works. (In reply to Paolo Bonzini from comment #19) > There's no code in GCC for must-initialized. Pierre's patch gets it right > (except that I'm not sure about the comment at line 2033). The "visited" bit I introduced is used to fake an "all bits set" initialization. The confluence_n method is meant to do: IN(dest) = OUT(src_0) AND OUT(src_1) AND ... ... by small increments of: IN(dest) := IN(dest) AND OUT(src_i) When it is executed for the first time, IN(dest) is all-zeros, so we do a copy because "a AND all_ones = a". Then we can do regular AND later on. In order to get rid of this "visited" bit, I guess we could instead pretend that IN/OUT sets are set of never-or-may-initialized registers, but this complicates other parts of the code, so... Paolo, does this clarify the comment at line 2033? (I will update it if you think this is enough :-)) (In reply to Bernd Schmidt from comment #14) > One testcase I looked at had this structure: > > entry -> 2 -> 3 -> 3 > > i.e. a loop in block 3. The confluence_n function takes the out bitmap from > block 3 (which is all zeros) and ands it with the in bitmap from the same > block, which has the incoming regs from block 2 at that point, but obviously > the bitmap turns into all zeros at this point (block 3 was already visited > due to the 2->3 edge). I don't see how your patch doesn't suffer from the > same problem. I don't understand what the problem is: the confluence_n function is used during forward propagation. So in your example: a. the confluence_n function will be called for the 3 -> edge only after... b. the transfer function is invoked for the basic block 3 (then OUT(3) is initialized and potentially not all-zeros); this will be invoked only after... c. the confluence_n function is invoked for the 2 -> 3 edge (then IN(3) is initialized and potentially not all-zeros). If I understand correctly, the BB_LAST_CHANGE_AGE mechanism in df-core.h makes sure computations comply with this dependency (c. before b., b. before a.). So at the point the confluence_n function for the 3 -> 3 edges is called for the first time, both IN(3) and OUT(3) can be not all-zeros. (In reply to Bernd Schmidt from comment #14) > I do have to say that I am still uncomfortable with changing RRE to > use a MUST problem rather than a MAY problem. I see this as dumbing > down the compiler to provide the semantics of uninitialized variables > and it is a path that we have generally avoided in GCC. I do not have > a better solution, but there is a feeling that something is being > missed here. Indeed, while trying to fix the bug, I noticed that no RTL pass needs this "is initialized on all paths" information. I'm not sure what "having no semantics for uninitialized variables" really implies: does this mean that we have an undefined behavior as soon as code uses the value of an uninitialized variable? If not, I think what makes REE special regarding this is that zero-extension is used to pack independent values into single storage units (registers). Because of this, considering that the whole storage unit is uninitialized because a single embedded value is uninitialized makes us generate wrong code. Now on a different topic, I forgot to mention with my first candidate patch: LIVE and MIR are supposed to work on the same GEN/KILL sets. These respectively represent the
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 Eric Botcazou changed: What|Removed |Added CC||bonzini at gnu dot org, ||zadeck at naturalbridge dot com --- Comment #17 from Eric Botcazou --- > So I think there's three things to solve > - which problem should df_live be using, the one it says it's using or the > one it actually does > - if it's the former, see if passes using the information need fixing > - if it's the latter and we need the new problem from this patch, ensure > that it actually works correctly (initializing the out bitmaps to all ones, > probably). That sounds like a good plan. On second thoughts, for the first point, maybe a native speaker understands "an available definition on any path" as "an available definition on one path, whatever it is", in which case the description would be correct, albeit very confusing for non-native speakers. It would be good to have some insight from the DF maintainers here (CCed). In any case, what's needed to fix the bug is "an available definition on every path" and that's what Pierre-Marie's patch implements. We're going to review it in light of your remarks.
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 --- Comment #18 from Bernd Schmidt --- FWIW I did some googling to refresh my memory, and this may be helpful: www.seas.harvard.edu/courses/cs252/2011sp/slides/Lec02-Dataflow.pdf It looks like you want exactly the available expressions problem from page 26. Maybe that's better terminology than must-initialized? (I'm not sure, but I'd never heard the latter term before.) I think I'm coming to the conclusion that df_live really does want what it currently uses, which is the guarantee that there is _any_ def that reaches a use. The commentary could use updating though, I think it clearly isn't computing a "must" problem. When updating the patch please ensure that all new parameters are documented before the function.
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 --- Comment #19 from Paolo Bonzini --- LIVE provides live registers that MAY be initialized (are initialized on at least one path). The comments are all wrong! There's no code in GCC for must-initialized. Pierre's patch gets it right (except that I'm not sure about the comment at line 2033). The MIR name can indeed add to the confusion about may/must. Perhaps valid registers (VR)? Note that this is not the available expressions problem. The confluence function is the same, but it operates on registers and not on expressions. The gen and kill sets are different, too. I wouldn't be surprised if you don't find it in the literature, since it's a relatively obvious extension of the usual dataflow problems. I think this issue can also be fixed easily with an approximated solution, which is already used for example by combine's set_nonzero_bits_and_sign_copies. If a register is undefined at the start of the function, you punt because the register has uninitialized uses. This is suboptimal if you have cases like: int y, x; x = y; /* uninitialized */ ... y = 5; ... x = y; /* initialized */ but they should be pretty rare.
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 --- Comment #20 from Kenneth Zadeck --- >> On second thoughts, for the first point, maybe a native speaker understands >> "an available definition on any path" as "an available definition on one >> path, >> whatever it is", in which case the description would be correct, albeit very >> confusing for non-native speakers. It would be good to have some insight >> from >> the DF maintainers here (CCed). A native English speaker would say that this could be written better. I would suggest the term "on at least one path" and this is what a MAY problem is generally defined as. I do have to say that I am still uncomfortable with changing RRE to use a MUST problem rather than a MAY problem. I see this as dumbing down the compiler to provide the semantics of uninitialized variables and it is a path that we have generally avoided in GCC. I do not have a better solution, but there is a feeling that something is being missed here.
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 --- Comment #21 from Eric Botcazou --- > LIVE provides live registers that MAY be initialized (are initialized on at > least one path). The comments are all wrong! > > There's no code in GCC for must-initialized. Pierre's patch gets it right > (except that I'm not sure about the comment at line 2033). The MIR name can > indeed add to the confusion about may/must. Perhaps valid registers (VR)? Thanks for the comment. Yes, I agree that the MIR name ought to be improved. > I think this issue can also be fixed easily with an approximated solution, > which is already used for example by combine's > set_nonzero_bits_and_sign_copies. If a register is undefined at the start > of the function, you punt because the register has uninitialized uses. This > is suboptimal if you have cases like: > > int y, x; > x = y; /* uninitialized */ > ... > y = 5; > ... > x = y; /* initialized */ > > but they should be pretty rare. Right, we pondered about it. The difference is that combine operates on pseudo while REE operates on hard registers, so the suboptimality could be large.
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 --- Comment #24 from Eric Botcazou --- Author: ebotcazou Date: Thu Sep 17 15:35:24 2015 New Revision: 227874 URL: https://gcc.gnu.org/viewcvs?rev=227874=gcc=rev Log: PR rtl-optimization/66790 * df-problems.c (LIVE): Amend documentation. Modified: trunk/gcc/ChangeLog trunk/gcc/df-problems.c
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 --- Comment #25 from Eric Botcazou --- Author: ebotcazou Date: Thu Sep 17 15:35:43 2015 New Revision: 227875 URL: https://gcc.gnu.org/viewcvs?rev=227875=gcc=rev Log: PR rtl-optimization/66790 * df-problems.c (LIVE): Amend documentation. Modified: branches/gcc-5-branch/gcc/ChangeLog branches/gcc-5-branch/gcc/df-problems.c
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 --- Comment #26 from Eric Botcazou --- Author: ebotcazou Date: Thu Sep 17 15:35:58 2015 New Revision: 227876 URL: https://gcc.gnu.org/viewcvs?rev=227876=gcc=rev Log: PR rtl-optimization/66790 * df-problems.c (LIVE): Amend documentation. Modified: branches/gcc-4_9-branch/gcc/ChangeLog branches/gcc-4_9-branch/gcc/df-problems.c
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 --- Comment #23 from Kenneth Zadeck --- This change to the doc looks fine to me.
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 --- Comment #22 from Eric Botcazou --- > A native English speaker would say that this could be written better. I > would suggest the term "on at least one path" and this is what a MAY problem > is generally defined as. Thanks. Here's a proposed amended wording: Index: df-problems.c === --- df-problems.c (revision 227819) +++ df-problems.c (working copy) @@ -1309,22 +1309,23 @@ df_lr_verify_transfer_functions (void) /* - LIVE AND MUST-INITIALIZED REGISTERS. + LIVE AND MAY-INITIALIZED REGISTERS. This problem first computes the IN and OUT bitvectors for the - must-initialized registers problems, which is a forward problem. - It gives the set of registers for which we MUST have an available - definition on any path from the entry block to the entry/exit of - a basic block. Sets generate a definition, while clobbers kill + may-initialized registers problems, which is a forward problem. + It gives the set of registers for which we MAY have an available + definition, i.e. for which there is an available definition on + at least one path from the entry block to the entry/exit of a + basic block. Sets generate a definition, while clobbers kill a definition. In and out bitvectors are built for each basic block and are indexed by regnum (see df.h for details). In and out bitvectors in struct - df_live_bb_info actually refers to the must-initialized problem; + df_live_bb_info actually refers to the may-initialized problem; Then, the in and out sets for the LIVE problem itself are computed. These are the logical AND of the IN and OUT sets from the LR problem - and the must-initialized problem. + and the may-initialized problem. */ /* Private data used to verify the solution for this problem. */ @@ -1531,7 +1532,7 @@ df_live_confluence_n (edge e) } -/* Transfer function for the forwards must-initialized problem. */ +/* Transfer function for the forwards may-initialized problem. */ static bool df_live_transfer_function (int bb_index) @@ -1555,7 +1556,7 @@ df_live_transfer_function (int bb_index) } -/* And the LR info with the must-initialized registers, to produce the LIVE info. */ +/* And the LR info with the may-initialized registers, to produce the LIVE info. */ static void df_live_finalize (bitmap all_blocks)
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 Bernd Schmidt changed: What|Removed |Added CC||bernds at gcc dot gnu.org --- Comment #14 from Bernd Schmidt --- I've looked at this for a while now. I agree that this is a bug in REE that needs to be fixed in a manner similar to this patch. However, there are some oddities here. As you say, the df-live problem claims to compute a must-initialized problem, so it would be very odd to add another problem with the same name. I experimented with changing df_live_confluence_n to use and instead of ior, followed by actually taking the confluence_n from your mir problem. However, this does not work: ior enlarges the set while and shrinks it, so the initialization of the bitmaps would have to be different. It looks like your "visited" bit tries to avoid that, but I don't think this works. One testcase I looked at had this structure: entry -> 2 -> 3 -> 3 i.e. a loop in block 3. The confluence_n function takes the out bitmap from block 3 (which is all zeros) and ands it with the in bitmap from the same block, which has the incoming regs from block 2 at that point, but obviously the bitmap turns into all zeros at this point (block 3 was already visited due to the 2->3 edge). I don't see how your patch doesn't suffer from the same problem. I think ideally we would figure out whether df_live really does have a mistake in it, and if so fix it rather than adding another problem.
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 --- Comment #15 from Eric Botcazou --- > I've looked at this for a while now. I agree that this is a bug in REE that > needs to be fixed in a manner similar to this patch. Thanks for looking into it. > I think ideally we would figure out whether df_live really does have a > mistake in it, and if so fix it rather than adding another problem. Its description is very confusing, to say the least. Quoting df-problems.c: LIVE AND MUST-INITIALIZED REGISTERS. This problem first computes the IN and OUT bitvectors for the must-initialized registers problems, which is a forward problem. It gives the set of registers for which we MUST have an available definition on any path from the entry block to the entry/exit of a basic block. I think that's incorrect, the correct description would be "it gives the set of registers for which we MUST have an available definition on at least one path from the entry block". That's why it doesn't work for the problem at hand, which requires the "available definition on any path" thing. But I'm not sure we can change it because, for example, init-regs uses it to detect must-uninitialized registers: /* Check all of the uses of pseudo variables. If any use that is MUST uninitialized, add a store of 0 immediately before it. /* A use is MUST uninitialized if it reaches the top of the block from the inside of the block (the lr test) and no def for it reaches the top of the block from outside of the block (the ur test). */ if (bitmap_bit_p (lr, regno) && (!bitmap_bit_p (ur, regno))) that is to say, uses that don't have any available definition.
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 --- Comment #16 from Bernd Schmidt --- So I think there's three things to solve - which problem should df_live be using, the one it says it's using or the one it actually does - if it's the former, see if passes using the information need fixing - if it's the latter and we need the new problem from this patch, ensure that it actually works correctly (initializing the out bitmaps to all ones, probably).
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 Eric Botcazou changed: What|Removed |Added CC||ebotcazou at gcc dot gnu.org --- Comment #10 from Eric Botcazou --- Just to mention that we have really thought hard about this bug at AdaCore and the current patch seems (unfortunately) to be the only plausible way out, if we don't want to pessimize the common case. But suggestions are of course welcome. We have also discussed papering over it in the Ada front-end by initializing the Out parameter to zero. The problem is that you can write an equivalent Ada testcase with an explicitly uninitialized variable and trigger the bug (Pierre-Marie, could you attach it to the PR? Concatenate the files though and mention that it needs to be gnatchop'ed) so we cannot paper over it in all cases. But the fundamental thing to keep in mind here is that this is a valid Ada program and that it could be translated into a valid C program: there is indeed an uninitialized variable but the run-time behavior of the program doesn't depend on its value. The bug in REE effectively propagates the uninitializedness of this variable to another, perfectly initialized variable, because the latter initialization is done with a zero-extension that is eliminated.
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 --- Comment #12 from Eric Botcazou --- Thanks. I misremembered, the testcase has a single variable with two fields, one uninitialized and one initialized, instead of two variables, but it's exactly the same reasoning (and it would be trivial to add the two variables anyway).
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 --- Comment #13 from Pierre-Marie de Rodat --- (In reply to Eric Botcazou from comment #12) > Thanks. I misremembered, the testcase has a single variable with two > fields, one uninitialized and one initialized, instead of two variables, but > it's exactly the same reasoning (and it would be trivial to add the two > variables anyway). Thank you for your involvement into this! :-)
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 --- Comment #11 from Pierre-Marie de Rodat --- Created attachment 36320 --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=36320=edit Reproducer with an uninitialized variable (no OUT parameter)
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790
--- Comment #8 from Pierre-Marie de Rodat derodat at adacore dot com ---
(In reply to Richard Biener from comment #7)
It would be certainly good to see why we have this UNDEF in the first place.
Sure: here is a C translation of what happens in my Ada reproducer (only wrt.
UNDEF: this is not a reproducer for the original bug).
#include stdint.h
struct option_t {
uint16_t is_present;
uint16_t value;
};
struct option_t
foo (uint16_t a, uint16_t b)
{
struct option_t result;
result.is_present = b != 0;
if (result.is_present)
result.value = a / b;
return result;
}
On x86, foo's return value is the 32-bit value in $eax. If b == 0, its lower
half is undefined while its upper one is supposed to be 0. In other words, even
though the value field is uninitialized, the is_present one must be 0. Although
a trunk GCC produces no zero-extension at -O2 for this example, this simply
exposes the source use case for the half-initialized value business.
But yes, I have to agree that zext UNDEF 16 should be zero. Unlike
sext UNDEF which is always undefined as the sign-bit is undefined.
Good point! The patch I submitted previously pessimized the sign-extension
case. The one I'm going to upload fixes this: bootstrapped and regtested
successfuly on x86_64-linux.
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 --- Comment #9 from Pierre-Marie de Rodat derodat at adacore dot com --- Created attachment 36098 -- https://gcc.gnu.org/bugzilla/attachment.cgi?id=36098action=edit Updated candidate patch
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 --- Comment #6 from Pierre-Marie de Rodat derodat at adacore dot com --- Thanks for your answer, Richard! (In reply to Richard Biener from comment #5) So what is the issue with replacing zero-extending an uninitialized %ebp with a random other value? Both are essentially undefined when reached via the somlabel bypass. Well, at least on x86, even when %ebp is uninitialized, “movzwl %bp, %ebp” makes its upper half zero (and yes, the lower half is uninitialized). Hence a following “shr $0x10, %ebp” is supposed to leave zero in %epb, for instance. If we have a random value instead as shr’s input, this does not work anymore, so I consider this transformation is an error. Is the real issue happening in a downstream pass? I don't think REE does anything wrong here. REE is the pass where I observed the change in behavior I described in my first message, and I did not notice anything weird beyond this. If the above is wrong (i.e. if we cannot assume (zext UNDEF from i16 to i32) 16 == 0), then I guess I’ll have to look for something wrong up in the pipe. ;-)
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 Richard Biener rguenth at gcc dot gnu.org changed: What|Removed |Added Status|WAITING |NEW --- Comment #7 from Richard Biener rguenth at gcc dot gnu.org --- (In reply to Pierre-Marie de Rodat from comment #6) Thanks for your answer, Richard! (In reply to Richard Biener from comment #5) So what is the issue with replacing zero-extending an uninitialized %ebp with a random other value? Both are essentially undefined when reached via the somlabel bypass. Well, at least on x86, even when %ebp is uninitialized, “movzwl %bp, %ebp” makes its upper half zero (and yes, the lower half is uninitialized). Hence a following “shr $0x10, %ebp” is supposed to leave zero in %epb, for instance. If we have a random value instead as shr’s input, this does not work anymore, so I consider this transformation is an error. Is the real issue happening in a downstream pass? I don't think REE does anything wrong here. REE is the pass where I observed the change in behavior I described in my first message, and I did not notice anything weird beyond this. If the above is wrong (i.e. if we cannot assume (zext UNDEF from i16 to i32) 16 == 0), then I guess I’ll have to look for something wrong up in the pipe. ;-) It would be certainly good to see why we have this UNDEF in the first place. But yes, I have to agree that zext UNDEF 16 should be zero. Unlike sext UNDEF which is always undefined as the sign-bit is undefined.
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 Richard Biener rguenth at gcc dot gnu.org changed: What|Removed |Added Status|UNCONFIRMED |WAITING Last reconfirmed||2015-07-29 Ever confirmed|0 |1 --- Comment #5 from Richard Biener rguenth at gcc dot gnu.org --- So what is the issue with replacing zero-extending an uninitialized %ebp with a random other value? Both are essentially undefined when reached via the somlabel bypass. Is the real issue happening in a downstream pass? I don't think REE does anything wrong here.
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790
--- Comment #4 from Pierre-Marie de Rodat derodat at adacore dot com ---
(In reply to Pierre-Marie de Rodat from comment #0)
Given the somelabel code path, I would rather expect DF_REF_CHAIN to hold
a NULL reference to materialize the lack of initialization in one path. I
found the DF_LR_IN/DF_LR_OUT macros from df.h: they provide information
about uninitialized variables but the associated comment says they should
not be used (This intolerance should eventually be fixed.). Besides, they
provide a basic-block-level information whereas we are rather interested in
instruction-level information in REE.
Having read more thoroughly dataflow code, I saw the DF_LIVE problem claims
that it provides the logical AND of the IN and OUT sets from the LR problem
and the must-initialized problem, which would be useful: it could provide a
conservative set of registers that *may* be uninitialized (i.e. all registers
that may be uninitialized are included).
So I started looking at the DF_LIVE results, but I got strange results. For
instance, with a very simple C function:
extern void do_nothing (void);
int foo (int i, int b) {
int r;
if (b) { do_nothing (); r = i; }
do_nothing ();
return r 0x;
}
/* foobar.c */
… the reference to the register holding r at the return statement is present
in the IN set for the corresponding basic block:
$ gdb --args cc1 -O2 foobar.c
(gdb) b find_removable_extensions
(gdb) r
(gdb) p dump_function_to_file(cfun.decl, stderr, 0)
[...]
(note 13 12 14 4 [bb 4] NOTE_INSN_BASIC_BLOCK)
(call_insn 14 13 15 4 [...])
(insn 15 14 21 4 (set (reg:SI 0 ax [orig:92 D.1771 ] [92])
(zero_extend:SI (reg:HI 3 bx [orig:87 r ] [87])))
foobar.c:13 136 {*zero_extendhisi2}
(nil))
[...]
(gdb) p df_live_top_dump(cfun.cfg.x_basic_block_info.m_vecdata[4], stderr)
;; live in 3 [bx] 7 [sp]
;; live gen 0 [ax]
;; live kill
This looks wrong to me: there is a path from the entry to this basic block that
doesn't cross a definition for the bx register, so it's not must-initialized
and thus should not be present in this set. Digging further, I noticed that in
df_live_confluence_n, we do:
IN(succ) = OUT(pred) OR IN(succ)
… which, I think, should instead be an AND with respect to the comment: we
want to keep only registers that are must-initialized, so as soon as one *may*
be uninitialized it is out of the result. But this is how it works since the
dataflow merge in 2006… and doing this change unsurprisingly makes the compiler
generate wrong code.
So assuming the LIVE pass actually does not compute must-initialized registers
(but instead what I would call maybe-initialized registers), I tried to add
another problem: MIR (Must-Initialized Registers) and to use it in the REE
pass. I'm about to submit the patch on gcc-patches@.
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 --- Comment #1 from Pierre-Marie de Rodat derodat at adacore dot com --- Created attachment 35923 -- https://gcc.gnu.org/bugzilla/attachment.cgi?id=35923action=edit Part of the reproducer
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 --- Comment #2 from Pierre-Marie de Rodat derodat at adacore dot com --- Created attachment 35924 -- https://gcc.gnu.org/bugzilla/attachment.cgi?id=35924action=edit Part of the reproducer
[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790 --- Comment #3 from Pierre-Marie de Rodat derodat at adacore dot com --- Created attachment 35925 -- https://gcc.gnu.org/bugzilla/attachment.cgi?id=35925action=edit Part of the reproducer
