From patchwork Mon Sep 16 10:11:46 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Feng Xue OS X-Patchwork-Id: 1162705 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-509045-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=os.amperecomputing.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="LANAcI4A"; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=os.amperecomputing.com header.i=@os.amperecomputing.com header.b="PiX++Odb"; 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 46X28z4TNnz9sPl for ; Mon, 16 Sep 2019 20:12:00 +1000 (AEST) 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:references:in-reply-to :content-type:content-transfer-encoding:mime-version; q=dns; s= default; b=fSKvKU55gIqoxYxsvzkTT14Mra/hZM9OM/PygpjSqoC6NCZMYTrYr qQW8qUxeFs7oJGcsdwiP9rsfN9NdCbtlJut1nNYUDJi8sMpk/CbeCqCKtv3vnuLm XQ7wCUhP2Q4Azq9dUINub4kDWT3zFgiEDMSnG05sQpQL7zyN5Fo8rY= 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:references:in-reply-to :content-type:content-transfer-encoding:mime-version; s=default; bh=tUAIxR5o/x/JnRQCC3JFyFt8XyU=; b=LANAcI4AED3VhcZWS4nlzHXaKi6J VU997VLziR/6HnNIetiU+t0bzDmdFa9kXHfQK4vgj24ujBke0fUH8utt6xe5er+d S3avciACJjsUIFKH3BmVAz3bpAHoXP7aov+hj3Cw5T+5lU+Xu+CboaQSarFkY+UQ TREJKEEBL+TAXDA= Received: (qmail 127817 invoked by alias); 16 Sep 2019 10:11:53 -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 127808 invoked by uid 89); 16 Sep 2019 10:11:52 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-24.8 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_NONE, SPF_HELO_PASS, SPF_PASS autolearn=ham version=3.3.1 spammy=diamond, 25000, exceed, aux X-HELO: NAM05-CO1-obe.outbound.protection.outlook.com Received: from mail-eopbgr720099.outbound.protection.outlook.com (HELO NAM05-CO1-obe.outbound.protection.outlook.com) (40.107.72.99) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 16 Sep 2019 10:11:50 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=hEM8nRHp9EwBbsGHgFlaTbXme8TBywOqfvwhVlIiyEiY7++h29viOIN0XkMAPuUE1aVdNgILntpfydD6dN5HmwNQm2j9XGv53qTmUUZ1snI+qqQR+9TqkJrxnrB9GxDFsvYLi/z8+LtgjiG4cy2NRF5D6z31JTjnSn/dYgXxf4UNPeI/5ZeHelcwZ1hWeBG4N2knd/Qedi7+KZCcF8R6gO32gVXIbaWvCfydXzYZSG7S/5uqQ/OgScGHKgnnDUoVEij6+Ab81mVoHGlA9WTV6mWk6P/5stzVZFb1eBAqWNZAuOxjbBsC1Uaz/IWKvYDhutJ8GogQGu7TTxrFR6lnng== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=UzD8EGaLE/CoZ1/b4S7JXUbJzSRFCqJxjFSGpGUO12s=; b=Y+rC57rkl+qUq3dxWKVMjZcAw5hgPrwT9d/KaDjgXFFXYhlmC0Rxmd7ThicQzG9YNlXQByGQlPPO8aqiPeq4A7FyW1UpYbyJ/Tid0AMv3nX23LcZMnOqrwGF4Y0T060xw2qdGi6xa0T/Htwh72+OjvSFuaRkeDV/1NRq4v9mMuw9/rV523L8Gakw1MXFoh1Nec9Kj4KLYUgOgvcMdD7iEpqZXLaB2+nm9f8rFHLhBfp4bA1nm+IO4wxfDGgeU09As9reILXYf5Sevrs6bS3MRhgfSFMv955Y8FvM7aSy8WeMns0Rilrkgtxf3VrSRsaNt3M6cKxI7/EDYxMtO/t3rw== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=os.amperecomputing.com; dmarc=pass action=none header.from=os.amperecomputing.com; dkim=pass header.d=os.amperecomputing.com; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=os.amperecomputing.com; s=selector2; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=UzD8EGaLE/CoZ1/b4S7JXUbJzSRFCqJxjFSGpGUO12s=; b=PiX++OdboLl+NGtIyy+S9HYarP7RaZEb3JEoKRH3JJSaDZuEOVCdftkMcNj4xjr8CMGzGjnQSkjO1u9S6QMh7CnTm+4gbhLTNYuyw0+8NgomWOwFEyA78rCmJO9oHr/51xc9bzqUk0J2S24X59A+9ZScvNTNGaSuRvBfoKxNpEI= Received: from BYAPR01MB4869.prod.exchangelabs.com (20.177.228.18) by BYAPR01MB4677.prod.exchangelabs.com (20.177.226.86) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2263.14; Mon, 16 Sep 2019 10:11:46 +0000 Received: from BYAPR01MB4869.prod.exchangelabs.com ([fe80::a016:e802:d3d0:f1c7]) by BYAPR01MB4869.prod.exchangelabs.com ([fe80::a016:e802:d3d0:f1c7%3]) with mapi id 15.20.2263.023; Mon, 16 Sep 2019 10:11:46 +0000 From: Feng Xue OS To: Jan Hubicka CC: Martin Jambor , "gcc-patches@gcc.gnu.org" Subject: [PATCH 1/2 V3] Setup predicate for switch default case in IPA (PR ipa/91089) Date: Mon, 16 Sep 2019 10:11:46 +0000 Message-ID: References: , <20190914155710.kjmnk42tdkdgmzd7@kam.mff.cuni.cz> In-Reply-To: <20190914155710.kjmnk42tdkdgmzd7@kam.mff.cuni.cz> authentication-results: spf=none (sender IP is ) smtp.mailfrom=fxue@os.amperecomputing.com; x-ms-oob-tlc-oobclassifiers: OLM:9508; received-spf: None (protection.outlook.com: os.amperecomputing.com does not designate permitted sender hosts) x-ms-exchange-senderadcheck: 1 x-ms-exchange-transport-forked: True MIME-Version: 1.0 X-MS-Exchange-CrossTenant-mailboxtype: HOSTED X-MS-Exchange-CrossTenant-userprincipalname: NM9YgKHnNe8iJ0AThPm9Ma0rZqTiZx1Wi+db2kRSSSOBqCOi9uoFFG6loNy7i6B9BsDsKP+FAKYYGxDieIXwVPjZclsjkF3SEEYlGe9gRQY= >> + if (this_code != ERROR_MARK >> + && !dominated_by_p (CDI_POST_DOMINATORS, bb, e->dest)) >> { >> predicate p >> = add_condition (summary, index, size, &aggpos, this_code, > So this change is handling the diamond conditional you describe above? > This is bit of hack since it leaves the edge predicate unnecesarily > conservative though I see it saves some conditions to be inserted and > makes things to go smoother. > > Please add a comment that explain this and reffers to the other places > where we do this (in the switch handling below). Done. > I believe the case ranges always has to be INTEGER_CST. In this case all > this can be written using wide ints and produce a lot better code > (avoiding need to build & lookup & share all temporary tree codes). > You can take a look at the tree-switch-conversion code which does quite > some of this wide int handling. > > Richard may have an opinion on this. Done. > So this basically the idea is to or BB's predicate to the > post-dominator predicate. This seems safe to do (we need to be careful > so that the dataflow still converges), but I would preffer to get this > in separately possibly with a testcase that shows an improvement in the > dataflow answer. I've split the patch to two. Thanks for your comments. Feng diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi index 1391a562c35..7f312c96f37 100644 --- a/gcc/doc/invoke.texi +++ b/gcc/doc/invoke.texi @@ -11960,6 +11960,12 @@ not spend too much time analyzing huge functions, it gives up and consider all memory clobbered after examining @option{ipa-max-aa-steps} statements modifying memory. +@item ipa-max-switch-predicate-bounds +Maximal number of boundary endpoints of case ranges of switch statement. +For switch exceeding this limit, IPA-CP will not construct cloning cost +predicate, which is used to estimate cloning benefit, for default case +of the switch statement. + @item lto-partitions Specify desired number of partitions produced during WHOPR compilation. The number of partitions should exceed the number of CPUs used for compilation. diff --git a/gcc/ipa-fnsummary.c b/gcc/ipa-fnsummary.c index 278bf606661..1bf1806eaf8 100644 --- a/gcc/ipa-fnsummary.c +++ b/gcc/ipa-fnsummary.c @@ -1269,13 +1269,21 @@ set_switch_stmt_execution_predicate (struct ipa_func_body_info *fbi, if (!unmodified_parm_or_parm_agg_item (fbi, last, op, &index, &size, &aggpos)) return; + auto_vec > ranges; + tree type = TREE_TYPE (op); + int bound_limit = PARAM_VALUE (PARAM_IPA_MAX_SWITCH_PREDICATE_BOUNDS); + int bound_count = 0; + wide_int vr_wmin, vr_wmax; + value_range_kind vr_type = get_range_info (op, &vr_wmin, &vr_wmax); + FOR_EACH_EDGE (e, ei, bb->succs) { e->aux = edge_predicate_pool.allocate (); *(predicate *) e->aux = false; } + n = gimple_switch_num_labels (last); - for (case_idx = 0; case_idx < n; ++case_idx) + for (case_idx = 1; case_idx < n; ++case_idx) { tree cl = gimple_switch_label (last, case_idx); tree min, max; @@ -1285,12 +1293,7 @@ set_switch_stmt_execution_predicate (struct ipa_func_body_info *fbi, min = CASE_LOW (cl); max = CASE_HIGH (cl); - /* For default we might want to construct predicate that none - of cases is met, but it is bit hard to do not having negations - of conditionals handy. */ - if (!min && !max) - p = true; - else if (!max) + if (!max) p = add_condition (summary, index, size, &aggpos, EQ_EXPR, unshare_expr_without_location (min)); else @@ -1304,7 +1307,113 @@ set_switch_stmt_execution_predicate (struct ipa_func_body_info *fbi, } *(class predicate *) e->aux = p.or_with (summary->conds, *(class predicate *) e->aux); + + /* If there are too many disjoint case ranges, predicate for default + case might become too complicated. So add a limit here. */ + if (bound_count > bound_limit) + continue; + + bool new_range = true; + + if (!ranges.is_empty ()) + { + wide_int curr_wmin = wi::to_wide (min); + wide_int last_wmax = wi::to_wide (ranges.last ().second); + + /* Merge case ranges if they are continuous. */ + if (curr_wmin == last_wmax + 1) + new_range = false; + else if (vr_type == VR_ANTI_RANGE) + { + /* If two disjoint case ranges can be connected by anti-range + of switch index, combine them to one range. */ + if (wi::lt_p (vr_wmax, curr_wmin - 1, TYPE_SIGN (type))) + vr_type = VR_UNDEFINED; + else if (wi::le_p (vr_wmin, last_wmax + 1, TYPE_SIGN (type))) + new_range = false; + } + } + + if (!max) + max = min; + + /* Create/extend a case range. And we count endpoints of range set, + this number nearly equals to number of conditions that we will create + for predicate of default case. */ + if (new_range) + { + bound_count += (min == max) ? 1 : 2; + ranges.safe_push (std::make_pair (min, max)); + } + else + { + bound_count += (ranges.last ().first == ranges.last ().second); + ranges.last ().second = max; + } + } + + e = gimple_switch_edge (cfun, last, 0); + if (bound_count > bound_limit) + { + *(class predicate *) e->aux = true; + return; } + + predicate p_seg = true; + predicate p_all = false; + + if (vr_type != VR_RANGE) + { + vr_wmin = wi::to_wide (TYPE_MIN_VALUE (type)); + vr_wmax = wi::to_wide (TYPE_MAX_VALUE (type)); + } + + /* Construct predicate to represent default range set that is negation of + all case ranges. Case range is classified as containing single/non-single + values. Suppose a piece of case ranges in the following. + + [D1...D2] [S1] ... [Sn] [D3...D4] + + To represent default case's range sets between two non-single value + case ranges (From D2 to D3), we construct predicate as: + + D2 < x < D3 && x != S1 && ... && x != Sn + */ + for (size_t i = 0; i < ranges.length (); i++) + { + tree min = ranges[i].first; + tree max = ranges[i].second; + + if (min == max) + p_seg &= add_condition (summary, index, size, &aggpos, NE_EXPR, + unshare_expr_without_location (min)); + else + { + /* Do not create sub-predicate for range that is beyond low bound + of switch index. */ + if (wi::lt_p (vr_wmin, wi::to_wide (min), TYPE_SIGN (type))) + { + p_seg &= add_condition (summary, index, size, &aggpos, LT_EXPR, + unshare_expr_without_location (min)); + p_all = p_all.or_with (summary->conds, p_seg); + } + + /* Do not create sub-predicate for range that is beyond up bound + of switch index. */ + if (wi::le_p (vr_wmax, wi::to_wide (max), TYPE_SIGN (type))) + { + p_seg = false; + break; + } + + p_seg = add_condition (summary, index, size, &aggpos, GT_EXPR, + unshare_expr_without_location (max)); + } + } + + p_all = p_all.or_with (summary->conds, p_seg); + *(class predicate *) e->aux + = p_all.or_with (summary->conds, *(class predicate *) e->aux); } diff --git a/gcc/params.def b/gcc/params.def index 13001a7bb2d..1461aa4849d 100644 --- a/gcc/params.def +++ b/gcc/params.def @@ -1123,6 +1123,14 @@ DEFPARAM (PARAM_IPA_MAX_AA_STEPS, "parameter analysis based on alias analysis in any given function.", 25000, 0, 0) +DEFPARAM (PARAM_IPA_MAX_SWITCH_PREDICATE_BOUNDS, + "ipa-max-switch-predicate-bounds", + "Maximal number of boundary endpoints of case ranges of switch " + "statement. For switch exceeding this limit, do not construct cost-" + "evaluating predicate for default case during IPA function summary" + "generation.", + 5, 0, 0) + /* WHOPR partitioning configuration. */ DEFPARAM (PARAM_LTO_PARTITIONS, diff --git a/gcc/testsuite/gcc.dg/ipa/pr91089.c b/gcc/testsuite/gcc.dg/ipa/pr91089.c new file mode 100644 index 00000000000..e9e206fc24d --- /dev/null +++ b/gcc/testsuite/gcc.dg/ipa/pr91089.c @@ -0,0 +1,62 @@ +/* { dg-do compile } */ +/* { dg-options "-O3 -fdump-ipa-cp-details -fdump-ipa-fnsummary-details --param ipa-max-switch-predicate-bounds=10 -fno-inline" } */ + +int fn (); + +int data; + +int callee (int i) +{ + switch (i) + { + case -126: return i + 13; + case -127: return i + 5; + case -8: return i * i; + case 0: return i % 9; + case 5: + case 7: + case 6: return 3; + default: + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + } + + return data += i; +} + +int caller () +{ + return callee (-127) + + callee (-126) + + callee (-8) + + callee (0) + + callee (5) + + callee (6) + + callee (7) + + callee (100); +} + +/* { dg-final { scan-ipa-dump-times "Creating a specialized node of callee" 7 "cp" } } */ +/* { dg-final { scan-ipa-dump "op0 < -127" "fnsummary" } } */ +/* { dg-final { scan-ipa-dump "op0 > -126" "fnsummary" } } */ +/* { dg-final { scan-ipa-dump "op0 != -8" "fnsummary" } } */ +/* { dg-final { scan-ipa-dump "op0 != 0" "fnsummary" } } */ +/* { dg-final { scan-ipa-dump "op0 < 5" "fnsummary" } } */ +/* { dg-final { scan-ipa-dump "op0 > 7" "fnsummary" } } */ From patchwork Mon Sep 16 10:16:11 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Feng Xue OS X-Patchwork-Id: 1162707 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-509046-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=os.amperecomputing.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="e4A17VEZ"; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=os.amperecomputing.com header.i=@os.amperecomputing.com header.b="b5fwiH0b"; 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 46X2Fz54Ypz9sNf for ; Mon, 16 Sep 2019 20:16:23 +1000 (AEST) 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:references:in-reply-to :content-type:content-transfer-encoding:mime-version; q=dns; s= default; b=uzPtNrFZcRAKpdXvMqK+QhB6VpJU83lZJURqaLpYDg0G2F1KfHxDv E+4vpi5IT21KeHzLw7gliS/mvJvAheEoet0a50t+ZjZEWqR5CS6Yp59qTLoEtKG0 VAqxQWZ5G2K25nFmf5YH/n5GOUlwy0e4SNZ2g+7V1ty9YsKUNCetNU= 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:references:in-reply-to :content-type:content-transfer-encoding:mime-version; s=default; bh=Ae+GyC/Q9+46B5UmJyCqEKFOIj4=; b=e4A17VEZa/WEGGRyuvVhfNhS00Y0 tSxnod4FlJf2AqNPuiqKzQVjD5p0MAeI4eRZrm/Dua9p/4JYLzIoP6yZoeO+jT34 OOx/Oh4Gan30wUaK9rWqHvwTrxvUl3MFnUXeiTF8LNkIbJXoD0YoePMC3tqcUIqZ G0oW0Y3e8FsbQcQ= Received: (qmail 33118 invoked by alias); 16 Sep 2019 10:16:16 -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 33105 invoked by uid 89); 16 Sep 2019 10:16:16 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-24.8 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_NONE, SPF_HELO_PASS, SPF_PASS autolearn=ham version=3.3.1 spammy=sk:analyze X-HELO: NAM01-BY2-obe.outbound.protection.outlook.com Received: from mail-eopbgr810102.outbound.protection.outlook.com (HELO NAM01-BY2-obe.outbound.protection.outlook.com) (40.107.81.102) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 16 Sep 2019 10:16:14 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=E4XTJiEICVOWnoYIe5jqfsorGxSWPOev536sACBPMwY7OziGHe/EGuebAghNtBmWhuDquVQ2ua9YC+kqSO5fQkr07zfoMUDQ/9MeQTrVwHh1KFtfdMfwdN7yVVzoHZ5QKwkZcJ8ViRHQN3wyEkaedET0WGH8hFL6kyqCHOMk3yI22zsZlRzXOfDB5s01P+ANXHYNXgXNgcelACC6PakJCZG56Vjes8MDgj0SGI9uvfPR6hcmYqfcvseqs5hu9aFLOoMDh62qGemJzXL8cJxIXNnler9/nwrfIBSt/CAiJ1cDDTiABDUdlbKC5fgdI+WLGK+Hn9pn22n65z4RjT5Org== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=yy6O/rGUxPc9WD828gVP9X6Jp0NYbHAOw5AliFAfudE=; b=C7wg/13K9qqQTiLXrTe9g1AKg90KVB5JrB1BA6+NGT6/Sb3n0GeKX/XxnPRYhv27ay4pUqUAU3CnythRC99dyu+klVErWa03g2M48oqHwmYJM69Ovj2KoLBTRDrd/wnUOK+S58/+T4u34rrR7w1o8oyszSScZVvR5qQ8/S+qgSUyTu3k3zXdTSqHpp3c4uuGwOqmoDZVRPKDT9TRpPczH4bL0YVjXZKlWJPcgurPtbZNncoReDxBiiYfmRomU1guM2/WzZOsej1PkcBoOfkGSIWVGv0qhJ0my7KVN2Cn3pe1g7h7Ihpe+wDjjWMpYzG23U8FJCHtwkyN2hAn+zf8aA== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=os.amperecomputing.com; dmarc=pass action=none header.from=os.amperecomputing.com; dkim=pass header.d=os.amperecomputing.com; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=os.amperecomputing.com; s=selector2; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=yy6O/rGUxPc9WD828gVP9X6Jp0NYbHAOw5AliFAfudE=; b=b5fwiH0biOdLXvptNQ76dtBarShkXXh9MtCBx9P207eG2JqYZmcA+qGA6IMSTmB6udjCWjkuUGXjtr0sxZs+hdpPHqGtCMF/Y4eaU8dMmfQDr/Hx7iZL1W6czmqZkVubZlramaIxZGi3lRN3huZeVOUibTGt/AM8W99LuXdl9T0= Received: from BYAPR01MB4869.prod.exchangelabs.com (20.177.228.18) by BYAPR01MB4536.prod.exchangelabs.com (20.178.0.161) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2263.17; Mon, 16 Sep 2019 10:16:11 +0000 Received: from BYAPR01MB4869.prod.exchangelabs.com ([fe80::a016:e802:d3d0:f1c7]) by BYAPR01MB4869.prod.exchangelabs.com ([fe80::a016:e802:d3d0:f1c7%3]) with mapi id 15.20.2263.023; Mon, 16 Sep 2019 10:16:11 +0000 From: Feng Xue OS To: Jan Hubicka CC: Martin Jambor , "gcc-patches@gcc.gnu.org" Subject: [PATCH 2/2 V3] Use post-dom info to update if/switch predicate (PR ipa/91089) Date: Mon, 16 Sep 2019 10:16:11 +0000 Message-ID: References: , <20190914155710.kjmnk42tdkdgmzd7@kam.mff.cuni.cz> In-Reply-To: <20190914155710.kjmnk42tdkdgmzd7@kam.mff.cuni.cz> authentication-results: spf=none (sender IP is ) smtp.mailfrom=fxue@os.amperecomputing.com; x-ms-oob-tlc-oobclassifiers: OLM:9508; received-spf: None (protection.outlook.com: os.amperecomputing.com does not designate permitted sender hosts) x-ms-exchange-senderadcheck: 1 x-ms-exchange-transport-forked: True MIME-Version: 1.0 X-MS-Exchange-CrossTenant-mailboxtype: HOSTED X-MS-Exchange-CrossTenant-userprincipalname: PFrGOEPMGJib2YnZyrAgfxov/fq3wUfgkZSUsG7FGnEfFcXWtYQlMS9QjL4urlrfkWep5F+gh6otFVgFJ50FnQA3l3IHSe+y02Itnv4qYag= This one is split from original patch. Feng diff --git a/gcc/ipa-fnsummary.c b/gcc/ipa-fnsummary.c index 1bf1806eaf8..5423756d275 100644 --- a/gcc/ipa-fnsummary.c +++ b/gcc/ipa-fnsummary.c @@ -1197,8 +1197,14 @@ set_cond_stmt_execution_predicate (struct ipa_func_body_info *fbi, ? code : inverted_code); /* invert_tree_comparison will return ERROR_MARK on FP comparsions that are not EQ/NE instead of returning proper - unordered one. Be sure it is not confused with NON_CONSTANT. */ - if (this_code != ERROR_MARK) + unordered one. Be sure it is not confused with NON_CONSTANT. + + And if the edge's target is the final block of diamond CFG graph + of this conditional statement, we do not need to compute + predicate for the edge because the final block's predicate must + be at least as that of the first block of the statement. */ + if (this_code != ERROR_MARK + && !dominated_by_p (CDI_POST_DOMINATORS, bb, e->dest)) { predicate p = add_condition (summary, index, size, &aggpos, this_code, @@ -1282,6 +1288,14 @@ set_switch_stmt_execution_predicate (struct ipa_func_body_info *fbi, *(predicate *) e->aux = false; } + e = gimple_switch_edge (cfun, last, 0); + /* Set BOUND_COUNT to maximum count to bypass computing predicate for + default case if its target basic block is in convergence point of all + switch cases, which can be determined by checking whether it + post-dominates the switch statement. */ + if (dominated_by_p (CDI_POST_DOMINATORS, bb, e->dest)) + bound_count = INT_MAX; + n = gimple_switch_num_labels (last); for (case_idx = 1; case_idx < n; ++case_idx) { @@ -1293,7 +1307,12 @@ set_switch_stmt_execution_predicate (struct ipa_func_body_info *fbi, min = CASE_LOW (cl); max = CASE_HIGH (cl); - if (!max) + /* The case's target basic block is in convergence point of all switch + cases, its predicate should be at least as that of the switch + statement. */ + if (dominated_by_p (CDI_POST_DOMINATORS, bb, e->dest)) + p = true; + else if (!max) p = add_condition (summary, index, size, &aggpos, EQ_EXPR, unshare_expr_without_location (min)); else @@ -1463,10 +1482,10 @@ compute_bb_predicates (struct ipa_func_body_info *fbi, break; } } - if (p == false) - gcc_checking_assert (!bb->aux); - else + if (p != false) { + basic_block pdom_bb; + if (!bb->aux) { done = false; @@ -1485,6 +1504,34 @@ compute_bb_predicates (struct ipa_func_body_info *fbi, *((predicate *) bb->aux) = p; } } + + /* For switch/if statement, we can OR-combine predicates of all + its cases/branches to get predicate for basic block in their + convergence point, but sometimes this will generate very + complicated predicate. Actually, we can get simplified + predicate in another way by using the fact that predicate + for a basic block must also hold true for its post dominators. + To be specific, basic block in convergence point of + conditional statement should include predicate of the + statement. */ + pdom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb); + if (pdom_bb == EXIT_BLOCK_PTR_FOR_FN (my_function) || !pdom_bb) + ; + else if (!pdom_bb->aux) + { + done = false; + pdom_bb->aux = edge_predicate_pool.allocate (); + *((predicate *) pdom_bb->aux) = p; + } + else if (p != *(predicate *) pdom_bb->aux) + { + p = p.or_with (summary->conds, *(predicate *)pdom_bb->aux); + if (p != *(predicate *) pdom_bb->aux) + { + done = false; + *((predicate *) pdom_bb->aux) = p; + } + } } } } @@ -2089,6 +2136,7 @@ analyze_function_body (struct cgraph_node *node, bool early) if (opt_for_fn (node->decl, optimize)) { calculate_dominance_info (CDI_DOMINATORS); + calculate_dominance_info (CDI_POST_DOMINATORS); if (!early) loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS); else @@ -2469,6 +2517,7 @@ analyze_function_body (struct cgraph_node *node, bool early) else if (!ipa_edge_args_sum) ipa_free_all_node_params (); free_dominance_info (CDI_DOMINATORS); + free_dominance_info (CDI_POST_DOMINATORS); } if (dump_file) { diff --git a/gcc/testsuite/gcc.dg/ipa/pr91089.c b/gcc/testsuite/gcc.dg/ipa/pr91089.c index e9e206fc24d..92b5550aa76 100644 --- a/gcc/testsuite/gcc.dg/ipa/pr91089.c +++ b/gcc/testsuite/gcc.dg/ipa/pr91089.c @@ -41,6 +41,52 @@ int callee (int i) return data += i; } +int fn2 (); + +int callee_complex_predicate (int i) +{ + switch (i ) + { + case 0: + fn (); + fn (); + fn (); + case 1: + fn (); + fn (); + case -1: + fn (); + case -2: + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + data += i; + break; + } + + if (i == 1000) + { + int j; + + for (j = 0; j < 100; j++) + fn2 (); + } + return i + 3; +} + int caller () { return callee (-127) + @@ -60,3 +106,4 @@ int caller () /* { dg-final { scan-ipa-dump "op0 != 0" "fnsummary" } } */ /* { dg-final { scan-ipa-dump "op0 < 5" "fnsummary" } } */ /* { dg-final { scan-ipa-dump "op0 > 7" "fnsummary" } } */ +/* { dg-final { scan-ipa-dump "loop depth: 1 .+ time:\[ \]*\[0-9\]+ predicate: \\(op0 == 1000\\)" "fnsummary" } } */