From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 23052 invoked by alias); 19 Apr 2011 00:24:39 -0000 Received: (qmail 23043 invoked by uid 22791); 19 Apr 2011 00:24:37 -0000 X-SWARE-Spam-Status: No, hits=-1.8 required=5.0 tests=AWL,BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,SPF_HELO_PASS,T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from smtp-out.google.com (HELO smtp-out.google.com) (216.239.44.51) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Tue, 19 Apr 2011 00:24:20 +0000 Received: from wpaz29.hot.corp.google.com (wpaz29.hot.corp.google.com [172.24.198.93]) by smtp-out.google.com with ESMTP id p3J0OJxG017354 for ; Mon, 18 Apr 2011 17:24:19 -0700 Received: from pzk36 (pzk36.prod.google.com [10.243.19.164]) by wpaz29.hot.corp.google.com with ESMTP id p3J0NaQx016764 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=NOT) for ; Mon, 18 Apr 2011 17:24:18 -0700 Received: by pzk36 with SMTP id 36so2802631pzk.32 for ; Mon, 18 Apr 2011 17:24:17 -0700 (PDT) MIME-Version: 1.0 Received: by 10.142.125.1 with SMTP id x1mr2428948wfc.296.1303172657543; Mon, 18 Apr 2011 17:24:17 -0700 (PDT) Received: by 10.142.230.18 with HTTP; Mon, 18 Apr 2011 17:24:17 -0700 (PDT) In-Reply-To: References: Date: Tue, 19 Apr 2011 03:23:00 -0000 Message-ID: Subject: Re: Improve stack layout heuristic. From: Easwaran Raman To: Michael Matz Cc: gcc-patches@gcc.gnu.org Content-Type: multipart/mixed; boundary=000e0cd22ac8557b3204a13a875d X-System-Of-Record: true 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-04/txt/msg01479.txt.bz2 --000e0cd22ac8557b3204a13a875d Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-length: 3563 On Mon, Apr 18, 2011 at 5:58 AM, Michael Matz wrote: > > Hi, > > [FWIW I can't approve patches, but some feedback nevertheless] > > On Sun, 17 Apr 2011, Easwaran Raman wrote: > > > =A0This patch impoves the heuristic used in assigning stack location to > > stack variables. =A0Currently, if there are 3 variables A, B and C with > > their sizes in increasing order and A and C have a conflict, it will > > put A and B in a partition and C in a separate partition with a total > > frame size of sizeof(B) + sizeof(C). =A0This patch puts B and C in the > > same partition and A in a separate partition, with a total size of > > sizeof(A) + sizeof(C). > > That's the change in stack_var_cmp, to match the comment, right? =A0Makes > sense. > > > The other change in this patch removes the field offset in struct > > stack_var. Right now, the field is always 0 due to the way it is set in > > partition_stack_vars. > > Huh, indeed, starting with the initial version of that code already. =A0T= he > idea clearly was to pack multiple conflicting small objects into the space > of only one larger non-conflicting one by placing them at different > offsets, but that never seems to have been implemented and would require > different tracking of conflicts. =A0I think removing the offset tracking > right now is okay, can be reintroduced once somebody gets motivated > enough. Yes, the intent seems to be what you describe above. I haven't thought about it much, but I am not sure how much a non-backtracking version will buy over the current heuristic. > > > - =A0 =A0 and merge them into partition A. =A0*/ > > - =A0for (last =3D i =3D b; i !=3D EOC; last =3D i, i =3D stack_vars[i]= .next) > > - =A0 =A0{ > > - =A0 =A0 =A0stack_vars[i].offset +=3D offset; > > - =A0 =A0 =A0stack_vars[i].representative =3D a; > > - =A0 =A0} > > - =A0stack_vars[last].next =3D stack_vars[a].next; > > + =A0 /* Add B to A's partition. =A0*/ > > + =A0stack_vars[b].next =3D stack_vars[a].next; > > + =A0stack_vars[b].representative =3D a; > > Hmm. =A0This seems fishy. =A0You don't update the representatives of the > members of the partition that B is the leader of. =A0Additionally you bre= ak > the chain of B's members. =A0That is only a problem if B actually has more > than one member. =A0That might be always the case with your changed sorti= ng > order, but it's an important invariant, so please assert this in this > routine. > B always has one member is an invariant in my scheme. The object corresponding to the outer loop index is always the representative. If B has to have more than one members, it must have been visited in the outer loop in some earlier iteration. But then, its index in the stack_vars_sorted must be greater than the current i. I have added an assertion than stack_vars[b].next =3D=3D EOC in union_stack_vars which is true only when B has one member. > > > @@ -596,7 +581,7 @@ > > =A0 =A0if (vb->conflicts) > > =A0 =A0 =A0{ > > =A0 =A0 =A0 =A0EXECUTE_IF_SET_IN_BITMAP (vb->conflicts, 0, u, bi) > > - =A0 =A0 add_stack_var_conflict (a, stack_vars[u].representative); > > + =A0 =A0 add_stack_var_conflict (a, u); > > Please don't. =A0This uselessly bloats the conflict bitmaps. It is sufficient to add the conflicts of =A0a variable only when it is not merged into some group. =A0I am adding a check to that effect. I am attaching a new patch which excludes the strict aliasing check (which I will send separately) and the changes I have mentioned above. Bootstraps and no regressions in tests. Thanks, Easwaran > > Ciao, > Michael. --000e0cd22ac8557b3204a13a875d Content-Type: text/x-patch; charset=US-ASCII; name="cfgexpand.patch" Content-Disposition: attachment; filename="cfgexpand.patch" Content-Transfer-Encoding: base64 X-Attachment-Id: f_gmo3b9az0 Content-length: 8154 SW5kZXg6IGdjYy90ZXN0c3VpdGUvZ2NjLmRnL3N0YWNrLWxheW91dC0yLmMK PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PQotLS0gZ2NjL3Rlc3RzdWl0ZS9nY2Mu ZGcvc3RhY2stbGF5b3V0LTIuYwkocmV2aXNpb24gMCkKKysrIGdjYy90ZXN0 c3VpdGUvZ2NjLmRnL3N0YWNrLWxheW91dC0yLmMJKHJldmlzaW9uIDApCkBA IC0wLDAgKzEsMjMgQEAKKy8qIHsgZGctZG8gY29tcGlsZSB9ICovCisvKiB7 IGRnLW9wdGlvbnMgIi1PMiAtZmR1bXAtcnRsLWV4cGFuZCIgfSAqLwordm9p ZCBiYXIoIGNoYXIgKik7CitpbnQgZm9vKCkKK3sKKyAgaW50IGk9MDsKKyAg eworICAgIGNoYXIgYVs4MDAwXTsKKyAgICBiYXIoYSk7CisgICAgaSArPSBh WzBdOworICB9CisgIHsKKyAgICBjaGFyIGFbODE5Ml07CisgICAgY2hhciBi WzMyXTsKKyAgICBiYXIoYSk7CisgICAgaSArPSBhWzBdOworICAgIGJhcihi KTsKKyAgICBpICs9IGFbMF07CisgIH0KKyAgcmV0dXJuIGk7Cit9CisvKiB7 IGRnLWZpbmFsIHsgc2Nhbi1ydGwtZHVtcCAic2l6ZSA4MTkyIiAiZXhwYW5k IiB9IH0gKi8KKy8qIHsgZGctZmluYWwgeyBzY2FuLXJ0bC1kdW1wICJzaXpl IDMyIiAiZXhwYW5kIiB9IH0gKi8KSW5kZXg6IGdjYy9jZmdleHBhbmQuYwo9 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09Ci0tLSBnY2MvY2ZnZXhwYW5kLmMJKHJl dmlzaW9uIDE3MTk1NCkKKysrIGdjYy9jZmdleHBhbmQuYwkod29ya2luZyBj b3B5KQpAQCAtMTU4LDExICsxNTgsNiBAQAogICAvKiBUaGUgVmFyaWFibGUu ICAqLwogICB0cmVlIGRlY2w7CiAKLSAgLyogVGhlIG9mZnNldCBvZiB0aGUg dmFyaWFibGUuICBEdXJpbmcgcGFydGl0aW9uaW5nLCB0aGlzIGlzIHRoZQot ICAgICBvZmZzZXQgcmVsYXRpdmUgdG8gdGhlIHBhcnRpdGlvbi4gIEFmdGVy IHBhcnRpdGlvbmluZywgdGhpcwotICAgICBpcyByZWxhdGl2ZSB0byB0aGUg c3RhY2sgZnJhbWUuICAqLwotICBIT1NUX1dJREVfSU5UIG9mZnNldDsKLQog ICAvKiBJbml0aWFsbHksIHRoZSBzaXplIG9mIHRoZSB2YXJpYWJsZS4gIExh dGVyLCB0aGUgc2l6ZSBvZiB0aGUgcGFydGl0aW9uLAogICAgICBpZiB0aGlz IHZhcmlhYmxlIGJlY29tZXMgaXQncyBwYXJ0aXRpb24ncyByZXByZXNlbnRh dGl2ZS4gICovCiAgIEhPU1RfV0lERV9JTlQgc2l6ZTsKQEAgLTI2Nyw3ICsy NjIsNiBAQAogICB2ID0gJnN0YWNrX3ZhcnNbc3RhY2tfdmFyc19udW1dOwog CiAgIHYtPmRlY2wgPSBkZWNsOwotICB2LT5vZmZzZXQgPSAwOwogICB2LT5z aXplID0gdHJlZV9sb3dfY3N0IChERUNMX1NJWkVfVU5JVCAoU1NBVkFSIChk ZWNsKSksIDEpOwogICAvKiBFbnN1cmUgdGhhdCBhbGwgdmFyaWFibGVzIGhh dmUgc2l6ZSwgc28gdGhhdCAmYSAhPSAmYiBmb3IgYW55IHR3bwogICAgICB2 YXJpYWJsZXMgdGhhdCBhcmUgc2ltdWx0YW5lb3VzbHkgbGl2ZS4gICovCkBA IC00MDMsOSArMzk3LDkgQEAKICAgICByZXR1cm4gKGludClsYXJnZWIgLSAo aW50KWxhcmdlYTsKIAogICAvKiBTZWNvbmRhcnkgY29tcGFyZSBvbiBzaXpl LCBkZWNyZWFzaW5nICAqLwotICBpZiAoc2l6ZWEgPCBzaXplYikKLSAgICBy ZXR1cm4gLTE7CiAgIGlmIChzaXplYSA+IHNpemViKQorICAgIHJldHVybiAt MTsKKyAgaWYgKHNpemVhIDwgc2l6ZWIpCiAgICAgcmV0dXJuIDE7CiAKICAg LyogVGVydGlhcnkgY29tcGFyZSBvbiB0cnVlIGFsaWdubWVudCwgZGVjcmVh c2luZy4gICovCkBAIC01NjQsMjggKzU1OCwxOSBAQAogCiAvKiBBIHN1YnJv dXRpbmUgb2YgcGFydGl0aW9uX3N0YWNrX3ZhcnMuICBUaGUgVU5JT04gcG9y dGlvbiBvZiBhIFVOSU9OL0ZJTkQKICAgIHBhcnRpdGlvbmluZyBhbGdvcml0 aG0uICBQYXJ0aXRpb25zIEEgYW5kIEIgYXJlIGtub3duIHRvIGJlIG5vbi1j b25mbGljdGluZy4KLSAgIE1lcmdlIHRoZW0gaW50byBhIHNpbmdsZSBwYXJ0 aXRpb24gQS4KKyAgIE1lcmdlIHRoZW0gaW50byBhIHNpbmdsZSBwYXJ0aXRp b24gQS4gICovCiAKLSAgIEF0IHRoZSBzYW1lIHRpbWUsIGFkZCBPRkZTRVQg dG8gYWxsIHZhcmlhYmxlcyBpbiBwYXJ0aXRpb24gQi4gIEF0IHRoZSBlbmQK LSAgIG9mIHRoZSBwYXJ0aXRpb25pbmcgcHJvY2VzcyB3ZSd2ZSBoYXZlIGEg bmljZSBibG9jayBlYXN5IHRvIGxheSBvdXQgd2l0aGluCi0gICB0aGUgc3Rh Y2sgZnJhbWUuICAqLwotCiBzdGF0aWMgdm9pZAotdW5pb25fc3RhY2tfdmFy cyAoc2l6ZV90IGEsIHNpemVfdCBiLCBIT1NUX1dJREVfSU5UIG9mZnNldCkK K3VuaW9uX3N0YWNrX3ZhcnMgKHNpemVfdCBhLCBzaXplX3QgYikKIHsKLSAg c2l6ZV90IGksIGxhc3Q7CiAgIHN0cnVjdCBzdGFja192YXIgKnZiID0gJnN0 YWNrX3ZhcnNbYl07CiAgIGJpdG1hcF9pdGVyYXRvciBiaTsKICAgdW5zaWdu ZWQgdTsKIAotICAvKiBVcGRhdGUgZWFjaCBlbGVtZW50IG9mIHBhcnRpdGlv biBCIHdpdGggdGhlIGdpdmVuIG9mZnNldCwKLSAgICAgYW5kIG1lcmdlIHRo ZW0gaW50byBwYXJ0aXRpb24gQS4gICovCi0gIGZvciAobGFzdCA9IGkgPSBi OyBpICE9IEVPQzsgbGFzdCA9IGksIGkgPSBzdGFja192YXJzW2ldLm5leHQp Ci0gICAgewotICAgICAgc3RhY2tfdmFyc1tpXS5vZmZzZXQgKz0gb2Zmc2V0 OwotICAgICAgc3RhY2tfdmFyc1tpXS5yZXByZXNlbnRhdGl2ZSA9IGE7Ci0g ICAgfQotICBzdGFja192YXJzW2xhc3RdLm5leHQgPSBzdGFja192YXJzW2Fd Lm5leHQ7CisgIGdjY19hc3NlcnQgKHN0YWNrX3ZhcnNbYl0ubmV4dCA9PSBF T0MpOworICAgLyogQWRkIEIgdG8gQSdzIHBhcnRpdGlvbi4gICovCisgIHN0 YWNrX3ZhcnNbYl0ubmV4dCA9IHN0YWNrX3ZhcnNbYV0ubmV4dDsKKyAgc3Rh Y2tfdmFyc1tiXS5yZXByZXNlbnRhdGl2ZSA9IGE7CiAgIHN0YWNrX3ZhcnNb YV0ubmV4dCA9IGI7CiAKICAgLyogVXBkYXRlIHRoZSByZXF1aXJlZCBhbGln bm1lbnQgb2YgcGFydGl0aW9uIEEgdG8gYWNjb3VudCBmb3IgQi4gICovCkBA IC01OTYsNyArNTgxLDggQEAKICAgaWYgKHZiLT5jb25mbGljdHMpCiAgICAg ewogICAgICAgRVhFQ1VURV9JRl9TRVRfSU5fQklUTUFQICh2Yi0+Y29uZmxp Y3RzLCAwLCB1LCBiaSkKLQlhZGRfc3RhY2tfdmFyX2NvbmZsaWN0IChhLCBz dGFja192YXJzW3VdLnJlcHJlc2VudGF0aXZlKTsKKyAgICAgICAgaWYgKHN0 YWNrX3ZhcnNbdV0ubmV4dCA9PSBFT0MgJiYgc3RhY2tfdmFyc1t1XS5yZXBy ZXNlbnRhdGl2ZSA9PSB1KQorICAgICAgICAgIGFkZF9zdGFja192YXJfY29u ZmxpY3QgKGEsIHUpOwogICAgICAgQklUTUFQX0ZSRUUgKHZiLT5jb25mbGlj dHMpOwogICAgIH0KIH0KQEAgLTYwNSwxNiArNTkxLDEzIEBACiAgICBwYXJ0 aXRpb25zIGNvbnN0cmFpbmVkIGJ5IHRoZSBpbnRlcmZlcmVuY2UgZ3JhcGgu ICBUaGUgb3ZlcmFsbAogICAgYWxnb3JpdGhtIHVzZWQgaXMgYXMgZm9sbG93 czoKIAotCVNvcnQgdGhlIG9iamVjdHMgYnkgc2l6ZS4KKwlTb3J0IHRoZSBv YmplY3RzIGJ5IHNpemUgaW4gZGVzY2VuZGluZyBvcmRlci4KIAlGb3IgZWFj aCBvYmplY3QgQSB7CiAJICBTID0gc2l6ZShBKQogCSAgTyA9IDAKIAkgIGxv b3AgewogCSAgICBMb29rIGZvciB0aGUgbGFyZ2VzdCBub24tY29uZmxpY3Rp bmcgb2JqZWN0IEIgd2l0aCBzaXplIDw9IFMuCiAJICAgIFVOSU9OIChBLCBC KQotCSAgICBvZmZzZXQoQikgPSBPCi0JICAgIE8gKz0gc2l6ZShCKQotCSAg ICBTIC09IHNpemUoQikKIAkgIH0KIAl9CiAqLwpAQCAtNjM2LDI0ICs2MTks MjMgQEAKICAgZm9yIChzaSA9IDA7IHNpIDwgbjsgKytzaSkKICAgICB7CiAg ICAgICBzaXplX3QgaSA9IHN0YWNrX3ZhcnNfc29ydGVkW3NpXTsKLSAgICAg IEhPU1RfV0lERV9JTlQgaXNpemUgPSBzdGFja192YXJzW2ldLnNpemU7CiAg ICAgICB1bnNpZ25lZCBpbnQgaWFsaWduID0gc3RhY2tfdmFyc1tpXS5hbGln bmI7Ci0gICAgICBIT1NUX1dJREVfSU5UIG9mZnNldCA9IDA7CiAKLSAgICAg IGZvciAoc2ogPSBzaTsgc2otLSA+IDA7ICkKKyAgICAgIC8qIElnbm9yZSBv YmplY3RzIHRoYXQgYXJlbid0IHBhcnRpdGlvbiByZXByZXNlbnRhdGl2ZXMu IElmIHdlCisgICAgICAgICBzZWUgYSB2YXIgdGhhdCBpcyBub3QgYSBwYXJ0 aXRpb24gcmVwcmVzZW50YXRpdmUsIGl0IG11c3QKKyAgICAgICAgIGhhdmUg YmVlbiBtZXJnZWQgZWFybGllci4gICovCisgICAgICBpZiAoc3RhY2tfdmFy c1tpXS5yZXByZXNlbnRhdGl2ZSAhPSBpKQorICAgICAgICBjb250aW51ZTsK KworICAgICAgZm9yIChzaiA9IHNpICsgMTsgc2ogPCBuOyArK3NqKQogCXsK IAkgIHNpemVfdCBqID0gc3RhY2tfdmFyc19zb3J0ZWRbc2pdOwotCSAgSE9T VF9XSURFX0lOVCBqc2l6ZSA9IHN0YWNrX3ZhcnNbal0uc2l6ZTsKIAkgIHVu c2lnbmVkIGludCBqYWxpZ24gPSBzdGFja192YXJzW2pdLmFsaWduYjsKIAog CSAgLyogSWdub3JlIG9iamVjdHMgdGhhdCBhcmVuJ3QgcGFydGl0aW9uIHJl cHJlc2VudGF0aXZlcy4gICovCiAJICBpZiAoc3RhY2tfdmFyc1tqXS5yZXBy ZXNlbnRhdGl2ZSAhPSBqKQogCSAgICBjb250aW51ZTsKIAotCSAgLyogSWdu b3JlIG9iamVjdHMgdG9vIGxhcmdlIGZvciB0aGUgcmVtYWluaW5nIHNwYWNl LiAgKi8KLQkgIGlmIChpc2l6ZSA8IGpzaXplKQotCSAgICBjb250aW51ZTsK LQogCSAgLyogSWdub3JlIGNvbmZsaWN0aW5nIG9iamVjdHMuICAqLwogCSAg aWYgKHN0YWNrX3Zhcl9jb25mbGljdF9wIChpLCBqKSkKIAkgICAgY29udGlu dWU7CkBAIC02NjQsMjUgKzY0Niw4IEBACiAJICAgICAgIT0gKGphbGlnbiAq IEJJVFNfUEVSX1VOSVQgPD0gTUFYX1NVUFBPUlRFRF9TVEFDS19BTElHTk1F TlQpKQogCSAgICBjb250aW51ZTsKIAotCSAgLyogUmVmaW5lIHRoZSByZW1h aW5pbmcgc3BhY2UgY2hlY2sgdG8gaW5jbHVkZSBhbGlnbm1lbnQuICAqLwot CSAgaWYgKG9mZnNldCAmIChqYWxpZ24gLSAxKSkKLQkgICAgewotCSAgICAg IEhPU1RfV0lERV9JTlQgdG9mZiA9IG9mZnNldDsKLQkgICAgICB0b2ZmICs9 IGphbGlnbiAtIDE7Ci0JICAgICAgdG9mZiAmPSAtKEhPU1RfV0lERV9JTlQp amFsaWduOwotCSAgICAgIGlmIChpc2l6ZSAtICh0b2ZmIC0gb2Zmc2V0KSA8 IGpzaXplKQotCQljb250aW51ZTsKLQotCSAgICAgIGlzaXplIC09IHRvZmYg LSBvZmZzZXQ7Ci0JICAgICAgb2Zmc2V0ID0gdG9mZjsKLQkgICAgfQotCiAJ ICAvKiBVTklPTiB0aGUgb2JqZWN0cywgcGxhY2luZyBKIGF0IE9GRlNFVC4g ICovCi0JICB1bmlvbl9zdGFja192YXJzIChpLCBqLCBvZmZzZXQpOwotCi0J ICBpc2l6ZSAtPSBqc2l6ZTsKLQkgIGlmIChpc2l6ZSA9PSAwKQotCSAgICBi cmVhazsKKwkgIHVuaW9uX3N0YWNrX3ZhcnMgKGksIGopOwogCX0KICAgICB9 CiAKQEAgLTcxMiw5ICs2NzcsOCBAQAogCXsKIAkgIGZwdXRjICgnXHQnLCBk dW1wX2ZpbGUpOwogCSAgcHJpbnRfZ2VuZXJpY19leHByIChkdW1wX2ZpbGUs IHN0YWNrX3ZhcnNbal0uZGVjbCwgZHVtcF9mbGFncyk7Ci0JICBmcHJpbnRm IChkdW1wX2ZpbGUsICIsIG9mZnNldCAiIEhPU1RfV0lERV9JTlRfUFJJTlRf REVDICJcbiIsCi0JCSAgIHN0YWNrX3ZhcnNbal0ub2Zmc2V0KTsKIAl9Cisg ICAgICBmcHV0YyAoJ1xuJywgZHVtcF9maWxlKTsKICAgICB9CiB9CiAKQEAg LTg2MywxMCArODI3LDkgQEAKIAkgcGFydGl0aW9uLiAgKi8KICAgICAgIGZv ciAoaiA9IGk7IGogIT0gRU9DOyBqID0gc3RhY2tfdmFyc1tqXS5uZXh0KQog CXsKLQkgIGdjY19hc3NlcnQgKHN0YWNrX3ZhcnNbal0ub2Zmc2V0IDw9IHN0 YWNrX3ZhcnNbaV0uc2l6ZSk7CiAJICBleHBhbmRfb25lX3N0YWNrX3Zhcl9h dCAoc3RhY2tfdmFyc1tqXS5kZWNsLAogCQkJCSAgIGJhc2UsIGJhc2VfYWxp Z24sCi0JCQkJICAgc3RhY2tfdmFyc1tqXS5vZmZzZXQgKyBvZmZzZXQpOwor CQkJCSAgIG9mZnNldCk7CiAJfQogICAgIH0KIAo= --000e0cd22ac8557b3204a13a875d--