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 DD7CF3858C60 for ; Wed, 29 Sep 2021 15:20:25 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org DD7CF3858C60 Received: from mail-qt1-f200.google.com (mail-qt1-f200.google.com [209.85.160.200]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-551-0QF_5ZMQPVGh3CNUR8cLSQ-1; Wed, 29 Sep 2021 11:20:24 -0400 X-MC-Unique: 0QF_5ZMQPVGh3CNUR8cLSQ-1 Received: by mail-qt1-f200.google.com with SMTP id a18-20020aed2792000000b002a6d480aa95so8830317qtd.14 for ; Wed, 29 Sep 2021 08:20:24 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:subject:to:cc:references:from:message-id:date :user-agent:mime-version:in-reply-to:content-transfer-encoding :content-language; bh=YkqujtxsFb0SsaO0n4NWrNuFGg9aabL4cepVoHnRv/4=; b=auOizRdDDUch8wRRH859nqBpMeUBHYDQjN5OjZMkR+OkwZX3+zthl1QD/9e+1ASFRT 67cxIN9IYGUXCtFuHVHzB9JuVJIYQb1qjoCVhuvy4/MG5K0XPbM+fRhh/K8goQ5SXljf RZ0Ux/9CjWDgCvnox6toXBt+zY5PKdnHQkTezYf//riuQ7i+yvXQ3ITqJx/78uSEpg8P qG8uPqz6f5FlNjEX01hYNFe2Duxxxk50NmQl6N51LvyXYJbYDgbfQL2NuUj7XZMRS8L8 JMxwFcfis+JAIi24TZ7TBmhvrqm5XcpAUDy5n/EePzo+b5yWDcdifuzZccgJql+WJkKh AY1w== X-Gm-Message-State: AOAM5307xNodb2pUgXdGrB/EyG2aKsbgvUZlmSZLk57nq93KyZwsc9CS +na44eVt66GFgoUIdfkZtPvp4O11tHvKAY+tXbEJEIfYohWHhaAEkRTxAJoOFQ6dLbNvaJ6rbrg w6O9v+ESRKcraZypm4hdumkLXbEkrFVBdbTwGsaDtExnPx84Uau9tod00Gp+EGKfNGQVvAA== X-Received: by 2002:a37:e17:: with SMTP id 23mr285785qko.301.1632928823176; Wed, 29 Sep 2021 08:20:23 -0700 (PDT) X-Google-Smtp-Source: ABdhPJz+zA1BtqXBPbuDFprBLmTrXpcaJ/OKhIM7CQfhgxwZ+NfQHC0RsXv33uRTENOc0ADt7VDEgg== X-Received: by 2002:a37:e17:: with SMTP id 23mr285759qko.301.1632928822792; Wed, 29 Sep 2021 08:20:22 -0700 (PDT) Received: from [192.168.0.102] ([104.219.123.55]) by smtp.gmail.com with ESMTPSA id bk20sm117529qkb.13.2021.09.29.08.20.20 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 29 Sep 2021 08:20:21 -0700 (PDT) Subject: Re: [PATCH] Loop unswitching: support gswitch statements. To: Richard Biener Cc: =?UTF-8?Q?Martin_Li=c5=a1ka?= , GCC Patches References: <7791e850-f74d-8c1c-f67c-e02f3f6e007d@redhat.com> From: Andrew MacLeod Message-ID: Date: Wed, 29 Sep 2021 11:20:19 -0400 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.13.0 MIME-Version: 1.0 In-Reply-To: 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-CA X-Spam-Status: No, score=-7.4 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, NICE_REPLY_A, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) 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, 29 Sep 2021 15:20:27 -0000 On 9/29/21 4:43 AM, Richard Biener wrote: > On Tue, Sep 28, 2021 at 10:39 PM Andrew MacLeod wrote: >> On 9/28/21 7:50 AM, Richard Biener wrote: >>> On Wed, Sep 15, 2021 at 10:46 AM Martin Liška wrote: >>>> /* Unswitch single LOOP. NUM is number of unswitchings done; we do not allow >>>> @@ -269,6 +311,7 @@ tree_unswitch_single_loop (class loop *loop, int num) >>>> class loop *nloop; >>>> unsigned i, found; >>>> tree cond = NULL_TREE; >>>> + edge cond_edge = NULL; >>>> gimple *stmt; >>>> bool changed = false; >>>> HOST_WIDE_INT iterations; >>>> @@ -311,11 +354,12 @@ tree_unswitch_single_loop (class loop *loop, int num) >>>> bbs = get_loop_body (loop); >>>> found = loop->num_nodes; >>>> >>>> + gimple_ranger ranger; >>> ISTR constructing/destructing ranger has a non-negligible overhead - >>> is it possible >>> to keep it live for a longer time (note we're heavily modifying the CFG)? >> >> There is some overhead.. right now we determine all the imports and >> exports for each block ahead of time, but thats about it. We can make >> adjustments for true on demand clients like this so that even that >> doesnt happen. we only do that so we know ahead of time which ssa-names >> are never used in outgoing edges, and never even have to check those. >> Thats mostly an optimization for heavy users like EVRP. If you want, I >> can make that an option so there virtually no overhead >> >> More importantly, the longer it remains alive, the more "reuse" of >> ranges you will get.. If there is not a pattern of using variables >> from earlier in the program it wouldnt really matter much. >> >> In Theory, modifying the IL should be fine, it happens already in >> places, but its not extensively tested under those conditions yet. > Note it's modifying the CFG as well. bah, thats what I meant.   as long as the IL is changed and CFG updated to match, it should in theory work.  And as long as existing SSA_NAMEs dont have their meaning changes..  ie reusing an SSA_NAME to have a  different definition is likely to cause problems without telling ranger that an SSA_NAME is now different. > > My issue is that the current place is one construction per loop > (and even when we do _not_ end up doing anything), so if the > ranger use isn't O(loop-size) (not to mention nest depth...) then > we'll quickly run into complexity issues for functions with a lot of > loops. It should, again in theory, be possible to simple call enable_ranger(cfun) at the beginning of the pass,  and then just use "get_range_query(cfun)"  throughout.. and call disable_ranger at the end.  or if you want to keep using the gimple_ranger pointer: gimple_ranger *ranger = enable_ranger (cfun); disable_ranger(cfun) I *think* it will work thru the CFG changes.. but one would have to try it and see if the same results happen.  If they don't loop me in because it might be something simple.   we may need to force a request for a range of the stmts which are changed under some circumstances.  Nothing occurs to me off the top of my head that would be needed. > >> >> Yes and no :-) I use to do that, but now that we allow uninitialized >> values to be treated as UNDEFINED, it may also mean that its >> uninitialized on that edge. >> >> Evaluating >> if (c_3 == 0) when we know c_3 = [1,1] >> >> What you suggest is fundamentally what ranger does... It evaluates what >> the full set of possible ranges are on the edge you ask about, then >> intersects it with the known range of c_3. . If the condition cannot >> ever be true,and is thus unexecutable, the result will be UNDEFINED . >> ie above, c_3 would have to have a range of [0,0] on the true edge, and >> its real range is [1,1].. intersecting the 2 values results in UNDEFINED... >> >> So it can mean the edge is unexecutable. It can also mean the value is >> actually undefined.. if this was a use-before-def case, the range of c_3 >> in the block would be UNDEFINED. and c_3 will be UNDEFINED on BOTH >> edges due ot the intersection. the UNDEFINED state is viral. >> >> I guess you can argue you can arbitrarily choose an edge to process in >> this case, but if you want to avoid that situation completely, I think >> you could also check that cond is not UNDEFINED in the stmt first.. >> then if you get UNDEFINED on and edge you are 100% sure its >> unexectuable.. ie >> >> + >> + if (ranger.range_of_expr (r, cond, stmt) && !r.undefined_p ()) >> + { >> + if (ranger.range_on_edge (r, edge_true, cond) && r.undefined_p ()) >> >> Note the call to range_of_expr () will do the supported_type check >> anyway and return false if it isnt supported. > So my question was probably more like if there's a way to evaluate > a condition with ranger to either true, false or unknown that looks less "odd"? well, you can directly try to fold the conditional stmt and see what the result is.   You can simply pass a range_query in which is used to resolve the operands on the stmt.   So where 'stmt' is :    if (c_3 == 0)   if (fold_range (r, stmt, ranger) && r.singleton_p ()) will return [0,1] if we don't know which edge is taken, or [0,0] if the false edge is known to be taken, or [1,1] if the true edge is known to be taken... Or, if we switch to the enable_ranger() mechanism for the entire pass:   if (fold_range (r, stmt, get_range_query (cfun)) && r.singleton_p ()) btw this is virtually the same as   if (get_range_query (cfun)->range_of_stmt (r, stmt) && r.singleton_p ()) > > In principle it would be asking for the range of the c_3 == 0 expression > which is embedded in the GIMPLE_COND. I really don't like the other > proposed options as they look like error-prone (wrt wrong-code). > yes, so its exactly like that Andrew