search

llvm / llvm-project

The LLVM Project is a collection of modular and reusable compiler and toolchain technologies.
http://llvm.org
Other
26.48k stars 10.83k forks source link

Jump threading produces funky output #2881

Closed llvmbot closed 15 years ago

llvmbot commented 15 years ago
Bugzilla Link 2509
Resolution FIXED
Resolved on Jul 03, 2008 00:08
Version unspecified
OS All
Attachments Input.ll, Output.ll
Reporter LLVM Bugzilla Contributor
CC @efriedma-quic

Extended Description

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.

lattner commented 15 years ago

It probably doesn't... owen?

efriedma-quic commented 15 years ago

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

lattner commented 15 years ago

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

efriedma-quic 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).

efriedma-quic 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.

That's simply wrong; see RemoveUnreachableBlocks and MarkAliveBlocks in SimplifyCFGPass.cpp.

lattner 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.

efriedma-quic commented 15 years ago

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

llvmbot commented 15 years ago

Part 1 is done as of r53038.

llvmbot commented 15 years ago

Part 2 is done as of r53032.

lattner commented 15 years ago

Owen was going to take a look at this :)

lattner 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).

llvmbot commented 15 years ago

Right, that's what I meant.

efriedma-quic commented 15 years ago

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