1 /**
2 * Copyright 2024 Huawei Technologies Co., Ltd
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16 #include "pipeline/jit/pi/graph_capture/local_liveness.h"
17 #include <algorithm>
18 #include <memory>
19 #include <utility>
20 #include "pipeline/jit/pi/graph_capture/graph.h"
21 #include "utils/log_adapter.h"
22
23 namespace mindspore {
24 namespace pijit {
25
CollectAlive(int start_bci) const26 BitMap Liveness::CollectAlive(int start_bci) const {
27 Block *cur = cfg_->GetBlockByBci(start_bci);
28 if (start_bci == cur->begin_ci()) {
29 return alive_[cur->id()];
30 }
31 BitMap read(cfg_->GetLocalCount());
32 BitMap write(cfg_->GetLocalCount());
33 for (int bci = start_bci; bci < cur->end_ci(); ++bci) {
34 Liveness::BuildRW(*cfg_->instr_pool()[bci], &read, &write);
35 }
36 for (const auto &i : cur->succ_bbs()) {
37 read.Or(alive_[i->id()]);
38 }
39 read.Diff(write);
40 return read;
41 }
42
BuildRW(const Instr & instr,BitMap * read,BitMap * write)43 void Liveness::BuildRW(const Instr &instr, BitMap *read, BitMap *write) {
44 if (instr.op() == STORE_FAST || instr.op() == DELETE_FAST) {
45 if (!read->Get(instr.arg())) {
46 write->Set(instr.arg());
47 }
48 return;
49 }
50 if (instr.op() == LOAD_FAST) {
51 if (!write->Get(instr.arg())) {
52 read->Set(instr.arg());
53 }
54 return;
55 }
56 }
57
Init()58 void Liveness::Init() {
59 const auto &bb = cfg_->bb_pool();
60 int block_count = SizeToInt(bb.size());
61 read_.resize(block_count, BitMap(cfg_->GetLocalCount()));
62 write_.resize(block_count, BitMap(cfg_->GetLocalCount()));
63 alive_.resize(block_count, BitMap(cfg_->GetLocalCount()));
64 alive_effect_.resize(block_count, BitMap(cfg_->GetLocalCount()));
65
66 // generate read write for each block
67 for (const auto &block : cfg_->bb_pool()) {
68 int id = SizeToInt(block->id());
69 for (int bci = block->begin_ci(); bci != block->end_ci(); ++bci) {
70 Liveness::BuildRW(*cfg_->instr_pool()[bci], &read_[id], &write_[id]);
71 }
72 }
73
74 // reverse traversal each block, generate alive effect of previous block, and propagate alive to previous
75 std::vector<Block *> list;
76 std::transform(bb.begin(), bb.end(), std::back_inserter(list), [](const auto &i) { return i.get(); });
77 while (!list.empty()) {
78 Block *cur = list.back();
79 list.pop_back();
80 Propagate(cur, &list);
81 }
82 }
83
84 /**
85 * liveness propagate for each block.
86 * merge alive to each previous block, it is previous block end alive effect.
87 * merge alive effect to alive, difference block write(kill), merge block read(generate),
88 * it is current block start alive.
89 */
Propagate(Block * cur,std::vector<Block * > * list)90 void Liveness::Propagate(Block *cur, std::vector<Block *> *list) {
91 int index = SizeToInt(cur->id());
92 alive_[index].Or(alive_effect_[index]);
93 alive_[index].Diff(write_[index]);
94 alive_[index].Or(read_[index]);
95
96 for (auto i : cur->pred_bbs()) {
97 int next = SizeToInt(i->id());
98 if (alive_effect_[next].OrWithChange(alive_[index])) {
99 list->push_back(i);
100 }
101 }
102 }
103
104 } // namespace pijit
105 } // namespace mindspore
106