## Summary Expensive loop invariant expression is not hoisted out of a recursive function. ## Steps to reproduce Compile and run the attached code: [loopInvariant.hs](/uploads/475ddd82deda4cd2e4b3660c8ead3263/loopInvariant.hs) ``` > ghc -O2 loopInvariant.hs Loaded package environment from /Users/gcolpitts/.ghc/x86_64-darwin-9.8.2/environments/default [1 of 2] Compiling Main ( loopInvariant.hs, loopInvariant.o ) [2 of 2] Linking loopInvariant ld: warning: ignoring duplicate libraries: '-lm' ld: warning: search path '/opt/local/lib/' not found gcolpitts@Georges-Mini haskell % ./loopInvariant +RTS -s 39001250856960000 1,920,053,000 bytes allocated in the heap 16,488 bytes copied during GC 8,028,224 bytes maximum residency (2 sample(s)) 393,152 bytes maximum slop 22 MiB total memory in use (0 MiB lost due to fragmentation) Tot time (elapsed) Avg pause Max pause Gen 0 239 colls, 0 par 0.001s 0.002s 0.0000s 0.0000s Gen 1 2 colls, 0 par 0.000s 0.002s 0.0009s 0.0017s INIT time 0.003s ( 0.003s elapsed) MUT time 3.141s ( 3.138s elapsed) GC time 0.001s ( 0.004s elapsed) EXIT time 0.001s ( 0.006s elapsed) Total time 3.146s ( 3.151s elapsed) %GC time 0.0% (0.0% elapsed) Alloc rate 611,361,327 bytes per MUT second Productivity 99.8% of total user, 99.6% of total elapsed ``` Comment out the line: ``` let p = smallest maxN ! m ``` Uncomment the lines: ``` -- let p = sm ! m -- sm = smallest maxN ``` Compile and run the changed code: ``` > ghc -O2 loopInvariant.hs Loaded package environment from /Users/gcolpitts/.ghc/x86_64-darwin-9.8.2/environments/default [1 of 2] Compiling Main ( loopInvariant.hs, loopInvariant.o ) [Source file changed] [2 of 2] Linking loopInvariant [Objects changed] ld: warning: ignoring duplicate libraries: '-lm' ld: warning: search path '/opt/local/lib/' not found gcolpitts@Georges-Mini haskell % ./loopInvariant +RTS -s 39001250856960000 16,051,152 bytes allocated in the heap 10,040 bytes copied during GC 44,328 bytes maximum residency (1 sample(s)) 29,400 bytes maximum slop 22 MiB total memory in use (0 MiB lost due to fragmentation) Tot time (elapsed) Avg pause Max pause Gen 0 2 colls, 0 par 0.000s 0.000s 0.0000s 0.0000s Gen 1 1 colls, 0 par 0.000s 0.001s 0.0012s 0.0012s INIT time 0.003s ( 0.003s elapsed) MUT time 0.018s ( 0.018s elapsed) GC time 0.000s ( 0.001s elapsed) EXIT time 0.001s ( 0.012s elapsed) Total time 0.022s ( 0.034s elapsed) %GC time 0.0% (0.0% elapsed) Alloc rate 889,408,322 bytes per MUT second Productivity 80.9% of total user, 53.0% of total elapsed ``` Allocation has been reduced from 2 billion bytes to 16 million. Runtime has been reduced from 3 seconds to 0.02 seconds. ## Expected behavior I expect the compiler to do the optimization given above ## Environment * GHC version used: 9.8.2 (reproducible on 9.10.1 also) Optional: * Operating System: MacOS Sonoma 14.5 * System Architecture: x86_64 (w 9.8.2) and Apple Silicon (w 9.10.1)[loopInvariant.hs](/uploads/33b631cc3b1d166fc49866b4d0063d3a/loopInvariant.hs)