From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 18194 invoked by alias); 12 Mar 2013 16:01:25 -0000 Received: (qmail 18175 invoked by uid 22791); 12 Mar 2013 16:01:21 -0000 X-SWARE-Spam-Status: No, hits=-5.2 required=5.0 tests=AWL,BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,KHOP_RCVD_TRUST,KHOP_THREADED,RCVD_IN_DNSWL_LOW,RCVD_IN_HOSTKARMA_YE X-Spam-Check-By: sourceware.org Received: from mail-ve0-f175.google.com (HELO mail-ve0-f175.google.com) (209.85.128.175) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Tue, 12 Mar 2013 16:01:04 +0000 Received: by mail-ve0-f175.google.com with SMTP id cy12so3572826veb.6 for ; Tue, 12 Mar 2013 09:01:03 -0700 (PDT) X-Received: by 10.52.89.83 with SMTP id bm19mr5789249vdb.123.1363104063428; Tue, 12 Mar 2013 09:01:03 -0700 (PDT) MIME-Version: 1.0 Received: by 10.58.237.1 with HTTP; Tue, 12 Mar 2013 09:00:22 -0700 (PDT) In-Reply-To: References: From: Steven Bosscher Date: Tue, 12 Mar 2013 16:01:00 -0000 Message-ID: Subject: Re: [PATCH][6/n] tree LIM TLC To: Richard Biener Cc: gcc-patches@gcc.gnu.org Content-Type: multipart/mixed; boundary=20cf307f32647e1ed704d7bc65e4 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: 2013-03/txt/msg00441.txt.bz2 --20cf307f32647e1ed704d7bc65e4 Content-Type: text/plain; charset=ISO-8859-1 Content-length: 1532 On Tue, Mar 12, 2013 at 4:33 PM, Richard Biener wrote: > On Tue, 12 Mar 2013, Steven Bosscher wrote: >> I suppose this renders my LIM patch obsolete. > > Not really - it's still > > tree loop invariant motion: 588.31 (78%) usr > > so limiting the O(n^2) dependence testing is a good thing. But I > can take it over from here and implement that ontop of my patches > if you like. That'd be good, let's keep it in one hand, one set. >> Did you also look at the memory foot print? > > Yeah, unfortunately processing outermost loops separately doesn't > reduce peak memory consumption. I'll look into getting rid of the > all-refs bitmaps, but I'm not there yet. A few more ideas (though probably not with as much impact): Is it possible to use a bitmap_head for the (now merged) dep_loop/indep_loop, instead of bitmap? Likewise for a few other bitmaps, especially the vectors of bitmaps. Put "struct depend" in an alloc pool. (Also allows one to wipe them all out in free_lim_aux_data.) Likewise for "struct mem_ref". Use a shared mem_ref for the error_mark_node case (and hoist the MEM_ANALYZABLE checks in refs_independent_p above the bitmap tests). Use nameless temps instead of lsm_tmp_name_add. > Currently the testcase peaks at 1.7GB for me (after LIM, then > it gets worse with DSE and IRA). And I only tested -O1 sofar. Try my DSE patch (corrected version attached). What are you using now to measure per-pass memory usage? I'm still using my old hack (also attached) but it's not quite optimal. Ciao! Steven --20cf307f32647e1ed704d7bc65e4 Content-Type: application/octet-stream; name="PR39326_RTLDSE.diff" Content-Disposition: attachment; filename="PR39326_RTLDSE.diff" Content-Transfer-Encoding: base64 X-Attachment-Id: f_he78umqo0 Content-length: 5267 CVBSIG1pZGRsZS1lbmQvMzkzMjYKCSogZHNlLmMgKHJlcGxhY2VfcmVhZCk6 IElmIHRoZSBzdG9yZWQgdmFsdWUgaXMgYSBwc2V1ZG8tcmVnaXN0ZXIKCXRo YXQgaXMgc2V0IG9ubHkgb25jZSwgcmUtdXNlIGl0IHRvIHJlcGxhY2UgdGhl IGxvYWQgaW5zdGVhZCBvZgoJY3JlYXRpbmcgYSBuZXcgcmVnaXN0ZXIuCgpJ bmRleDogZHNlLmMKPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PQotLS0gZHNlLmMJ KHJldmlzaW9uIDE5NjU3NikKKysrIGRzZS5jCSh3b3JraW5nIGNvcHkpCkBA IC0yMDExLDcgKzIwMTEsNyBAQCByZXBsYWNlX3JlYWQgKHN0b3JlX2luZm9f dCBzdG9yZV9pbmZvLCBpbnNuX2luZm9fdAogewogICBlbnVtIG1hY2hpbmVf bW9kZSBzdG9yZV9tb2RlID0gR0VUX01PREUgKHN0b3JlX2luZm8tPm1lbSk7 CiAgIGVudW0gbWFjaGluZV9tb2RlIHJlYWRfbW9kZSA9IEdFVF9NT0RFIChy ZWFkX2luZm8tPm1lbSk7Ci0gIHJ0eCBpbnNucywgdGhpc19pbnNuLCByZWFk X3JlZzsKKyAgcnR4IGluc25zLCB0aGlzX2luc24sIHJlYWRfdmFsLCByZWFk X3JlZzsKICAgYmFzaWNfYmxvY2sgYmI7CiAKICAgaWYgKCFkYmdfY250IChk c2UpKQpAQCAtMjAzMywxOSArMjAzMywyNyBAQCByZXBsYWNlX3JlYWQgKHN0 b3JlX2luZm9fdCBzdG9yZV9pbmZvLCBpbnNuX2luZm9fdAogCSAgICAgR0VU X01PREVfTkFNRSAoc3RvcmVfbW9kZSksIElOU05fVUlEIChzdG9yZV9pbnNu LT5pbnNuKSk7CiAgIHN0YXJ0X3NlcXVlbmNlICgpOwogICBiYiA9IEJMT0NL X0ZPUl9JTlNOIChyZWFkX2luc24tPmluc24pOwotICByZWFkX3JlZyA9IGdl dF9zdG9yZWRfdmFsIChzdG9yZV9pbmZvLAorICByZWFkX3ZhbCA9IGdldF9z dG9yZWRfdmFsIChzdG9yZV9pbmZvLAogCQkJICAgICByZWFkX21vZGUsIHJl YWRfaW5mby0+YmVnaW4sIHJlYWRfaW5mby0+ZW5kLAogCQkJICAgICBiYiwg ZmFsc2UpOwotICBpZiAocmVhZF9yZWcgPT0gTlVMTF9SVFgpCisgIGlmIChy ZWFkX3ZhbCA9PSBOVUxMX1JUWCkKICAgICB7CiAgICAgICBlbmRfc2VxdWVu Y2UgKCk7CiAgICAgICBpZiAoZHVtcF9maWxlICYmIChkdW1wX2ZsYWdzICYg VERGX0RFVEFJTFMpKQogCWZwcmludGYgKGR1bXBfZmlsZSwgIiAtLSBjb3Vs ZCBub3QgZXh0cmFjdCBiaXRzIG9mIHN0b3JlZCB2YWx1ZVxuIik7CiAgICAg ICByZXR1cm4gZmFsc2U7CiAgICAgfQotICAvKiBGb3JjZSB0aGUgdmFsdWUg aW50byBhIG5ldyByZWdpc3RlciBzbyB0aGF0IGl0IHdvbid0IGJlIGNsb2Ji ZXJlZAotICAgICBiZXR3ZWVuIHRoZSBzdG9yZSBhbmQgdGhlIGxvYWQuICAq LwotICByZWFkX3JlZyA9IGNvcHlfdG9fbW9kZV9yZWcgKHJlYWRfbW9kZSwg cmVhZF9yZWcpOworCisgIC8qIElmIFJFQURfUkVHIGlzIGEgcHNldWRvIHRo YXQgaXMgb25seSBzZXQgb25jZSwgcmUtdXNlIHRoZSByZWdpc3Rlci4KKyAg ICAgT3RoZXJ3aXNlLCBmb3JjZSB0aGUgdmFsdWUgaW50byBhIG5ldyByZWdp c3RlciBzbyB0aGF0IGl0IHdvbid0IGJlCisgICAgIGNsb2JiZXJlZCBiZXR3 ZWVuIHRoZSBzdG9yZSBhbmQgdGhlIGxvYWQuICAqLworICBpZiAoISBSRUdf UCAocmVhZF92YWwpIHx8IEhBUkRfUkVHSVNURVJfUCAocmVhZF92YWwpCisg ICAgICB8fCBSRUdOTyAocmVhZF92YWwpID49IERGX1JFR19TSVpFIChkZikK KyAgICAgIHx8IERGX1JFR19ERUZfQ09VTlQgKFJFR05PIChyZWFkX3ZhbCkp ICE9IDEpCisgICAgcmVhZF9yZWcgPSBjb3B5X3RvX21vZGVfcmVnIChyZWFk X21vZGUsIHJlYWRfdmFsKTsKKyAgZWxzZQorICAgIHJlYWRfcmVnID0gcmVh ZF92YWw7CisKICAgaW5zbnMgPSBnZXRfaW5zbnMgKCk7CiAgIGVuZF9zZXF1 ZW5jZSAoKTsKIApAQCAtMjA3OSwxNiArMjA4NywxNSBAQCByZXBsYWNlX3Jl YWQgKHN0b3JlX2luZm9fdCBzdG9yZV9pbmZvLCBpbnNuX2luZm9fdAogCiAg IGlmICh2YWxpZGF0ZV9jaGFuZ2UgKHJlYWRfaW5zbi0+aW5zbiwgbG9jLCBy ZWFkX3JlZywgMCkpCiAgICAgewotICAgICAgZGVmZXJyZWRfY2hhbmdlX3Qg ZGVmZXJyZWRfY2hhbmdlID0KLQkoZGVmZXJyZWRfY2hhbmdlX3QpIHBvb2xf YWxsb2MgKGRlZmVycmVkX2NoYW5nZV9wb29sKTsKLQotICAgICAgLyogSW5z ZXJ0IHRoaXMgcmlnaHQgYmVmb3JlIHRoZSBzdG9yZSBpbnNuIHdoZXJlIGl0 IHdpbGwgYmUgc2FmZQotCSBmcm9tIGxhdGVyIGluc25zIHRoYXQgbWlnaHQg Y2hhbmdlIGl0IGJlZm9yZSB0aGUgcmVhZC4gICovCi0gICAgICBlbWl0X2lu c25fYmVmb3JlIChpbnNucywgc3RvcmVfaW5zbi0+aW5zbik7Ci0KLSAgICAg IC8qIEFuZCBub3cgZm9yIHRoZSBrbHVkZ2UgcGFydDogY3NlbGliIGNyb2Fr cyBpZiB5b3UganVzdAotCSByZXR1cm4gYXQgdGhpcyBwb2ludC4gIFRoZXJl IGFyZSB0d28gcmVhc29ucyBmb3IgdGhpczoKLQorICAgICAgaWYgKGluc25z ICE9IE5VTExfUlRYKQorCS8qIEluc2VydCB0aGlzIHJpZ2h0IGJlZm9yZSB0 aGUgc3RvcmUgaW5zbiB3aGVyZSBpdCB3aWxsIGJlIHNhZmUKKwkgICBmcm9t IGxhdGVyIGluc25zIHRoYXQgbWlnaHQgY2hhbmdlIGl0IGJlZm9yZSB0aGUg cmVhZC4gICovCisJZW1pdF9pbnNuX2JlZm9yZSAoaW5zbnMsIHN0b3JlX2lu c24tPmluc24pOworCisgICAgICAvKiBBbmQgbm93IGZvciB0aGUga2x1ZGdl IHBhcnQ6IGNzZWxpYiBjcm9ha3MgaWYgeW91IGhhdmUKKwkgY3JlYXRlIGEg bmV3IHJlZ2lzdGVyIGFuZCBqdXN0IHJldHVybiBhdCB0aGlzIHBvaW50Lgor CSBUaGVyZSBhcmUgdHdvIHJlYXNvbnMgZm9yIHRoaXM6CisKIAkgMSkgQ3Nl bGliIGhhcyBhbiBpZGVhIG9mIGhvdyBtYW55IHBzZXVkb3MgdGhlcmUgYXJl IGFuZAogCSB0aGF0IGRvZXMgbm90IGluY2x1ZGUgdGhlIG5ldyBvbmVzIHdl IGp1c3QgYWRkZWQuCiAKQEAgLTIxMDgsMTMgKzIxMTUsMTcgQEAgcmVwbGFj ZV9yZWFkIChzdG9yZV9pbmZvX3Qgc3RvcmVfaW5mbywgaW5zbl9pbmZvX3QK IAkgYW5kIHdoZW4gd2UgYXJlIGZpbmlzaGVkIHdpdGggdGhlIGJsb2NrLCB3 ZSB1bmRvIHRoaXMuICBXZQogCSBrZWVwIGEgdGFibGUgb2YgbWVtcyB0byBn ZXQgcmlkIG9mLiAgQXQgdGhlIGVuZCBvZiB0aGUgYmFzaWMKIAkgYmxvY2sg d2UgY2FuIHB1dCB0aGVtIGJhY2suICAqLworICAgICAgaWYgKHJlYWRfcmVn ICE9IHJlYWRfdmFsKQorCXsKKwkgIGRlZmVycmVkX2NoYW5nZV90IGRlZmVy cmVkX2NoYW5nZSA9CisJICAgIChkZWZlcnJlZF9jaGFuZ2VfdCkgcG9vbF9h bGxvYyAoZGVmZXJyZWRfY2hhbmdlX3Bvb2wpOworCSAgKmxvYyA9IHJlYWRf aW5mby0+bWVtOworCSAgZGVmZXJyZWRfY2hhbmdlLT5uZXh0ID0gZGVmZXJy ZWRfY2hhbmdlX2xpc3Q7CisJICBkZWZlcnJlZF9jaGFuZ2VfbGlzdCA9IGRl ZmVycmVkX2NoYW5nZTsKKwkgIGRlZmVycmVkX2NoYW5nZS0+bG9jID0gbG9j OworCSAgZGVmZXJyZWRfY2hhbmdlLT5yZWcgPSByZWFkX3JlZzsKKwl9CiAK LSAgICAgICpsb2MgPSByZWFkX2luZm8tPm1lbTsKLSAgICAgIGRlZmVycmVk X2NoYW5nZS0+bmV4dCA9IGRlZmVycmVkX2NoYW5nZV9saXN0OwotICAgICAg ZGVmZXJyZWRfY2hhbmdlX2xpc3QgPSBkZWZlcnJlZF9jaGFuZ2U7Ci0gICAg ICBkZWZlcnJlZF9jaGFuZ2UtPmxvYyA9IGxvYzsKLSAgICAgIGRlZmVycmVk X2NoYW5nZS0+cmVnID0gcmVhZF9yZWc7Ci0KICAgICAgIC8qIEdldCByaWQg b2YgdGhlIHJlYWRfaW5mbywgZnJvbSB0aGUgcG9pbnQgb2YgdmlldyBvZiB0 aGUKIAkgcmVzdCBvZiBkc2UsIHBsYXkgbGlrZSB0aGlzIHJlYWQgbmV2ZXIg aGFwcGVuZWQuICAqLwogICAgICAgcmVhZF9pbnNuLT5yZWFkX3JlYyA9IHJl YWRfaW5mby0+bmV4dDsK --20cf307f32647e1ed704d7bc65e4 Content-Type: application/octet-stream; name="passes_memstat.diff" Content-Disposition: attachment; filename="passes_memstat.diff" Content-Transfer-Encoding: base64 X-Attachment-Id: f_he78xidk1 Content-length: 3136 SW5kZXg6IHBhc3Nlcy5jCj09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KLS0tIHBh c3Nlcy5jCShyZXZpc2lvbiAxOTYxODIpCisrKyBwYXNzZXMuYwkod29ya2lu ZyBjb3B5KQpAQCAtNzcsMTUgKzc3LDY4IEBAIHN0cnVjdCBvcHRfcGFzcyAq Y3VycmVudF9wYXNzOwogCiBzdGF0aWMgdm9pZCByZWdpc3Rlcl9wYXNzX25h bWUgKHN0cnVjdCBvcHRfcGFzcyAqLCBjb25zdCBjaGFyICopOwogCit0eXBl ZGVmIHN0cnVjdAoreworICB1bnNpZ25lZCBsb25nIHNpemUscmVzaWRlbnQs c2hhcmUsdGV4dCxsaWIsZGF0YSxkdDsKK30gc3RhdG1fdDsKKworc3RhdGlj IHZvaWQKK3JlYWRfcHJvY19tZW1vcnlfc3RhdHVzIChzdGF0bV90ICZyZXN1 bHQpCit7CisgIGNvbnN0IGNoYXIqIHN0YXRtX3BhdGggPSAiL3Byb2Mvc2Vs Zi9zdGF0bSI7CisKKyAgRklMRSAqZiA9IGZvcGVuKHN0YXRtX3BhdGgsInIi KTsKKyAgaWYgKCFmKQorICAgIHsKKyAgICAgIHBlcnJvciAoc3RhdG1fcGF0 aCk7CisgICAgICBnY2NfdW5yZWFjaGFibGUgKCk7CisgICAgfQorICBpZiAo NyAhPSBmc2NhbmYgKGYsICIlbHUgJWx1ICVsdSAlbHUgJWx1ICVsdSAlbHUi LAorCQkgICAmcmVzdWx0LnNpemUsICZyZXN1bHQucmVzaWRlbnQsICZyZXN1 bHQuc2hhcmUsCisJCSAgICZyZXN1bHQudGV4dCwgJnJlc3VsdC5saWIsICZy ZXN1bHQuZGF0YSwKKwkJICAgJnJlc3VsdC5kdCkpCisgICAgeworICAgICAg cGVycm9yIChzdGF0bV9wYXRoKTsKKyAgICAgIGdjY191bnJlYWNoYWJsZSAo KTsKKyAgICB9CisgIGZjbG9zZShmKTsKK30KKwogLyogQ2FsbCBmcm9tIGFu eXdoZXJlIHRvIGZpbmQgb3V0IHdoYXQgcGFzcyB0aGlzIGlzLiAgVXNlZnVs IGZvcgogICAgcHJpbnRpbmcgb3V0IGRlYnVnZ2luZyBpbmZvcm1hdGlvbiBk ZWVwIGluc2lkZSBhbiBzZXJ2aWNlCiAgICByb3V0aW5lLiAgKi8KKworI2lu Y2x1ZGUgImJpdG1hcC5oIgorI2luY2x1ZGUgInJlZ3NldC5oIgorCitzdGF0 aWMgc2l6ZV90CitvYnN0YWNrX21lbW9yeV91c2VkMiAoc3RydWN0IG9ic3Rh Y2sgKmgpCit7CisgIHN0cnVjdCBfb2JzdGFja19jaHVuayogbHA7CisgIHNp emVfdCBuYnl0ZXMgPSAwOworCisgIGZvciAobHAgPSBoLT5jaHVuazsgbHAg IT0gMDsgbHAgPSBscC0+cHJldikKKyAgICB7CisgICAgICBuYnl0ZXMgKz0g KHNpemVfdCkgKGxwLT5saW1pdCAtIChjaGFyICopIGxwKTsKKyAgICB9Cisg IHJldHVybiBuYnl0ZXM7Cit9CisKIHZvaWQKIHByaW50X2N1cnJlbnRfcGFz cyAoRklMRSAqZmlsZSkKIHsKICAgaWYgKGN1cnJlbnRfcGFzcykKLSAgICBm cHJpbnRmIChmaWxlLCAiY3VycmVudCBwYXNzID0gJXMgKCVkKVxuIiwKLQkg ICAgIGN1cnJlbnRfcGFzcy0+bmFtZSwgY3VycmVudF9wYXNzLT5zdGF0aWNf cGFzc19udW1iZXIpOworICAgIHsKKyAgICAgIHN0YXRtX3Qgc3RhdG07Cisg ICAgICBpbnQgcGFnZXNpemUgPSBnZXRwYWdlc2l6ZSAoKTsKKyAgICAgIHVu c2lnbmVkIGJvcyA9IG9ic3RhY2tfbWVtb3J5X3VzZWQyICgmYml0bWFwX2Rl ZmF1bHRfb2JzdGFjay5vYnN0YWNrKTsKKyAgICAgIHVuc2lnbmVkIHJvcyA9 IG9ic3RhY2tfbWVtb3J5X3VzZWQyICgmcmVnX29ic3RhY2sub2JzdGFjayk7 CisgICAgICByZWFkX3Byb2NfbWVtb3J5X3N0YXR1cyAoc3RhdG0pOworICAg ICAgZnByaW50ZiAoZmlsZSwgImN1cnJlbnQgcGFzcyA9ICUzMnMgKCUzZCkg JTEybHUgJTEybHUgJTEybHUgJTEydSAlMTJ1XG4iLAorCSAgICAgICBjdXJy ZW50X3Bhc3MtPm5hbWUsIGN1cnJlbnRfcGFzcy0+c3RhdGljX3Bhc3NfbnVt YmVyLAorCSAgICAgICBzdGF0bS5zaXplICogcGFnZXNpemUsIHN0YXRtLnJl c2lkZW50ICogcGFnZXNpemUsCisJICAgICAgIHN0YXRtLnNoYXJlICogcGFn ZXNpemUsIGJvcywgcm9zKTsKKyAgICB9CiAgIGVsc2UKICAgICBmcHJpbnRm IChmaWxlLCAibm8gY3VycmVudCBwYXNzLlxuIik7CiB9CkBAIC0yMjg2LDcg KzIzMzksNyBAQCBleGVjdXRlX29uZV9wYXNzIChzdHJ1Y3Qgb3B0X3Bhc3Mg KnBhc3MpCiAgICAgICBjdXJyZW50X3Bhc3MgPSBOVUxMOwogICAgICAgcmV0 dXJuIGZhbHNlOwogICAgIH0KLQorcHJpbnRfY3VycmVudF9wYXNzIChzdGRl cnIpOwogICAvKiBQYXNzIGV4ZWN1dGlvbiBldmVudCB0cmlnZ2VyOiB1c2Vm dWwgdG8gaWRlbnRpZnkgcGFzc2VzIGJlaW5nCiAgICAgIGV4ZWN1dGVkLiAg Ki8KICAgaW52b2tlX3BsdWdpbl9jYWxsYmFja3MgKFBMVUdJTl9QQVNTX0VY RUNVVElPTiwgcGFzcyk7Cg== --20cf307f32647e1ed704d7bc65e4--