From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [216.205.24.124]) by sourceware.org (Postfix) with ESMTP id 950A03943421 for ; Wed, 14 Oct 2020 18:09:17 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 950A03943421 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-267-a026nMc1M--CbotBpqgFLg-1; Wed, 14 Oct 2020 14:09:15 -0400 X-MC-Unique: a026nMc1M--CbotBpqgFLg-1 Received: from smtp.corp.redhat.com (int-mx01.intmail.prod.int.phx2.redhat.com [10.5.11.11]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id F41111882FB0; Wed, 14 Oct 2020 18:09:13 +0000 (UTC) Received: from [10.10.118.239] (ovpn-118-239.rdu2.redhat.com [10.10.118.239]) by smtp.corp.redhat.com (Postfix) with ESMTP id DA8CB76669; Wed, 14 Oct 2020 18:09:11 +0000 (UTC) Subject: Re: [PATCH] Add if-chain to switch conversion pass. To: =?UTF-8?Q?Martin_Li=c5=a1ka?= , Jakub Jelinek Cc: GCC Patches , Jan Hubicka , Aldy Hernandez References: <6169f91a-4884-55f5-c76f-ea1dae11d996@suse.cz> <35eb0279-77d8-36f8-3ab7-afb9ae97fdb3@suse.cz> <42c91f11-c1a6-3ae4-08da-0a0b77f63b80@suse.cz> <72541e13d26f92577637b8f0e23d82435f35ddea.camel@redhat.com> <46e9e574-80f8-3cce-3fcf-dbc8205e74ae@suse.cz> <20201006141212.GE2176@tucnak> <8e40f1ca-8d9f-3171-fb2a-c876c5a90064@suse.cz> From: Andrew MacLeod Message-ID: <19667c2e-c78f-2917-a699-2e85007da775@redhat.com> Date: Wed, 14 Oct 2020 14:09:10 -0400 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.4.0 MIME-Version: 1.0 In-Reply-To: <8e40f1ca-8d9f-3171-fb2a-c876c5a90064@suse.cz> X-Scanned-By: MIMEDefang 2.79 on 10.5.11.11 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Content-Language: en-US X-Spam-Status: No, score=-4.9 required=5.0 tests=BAYES_00, BODY_8BITS, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, NICE_REPLY_A, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H4, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) 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-List-Received-Date: Wed, 14 Oct 2020 18:09:19 -0000 On 10/12/20 8:39 AM, Martin Liška wrote: > On 10/6/20 4:12 PM, Jakub Jelinek wrote: >> On Tue, Oct 06, 2020 at 03:48:38PM +0200, Martin Liška wrote: >>> On 10/6/20 9:47 AM, Richard Biener wrote: >>>> But is it really extensible with the current implementation?  I >>>> doubt so. >>> >>> I must agree with the statement. So let's make the pass properly. >>> I would need a help with the algorithm where I'm planning to do the >>> following >>> steps: >>> >>> 1) for each BB ending with a gcond, parse index variable and it's VR; >>>     I'll support: >>>     a) index == 123 ([123, 123]) >>>     b) 1 <= index && index <= 9 ([1, 9]) >>>     c) index == 123 || index == 12345 ([123, 123] [12345, 12345]) >>>     d) index != 1 ([1, 1]) >>>     e) index != 1 && index != 5 ([1, 1] [5, 5]) >> >> The fold_range_test created cases are essential to support, so >> f) index - 123U < 456U ([123, 456+123]) >> g) (unsigned) index - 123U < 456U (ditto) >> but the discovery should actually recurse on all of those forms, so >> it will >> handle >> (unsigned) index - 123U < 456U || (unsigned) index - 16384U <= 32711U >> etc. >> You can see what reassoc init_range_entry does and do something similar? > > All right, I started to use init_range_entry in combination with > linearize_expr_tree. > One thing I have problem with is that linearize_expr_tree doesn't > properly mark > all statements as visited for cases like: > >   : >   index2.1_1 = (unsigned int) index2_16(D); >   _2 = index2.1_1 + 4294967196; >   _3 = _2 <= 100; >   _5 = index2.1_1 + 4294966996; >   _6 = _5 <= 33; >   _7 = _3 | _6; >   if (_7 != 0) >     goto ; [INV] >   else >     goto ; [INV] > > As seen, all statements in this BB are used by the final _7 != 0 and > it would > be handy for me to identify all statements that should be hoisted. The ranger infrastructure includes definition chains for what can potentially have a range calculated on an outgoing edge.  It contains all the ssa-names defined in the block for which we have range-ops entries that allow us to potentially wind back thru a calculation.   ie, any name which is defined in the block whose value can be changed based on which edge is taken... I created: foo (int index) {  if (index - 123U < 456U || index - 16384U <= 32711U )     foo (42); } the exports range list contains  =========== BB 2 ============ index_9(D)      int VARYING     :     index.0_1 = (unsigned int) index_9(D);     _2 = index.0_1 + 4294967173;     _3 = _2 <= 455;     _5 = index.0_1 + 4294950912;     _6 = _5 <= 32711;     _7 = _3 | _6;     if (_7 != 0)       goto ; [INV]     else       goto ; [INV] 2->3  (T) index.0_1 :   unsigned int [123, 578][16384, 49095] 2->3  (T) _7 :  _Bool [1, 1] 2->3  (T) index_9(D) :  int [123, 578][16384, 49095] 2->4  (F) index.0_1 :   unsigned int [0, 122][579, 16383][49096, +INF] 2->4  (F) _2 :  unsigned int [456, +INF] 2->4  (F) _3 :  _Bool [0, 0] 2->4  (F) _5 :  unsigned int [32712, +INF] 2->4  (F) _6 :  _Bool [0, 0] 2->4  (F) _7 :  _Bool [0, 0] 2->4  (F) index_9(D) :  int [-INF, 122][579, 16383][49096, +INF] and importantly, the defchain structure which lists names which are used to define this name  looks like: DUMPING GORI MAP bb2    index.0_1 : index_9(D)        _2 : index.0_1  index_9(D)        _3 : index.0_1  _2  index_9(D)        _5 : index.0_1  index_9(D)        _6 : index.0_1  _5  index_9(D)        _7 : index.0_1  _2  _3  _5  _6  index_9(D)        exports: index.0_1  _2  _3  _5  _6  _7  index_9(D) This indicates that if you are using _7 as the control name of the branch, _7 : index.0_1  _2  _3  _5  _6  index_9(D) is the list of names that _7 uses in its definition chain...and we can calculate ranges for.      index_9 is not defined in this BB, so it is considered an import.  you'd probably be looking for all the names in this list whose SSA_NAME_DEF_STMT is in this block.. That looks a lot like the list of statements you want to hoist. Caveats are that   1)  this is currently only used internally by the ranger, so there are some  minor warts that may currently limit its usefulness elsewhere   2) its is limited to only processing statements for which we have range-ops understanding.    which means we know how to calculate ranges for the statement.  Perhaps this is also not an issue since if there are statements we cant generate a range for, perhaps you dont care. This might be more ionfo than  you need, but also   3) before the enxt stage 1 I plan to rework the GORI component, and I plan to split this into additional "parts"  in particualr, this entire export list will still exist, but there will be 3 subcomponents which form it:        a)  control names :   These are booleans which contribute to the TRUE/FALSEness of the edge        b) direct exports  : These are ssanames which are directly affected by relations on the edge.. Ie, the edge gives them a range        c) calculable exports  : These are other ssa_names which can be calculated based on the direct exports. Ie, the direct export is used in calculating this value for the above block,   control names :  _7, _6 and _3   direct exports : _5 and _2   calculable exports : index.0_1 index_9(D) I bring it up because as IM reworking those bits, we can take into account other requirements that might be needed that can make it useful other places. And by anaylzing the names that are common between any direct exports, you may find useful information. Currently, the exports list is not exported from the ranger, nor is the gori map,  but that would be trivial to do.   You basically get a bitmap back.. The classes are not dependant on the ranger either, so you can roll your own if you wanted to experiment.  Since they are internal  they are currently located in  gimple-range-gori.cc.. its basically the gori_map class which tracks all this and uses the range_def_chain class to manage the definition chains.  I threw a number fo comments in there already.   Its lazily evaluated as queries are made. If you think there is something useful, we can move those classes into the gimple-range-gori.h header file and adjust the APIs as needed. > > Thoughts how can I achieve that? > Thanks, > Martin >