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 1ED38385702C for ; Thu, 4 Aug 2022 18:29:24 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 1ED38385702C Received: from mail-qv1-f69.google.com (mail-qv1-f69.google.com [209.85.219.69]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-108-qWRYjkxUP8-1BTbQtOrZDA-1; Thu, 04 Aug 2022 14:29:22 -0400 X-MC-Unique: qWRYjkxUP8-1BTbQtOrZDA-1 Received: by mail-qv1-f69.google.com with SMTP id ln10-20020a0562145a8a00b004749ae27efcso126424qvb.22 for ; Thu, 04 Aug 2022 11:29:22 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=subject:from:cc:to:content-language:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc; bh=OSvsSuPzScq3QfXO6lVQ4P6dQin1Fba0nY1p85EWDi8=; b=EBrerxt72PZiq9r/0KhWJzoRIYMQ75rjK/KspNnUN6P1Xj4sIrxyHqhN5r/hkP5hDl rHDIeWVYci8m6q5RAQBAosv+sbZSw0osODHJo23W7CKXSNX7htEOiRxQeksH6ivaliNL RYCEWI3mZiJeNTZ2VpSabLTzkimxw5f9B3E0+Dj8XMWbA68Eq97HB4BYw9fWhp0HHkCi 9f/9urpuitrBfPkcua5epURZSpop5UJ2jQMXCFbS3c2syzrFIB4nDk5MHSfiM89rHTCk cORG484mjfdnqF5TccMue8nDrPFQ9WOouD/oQwhYdKlFiBtdo93b6dTQCSVI3rupFDrK +0ng== X-Gm-Message-State: ACgBeo1DodsSyu7zCakIi58+/1stBWTSVY9Dwf7wZPKY9EG7qreT3AXv EgEHM8zfG3+McP/vh74iytvcocO3gJMNruhIa6WWe5p1IJHTDaLX4si9Wek8zhDx8d9xZfwZ3lq pLqvHjaXlVwL9O09zq0vID5fg0+UIxZJHv75qMFi8SKxpQGEQTKgj2eRZiSpbaDDQt7acVw== X-Received: by 2002:ac8:7f4b:0:b0:31e:f97c:52a7 with SMTP id g11-20020ac87f4b000000b0031ef97c52a7mr2702783qtk.14.1659637761676; Thu, 04 Aug 2022 11:29:21 -0700 (PDT) X-Google-Smtp-Source: AA6agR4Z4A9ooGZLOM4cfSQe9M+a9t86TIL24SdSRh2tZDmSUQzD48FiPBsquExxyT2tb+GlW64Yag== X-Received: by 2002:ac8:7f4b:0:b0:31e:f97c:52a7 with SMTP id g11-20020ac87f4b000000b0031ef97c52a7mr2702769qtk.14.1659637761347; Thu, 04 Aug 2022 11:29:21 -0700 (PDT) Received: from [192.168.0.135] ([104.219.120.152]) by smtp.gmail.com with ESMTPSA id j2-20020ac806c2000000b00304fe5247bfsm1026726qth.36.2022.08.04.11.29.20 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 04 Aug 2022 11:29:20 -0700 (PDT) Message-ID: <74369404-3c07-583a-eb2b-0c1f7989577b@redhat.com> Date: Thu, 4 Aug 2022 14:29:18 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.11.0 To: gcc-patches From: Andrew MacLeod Subject: [COMMITTED] PR tree-optimization/106514 - Loop over intersected bitmaps. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: multipart/mixed; boundary="------------ljzPyYrI00KOhK60xmjREAVj" Content-Language: en-US X-Spam-Status: No, score=-11.1 required=5.0 tests=BAYES_00, BODY_8BITS, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_NONE, TXREP 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, 04 Aug 2022 18:29:26 -0000 This is a multi-part message in MIME format. --------------ljzPyYrI00KOhK60xmjREAVj Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit compute_ranges_in_block loops over all the imports, and checks to see if each one is exported, then calculated an outgoing range for those that are. The outer loop loops over the import list, whereas the export list is usually smaller, and empty half the time.  This means we were doing a lot of busy work looping over the imports for no reason. The export list was extracted on each iteration of the loop, and because its a self sizing thing with a call, It doesn't get hauled out of the loop.  More extra work. This patch changes the loop to use EXECUTE_IF_AND_IN_BITMAP to only look at the intersection of imports and exports, ths only doing the work it needs to do. With a performance build, running with --param max-jump-thread-duplication-stmts=50 for good measure: before patch: backwards jump threading           :   5.91 ( 90%)   0.01 ( 20%)   5.93 ( 89%)    72  (  0%) TOTAL                           :   6.58          0.05 6.66           47M after patch: backwards jump threading           :   4.67 ( 88%)   0.01 ( 14%)   4.67 ( 86%)    72  (  0%) TOTAL                           :   5.31          0.07 5.42           47M bootstrapped on 86_64-pc-linux-gnu  with no regressions, and no change in the thread count.  pushed. Andrew --------------ljzPyYrI00KOhK60xmjREAVj Content-Type: text/x-patch; charset=UTF-8; name="forand.diff" Content-Disposition: attachment; filename="forand.diff" Content-Transfer-Encoding: base64 Y29tbWl0IDhlMzRkOTJlZjI5YTE3NWI4NGNjN2Y1MTg1ZGI0MzY1NmFlNzYyYmIKQXV0aG9yOiBB bmRyZXcgTWFjTGVvZCA8YW1hY2xlb2RAcmVkaGF0LmNvbT4KRGF0ZTogICBUaHUgQXVnIDQgMTI6 MjI6NTkgMjAyMiAtMDQwMAoKICAgIExvb3Agb3ZlciBpbnRlcnNlY3RlZCBiaXRtYXBzLgogICAg CiAgICBjb21wdXRlX3Jhbmdlc19pbl9ibG9jayBsb29wcyBvdmVyIHRoZSBpbXBvcnQgbGlzdCBh bmQgdGhlbiBjaGVja3MgdGhlCiAgICBzYW1lIGJpdCBpbiBleHBvcnRzLiAgSXQgaXMgbm1vcmUg ZWZmaWNlbnQgdG8gbG9vcCBvdmVyIHRoZSBpbnRlcnNlY3Rpb24KICAgIG9mIHRoZSAyIGJpdG1h cHMuCiAgICAKICAgICAgICAgICAgUFIgdHJlZS1vcHRpbWl6YXRpb24vMTA2NTE0CiAgICAgICAg ICAgICogZ2ltcGxlLXJhbmdlLXBhdGguY2MgKHBhdGhfcmFuZ2VfcXVlcnk6OmNvbXB1dGVfcmFu Z2VzX2luX2Jsb2NrKToKICAgICAgICAgICAgVXNlIEVYRUNVVEVfSUZfQU5EX0lOX0JJVE1BUCB0 byBsb29wIG92ZXIgMiBiaXRtYXBzLgoKZGlmZiAtLWdpdCBhL2djYy9naW1wbGUtcmFuZ2UtcGF0 aC5jYyBiL2djYy9naW1wbGUtcmFuZ2UtcGF0aC5jYwppbmRleCBlMWI5NjgzYzFlNC4uNDNlNzUy NmI2ZmMgMTAwNjQ0Ci0tLSBhL2djYy9naW1wbGUtcmFuZ2UtcGF0aC5jYworKysgYi9nY2MvZ2lt cGxlLXJhbmdlLXBhdGguY2MKQEAgLTQ3OSwzMiArNDc5LDI4IEBAIHBhdGhfcmFuZ2VfcXVlcnk6 OmNvbXB1dGVfcmFuZ2VzX2luX2Jsb2NrIChiYXNpY19ibG9jayBiYikKICAgICAgIHAtPnNldF9y b290X29yYWNsZSAobnVsbHB0cik7CiAgICAgfQogCi0gIEVYRUNVVEVfSUZfU0VUX0lOX0JJVE1B UCAobV9pbXBvcnRzLCAwLCBpLCBiaSkKKyAgZ29yaV9jb21wdXRlICZnID0gbV9yYW5nZXItPmdv cmkgKCk7CisgIGJpdG1hcCBleHBvcnRzID0gZy5leHBvcnRzIChiYik7CisgIEVYRUNVVEVfSUZf QU5EX0lOX0JJVE1BUCAobV9pbXBvcnRzLCBleHBvcnRzLCAwLCBpLCBiaSkKICAgICB7CiAgICAg ICB0cmVlIG5hbWUgPSBzc2FfbmFtZSAoaSk7Ci0gICAgICBnb3JpX2NvbXB1dGUgJmcgPSBtX3Jh bmdlci0+Z29yaSAoKTsKLSAgICAgIGJpdG1hcCBleHBvcnRzID0gZy5leHBvcnRzIChiYik7Ci0K LSAgICAgIGlmIChiaXRtYXBfYml0X3AgKGV4cG9ydHMsIGkpKQorICAgICAgVmFsdWVfUmFuZ2Ug ciAoVFJFRV9UWVBFIChuYW1lKSk7CisgICAgICBpZiAoZy5vdXRnb2luZ19lZGdlX3JhbmdlX3Ag KHIsIGUsIG5hbWUsICp0aGlzKSkKIAl7Ci0JICBWYWx1ZV9SYW5nZSByIChUUkVFX1RZUEUgKG5h bWUpKTsKLQkgIGlmIChnLm91dGdvaW5nX2VkZ2VfcmFuZ2VfcCAociwgZSwgbmFtZSwgKnRoaXMp KQorCSAgVmFsdWVfUmFuZ2UgY2FjaGVkX3JhbmdlIChUUkVFX1RZUEUgKG5hbWUpKTsKKwkgIGlm IChnZXRfY2FjaGUgKGNhY2hlZF9yYW5nZSwgbmFtZSkpCisJICAgIHIuaW50ZXJzZWN0IChjYWNo ZWRfcmFuZ2UpOworCisJICBzZXRfY2FjaGUgKHIsIG5hbWUpOworCSAgaWYgKERFQlVHX1NPTFZF UikKIAkgICAgewotCSAgICAgIFZhbHVlX1JhbmdlIGNhY2hlZF9yYW5nZSAoVFJFRV9UWVBFIChu YW1lKSk7Ci0JICAgICAgaWYgKGdldF9jYWNoZSAoY2FjaGVkX3JhbmdlLCBuYW1lKSkKLQkJci5p bnRlcnNlY3QgKGNhY2hlZF9yYW5nZSk7Ci0KLQkgICAgICBzZXRfY2FjaGUgKHIsIG5hbWUpOwot CSAgICAgIGlmIChERUJVR19TT0xWRVIpCi0JCXsKLQkJICBmcHJpbnRmIChkdW1wX2ZpbGUsICJv dXRnb2luZ19lZGdlX3JhbmdlX3AgZm9yICIpOwotCQkgIHByaW50X2dlbmVyaWNfZXhwciAoZHVt cF9maWxlLCBuYW1lLCBUREZfU0xJTSk7Ci0JCSAgZnByaW50ZiAoZHVtcF9maWxlLCAiIG9uIGVk Z2UgJWQtPiVkICIsCi0JCQkgICBlLT5zcmMtPmluZGV4LCBlLT5kZXN0LT5pbmRleCk7Ci0JCSAg ZnByaW50ZiAoZHVtcF9maWxlLCAiaXMgIik7Ci0JCSAgci5kdW1wIChkdW1wX2ZpbGUpOwotCQkg IGZwcmludGYgKGR1bXBfZmlsZSwgIlxuIik7Ci0JCX0KKwkgICAgICBmcHJpbnRmIChkdW1wX2Zp bGUsICJvdXRnb2luZ19lZGdlX3JhbmdlX3AgZm9yICIpOworCSAgICAgIHByaW50X2dlbmVyaWNf ZXhwciAoZHVtcF9maWxlLCBuYW1lLCBUREZfU0xJTSk7CisJICAgICAgZnByaW50ZiAoZHVtcF9m aWxlLCAiIG9uIGVkZ2UgJWQtPiVkICIsCisJCSAgICAgICBlLT5zcmMtPmluZGV4LCBlLT5kZXN0 LT5pbmRleCk7CisJICAgICAgZnByaW50ZiAoZHVtcF9maWxlLCAiaXMgIik7CisJICAgICAgci5k dW1wIChkdW1wX2ZpbGUpOworCSAgICAgIGZwcmludGYgKGR1bXBfZmlsZSwgIlxuIik7CiAJICAg IH0KIAl9CiAgICAgfQo= --------------ljzPyYrI00KOhK60xmjREAVj--