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