From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 20958 invoked by alias); 9 Feb 2008 01:07:54 -0000 Received: (qmail 20949 invoked by uid 22791); 9 Feb 2008 01:07:53 -0000 X-Spam-Check-By: sourceware.org Received: from py-out-1112.google.com (HELO py-out-1112.google.com) (64.233.166.179) by sourceware.org (qpsmtpd/0.31) with ESMTP; Sat, 09 Feb 2008 01:07:34 +0000 Received: by py-out-1112.google.com with SMTP id d37so6988209pye.29 for ; Fri, 08 Feb 2008 17:07:30 -0800 (PST) Received: by 10.65.133.8 with SMTP id k8mr26085609qbn.58.1202519249111; Fri, 08 Feb 2008 17:07:29 -0800 (PST) Received: by 10.65.96.19 with HTTP; Fri, 8 Feb 2008 17:07:28 -0800 (PST) Message-ID: Date: Sat, 09 Feb 2008 01:26:00 -0000 From: "=?EUC-KR?B?U2VvbmdiYWUgUGFyayAoudq8urnoLCDa0+D328Yp?=" To: gcc-patches , "Kenneth Zadeck" , "Bonzini, Paolo" Subject: [PATCH] proper dataflow block visitation order MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_16154_19090692.1202519248971" 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: 2008-02/txt/msg00270.txt.bz2 ------=_Part_16154_19090692.1202519248971 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-Disposition: inline Content-length: 1697 This is an embarrassing mistake on my part that I only noticed this week, where we were using wrong block visit orders for dataflow analysis i.e. for forward problem, reverse postorder is the best known but we have been using postorder of inverted graph, and for backward problem, we should have used reverse postorder of inverted graph but we've been using postorder (of non-inverted). Two mistakes (of not reversing the postorder, and using wrong graph direction) canceled each other somewhat which made this mistake not noticeable for this long. The following patch reduces the total number of block visits during dataflow by about 4% building cc1 on i686, and it also reduces the block visits for the testcases in PR34400. While this is an overall win, there are cases where this patch increases the number of visits - I'll have to look at them further later, but clearly this is the right thing to do for now. Bootstrapped on i686 with c/c++ and no regression. While this is not exactly a regression, I'd like to commit this to 4.3 - as it's a fairly safe change (famous last word :). On the other hand, this is only a compile time fix and not a high-impact one at that, so I don't have very strong opinion on this. Seongbae 2008-02-08 Seongbae Park * df-core.c (reverse_array, df_compute_postoder): New functions. (rest_of_handle_df_initialize): Refactored to call df_compute_postorder. (df_analyze): Refactored to call df_compute_postorder. Pass proper ordering for forward and backward problems. (df_get_postorder): Return the correct block ordering. (df_compact_blocks): Call df_compute_postorder. ------=_Part_16154_19090692.1202519248971 Content-Type: text/x-patch; name=df-reverse-postorder-0208.patch Content-Transfer-Encoding: base64 X-Attachment-Id: f_fcfepgog0 Content-Disposition: attachment; filename=df-reverse-postorder-0208.patch Content-length: 5844 SW5kZXg6IGdjYy9kZi1jb3JlLmMKPT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PQot LS0gZ2NjL2RmLWNvcmUuYwkocmV2aXNpb24gMTMyMTg4KQorKysgZ2NjL2Rm LWNvcmUuYwkod29ya2luZyBjb3B5KQpAQCAtNzAzLDYgKzcwMyw0NiBAQCBk Zl9maW5pc2hfcGFzcyAoYm9vbCB2ZXJpZnkgQVRUUklCVVRFX1VOCiB9CiAK IAorLyogUHV0IGFsbCBlbGVtZW50cyBpbiB0aGUgcmV2ZXJzZSBvcmRlci4g ICovCisKK3N0YXRpYyB2b2lkCityZXZlcnNlX2FycmF5IChpbnQgbiwgaW50 ICphcnJheSkKK3sKKyAgaW50IGk7CisgIGZvciAoaSA9IDA7IGkgPCBuIC8g MjsgaSsrKQorICAgIHsKKyAgICAgIGludCB0ZW1wID0gYXJyYXlbaV07Cisg ICAgICBhcnJheVtpXSA9IGFycmF5W24gLSBpIC0gMV07CisgICAgICBhcnJh eVtuIC0gaSAtIDFdID0gdGVtcDsKKyAgICB9Cit9CisKKworLyogQ29tcHV0 ZSB0aGUgYmxvY2sgdmlzaXQgb3JkZXJzIAorICAgZm9yIGZvcndhcmQgYW5k IGJhY2t3YXJkIGRhdGFmbG93IHByb2JsZW1zLiAgKi8KKworc3RhdGljIHZv aWQKK2RmX2NvbXB1dGVfcG9zdG9yZGVyIChzdHJ1Y3QgZGYgKnRoaXNfZGYp Cit7CisgIGlmICh0aGlzX2RmLT5wb3N0b3JkZXIpCisgICAgZnJlZSAodGhp c19kZi0+cG9zdG9yZGVyKTsKKyAgaWYgKHRoaXNfZGYtPnBvc3RvcmRlcl9p bnZlcnRlZCkKKyAgICBmcmVlICh0aGlzX2RmLT5wb3N0b3JkZXJfaW52ZXJ0 ZWQpOworICB0aGlzX2RmLT5wb3N0b3JkZXIgPSBYTkVXVkVDIChpbnQsIGxh c3RfYmFzaWNfYmxvY2spOworICB0aGlzX2RmLT5wb3N0b3JkZXJfaW52ZXJ0 ZWQgPSBYTkVXVkVDIChpbnQsIGxhc3RfYmFzaWNfYmxvY2spOworICB0aGlz X2RmLT5uX2Jsb2NrcyAKKyAgICA9IHBvc3Rfb3JkZXJfY29tcHV0ZSAodGhp c19kZi0+cG9zdG9yZGVyLCB0cnVlLCB0cnVlKTsKKyAgdGhpc19kZi0+bl9i bG9ja3NfaW52ZXJ0ZWQgCisgICAgPSBpbnZlcnRlZF9wb3N0X29yZGVyX2Nv bXB1dGUgKHRoaXNfZGYtPnBvc3RvcmRlcl9pbnZlcnRlZCk7CisKKyAgLyog VGhlc2Ugc2hvdWxkIGJlIHRoZSBzYW1lLiAgKi8KKyAgZ2NjX2Fzc2VydCAo dGhpc19kZi0+bl9ibG9ja3MgPT0gdGhpc19kZi0+bl9ibG9ja3NfaW52ZXJ0 ZWQpOworCisgIC8qIE1ha2UgdGhlbSByZXZlcnNlIHBvc3RvcmRlci4gICov CisgIHJldmVyc2VfYXJyYXkgKHRoaXNfZGYtPm5fYmxvY2tzLCB0aGlzX2Rm LT5wb3N0b3JkZXIpOworICByZXZlcnNlX2FycmF5ICh0aGlzX2RmLT5uX2Js b2NrcywgdGhpc19kZi0+cG9zdG9yZGVyX2ludmVydGVkKTsKK30KKwogLyog U2V0IHVwIHRoZSBkYXRhZmxvdyBpbnN0YW5jZSBmb3IgdGhlIGVudGlyZSBi YWNrIGVuZC4gICovCiAKIHN0YXRpYyB1bnNpZ25lZCBpbnQKQEAgLTcyNiwx MSArNzY2LDcgQEAgcmVzdF9vZl9oYW5kbGVfZGZfaW5pdGlhbGl6ZSAodm9p ZCkKICAgaWYgKG9wdGltaXplID4gMSkKICAgICBkZl9saXZlX2FkZF9wcm9i bGVtICgpOwogCi0gIGRmLT5wb3N0b3JkZXIgPSBYTkVXVkVDIChpbnQsIGxh c3RfYmFzaWNfYmxvY2spOwotICBkZi0+cG9zdG9yZGVyX2ludmVydGVkID0g WE5FV1ZFQyAoaW50LCBsYXN0X2Jhc2ljX2Jsb2NrKTsKLSAgZGYtPm5fYmxv Y2tzID0gcG9zdF9vcmRlcl9jb21wdXRlIChkZi0+cG9zdG9yZGVyLCB0cnVl LCB0cnVlKTsKLSAgZGYtPm5fYmxvY2tzX2ludmVydGVkID0gaW52ZXJ0ZWRf cG9zdF9vcmRlcl9jb21wdXRlIChkZi0+cG9zdG9yZGVyX2ludmVydGVkKTsK LSAgZ2NjX2Fzc2VydCAoZGYtPm5fYmxvY2tzID09IGRmLT5uX2Jsb2Nrc19p bnZlcnRlZCk7CisgIGRmX2NvbXB1dGVfcG9zdG9yZGVyIChkZik7CiAKICAg ZGYtPmhhcmRfcmVnc19saXZlX2NvdW50ID0gWE5FV1ZFQyAodW5zaWduZWQg aW50LCBGSVJTVF9QU0VVRE9fUkVHSVNURVIpOwogICBtZW1zZXQgKGRmLT5o YXJkX3JlZ3NfbGl2ZV9jb3VudCwgMCwgCkBAIC0xMTg0LDYgKzEyMjAsOCBA QCBkZl9hbmFseXplX3Byb2JsZW0gKHN0cnVjdCBkYXRhZmxvdyAqZGZsCiB9 CiAKIAorCisKIC8qIEFuYWx5emUgZGF0YWZsb3cgaW5mbyBmb3IgdGhlIGJh c2ljIGJsb2NrcyBzcGVjaWZpZWQgYnkgdGhlIGJpdG1hcAogICAgQkxPQ0tT LCBvciBmb3IgdGhlIHdob2xlIENGRyBpZiBCTE9DS1MgaXMgemVyby4gICov CiAKQEAgLTExOTQsMTcgKzEyMzIsNyBAQCBkZl9hbmFseXplICh2b2lkKQog ICBib29sIGV2ZXJ5dGhpbmc7CiAgIGludCBpOwogICAKLSAgaWYgKGRmLT5w b3N0b3JkZXIpCi0gICAgZnJlZSAoZGYtPnBvc3RvcmRlcik7Ci0gIGlmIChk Zi0+cG9zdG9yZGVyX2ludmVydGVkKQotICAgIGZyZWUgKGRmLT5wb3N0b3Jk ZXJfaW52ZXJ0ZWQpOwotICBkZi0+cG9zdG9yZGVyID0gWE5FV1ZFQyAoaW50 LCBsYXN0X2Jhc2ljX2Jsb2NrKTsKLSAgZGYtPnBvc3RvcmRlcl9pbnZlcnRl ZCA9IFhORVdWRUMgKGludCwgbGFzdF9iYXNpY19ibG9jayk7Ci0gIGRmLT5u X2Jsb2NrcyA9IHBvc3Rfb3JkZXJfY29tcHV0ZSAoZGYtPnBvc3RvcmRlciwg dHJ1ZSwgdHJ1ZSk7Ci0gIGRmLT5uX2Jsb2Nrc19pbnZlcnRlZCA9IGludmVy dGVkX3Bvc3Rfb3JkZXJfY29tcHV0ZSAoZGYtPnBvc3RvcmRlcl9pbnZlcnRl ZCk7Ci0KLSAgLyogVGhlc2Ugc2hvdWxkIGJlIHRoZSBzYW1lLiAgKi8KLSAg Z2NjX2Fzc2VydCAoZGYtPm5fYmxvY2tzID09IGRmLT5uX2Jsb2Nrc19pbnZl cnRlZCk7CisgIGRmX2NvbXB1dGVfcG9zdG9yZGVyIChkZik7CiAKICAgLyog V2UgbmVlZCB0byBkbyB0aGlzIGJlZm9yZSB0aGUgZGZfdmVyaWZ5X2FsbCBi ZWNhdXNlIHRoaXMgaXMKICAgICAgbm90IGtlcHQgaW5jcmVtZW50YWxseSB1 cCB0byBkYXRlLiAgKi8KQEAgLTEyNTgsMTIgKzEyODYsMTIgQEAgZGZfYW5h bHl6ZSAodm9pZCkKICAgICAgICAgICBpZiAoZGZsb3ctPnByb2JsZW0tPmRp ciA9PSBERl9GT1JXQVJEKQogICAgICAgICAgICAgZGZfYW5hbHl6ZV9wcm9i bGVtIChkZmxvdywKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAg ZGYtPmJsb2Nrc190b19hbmFseXplLAotICAgICAgICAgICAgICAgICAgICAg ICAgICAgICAgICBkZi0+cG9zdG9yZGVyX2ludmVydGVkLAorICAgICAgICAg ICAgICAgICAgICAgICAgICAgICAgICBkZi0+cG9zdG9yZGVyLAogICAgICAg ICAgICAgICAgICAgICAgICAgICAgICAgICBkZi0+bl9ibG9ja3NfaW52ZXJ0 ZWQpOwogICAgICAgICAgIGVsc2UKICAgICAgICAgICAgIGRmX2FuYWx5emVf cHJvYmxlbSAoZGZsb3csCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAg ICAgIGRmLT5ibG9ja3NfdG9fYW5hbHl6ZSwKLSAgICAgICAgICAgICAgICAg ICAgICAgICAgICAgICAgZGYtPnBvc3RvcmRlciwKKyAgICAgICAgICAgICAg ICAgICAgICAgICAgICAgICAgZGYtPnBvc3RvcmRlcl9pbnZlcnRlZCwKICAg ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZGYtPm5fYmxvY2tzKTsK ICAgICAgICAgfQogICAgIH0KQEAgLTEzMDUsMTUgKzEzMzMsMTMgQEAgZGZf Z2V0X25fYmxvY2tzIChlbnVtIGRmX2Zsb3dfZGlyIGRpcikKIGludCAqCiBk Zl9nZXRfcG9zdG9yZGVyIChlbnVtIGRmX2Zsb3dfZGlyIGRpcikKIHsKLSAg Z2NjX2Fzc2VydCAoZGlyICE9IERGX05PTkUpOwotCiAgIGlmIChkaXIgPT0g REZfRk9SV0FSRCkKICAgICB7Ci0gICAgICBnY2NfYXNzZXJ0IChkZi0+cG9z dG9yZGVyX2ludmVydGVkKTsKLSAgICAgIHJldHVybiBkZi0+cG9zdG9yZGVy X2ludmVydGVkOworICAgICAgZ2NjX2Fzc2VydCAoZGYtPnBvc3RvcmRlcik7 CisgICAgICByZXR1cm4gZGYtPnBvc3RvcmRlcjsKICAgICB9Ci0gIGdjY19h c3NlcnQgKGRmLT5wb3N0b3JkZXIpOwotICByZXR1cm4gZGYtPnBvc3RvcmRl cjsKKyAgZ2NjX2Fzc2VydCAoZGYtPnBvc3RvcmRlcl9pbnZlcnRlZCk7Cisg IHJldHVybiBkZi0+cG9zdG9yZGVyX2ludmVydGVkOwogfQogCiBzdGF0aWMg c3RydWN0IGRmX3Byb2JsZW0gdXNlcl9wcm9ibGVtOyAKQEAgLTE1MzksNiAr MTU2NSw5IEBAIGRmX2NvbXBhY3RfYmxvY2tzICh2b2lkKQogICBmb3IgKDsg aSA8IGxhc3RfYmFzaWNfYmxvY2s7IGkrKykKICAgICBTRVRfQkFTSUNfQkxP Q0sgKGksIE5VTEwpOwogCisgIC8qIFJlY29tcHV0ZSB0aGUgYmxvY2sgdmlz aXQgb3JkZXIuICovCisgIGRmX2NvbXB1dGVfcG9zdG9yZGVyIChkZik7CisK ICNpZmRlZiBERl9ERUJVR19DRkcKICAgaWYgKCFkZl9sci0+c29sdXRpb25z X2RpcnR5KQogICAgIGRmX3NldF9jbGVhbl9jZmcgKCk7Cg== ------=_Part_16154_19090692.1202519248971--