From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1011) id 72F4A3858D20; Mon, 26 Jun 2023 14:02:13 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 72F4A3858D20 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1687788133; bh=O+3vbzqbbCh28Ztw0jzHw07K+cqh9rWVbU6cdTwqdks=; h=From:To:Subject:Date:From; b=g+Jo77WAsTKrGHjR2aQ0zrDSqYlEeu8b91v/g6xCw10NmiwSwISK1cg8auu+rccjN YaQ+5Njw1tdou1X8G41NvNvyqELd6UKxPE/YoW3hz3AxeS4FzbZ9lJV+7mHmcrgdQl d/z3oOESbBzLRRAWtw5zHqpTsuhxAsmk86Tl0HJc= MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: Andrew Macleod To: gcc-cvs@gcc.gnu.org Subject: [gcc r14-2097] Avoid redundant GORI calcuations. X-Act-Checkin: gcc X-Git-Author: Andrew MacLeod X-Git-Refname: refs/heads/master X-Git-Oldrev: 9302b0743b366037379af0568534c23ab597b4d4 X-Git-Newrev: 4dfeb1cd8dfca234186216d891ec8f46235c3a14 Message-Id: <20230626140213.72F4A3858D20@sourceware.org> Date: Mon, 26 Jun 2023 14:02:13 +0000 (GMT) List-Id: https://gcc.gnu.org/g:4dfeb1cd8dfca234186216d891ec8f46235c3a14 commit r14-2097-g4dfeb1cd8dfca234186216d891ec8f46235c3a14 Author: Andrew MacLeod Date: Thu Jun 22 10:00:12 2023 -0400 Avoid redundant GORI calcuations. When GORI evaluates a statement, if operand 1 and 2 are both in the dependency chain, GORI evaluates the name through both operands sequentially and combines the results. If either operand is in the dependency chain of the other, this evaluation will do the same work twice, for questionable gain. Instead, simple evaluate only the operand which depends on the other and keep the evaluation linear in time. * gimple-range-gori.cc (compute_operand1_and_operand2_range): Check for interdependence between operands 1 and 2. Diff: --- gcc/gimple-range-gori.cc | 21 +++++++++++++++++---- 1 file changed, 17 insertions(+), 4 deletions(-) diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc index abc70cd54ee..4ee0ae36014 100644 --- a/gcc/gimple-range-gori.cc +++ b/gcc/gimple-range-gori.cc @@ -1291,13 +1291,26 @@ gori_compute::compute_operand1_and_operand2_range (vrange &r, { Value_Range op_range (TREE_TYPE (name)); - // Calculate a good a range for op2. Since op1 == op2, this will - // have already included whatever the actual range of name is. - if (!compute_operand2_range (op_range, handler, lhs, name, src, rel)) + // If op1 is in the def chain of op2, we'll do the work twice to evalaute + // op1. This can result in an exponential time calculation. + // Instead just evaluate op2, which will eventualy get to op1. + if (in_chain_p (handler.operand1 (), handler.operand2 ())) + return compute_operand2_range (r, handler, lhs, name, src, rel); + + // Likewise if op2 is in the def chain of op1. + if (in_chain_p (handler.operand2 (), handler.operand1 ())) + return compute_operand1_range (r, handler, lhs, name, src, rel); + + // Calculate a good a range through op2. + if (!compute_operand2_range (r, handler, lhs, name, src, rel)) return false; + // If op1 == op2 there is again no need to go further. + if (handler.operand1 () == handler.operand2 ()) + return true; + // Now get the range thru op1. - if (!compute_operand1_range (r, handler, lhs, name, src, rel)) + if (!compute_operand1_range (op_range, handler, lhs, name, src, rel)) return false; // Both operands have to be simultaneously true, so perform an intersection.