[Sprint 2] Add Tailcallelim Pass

[sharaelong]

Overview

It is addition of existing llvm pass. In the LLVM compiler infrastructure, the tail recursion elimination pass is responsible for optimizing recursive function calls in a specific way known as tail recursion elimination (TRE). Tail recursion elimination is a compiler optimization technique that transforms certain recursive function calls into iterative loops, which can improve the performance and memory usage of the program.

When a function call is made in a recursive function, typically the calling function's state (such as return address and local variables) needs to be saved on the call stack. In traditional recursion, this can lead to stack overflow issues or inefficient use of stack space for deep recursion.

Tail recursion occurs when a recursive call is made as the last operation within a function, meaning that there is no further computation to be done after the recursive call returns. In this case, the tail recursion elimination pass rewrites the code to convert the recursive call into a loop, avoiding the need for additional stack frames.

Implementation

It's just including appropriate headers and passes. Read opt.cpp!

Test cases

I tested this pass for 3 cases: factorial calculation, fibonacci number calculation, and calculate sum of digits of given number. All these 3 cases implemented in c file with the form of recursive function, then converted to .ll files through c-to-ll.sh scripts.

I selected these 3 cases because of they have all different form in return statement. Factorial function implemented as they change parameters in function, and direct return value. Fibonacci function has add instruction at last. Sum of digits has to do more instructions which uses recursive function return value.

[willi19]

Good. I think will help my "heap2stack" since it remove recursive function call. Does this remove recursive calls in benchmark?

Also does this support swpp intrinsic?

[germanium32]

Adding pass and test cases looks good to me. Just handle the opt.cpp where you've commented all other passes.

Slight note: Capitalize each words in the PR title plz

[sharaelong]

Good. I think will help my "heap2stack" since it remove recursive function call. Does this remove recursive calls in benchmark?

Also does this support swpp intrinsic?

Tail call elimination is not that much general optimization, so I'm not sure about that. Also SWPP intrinsic cannot be optimized if we can't access intrinsic function at compile time.

[sharaelong]

Adding pass and test cases looks good to me. Just handle the opt.cpp where you've commented all other passes.

Slight note: Capitalize each words in the PR title plz

What do you mean 'capitalize each words'? Do you mean changes into 'TailCallElim'? If it is right, I thought that it is proper noun which don't need to be changed.