From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 19281 invoked by alias); 8 Jul 2011 03:20:29 -0000 Received: (qmail 19260 invoked by uid 22791); 8 Jul 2011 03:20:26 -0000 X-SWARE-Spam-Status: No, hits=-1.6 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,RCVD_IN_DNSWL_NONE,T_RP_MATCHES_RCVD,T_TO_NO_BRKTS_FREEMAIL X-Spam-Check-By: sourceware.org Received: from mailout-de.gmx.net (HELO mailout-de.gmx.net) (213.165.64.23) by sourceware.org (qpsmtpd/0.43rc1) with SMTP; Fri, 08 Jul 2011 03:20:08 +0000 Received: (qmail invoked by alias); 08 Jul 2011 03:20:06 -0000 Received: from mon.egee-see.org (EHLO [139.91.70.93]) [139.91.70.93] by mail.gmx.net (mp003) with SMTP; 08 Jul 2011 05:20:06 +0200 Date: Fri, 08 Jul 2011 03:33:00 -0000 From: Dimitrios Apostolou To: gcc-patches@gcc.gnu.org cc: Paolo Bonzini , Steven Bosscher Subject: [df-scan.c] Optimise DF_REFs ordering in collection_rec, use HARD_REG_SETs instead of bitmaps Message-ID: User-Agent: Alpine 2.02 (LNX 1266 2009-07-14) MIME-Version: 1.0 Content-Type: MULTIPART/MIXED; BOUNDARY="8323328-1642841221-1310095206=:1237" X-IsSubscribed: yes Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org X-SW-Source: 2011-07/txt/msg00580.txt.bz2 This message is in MIME format. The first part should be readable text, while the remaining parts are likely unreadable without MIME-aware tools. --8323328-1642841221-1310095206=:1237 Content-Type: TEXT/PLAIN; format=flowed; charset=US-ASCII Content-length: 786 Hello list, The attached patch does two things for df_get_call_refs(): * First it uses HARD_REG_SETs for defs_generated and regs_invalidated_by_call, instead of bitmaps. Replacing in total more than 400K calls (for my testcase) to bitmap_bit_p() with the much faster TEST_HARD_REG_BIT, reduces the total instruction count from about 13M to 1.5M. * Second it produces the REFs in REGNO order, which is important to keep the collection_rec sorted most times, and avoid expensive calls to qsort(). Thanks to Paolo Bonzini for idea and mentoring. The second part makes a big difference if accompanied with another patch in df_insn_refs_collect(). I'll post a followup patch, that is unfortunately unstable for some of my tests, so I'd appreciate any comments. Thanks, Dimitris --8323328-1642841221-1310095206=:1237 Content-Type: TEXT/plain; name=df1.diff Content-Transfer-Encoding: BASE64 Content-ID: Content-Description: Content-Disposition: attachment; filename=df1.diff Content-length: 5889 PT09IG1vZGlmaWVkIGZpbGUgJ2djYy9kZi1zY2FuLmMnDQotLS0gZ2NjL2Rm LXNjYW4uYwkyMDExLTAyLTAyIDIwOjA4OjA2ICswMDAwDQorKysgZ2NjL2Rm LXNjYW4uYwkyMDExLTA3LTA4IDAxOjI4OjU1ICswMDAwDQpAQCAtMzMxNywy MCArMzMxNyw1NiBAQA0KICAgICAgICAgICAgICAgICAgIGludCBmbGFncykN CiB7DQogICBydHggbm90ZTsNCi0gIGJpdG1hcF9pdGVyYXRvciBiaTsNCi0g IHVuc2lnbmVkIGludCB1aTsNCiAgIGJvb2wgaXNfc2libGluZ19jYWxsOw0K ICAgdW5zaWduZWQgaW50IGk7DQogICBkZl9yZWYgZGVmOw0KLSAgYml0bWFw X2hlYWQgZGVmc19nZW5lcmF0ZWQ7DQorICBIQVJEX1JFR19TRVQgZGVmc19n ZW5lcmF0ZWQ7DQogDQotICBiaXRtYXBfaW5pdGlhbGl6ZSAoJmRlZnNfZ2Vu ZXJhdGVkLCAmZGZfYml0bWFwX29ic3RhY2spOw0KKyAgQ0xFQVJfSEFSRF9S RUdfU0VUKGRlZnNfZ2VuZXJhdGVkKTsNCiANCiAgIC8qIERvIG5vdCBnZW5l cmF0ZSBjbG9iYmVycyBmb3IgcmVnaXN0ZXJzIHRoYXQgYXJlIHRoZSByZXN1 bHQgb2YgdGhlDQogICAgICBjYWxsLiAgVGhpcyBjYXVzZXMgb3JkZXJpbmcg cHJvYmxlbXMgaW4gdGhlIGNoYWluIGJ1aWxkaW5nIGNvZGUNCiAgICAgIGRl cGVuZGluZyBvbiB3aGljaCBkZWYgaXMgc2VlbiBmaXJzdC4gICovDQogICBG T1JfRUFDSF9WRUNfRUxUIChkZl9yZWYsIGNvbGxlY3Rpb25fcmVjLT5kZWZf dmVjLCBpLCBkZWYpDQotICAgIGJpdG1hcF9zZXRfYml0ICgmZGVmc19nZW5l cmF0ZWQsIERGX1JFRl9SRUdOTyAoZGVmKSk7DQorICAgIFNFVF9IQVJEX1JF R19CSVQgKGRlZnNfZ2VuZXJhdGVkLCBERl9SRUZfUkVHTk8gKGRlZikpOw0K Kw0KKyAgaXNfc2libGluZ19jYWxsID0gU0lCTElOR19DQUxMX1AgKGluc25f aW5mby0+aW5zbik7DQorDQorICBmb3IgKGkgPSAwOyBpIDwgRklSU1RfUFNF VURPX1JFR0lTVEVSOyBpKyspDQorICAgIHsNCisgICAgICBpZiAoaSA9PSBT VEFDS19QT0lOVEVSX1JFR05VTSkNCisJLyogVGhlIHN0YWNrIHB0ciBpcyB1 c2VkIChob25vcmFyaWx5KSBieSBhIENBTEwgaW5zbi4gICovDQorCWRmX3Jl Zl9yZWNvcmQgKERGX1JFRl9CQVNFLCBjb2xsZWN0aW9uX3JlYywgcmVnbm9f cmVnX3J0eFtpXSwNCisJCSAgICAgICBOVUxMLCBiYiwgaW5zbl9pbmZvLCBE Rl9SRUZfUkVHX1VTRSwNCisJCSAgICAgICBERl9SRUZfQ0FMTF9TVEFDS19V U0FHRSB8IGZsYWdzKTsNCisgICAgICBlbHNlIGlmIChnbG9iYWxfcmVnc1tp XSkNCisJew0KKwkgIC8qIENhbGxzIHRvIGNvbnN0IGZ1bmN0aW9ucyBjYW5u b3QgYWNjZXNzIGFueSBnbG9iYWwgcmVnaXN0ZXJzIGFuZA0KKwkgICAgIGNh bGxzIHRvIHB1cmUgZnVuY3Rpb25zIGNhbm5vdCBzZXQgdGhlbS4gIEFsbCBv dGhlciBjYWxscyBtYXkNCisJICAgICByZWZlcmVuY2UgYW55IG9mIHRoZSBn bG9iYWwgcmVnaXN0ZXJzLCBzbyB0aGV5IGFyZSByZWNvcmRlZCBhcw0KKwkg ICAgIHVzZWQuICovDQorCSAgaWYgKCFSVExfQ09OU1RfQ0FMTF9QIChpbnNu X2luZm8tPmluc24pKQ0KKwkgICAgew0KKwkgICAgICBkZl9yZWZfcmVjb3Jk IChERl9SRUZfQkFTRSwgY29sbGVjdGlvbl9yZWMsIHJlZ25vX3JlZ19ydHhb aV0sDQorCQkJICAgICBOVUxMLCBiYiwgaW5zbl9pbmZvLCBERl9SRUZfUkVH X1VTRSwgZmxhZ3MpOw0KKwkgICAgICBpZiAoIVJUTF9QVVJFX0NBTExfUCAo aW5zbl9pbmZvLT5pbnNuKSkNCisJCWRmX3JlZl9yZWNvcmQgKERGX1JFRl9C QVNFLCBjb2xsZWN0aW9uX3JlYywgcmVnbm9fcmVnX3J0eFtpXSwNCisJCQkg ICAgICAgTlVMTCwgYmIsIGluc25faW5mbywgREZfUkVGX1JFR19ERUYsIGZs YWdzKTsNCisJICAgIH0NCisJfQ0KKyAgICAgIC8qIFRPRE8gSEFSRF9SRUdf U0VUIHNldCBpbnRlcnNlY3Rpb24hICovDQorICAgICAgZWxzZQkJCS8qICFn bG9iYWxfcmVnc1tpXSAqLw0KKwkvKiB0cmFjayBDYWxsZXItU2F2ZWQgcmVn aXN0ZXJzICovDQorCWlmIChURVNUX0hBUkRfUkVHX0JJVChyZWdzX2ludmFs aWRhdGVkX2J5X2NhbGwsIGkpDQorCSAgICAmJiAhVEVTVF9IQVJEX1JFR19C SVQgKGRlZnNfZ2VuZXJhdGVkLCBpKQ0KKwkgICAgJiYgKCFpc19zaWJsaW5n X2NhbGwNCisJCXx8ICFiaXRtYXBfYml0X3AgKGRmLT5leGl0X2Jsb2NrX3Vz ZXMsIGkpDQorCQl8fCByZWZlcnNfdG9fcmVnbm9fcCAoaSwgaSsxLA0KKwkJ CQkgICAgICBjcnRsLT5yZXR1cm5fcnR4LCBOVUxMKSkpDQorCSAgZGZfcmVm X3JlY29yZCAoREZfUkVGX0JBU0UsIGNvbGxlY3Rpb25fcmVjLCByZWdub19y ZWdfcnR4W2ldLA0KKwkJCSBOVUxMLCBiYiwgaW5zbl9pbmZvLCBERl9SRUZf UkVHX0RFRiwNCisJCQkgREZfUkVGX01BWV9DTE9CQkVSIHwgZmxhZ3MpOw0K KyAgICB9DQogDQogICAvKiBSZWNvcmQgdGhlIHJlZ2lzdGVycyB1c2VkIHRv IHBhc3MgYXJndW1lbnRzLCBhbmQgZXhwbGljaXRseQ0KICAgICAgbm90ZWQg YXMgY2xvYmJlcmVkLiAgKi8NCkBAIC0zMzQ1LDcgKzMzODEsNyBAQA0KIAkg IGlmIChSRUdfUCAoWEVYUCAoWEVYUCAobm90ZSwgMCksIDApKSkNCiAJICAg IHsNCiAJICAgICAgdW5zaWduZWQgaW50IHJlZ25vID0gUkVHTk8gKFhFWFAg KFhFWFAgKG5vdGUsIDApLCAwKSk7DQotCSAgICAgIGlmICghYml0bWFwX2Jp dF9wICgmZGVmc19nZW5lcmF0ZWQsIHJlZ25vKSkNCisJICAgICAgaWYgKCFU RVNUX0hBUkRfUkVHX0JJVCAoZGVmc19nZW5lcmF0ZWQsIHJlZ25vKSkNCiAJ CWRmX2RlZnNfcmVjb3JkIChjb2xsZWN0aW9uX3JlYywgWEVYUCAobm90ZSwg MCksIGJiLA0KIAkJCQlpbnNuX2luZm8sIGZsYWdzKTsNCiAJICAgIH0NCkBA IC0zMzU1LDQwICszMzkxLDYgQEANCiAJfQ0KICAgICB9DQogDQotICAvKiBU aGUgc3RhY2sgcHRyIGlzIHVzZWQgKGhvbm9yYXJpbHkpIGJ5IGEgQ0FMTCBp bnNuLiAgKi8NCi0gIGRmX3JlZl9yZWNvcmQgKERGX1JFRl9CQVNFLCBjb2xs ZWN0aW9uX3JlYywgcmVnbm9fcmVnX3J0eFtTVEFDS19QT0lOVEVSX1JFR05V TV0sDQotCQkgTlVMTCwgYmIsIGluc25faW5mbywgREZfUkVGX1JFR19VU0Us DQotCQkgREZfUkVGX0NBTExfU1RBQ0tfVVNBR0UgfCBmbGFncyk7DQotDQot ICAvKiBDYWxscyB0byBjb25zdCBmdW5jdGlvbnMgY2Fubm90IGFjY2VzcyBh bnkgZ2xvYmFsIHJlZ2lzdGVycyBhbmQgY2FsbHMgdG8NCi0gICAgIHB1cmUg ZnVuY3Rpb25zIGNhbm5vdCBzZXQgdGhlbS4gIEFsbCBvdGhlciBjYWxscyBt YXkgcmVmZXJlbmNlIGFueSBvZiB0aGUNCi0gICAgIGdsb2JhbCByZWdpc3Rl cnMsIHNvIHRoZXkgYXJlIHJlY29yZGVkIGFzIHVzZWQuICAqLw0KLSAgaWYg KCFSVExfQ09OU1RfQ0FMTF9QIChpbnNuX2luZm8tPmluc24pKQ0KLSAgICBm b3IgKGkgPSAwOyBpIDwgRklSU1RfUFNFVURPX1JFR0lTVEVSOyBpKyspDQot ICAgICAgaWYgKGdsb2JhbF9yZWdzW2ldKQ0KLQl7DQotCSAgZGZfcmVmX3Jl Y29yZCAoREZfUkVGX0JBU0UsIGNvbGxlY3Rpb25fcmVjLCByZWdub19yZWdf cnR4W2ldLA0KLQkJCSBOVUxMLCBiYiwgaW5zbl9pbmZvLCBERl9SRUZfUkVH X1VTRSwgZmxhZ3MpOw0KLQkgIGlmICghUlRMX1BVUkVfQ0FMTF9QIChpbnNu X2luZm8tPmluc24pKQ0KLQkgICAgZGZfcmVmX3JlY29yZCAoREZfUkVGX0JB U0UsIGNvbGxlY3Rpb25fcmVjLCByZWdub19yZWdfcnR4W2ldLA0KLQkJCSAg IE5VTEwsIGJiLCBpbnNuX2luZm8sIERGX1JFRl9SRUdfREVGLCBmbGFncyk7 DQotCX0NCi0NCi0gIGlzX3NpYmxpbmdfY2FsbCA9IFNJQkxJTkdfQ0FMTF9Q IChpbnNuX2luZm8tPmluc24pOw0KLSAgRVhFQ1VURV9JRl9TRVRfSU5fQklU TUFQIChyZWdzX2ludmFsaWRhdGVkX2J5X2NhbGxfcmVnc2V0LCAwLCB1aSwg YmkpDQotICAgIHsNCi0gICAgICBpZiAoIWdsb2JhbF9yZWdzW3VpXQ0KLQkg ICYmICghYml0bWFwX2JpdF9wICgmZGVmc19nZW5lcmF0ZWQsIHVpKSkNCi0J ICAmJiAoIWlzX3NpYmxpbmdfY2FsbA0KLQkgICAgICB8fCAhYml0bWFwX2Jp dF9wIChkZi0+ZXhpdF9ibG9ja191c2VzLCB1aSkNCi0JICAgICAgfHwgcmVm ZXJzX3RvX3JlZ25vX3AgKHVpLCB1aSsxLA0KLQkJCQkgICAgY3J0bC0+cmV0 dXJuX3J0eCwgTlVMTCkpKQ0KLSAgICAgICAgZGZfcmVmX3JlY29yZCAoREZf UkVGX0JBU0UsIGNvbGxlY3Rpb25fcmVjLCByZWdub19yZWdfcnR4W3VpXSwN Ci0JCSAgICAgICBOVUxMLCBiYiwgaW5zbl9pbmZvLCBERl9SRUZfUkVHX0RF RiwNCi0JCSAgICAgICBERl9SRUZfTUFZX0NMT0JCRVIgfCBmbGFncyk7DQot ICAgIH0NCi0NCi0gIGJpdG1hcF9jbGVhciAoJmRlZnNfZ2VuZXJhdGVkKTsN CiAgIHJldHVybjsNCiB9DQogDQoNCg== --8323328-1642841221-1310095206=:1237--