Cost-aware Function Specialization

**Motivation:** DaphneDSL supports user-defined functions (UDFs) with typed and untyped parameters and results. DAPHNE's MLIR-based optimizing compiler automatically infers the types and properties (e.g., shape, sparsity) of intermediate results in a DaphneDSL script and uses this information for various optimizations. Function calls pose a special challenge as a function must be generic, but should also benefit from information on the inputs to further optimize the code. To fully exploit this information inside functions, DAPHNE currently creates a separate copy of each function per call-site and specializes it with the information available on the parameters (properties, constants). This eager specialization has some drawbacks, e.g., (1) it can increase the size of the intermediate representation (IR) considerably, which can result in (a) multiplied optimization/compilation effort in follow-up compiler passes, (b) decreased readability of the IR by humans, and (c) significantly increased processing time for the function specialization pass or even a crash (e.g., due to running out of memory). A higher optimization/compilation effort can be justified if it is amortized by a decreased execution time afterwards. However, function specialization does not lead to such improvements in all cases.

**Task:** Implement (C++) one or multiple passes in DAPHNE's MLIR-based optimizer, which automatically decide in which cases it makes sense to specialize a function, such that a balance between code/IR size and improved runtime performance is achieved. A viable approach could be to implement the following features (perhaps in separate compiler passes):
- A *conscious and robust specialization of functions*. Ideally with a good decision on when it makes sense to specialize a function (e.g., based on the structure of the function call graph and the size and structure of the function). At least, it should avoid crashes due to excessive specialization.
- *Cleaning up the IR after function specialization*. This could involve (a) removing unused functions (note that a function could become unused as a consequence of simplifcation rewrites made possible through function specialization), (b) removing equal functions (e.g., when two specializations of the same function led to the same result, and (c) generalizing different, but "almost equal", functions into one (e.g., when those functions only differ in constants that could be made function arguments or in concrete data characteristics of the function arguments that could be set to unknown).
- *Inlining functions* is also an option that should be used consciously.

**Hints:**
- Read up on some **helpful background** on this project topic, such as:
- Inter-procedural analysis in general. See, e.g., the slides of Matthias Boehm's AMLS lecture at TU Berlin: [03_Compilation.pdf](https://mboehm7.github.io/teaching/ss24_amls/03_Compilation.pdf) (especially slides 10ff).
- [MLIR](https://mlir.llvm.org/), a framework for building domain-specific compilers, e.g., its [pass infrastructure](https://mlir.llvm.org/docs/PassManagement/).
- DAPHNE EU-project deliverables related to the compiler, such as [D3.3 (Extended Compiler Prototype)](https://daphne-eu.eu/wp-content/uploads/2023/05/DAPHNE_D3.3_ExtendedCompilerPrototype_v1.1.pdf) and [D3.4 (Compiler Design and Overview)](https://daphne-eu.eu/wp-content/uploads/2023/12/D3.4-Compiler-Design-and-Overview-.pdf).
- Get familiar with the **DAPHNE system and code base**. Especially relevant pieces include:
- User documentation on [UDFs in DaphneDSL](https://daphne-eu.github.io/daphne/DaphneDSL/LanguageRef/#user-defined-functions-udfs)
- See `daphne --help`, e.g., for finding out how to display the IR at a certain level (`--explain`) and how to measure the time of the optimization/compilation and execution.
- The current compiler pass on function specialization: `src/compiler/lowering/SpecializeGenericFunctionsPass.cpp`
- The DaphneDSL parser (for parsing of UDFs and the creation of the initial DaphneIR): `src/parser/daphnedsl/DaphneDSLVisitor.cpp`
- The overall DAPHNE compilation chain: `src/compiler/lowering/DaphneIrExecutor.cpp`
- Type and property inference: `src/compiler/inference/InferencePass.cpp`, MLIR interface implementations in `src/ir/daphneir/`
- Some **hints on the design and implementation**:
- Feel free to either improve the current `SpecializeGenericFunctionsPass` or to discard it and implement your passes from scratch (potentially taking inspiration from the existing pass), both is fine.
- Think about meaningful limits to function specialization (e.g., based on the number of specialized variants or the size of the IR, or by analyzing the function and finding out that specialization is not useful).
- More expressive names of specialized functions could help to make the IR after function specialization more human-readable. At the moment, a DaphneDSL UDF `foo` could become, e.g., `foo-1-2` during specialization. A more helpful name could be something like `foo_x0` if `foo` was specialized by propagating the value `0` for the argument `x` into the function.
- Note that UDFs can be used in DaphneDSL through function calls (`daphne.GenericCallOp`) and through second-order functions (so far only `map()`/`daphne.MapOp`).
- In the context of this project, you may naturally address a few related open issues (e.g., #661, #685) and fill in some missing bits and pieces here and there (e.g., support for recursion in UDFs without result type specified, support for optional function parameters with defaults, support for propagating constants into untyped functions, support for calling a function in a code line above its definition).
- Feel free to take inspiration from IPA in [Apache SystemDS](https://github.com/apache/systemds) (e.g., its code on [IPA](https://github.com/apache/systemds/tree/main/src/main/java/org/apache/sysds/hops/ipa)). But if you do so, mind the software license.
- Think of meaningful **experiments**. For instance, you could show (a) cases that used to crash and became manageable through your contribution, (b) the impact of your balanced function specialization on the footprint of the IR as well as on optimization/compilation time and execution time.

**Some example scripts:**
- A script that currently crashes DAPHNE due to excessive function specialization:
```R
# foo.daphne
def foo(n: si64) -> si64 {
if(n == 0)
return 0;
return foo(n - 1);
}
print(foo($n));
```
Try different values of `n`, e.g., `0`, `1`, `1000000` and see what happens.
```
bin/daphne --explain property_inference foo.daphne n=0
```
- A script resulting in two equal function specialization:
```R
# bar.daphne
def bar(x: si64) {
print(x);
}
bar(1);
bar(1);
```
```
bin/daphne --explain property_inference bar.daphne
```

Start by reading src/compiler/lowering/SpecializeGenericFunctionsPass.cpp and the compilation flow in src/compiler/lowering/DaphneIrExecutor.cpp, then inspect the inference and DaphneIR interfaces. Run the recursive foo and duplicate bar examples with --explain property_inference to establish current behavior. Done means specialization avoids excessive growth or crashes, cleans up equivalent or unused functions where addressed, and includes measurements of IR size, compilation time, and execution time.

Written by the indexing model from the issue text.