From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 7486 invoked by alias); 20 Apr 2011 17:59:02 -0000 Received: (qmail 7472 invoked by uid 22791); 20 Apr 2011 17:59:00 -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; Wed, 20 Apr 2011 17:58:42 +0000 Received: from wpaz37.hot.corp.google.com (wpaz37.hot.corp.google.com [172.24.198.101]) by smtp-out.google.com with ESMTP id p3KHwfCs031670 for ; Wed, 20 Apr 2011 10:58:41 -0700 Received: from pzk10 (pzk10.prod.google.com [10.243.19.138]) by wpaz37.hot.corp.google.com with ESMTP id p3KHwSUe031832 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=NOT) for ; Wed, 20 Apr 2011 10:58:40 -0700 Received: by pzk10 with SMTP id 10so659989pzk.21 for ; Wed, 20 Apr 2011 10:58:39 -0700 (PDT) MIME-Version: 1.0 Received: by 10.142.9.36 with SMTP id 36mr4198284wfi.125.1303322319556; Wed, 20 Apr 2011 10:58:39 -0700 (PDT) Received: by 10.142.230.18 with HTTP; Wed, 20 Apr 2011 10:58:39 -0700 (PDT) In-Reply-To: References: Date: Wed, 20 Apr 2011 18:25: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=00504502ab61e292b904a15d5f96 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/msg01687.txt.bz2 --00504502ab61e292b904a15d5f96 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-length: 1907 On Wed, Apr 20, 2011 at 6:53 AM, Michael Matz wrote: > Hi, > > On Tue, 19 Apr 2011, Easwaran Raman wrote: > >> > That is correct but is also what the use of stack_vars[u].representati= ve >> > achieves alone, ... >> > >> >>=A0I am adding a check to that effect. >> > >> > ... without any check. >> > >> > @@ -596,7 +581,8 @@ >> > =A0 if (vb->conflicts) >> > =A0 =A0 { >> > =A0 =A0 =A0 EXECUTE_IF_SET_IN_BITMAP (vb->conflicts, 0, u, bi) >> > - =A0 =A0 =A0 add_stack_var_conflict (a, stack_vars[u].representative); >> > + =A0 =A0 =A0 =A0if (stack_vars[u].next =3D=3D EOC && stack_vars[u].re= presentative =3D=3D u) >> > + =A0 =A0 =A0 =A0 =A0add_stack_var_conflict (a, u); >> > =A0 =A0 =A0 BITMAP_FREE (vb->conflicts); >> > =A0 =A0 } >> > =A0} >> > >> > What's your objective with this change? =A0I find the original code cl= earer. >> >> Let us say we try to merge 'a' to 'b' and 'a' has conflicts with many >> members of an existing partition C. It is not necessary to add all >> those conflicts to 'b' since they will be never considered in the call >> to union_stack_vars. > > Right, that's why I was objecting to your initial change. a I agree that my initial change - adding a conflict with u - was wrong. >=A0The original > code (adding stack_vars[u].representative to the conflicts of A) made sure > the target conflict bitmap only got representatives added. In my above example, it is not even necessary to add a conflict between 'b' and representative(C) since it is already in a partition. But you're right - not adding that conflict doesn't actually reduce the size of bit maps. Reverting back to what was there originally. Thanks, Easwaran =A0That's why I > was asking why you changed this area at all. > >> I was motivated by your comment on bit-vector bloat to try this, but if >> this affects readability I'll happily revert back to what it was before. > > > Ciao, > Michael. --00504502ab61e292b904a15d5f96 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_gmqkfhy50 Content-length: 7703 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 IC02MDUsMTYgKzU5MCwxMyBAQAogICAgcGFydGl0aW9ucyBjb25zdHJhaW5l ZCBieSB0aGUgaW50ZXJmZXJlbmNlIGdyYXBoLiAgVGhlIG92ZXJhbGwKICAg IGFsZ29yaXRobSB1c2VkIGlzIGFzIGZvbGxvd3M6CiAKLQlTb3J0IHRoZSBv YmplY3RzIGJ5IHNpemUuCisJU29ydCB0aGUgb2JqZWN0cyBieSBzaXplIGlu IGRlc2NlbmRpbmcgb3JkZXIuCiAJRm9yIGVhY2ggb2JqZWN0IEEgewogCSAg UyA9IHNpemUoQSkKIAkgIE8gPSAwCiAJICBsb29wIHsKIAkgICAgTG9vayBm b3IgdGhlIGxhcmdlc3Qgbm9uLWNvbmZsaWN0aW5nIG9iamVjdCBCIHdpdGgg c2l6ZSA8PSBTLgogCSAgICBVTklPTiAoQSwgQikKLQkgICAgb2Zmc2V0KEIp ID0gTwotCSAgICBPICs9IHNpemUoQikKLQkgICAgUyAtPSBzaXplKEIpCiAJ ICB9CiAJfQogKi8KQEAgLTYzNiwyNCArNjE4LDIzIEBACiAgIGZvciAoc2kg PSAwOyBzaSA8IG47ICsrc2kpCiAgICAgewogICAgICAgc2l6ZV90IGkgPSBz dGFja192YXJzX3NvcnRlZFtzaV07Ci0gICAgICBIT1NUX1dJREVfSU5UIGlz aXplID0gc3RhY2tfdmFyc1tpXS5zaXplOwogICAgICAgdW5zaWduZWQgaW50 IGlhbGlnbiA9IHN0YWNrX3ZhcnNbaV0uYWxpZ25iOwotICAgICAgSE9TVF9X SURFX0lOVCBvZmZzZXQgPSAwOwogCi0gICAgICBmb3IgKHNqID0gc2k7IHNq LS0gPiAwOyApCisgICAgICAvKiBJZ25vcmUgb2JqZWN0cyB0aGF0IGFyZW4n dCBwYXJ0aXRpb24gcmVwcmVzZW50YXRpdmVzLiBJZiB3ZQorICAgICAgICAg c2VlIGEgdmFyIHRoYXQgaXMgbm90IGEgcGFydGl0aW9uIHJlcHJlc2VudGF0 aXZlLCBpdCBtdXN0CisgICAgICAgICBoYXZlIGJlZW4gbWVyZ2VkIGVhcmxp ZXIuICAqLworICAgICAgaWYgKHN0YWNrX3ZhcnNbaV0ucmVwcmVzZW50YXRp dmUgIT0gaSkKKyAgICAgICAgY29udGludWU7CisKKyAgICAgIGZvciAoc2og PSBzaSArIDE7IHNqIDwgbjsgKytzaikKIAl7CiAJICBzaXplX3QgaiA9IHN0 YWNrX3ZhcnNfc29ydGVkW3NqXTsKLQkgIEhPU1RfV0lERV9JTlQganNpemUg PSBzdGFja192YXJzW2pdLnNpemU7CiAJICB1bnNpZ25lZCBpbnQgamFsaWdu ID0gc3RhY2tfdmFyc1tqXS5hbGlnbmI7CiAKIAkgIC8qIElnbm9yZSBvYmpl Y3RzIHRoYXQgYXJlbid0IHBhcnRpdGlvbiByZXByZXNlbnRhdGl2ZXMuICAq LwogCSAgaWYgKHN0YWNrX3ZhcnNbal0ucmVwcmVzZW50YXRpdmUgIT0gaikK IAkgICAgY29udGludWU7CiAKLQkgIC8qIElnbm9yZSBvYmplY3RzIHRvbyBs YXJnZSBmb3IgdGhlIHJlbWFpbmluZyBzcGFjZS4gICovCi0JICBpZiAoaXNp emUgPCBqc2l6ZSkKLQkgICAgY29udGludWU7Ci0KIAkgIC8qIElnbm9yZSBj b25mbGljdGluZyBvYmplY3RzLiAgKi8KIAkgIGlmIChzdGFja192YXJfY29u ZmxpY3RfcCAoaSwgaikpCiAJICAgIGNvbnRpbnVlOwpAQCAtNjY0LDI1ICs2 NDUsOCBAQAogCSAgICAgICE9IChqYWxpZ24gKiBCSVRTX1BFUl9VTklUIDw9 IE1BWF9TVVBQT1JURURfU1RBQ0tfQUxJR05NRU5UKSkKIAkgICAgY29udGlu dWU7CiAKLQkgIC8qIFJlZmluZSB0aGUgcmVtYWluaW5nIHNwYWNlIGNoZWNr IHRvIGluY2x1ZGUgYWxpZ25tZW50LiAgKi8KLQkgIGlmIChvZmZzZXQgJiAo amFsaWduIC0gMSkpCi0JICAgIHsKLQkgICAgICBIT1NUX1dJREVfSU5UIHRv ZmYgPSBvZmZzZXQ7Ci0JICAgICAgdG9mZiArPSBqYWxpZ24gLSAxOwotCSAg ICAgIHRvZmYgJj0gLShIT1NUX1dJREVfSU5UKWphbGlnbjsKLQkgICAgICBp ZiAoaXNpemUgLSAodG9mZiAtIG9mZnNldCkgPCBqc2l6ZSkKLQkJY29udGlu dWU7Ci0KLQkgICAgICBpc2l6ZSAtPSB0b2ZmIC0gb2Zmc2V0OwotCSAgICAg IG9mZnNldCA9IHRvZmY7Ci0JICAgIH0KLQogCSAgLyogVU5JT04gdGhlIG9i amVjdHMsIHBsYWNpbmcgSiBhdCBPRkZTRVQuICAqLwotCSAgdW5pb25fc3Rh Y2tfdmFycyAoaSwgaiwgb2Zmc2V0KTsKLQotCSAgaXNpemUgLT0ganNpemU7 Ci0JICBpZiAoaXNpemUgPT0gMCkKLQkgICAgYnJlYWs7CisJICB1bmlvbl9z dGFja192YXJzIChpLCBqKTsKIAl9CiAgICAgfQogCkBAIC03MTIsOSArNjc2 LDggQEAKIAl7CiAJICBmcHV0YyAoJ1x0JywgZHVtcF9maWxlKTsKIAkgIHBy aW50X2dlbmVyaWNfZXhwciAoZHVtcF9maWxlLCBzdGFja192YXJzW2pdLmRl Y2wsIGR1bXBfZmxhZ3MpOwotCSAgZnByaW50ZiAoZHVtcF9maWxlLCAiLCBv ZmZzZXQgIiBIT1NUX1dJREVfSU5UX1BSSU5UX0RFQyAiXG4iLAotCQkgICBz dGFja192YXJzW2pdLm9mZnNldCk7CiAJfQorICAgICAgZnB1dGMgKCdcbics IGR1bXBfZmlsZSk7CiAgICAgfQogfQogCkBAIC04NjMsMTAgKzgyNiw5IEBA CiAJIHBhcnRpdGlvbi4gICovCiAgICAgICBmb3IgKGogPSBpOyBqICE9IEVP QzsgaiA9IHN0YWNrX3ZhcnNbal0ubmV4dCkKIAl7Ci0JICBnY2NfYXNzZXJ0 IChzdGFja192YXJzW2pdLm9mZnNldCA8PSBzdGFja192YXJzW2ldLnNpemUp OwogCSAgZXhwYW5kX29uZV9zdGFja192YXJfYXQgKHN0YWNrX3ZhcnNbal0u ZGVjbCwKIAkJCQkgICBiYXNlLCBiYXNlX2FsaWduLAotCQkJCSAgIHN0YWNr X3ZhcnNbal0ub2Zmc2V0ICsgb2Zmc2V0KTsKKwkJCQkgICBvZmZzZXQpOwog CX0KICAgICB9CiAK --00504502ab61e292b904a15d5f96--