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
8namespace triton {
9namespace codegen{
10namespace transform{
11
12
13void 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