From patchwork Fri Aug 12 10:43:27 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 658588 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org 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 3s9hMD6y0cz9sBR for ; Fri, 12 Aug 2016 20:43:51 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=kN5s3+O6; dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :mime-version:in-reply-to:references:from:date:message-id :subject:to:cc:content-type; q=dns; s=default; b=kHlkINr23YUQ5Yj V6aUfTVEXi9du6wgzwzKl6TrzOWcZTdIXTPC3sZQc8s+d2edC2T/mjI4VAZySyYM gE3J6uUtRpc6ezmWMn4dqCsD0Wbm5sFLJWpBvmgtDlSLRN7UodM4DZxPacqQU4qK jWGRgGwseqgctjLBstqo9NQOAbRE= 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 :mime-version:in-reply-to:references:from:date:message-id :subject:to:cc:content-type; s=default; bh=BR+8WpNlvs/fJqxUMKQuN MJakkA=; b=kN5s3+O6TdiaJDxZZN/Cd9ksj6hP+bnJWQEpzVolh9VdvGkjCJXjp h0omxdvktLZ8mZIIfkPpuEt2UqA32Vhd05oTK3khQI3dmK7V6dcJUIgUu8jMfgD8 vdksq8qgJ3Bp4byH77FeyX0UXIG+VKJAOyFyC2RZgq5zBQEzZAx57g= Received: (qmail 83194 invoked by alias); 12 Aug 2016 10:43: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 83178 invoked by uid 89); 12 Aug 2016 10:43:41 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.3 required=5.0 tests=AWL, BAYES_05, FREEMAIL_FROM, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=ham version=3.3.2 spammy=they'd, theyd, initialized, ssa_names X-HELO: mail-wm0-f51.google.com Received: from mail-wm0-f51.google.com (HELO mail-wm0-f51.google.com) (74.125.82.51) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 12 Aug 2016 10:43:31 +0000 Received: by mail-wm0-f51.google.com with SMTP id i5so24639811wmg.0 for ; Fri, 12 Aug 2016 03:43:30 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=JjGBPeO2BNPsThxTNnpv00MIs7AAEa2yBlgz3gIWObk=; b=k3ZFW+qTZ2AkIWbS+ct+NPkLFYQS+FPoprfNz8kLxwjrEWOT9kh/vWt2ZD1o4fKfLK eF+uXU3voHTYna9JPMjg4ycaM1evfpQsNA+vbA1huHLgZ9noSSS1O/tc+GgWngVv94dB MgjylETTWER3nK7pGgCZW5ywBFcJiEAX++o+ueKTm+uCCZzSkn9HHTGSfHeXs2wYlOAi ZAMWu3nhezIq68frtg4GeDd/QAmZ0vFMq2m7WzJqy1onCPlxGvnV2XoH9o+uuwfU/aDI cb0+kq3dTFF4QKnYKis4dMhUoiywWXJksfJCISdVi/lWfc3+WgpbrS7dBK/lZ8qrqwCD YP5Q== X-Gm-Message-State: AEkoouuqKmCW2LrjERE/bpCxXJ7qNkIi0IIW+qLi+29gCtH9iuB09jn89CpjzbmE0y4D21SStsI6wEoFi5Ywow== X-Received: by 10.194.77.142 with SMTP id s14mr14208174wjw.77.1470998608846; Fri, 12 Aug 2016 03:43:28 -0700 (PDT) MIME-Version: 1.0 Received: by 10.28.137.202 with HTTP; Fri, 12 Aug 2016 03:43:27 -0700 (PDT) In-Reply-To: <48e42d0c-057c-312a-4e41-cd78c8b38b5e@linaro.org> References: <57886949.8010300@linaro.org> <57886A71.6030103@linaro.org> <57888BD6.6070200@linaro.org> <578891C8.7090609@linaro.org> <19ff8188-aed7-0f9e-cc0b-0603698787ff@linaro.org> <48e42d0c-057c-312a-4e41-cd78c8b38b5e@linaro.org> From: Richard Biener Date: Fri, 12 Aug 2016 12:43:27 +0200 Message-ID: Subject: Re: [RFC][IPA-VRP] Early VRP Implementation To: kugan Cc: Andrew Pinski , "gcc-patches@gcc.gnu.org" , Jan Hubicka , Martin Jambor X-IsSubscribed: yes On Wed, Aug 3, 2016 at 3:17 AM, kugan wrote: > Hi Richard, > > Thanks for the review. > > On 28/07/16 21:34, Richard Biener wrote: >> >> On Thu, Jul 28, 2016 at 9:35 AM, kugan >> wrote: >>> >>> Hi Richard, >>> >>> Thanks for the review. >>>> >>>> >>>> >>>> It seems that in your pop_value_range you assume you only pop one >>>> range per BB - while that's likely true at the moment it will be a >>>> limitation >>>> in the future. You want to pop ranges until you hit the NULL marker >>>> in after_dom_children and unconditionally push a NULL marker. >>>> >>> I understand. Right now, I am adding only one assert based on the >>> condition. >>> But in future, we will be adding more so this is needed. I will do that. >>> >>>> For example to match current VRPs behavior on say >>>> >>>> i_2 = (int) j_3; >>>> if (i_2 < 0) >>>> ... >>>> >>>> which can register an assert for j_3 when i_2 < 0 is true we'd do that >>>> by re-simulating DEFs of uses we figured out new ranges of (and all >>>> their uses). All those ranges would be temporary as well, thus they'd >>>> need to be pushed/popped. In my quick prototype this was done >>>> using a worklist seeded by the names we can derive a range from from >>>> conditionals and "SSA propagating" from it. Note that for this >>>> the generic vrp_visit_stmt cannot be re-used as it doesn't push/pop, >>>> factoring out the lattice update is what is needed here. >>>> >>> >>> I dont think I understand this part. vrp_visit_stmt is going to add value >>> ranges for the variables defined in the if-block (in the example below it >>> is >>> for t). If we push the value range for i_2 and j_3 when we enter >>> if-block, >>> vrp_visit_stmt should compute "t" correctly. When we leave the if-block, >>> we >>> will pop i_2 and j_3. >>> >>> i_2 = (int) j_3; >>> if (i_2 < 0) >>> { >>> t = j_2 * 2; >>> } >>> Am I missing something here? >> >> >> It works if you push the old value before calling vrp_visit_stmt, yes. >> But I think >> you want to do that only if the value-range changed to avoid too many >> changes >> on the stack. I guess we can defer further refactoring and >> optimization of this case >> to the point where we consider looking back very aggressively. >> >>>> +/* Visit the basic blocks in the dominance order and set the Value >>>> Ranges >>>> (VR) >>>> + for SSA_NAMEs in the scope. Use this VR to discover more VRs. >>>> Restore the >>>> + old VR once the scope is exited. */ >>>> + >>>> +static bool >>>> +evrp_visit_phi_node_local (gphi *phi) >>>> +{ >>>> + size_t i; >>>> + tree lhs = PHI_RESULT (phi); >>>> + value_range vr_result = VR_INITIALIZER; >>>> + bool first = true; >>>> + int edges; >>>> + >>>> + edges = 0; >>>> + for (i = 0; i < gimple_phi_num_args (phi); i++) >>>> + { >>>> + edge e = gimple_phi_arg_edge (phi, i); >>>> + tree arg = PHI_ARG_DEF (phi, i); >>>> + value_range vr_arg = VR_INITIALIZER; >>>> + ++edges; >>>> + >>>> + /* If there is a back-edge, set the result to VARYING. */ >>>> + if (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX)) >>>> + { >>>> + set_value_range_to_varying (&vr_result); >>>> + break; >>>> + } >>>> ... >>>> + /* If any of the RHS value is VARYING, set the result to VARYING. >>>> */ >>>> + if ((vr_arg.type != VR_RANGE) >>>> + && (vr_arg.type != VR_ANTI_RANGE)) >>>> + { >>>> + set_value_range_to_varying (&vr_result); >>>> + break; >>>> + } >>>> >>>> this shows that you need to start conservative for a DOM based VRP, >>>> thus with all lattice values initialized to VARYING (but undefined SSA >>>> names of course still can be UNDEFINED) rather than UNDEFINED. >>>> >>>> + if (TREE_CODE (arg) == SSA_NAME) >>>> + vr_arg = *(get_value_range (arg)); >>>> + else >>>> + set_value_range_to_varying (&vr_arg); >>>> >>>> err - what about constants? When you initialize the lattice properly >>>> you should be able to re-use vrp_visit_phi_node (maybe split out >>>> its head to avoid using SCEV or the iteration limitation). >>> >>> >>> >>> I also like re-using vrp_visit_phi_node but the issue is, we will have to >>> keep a work-list of nodes to be re-evaluated till the lattice reach a >>> fixpoint. Is that OK with you? >> >> >> No, why would you need to iterate here? As said, the key point is to >> initialize value-ranges as VARYING rather than UNDEFINED. >> >>> If we are to do this, we should be able to reuse the callbacks >>> vrp_visit_phi_node and vrp_visit_stmt as it is. >>> >>> Do you have a reference to your DOM based prototype? >> >> >> I never posted it I think, it's structure is similar to yours with lots >> of ??? comments ;) >> > > > Here is an updated patch which addresses the earlier review comments. > > Just to see the effectiveness of this, I did a simple test. > > That is, I built gcc with --enable-languages=c,c++ --disable-bootstrap > --disable-multilib and added -fdump-ipa-cp to the compiler flag and grepped > for number of times ipa-vrp (with the ipa-vrp patch) is setting the value > range for argument. I also did the same with tree-vrp used in place of > tree-evrp as an early vrp. tree-evrp is setting 186 times compared to > tree-vrp which is setting 207 times. I didn't see the actual value ranges > which can also make lots of difference. > > In future we might want to iterate on dom based vrp till fixed point is > reached if there is a need. why do you need these changes? I think I already told you you need to initialize the lattice to sth else than VR_UNDEFINED and that you can't fully re-use update_value_range. If you don't want to do that then instead of doing changes all over the place do it in get_value_range and have a global flag. @@ -3594,7 +3643,8 @@ extract_range_from_cond_expr (value_range *vr, gassign *stmt) on the range of its operand and the expression code. */ static void -extract_range_from_comparison (value_range *vr, enum tree_code code, +extract_range_from_comparison (value_range *vr, + enum tree_code code, tree type, tree op0, tree op1) { bool sop = false; remove these kind of no-op changes. +/* Initialize local data structures for VRP. If DOM_P is true, + we will be calling this from early_vrp where value range propagation + is done by visiting stmts in dominator tree. ssa_propagate engine + is not used in this case and that part of the ininitialization will + be skipped. */ static void -vrp_initialize (void) +vrp_initialize (bool dom_p) { basic_block bb; @@ -6949,6 +7010,9 @@ vrp_initialize (void) vr_phi_edge_counts = XCNEWVEC (int, num_ssa_names); bitmap_obstack_initialize (&vrp_equiv_obstack); + if (dom_p) + return; + split the function instead. @@ -7926,7 +7992,8 @@ vrp_visit_switch_stmt (gswitch *stmt, edge *taken_edge_p) If STMT produces a varying value, return SSA_PROP_VARYING. */ static enum ssa_prop_result -vrp_visit_stmt (gimple *stmt, edge *taken_edge_p, tree *output_p) +vrp_visit_stmt_worker (gimple *stmt, bool dom_p, edge *taken_edge_p, + tree *output_p) { tree def; ssa_op_iter iter; @@ -7940,7 +8007,7 @@ vrp_visit_stmt (gimple *stmt, edge *taken_edge_p, tree *output_p) if (!stmt_interesting_for_vrp (stmt)) gcc_assert (stmt_ends_bb_p (stmt)); else if (is_gimple_assign (stmt) || is_gimple_call (stmt)) - return vrp_visit_assignment_or_call (stmt, output_p); + return vrp_visit_assignment_or_call (stmt, dom_p, output_p); else if (gimple_code (stmt) == GIMPLE_COND) return vrp_visit_cond_stmt (as_a (stmt), taken_edge_p); else if (gimple_code (stmt) == GIMPLE_SWITCH) @@ -7954,6 +8021,12 @@ vrp_visit_stmt (gimple *stmt, edge *taken_edge_p, tree *output_p) return SSA_PROP_VARYING; } +static enum ssa_prop_result +vrp_visit_stmt (gimple *stmt, edge *taken_edge_p, tree *output_p) +{ + return vrp_visit_stmt_worker (stmt, false, taken_edge_p, output_p); +} as said the refactoring that would be appreciated is to split out the update_value_range calls from the worker functions so you can call the respective functions from the DOM implementations. That they are globbed in vrp_visit_stmt currently is due to the API of the SSA propagator. @@ -8768,6 +8842,12 @@ vrp_visit_phi_node (gphi *phi) fprintf (dump_file, "\n"); } + if (dom_p && vr_arg.type == VR_UNDEFINED) + { + set_value_range_to_varying (&vr_result); + break; + } + eh... ok, so another way to attack this is, instead of initializing the lattice to sth else than VR_UNDEFINED, make sure to drop the lattice to varying for all PHI args on yet unvisited incoming edges (you're not doing optimistic VRP). That's the only place you _have_ to do it. Richard. > Thanks, > Kugan > > diff --git a/gcc/common.opt b/gcc/common.opt index 8a292ed..7028cd4 100644 --- a/gcc/common.opt +++ b/gcc/common.opt @@ -2482,6 +2482,10 @@ ftree-vrp Common Report Var(flag_tree_vrp) Init(0) Optimization Perform Value Range Propagation on trees. +fdisable-tree-evrp +Common Report Var(flag_disable_early_vrp) Init(0) Optimization +Disable Early Value Range Propagation on trees. + no please, this is automatically supported via -fdisable- @@ -1728,11 +1736,12 @@ extract_range_from_assert (value_range *vr_p, tree expr) always false. */ static void -extract_range_from_ssa_name (value_range *vr, tree var) +extract_range_from_ssa_name (value_range *vr, bool dom_p, tree var) { value_range *var_vr = get_value_range (var); - if (var_vr->type != VR_VARYING) + if (var_vr->type != VR_VARYING + && (!dom_p || var_vr->type != VR_UNDEFINED)) copy_value_range (vr, var_vr); else set_value_range (vr, VR_RANGE, var, var, NULL);