1 | #include "triton/codegen/transform/dce.h" |
---|---|
2 | #include "triton/ir/function.h" |
3 | #include "triton/ir/basic_block.h" |
4 | #include "triton/ir/module.h" |
5 | #include "triton/ir/utils.h" |
6 | #include <iostream> |
7 | |
8 | namespace triton { |
9 | namespace codegen{ |
10 | namespace transform{ |
11 | |
12 | |
13 | void dce::run(ir::module &mod) { |
14 | std::list<ir::instruction*> work_list; |
15 | std::set<ir::instruction*> marked; |
16 | |
17 | // initialize work-list |
18 | for(ir::function *fn: mod.get_function_list()){ |
19 | std::vector<ir::basic_block*> rpo = ir::cfg::reverse_post_order(fn); |
20 | // iterate through blocks |
21 | for(ir::basic_block *block: rpo) |
22 | for(ir::instruction *i: block->get_inst_list()){ |
23 | switch(i->get_id()){ |
24 | case ir::INST_RETURN: |
25 | case ir::INST_UNCOND_BRANCH: |
26 | case ir::INST_COND_BRANCH: |
27 | case ir::INST_UNMASKED_STORE: |
28 | case ir::INST_MASKED_STORE: |
29 | case ir::INST_ATOMIC_CAS: |
30 | case ir::INST_ATOMIC_RMW: |
31 | case ir::INST_ATOMIC_EXCH: |
32 | case ir::INST_CALL: |
33 | case ir::INST_LAUNCH: |
34 | case ir::INST_BARRIER: { |
35 | work_list.push_back(i); |
36 | marked.insert(i); |
37 | break; |
38 | } |
39 | default: |
40 | break; |
41 | } |
42 | } |
43 | } |
44 | |
45 | // mark -- ignore branches |
46 | while(!work_list.empty()){ |
47 | ir::instruction* current = work_list.back(); |
48 | work_list.pop_back(); |
49 | // mark instruction operands |
50 | for(ir::value* op: current->ops()) { |
51 | if(auto *i = dynamic_cast<ir::instruction*>(op)){ |
52 | if(marked.insert(i).second) |
53 | work_list.push_back(i); |
54 | } |
55 | } |
56 | // TODO: mark last intstruction of current's reverse-dominance frontier |
57 | } |
58 | |
59 | // sweep -- delete non-branch unmarked instructions |
60 | std::vector<ir::instruction*> to_delete; |
61 | for(ir::function *fn: mod.get_function_list()){ |
62 | std::vector<ir::basic_block*> rpo = ir::cfg::reverse_post_order(fn); |
63 | // iterate through blocks |
64 | for(ir::basic_block *block: rpo) |
65 | for(ir::instruction *i: block->get_inst_list()){ |
66 | if(marked.find(i) == marked.end()) |
67 | to_delete.push_back(i); |
68 | } |
69 | } |
70 | |
71 | |
72 | // delete |
73 | for(ir::instruction* i: to_delete) |
74 | i->erase_from_parent(); |
75 | } |
76 | |
77 | } |
78 | } |
79 | } |
80 |