digitalmars.D.bugs - [Issue 4453] New: Loop-invariant code motion for pure functions
- d-bugmail puremagic.com (61/61) Jul 13 2010 http://d.puremagic.com/issues/show_bug.cgi?id=4453
- d-bugmail puremagic.com (12/12) Aug 19 2013 http://d.puremagic.com/issues/show_bug.cgi?id=4453
http://d.puremagic.com/issues/show_bug.cgi?id=4453 Summary: Loop-invariant code motion for pure functions Product: D Version: D2 Platform: All OS/Version: All Status: NEW Severity: enhancement Priority: P2 Component: DMD AssignedTo: nobody puremagic.com ReportedBy: bearophile_hugs eml.cc D pure functions return the same result (or they throw an error/exception), so their call can be pulled out of loops if their input is loop-invariant. It's a compiler optimization: http://en.wikipedia.org/wiki/Loop-invariant_code_motion This example of D2 code shows two examples of this possible optimization: import core.stdc.stdio: printf; pure int foo(int n) { auto array = new int[n]; foreach (i, ref x; array) x = i; int total = 0; foreach (x; array) total += x; return total; } void main() { int[int] aa = [1:10]; int total = 0; foreach (i; 0 .. 5) { int n = aa[1]; total += foo(n); } printf("%d\n", total); } The fetching of a value from an associative array (__aaGetRvalue) is a pure function, and there is no other change done on the associative array, so it can be moved outside the foreach(i) loop of main(). Then the call to foo(n) too becomes loop-invariant. (Later further optimizations can replace the constant sums inside a loop by a multiplication, but this is a different kind of optimization). Currently dmd v2.047 doesn't move the calls to not-inlined pure functions out of the loop: L1D: push 1 mov EDX,offset FLAT:_D10TypeInfo_i6__initZ push 4 push EDX push EDI call near ptr __aaGetRvalue add ESP,010h mov EAX,[EAX] call near ptr _D5test23fooFNaiZi add ESI,EAX inc EBX cmp EBX,5 jb L1D -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Jul 13 2010
http://d.puremagic.com/issues/show_bug.cgi?id=4453 hsteoh quickfur.ath.cx changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |hsteoh quickfur.ath.cx This looks like a front-end enhancement; just tested the code with gdc -O3, and the call to _aaGetRvalueX is still inside the loop body (in spite of massive inlining and loop unrolling by the gcc backend). -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Aug 19 2013