From patchwork Fri Jun 1 12:38:36 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Sandiford X-Patchwork-Id: 137527 Delivered-To: patch@linaro.org Received: by 2002:a2e:9706:0:0:0:0:0 with SMTP id r6-v6csp884131lji; Fri, 1 Jun 2018 05:38:54 -0700 (PDT) X-Google-Smtp-Source: ADUXVKIPvEGXKQntz41yJmwz7sv1pAKCgFLg5TtuVqtskM+4niPJ4E4fK+ituvUTc6I95OevyOP4 X-Received: by 2002:a63:744a:: with SMTP id e10-v6mr8795449pgn.275.1527856734418; Fri, 01 Jun 2018 05:38:54 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1527856734; cv=none; d=google.com; s=arc-20160816; b=pOusF1afkkNbN+7T5LYCjp1FtF6ay9ugClpXiUr1gGYm5NFlqU8jlE1AfrkU4jdng3 RuQU3Z5oBqVf0tEaFXRC+60i6wIDowujiV7DMTCTn4U9GZ4PSj3X7HmEMiIatmK4ABX2 cZFq5+JFCr6gB1F/v4idhjiP8Kwog6eof9lZu7Cs38aiglMko9DxOYcZ1Ig648D0q/IU w9BX3h1vE9JcjbAMOHaDwJxMOag2cjgoWb4bbn33EQEEAPFtCu8S0Jou/ozch98WDYPB U8qWIvsz74P7+SPwOuze1TXQ28fuOxfrt8O/E/jj+sJ3qrokDn5qi0EBYdWjoEKdKjaB Hqrg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=mime-version:user-agent:message-id:date:subject:mail-followup-to:to :from:delivered-to:sender:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:mailing-list:dkim-signature :domainkey-signature:arc-authentication-results; bh=mUAZj+zQNm8ac+iojjB9aYyLNxvXVW3myRIsFP1qIXs=; b=JtE7xSvuzlxMx3MkQeIneja+MLdSOjGVNsmsnRwY/0GjcPfeAE8pWC9ZPrJLmznwZR d81jkCny/Gm/cQpGJWsth5tc/g0woVpmWIiXS01Zvk5+tvj+HgqSOtmNMIgv1j0gh0g+ xIhDq5pJVVYRzm1bIuaDrVDlfJoAWJspxOzcGT4zwerKZ9rWiYdtZ/BNCi5gfCYcnUN1 BfPYFI5SESPi6HPCONF4+Gv7cLtpQM/VS18Rd5ZJKtwR0fc6rwv5RAGAD1ts+1byavL9 WGEJUtbi37axOwGl2xNYulDD6l+4q+Uw59rm98za9QOOOYIOrP253BG9UeUaucT7R2mn 08fw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=WGJaxugS; spf=pass (google.com: domain of gcc-patches-return-478902-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-478902-patch=linaro.org@gcc.gnu.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id h12-v6si38471034pls.278.2018.06.01.05.38.53 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 01 Jun 2018 05:38:54 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-return-478902-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) client-ip=209.132.180.131; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=WGJaxugS; spf=pass (google.com: domain of gcc-patches-return-478902-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-478902-patch=linaro.org@gcc.gnu.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:subject:date:message-id:mime-version:content-type; q=dns; s= default; b=psmiMkxAQmt1vlyjeSwTa7y8aoXlD0dvqtMnnf1ZWFO6/cbfaTK2W I8+JUdj7AmJuAiwRRdcaurWIN/DnE4zjlh+ciaWAEWYaaKRClBIU/e/YwyVeJhUo k9nlGBvtljBnjGAkzZsOzPjzmgJCI7ZkH0iOfX0sWrwdtupCCY+xyA= 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:from :to:subject:date:message-id:mime-version:content-type; s= default; bh=YljRWVRQImn6mxmNAsnRnzetWpI=; b=WGJaxugSlhuxsmrpzo5A l9sVF8HBN+jHDi071wFCcdng3Jw4Kh+abGUH4UQiVvW4CsJ1GZfrGj7IdZVaxvVN v2gKvjPrATV/TK4R2nrlvZFxmdPLjTw5v4CpsYiUv1l+gaDIPBf45Reke1HnDTfn 07au6NYKnErO8XPwuLCXTlc= Received: (qmail 32022 invoked by alias); 1 Jun 2018 12:38:42 -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 32001 invoked by uid 89); 1 Jun 2018 12:38:41 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-11.0 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_2, GIT_PATCH_3, KAM_ASCII_DIVIDERS, RCVD_IN_DNSWL_NONE, SPF_PASS autolearn=ham version=3.3.2 spammy=nasty X-HELO: mail-wr0-f177.google.com Received: from mail-wr0-f177.google.com (HELO mail-wr0-f177.google.com) (209.85.128.177) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 01 Jun 2018 12:38:40 +0000 Received: by mail-wr0-f177.google.com with SMTP id u12-v6so36175587wrn.8 for ; Fri, 01 Jun 2018 05:38:39 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:mail-followup-to:subject:date:message-id :user-agent:mime-version; bh=mUAZj+zQNm8ac+iojjB9aYyLNxvXVW3myRIsFP1qIXs=; b=g2KR+fP//4qZB65CMUK7qV2+FPBA1Hkb9yqsvZckckExnb0fK4hs2AR9Omr+2+ic/+ dFkr9buw0oDaOMvk8DixHPA4MZhj1lcqA7V2QAp+ZTvx3NoRlmmo2KcYcHaP1mBrIrZW Im4z/Mo1c39bXSkmBaoN9kKbnfbKM/fRCq3naUN3X57ZRdx/j4Y8DRuAgHeGv85hnqgD iajJ1fxav7wRA64oEcXFTTF/3L2TWYNVwzXl6mjfF0QPMMzak2oyprM6Cfsh1YUUiOZn xp9pPwnY0m2Cl0QVA7H8jl2RYZva7kGgjWYEXiVwqwU51LSEL0DahKqowKWR6pf4ZVU9 q0hg== X-Gm-Message-State: ALKqPwebC8laWhZ0ngJiKx6sVim7lO08eOxHTPoM+PKOzN8zkHG3FTg+ vtDrXveTxIM8mnj4Bkgj3rEfQBcp0+Q= X-Received: by 2002:a5d:470b:: with SMTP id y11-v6mr2209154wrq.107.1527856717937; Fri, 01 Jun 2018 05:38:37 -0700 (PDT) Received: from localhost (144.69.7.51.dyn.plus.net. [51.7.69.144]) by smtp.gmail.com with ESMTPSA id t198-v6sm2486568wmt.23.2018.06.01.05.38.36 for (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Fri, 01 Jun 2018 05:38:36 -0700 (PDT) From: Richard Sandiford To: gcc-patches@gcc.gnu.org Mail-Followup-To: gcc-patches@gcc.gnu.org, richard.sandiford@linaro.org Subject: Fix phi backedge detection in backprop (PR85989) Date: Fri, 01 Jun 2018 13:38:36 +0100 Message-ID: <87fu268ywj.fsf@linaro.org> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.3 (gnu/linux) MIME-Version: 1.0 This PR is a nasty wrong code bug due to my fluffing a test for a backedge in gimple-ssa-backprop.c. Backedges are supposed to be from definitions in the statement we're visiting to uses in statements that we haven't visited yet. However, the check failed to account for PHIs in the current block that had already been processed, so if two PHIs in the same block referenced each other, we'd treat both references as backedges. In more detail: The first phase of the pass goes through all statements in an arbitrary order, making optimistic assumptions about any statements that haven't been visited yet. The second phase then calculates a correct (supposedly maximal) fixed point. Although the first phase order is arbitrary in principle, we still use the CFG rpo to cut down on the backedges. This means that the only thing that's truly arbitrary is the order that we process the PHIs in a block. Any order should be OK and should eventually give the same results. But we have to follow whatever order we pick, and the pass wasn't doing that. Tested on aarch64-linux-gnu (with and without SVE), aarch64_be-elf and x86_64-linux-gnu. OK for trunk and all release branches? Sorry for what in hindsight was a really stupid bug. Richard 2018-06-01 Richard Sandiford gcc/ PR tree-optimization/85989 * gimple-ssa-backprop.c (backprop::m_visited_phis): New member variable. (backprop::intersect_uses): Check it when deciding whether this is a backedge reference. (backprop::process_block): Add each phi to m_visited_phis after visiting it, then clear it at the end. gcc/testsuite/ PR tree-optimization/85989 * gcc.dg/torture/pr85989.c: New test. Index: gcc/gimple-ssa-backprop.c =================================================================== --- gcc/gimple-ssa-backprop.c 2018-05-18 09:26:37.726714678 +0100 +++ gcc/gimple-ssa-backprop.c 2018-06-01 13:36:04.223449400 +0100 @@ -260,6 +260,11 @@ dump_usage_info (FILE *file, tree var, u post-order walk. */ auto_sbitmap m_visited_blocks; + /* A bitmap of phis that we have finished processing in the initial + post-order walk, excluding those from blocks mentioned in + M_VISITED_BLOCKS. */ + auto_bitmap m_visited_phis; + /* A worklist of SSA names whose definitions need to be reconsidered. */ auto_vec m_worklist; @@ -496,8 +501,11 @@ backprop::intersect_uses (tree var, usag { if (is_gimple_debug (stmt)) continue; - if (is_a (stmt) - && !bitmap_bit_p (m_visited_blocks, gimple_bb (stmt)->index)) + gphi *phi = dyn_cast (stmt); + if (phi + && !bitmap_bit_p (m_visited_blocks, gimple_bb (phi)->index) + && !bitmap_bit_p (m_visited_phis, + SSA_NAME_VERSION (gimple_phi_result (phi)))) { /* Skip unprocessed phis. */ if (dump_file && (dump_flags & TDF_DETAILS)) @@ -505,7 +513,7 @@ backprop::intersect_uses (tree var, usag fprintf (dump_file, "[BACKEDGE] "); print_generic_expr (dump_file, var); fprintf (dump_file, " in "); - print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); + print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); } } else @@ -629,7 +637,12 @@ backprop::process_block (basic_block bb) } for (gphi_iterator gpi = gsi_start_phis (bb); !gsi_end_p (gpi); gsi_next (&gpi)) - process_var (gimple_phi_result (gpi.phi ())); + { + tree result = gimple_phi_result (gpi.phi ()); + process_var (result); + bitmap_set_bit (m_visited_phis, SSA_NAME_VERSION (result)); + } + bitmap_clear (m_visited_phis); } /* Delete the definition of VAR, which has no uses. */ Index: gcc/testsuite/gcc.dg/torture/pr85989.c =================================================================== --- /dev/null 2018-04-20 16:19:46.369131350 +0100 +++ gcc/testsuite/gcc.dg/torture/pr85989.c 2018-06-01 13:36:04.223449400 +0100 @@ -0,0 +1,31 @@ +/* { dg-do run } */ + +#define N 9 + +void __attribute__((noipa)) +f (double x, double y, double *res) +{ + y = -y; + for (int i = 0; i < N; ++i) + { + double tmp = y; + y = x; + x = tmp; + res[i] = i; + } + res[N] = y * y; + res[N + 1] = x; +} + +int +main (void) +{ + double res[N + 2]; + f (10, 20, res); + for (int i = 0; i < N; ++i) + if (res[i] != i) + __builtin_abort (); + if (res[N] != 100 || res[N + 1] != -20) + __builtin_abort (); + return 0; +}