Early-CSE is not idempotent

[llvmbot]

Bugzilla Link	8991
Version	trunk
OS	Linux
Reporter	LLVM Bugzilla Contributor
CC	@lattner

Extended Description

Running the Early-CSE several times in succession results in more
simplifications than running it once, for example:

$ opt -disable-output -stats gcc.bc -early-cse
===-------------------------------------------------------------------------===
... Statistics Collected ...
===-------------------------------------------------------------------------===

24 early-cse    - Number of call instructions CSE'd

190990 early-cse - Number of instructions CSE'd
68115 early-cse - Number of instructions simplified or DCE'd
44538 early-cse - Number of load instructions CSE'd
140 early-cse - Number of trivial dead stores removed
2 instsimplify - Number of expansions
31 instsimplify - Number of reassociations

$ opt -disable-output -stats gcc.bc -early-cse -early-cse -early-cse -early-cse -early-cse -early-cse -early-cse -early-cse -early-cse -early-cse -early-cse -early-cse -early-cse -early-cse -early-cse -early-cse -early-cse
===-------------------------------------------------------------------------===
... Statistics Collected ...
===-------------------------------------------------------------------------===

24 early-cse    - Number of call instructions CSE'd

190993 early-cse - Number of instructions CSE'd
70166 early-cse - Number of instructions simplified or DCE'd
44587 early-cse - Number of load instructions CSE'd
176 early-cse - Number of trivial dead stores removed
18 instsimplify - Number of expansions
271 instsimplify - Number of reassociations

That's about a 3% increase in "Number of instructions simplified or DCE'd"
and a 25% increase in "Number of trivial dead stores removed".

My guess is that when an instruction is CSE'd/simplified, its uses are not
being revisited/recursively CSE'd/simplified. I think this can only occur
in loops when uses occur before the instruction.

[lattner]

Do you consider this to be a bug or feature? :) EarlyCSE being fast is a feature to me.

[llvmbot]

It's a bug if it is possible to have early-cse catch more stuff while staying
fast, it's a feature if you sacrificed catching more stuff in order to gain
speed :)

There was the same issue with instsimplify, but there it was easy to revisit
instructions for not much cost: when an instruction simplifies, uses are added
to a set. The function is then rescanned, but only instructions in the set are
re-simplified (so for most instructions you just do a set lookup). This could
be sped up even more by also keeping track of the parent basic block of uses,
and only revisiting those basic blocks. Could such a technique be used with
Early-CSE?