From patchwork Thu Nov 18 19:28:10 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 47901 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id AEEE5385BF83 for ; Thu, 18 Nov 2021 19:30:16 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org AEEE5385BF83 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1637263816; bh=ufbhmMI5OUpws9W/DaAAdZ2MCjswtaftUo/HvC5LDdA=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=nQCbEyM2Dd8oOSuTTbSoNztuaWNwM1G5XgxPHQ3Td95kZgIQzkSsjdNHj4ztAieiK NLEzo8rc1Suq3A0JvXBotdFx3PSt8ZEQIzmE+CcAwyYRFbpEzJHbXYS+6nUsqYAFV1 BwfQMUDoUBBz8zt1ggU2OXEKbv5jRaqslq2HDQ8U= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id 7595C385C41D for ; Thu, 18 Nov 2021 19:28:15 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 7595C385C41D Received: from mail-qk1-f197.google.com (mail-qk1-f197.google.com [209.85.222.197]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-294-F_TJTRsyNayfe0MmTSdniQ-1; Thu, 18 Nov 2021 14:28:14 -0500 X-MC-Unique: F_TJTRsyNayfe0MmTSdniQ-1 Received: by mail-qk1-f197.google.com with SMTP id bq9-20020a05620a468900b004681cdb3483so5780038qkb.23 for ; Thu, 18 Nov 2021 11:28:13 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:date:mime-version:user-agent :content-language:to:from:subject:cc; bh=oyqGtjb/V5VxhjtWbbaskON2nWbABpZv/RVa0XTD05Y=; b=GaWEXsFY5Ly8ipn15iSIre0cVODhcOVAKGhz3pcyQtpSMConXNrD7MB1za5Crb7Np7 PJbS9NG8lhV6tAnaPf5f/JbMxbWmCnX0577weMHP0jkVx2NYipVfHt0tZsUG+WwVx32k 7gGa+wA+zSB4lRZgQMO3bJu0EoBwvuQdM8etwDYsPS8jw44PDfA++uoIeP6vtRPdL9YY itCoMmuVpS9XyM/ueREn3z/KlTWPhFs5hKroMc14La6aDzklJ28bpbR8aR7ouSp9bo1/ v494gyYRCv08fUVL3eNHPhWiMcfm74BtH3h4gaMdHk+cUpwhfnjskLV4wFySggpm1ABN NKvg== X-Gm-Message-State: AOAM532cLD3gl95P68kdr7eo2MKH/tZvU+0iOAllosW/g4tPbYLvxH6B BTLXOcWGfpSvGJLLYT50ExuJd6Dv9PLLKXoWz9aJrmmuBftCLq3lKPhLwnVXN/9H9n9SkJfHP5/ V+aI/MQmiJiQj4rA0fWui5+oefFak1o/8idFLPmqYltmefwMgXrgKYgF1u4R+zwhtVdcOKw== X-Received: by 2002:ac8:5a90:: with SMTP id c16mr28639943qtc.199.1637263692907; Thu, 18 Nov 2021 11:28:12 -0800 (PST) X-Google-Smtp-Source: ABdhPJwdrQ/jrpSeuqRfn19CO1iGwY9D1VxyBOu9P63mVXysHyZTx/DDO/KzihZnwa6EcAPWODt48A== X-Received: by 2002:ac8:5a90:: with SMTP id c16mr28639913qtc.199.1637263692653; Thu, 18 Nov 2021 11:28:12 -0800 (PST) Received: from ?IPV6:2607:fea8:a262:5f00::38cf? ([2607:fea8:a262:5f00::38cf]) by smtp.gmail.com with ESMTPSA id x125sm387044qkd.8.2021.11.18.11.28.11 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 18 Nov 2021 11:28:12 -0800 (PST) Message-ID: Date: Thu, 18 Nov 2021 14:28:10 -0500 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.3.1 To: gcc-patches Subject: [PATCH] PR tree-optimization/103254 - Limit depth for all GORI expressions. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-CA X-Spam-Status: No, score=-12.8 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Andrew MacLeod via Gcc-patches From: Andrew MacLeod Reply-To: Andrew MacLeod Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" At issue here is the dynamic approach we currently use for outgoing edge calculations.  It isn't normally a problem, but once you get a very large number of possible outgoing values (ie very long unrolled blocks) with pairs of values on a statement, and individual queries for each one, it becomes exponential if they relate to each other. So.  We previously introduced a param for PR 100081 which limited the depth of logical expressions GORI would pursue because we always make 2 or 4 queries for each logical expression, which accelerated the exponential behaviour much quicker. This patch reuses that to apply to any statement which has 2 ssa-names, as the potential for 2 queries can happen then as well..  leading to exponential behaviour.  Each statement we step back through with multiple ssa-names decreases the odds of calculating a useful outgoing range anyway.  This will remove ridiculous behaviour like this PR demonstrates. Next release I plan to revamp GORI to cache outgoing values, which will eliminate all this sort of behaviour, and we can remove all such restrictions. Bootstrapped on x86_64-pc-linux-gnu with no regressions.  OK for trunk? Andrew PS. This also points out something we are investigating with the threader.  There are no uses of _14 outside the block, so asking for its range is problematic and contributing to excess work and cache filling that we don't need to be doing.  The VRP passes do not demonstrate this behaviour unless, as observed, we ask for details output which queries *all* the names. commit bfecf512fb719dcb072e54d842b1e7a62fe03d2d Author: Andrew MacLeod Date: Wed Nov 17 14:14:06 2021 -0500 Limit depth for all GORI expressions. Apply the logical_depth limit ranger uses to all stmts with multiple ssa-names to avoid excessive outgoing calculations. gcc/ PR tree-optimization/103254 * gimple-range-gori.cc (range_def_chain::get_def_chain): Limit the depth for all statements with multple ssa names. gcc/testsuite/ * gcc.dg/pr103254.c: New. diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc index fb2d571ef44..911d7ac4ec8 100644 --- a/gcc/gimple-range-gori.cc +++ b/gcc/gimple-range-gori.cc @@ -331,7 +331,6 @@ range_def_chain::get_def_chain (tree name) { tree ssa1, ssa2, ssa3; unsigned v = SSA_NAME_VERSION (name); - bool is_logical = false; // If it has already been processed, just return the cached value. if (has_def_chain (name)) @@ -348,15 +347,6 @@ range_def_chain::get_def_chain (tree name) gimple *stmt = SSA_NAME_DEF_STMT (name); if (gimple_range_handler (stmt)) { - is_logical = is_gimple_logical_p (stmt); - // Terminate the def chains if we see too many cascading logical stmts. - if (is_logical) - { - if (m_logical_depth == param_ranger_logical_depth) - return NULL; - m_logical_depth++; - } - ssa1 = gimple_range_ssa_p (gimple_range_operand1 (stmt)); ssa2 = gimple_range_ssa_p (gimple_range_operand2 (stmt)); ssa3 = NULL_TREE; @@ -376,6 +366,14 @@ range_def_chain::get_def_chain (tree name) return NULL; } + // Terminate the def chains if we see too many cascading stmts. + if (m_logical_depth == param_ranger_logical_depth) + return NULL; + + // Increase the depth if we have a pair of ssa-names. + if (ssa1 && ssa2) + m_logical_depth++; + register_dependency (name, ssa1, gimple_bb (stmt)); register_dependency (name, ssa2, gimple_bb (stmt)); register_dependency (name, ssa3, gimple_bb (stmt)); @@ -383,7 +381,7 @@ range_def_chain::get_def_chain (tree name) if (!ssa1 && !ssa2 & !ssa3) set_import (m_def_chain[v], name, NULL); - if (is_logical) + if (ssa1 && ssa2) m_logical_depth--; return m_def_chain[v].bm; diff --git a/gcc/testsuite/gcc.dg/pr103254.c b/gcc/testsuite/gcc.dg/pr103254.c new file mode 100644 index 00000000000..62d2415f216 --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr103254.c @@ -0,0 +1,25 @@ +/* { dg-do compile } */ +/* { dg-options "-O3" } */ +/* { dg-timeout 10 } */ + +short int i; + +void +foo (void) +{ + for (i = 1; i < 2; i += 4) + { + int j; + + for (j = 0; j < 5; j += 4) + { + int k; + + for (k = 0; k < 68; k += 4) + { + i &= j; + j &= i; + } + } + } +}