llvm dev - Aug 2011 - [LLVMdev] A pass to minimize instruction bitwidth?

Does llvm have a pass that minimizes the bitwidth of llvm instructions?
For instance:

  %8 = and i32 %7, 63

63 is 111111 in binary. So the 'and' instruction only requires 6 bits.

We could rewrite the above code as:
  %8 = trunc i32 %7 to i6
  %9 = and i6 %8, 63

Since we only need the lower 6 bits we could also propagate this
change backwards to reduce the bitwidth of prior instructions.
I'm synthesizing hardware from LLVM IR so these non-standard bitwidths
can actually save chip area.
I've started writing a pass to do this but I figured there might be an
existing pass for downcasting 64-bit operations to 32-bit operations
that I could borrow code from.

Thanks,
Andrew

Hi Andrew,
> Does llvm have a pass that minimizes the bitwidth of llvm instructions?
Douglas do Couto Teixeira and Fernando Magno Quintao Pereira implemented
such a pass already, but it didn't get into LLVM (yet).  One reason is the
lack of interest from most LLVM users for this.  So if you are interested,
perhaps you can help them get their work incorporated into LLVM.

Ciao, Duncan.
> For instance:
>
>    %8 = and i32 %7, 63
>
> 63 is 111111 in binary. So the 'and' instruction only requires 6
bits.
>
> We could rewrite the above code as:
>    %8 = trunc i32 %7 to i6
>    %9 = and i6 %8, 63
>
> Since we only need the lower 6 bits we could also propagate this
> change backwards to reduce the bitwidth of prior instructions.
> I'm synthesizing hardware from LLVM IR so these non-standard bitwidths
> can actually save chip area.
> I've started writing a pass to do this but I figured there might be an
> existing pass for downcasting 64-bit operations to 32-bit operations
> that I could borrow code from.
>
> Thanks,
> Andrew
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

Hi Andrew,

We have a pass to perform this kind of bitwidth reduction. And we are
now working on an inter-procedural version of our range analysis
algorithm. We already have an intra-procedural version and we hope to
have an inter-procedural version working in the next few weeks. If you
are interested, let me know. I'd be happy to share the code and it
would be great if you can help us to improve our work, so it can get
in into the LLVM :).

You can find a report describing our previous work here:
http://homepages.dcc.ufmg.br/~douglas/projects/RangeAnalysis/RangeAnalysis.html

And I can explain you a bit more about our current work, if you want.

Regards,

Douglas

On Wed, Aug 31, 2011 at 6:14 PM, Andrew Canis <andrewcanis at gmail.com>
wrote:
> Does llvm have a pass that minimizes the bitwidth of llvm instructions?
> For instance:
>
>   %8 = and i32 %7, 63
>
> 63 is 111111 in binary. So the 'and' instruction only requires 6
bits.
>
> We could rewrite the above code as:
>   %8 = trunc i32 %7 to i6
>   %9 = and i6 %8, 63
>
> Since we only need the lower 6 bits we could also propagate this
> change backwards to reduce the bitwidth of prior instructions.
> I'm synthesizing hardware from LLVM IR so these non-standard bitwidths
> can actually save chip area.
> I've started writing a pass to do this but I figured there might be an
> existing pass for downcasting 64-bit operations to 32-bit operations
> that I could borrow code from.
>
> Thanks,
> Andrew
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>