From patchwork Wed Aug 29 10:55:30 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Aldy Hernandez X-Patchwork-Id: 963387 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-484680-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=redhat.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="jnAW4f5s"; 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 420jG76hThz9s3C for ; Wed, 29 Aug 2018 20:55:43 +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 :subject:to:message-id:date:mime-version:content-type; q=dns; s= default; b=EjQp525Frw2pw6v+z0PEL1KaZkKyVzqKpRNfVkA3V411VKUf8pbH+ vVLju9zi0ZcRAdlKxbn+YFW2pO2c/dCSdMjboY5CheVNXGKgKtSM6obYUx6b0nt1 XnwzF3cQ16EuisOoAt59x4YqpF7nb4+yJoVgh8zEUGqIIiSWxqbGJA= 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 :subject:to:message-id:date:mime-version:content-type; s= default; bh=Gw8Yhdyqp822Crpf0U0VvPTGGIs=; b=jnAW4f5sNr5hlXpzatBV AapZDzpwhb8vbrldGMD9o3oVOoszyigTh9Rp6L+olHBSprce9TOsbnPPj5MJhP2J R3vrL/qgd0LybtDxEQu4hmrsIJoa0uHDe9D+UKfX1S7S7tsiSgRhj8zQ9mjfdDAu ResbiY5dHk/bexAlfML+pLU= Received: (qmail 96677 invoked by alias); 29 Aug 2018 10:55:36 -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 96662 invoked by uid 89); 29 Aug 2018 10:55:36 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-26.8 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.2 spammy=10666, wide_int_binop, int_const_binop, 5510 X-HELO: mail-wm0-f49.google.com Received: from mail-wm0-f49.google.com (HELO mail-wm0-f49.google.com) (74.125.82.49) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 29 Aug 2018 10:55:34 +0000 Received: by mail-wm0-f49.google.com with SMTP id j192-v6so5070390wmj.1 for ; Wed, 29 Aug 2018 03:55:34 -0700 (PDT) Received: from abulafia.quesejoda.com (131.107.133.37.dynamic.jazztel.es. [37.133.107.131]) by smtp.gmail.com with ESMTPSA id s10-v6sm7624451wmd.22.2018.08.29.03.55.31 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 29 Aug 2018 03:55:31 -0700 (PDT) From: Aldy Hernandez Subject: VRP: abstract out bitwise AND/OR optimizations To: gcc-patches Message-ID: Date: Wed, 29 Aug 2018 06:55:30 -0400 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.8.0 MIME-Version: 1.0 X-IsSubscribed: yes I thought I was done with this one as well, but it looks like we can push more things out to wide-int-range.*. I also pushed the optimization itself into wide_int_range_bit_{and,or}, for maximal sharing. And finally, I split out getting the mask and the bounds into its own function (wide_int_range_get_mask_and_bounds), because I have an upcoming optimization that uses this information, and there's no sense duplicating work :). No change in functionality. Tested on x86-64 Linux with all languages. OK? commit df27e625c8322b63d4ef7baa0a8a9521e879c995 Author: Aldy Hernandez Date: Tue Aug 28 13:16:22 2018 +0200 * tree-vrp.c (vrp_can_optimize_bit_op): Remove. (extract_range_from_binary_expr_1): Do not call vrp_can_optimize_bit_op. * wide-int-range.cc (wide_int_range_can_optimize_bit_op): Make static. (wide_int_range_get_mask_and_bounds): New. (wide_int_range_optimize_bit_op): New. (wide_int_range_bit_ior): Call wide_int_range_optimize_bit_op. (wide_int_range_bit_and): Same. * wide-int-range.h (wide_int_range_can_optimize_bit_op): Remove. (wide_int_range_optimize_bit_op): New. (wide_int_range_get_mask_and_bounds): New. diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index f20730a85ba..d14e4cf7599 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -1066,49 +1066,6 @@ extract_range_from_multiplicative_op (value_range *vr, set_value_range_to_varying (vr); } -/* Value range wrapper for wide_int_range_can_optimize_bit_op. - - If a bit operation on two ranges can be easily optimized in terms - of a mask, store the optimized new range in VR and return TRUE. */ - -static bool -vrp_can_optimize_bit_op (value_range *vr, enum tree_code code, - value_range *vr0, value_range *vr1) -{ - tree lower_bound, upper_bound, mask; - if (code != BIT_AND_EXPR && code != BIT_IOR_EXPR) - return false; - if (range_int_cst_singleton_p (vr1)) - { - if (!range_int_cst_p (vr0)) - return false; - mask = vr1->min; - lower_bound = vr0->min; - upper_bound = vr0->max; - } - else if (range_int_cst_singleton_p (vr0)) - { - if (!range_int_cst_p (vr1)) - return false; - mask = vr0->min; - lower_bound = vr1->min; - upper_bound = vr1->max; - } - else - return false; - if (wide_int_range_can_optimize_bit_op (code, - wi::to_wide (lower_bound), - wi::to_wide (upper_bound), - wi::to_wide (mask))) - { - tree min = int_const_binop (code, lower_bound, mask); - tree max = int_const_binop (code, upper_bound, mask); - set_value_range (vr, VR_RANGE, min, max, NULL); - return true; - } - return false; -} - /* If BOUND will include a symbolic bound, adjust it accordingly, otherwise leave it as is. @@ -1702,9 +1659,6 @@ extract_range_from_binary_expr_1 (value_range *vr, } else if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR || code == BIT_XOR_EXPR) { - if (vrp_can_optimize_bit_op (vr, code, &vr0, &vr1)) - return; - wide_int may_be_nonzero0, may_be_nonzero1; wide_int must_be_nonzero0, must_be_nonzero1; wide_int wmin, wmax; diff --git a/gcc/wide-int-range.cc b/gcc/wide-int-range.cc index 3cdcede04cd..04d391b33d5 100644 --- a/gcc/wide-int-range.cc +++ b/gcc/wide-int-range.cc @@ -403,7 +403,7 @@ wide_int_range_lshift (wide_int &res_lb, wide_int &res_ub, It is up to the caller to perform the actual folding above. */ -bool +static bool wide_int_range_can_optimize_bit_op (tree_code code, const wide_int &lb, const wide_int &ub, const wide_int &mask) @@ -443,6 +443,68 @@ wide_int_range_can_optimize_bit_op (tree_code code, return false; } +/* Helper function for wide_int_range_optimize_bit_op. + + Calculates bounds and mask for a pair of ranges. The mask is the + singleton range among the ranges, if any. The bounds are the + bounds for the remaining range. */ + +bool +wide_int_range_get_mask_and_bounds (wide_int &mask, + wide_int &lower_bound, + wide_int &upper_bound, + const wide_int &vr0_min, + const wide_int &vr0_max, + const wide_int &vr1_min, + const wide_int &vr1_max) +{ + if (wi::eq_p (vr1_min, vr1_max)) + { + mask = vr1_min; + lower_bound = vr0_min; + upper_bound = vr0_max; + return true; + } + else if (wi::eq_p (vr0_min, vr0_max)) + { + mask = vr0_min; + lower_bound = vr1_min; + upper_bound = vr1_max; + return true; + } + return false; +} + +/* Optimize a bit operation (BIT_AND_EXPR or BIT_IOR_EXPR) if + possible. If so, return TRUE and store the result in + [RES_LB, RES_UB]. */ + +bool +wide_int_range_optimize_bit_op (wide_int &res_lb, wide_int &res_ub, + enum tree_code code, + signop sign, + const wide_int &vr0_min, + const wide_int &vr0_max, + const wide_int &vr1_min, + const wide_int &vr1_max) +{ + gcc_assert (code == BIT_AND_EXPR || code == BIT_IOR_EXPR); + + wide_int lower_bound, upper_bound, mask; + if (!wide_int_range_get_mask_and_bounds (mask, lower_bound, upper_bound, + vr0_min, vr0_max, vr1_min, vr1_max)) + return false; + if (wide_int_range_can_optimize_bit_op (code, + lower_bound, upper_bound, mask)) + { + wi::overflow_type ovf; + wide_int_binop (res_lb, code, lower_bound, mask, sign, &ovf); + wide_int_binop (res_ub, code, upper_bound, mask, sign, &ovf); + return true; + } + return false; +} + /* Calculate the XOR of two ranges and store the result in [WMIN,WMAX]. The two input ranges are described by their MUST_BE_NONZERO and MAY_BE_NONZERO bit masks. @@ -489,6 +551,10 @@ wide_int_range_bit_ior (wide_int &wmin, wide_int &wmax, const wide_int &must_be_nonzero1, const wide_int &may_be_nonzero1) { + if (wide_int_range_optimize_bit_op (wmin, wmax, BIT_IOR_EXPR, sign, + vr0_min, vr0_max, + vr1_min, vr1_max)) + return true; wmin = must_be_nonzero0 | must_be_nonzero1; wmax = may_be_nonzero0 | may_be_nonzero1; /* If the input ranges contain only positive values we can @@ -530,6 +596,10 @@ wide_int_range_bit_and (wide_int &wmin, wide_int &wmax, const wide_int &must_be_nonzero1, const wide_int &may_be_nonzero1) { + if (wide_int_range_optimize_bit_op (wmin, wmax, BIT_AND_EXPR, sign, + vr0_min, vr0_max, + vr1_min, vr1_max)) + return true; wmin = must_be_nonzero0 & must_be_nonzero1; wmax = may_be_nonzero0 & may_be_nonzero1; /* If both input ranges contain only negative values we can diff --git a/gcc/wide-int-range.h b/gcc/wide-int-range.h index 427ef34c6b4..eaf47bca449 100644 --- a/gcc/wide-int-range.h +++ b/gcc/wide-int-range.h @@ -55,10 +55,20 @@ extern void wide_int_range_set_zero_nonzero_bits (signop, const wide_int &ub, wide_int &may_be_nonzero, wide_int &must_be_nonzero); -extern bool wide_int_range_can_optimize_bit_op (tree_code, - const wide_int &lb, - const wide_int &ub, - const wide_int &mask); +extern bool wide_int_range_optimize_bit_op (wide_int &res_lb, wide_int &res_ub, + enum tree_code code, + signop sign, + const wide_int &vr0_lb, + const wide_int &vr0_ub, + const wide_int &vr1_lb, + const wide_int &vr1_ub); +extern bool wide_int_range_get_mask_and_bounds (wide_int &mask, + wide_int &lower_bound, + wide_int &upper_bound, + const wide_int &vr0_min, + const wide_int &vr0_max, + const wide_int &vr1_min, + const wide_int &vr1_max); extern bool wide_int_range_bit_xor (wide_int &wmin, wide_int &wmax, signop sign, unsigned prec,