From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 23374 invoked by alias); 28 Jun 2009 10:30:20 -0000 Received: (qmail 23363 invoked by uid 22791); 28 Jun 2009 10:30:19 -0000 X-SWARE-Spam-Status: No, hits=0.9 required=5.0 tests=BAYES_40,URIBL_RHS_DOB X-Spam-Check-By: sourceware.org Received: from mail.uni-paderborn.de (HELO mail.uni-paderborn.de) (131.234.142.9) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Sun, 28 Jun 2009 10:30:12 +0000 Received: from d90-134-186-11.cust.tele2.de ([90.134.186.11] helo=[192.168.178.111]) by mail.uni-paderborn.de with esmtpsa (TLS-1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.63 spheron) id 1MKreB-0004Ab-Iu; Sun, 28 Jun 2009 12:30:09 +0200 Message-ID: <4A47462E.1080402@uni-paderborn.de> Date: Sun, 28 Jun 2009 12:37:00 -0000 From: Michael Kruse Reply-To: reply@meinersbur.de User-Agent: Thunderbird 2.0.0.22 (Windows/20090605) MIME-Version: 1.0 To: gcc@gcc.gnu.org Subject: Register Pressure in Instruction Level Parallelism Content-Type: multipart/signed; protocol="application/x-pkcs7-signature"; micalg=sha1; boundary="------------ms020400020707080004000706" X-IMT-Spam-Score: 0.0 () X-IMT-Authenticated-Sender: uid=meinert,ou=People,o=upb,c=de Mailing-List: contact gcc-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-owner@gcc.gnu.org X-SW-Source: 2009-06/txt/msg00651.txt.bz2 This is a cryptographically signed message in MIME format. --------------ms020400020707080004000706 Content-Type: text/plain; charset=ISO-8859-15; format=flowed Content-Transfer-Encoding: 7bit Content-length: 2463 Hello GCC developers, I am going to write a Master's Thesis about instruction scheduling based on the technique presented in [1]. This will also include a implementation. The basic idea is to have an additional pass on the data dependency graph before instruction scheduling and register allocation takes place. It estimates the minimal (register sufficiency) and maximal number of registers (register saturation) required by schedules based on that graph. If the register sufficiency is higher than the physical number of registers, spill code is added to the graph. If the register saturation is higher than the physical number of registers, artificial dependencies are added to the graph, such that the instruction scheduler is forced to generate a schedule with less registers. The aim is that the instruction scheduler can focus on the optimal arrangement of instructions to exploit a maximal amount of instruction level parallelism. [1] also suggests heuristics for all these problems. According to the author, these are "nearly optimal" in practice. The heuristics for estimating register sufficiency and saturation are both optimistic, meaning that it might still be necessary to add more spill code to the final code. Hence, this this technique is just an optimization pass and doesn't replace existing register allocation or instruction scheduling passes. [1] also has a part about loop scheduling, but my thesis will be about basic blocks only. See [2] for an presentation of this technique. So, now my questions: How much do you think could this could improve compiled code speed? Would the current GCC/YARA benefit from such an optimization pass at all? What are the chances that this could get into the main GCC tree if it shows up to be an improvement? There has been a short discussion on this mailing list already [3] some years ago (Note if you read this: intLP has been used to compare the heuristic to the optimal result only). To my knowledge, there hasn't been any more on this topic yet (anywhere). I'd prefer to implement this for the gcc, but my advisor wants me to do it for the university's own compiler. Therefore I could also need arguments why to do it for the GCC. Regards, Michael Kruse [1] http://www.prism.uvsq.fr/~touati/thesis.html [2] http://tel.archives-ouvertes.fr/docs/00/04/72/88/ANNEX/tel-00007405.ppt [3] http://gcc.gnu.org/ml/gcc/2002-07/msg00565.html -- Tardyzentrismus verboten! --------------ms020400020707080004000706 Content-Type: application/x-pkcs7-signature; name="smime.p7s" Content-Transfer-Encoding: base64 Content-Disposition: attachment; filename="smime.p7s" Content-Description: S/MIME Cryptographic Signature Content-length: 5966 MIAGCSqGSIb3DQEHAqCAMIACAQExCzAJBgUrDgMCGgUAMIAGCSqGSIb3DQEH AQAAoIINjzCCAz8wggKooAMCAQICAQ0wDQYJKoZIhvcNAQEFBQAwgdExCzAJ BgNVBAYTAlpBMRUwEwYDVQQIEwxXZXN0ZXJuIENhcGUxEjAQBgNVBAcTCUNh cGUgVG93bjEaMBgGA1UEChMRVGhhd3RlIENvbnN1bHRpbmcxKDAmBgNVBAsT H0NlcnRpZmljYXRpb24gU2VydmljZXMgRGl2aXNpb24xJDAiBgNVBAMTG1Ro YXd0ZSBQZXJzb25hbCBGcmVlbWFpbCBDQTErMCkGCSqGSIb3DQEJARYccGVy c29uYWwtZnJlZW1haWxAdGhhd3RlLmNvbTAeFw0wMzA3MTcwMDAwMDBaFw0x MzA3MTYyMzU5NTlaMGIxCzAJBgNVBAYTAlpBMSUwIwYDVQQKExxUaGF3dGUg Q29uc3VsdGluZyAoUHR5KSBMdGQuMSwwKgYDVQQDEyNUaGF3dGUgUGVyc29u YWwgRnJlZW1haWwgSXNzdWluZyBDQTCBnzANBgkqhkiG9w0BAQEFAAOBjQAw gYkCgYEAxKY8VXNV+065yplaHmjAdQRwnd/p/6Me7L3N9VvyGna9fww6YfK/ Uc4B1OVQCjDXAmNaLIkVcI7dyfArhVqqP3FWy688Cwfn8R+RNiQqE88r1fOC dz0Dviv+uxg+B79AgAJk16emu59l0cUqVIUPSAR/p7bRPGEEQB5kGXJgt/sC AwEAAaOBlDCBkTASBgNVHRMBAf8ECDAGAQH/AgEAMEMGA1UdHwQ8MDowOKA2 oDSGMmh0dHA6Ly9jcmwudGhhd3RlLmNvbS9UaGF3dGVQZXJzb25hbEZyZWVt YWlsQ0EuY3JsMAsGA1UdDwQEAwIBBjApBgNVHREEIjAgpB4wHDEaMBgGA1UE AxMRUHJpdmF0ZUxhYmVsMi0xMzgwDQYJKoZIhvcNAQEFBQADgYEASIzRUIPq Cy7MDaNmrGcPf6+svsIXoUOWlJ1/TCG4+DYfqi2fNi/A9BxQIJNwPP2t4WFi w9k6GX6EsZkbAMUaC4J0niVQlGLH2ydxVyWN3amcOY6MIE9lX5Xa9/eH1sYI Tq726jTlEBpbNU1341YheILcIRk13iSx0x1G/11fZU8wggUiMIIEi6ADAgEC AhABlkfcqgBx7l/30QjQrmHwMA0GCSqGSIb3DQEBBQUAMGIxCzAJBgNVBAYT AlpBMSUwIwYDVQQKExxUaGF3dGUgQ29uc3VsdGluZyAoUHR5KSBMdGQuMSww KgYDVQQDEyNUaGF3dGUgUGVyc29uYWwgRnJlZW1haWwgSXNzdWluZyBDQTAe Fw0wODEyMTYyMzIyNThaFw0wOTEyMTYyMzIyNThaMIIBsjEOMAwGA1UEBBMF S3J1c2UxEDAOBgNVBCoTB01pY2hhZWwxFjAUBgNVBAMTDU1pY2hhZWwgS3J1 c2UxKTAnBgkqhkiG9w0BCQEWGk1pY2hhZWxLcnVzZUBNZWluZXJzYnVyLmRl MSIwIAYJKoZIhvcNAQkBFhNyZXBseUBtZWluZXJzYnVyLmRlMSIwIAYJKoZI hvcNAQkBFhNNaWNoYWVsS3J1c2VAV2ViLmRlMScwJQYJKoZIhvcNAQkBFhht ZWluZXJ0QHVuaS1wYWRlcmJvcm4uZGUxKDAmBgkqhkiG9w0BCQEWGW1laW5l cnNidXJAZ29vZ2xlbWFpbC5jb20xIzAhBgkqhkiG9w0BCQEWFE1laW5lcnNi dXJAZ21haWwuY29tMScwJQYJKoZIhvcNAQkBFhhNZWluZXJzYnVyQE1laW5l cnNidXIuZGUxITAfBgkqhkiG9w0BCQEWEm1rcnVzZUB1dGFzLmVkdS5hdTEd MBsGCSqGSIb3DQEJARYObWVpbmVydEB1cGIuZGUxIDAeBgkqhkiG9w0BCQEW EWJjY0BtZWluZXJzYnVyLmRlMIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIB CgKCAQEAt2ONiWmDiRnsU9pfSho6+6D1DG+egKhwPcofcdgl/MgriZUnZ7nk xeTP1FLZF7Io+Nm8vLB9O4HpDKhiOjXA6hPpWiq+YEsl2urEEEr4eiKccC+C mIf0UlGVnVWXrt5yH3ia8AH8EZrYQV5THtg0JV6maQwkdbh8iEJ8nYh20fzy Jg4vRHAcr1YNNYW9m3ODFvQNFzAAOU0Kv5HGZcMCEJQv/+DQLCPkizWXpl8l XOp2DhqK3vSPaQWu44oUk7Z8nFtCkNEREoKaYB9iivh+tFHT1+YfpYYzaoU3 N+gryqzrs63deKmiH0cdn+wDIgnWfpwgWH9iXYPypgxuf1azzwIDAQABo4IB ATCB/jCB7QYDVR0RBIHlMIHigRpNaWNoYWVsS3J1c2VATWVpbmVyc2J1ci5k ZYETcmVwbHlAbWVpbmVyc2J1ci5kZYETTWljaGFlbEtydXNlQFdlYi5kZYEY bWVpbmVydEB1bmktcGFkZXJib3JuLmRlgRltZWluZXJzYnVyQGdvb2dsZW1h aWwuY29tgRRNZWluZXJzYnVyQGdtYWlsLmNvbYEYTWVpbmVyc2J1ckBNZWlu ZXJzYnVyLmRlgRJta3J1c2VAdXRhcy5lZHUuYXWBDm1laW5lcnRAdXBiLmRl gRFiY2NAbWVpbmVyc2J1ci5kZTAMBgNVHRMBAf8EAjAAMA0GCSqGSIb3DQEB BQUAA4GBAAaqGNzCuVZPwrtax+FjxNV0Gvp+1mFysNcbXphD5aAmygKutey9 rIxSgYXSZeixBi93JzNAhY3XgFqDgLAgwJjsqmiI+m2HRDqn4f7WX+cC2Oy5 9teS93TH7mt1e8wd5zRXfnEvqkCf7gfBs80Ja2v0CxIpeWDWNRoqzfaiDEGt MIIFIjCCBIugAwIBAgIQAZZH3KoAce5f99EI0K5h8DANBgkqhkiG9w0BAQUF ADBiMQswCQYDVQQGEwJaQTElMCMGA1UEChMcVGhhd3RlIENvbnN1bHRpbmcg KFB0eSkgTHRkLjEsMCoGA1UEAxMjVGhhd3RlIFBlcnNvbmFsIEZyZWVtYWls IElzc3VpbmcgQ0EwHhcNMDgxMjE2MjMyMjU4WhcNMDkxMjE2MjMyMjU4WjCC AbIxDjAMBgNVBAQTBUtydXNlMRAwDgYDVQQqEwdNaWNoYWVsMRYwFAYDVQQD Ew1NaWNoYWVsIEtydXNlMSkwJwYJKoZIhvcNAQkBFhpNaWNoYWVsS3J1c2VA TWVpbmVyc2J1ci5kZTEiMCAGCSqGSIb3DQEJARYTcmVwbHlAbWVpbmVyc2J1 ci5kZTEiMCAGCSqGSIb3DQEJARYTTWljaGFlbEtydXNlQFdlYi5kZTEnMCUG CSqGSIb3DQEJARYYbWVpbmVydEB1bmktcGFkZXJib3JuLmRlMSgwJgYJKoZI hvcNAQkBFhltZWluZXJzYnVyQGdvb2dsZW1haWwuY29tMSMwIQYJKoZIhvcN AQkBFhRNZWluZXJzYnVyQGdtYWlsLmNvbTEnMCUGCSqGSIb3DQEJARYYTWVp bmVyc2J1ckBNZWluZXJzYnVyLmRlMSEwHwYJKoZIhvcNAQkBFhJta3J1c2VA dXRhcy5lZHUuYXUxHTAbBgkqhkiG9w0BCQEWDm1laW5lcnRAdXBiLmRlMSAw HgYJKoZIhvcNAQkBFhFiY2NAbWVpbmVyc2J1ci5kZTCCASIwDQYJKoZIhvcN AQEBBQADggEPADCCAQoCggEBALdjjYlpg4kZ7FPaX0oaOvug9QxvnoCocD3K H3HYJfzIK4mVJ2e55MXkz9RS2ReyKPjZvLywfTuB6QyoYjo1wOoT6VoqvmBL JdrqxBBK+HoinHAvgpiH9FJRlZ1Vl67ech94mvAB/BGa2EFeUx7YNCVepmkM JHW4fIhCfJ2IdtH88iYOL0RwHK9WDTWFvZtzgxb0DRcwADlNCr+RxmXDAhCU L//g0Cwj5Is1l6ZfJVzqdg4ait70j2kFruOKFJO2fJxbQpDRERKCmmAfYor4 frRR09fmH6WGM2qFNzfoK8qs67Ot3Xipoh9HHZ/sAyIJ1n6cIFh/Yl2D8qYM bn9Ws88CAwEAAaOCAQEwgf4wge0GA1UdEQSB5TCB4oEaTWljaGFlbEtydXNl QE1laW5lcnNidXIuZGWBE3JlcGx5QG1laW5lcnNidXIuZGWBE01pY2hhZWxL cnVzZUBXZWIuZGWBGG1laW5lcnRAdW5pLXBhZGVyYm9ybi5kZYEZbWVpbmVy c2J1ckBnb29nbGVtYWlsLmNvbYEUTWVpbmVyc2J1ckBnbWFpbC5jb22BGE1l aW5lcnNidXJATWVpbmVyc2J1ci5kZYESbWtydXNlQHV0YXMuZWR1LmF1gQ5t ZWluZXJ0QHVwYi5kZYERYmNjQG1laW5lcnNidXIuZGUwDAYDVR0TAQH/BAIw ADANBgkqhkiG9w0BAQUFAAOBgQAGqhjcwrlWT8K7WsfhY8TVdBr6ftZhcrDX G16YQ+WgJsoCrrXsvayMUoGF0mXosQYvdyczQIWN14Bag4CwIMCY7KpoiPpt h0Q6p+H+1l/nAtjsufbXkvd0x+5rdXvMHec0V35xL6pAn+4HwbPNCWtr9AsS KXlg1jUaKs32ogxBrTGCA2QwggNgAgEBMHYwYjELMAkGA1UEBhMCWkExJTAj BgNVBAoTHFRoYXd0ZSBDb25zdWx0aW5nIChQdHkpIEx0ZC4xLDAqBgNVBAMT I1RoYXd0ZSBQZXJzb25hbCBGcmVlbWFpbCBJc3N1aW5nIENBAhABlkfcqgBx 7l/30QjQrmHwMAkGBSsOAwIaBQCgggHDMBgGCSqGSIb3DQEJAzELBgkqhkiG 9w0BBwEwHAYJKoZIhvcNAQkFMQ8XDTA5MDYyODEwMzAwNlowIwYJKoZIhvcN AQkEMRYEFMqbHjo/FOIax9E1JIiJWoe1kAFiMFIGCSqGSIb3DQEJDzFFMEMw CgYIKoZIhvcNAwcwDgYIKoZIhvcNAwICAgCAMA0GCCqGSIb3DQMCAgFAMAcG BSsOAwIHMA0GCCqGSIb3DQMCAgEoMIGFBgkrBgEEAYI3EAQxeDB2MGIxCzAJ BgNVBAYTAlpBMSUwIwYDVQQKExxUaGF3dGUgQ29uc3VsdGluZyAoUHR5KSBM dGQuMSwwKgYDVQQDEyNUaGF3dGUgUGVyc29uYWwgRnJlZW1haWwgSXNzdWlu ZyBDQQIQAZZH3KoAce5f99EI0K5h8DCBhwYLKoZIhvcNAQkQAgsxeKB2MGIx CzAJBgNVBAYTAlpBMSUwIwYDVQQKExxUaGF3dGUgQ29uc3VsdGluZyAoUHR5 KSBMdGQuMSwwKgYDVQQDEyNUaGF3dGUgUGVyc29uYWwgRnJlZW1haWwgSXNz dWluZyBDQQIQAZZH3KoAce5f99EI0K5h8DANBgkqhkiG9w0BAQEFAASCAQB3 gBRQQfFNH+ujqC//6ZWrGSqVIZZGMBp8c+iBitzR4D7/wi5Jk9L7LkL7CmjM hXB2EiMs5FUtYTnH1corzpsszt7UeDXSa50lJ2vgBrOt5XeP3Ew01aNbLgr5 xyHZeIb/1y0AsTK7nAkQ7h+VtNqy63tNZselITlfYUYgbg3EXbHIEPP94/++ Of1aCMkcQTNJPzBI+g6qwS+phUEGRFeV3izPxbcAIZKfD2oNJE/ifSiEh+8B fnXo/i5hi6d3FtI0esQ5qJY1csbxs3fWfhAnsR9zPw6Iz7qOKKGmkkvYL2AK dI22J0GSm8iv8gLFRtGGaZeflLQq/kt0h59OdTjsAAAAAAAA --------------ms020400020707080004000706--