optimize.c

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