kit

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

pass_loop.c (3376B)

      1 #include <string.h>
      2 
      3 #include "core/arena.h"
      4 #include "opt/opt_internal.h"
      5 
      6 static void loop_body_mark(u32* mark, u32 gen, u32* body_list, u32* nbody,
      7                            u32 b) {
      8   if (mark[b] == gen) return;
      9   mark[b] = gen;
     10   body_list[(*nbody)++] = b;
     11 }
     12 
     13 static void loop_mark_body(Func* f, const u8* visited, u32 header, u32 latch,
     14                            u32* mark, u32 gen, u32* body_list, u32* nbody,
     15                            u32* stack) {
     16   u32 sp = 0;
     17   loop_body_mark(mark, gen, body_list, nbody, header);
     18   if (mark[latch] != gen) {
     19     loop_body_mark(mark, gen, body_list, nbody, latch);
     20     stack[sp++] = latch;
     21   }
     22 
     23   while (sp) {
     24     u32 b = stack[--sp];
     25     if (b == header) continue;
     26     Block* bl = &f->blocks[b];
     27     for (u32 p = 0; p < bl->npreds; ++p) {
     28       u32 pred = bl->preds[p];
     29       if (pred >= f->nblocks || !visited[pred] || mark[pred] == gen) continue;
     30       loop_body_mark(mark, gen, body_list, nbody, pred);
     31       stack[sp++] = pred;
     32     }
     33   }
     34 }
     35 
     36 static u32 loop_frequency(u8 depth) {
     37   u8 capped = depth > 10 ? 10 : depth;
     38   return 1u << capped;
     39 }
     40 
     41 void opt_build_loop_tree(Func* f) {
     42   if (!f) return;
     43   opt_analysis_invalidate(f, OPT_ANALYSIS_LOOP);
     44   for (u32 b = 0; b < f->nblocks; ++b) {
     45     f->blocks[b].loop_depth = 0;
     46     f->blocks[b].frequency = 1;
     47   }
     48   if (f->nblocks == 0 || f->entry >= f->nblocks) {
     49     opt_analysis_mark_valid(f, OPT_ANALYSIS_LOOP);
     50     return;
     51   }
     52 
     53   OptAnalysis a;
     54   memset(&a, 0, sizeof a);
     55   opt_analysis_build_dominators(f, &a);
     56   if (a.npo == 0) {
     57     opt_analysis_mark_valid(f, OPT_ANALYSIS_LOOP);
     58     return;
     59   }
     60 
     61   u32* first_edge = arena_array(f->arena, u32, f->nblocks);
     62   for (u32 b = 0; b < f->nblocks; ++b) first_edge[b] = UINT32_MAX;
     63   u32 max_edges = 0;
     64   for (u32 b = 0; b < f->nblocks; ++b)
     65     if (a.reachable[b]) max_edges += f->blocks[b].nsucc;
     66   u32* edge_latch = arena_array(f->arena, u32, max_edges ? max_edges : 1u);
     67   u32* edge_next = arena_array(f->arena, u32, max_edges ? max_edges : 1u);
     68   u32 nedges = 0;
     69 
     70   for (u32 latch = 0; latch < f->nblocks; ++latch) {
     71     if (!a.reachable[latch]) continue;
     72     Block* lb = &f->blocks[latch];
     73     for (u32 s = 0; s < lb->nsucc; ++s) {
     74       u32 header = lb->succ[s];
     75       if (header >= f->nblocks || !a.reachable[header]) continue;
     76       if (!opt_analysis_dominates(&a, header, latch)) continue;
     77       edge_latch[nedges] = latch;
     78       edge_next[nedges] = first_edge[header];
     79       first_edge[header] = nedges++;
     80     }
     81   }
     82 
     83   u32* mark = arena_zarray(f->arena, u32, f->nblocks);
     84   u32* body_list = arena_array(f->arena, u32, f->nblocks);
     85   u32* stack = arena_array(f->arena, u32, f->nblocks);
     86   u32 gen = 1;
     87 
     88   for (u32 header = 0; header < f->nblocks; ++header) {
     89     if (first_edge[header] == UINT32_MAX) continue;
     90     u32 nbody = 0;
     91     for (u32 e = first_edge[header]; e != UINT32_MAX; e = edge_next[e])
     92       loop_mark_body(f, a.reachable, header, edge_latch[e], mark, gen,
     93                      body_list, &nbody, stack);
     94     for (u32 i = 0; i < nbody; ++i) {
     95       u32 b = body_list[i];
     96       if (f->blocks[b].loop_depth < 31) ++f->blocks[b].loop_depth;
     97     }
     98     if (++gen == 0) {
     99       memset(mark, 0, f->nblocks * sizeof mark[0]);
    100       gen = 1;
    101     }
    102   }
    103 
    104   for (u32 b = 0; b < f->nblocks; ++b)
    105     f->blocks[b].frequency = loop_frequency(f->blocks[b].loop_depth);
    106   opt_analysis_mark_valid(f, OPT_ANALYSIS_LOOP);
    107 }