Non-local DSE optimization

Hello,

This patch adds non-local DSE optimization. It uses Static Single Use representation. This is my first "big" patch, please be tolerant :slight_smile:

Please note that optimization is disabled by default.

-Jakub

dse_ssu.patch (16.9 KB)

Hi Jakub, interesting patch. I ran it over the Ada testsuite and this
picked up some problems even without enabling dse-ssu. For example,
"opt -inline -dse -domtree" crashes on the attached testcase.

Ciao,

Duncan.

dom_crash.ll (8.09 KB)

Hi,

It looks like PDT.getRootNode() returns NULL for:

define fastcc void @c974001__lengthy_calculation.1736(%struct.FRAME.c974001* nocapture %CHAIN.185) noreturn {
entry:
   br label %bb

bb:
   br label %bb
}

Isn't it a bug in PostDominatorTree?

Please note that this crashes:
opt -postdomtree -debug dom_crash.bc

I think this should be reported as a bug,

-Jakub

Jakub Staszak wrote:

Hi,

It looks like PDT.getRootNode() returns NULL for:

define fastcc void @c974001__lengthy_calculation. 1736(%struct.FRAME.c974001* nocapture %CHAIN.185) noreturn {
entry:
   br label %bb

bb:
   br label %bb
}

Isn't it a bug in PostDominatorTree?

Please note that this crashes:
opt -postdomtree -debug dom_crash.bc

I think this should be reported as a bug,

Yes, that's a bug. Please file it.

The PDT root calculation is looking for all BBs with no successors, this won't work in the face of loops. Either we need to teach PDT users that there can be zero roots, or we need to synthesize a fake root.

The latter is already supported (to handle multiple exits) so that's probably the easiest fix.

Nick

Hello,

Bug is already fixed by Chris (see: http://llvm.org/bugs/show_bug.cgi?id=4915).

I added getRootNode() == NULL condition to my patch. It's not a great solution, but it is enough for now I think. New patch attached.

-Jakub

dse_ssu-2.patch (17.3 KB)

Hello,

I would like to remain my non-local dse patch. I made some small fixes for latest trunk. Can anyone look at this?

dse_ssu-3.patch (17.3 KB)

Hello,

Patch was improved and adjusted to the trunk. I think that CFG Simplification would be useful before DSE. In other case some modification of "MergeBlockIntoPredecessor" would be needed (see TODO note). Please note also, that patch is disabled by default. Tests on test-suite haven't shown any failures.

Regards
-Jakub

dse_ssu-4.patch (17.4 KB)