Is it possible for a c compiler to transform an 'if-elseif' bloc into a 'switch' bloc to optimize the code?

Question

Is it possible for a c compiler to transform an 'if-elseif' bloc into a 'switch' bloc to optimize the code ?

The following code :

if ( a == 1 ) {
  bloc1
} else if ( a == 2 ) {
  bloc2
} else if ( ... ) {
....
} else if ( a == n ) {
  bloc n
}

during compilation is transformed to :

switch(a) {
  case 1:
    bloc1
    break;

  case 2:
    bloc2
    break;
  ...
  case n:
    blocn
    break;
}

If it is possible every time it is feasible, is there again an advantage of 'if...elseif' blocs on 'switch' blocs ?

There is no "switch" in the machine code generated by the compiler. But yes, the compiler may produce any code that it thinks that is executed faster. On the other hand it is possible that your two program snippets result in identical or at least very similar machine code. — Jabberwocky, Jan 28 '16 at 14:36
@MichaelWalz: I think OP means some code which executes in constant time using a jump-table or similar (some CPUs have special instructions for that). — too honest for this site, Jan 28 '16 at 15:08

score 3 · Answer 1 · edited May 23 '17 at 12:25

3

In case you've never heard about the "as-if" rule: here it is. That means, the compiler is allowed to migrate if to switch in certain occasions, yes.

switch should be used whenever possible; it gives the compiler more information about the type of data parsed and enables it to construct something like hash tables.
if should be used when switch cannot be used. That's as easy as it gets.

edited May 23 '17 at 12:25

Community

1
1

answered Jan 28 '16 at 14:37

cadaniluk

15,027
2
39
67

"it gives the compiler more information about the type of data parsed" Huh? Why would the compiler not know the type of a variable? Furthermore the compiler is smart enough to construct something like hash tables out if `if-else` too, given that the conditions are compile-time constants. So most of your answer seems rather subjective to me. – Lundin Jan 28 '16 at 15:28
@Lundin By "type" I mean "kind," not really a data type. I'll clarify that. – cadaniluk Jan 28 '16 at 19:11

score 3 · Answer 2 · answered Jan 28 '16 at 14:37

A c compiler can make any optimisations it likes, so long as the program intent is not altered in any way.

Noting that a switch can only occur on integral types, the conversion to a switch in your case does appear to be optimal. Trust your optimiser to make such a transformation if appropriate. You can always inspect the output assembly to verify.

score 3 · Accepted Answer · edited Jan 28 '16 at 15:38

A compiler translates C code to machine code. On assembler level, there is no such thing as if, else or switch. There are just conditional branches and non-conditional branches.

So, no, the compiler will never do anything like what you are suggesting, because an if-else that can be replaced by a switch will already result in identical machine code, no matter which one you wrote. There is no middle "convert C to C" step.

For this reason, switch is kind of an obscure language feature, since it is in theory completely redundant. It is subjective whether a switch results in more readable or less readable code. It can do either, on a case-by-case basis.

Special case:

There exists a common optimization of switch statements that the compiler can do when all the case labels are adjacent integer constants, and that is to replace the whole switch with an array of function pointers. It can then simply use the switch condition as array index to determine which function to call. No comparisons needed. This is quite a radical optimization, because it removes numerous comparisons and thereby speeds up the code, improves branch prediction, etc.

The very same optimization is possible if you have a chain of if - else if, like so:

if(n==0)
{ }
else if(n==1)
{ }
else if(n==2)
{ }
...

This can also get optimized into an array of function pointers, just like if it were written as a switch.

Is it possible for a c compiler to transform an 'if-elseif' bloc into a 'switch' bloc to optimize the code?

3 Answers3