vm.fail
MLIR DAG rewriter w/ SSA IR, dominance and CFG analysis passes
1open Ir
2
3module IntMap = Map.Make(Int)
4module IntSet = Set.Make(Int)
5
6type cfg = {
7 blocks : block IntMap.t;
8 entry : value;
9}
10
11let build_cfg (f : func) =
12 let blocks = List.fold_left (fun m b -> IntMap.add b.id b m) IntMap.empty f.blocks in
13 let cfg = { blocks; entry = f.entry } in
14 let add_edges b =
15 let rec scan acc = function
16 | [] -> List.rev acc
17 | Ret _ :: _ -> List.rev acc
18 | BinOp (_, _, t) :: rest -> scan (t :: acc) rest
19 | Br t :: rest -> scan (t :: acc) rest
20 | CondBr (_, t1, t2) :: rest -> scan (t2 :: t1 :: acc) rest
21 | _ :: rest -> scan acc rest
22 in
23 b.succs <- scan [] b.insts
24 in
25 IntMap.iter (fun _ b -> add_edges b) blocks;
26 IntMap.iter (fun _ b ->
27 List.iter (fun s ->
28 try
29 let sb = IntMap.find s cfg.blocks in
30 sb.preds <- b.id :: sb.preds
31 with Not_found -> ()
32 ) b.succs
33 ) blocks;
34 cfg
35
36let get_block cfg id = IntMap.find id cfg.blocks
37let get_succs cfg id = (get_block cfg id).succs
38let get_preds cfg id = (get_block cfg id).preds