Add instcombine and a pass to eliminate intrinsics

[goranmoomin]

This PR adds InstCombinePass and intrinsic_elim::IntrinsicEliminatePass that eliminates the intrinsics that InstCombinePass produces.

[sharaelong]

Not only this PR, but it also appears that we need to change CMakeLIsts.txt according to this notice in sprint 1 and 2 as well. Except that, LGTM.

[germanium32]

As I searched about the potential scope of InstCombine, I found that it can optimize numerous cases. Are there any other optimization results that can(must) be handled, besides of smax, smin, umax, umin?

Nevertheless, LGTM!

[germanium32]

Also, remind that existing pass also requires test cases. Add some simple test instructions that can be combined.

[willi19]

The LLVM instcombine pass, also known as the "Instruction Combination" pass, performs various algebraic simplifications and optimizations on LLVM instructions. While it doesn't generate intrinsic instructions directly, it can transform existing instructions into equivalent or more optimized forms, which may involve the use of intrinsic functions.

Here are some examples of intrinsic functions that the instcombine pass can generate as part of its optimization process:

1. Memory intrinsics:

   • llvm.memcpy: Intrinsic for copying a block of memory.
   • llvm.memset: Intrinsic for setting a block of memory to a specific value.
   • llvm.memmove: Intrinsic for moving a block of memory, handling overlapping regions.

2. Arithmetic intrinsics:

   • llvm.ctpop: Intrinsic for counting the number of population (set) bits in an integer.
   • llvm.cttz: Intrinsic for counting trailing zeros in an integer.
   • llvm.ctlz: Intrinsic for counting leading zeros in an integer.
   • llvm.sadd.with.overflow and llvm.uadd.with.overflow: Intrinsics for signed and unsigned addition with overflow detection.
   • llvm.ssub.with.overflow and llvm.usub.with.overflow: Intrinsics for signed and unsigned subtraction with overflow detection.
   • llvm.smul.with.overflow and llvm.umul.with.overflow: Intrinsics for signed and unsigned multiplication with overflow detection.

3. Other intrinsics:

   • llvm.expect: Intrinsic for providing branch prediction hints to the optimizer.
   • llvm.bitreverse: Intrinsic for reversing the order of bits in an integer.
   • llvm.sadd.sat and llvm.uadd.sat: Intrinsics for saturating signed and unsigned addition.
   • llvm.ssub.sat and llvm.usub.sat: Intrinsics for saturating signed and unsigned subtraction.
   • llvm.sadd.with.overflow.sat and llvm.uadd.with.overflow.sat: Intrinsics for saturating signed and unsigned addition with overflow detection.
   • llvm.ssub.with.overflow.sat and llvm.usub.with.overflow.sat: Intrinsics for saturating signed and unsigned subtraction with overflow detection.

These are just a few examples of intrinsic functions that can be generated or utilized by the instcombine pass during its optimization process. The specific intrinsics used will depend on the patterns and optimizations applicable to the code being processed.

This is what chat-gpt replied for intrinsic that this pass can generate. Would this instrinsic will not be generated for the hidden benchmark?

[goranmoomin]

I still have to check the source code of InstCombine to confirm what kind of intrinsics can be generated.