1 | #include <climits> |
2 | #include <iostream> |
3 | #include "triton/codegen/analysis/liveness.h" |
4 | #include "triton/codegen/analysis/layout.h" |
5 | #include "triton/ir/function.h" |
6 | #include "triton/ir/module.h" |
7 | #include "triton/ir/utils.h" |
8 | |
9 | namespace triton{ |
10 | namespace codegen{ |
11 | namespace analysis{ |
12 | |
13 | |
14 | void liveness::run(ir::module &mod) { |
15 | intervals_.clear(); |
16 | |
17 | std::map<ir::value*, std::set<shared_layout*>> layouts_map; |
18 | for(auto &x: layouts_->get_all()){ |
19 | shared_layout* layout = x.second->to_shared(); |
20 | if(!layout || layout->is_tmp()) |
21 | continue; |
22 | for(ir::value* v:layout->get_values()){ |
23 | layouts_map[v].insert(layout); |
24 | } |
25 | } |
26 | |
27 | |
28 | |
29 | std::map<ir::user*, std::set<shared_layout*>> live_in; |
30 | while(true){ |
31 | bool changed = false; |
32 | ir::instruction* last_inst = nullptr; |
33 | ir::for_each_instruction_backward(mod, [&](ir::instruction* i){ |
34 | // gen |
35 | std::set<shared_layout*> gen; |
36 | for(ir::value* v: i->ops()) |
37 | for(shared_layout* layout: layouts_map[v]) |
38 | gen.insert(layout); |
39 | // kill |
40 | std::set<shared_layout*> kill; |
41 | for(shared_layout* layout: layouts_map[i]) |
42 | kill.insert(layout); |
43 | // temporaries are handled separately |
44 | if(layouts_->has_tmp(i)){ |
45 | gen.insert(layouts_->get(layouts_->tmp(i))->to_shared()); |
46 | kill.insert(layouts_->get(layouts_->tmp(i))->to_shared()); |
47 | } |
48 | if(layouts_->has_tmp_index(i)){ |
49 | gen.insert(layouts_->get(layouts_->tmp_index(i))->to_shared()); |
50 | kill.insert(layouts_->get(layouts_->tmp_index(i))->to_shared()); |
51 | } |
52 | // live-out |
53 | std::set<shared_layout*> live_out; |
54 | std::vector<ir::instruction*> succs = {last_inst}; |
55 | if(i == i->get_parent()->get_inst_list().back()) |
56 | for(ir::basic_block* succ: i->get_parent()->get_successors()) |
57 | succs.push_back(succ->get_inst_list().front()); |
58 | for(ir::instruction* succ: succs) |
59 | for(shared_layout* layout: live_in[succ]) |
60 | if(!layout->is_tmp()) |
61 | live_out.insert(layout); |
62 | |
63 | // new sets |
64 | std::set<shared_layout*> live_out_minus_kill; |
65 | std::set_difference(live_out.begin(), live_out.end(), kill.begin(), kill.end(), |
66 | std::inserter(live_out_minus_kill, live_out_minus_kill.end())); |
67 | std::set<shared_layout*> new_live_in; |
68 | std::set_union(gen.begin(), gen.end(), live_out_minus_kill.begin(), live_out_minus_kill.end(), |
69 | std::inserter(new_live_in, new_live_in.end())); |
70 | |
71 | changed = changed || (new_live_in != live_in[i]); |
72 | live_in[i] = new_live_in; |
73 | last_inst = i; |
74 | }); |
75 | if(!changed) |
76 | break; |
77 | } |
78 | |
79 | // ir::for_each_instruction(mod, [&](ir::instruction* i){ |
80 | // i->print(std::cout); |
81 | // std::cout << " live_in: " << live_in[i].size() << std::endl; |
82 | // }); |
83 | |
84 | |
85 | |
86 | // Assigns index to each instruction |
87 | std::map<ir::value*, slot_index> indices; |
88 | slot_index index = 0; |
89 | ir::for_each_instruction(mod, [&](ir::instruction* instr){ |
90 | index += 1; |
91 | indices.insert({instr, index}); |
92 | }); |
93 | |
94 | |
95 | for(auto &x: layouts_->get_all()){ |
96 | shared_layout* layout = x.second->to_shared(); |
97 | if(layout) |
98 | intervals_[layout] = segment{INT32_MAX, 0}; |
99 | } |
100 | |
101 | for(auto& x: live_in) |
102 | for(shared_layout* layout: x.second) |
103 | intervals_[layout].start = std::min<int>(intervals_[layout].start, indices[x.first]); |
104 | |
105 | for(auto& x: live_in) |
106 | for(shared_layout* layout: x.second){ |
107 | intervals_[layout].end = std::max<int>(intervals_[layout].end, indices[x.first] + 1); |
108 | } |
109 | |
110 | |
111 | for(auto &x: layouts_->get_all()) { |
112 | shared_layout* layout = x.second->to_shared(); |
113 | if(!layout) |
114 | continue; |
115 | // std::cout << intervals_[layout].start << " " << intervals_[layout].end << std::endl; |
116 | } |
117 | |
118 | |
119 | |
120 | } |
121 | |
122 | } |
123 | } |
124 | } |
125 | |