[comb] Build Reduction Ops whenever possible

[Schottkyc137]

See issue #3002

Build reduction ops when possible to reduce operations of the form or(a[0], a[1], ..., a[n]) to icmp ne(a, 0).

This optimization is implemented for the and, or and xor operations

[Schottkyc137]

Thanks! This canonicalization logic makes sense to me! I added a few comments.

Thanks for the review! In my new approach, I use an APInt as a bit-set. Is this approach OK or is there a better structure for that purpose?

[uenoku]

I use an APInt as a bit-set. Is this approach OK or is there a better structure for that purpose?

Probably llvm::BitVector would be more appropriate.

[Schottkyc137]

Sorry I guess it is incorrect to fold duplication in xor op xor(x[0], x[0], x[1], ..., x[n-1]) into parity.

Oh, you're absolutely right, I missed that. Thinking about it, a possible solution could be to reintroduce the size != source.getType().getIntOrFloatBitWidth(). While this will disallow optimizations of the form and(a[0], a[0], a[1], ..., a[n]) it shouldn't matter because the case and(x, x, ...) is covered already and the case or(x, x, ...) should be covered (currently it only works if the two 'x' elements are the last elements). That would also re-introduce a nice early out, what do you think?

[uenoku]

Yeah, I think it makes sense to restore size != source.getType().getIntOrFloatBitWidth() condition.

[uenoku]

Sorry for the long delay, I think the canonicalizer is definitely useful so let me merge this. Thank you for sending PR :)