Utilize dominators for constructing extended basic blocks

[jserv]

Quoted from Basic Blocks and CFG, the definition of extended basic block (EBB):

• Extended basic block a maximal sequence of instructions beginning with a leader that contains no join nodes other than its first node.
• Has a single entry, but possible multiple exit points.
• Some optimizations are more effective on extended basic blocks.

We can identify loops by using dominators:

• a node A in the flowgraph dominates a node B if every path from entry node to B includes A.
• This relations is antisymmetric, reflexive, and transitive.

back edge: An edge in the flow graph, whose head dominates its tail (example - edge from B6 to B4).

A loop consists of all nodes dominated by its entry node (head of the back edge) and having exactly one back edge in it.

Intercept contains an effective dominator implementation. See

• src/ir/dom.c
• src/codegen/opt/opt.c

Usage:

void codegen_optimise(CodegenContext *ctx) {
  opt_inline_global_vars(ctx);
  opt_analyse_functions(ctx);

  /// Optimise each function individually.
  do {
    foreach_ptr (IRFunction*, f, ctx->functions) {
      if (f->is_extern) continue;

      DominatorInfo dom = {0};
      do {
        build_dominator_tree(f, &dom, true);
        opt_reorder_blocks(f, &dom);
      } while (
          opt_const_folding_and_strengh_reduction(f) ||
          opt_dce(f) ||
          opt_mem2reg(f) ||
          opt_jump_threading(f, &dom) ||
          opt_tail_call_elim(f)
      );
      free_dominator_info(&dom);
    }
  }

  /// Cross-function optimisations.
  while (opt_inline_global_vars(ctx) || opt_analyse_functions(ctx));
}

Similarly, blink comes with an approach to detect loops during code generation.

[qwe661234]

Previously, we employed recursive jump translation to implement an extended basic block. Nevertheless, this approach makes it challenging to detect loop paths since we position the loop's entry block inside the block, and its using frequency would not be updated.

Based on this observation, it becomes necessary to eliminate the recursive jump translation. By doing so, we can accurately update the using frequency of the loop's entry block.

As shown in the performance results below, we gain 4% performance improvement when running coreMark and SciMark2 and lost 1% performance when running dhrysone.

• Intel Core i7-11700

Metric	origin	proposed	Speedup
CoreMark	2193.28	2289.26	+4%
SciMark2	13.45	18.48	+4%
Dhrystone	1413.11	1447.11	-1%

[jserv]

The effectiveness has been confirmed. We shall look for further faster approaches for loop detection.