About LLVM switch instruction

I am performing a transformation that requires changing the targets of
a basic block ending with a switch instruction.
In particular, I need to delete the edge that goes to the "default"
basic block.
But, LLVM switch instruction always wants a default target basic block
for a switch instruction.
It is not clear how to accomplish this, since I don't have a
replacement default target block.
I could potentially fake that edge to be one of the other case label
targets, but that is an ugly hack and I don't want to do that.
I would appreciate if you can suggest better alternatives.

-Milind

Hi Milind,

If you make the "default" branch to a block that has an UnreachableInst as a terminator, the SimplifyCFG pass will remove one of the switch cases and replace the block that the default branches to with the block that this removed case branches to. This sounds a lot like the "ugly hack" that you would like to avoid. Would it be a reasonable solution for what you are trying to accomplish?

Mark

Hi Mark,

This will workaround the problem of "default" branch restriction on
the switch instruction. The trouble with this technique is that it
will trump later optimization phases such as constant propagation.
When a block was part of a case, because of the knowledge of the case
value, the block was a candidate for better optimization. However,
when we move the body of the case into the default, the knowledge of
the case value is lost and the body is less optimizable.

-Milind

Yes, it is not ideal for a variety of reasons, and I am actually looking at improving how we deal with unreachable switch defaults now because of that.

Could you provide any additional detail about the transforms you are doing and what you are trying to accomplish?

Mark

Hi Milind,

Maybe you could annotate the default case value as metadata to the swith instruction.

Thanks
Hongbin

Mark,

I am basically trying to do a specialized form of unreachable block
elimination. I bumped into this issue when I was thinking of
eliminating unreachable cases (including default). In the following
code, assertion propagation should easily infer that the default is
unreachable. But, llvm at -O3 leaves the code in default intact. Your
technique of placing "unreachable" instruction in the default case
makes a difference though.

Hongbin

Can you elaborate more on your suggestion? I am not sure I fully
understand what you suggested.

-Milind

Hi Milind,

My suggestion just for your concern that if you eliminate the default block, a block associated with a case value will become the default block of the swhich instruction, since a switch instruction always requires a default block.
But when a block associated with a case value become the default block, the associated case value is lost and may confuse the later optimizations such as constant propagation.

To prevent such information lost when you eliminate the default block and make a block associated with a case value will become the default block, you can attach a metadata[1] to the switch instruction to provide the case value of the default block.

In order to take the advantage of the attached metadata for the default case of the switch instruction you also need to modify the later optimization accordingly.

Thanks
Hongbin

[1]http://blog.llvm.org/2010/04/extensible-metadata-in-llvm-ir.html

Hi Milind,

My suggestion just for your concern that if you eliminate the default block,
a block associated with a case value will become the default block of the
swhich instruction, since a switch instruction always requires a default
block.
But when a block associated with a case value become the default block, the
associated case value is lost and may confuse the later optimizations such
as constant propagation.

To prevent such information lost when you eliminate the default block and
make a block associated with a case value will become the default block, you
can attach a metadata[1] to the switch instruction to provide the case value
of the default block.

If I'm understanding you correctly you're suggesting removing the
default block & representing it in metadata only (instead of using an
existing case block as the default as well). That seems like it would
break the invariant that every switch has a default (if we didn't have
that invariant we would just eliminate the unreachable default block &
not bother associating it with an existing case), wouldn't it?
Metadata has to be droppable (because not all passes
preserve/understand all metadata) so we can't rely on the preservation
of the metadata to maintain the switch instructions invariant.