1/**
2 * Copyright (c) 2021-2022 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16#ifndef COMPILER_OPTIMIZER_ANALYSIS_RPO_H
17#define COMPILER_OPTIMIZER_ANALYSIS_RPO_H
18
19#include <algorithm>
20#include "utils/arena_containers.h"
21#include "optimizer/ir/marker.h"
22#include "optimizer/pass.h"
23
24namespace panda::compiler {
25class BasicBlock;
26class Graph;
27
28/**
29 * This class builds blocks list for reverse postorder traversal.
30 * There is an option to invalidate blocks list. In this case the list
31 * will be build from scratch after the next request for it.
32 * Also it provides methods for updating an existing tree.
33 */
34class Rpo : public Analysis {
35public:
36    explicit Rpo(Graph *graph);
37
38    NO_MOVE_SEMANTIC(Rpo);
39    NO_COPY_SEMANTIC(Rpo);
40    ~Rpo() override = default;
41
42    const char *GetPassName() const override
43    {
44        return "RPO";
45    }
46
47public:
48    void RemoveBasicBlock(BasicBlock *rm_block)
49    {
50        ASSERT_PRINT(IsValid(), "RPO is invalid");
51        auto it = std::find(rpo_vector_.begin(), rpo_vector_.end(), rm_block);
52        if (it != rpo_vector_.end()) {
53            rpo_vector_.erase(it);
54        }
55    }
56
57    void AddBasicBlockAfter(BasicBlock *cur_block, BasicBlock *new_block)
58    {
59        ASSERT_PRINT(IsValid(), "RPO is invalid");
60        auto it = std::find(rpo_vector_.begin(), rpo_vector_.end(), cur_block);
61        rpo_vector_.insert(it + 1, new_block);
62    }
63
64    void AddBasicBlockBefore(BasicBlock *cur_block, BasicBlock *new_block)
65    {
66        ASSERT_PRINT(IsValid(), "RPO is invalid");
67        auto it = std::find(rpo_vector_.begin(), rpo_vector_.end(), cur_block);
68        rpo_vector_.insert(it, new_block);
69    }
70
71    void AddVectorAfter(BasicBlock *cur_block, const ArenaVector<BasicBlock *> &new_vector)
72    {
73        ASSERT_PRINT(IsValid(), "RPO is invalid");
74        auto it = std::find(rpo_vector_.begin(), rpo_vector_.end(), cur_block);
75        rpo_vector_.insert(it + 1, new_vector.begin(), new_vector.end());
76    }
77
78    const ArenaVector<BasicBlock *> &GetBlocks() const
79    {
80        return rpo_vector_;
81    }
82
83private:
84    bool RunImpl() override;
85
86    void DFS(BasicBlock *block, size_t *blocks_count);
87
88private:
89    Marker marker_ {UNDEF_MARKER};
90    ArenaVector<BasicBlock *> rpo_vector_;
91};
92}  // namespace panda::compiler
93
94#endif  // COMPILER_OPTIMIZER_ANALYSIS_RPO_H
95