1#pragma once
2
3#include "taichi/ir/ir.h"
4#include "taichi/ir/mesh.h"
5#include "taichi/ir/pass.h"
6#include "taichi/analysis/gather_uniquely_accessed_pointers.h"
7#include "taichi/analysis/mesh_bls_analyzer.h"
8#include <atomic>
9#include <optional>
10#include <unordered_set>
11#include <unordered_map>
12
13namespace taichi::lang {
14
15class DiffRange {
16 private:
17 bool related_;
18
19 public:
20 int coeff;
21 int low, high;
22
23 DiffRange() : DiffRange(false, 0) {
24 }
25
26 DiffRange(bool related, int coeff) : DiffRange(related, 0, 0) {
27 TI_ASSERT(related == false);
28 }
29
30 DiffRange(bool related, int coeff, int low)
31 : DiffRange(related, coeff, low, low + 1) {
32 }
33
34 DiffRange(bool related, int coeff, int low, int high)
35 : related_(related), coeff(coeff), low(low), high(high) {
36 if (!related) {
37 this->low = this->high = 0;
38 }
39 }
40
41 bool related() const {
42 return related_;
43 }
44
45 bool linear_related() const {
46 return related_ && coeff == 1;
47 }
48
49 bool certain() {
50 TI_ASSERT(related_);
51 return high == low + 1;
52 }
53};
54
55enum AliasResult { same, uncertain, different };
56
57class ControlFlowGraph;
58
59// IR Analysis
60namespace irpass {
61namespace analysis {
62
63/**
64 * Checks if the two input statements may be aliased to the same address.
65 *
66 * @param val1
67 * The first statement to check.
68 *
69 * @param val2
70 * The second statement to check.
71 *
72 * @return
73 * The analyzed result.
74 */
75AliasResult alias_analysis(Stmt *var1, Stmt *var2);
76
77std::unique_ptr<ControlFlowGraph> build_cfg(IRNode *root);
78void check_fields_registered(IRNode *root);
79std::unique_ptr<IRNode> clone(IRNode *root);
80int count_statements(IRNode *root);
81
82/**
83 * Checks if the two input statements definitely point to the same address.
84 *
85 * @param val1
86 * The first statement to check.
87 *
88 * @param val2
89 * The second statement to check.
90 *
91 * @return
92 * Returns true iff. the two stmts definitely point to the same address.
93 */
94bool definitely_same_address(Stmt *var1, Stmt *var2);
95
96std::unordered_set<Stmt *> detect_fors_with_break(IRNode *root);
97std::unordered_set<Stmt *> detect_loops_with_continue(IRNode *root);
98std::unordered_map<Stmt *, std::vector<std::pair<Stmt *, int>>>
99gather_statement_usages(IRNode *root);
100std::unordered_set<Stmt *> gather_immutable_local_vars(IRNode *root);
101std::unordered_set<SNode *> gather_deactivations(IRNode *root);
102std::pair<std::unordered_set<SNode *>, std::unordered_set<SNode *>>
103gather_snode_read_writes(IRNode *root);
104std::vector<Stmt *> gather_statements(IRNode *root,
105 const std::function<bool(Stmt *)> &test);
106void gather_uniquely_accessed_bit_structs(IRNode *root, AnalysisManager *amgr);
107std::pair<std::unordered_map<const SNode *, GlobalPtrStmt *>,
108 std::unordered_map<int, ExternalPtrStmt *>>
109gather_uniquely_accessed_pointers(IRNode *root);
110std::unique_ptr<std::unordered_set<AtomicOpStmt *>> gather_used_atomics(
111 IRNode *root);
112stmt_refs get_load_pointers(Stmt *load_stmt);
113
114Stmt *get_store_data(Stmt *store_stmt) noexcept;
115stmt_refs get_store_destination(Stmt *store_stmt) noexcept;
116bool has_store_or_atomic(IRNode *root, const std::vector<Stmt *> &vars);
117std::pair<bool, Stmt *> last_store_or_atomic(IRNode *root, Stmt *var);
118
119/**
120 * Checks if the two input statements may point to the same address.
121 *
122 * @param val1
123 * The first statement to check.
124 *
125 * @param val2
126 * The second statement to check.
127 *
128 * @return
129 * Returns false iff. the two stmts are definitely not aliased.
130 */
131bool maybe_same_address(Stmt *var1, Stmt *var2);
132
133/**
134 * Test if root1 and root2 are the same, i.e., have the same type,
135 * the same operands, the same fields, and the same containing statements.
136 *
137 * @param root1
138 * The first root to check.
139 *
140 * @param root2
141 * The second root to check.
142 *
143 * @param id_map
144 * If id_map is std::nullopt by default, two operands are considered
145 * the same if they have the same id and do not belong to either root,
146 * or they belong to root1 and root2 at the same position in the roots.
147 * Otherwise, this function also recursively check the operands until
148 * ids in the id_map are reached.
149 */
150bool same_statements(
151 IRNode *root1,
152 IRNode *root2,
153 const std::optional<std::unordered_map<int, int>> &id_map = std::nullopt);
154
155/**
156 * Test if stmt1 and stmt2 definitely have the same value.
157 * Any global fields can be modified between stmt1 and stmt2.
158 *
159 * @param id_map
160 * Same as in same_statements(root1, root2, id_map).
161 */
162bool same_value(
163 Stmt *stmt1,
164 Stmt *stmt2,
165 const std::optional<std::unordered_map<int, int>> &id_map = std::nullopt);
166
167DiffRange value_diff_loop_index(Stmt *stmt, Stmt *loop, int index_id);
168
169/**
170 * Result of the value_diff_ptr_index pass.
171 */
172struct DiffPtrResult {
173 // Whether the difference of the checked statements is certain.
174 bool is_diff_certain{false};
175 // The difference of the value of two statements (i.e. val1 - val2). This is
176 // meaningful only when |is_diff_certain| is true.
177 int diff_range{0};
178
179 static DiffPtrResult make_certain(int diff) {
180 return DiffPtrResult{/*is_diff_certain=*/true, /*diff_range=*/diff};
181 }
182 static DiffPtrResult make_uncertain() {
183 return DiffPtrResult{/*is_diff_certain=*/false, /*diff_range=*/0};
184 }
185};
186
187/**
188 * Checks if the difference of the value of the two statements is certain.
189 *
190 * @param val1
191 * The first statement to check.
192 *
193 * @param val2
194 * The second statement to check.
195 */
196DiffPtrResult value_diff_ptr_index(Stmt *val1, Stmt *val2);
197
198std::unordered_set<Stmt *> constexpr_prop(
199 Block *block,
200 std::function<bool(Stmt *)> is_const_seed);
201
202void verify(IRNode *root);
203
204// Mesh Related.
205void gather_meshfor_relation_types(IRNode *node);
206std::pair</* owned= */ std::unordered_set<mesh::MeshElementType>,
207 /* total= */ std::unordered_set<mesh::MeshElementType>>
208gather_mesh_thread_local(OffloadedStmt *offload, const CompileConfig &config);
209std::unique_ptr<MeshBLSCaches> initialize_mesh_local_attribute(
210 OffloadedStmt *offload,
211 bool auto_mesh_local,
212 const CompileConfig &config);
213
214} // namespace analysis
215} // namespace irpass
216} // namespace taichi::lang
217