From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 22960 invoked by alias); 16 Jan 2015 05:37:09 -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 22849 invoked by uid 48); 16 Jan 2015 05:37:00 -0000 From: "law at redhat dot com" To: gcc-bugs@gcc.gnu.org Subject: [Bug tree-optimization/61757] [4.10 Regression] genmodes failure with enable-checking Date: Fri, 16 Jan 2015 05:37:00 -0000 X-Bugzilla-Reason: CC X-Bugzilla-Type: changed X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: gcc X-Bugzilla-Component: tree-optimization X-Bugzilla-Version: 5.0 X-Bugzilla-Keywords: build X-Bugzilla-Severity: normal X-Bugzilla-Who: law at redhat dot com X-Bugzilla-Status: RESOLVED X-Bugzilla-Priority: P1 X-Bugzilla-Assigned-To: rguenth at gcc dot gnu.org X-Bugzilla-Target-Milestone: 5.0 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-01/txt/msg01442.txt.bz2 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61757 --- Comment #34 from Jeffrey A. Law --- Whee, fun, finally getting a chance to investigate this BZ. Namely why does canonicalization of equivalences in DOM effect correctness of jump threading. BB12 is what's interesting here. It's the head of the loop. It has two predecessors. BB7 which is outside the loop and BB6 which is inside the loop. BB7->BB12 is the loop entry and BB6->BB12 is the latch edge, naturally. # i_9 = PHI <_3(7), i_12(6)> # prephitmp_16 = PHI i_17 = i_9 + 4294967295; if (q_8(D) == prephitmp_16) goto ; else goto ; When DOM enters BB12 (via BB7) it does not record anything from the PHI since the block has multiple predecessors and the PHI is not a degenerate (ie, the PHI doesn't generate an equivalence that holds every time BB12 executes). When DOM gets to the conditional, it'll record that on the true edge that _8 and _16 are equivalent. It's important to realize that _16 is clearly defined in the loop and that _8 comes from outside the loop (it's actually a default definition). Eventually DOM "traverses" that true edge and we call record_equivalence (which has the loop depth canonicalization). It can record either _8 = _16 or _16 = _8 (OK, I guess it could record both). Without canonicalization we can end up with _8 = 16, ie, an object from outside the loop is defined as equivalent to an object inside the loop. That is bad because when we traverse the loop back edge during threading, objects in the loop can change their values and must trigger invalidations. Invalidation of equivalences the threader is designed on the assumption that nothing outside the loop is ever equivalent to something inside the loop. In effect we assume that all we need to do is either record a new equivalence or invalidate equivalences on every SSA_NAME assigned in the loop as we process the assignment. If we have to handle cases where something outside the loop is recorded as equivalent to something inside the loop, then we'd do to an invalidate for every ssa name in the loop, then record any newly discovered equivalences. I tried real hard to avoid that because of the cost of invalidation. Granted the cost of invalidation now is dramatically smaller, I'd still prefer not to have to do so many invalidations. Given that I want to look at ripping all the backedge stuff out in favor of the on-demand backwards walk approach we're doing for FSMs, I think our best bet is to leave things as-is for gcc-5. The comment in the code references back to this BZ, so I don't think we need to update the comment further.