From patchwork Tue Jan 21 11:20:14 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andrew Pinski X-Patchwork-Id: 1226399 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-517867-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=pass (p=none dis=none) header.from=marvell.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha1 header.s=default header.b=JPTr6eAq; dkim=pass (2048-bit key; unprotected) header.d=marvell.com header.i=@marvell.com header.a=rsa-sha256 header.s=pfpt0818 header.b=LuMUlDmK; 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 4825gn5GXrz9sP6 for ; Tue, 21 Jan 2020 22:20:52 +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:from :to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-type; q=dns; s=default; b=FHlrLi5KhPDMgOmH PY398LFpHlvB0fcOapLO5eawjKaY+MzI9KmLr6jXT/gvgwcedpR/4Q0ZHtVzVRpA d3f7gsT+MlU9ivsIDUD8DP6yJDQt5L7YEfD/Ld67kTRQy4a3UekMQoeBxICFci9h BAma3aOJVOZ2clEg4SPytXWsOxM= 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:cc:subject:date:message-id:in-reply-to:references :mime-version:content-type; s=default; bh=zUP1AgheJJL4Bwm0pVJKuq khe40=; b=JPTr6eAqfCjlBai2VbsonzEpHjy2s9/VTP3IX2zQPxC6RaWuROIBIU HJXxLmOcVMNZVJqKVo3cgILFg+xn1N7gUKntSNGkhPSTN0ZsFPUSk37Ur613tmVx S9A1RBSJemqDmcur3HLXPN6gJHXLFChOmtT1Gc4pKoDOVmmTMDTeY= Received: (qmail 79149 invoked by alias); 21 Jan 2020 11:20:43 -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 79139 invoked by uid 89); 21 Jan 2020 11:20:43 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-27.4 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=ham version=3.3.1 spammy= X-HELO: mx0b-0016f401.pphosted.com Received: from mx0b-0016f401.pphosted.com (HELO mx0b-0016f401.pphosted.com) (67.231.156.173) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 21 Jan 2020 11:20:32 +0000 Received: from pps.filterd (m0045851.ppops.net [127.0.0.1]) by mx0b-0016f401.pphosted.com (8.16.0.42/8.16.0.42) with SMTP id 00LBE9fF014435; Tue, 21 Jan 2020 03:20:31 -0800 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=marvell.com; h=from : to : cc : subject : date : message-id : in-reply-to : references : mime-version : content-type; s=pfpt0818; bh=NUnveE1gSHSkGNxWz5yfX1utwgxcR//Ss4XwznNW36Y=; b=LuMUlDmKemZlIshvFtPmU6EWCm25Lzb4Ih6Hyi89fmxc0rdnG7b0k9bujHvHn9/tEWPC 1DX/oko4z7Je4Rb+AUlz1l8ZzU+1zsdBeOSdF/mPtU5+A/IoN0HffcdINwpi1gYA/YTJ Yt7DJEbde382sTM/gv0ZYksPwywVxFOxo/1Uwz9rJbaGHnl0y5/PkAK9Xb6BPLrDqLeO n13HMNexXqD8/QrDx8wcvjTpHxknna1sSgmGcdwZDm3aVRWJkLxkjXEZUJGlNrlRCGNP PZYmokK2B7Ie4zgnKCeYR3ymDgCSvvsT4+OdhyTt/h6YDkkkRnFeztMWhnZuwWg2/plp pQ== Received: from sc-exch04.marvell.com ([199.233.58.184]) by mx0b-0016f401.pphosted.com with ESMTP id 2xm2dt1n4h-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-SHA384 bits=256 verify=NOT); Tue, 21 Jan 2020 03:20:31 -0800 Received: from SC-EXCH01.marvell.com (10.93.176.81) by SC-EXCH04.marvell.com (10.93.176.84) with Microsoft SMTP Server (TLS) id 15.0.1497.2; Tue, 21 Jan 2020 03:20:28 -0800 Received: from maili.marvell.com (10.93.176.43) by SC-EXCH01.marvell.com (10.93.176.81) with Microsoft SMTP Server id 15.0.1497.2 via Frontend Transport; Tue, 21 Jan 2020 03:20:29 -0800 Received: from linux.pinskiwright.org.com (unknown [10.11.201.32]) by maili.marvell.com (Postfix) with ESMTP id 78F2B3F703F; Tue, 21 Jan 2020 03:20:28 -0800 (PST) From: To: , CC: Andrew Pinski Subject: [PATCH/commited] Change recursive prepare_block_for_update to use a worklist Date: Tue, 21 Jan 2020 03:20:14 -0800 Message-ID: <1579605614-2833-1-git-send-email-apinski@marvell.com> In-Reply-To: References: MIME-Version: 1.0 From: Andrew Pinski This is what I committed. Reported as PR 93321, prepare_block_for_update with some huge recusive inlining can go past the stack limit. Transforming this recursive into worklist improves the stack usage here and we no longer seg fault for the testcase. Note the order we walk the siblings change. ChangeLog: PR tree-opt/93321 * tree-into-ssa.c (prepare_block_for_update_1): Split out from ... (prepare_block_for_update): This. Use a worklist instead of recursing. --- gcc/ChangeLog | 8 ++++++ gcc/tree-into-ssa.c | 59 ++++++++++++++++++++++++++++++++++++--------- 2 files changed, 55 insertions(+), 12 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 8c17e5992d2..262f0d6506f 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,11 @@ +2020-01-21 Andrew Pinski + + PR tree-opt/93321 + * tree-into-ssa.c (prepare_block_for_update_1): Split out + from ... + (prepare_block_for_update): This. Use a worklist instead of + recursing. + 2020-01-21 Mihail-Calin Ionescu * gcc/config/arm/arm.c (clear_operation_p): diff --git a/gcc/tree-into-ssa.c b/gcc/tree-into-ssa.c index c27bf2ce121..6528acac31a 100644 --- a/gcc/tree-into-ssa.c +++ b/gcc/tree-into-ssa.c @@ -2593,11 +2593,9 @@ mark_use_interesting (tree var, gimple *stmt, basic_block bb, } } - -/* Do a dominator walk starting at BB processing statements that - reference symbols in SSA operands. This is very similar to - mark_def_sites, but the scan handles statements whose operands may - already be SSA names. +/* Processing statements in BB that reference symbols in SSA operands. + This is very similar to mark_def_sites, but the scan handles + statements whose operands may already be SSA names. If INSERT_PHI_P is true, mark those uses as live in the corresponding block. This is later used by the PHI placement @@ -2610,9 +2608,8 @@ mark_use_interesting (tree var, gimple *stmt, basic_block bb, that. */ static void -prepare_block_for_update (basic_block bb, bool insert_phi_p) +prepare_block_for_update_1 (basic_block bb, bool insert_phi_p) { - basic_block son; edge e; edge_iterator ei; @@ -2694,13 +2691,51 @@ prepare_block_for_update (basic_block bb, bool insert_phi_p) } } - /* Now visit all the blocks dominated by BB. */ - for (son = first_dom_son (CDI_DOMINATORS, bb); - son; - son = next_dom_son (CDI_DOMINATORS, son)) - prepare_block_for_update (son, insert_phi_p); } +/* Do a dominator walk starting at BB processing statements that + reference symbols in SSA operands. This is very similar to + mark_def_sites, but the scan handles statements whose operands may + already be SSA names. + + If INSERT_PHI_P is true, mark those uses as live in the + corresponding block. This is later used by the PHI placement + algorithm to make PHI pruning decisions. + + FIXME. Most of this would be unnecessary if we could associate a + symbol to all the SSA names that reference it. But that + sounds like it would be expensive to maintain. Still, it + would be interesting to see if it makes better sense to do + that. */ +static void +prepare_block_for_update (basic_block bb, bool insert_phi_p) +{ + size_t sp = 0; + basic_block *worklist; + + /* Allocate the worklist. */ + worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun)); + /* Add the BB to the worklist. */ + worklist[sp++] = bb; + + while (sp) + { + basic_block bb; + basic_block son; + + /* Pick a block from the worklist. */ + bb = worklist[--sp]; + + prepare_block_for_update_1 (bb, insert_phi_p); + + /* Now add all the blocks dominated by BB to the worklist. */ + for (son = first_dom_son (CDI_DOMINATORS, bb); + son; + son = next_dom_son (CDI_DOMINATORS, son)) + worklist[sp++] = son; + } + free (worklist); +} /* Helper for prepare_names_to_update. Mark all the use sites for NAME as interesting. BLOCKS and INSERT_PHI_P are as in