Adds an optimization that moves loop-invariant nodes in front of the loop (to the deepest common dominator of the loop entry point predecessors). In nested loops, nodes are moved out as far as possible. Currently, only data nodes are moved (except Phis), but const/pure (? @g4rgoil) functions could be added, if applicable.

This PR proposes a unified logging system for our compiler. Please let me know if you would like changes to the overall design or to the API of Logger. Console output is currently structured as follows:

error: lexer: 42,28: unexpected character '$'

Adds an inliner to the local optimizations. Features:

• efficient convergence by bottom-up traversal of call graph in alternation with local optimizations
• heuristic analysis of the benefit of inlining a given call site via number of constant parameters and size of callee
• ensures that the total code size only grows by a constant factor by tracking the size of visited functions in comparison to the first visit
• Recursive functions usually won't be inlined; however, this is not necessarily so if some input arguments are constant. In this case, the inliner will apply up to a constant number of inlining passes in hope of eliminating the function call completely or at least partially.

Further possible improvements:

• add loop analysis (e.g. execfreq of libfirm) to inlining heuristics

Furthermore, the PR adds dead code elimination based on the call graph, which is directly integrated into Optimizer. This is especially useful in combination with the inliner, which often "kills" many functions during the inlining passes.

Note that in principal, the inliner might increase the compilation time significantly. However, based on some manual testing, the only test case that compiles much slower (about 3 times slower) at the moment seems to be the raytracer.

This PR introduces an interface for global optimizations (i.e. optimizations that work on the entire program instead of a single graph). A call graph is also implemented to query calling-realtionships between functions and to detect recursions.

Standard library calls are now a special construct without System or System.out/System.in being defined on its own. The following code yields "System cannot be resolved":

// inside some method
if (System.out == null) {
  ...

detailed changes:

• remove global variable System
• change StandardLibrary to include only names and method definitions
• explicitly check method invocations to identify standard library calls
• allow removing the object of a method invocation
• add tests for standard library calls

This branch is intended to collect some ideas for benchmarks.

If you want to see a really huge difference between -O1 and -O0, check out the AbstractedMath benchmark :smile:

This PR implements an optimization that tries to unroll loops when the number of iterations is known at compile time. Currently loops can only be unrolled by factors that evenly divide the number of iterations.

This PR implements an analysis for a number of possible attributes of functions and uses the results to make some optimizations regarding calls to pure and const functions.

• Calls to const functions are completely removed from the memory chain.
• Unused calls to pure functions are removed from the graph (this also includes malloc-like functions).
• Calls to pure or const functions are unpinned so that they're free to move between blocks.

On it's own, this optimization will only have a very minor performance impact. It will however open up opportunities for improvements to other optimizations. For example, certain function calls may be optimized as part of CSE, loop-invariant code motion, or a load-store optimization.

This PR seeks to improve our handling of division and modulus operations. The goal is to check for the edge case of INT_MIN (/|%) -1 explicitly and to handle it separately. We will then be free to use 32-bit instead of 64-bit divisions.

• [x] Generate the required Firm graphs during transformation
• [x] Switch to double-word division during register allocation
• [x] Update strength reductions to work with the new graphs

It would improve the detailed name and type analysis, if we were able to report more than one error. The necessary changes include moving from exception throwing to collecting errors (easy), as well as taking into account that reporting an error would not end the method immediately, potentialy causing follow-up errors (more complicated).

The value of an integer should not be restricted in the Lexer, therefore any integer (that is reasonable to store in the memory, ~1000 characters at least) should be accepted by the Lexer.

Current behaviour: error: [...] integer literal too large