search

Quuxplusone / LLVMBugzillaTest

0 stars 0 forks source link

Jump threading produces funky output #2733

Closed Quuxplusone closed 15 years ago

Quuxplusone commented 15 years ago
Bugzilla Link PR2509
Status RESOLVED FIXED
Importance P normal
Reported by Owen Anderson (resistor@mac.com)
Reported on 2008-06-30 19:46:47 -0700
Last modified on 2008-07-03 00:08:19 -0700
Version unspecified
Hardware PC All
CC efriedma@quicinc.com, evan.cheng@apple.com, llvm-bugs@lists.llvm.org
Fixed by commit(s)
Attachments 1.ll (1821 bytes, text/plain)
2.ll (1872 bytes, text/plain)
Blocks
Blocked by
See also

In the case attached, jump threading produces output with unreachable blocks that still branch to reachable blocks. It would be really nice if it didn't do this. This situation causes GVN to miss some optimizations.

Quuxplusone commented 15 years ago

Attached 1.ll (1821 bytes, text/plain): Input.ll

Quuxplusone commented 15 years ago

Attached 2.ll (1872 bytes, text/plain): Output.ll

Quuxplusone commented 15 years ago

Jump threading naturally kills blocks... maybe it should remove the dead blocks using something like the RemoveUnreachableBlocks code in SimplifyCFG.

Quuxplusone commented 15 years ago

Right, that's what I meant.

Quuxplusone commented 15 years ago 
The problem is that this is producing a cyclic structure with multiple blocks
that are unreachable, all of which have preds.

We should do two things:

1) the ADCE pass should do a mark and sweep pass to nuke unreachable blocks
2) GVN should be improved to not be pessimized by unreachable blocks (using
'undef' as an available version of any expression from the unreachable block).
Quuxplusone commented 15 years ago

Owen was going to take a look at this :)

Quuxplusone commented 15 years ago

Part 2 is done as of r53032.

Quuxplusone commented 15 years ago

Part 1 is done as of r53038.

Quuxplusone commented 15 years ago

I don't follow why "part 1" is necessary; SimplifyCFG already prunes unreachable blocks.

Quuxplusone commented 15 years ago

simplifycfg deletes blocks with no predecessors. If you have a cyclic subgraph of the cfg that is not reachable, simplifycfg won't touch it.

Quuxplusone commented 15 years ago 
(In reply to comment #10)
> simplifycfg deletes blocks with no predecessors.  If you have a cyclic
subgraph
> of the cfg that is not reachable, simplifycfg won't touch it.

That's simply wrong; see RemoveUnreachableBlocks and MarkAliveBlocks in
SimplifyCFGPass.cpp.
Quuxplusone commented 15 years ago

I just realized that we might not have been talking about the same thing, since simplifycfg can refer to both the SimplifyCFG function and the "simplifycfg" pass (whose full name is CFGSimplifyPass).

Quuxplusone commented 15 years ago

Right, I was thinking of the function... you're right though that the pass is what really matters.

Quuxplusone commented 15 years ago

Okay... so then the question remains: why does ADCE need to be able to deal with this?

Quuxplusone commented 15 years ago

It probably doesn't... owen?