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 0C5C63858D39 for ; Wed, 2 Mar 2022 13:58:34 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 0C5C63858D39 Received: from mail-qk1-f200.google.com (mail-qk1-f200.google.com [209.85.222.200]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-362-B8c7CGbrNOifhjbZiua-Tw-1; Wed, 02 Mar 2022 08:58:30 -0500 X-MC-Unique: B8c7CGbrNOifhjbZiua-Tw-1 Received: by mail-qk1-f200.google.com with SMTP id f17-20020a05620a069100b0060dfbbb52cfso1150879qkh.1 for ; Wed, 02 Mar 2022 05:58:30 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:date:mime-version:user-agent:subject :content-language:to:references:from:in-reply-to :content-transfer-encoding; bh=EPRWfj/s6sA0Y6xr8Ra8FezPHNoXvhBa2azFOA/1nT8=; b=dUgKQ6Iq3roIR6TOReY14+6qikcQpUH9EfeVZ4xQMuMt3On2w669JfAz3WE8tnIJ6n 0FYOXcm1ciamqB7OMBh3/uQ8xxrbRTJjKDqD7cisAcfr8lBwUxPZ15z5dKo7gJU1Nay4 XLWgzLJIFgcFrOOKD3mZCzwsi+e/pdPMOtZm1UDlC+LBwV1KYDuKO8QFP0R9H02W19MY 3ANUhL9FYDZqmqwPFSIpdskukN2KdIENY4tUFyAWQE0R84e6T7N55QBZ9Iv3Fb46Cp7R dQsORHkWNg0j2CY6oppvreL72mDCUXghwlI4G7o4IPOkL/Br4mh75GR36xoHamzs+cCj ccMg== X-Gm-Message-State: AOAM533Mixysj49mxXBeLefbdKxlf7bWz+jECGr8lg2lDN4X6KATDsUA kH5r2gfYyMZ62sxqCKz7pbOw3LhHBub1V6NIWzC8kIKO0nCYeIx66x9ttTlycI2Q16znQAdgWIO cnGWoeKy/JZdkQcywNA== X-Received: by 2002:a05:6214:e43:b0:432:58fa:4cbb with SMTP id o3-20020a0562140e4300b0043258fa4cbbmr20583420qvc.94.1646229509451; Wed, 02 Mar 2022 05:58:29 -0800 (PST) X-Google-Smtp-Source: ABdhPJwssqGN0d7CMfxoYV/tfvqmjSX4sU360glleh5Kgu33zTVS68lAQtO1RDF8y0z7HktFjUXEDQ== X-Received: by 2002:a05:6214:e43:b0:432:58fa:4cbb with SMTP id o3-20020a0562140e4300b0043258fa4cbbmr20583416qvc.94.1646229509178; Wed, 02 Mar 2022 05:58:29 -0800 (PST) Received: from [192.168.1.113] ([69.165.238.126]) by smtp.gmail.com with ESMTPSA id b127-20020a376785000000b00648ee0245dasm8276852qkc.69.2022.03.02.05.58.28 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 02 Mar 2022 05:58:28 -0800 (PST) Message-ID: <10e68be1-314a-4078-243b-09ccbf08176b@redhat.com> Date: Wed, 2 Mar 2022 08:58:27 -0500 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.5.0 Subject: Re: [PATCH] rtl-optimization/104686 - speedup IRA allocno conflict test To: Richard Biener , gcc-patches@gcc.gnu.org References: <20220302085845.423FC13345@imap2.suse-dmz.suse.de> From: Vladimir Makarov In-Reply-To: <20220302085845.423FC13345@imap2.suse-dmz.suse.de> 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: 7bit X-Spam-Status: No, score=-6.2 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_H5, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE 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, 02 Mar 2022 13:58:36 -0000 On 2022-03-02 03:58, Richard Biener wrote: > In this PR allocnos_conflict_p takes 90% of the compile-time via > the calls from update_conflict_hard_regno_costs. This is due to > the high number of conflicts recorded in the dense bitvector > representation. Fortunately we can take advantage of the bitvector > representation here and turn the O(n) conflict test into an O(1) one, > greatly speeding up the compile of the testcase from 39s to just 4s > (93% IRA time to 26% IRA time). > > While for the testcase in question the first allocno is almost always > the nice one the patch tries a more systematic approach to finding > the allocno to iterate object conflicts over. That does reduce > the actual number of compares for the testcase but it doesn't make > a measurable difference wall-clock wise. That's not guaranteed > though I think so I've kept this systematic way of choosing the > cheapest allocno. > > Bootstrapped and tested on x86_64-unknown-linux-gnu. > > OK for trunk? > Yes. Richard, thank you again for working on this issue. > 2022-03-02 Richard Biener > > PR rtl-optimization/104686 > * ira-color.cc (object_conflicts_with_allocno_p): New function > using a bitvector test instead of iterating when possible. > (allocnos_conflict_p): Choose the best allocno to iterate over > object conflicts. > (update_conflict_hard_regno_costs): Do allocnos_conflict_p test > last. > other_allocno),