Opt: Need empty control flow removal

[greg-lunarg]

The current aggressive dead code elimination does not get rid of empty control flow ie control flow headers and structures which are "empty" ie do not contain code which contributes to the externally facing results of the function. The most simple example of this is an OpBranchConditional where both true and false branches branch to blocks which are empty and branch directly to the merge block.

Elimination of such control flow can lead to elimination of a potentially significant amount of dead code which is used to compute the useless control flow. This dead code can cause a shader to reflect a false use of texture or shader object. Elimination of such false uses is essential in the porting of HLSL shaders.

The highest priority is empty "if" structures, followed by "loops" and "switches".

My first thought is to make this part of aggressive dce. The following is a description of how ADCE would be modified.

ADCE currently marks all branches as live. This would be changed to not mark OpBranchCondtionals which are associated with a SelectionMerge.

When an instruction is marked live, its block will be marked live. When a block is first marked live, if its immediately containing control structure is an "if", the corresponding OpBranchConditional will be marked live.

It is possible for the BranchConditional of an "if" to be live even when both branches are empty. This is when there are live phis in the merge block of the "if". So if such a phi is marked live, the OpBranchConditional in the merge's corresponding header block is marked live.

After closure is performed on all live instructions, if an OpBranchConditional is dead, it is replaced with an unconditional branch to its corresponding merge block.

Any control flow so processed will become a candidate for Unreachable Block Elimination.

I am claiming this issue and am beginning active implementation of empty "if" removal.

[s-perron]

I have a suggestion on how to make the implementation a bit simpler. We could get a pass called "Branch Improvements", where we look for ways if simplifying the CFG. One of those would be, if you have a branch to an empty block, then change it to branch to the successor of the empty block. Empty here means no code in the block except for a label, NOPs and an unconditional branch.

Then if you have a condition branch that branches to the same block on all paths, replace it with in an unconditional branch. Let unreachable block removal get rid of the blocks.

Doing this would mean implementing it outside of ADCE, and running it afterwards, and then rerunning DCE. It has this extra complication.

This advantage of this method it that is will get rid of all empty blocks, not just those in the particular pattern you are looking for. The code will be much simpler, and therefore less prone to bugs.

What do you think?

[greg-lunarg]

You have some good ideas and I appreciate your review.

I thought of something similar, but it was the cycling with ADCE that I wanted to avoid. That is because we would potentially need to cycle on the order of the nesting of the empty control structures.

Right now we don't have any nice way to query pass results and do conditional execution of passes, at least at the command interface, and I think at the library interface as well. Since we are required to remove all empty control flow in order to get DX-equivalent reflection results, given the interface we currently have, it seemed that there was no scalable solution.

Not that we couldn't or shouldn't come up with a more flexible interface. But I have been asked to solve this problem for a team that is trying to port an engine to Vulkan on a deadline, so I thought expanding ADCE was the most expedient solution.

[dnovillo]

I've been thinking that we may want to move all these CFG cleaners into the CFG cleanup pass I've been working on. Let dce and friends leave all the control flow intact and have all the straightening and rearranging in one spot.

On Oct 12, 2017 21:36, "greg-lunarg" notifications@github.com wrote:

You have some good ideas and I appreciate your review.

I thought of something similar, but it was the cycling with ADCE that I wanted to avoid. That is because we would potentially need to cycle on the order of the nesting of the empty control structures.

Right now we don't have any nice way to query pass results and do conditional execution of passes, at least at the command interface, and I think at the library interface as well. Since we are required to remove all empty control flow in order to get DX-equivalent reflection results, given the interface we currently have, it seemed that there was no scalable solution.

Not that we couldn't or shouldn't come up with a more flexible interface. But I have been asked to solve this problem for a team that is trying to port an engine to Vulkan on a deadline, so I thought expanding ADCE was the most expedient solution.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/KhronosGroup/SPIRV-Tools/issues/878#issuecomment-336326292, or mute the thread https://github.com/notifications/unsubscribe-auth/AG9RZ4Ha3LYTrC2C_9LgJcLXe9LBnAZIks5srr6hgaJpZM4P3xHi .

[greg-lunarg]

Yes. Once it's out there, we will have to start using it (and retro-fit dead-branch-elim, etc.)

[s-perron]

That will be a good idea. Moving some of this stuff around afterwards will be good.

[greg-lunarg]

Status: I have dead if elimination coded up and passing (regression) testing.

The group that needs this also needs dead loop elimination as well. I am beginning that and should have something in a day or two.