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                 //ir_validate(ep);
  79                 do {
  80                         repeat_phase = 0;
  81                         clean_up_insns(ep);
  82                         if (repeat_phase & REPEAT_CFG_CLEANUP)
  83                                 kill_unreachable_bbs(ep);
  84 
  85                         cse_eliminate(ep);
  86 
  87                         if (repeat_phase & REPEAT_SYMBOL_CLEANUP)
  88                                 simplify_memops(ep);
  89                         //ir_validate(ep);
  90                 } while (repeat_phase);
  91                 pack_basic_blocks(ep);
  92                 //ir_validate(ep);
  93                 if (repeat_phase & REPEAT_CFG_CLEANUP)
  94                         kill_unreachable_bbs(ep);
  95                 //ir_validate(ep);
  96         } while (repeat_phase);
  97         //ir_validate(ep);
  98 
  99         vrfy_flow(ep);
 100 
 101         /* Cleanup */
 102         clear_symbol_pseudos(ep);
 103 
 104         /* And track pseudo register usage */
 105         track_pseudo_liveness(ep);
 106 
 107         /*
 108          * Some flow optimizations can only effectively
 109          * be done when we've done liveness analysis. But
 110          * if they trigger, we need to start all over
 111          * again
 112          */
 113         if (simplify_flow(ep)) {
 114                 //ir_validate(ep);
 115                 clear_liveness(ep);
 116                 if (repeat_phase & REPEAT_CFG_CLEANUP)
 117                         kill_unreachable_bbs(ep);
 118                 goto repeat;
 119         }
 120         //ir_validate(ep);
 121 
 122         /* Finally, add deathnotes to pseudos now that we have them */
 123         if (dbg_dead)
 124                 track_pseudo_death(ep);
 125 }