From patchwork Sun Oct 20 14:28:11 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Hubicka X-Patchwork-Id: 1180013 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-511377-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=ucw.cz Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="fd63W/zf"; dkim-atps=neutral Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 46x2FC0gj1z9sNx for ; Mon, 21 Oct 2019 01:28:28 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; q=dns; s= default; b=eQUpkCpDIRlWoNiobPyO/tVk+rfBceq4Xuxb9E8F/0kLBUBok1ori bpesMjzQh0IvYKty0tN/eQuboBeS+fVvWzJLpeEh2WJbF2NrSYltc7h9aCtVsxHW nSU6IjmtNm/HYSS+w7ziO0pIFepoZotUcHAcopwQp2nF8RfMb/iHqE= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; s= default; bh=8OP5gPObnNIjQIMC+3T+ieFvgH0=; b=fd63W/zfBNuRQcVvAMDp 8QOFywckwzlCOqwywp6U+YfXMMM+FEbe0Cict4nrT6+dIuAuFTtlHbpIQAsCHh30 84WQdRIjWPt1pLtXH5neTShu45Dk9ABTOk9rm6IgM7l/cmLa3DTGNPcrV39LqfC9 DmJVhquFktDf3FkELjPdvfc= Received: (qmail 20952 invoked by alias); 20 Oct 2019 14:28:20 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 20944 invoked by uid 89); 20 Oct 2019 14:28:19 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-12.2 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_ASCII_DIVIDERS autolearn=ham version=3.3.1 spammy=Track, accident, multiply, bases X-HELO: nikam.ms.mff.cuni.cz Received: from nikam.ms.mff.cuni.cz (HELO nikam.ms.mff.cuni.cz) (195.113.20.16) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Sun, 20 Oct 2019 14:28:15 +0000 Received: by nikam.ms.mff.cuni.cz (Postfix, from userid 16202) id C273A280FD1; Sun, 20 Oct 2019 16:28:11 +0200 (CEST) Date: Sun, 20 Oct 2019 16:28:11 +0200 From: Jan Hubicka To: law@redhat.com, rguenther@suse.de, gcc-patches@gcc.gnu.org Subject: Fix wrong code issue in access path oracle Message-ID: <20191020142811.woamna3qz7mnjvbi@kam.mff.cuni.cz> MIME-Version: 1.0 Content-Disposition: inline User-Agent: NeoMutt/20170113 (1.7.2) Hi, this patch fixes micompilation of babel Jeff wrote me about. Problem is the array walking in nonoverlapping_refs_since_match_p which gets wrong the following testcase: int main (int argc, char **argv) { int c; unsigned char out[][1] = { {71}, {71}, {71} }; for (int i = 0; i < 3; i++) if (!out[i][0]) __builtin_abort (); return 0; } Now the oracle is called for out[2] store and out[i][0] read. It correctly idenfifies that base pointers are the same and proceeds to nonoverlapping_refs_since_match_p this function expects two access path of same form (i.e. something like a.b.foo and a.b.bar) attempts to match the common part of paths and if they differ at some point disambiguate the accesses. It walks from outermost to innermost reference. At this point it sees that there is one array acces in one path and two in other. To synchronize it it pops [i] access and containues comparing base[0] and base[2] which gets disambiguated because they happen to have same type size bit by accident - changing [1] in testcase to [2] avoids the misoptimization. While writing the code I was imagining that the access path with more array references will eventually lead to same type as the shorter access path. This is not the case here where shorter access path ends by non-scalar value. I was thikning of this option, but incorrectly convinced myself that the size check later is sufficient. It is not safe to pop the access without verifying that the size of the innter type is actually and integer multiply of the other type size (so we maintain the invariant that bases are either same or competely disjoint). This seem to get tricky at least with -fno-strict-aliasing if code walks past end of arrays (and expects it work) and probably also for trailing arrays, so this patch is just a quick fix to disable the logic for all array referneces which are not known to have zero offset (where the invariant is trivially manitained). I will discuss with richi options next week, but perhaps it is not worth the extra effort as the case we look for is relatively rare. For now I am going to commit the following patch which fixes the wrong code (and xfails the testcase I made for different length paths). I will collect some data how much it matters in practice at Monday. Bootstrapped/regtested x86_64-linux. * gcc.c-torture/execute/alias-access-path-2.c: New testcase. * gcc.dg/tree-ssa/alias-access-path-11.c: Xfail. * tree-ssa-alias.c (nonoverlapping_refs_since_match_p): Do not skip non-zero array accesses. Index: testsuite/gcc.c-torture/execute/alias-access-path-2.c =================================================================== --- testsuite/gcc.c-torture/execute/alias-access-path-2.c (nonexistent) +++ testsuite/gcc.c-torture/execute/alias-access-path-2.c (working copy) @@ -0,0 +1,11 @@ +int +main (int argc, char **argv) +{ + int c; + unsigned char out[][1] = { {71}, {71}, {71} }; + + for (int i = 0; i < 3; i++) + if (!out[i][0]) + __builtin_abort (); + return 0; +} Index: testsuite/gcc.dg/tree-ssa/alias-access-path-11.c =================================================================== --- testsuite/gcc.dg/tree-ssa/alias-access-path-11.c (revision 276935) +++ testsuite/gcc.dg/tree-ssa/alias-access-path-11.c (working copy) @@ -12,4 +12,4 @@ test(int i,int j) (*innerptr)[3][j]=11; return (*barptr)[i][2][j]; } -/* { dg-final { scan-tree-dump-times "return 10" 1 "fre3"} } */ +/* { dg-final { scan-tree-dump-times "return 10" 1 "fre3" { xfail *-*-* } } } */ Index: tree-ssa-alias.c =================================================================== --- tree-ssa-alias.c (revision 276935) +++ tree-ssa-alias.c (working copy) @@ -1444,20 +1444,36 @@ nonoverlapping_refs_since_match_p (tree for (; narray_refs1 > narray_refs2; narray_refs1--) { ref1 = component_refs1.pop (); - /* Track whether we possibly introduced partial overlap assuming - that innermost type sizes does not match. This only can - happen if the offset introduced by the ARRAY_REF - is non-zero. */ + + /* If index is non-zero we need to check whether the reference + does not break the main invariant that bases are either + disjoint or equal. Consider the example: + + unsigned char out[][1]; + out[1]="a"; + out[i][0]; + + Here bases out and out are same, but after removing the + [i] index, this invariant no longer holds, because + out[i] points to the middle of array out. + + TODO: If size of type of the skipped reference is an integer + multiply of the size of type of the other reference this + invariant can be verified, but even then it is not completely + safe with !flag_strict_aliasing if the other reference contains + unbounded array accesses. + See */ + if (!operand_equal_p (TREE_OPERAND (ref1, 1), cheap_array_ref_low_bound (ref1), 0)) - seen_unmatched_ref_p = true; + return 0; } for (; narray_refs2 > narray_refs1; narray_refs2--) { ref2 = component_refs2.pop (); if (!operand_equal_p (TREE_OPERAND (ref2, 1), cheap_array_ref_low_bound (ref2), 0)) - seen_unmatched_ref_p = true; + return 0; } /* Try to disambiguate matched arrays. */ for (unsigned int i = 0; i < narray_refs1; i++)