From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 80958 invoked by alias); 28 Jul 2016 11:34:33 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 80848 invoked by uid 89); 28 Jul 2016 11:34:33 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.3 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,RCVD_IN_DNSWL_LOW,SPF_PASS autolearn=ham version=3.3.2 spammy=visit, yours X-HELO: mail-wm0-f48.google.com Received: from mail-wm0-f48.google.com (HELO mail-wm0-f48.google.com) (74.125.82.48) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-GCM-SHA256 encrypted) ESMTPS; Thu, 28 Jul 2016 11:34:22 +0000 Received: by mail-wm0-f48.google.com with SMTP id p129so36217061wmp.0 for ; Thu, 28 Jul 2016 04:34:22 -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=byo96xbawT7RqwLR8VTiRk35ZK2WbGCAlmKBd/CjQfU=; b=b8PRhw8GOT707M7drSyerRpdABuYcOBXkN7kAGB1kBHvN2gsmOUvHJk04aRB+yfVh6 AtUDJlJ+1iWZE7rij1wAhF818Lri5aiSKulghK02QpoeCgLTITR5q7NVFK4jDpx6rSIA 3UgUJY1z4hblQd7E+QWuIK+KU8BGmkM1AZREvAFKO99TUxlJfac4fzsVt2LO683eg7Mv kqsjU3Uv7jLMmvQyHo2a0gtgNgahBuETSYCgWyJYmAUC8krCY+HgAtFnguP5zJdORNf7 jpB2N6xxyn4Nst69rUmOke85Jf9Fcv1SOKoaANU15bVOe6/hXiZHhZP19Bb9UrHb51oK QuZQ== X-Gm-Message-State: AEkoousNpY+F+pvjF3Fg9yQUqtMhVKjlWG4/alAmcdQHd7sW/vfimnrbrKybjiWRXSJYOCD8Yxys9mrt2K1Cng== X-Received: by 10.194.58.112 with SMTP id p16mr33545476wjq.24.1469705659675; Thu, 28 Jul 2016 04:34:19 -0700 (PDT) MIME-Version: 1.0 Received: by 10.28.137.202 with HTTP; Thu, 28 Jul 2016 04:34:18 -0700 (PDT) In-Reply-To: References: <57886949.8010300@linaro.org> <57886A71.6030103@linaro.org> <57888BD6.6070200@linaro.org> <578891C8.7090609@linaro.org> <19ff8188-aed7-0f9e-cc0b-0603698787ff@linaro.org> From: Richard Biener Date: Thu, 28 Jul 2016 11:34:00 -0000 Message-ID: Subject: Re: [RFC][IPA-VRP] Early VRP Implementation To: kugan Cc: Andrew Pinski , "gcc-patches@gcc.gnu.org" , Jan Hubicka , Martin Jambor Content-Type: text/plain; charset=UTF-8 X-IsSubscribed: yes X-SW-Source: 2016-07/txt/msg01853.txt.bz2 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 ;) Richard. > Thanks, > Kugan > > >> Btw, you don't want to call vrp_initialize in evrp either, this is setting >> SSA propagator state which you do not want to do. Please factor >> out lattice allocation/deallocation instead. I see that might require >> really factoring vrp_visit_stmt into a function that omits updating >> the lattice and just returns a range for the single DEF. >> >> That said, a good refactoring is to split the SSA propagator callback >> implementations (vrp_visit_stmt and vrp_visit_phi_node) into workers >> returning a value range and the callback that does the update_value_range >> call plus returing a SSA propgator state. You can then re-use the worker. >> >> Thanks, >> Richard. >> >>> I have tested the last set of patch separately. >>> >>> I will do more testing on this patch based on your feedback. Does this >>> look >>> better? >>> >>> Thanks, >>> Kugan >>> >>> >