Switch instruction optimization

Project Infrastructure LLVM Dev List Archives
#1

Hello there,

I have a high level code which would look like that in C++:

enum E { A, B, C };

E int2e(long i) {
switch(i) {
case 0: return A;
case 1: return B;
case 2: return C;
default: return A;
}
}

It is compiled to this IR with O3 optimization:

define i64 @int2e(i64 %i_arg) #0 {
entry:
switch i64 %i_arg, label %label_case1 [
i64 2, label %label_case3
i64 1, label %label_case2
]

label_case1: ; preds = %entry, %label_case3, %label_case2
%merge = phi i64 [ %i_arg, %label_case2 ], [ %i_arg, %label_case3 ], [ 0, %entry ]
ret i64 %merge

label_case2: ; preds = %entry
br label %label_case1

label_case3: ; preds = %entry
br label %label_case1
}

In the result IR phi instruction has 3 branches, but two first of them returns the same value. Shouln’t it be optimized?

  • Paweł
#2

On first glance, this looks like it should be handled by ForwardSwitchConditionToPHI in SimplifyCFG. (Note: That's a guess. I'm reading the code for the first time.) I'd suggest filling a bug with all of the options you're running with. We really should catch this case.

Well, really there's two missed optimization cases here. Even without the case value forwarding, label_case2 and label_case3 are redundant.

Philip

#3

On first glance, this looks like it should be handled by
ForwardSwitchConditionToPHI in SimplifyCFG. (Note: That's a guess. I'm
reading the code for the first time.)

Yes, that's the idea.

It looks like ForwardSwitchConditionToPHI has done its thing here,
since %i_arg is coming into the phi node instead of 1 and 2, but then
there's some other code that's supposed to fold away the redundant
basic blocks, and that doesn't seem to have worked.

I'd suggest filling a bug with all of
the options you're running with. We really should catch this case.

+1 on getting a bug filed, I'd like this to work.

Well, really there's two missed optimization cases here. Even without the
case value forwarding, label_case2 and label_case3 are redundant.

I think it's still just one missed optimization. We'll always end up
with two blocks since we need to range-check the switch expression.

- Hans

#4

I ran into almost the same case a few months ago, and half fixed it but never finished the patch. I found that it does the right thing if you manually ran some combination of simplifycfg and instcombine on the unoptimized IR it would do the right thing, but the standard pass order doesn’t do it.