optimize.c

   1 // SPDX-License-Identifier: MIT
   2 //
   3 // Copyright (C) 2004 Linus Torvalds
   4 // Copyright (C) 2004 Christopher Li
   5
   6 ///
   7 // Optimization main loop
   8 // ----------------------
   9
  10 #include <assert.h>
  11 #include "optimize.h"
  12 #include "flowgraph.h"
  13 #include "linearize.h"
  14 #include "liveness.h"
  15 #include "simplify.h"
  16 #include "flow.h"
  17 #include "cse.h"
  18 #include "ir.h"
  19 #include "ssa.h"
  20
  21 int repeat_phase;
  22
  23 static void clear_symbol_pseudos(struct entrypoint *ep)
  24 {
  25         pseudo_t pseudo;
  26
  27         FOR_EACH_PTR(ep->accesses, pseudo) {
  28                 pseudo->sym->pseudo = NULL;
  29         } END_FOR_EACH_PTR(pseudo);
  30 }
  31
  32
  33 static void clean_up_insns(struct entrypoint *ep)
  34 {
  35         struct basic_block *bb;
  36
  37         FOR_EACH_PTR(ep->bbs, bb) {
  38                 struct instruction *insn;
  39                 FOR_EACH_PTR(bb->insns, insn) {
  40                         if (!insn->bb)
  41                                 continue;
  42                         repeat_phase |= simplify_instruction(insn);
  43                         if (!insn->bb)
  44                                 continue;
  45                         assert(insn->bb == bb);
  46                         cse_collect(insn);
  47                 } END_FOR_EACH_PTR(insn);
  48         } END_FOR_EACH_PTR(bb);
  49 }
  50
  51 static void cleanup_cfg(struct entrypoint *ep)
  52 {
  53         kill_unreachable_bbs(ep);
  54         domtree_build(ep);
  55 }
  56
  57 ///
  58 // optimization main loop
  59 void optimize(struct entrypoint *ep)
  60 {
  61         if (fdump_ir & PASS_LINEARIZE)
  62                 show_entry(ep);
  63
  64         /*
  65          * Do trivial flow simplification - branches to
  66          * branches, kill dead basicblocks etc
  67          */
  68         kill_unreachable_bbs(ep);
  69         ir_validate(ep);
  70
  71         cfg_postorder(ep);
  72         if (simplify_cfg_early(ep))
  73                 kill_unreachable_bbs(ep);
  74         ir_validate(ep);
  75
  76         domtree_build(ep);
  77
  78         /*
  79          * Turn symbols into pseudos
  80          */
  81         if (fpasses & PASS_MEM2REG)
  82                 ssa_convert(ep);
  83         ir_validate(ep);
  84         if (fdump_ir & PASS_MEM2REG)
  85                 show_entry(ep);
  86
  87         if (!(fpasses & PASS_OPTIM))
  88                 return;
  89 repeat:
  90         /*
  91          * Remove trivial instructions, and try to CSE
  92          * the rest.
  93          */
  94         do {
  95                 simplify_memops(ep);
  96                 do {
  97                         repeat_phase = 0;
  98                         clean_up_insns(ep);
  99                         if (repeat_phase & REPEAT_CFG_CLEANUP)
 100                                 kill_unreachable_bbs(ep);
 101
 102                         cse_eliminate(ep);
 103                         simplify_memops(ep);
 104                 } while (repeat_phase);
 105                 pack_basic_blocks(ep);
 106                 if (repeat_phase & REPEAT_CFG_CLEANUP)
 107                         cleanup_cfg(ep);
 108         } while (repeat_phase);
 109
 110         vrfy_flow(ep);
 111
 112         /* Cleanup */
 113         clear_symbol_pseudos(ep);
 114
 115         /* And track pseudo register usage */
 116         track_pseudo_liveness(ep);
 117
 118         /*
 119          * Some flow optimizations can only effectively
 120          * be done when we've done liveness analysis. But
 121          * if they trigger, we need to start all over
 122          * again
 123          */
 124         if (simplify_flow(ep)) {
 125                 clear_liveness(ep);
 126                 if (repeat_phase & REPEAT_CFG_CLEANUP)
 127                         cleanup_cfg(ep);
 128                 goto repeat;
 129         }
 130
 131         /* Finally, add deathnotes to pseudos now that we have them */
 132         if (dbg_dead)
 133                 track_pseudo_death(ep);
 134 }