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 | |
8 | namespace triton{ |
9 | namespace ir{ |
10 | |
11 | std::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 | |
40 | std::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 | |
46 | void 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 | |
55 | void 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 | |
62 | void 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 |