kit

kit
git clone https://git.ryansepassi.com/git/kit.git
Log | Files | Refs | README

pass_loop.c (2231B)

      1 #include <string.h>
      2 
      3 #include "core/arena.h"
      4 #include "opt/opt_internal.h"
      5 
      6 static void loop_mark_body(Func* f, const u8* visited, u32 header, u32 latch,
      7                            u8* body, u32* stack) {
      8   u32 sp = 0;
      9   if (!body[header]) body[header] = 1;
     10   if (!body[latch]) {
     11     body[latch] = 1;
     12     stack[sp++] = latch;
     13   }
     14 
     15   while (sp) {
     16     u32 b = stack[--sp];
     17     if (b == header) continue;
     18     Block* bl = &f->blocks[b];
     19     for (u32 p = 0; p < bl->npreds; ++p) {
     20       u32 pred = bl->preds[p];
     21       if (pred >= f->nblocks || !visited[pred] || body[pred]) continue;
     22       body[pred] = 1;
     23       stack[sp++] = pred;
     24     }
     25   }
     26 }
     27 
     28 static u32 loop_frequency(u8 depth) {
     29   u8 capped = depth > 10 ? 10 : depth;
     30   return 1u << capped;
     31 }
     32 
     33 void opt_build_loop_tree(Func* f) {
     34   if (!f) return;
     35   opt_analysis_invalidate(f, OPT_ANALYSIS_LOOP);
     36   for (u32 b = 0; b < f->nblocks; ++b) {
     37     f->blocks[b].loop_depth = 0;
     38     f->blocks[b].frequency = 1;
     39   }
     40   if (f->nblocks == 0 || f->entry >= f->nblocks) {
     41     opt_analysis_mark_valid(f, OPT_ANALYSIS_LOOP);
     42     return;
     43   }
     44 
     45   OptAnalysis a;
     46   memset(&a, 0, sizeof a);
     47   opt_analysis_build_dominators(f, &a);
     48   if (a.npo == 0) {
     49     opt_analysis_mark_valid(f, OPT_ANALYSIS_LOOP);
     50     return;
     51   }
     52 
     53   u8* body = arena_zarray(f->arena, u8, f->nblocks);
     54   u32* stack = arena_array(f->arena, u32, f->nblocks);
     55 
     56   for (u32 header = 0; header < f->nblocks; ++header) {
     57     if (!a.reachable[header]) continue;
     58     memset(body, 0, f->nblocks * sizeof body[0]);
     59     int has_loop = 0;
     60 
     61     for (u32 latch = 0; latch < f->nblocks; ++latch) {
     62       if (!a.reachable[latch]) continue;
     63       Block* lb = &f->blocks[latch];
     64       for (u32 s = 0; s < lb->nsucc; ++s) {
     65         if (lb->succ[s] != header) continue;
     66         if (!opt_analysis_dominates(&a, header, latch)) continue;
     67         has_loop = 1;
     68         loop_mark_body(f, a.reachable, header, latch, body, stack);
     69       }
     70     }
     71 
     72     if (!has_loop) continue;
     73     for (u32 b = 0; b < f->nblocks; ++b)
     74       if (body[b] && f->blocks[b].loop_depth < 31) ++f->blocks[b].loop_depth;
     75   }
     76 
     77   for (u32 b = 0; b < f->nblocks; ++b)
     78     f->blocks[b].frequency = loop_frequency(f->blocks[b].loop_depth);
     79   opt_analysis_mark_valid(f, OPT_ANALYSIS_LOOP);
     80 }