1#include <stack>
2#include <iostream>
3#include "triton/ir/utils.h"
4#include "triton/ir/basic_block.h"
5#include "triton/ir/function.h"
6#include "triton/ir/module.h"
7
8namespace triton{
9namespace ir{
10
11std::vector<basic_block*> cfg::post_order(function* fn) {
12 std::stack<basic_block*> stack;
13 std::set<basic_block*> visited;
14 std::vector<basic_block*> result;
15 // initialize stack
16 for(ir::basic_block* block: fn->blocks())
17 if(block->get_predecessors().empty()){
18 stack.push(block);
19 visited.insert(block);
20 }
21 // DFS
22 while(!stack.empty()) {
23 basic_block* current = stack.top();
24 bool tail = true;
25 for(basic_block* succ: current->get_successors())
26 if(visited.find(succ) == visited.end()){
27 stack.push(succ);
28 visited.insert(succ);
29 tail = false;
30 break;
31 }
32 if(tail){
33 stack.pop();
34 result.push_back(current);
35 }
36 }
37 return result;
38}
39
40std::vector<basic_block*> cfg::reverse_post_order(function* fn) {
41 auto result = post_order(fn);
42 std::reverse(result.begin(), result.end());
43 return result;
44}
45
46void for_each_instruction_backward(module &mod, const std::function<void (instruction *)> &do_work) {
47 for(ir::function *fn: mod.get_function_list())
48 for(ir::basic_block *block: cfg::post_order(fn)){
49 auto inst_list = block->get_inst_list();
50 for(auto it = inst_list.rbegin(); it != inst_list.rend() ; it++)
51 do_work(*it);
52 }
53}
54
55void for_each_instruction(module &mod, const std::function<void (instruction *)> &do_work) {
56 for(ir::function *fn: mod.get_function_list())
57 for(ir::basic_block *block: cfg::reverse_post_order(fn))
58 for(ir::instruction *i: block->get_inst_list())
59 do_work(i);
60}
61
62void for_each_value(module &mod, const std::function<void (value *)> &do_work) {
63 std::set<ir::value*> seen;
64 for(ir::function *fn: mod.get_function_list())
65 for(ir::basic_block *block: cfg::reverse_post_order(fn))
66 for(ir::instruction *i: block->get_inst_list()){
67 for(ir::value *op: i->ops()){
68 if(seen.insert(op).second)
69 do_work(op);
70 }
71 if(seen.insert(i).second)
72 do_work(i);
73 }
74}
75
76}
77}
78