{"action":"created","issue":{"url":"https://api.github.com/repos/dotnet/coreclr/issues/1218","labels_url":"https://api.github.com/repos/dotnet/coreclr/issues/1218/labels{/name}","comments_url":"https://api.github.com/repos/dotnet/coreclr/issues/1218/comments","events_url":"https://api.github.com/repos/dotnet/coreclr/issues/1218/events","html_url":"https://github.com/dotnet/coreclr/issues/1218","id":93857540,"number":1218,"title":"Feature - loop-invariant code motion (hoisting) optimization","user":{"login":"jasonwilliams200OK","id":2031765,"avatar_url":"https://avatars.githubusercontent.com/u/2031765?v=3","gravatar_id":"","url":"https://api.github.com/users/jasonwilliams200OK","html_url":"https://github.com/jasonwilliams200OK","followers_url":"https://api.github.com/users/jasonwilliams200OK/followers","following_url":"https://api.github.com/users/jasonwilliams200OK/following{/other_user}","gists_url":"https://api.github.com/users/jasonwilliams200OK/gists{/gist_id}","starred_url":"https://api.github.com/users/jasonwilliams200OK/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jasonwilliams200OK/subscriptions","organizations_url":"https://api.github.com/users/jasonwilliams200OK/orgs","repos_url":"https://api.github.com/users/jasonwilliams200OK/repos","events_url":"https://api.github.com/users/jasonwilliams200OK/events{/privacy}","received_events_url":"https://api.github.com/users/jasonwilliams200OK/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":13,"created_at":"2015-07-08T18:23:47Z","updated_at":"2015-07-12T00:58:32Z","closed_at":null,"body":"Source: http://stackoverflow.com/a/11303693/863980\r\n\r\nFrom the link above it is evident that the following two methods are logically equal, due to [Loop-Invariant code motion](https://en.wikipedia.org/wiki/Loop-invariant_code_motion):\r\n\r\n```c#\r\npublic static void UnHoisted(ref int[] data, int arraySize)\r\n{\r\n    long sum = 0;\r\n\r\n    for (int i = 0; i < 100000; ++i)\r\n    {\r\n        for (int j = 0; j < arraySize; ++j)\r\n        {\r\n            if (data[j] >= 128)\r\n                sum += data[j];\r\n        }\r\n    }\r\n}\r\n```\r\nand\r\n```c#\r\npublic static void Hoisted(ref int[] data, int arraySize)\r\n{\r\n    long sum = 0;\r\n\r\n    for (int j = 0; j < arraySize; ++j)\r\n    {\r\n        if (data[j] >= 128)\r\n        {\r\n            sum += data[j] * 100000;\r\n        }\r\n    }\r\n}\r\n```\r\n\r\nThe driver (`Main`) method looks like:\r\n\r\n```c#\r\npublic static void Main (string[] args)\r\n{\r\n    const int arraySize = 32768;\r\n    int[] data = new int[arraySize];\r\n    Random random = new Random();\r\n\r\n    for (int c = 0; c < arraySize; ++c)\r\n        data[c] = random.Next() % 256;\r\n\r\n    UnHoisted(ref data, arraySize);\r\n    // Hoisted(ref data, arraySize);\r\n}\r\n```\r\n\r\nDiffing the produced disasm of `UnHoisted` and `Hoisted` methods results in:\r\n\r\n```diff\r\ndiff --git a/c:/temp/UnHoisted.txt b/c:/temp/Hoisted.txt\r\nindex 9f25a6b..e4cbf57 100644\r\n--- a/c:/temp/UnHoisted.txt\r\n+++ b/c:/temp/Hoisted.txt\r\n@@ -1,79 +1,66 @@\r\n-; Assembly listing for method Program:UnHoisted(byref,int)\r\n+; Assembly listing for method Program:Hoisted(byref,int)\r\n ; Emitting BLENDED_CODE for X64 CPU with AVX\r\n ; optimized code\r\n ; rsp based frame\r\n ; fully interruptible\r\n ; Final local variable assignments\r\n ;\r\n-;  V00 arg0         [V00,T04] (  4,  18  )   byref  ->  rcx        \r\n-;  V01 arg1         [V01,T05] (  3,  18  )     int  ->  rdx        \r\n-;  V02 loc0         [V02,T06] (  3,  17  )    long  ->  rax        \r\n-;  V03 loc1         [V03,T07] (  4,  13  )     int  ->   r8        \r\n-;  V04 loc2         [V04,T00] (  8,  66  )     int  ->  r10        \r\n-;  V05 loc3         [V05,T01] (  6,  64  )    bool  ->   r9        \r\n-;  V06 tmp0         [V06,T02] (  3,  48  )     ref  ->   r9        \r\n-;  V07 tmp1         [V07,T03] (  3,  48  )     ref  ->   r9        \r\n-;  V08 OutArgs      [V08    ] (  1,   1  )  lclBlk (32) [rsp+0x00]  \r\n+;  V00 arg0         [V00,T05] (  4,   6  )   byref  ->  rcx        \r\n+;  V01 arg1         [V01,T04] (  3,  10  )     int  ->  rdx        \r\n+;  V02 loc0         [V02,T06] (  3,   5  )    long  ->  rax        \r\n+;  V03 loc1         [V03,T00] (  8,  21  )     int  ->   r8        \r\n+;  V04 loc2         [V04,T01] (  4,  20  )    bool  ->   r9        \r\n+;  V05 tmp0         [V05,T02] (  3,  12  )     ref  ->   r9        \r\n+;  V06 tmp1         [V06,T03] (  3,  12  )     ref  ->   r9        \r\n+;  V07 OutArgs      [V07    ] (  1,   1  )  lclBlk (32) [rsp+0x00]  \r\n ;\r\n ; Lcl frame size = 40\r\n \r\n-G_M4700_IG01:\r\n+G_M9639_IG01:\r\n        4883EC28             sub      rsp, 40\r\n \r\n-G_M4700_IG02:\r\n+G_M9639_IG02:\r\n        33C0                 xor      rax, rax\r\n        4533C0               xor      r8d, r8d\r\n-       EB5D                 jmp      SHORT G_M4700_IG07\r\n+       EB49                 jmp      SHORT G_M9639_IG05\r\n \r\n-G_M4700_IG03:\r\n-       4533D2               xor      r10d, r10d\r\n-       EB45                 jmp      SHORT G_M4700_IG06\r\n-\r\n-G_M4700_IG04:\r\n+G_M9639_IG03:\r\n        4C8B09               mov      r9, gword ptr [rcx]\r\n-       458B5908             mov      r11d, dword ptr [r9+8]\r\n-       453BD3               cmp      r10d, r11d\r\n-       7365                 jae      SHORT G_M4700_IG09\r\n-       4D63DA               movsxd   r11d, r10d\r\n-       43817C991080000000   cmp      dword ptr [r9+4*r11+16], 128\r\n+       458B5108             mov      r10d, dword ptr [r9+8]\r\n+       453BC2               cmp      r8d, r10d\r\n+       7352                 jae      SHORT G_M9639_IG07\r\n+       4D63D0               movsxd   r10d, r8d\r\n+       43817C911080000000   cmp      dword ptr [r9+4*r10+16], 128\r\n        410F9CC1             setl     r9b\r\n        450FB6C9             movzx    r9, r9b\r\n        4585C9               test     r9d, r9d\r\n-       751D                 jne      SHORT G_M4700_IG05\r\n+       7521                 jne      SHORT G_M9639_IG04\r\n        4C8B09               mov      r9, gword ptr [rcx]\r\n-       458B5908             mov      r11d, dword ptr [r9+8]\r\n-       453BD3               cmp      r10d, r11d\r\n-       7340                 jae      SHORT G_M4700_IG09\r\n-       4D63DA               movsxd   r11d, r10d\r\n-       478B4C9910           mov      r9d, dword ptr [r9+4*r11+16]\r\n+       458B5108             mov      r10d, dword ptr [r9+8]\r\n+       453BC2               cmp      r8d, r10d\r\n+       732D                 jae      SHORT G_M9639_IG07\r\n+       4D63D0               movsxd   r10d, r8d\r\n+       47694C9110A0860100   imul     r9d, dword ptr [r9+4*r10+16], 0x186A0\r\n        4D63C9               movsxd   r9d, r9d\r\n        4903C1               add      rax, r9\r\n \r\n-G_M4700_IG05:\r\n-       41FFC2               inc      r10d\r\n-\r\n-G_M4700_IG06:\r\n-       443BD2               cmp      r10d, edx\r\n-       410F9CC1             setl     r9b\r\n-       450FB6C9             movzx    r9, r9b\r\n-       4585C9               test     r9d, r9d\r\n-       75AE                 jne      SHORT G_M4700_IG04\r\n+G_M9639_IG04:\r\n        41FFC0               inc      r8d\r\n \r\n-G_M4700_IG07:\r\n-       4181F8A0860100       cmp      r8d, 0x186A0\r\n+G_M9639_IG05:\r\n+       443BC2               cmp      r8d, edx\r\n        410F9CC1             setl     r9b\r\n        450FB6C9             movzx    r9, r9b\r\n        4585C9               test     r9d, r9d\r\n-       7592                 jne      SHORT G_M4700_IG03\r\n+       75AA                 jne      SHORT G_M9639_IG03\r\n \r\n-G_M4700_IG08:\r\n+G_M9639_IG06:\r\n        4883C428             add      rsp, 40\r\n        C3                   ret      \r\n \r\n-G_M4700_IG09:\r\n-       E8D152265F           call     CORINFO_HELP_RNGCHKFAIL\r\n+G_M9639_IG07:\r\n+       E8E952245F           call     CORINFO_HELP_RNGCHKFAIL\r\n        CC                   int3     \r\n \r\n-; Total bytes of code 132, prolog size 4 for method Program:UnHoisted(byref,int)\r\n+; Total bytes of code 108, prolog size 4 for method Program:Hoisted(byref,int)\r\n ; ============================================================\r\n```\r\n\r\nThe execution time of `UnHoisted()` is much higher than that of `Hoisted()`.\r\n\r\nDo we have a starting point for this kind of optimization; such as some basic heuristics in place which needs to be enhanced or would it require an implementation from ground-up?\r\n\r\nCc @mikedn, @omariom, @cmckinsey"},"comment":{"url":"https://api.github.com/repos/dotnet/coreclr/issues/comments/120674842","html_url":"https://github.com/dotnet/coreclr/issues/1218#issuecomment-120674842","issue_url":"https://api.github.com/repos/dotnet/coreclr/issues/1218","id":120674842,"user":{"login":"leppie","id":127666,"avatar_url":"https://avatars.githubusercontent.com/u/127666?v=3","gravatar_id":"","url":"https://api.github.com/users/leppie","html_url":"https://github.com/leppie","followers_url":"https://api.github.com/users/leppie/followers","following_url":"https://api.github.com/users/leppie/following{/other_user}","gists_url":"https://api.github.com/users/leppie/gists{/gist_id}","starred_url":"https://api.github.com/users/leppie/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/leppie/subscriptions","organizations_url":"https://api.github.com/users/leppie/orgs","repos_url":"https://api.github.com/users/leppie/repos","events_url":"https://api.github.com/users/leppie/events{/privacy}","received_events_url":"https://api.github.com/users/leppie/received_events","type":"User","site_admin":false},"created_at":"2015-07-12T00:58:32Z","updated_at":"2015-07-12T00:58:32Z","body":"Easy test, can you prove the array is not being mutated?"}}