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 [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id 3214D3858C74 for ; Thu, 11 Aug 2022 17:46:20 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 3214D3858C74 Received: from mail-qv1-f71.google.com (mail-qv1-f71.google.com [209.85.219.71]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-534-lpu6SAsfOJi_AAVzsnvj3w-1; Thu, 11 Aug 2022 13:46:18 -0400 X-MC-Unique: lpu6SAsfOJi_AAVzsnvj3w-1 Received: by mail-qv1-f71.google.com with SMTP id ln10-20020a0562145a8a00b004749ae27efcso9897387qvb.22 for ; Thu, 11 Aug 2022 10:46:18 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:in-reply-to:from:references:cc:to :content-language:subject:user-agent:mime-version:date:message-id :x-gm-message-state:from:to:cc; bh=SNYMkmf6kAb89AqcO4h4Cxlh9BHWMZ8R7z10izSAfU8=; b=sKVohxP81IDCkWKrtkC/0m/V/8pmfAan+YSYThwdYMXXGC+iLVQml1lVo22xM+f7GB lgoBBkXKsOLojjknCHKKyW1ICS1NWdZnxrVBnA7A+G2BaVaoaNnC4zmcOhSShAcW+bbH 3u++axSxYKOnYPytBJ0zN1G84Yl9NbivrHzABvi5u+ZwC9R/G6otmkMGMI9Zi2DDWYrs 107EEg/2qTBd+8J0gAmeGPETiMMWpQHPE4HiDsaeFNy69+Rb7bWR43zAIWouZt+HHwSs f1HFRtWT33SinTiFlqg+9xq+JOz2janW2da/L7f1lUeQlTT40iYQBFQWC726SXmtCBot +Pzg== X-Gm-Message-State: ACgBeo0gEha/YxHbdVpEuqQLWI9hUyCWrn822NbRIcHmL1mkr5ym1d6P gJwSffsfdA3K3D209mmjbhJDkNONAGHvPi65DdcX5IU4M/CTmYxZJhJXGYl/mvOQ7DGqw7w/CBt 4qiRz0bL6zUMUDWW8/Q== X-Received: by 2002:a05:620a:269a:b0:6b5:b769:2591 with SMTP id c26-20020a05620a269a00b006b5b7692591mr69319qkp.293.1660239978194; Thu, 11 Aug 2022 10:46:18 -0700 (PDT) X-Google-Smtp-Source: AA6agR6Nu9VKR6FZGgmxnKbe5/d+2heWDA3zs4e8Ok1TAXweuBPLvaj2d1nvuBLJ4L3RJCrJcywcuQ== X-Received: by 2002:a05:620a:269a:b0:6b5:b769:2591 with SMTP id c26-20020a05620a269a00b006b5b7692591mr69306qkp.293.1660239977955; Thu, 11 Aug 2022 10:46:17 -0700 (PDT) Received: from [192.168.0.135] ([192.24.49.145]) by smtp.gmail.com with ESMTPSA id z22-20020ac87cb6000000b00342fbe7f3a2sm21478qtv.70.2022.08.11.10.46.16 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 11 Aug 2022 10:46:17 -0700 (PDT) Message-ID: <3c003adc-32de-1858-6239-db3b968c5c5c@redhat.com> Date: Thu, 11 Aug 2022 13:46:18 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.11.0 Subject: Re: [PATCH] tree-optimization/106514 - revisit m_import compute in backward threading To: Richard Biener Cc: gcc-patches@gcc.gnu.org, aldyh@redhat.com References: <37255.122080909012202281@us-mta-359.us.mimecast.lan> <55ed3acb-ac0c-d7b7-0e9b-58591cf992a2@redhat.com> From: Andrew MacLeod In-Reply-To: X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-6.3 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_NONE, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) 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: Thu, 11 Aug 2022 17:46:21 -0000 On 8/10/22 06:46, Richard Biener wrote: > > I see the solver itself adds relations from edges on the path so > the cruical item here seems to be to add imports for the path > entry conditional, but those would likely be GORI imports for that > block? Unfortunately that fails to add t[012], the GORI exports > seem to cover all that's needed but then exports might be too much the GORI export list is the list of names which which GORi thinks might be different on the outgoing edges from a block. The GORI import list is the list of names which GORI thinks can affect those ranges from outside the block.  It doesnt try to look at individual PHI aguments, so IIRC it treats a PHI def as originating outside the block for import purposes.  This should be a subset of the export list. GORI info is only every concerned ONLY with the basic block... all external influences are considrered to be in the import list. And all GORI calculations utilize a range_of_expr query from a range_query to resolve the incoming value of an import in order to calculate an outgoing edge. outgoing_edge_range_p () has some additional smarts in it which allows for recomputations. You may have noticed the depend1/depend2 fields in the range_def_chain structure.  These are quick and dirty caches which represent the first 2 ssa-names encountered on the stmt when it was processed.  so for PHIs, the first 2 ssa names encountered, and for simple range-op qualifying stmts, the 1 or 2 ssanames in the def stmt for an ssa-name. If you ask for the range of a_32 on an outgoing edge, and it is not in the export list, GORI would not be able to provide a range. Outgoing_edge_range_p utilizes those 2 depend fields as a quick check to see if a recomputation may give us a better range.  if either depend1 or depend2 asociated with a_32 IS i the export list, then it performs a recompuation of a_32 instead of a GORI calculation.  ie  from the example in my previous note:   a_32 = f_16 + 10 <...> bb88:   if (f_16 < 20) bb89:      b_8 = a_32 + 8 depend1 for a_32 will be f_16. during rangers evaluation of b_8 in bb89, it will ask for the range of a_32 on the edge 88->89.  a_32 is not an export, but it sees that depend1 (f_16) is in the export list, so it does a recalculation of a_32 on the edge, coming up with f_16 being [0, 19] and returning a_32 as [10, 29]. This is why you may see outgoing_edge_range_p coming up with things that GORI itself doesnt actually provide... your example: void foo (int nest, int print_nest) {   _Bool t0 = nest != 0;   _Bool t1 = nest == print_nest;   _Bool t2 = t0 & t1;   if (t2)     __builtin_puts ("x");   nest++;   if (nest > 2)     __builtin_abort ();   if (print_nest == nest)     __builtin_puts ("y"); } if (nest > 2) , : nest is the only import and export in that block, but outgoing_edge_range_p would be able to recompute t1 and t0 on those edges as nest is used in defining them. Likewise, print_nest is used in defining t1, so it can also be recomputed. on the final edges.     This could be why adding some dependencies from outside the block sometimes gets a better result. the recomputation information is not rolled into the GORI exports, as it is more dynamic.  we don't know which order this will be seen in, so we dont know what ssa_names in advance use 'nest' in their calculations.   we could add them as they are seen, but then the bitmaps could explode in size.. so leaving it in this dynamic quick check seemed more practical. There is no mapping from a name to the other ssanames that depend on it in either..  ie, given 'nest', there is no mechaism to see that t0 and t1 use it.   I had considered building this list as well, but at the moment didnt have a lot of use for it and thought a use map might get large quickly. I wonder if what might help is to loop thru all the interesting names that have been calculated, and adding  the GORI export names from the original block which occur in either a depend1 or depend2 field of those names..   That would be more concise than the entire gori export list. if it is just the entry path exports that are relevant, then perhaps as names are added to the interesting list we could check if either of its 'depend's fields is in the entry blocks export list, and add it then. > here? At least that's what the code in compute_imports effectively > does (also for the entry block). But I do wonder why compute_ranges > does not add relations computed by the entry conditional ... > That's probably because of > > void > path_range_query::compute_outgoing_relations (basic_block bb, basic_block > next) > { > gimple *stmt = last_stmt (bb); > > if (stmt > && gimple_code (stmt) == GIMPLE_COND > && (import_p (gimple_cond_lhs (stmt)) > || import_p (gimple_cond_rhs (stmt)))) > > where for a condition like above the names in the imports are not > in the condition itself. The gori.outgoing_edge_range_p compute > of the import ranges is appearantly not affected by this > restriction and picks up nest as ~[0, 0] on the respective path > even though, while 'nest' is in imports, the temporaries are not. > That would support the argument to drop the import_p checks in > path_range_query::compute_outgoing_relations. > > I'm not sure it's worth fixing incrementally though, it's fallout > of r12-5157-gbfa04d0ec958eb that in some way did the reverse of > my patch. Interestingly hybrid_jt_simplifier::compute_ranges_from_state > still computes imports itself before calling compute_ranges. > > For comparing thread numbers fixing the current state incrementally > would be nice I guess, I will test something but not further pursue it > if not successful. > > Richard.