Eliminating Unnecessary MUX structures

You will often hear engineers in our business saying something along these lines:
“I first code, and then let synthesis find the optimal implementation” or “synthesis tools are so good these days, there is no use in spending time on thinking in the circuit level…”. Well not me – sorry!! I am a true fan of “helping” or “directing” the synthesis.
The example I will discuss on this post, is a real life example that occurred while reviewing a fellow engineer’s work.

The block in discussion is quite a heavy one, with very tight timing requirements and complicated functionality (aren’t they all like that…). Somewhere in the code I encountered this if-else-if statement (Verilog):

if (s1)
   y = 1'b1;
else if (s2)
         y = 1'b0;
      else
         y = x;

Now, if this would have stood on its own, it would not have risen much suspicion. But this statement happened to be part of the critical path. On first look, the if-else-if ladder is translated into a set of cascaded muxes, but looking carefully at it, one can simplify it into two gates (or even one complex gate in most libraries) as shown below.

I do not say that a good synthesis tool is not able to simplify this construction, and I have to admit I do not really know what is going on inside the optimization process – this seems to be some sort of black magic of our art – but fact is, that timing improved after describing the if-else-if statement explicitly as an or-and combination.
The reason can be, as depicted, that the muxes are being “dragged” somehow into the logic clouds just before and after them in hope of simplifying them there. I just don’t know!
A good sign to spot when such simplification is easily possible, is when you have an if-else-if ladder or a case statement with constants on the right hand side (RHS). It does make the code a bit less readable, but IMHO it is worth it.

Here is a short summery of some common mux constructs with fixed inputs and their simplified forms.