Opened 8 years ago

Last modified 15 months ago

#701 new task

Better CSE optimisation

Reported by: simonmar Owned by: michalt
Priority: normal Milestone:
Component: Compiler Version: 6.4.1
Keywords: Cc: Bulat.Ziganshin@…, pho@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Difficulty: Difficult (2-5 days)
Test Case: N/A Blocked By:
Blocking: Related Tickets:

Description

GHC's CSE optimisation is pretty weedy. It looks for expressions like this:

   let x = e1 in e2

and replaces all occurrences of e1 in e2 with x. This doesn't do full CSE, but it does catch some cases. There have been case where full CSE would be significantly beneficial, though.

One possible way forward is to have a separate CSE pass that transformed expressions containing common subexpressions into the let-form above, and let the existing CSE pass do the final replacement.

We must be cautious, though: increasing sharing can introduce space leaks. Sometimes we can prove that this cannot happen, for example when the shared object is primitive, or has a bounded size.

Change History (14)

comment:1 Changed 8 years ago by igloo

  • Milestone set to 6.8
  • Test Case set to N/A

comment:2 Changed 7 years ago by guest

  • Cc Bulat.Ziganshin@… added

we also can add pragma like

{-# CSE f #-}

comment:3 Changed 6 years ago by simonmar

  • Milestone changed from 6.8 branch to _|_

comment:4 Changed 6 years ago by simonmar

  • Architecture changed from Unknown to Unknown/Multiple

comment:5 Changed 6 years ago by simonmar

  • Operating System changed from Unknown to Unknown/Multiple

comment:6 Changed 4 years ago by PHO

  • Cc pho@… added

comment:7 Changed 4 years ago by simonmar

  • Difficulty changed from Difficult (1 week) to Difficult (2-5 days)

comment:8 Changed 4 years ago by SamAnklesaria

  • Owner set to SamAnklesaria
  • Type of failure set to None/Unknown

comment:9 Changed 4 years ago by SamAnklesaria

  • Owner SamAnklesaria deleted

comment:10 Changed 2 years ago by michalt

  • Owner set to michalt

Interesting ticket. :)

One possible way forward is to have a separate CSE pass that transformed
expressions containing common subexpressions into the let-form above, and let
the existing CSE pass do the final replacement.

But how to identify those subexpressions that are common? Wouldn't that need
another pass? I was thinking about sligthly modifying the idea: have one pass to
identify common subexpressions and then a second one that is an improved version
of current CSE, i.e. uses the information about what subexpressions could be
shared to split more complex expressions and also does the elimination along the
way. Like

  let x = e1 + e2
      y = e1 + e3         

So e1 would be identified as a common subexpression and then so we would
transfor the above to:

  let z = e1     
      x = z + e2 
      y = z + e3 

What do you think?

comment:11 Changed 2 years ago by simonpj

Yes, something like that. Don't forget that CSE might reveal furhter opportunities for CSE.... for example

let x = (p+q) * r in 
let v = p+q       in
let y = v * r     in
let a = y + v     in
let b = x + v     in ...

Here, we can common-up x and y, and then in turn a and b. Note that

  • v is not in scope where x is defined
  • The definitions of x and y look different but are the same
  • Ditto the definitions of a and b

Here's the result we want:

let v = p + q  in
let x = v * r  in
let y = x      in
let a = x + v  in
let b = a      in ...

I think the key word is hash-consing. Never build an expression that you have already built.

I'm sure there is a good literature on CSE if you look in compiler books.

Don't forget that CSE can make things worse by introducing a space leak. Consider

f n = sum [1..n] / length [1..n]

Doing CSE in [1..n] will change the space behaviour from constant to linear in n.

Simon

comment:12 Changed 2 years ago by tibbe

You might also want to look into Global Value Numbering.

comment:13 Changed 15 months ago by morabbin

Seems to be obsolete now, given the presence of #5996, #5344, #2940, and others indicating that CSE is being actively worked on, and with more specifics than here.

Recommend resolve as duplicate.

comment:14 Changed 15 months ago by simonmar

Looking at the tickets, they don't completely overlap. This one is about spotting common subexpressions when they don't occur in the form let x = e in E[e]. #2940 would fix some of those cases, but not all.

Note: See TracTickets for help on using tickets.