From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 109815 invoked by alias); 21 Sep 2015 16:32:36 -0000 Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-bugs-owner@gcc.gnu.org Received: (qmail 109592 invoked by uid 48); 21 Sep 2015 16:32:31 -0000 From: "derodat at adacore dot com" To: gcc-bugs@gcc.gnu.org Subject: [Bug rtl-optimization/66790] Invalid uninitialized register handling in REE Date: Mon, 21 Sep 2015 16:32:00 -0000 X-Bugzilla-Reason: CC X-Bugzilla-Type: changed X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: gcc X-Bugzilla-Component: rtl-optimization X-Bugzilla-Version: 6.0 X-Bugzilla-Keywords: X-Bugzilla-Severity: normal X-Bugzilla-Who: derodat at adacore dot com X-Bugzilla-Status: NEW X-Bugzilla-Resolution: X-Bugzilla-Priority: P3 X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org X-Bugzilla-Target-Milestone: --- X-Bugzilla-Flags: X-Bugzilla-Changed-Fields: Message-ID: In-Reply-To: References: Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: 7bit X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/ Auto-Submitted: auto-generated MIME-Version: 1.0 X-SW-Source: 2015-09/txt/msg01729.txt.bz2 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 set of registers that are initialized/clobbered in the basic block. As you might have noticed, LIVE and MIR don't have the same bb_local_compute function, though. 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. In order to get this right for MIR, I stated that MIR's GEN set excludes the registers left killed at the end of the basic block (and by the way, the bb_local_compute should process artificial defs with DF_REF_AT_TOP before anything else). It seems that RD's and MD's local_compute_process_def do this properly by clearing GEN's bit when setting the corresponding KILL's and reciprocally (and they handle artificial defs properly too!). I think we should do the same for LIVE but lacks confidence because I have not heard of any bug due to this so far... What do you think?