Branch data Line data Source code
1 : : // Copyright (C) 2020-2025 Free Software Foundation, Inc.
2 : :
3 : : // This file is part of GCC.
4 : :
5 : : // GCC is free software; you can redistribute it and/or modify it under
6 : : // the terms of the GNU General Public License as published by the Free
7 : : // Software Foundation; either version 3, or (at your option) any later
8 : : // version.
9 : :
10 : : // GCC is distributed in the hope that it will be useful, but WITHOUT ANY
11 : : // WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 : : // FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 : : // for more details.
14 : :
15 : : // You should have received a copy of the GNU General Public License
16 : : // along with GCC; see the file COPYING3. If not see
17 : : // <http://www.gnu.org/licenses/>.
18 : :
19 : : #ifndef RUST_BIR_BASE_H
20 : : #define RUST_BIR_BASE_H
21 : :
22 : : #include "rust-bir-place.h"
23 : : #include "rust-bir-visitor.h"
24 : :
25 : : #include "polonius/rust-polonius-ffi.h"
26 : : #include "rust-tyty-variance-analysis.h"
27 : :
28 : : namespace Rust {
29 : :
30 : : namespace BIR {
31 : :
32 : : struct BasicBlock;
33 : : struct BasicBlockId;
34 : : using BasicBlocks = IndexVec<BasicBlockId, BasicBlock>;
35 : : class Statement;
36 : : class AbstractExpr;
37 : :
38 : : /** Unique identifier for a basic block in the BIR. */
39 : : struct BasicBlockId
40 : : {
41 : : uint32_t value;
42 : : // some overloads for comparision
43 : 8 : bool operator== (const BasicBlockId &rhs) const { return value == rhs.value; }
44 : 8 : bool operator!= (const BasicBlockId &rhs) const
45 : : {
46 : 8 : return !(operator== (rhs));
47 : : }
48 : : bool operator< (const BasicBlockId &rhs) const { return value < rhs.value; }
49 : : bool operator> (const BasicBlockId &rhs) const { return value > rhs.value; }
50 : : bool operator<= (const BasicBlockId &rhs) const { return !(operator> (rhs)); }
51 : : bool operator>= (const BasicBlockId &rhs) const { return !(operator< (rhs)); }
52 : : };
53 : :
54 : : static constexpr BasicBlockId INVALID_BB
55 : : = {std::numeric_limits<uint32_t>::max ()};
56 : : static constexpr BasicBlockId ENTRY_BASIC_BLOCK = {0};
57 : :
58 : : /**
59 : : * Top-level entity of the Borrow-checker IR (BIR).
60 : : * It represents a single function (method, closure, etc.), which is the
61 : : * basic unit of borrow-checking.
62 : : */
63 : : struct Function
64 : : {
65 : : PlaceDB place_db;
66 : : std::vector<PlaceId> arguments;
67 : : BasicBlocks basic_blocks;
68 : : FreeRegions universal_regions;
69 : : std::vector<std::pair<FreeRegion, FreeRegion>> universal_region_bounds;
70 : : std::unordered_map<Polonius::Origin, HIR::LifetimeParam *> region_hir_map;
71 : : location_t location;
72 : : };
73 : :
74 : : /** Single statement of BIR. */
75 : 2716 : class Statement
76 : : {
77 : : public:
78 : : enum class Kind
79 : : {
80 : : ASSIGNMENT, // <place> = <expr>
81 : : SWITCH, // switch <place>
82 : : RETURN, // return
83 : : GOTO, // goto
84 : : STORAGE_DEAD, // StorageDead(<place>)
85 : : STORAGE_LIVE, // StorageLive(<place>)
86 : : USER_TYPE_ASCRIPTION, // UserTypeAscription(<place>, <tyty>)
87 : : FAKE_READ,
88 : : };
89 : :
90 : : private:
91 : : Kind kind;
92 : : // ASSIGNMENT: lhs
93 : : // SWITCH: switch_val
94 : : // StorageDead/StorageLive: place
95 : : // otherwise: <unused>
96 : : PlaceId place;
97 : : // ASSIGNMENT: rhs
98 : : // otherwise: <unused>
99 : : std::unique_ptr<AbstractExpr> expr;
100 : : TyTy::BaseType *type;
101 : : // stores location of the actual expression from source code
102 : : // currently only available when kind is ASSIGNMENT | RETURN
103 : : // FIXME: Add location for other statement kinds
104 : : location_t location;
105 : :
106 : : public:
107 : 185 : static Statement make_assignment (PlaceId place, AbstractExpr *rhs,
108 : : location_t location)
109 : : {
110 : 185 : return Statement (Kind::ASSIGNMENT, place, rhs, nullptr, location);
111 : : }
112 : 7 : static Statement make_switch (PlaceId place)
113 : : {
114 : 7 : return Statement (Kind::SWITCH, place);
115 : : }
116 : 38 : static Statement make_return (location_t location)
117 : : {
118 : 38 : return Statement (Kind::RETURN, INVALID_PLACE, nullptr, nullptr, location);
119 : : }
120 : 8 : static Statement make_goto () { return Statement (Kind::GOTO); }
121 : 145 : static Statement make_storage_dead (PlaceId place)
122 : : {
123 : 145 : return Statement (Kind::STORAGE_DEAD, place);
124 : : }
125 : 159 : static Statement make_storage_live (PlaceId place)
126 : : {
127 : 159 : return Statement (Kind::STORAGE_LIVE, place);
128 : : }
129 : 0 : static Statement make_user_type_ascription (PlaceId place,
130 : : TyTy::BaseType *type)
131 : : {
132 : 0 : return Statement (Kind::USER_TYPE_ASCRIPTION, place, nullptr, type);
133 : : }
134 : 90 : static Statement make_fake_read (PlaceId place)
135 : : {
136 : 90 : return Statement (Kind::FAKE_READ, place);
137 : : }
138 : :
139 : : private:
140 : : // compelete constructor, used by make_* functions
141 : 632 : Statement (Kind kind, PlaceId place = INVALID_PLACE,
142 : : AbstractExpr *rhs = nullptr, TyTy::BaseType *type = nullptr,
143 : : location_t location = UNKNOWN_LOCATION)
144 : 632 : : kind (kind), place (place), expr (rhs), type (type), location (location)
145 : : {}
146 : :
147 : : public:
148 : 814 : WARN_UNUSED_RESULT Kind get_kind () const { return kind; }
149 : 586 : WARN_UNUSED_RESULT PlaceId get_place () const { return place; }
150 : 250 : WARN_UNUSED_RESULT AbstractExpr &get_expr () const { return *expr; }
151 : 0 : WARN_UNUSED_RESULT TyTy::BaseType *get_type () const { return type; }
152 : 30 : WARN_UNUSED_RESULT location_t get_location () const { return location; }
153 : : };
154 : :
155 : 162 : struct BasicBlock
156 : : {
157 : : // BIR "instructions".
158 : : std::vector<Statement> statements;
159 : : // A basic block can end with: goto, return or switch
160 : : std::vector<BasicBlockId> successors;
161 : :
162 : : public:
163 : : WARN_UNUSED_RESULT bool is_terminated () const;
164 : :
165 : 10 : WARN_UNUSED_RESULT bool is_goto_terminated () const
166 : : {
167 : 10 : return is_terminated ()
168 : 10 : && statements.back ().get_kind () == Statement::Kind::GOTO;
169 : : }
170 : : };
171 : :
172 : : enum class ExprKind
173 : : {
174 : : INITIALIZER,
175 : : OPERATOR,
176 : : BORROW,
177 : : ASSIGNMENT,
178 : : CALL,
179 : : };
180 : :
181 : : // Rhs expression of BIR assignment statements (abstract).
182 : : class AbstractExpr : public Visitable
183 : : {
184 : : ExprKind kind;
185 : :
186 : : public:
187 : 185 : explicit AbstractExpr (ExprKind kind) : kind (kind) {}
188 : 65 : WARN_UNUSED_RESULT ExprKind get_kind () const { return kind; }
189 : :
190 : : virtual ~AbstractExpr () {}
191 : : };
192 : :
193 : : class InitializerExpr : public VisitableImpl<AbstractExpr, InitializerExpr>
194 : : {
195 : : std::vector<PlaceId> values;
196 : :
197 : : public:
198 : 6 : explicit InitializerExpr (std::vector<PlaceId> &&values)
199 : 6 : : VisitableImpl<AbstractExpr, InitializerExpr> (ExprKind::INITIALIZER),
200 : 6 : values (values)
201 : : {}
202 : :
203 : : public:
204 : : std::vector<PlaceId> &get_values () { return values; }
205 : 0 : WARN_UNUSED_RESULT const std::vector<PlaceId> &get_values () const
206 : : {
207 : 6 : return values;
208 : : }
209 : : };
210 : :
211 : : template <unsigned ARITY>
212 : : class Operator : public VisitableImpl<AbstractExpr, Operator<ARITY>>
213 : : {
214 : : std::array<PlaceId, ARITY> operands;
215 : :
216 : : public:
217 : 0 : explicit Operator (std::array<PlaceId, ARITY> &&operands)
218 : 0 : : VisitableImpl<AbstractExpr, Operator<ARITY>> (ExprKind::OPERATOR),
219 : 0 : operands (operands)
220 : : {}
221 : :
222 : : public:
223 : 0 : template <size_t I> WARN_UNUSED_RESULT PlaceId get_operand () const
224 : : {
225 : : static_assert (I < ARITY, "Index out of bounds");
226 : 0 : return operands[I];
227 : : }
228 : : };
229 : :
230 : : class BorrowExpr : public VisitableImpl<AbstractExpr, BorrowExpr>
231 : : {
232 : : PlaceId place;
233 : : LoanId loan;
234 : : Polonius::Origin origin;
235 : :
236 : : public:
237 : 55 : explicit BorrowExpr (PlaceId place, LoanId loan_id, Polonius::Origin lifetime)
238 : 55 : : VisitableImpl<AbstractExpr, BorrowExpr> (ExprKind::BORROW), place (place),
239 : 55 : loan (loan_id), origin (lifetime)
240 : : {}
241 : 55 : WARN_UNUSED_RESULT PlaceId get_place () const { return place; }
242 : 55 : WARN_UNUSED_RESULT LoanId get_loan_id () const { return loan; }
243 : 77 : WARN_UNUSED_RESULT Polonius::Origin get_origin () const { return origin; }
244 : : };
245 : :
246 : : /**
247 : : * This expression is only to be used inside the assignment statement and acts
248 : : * as identity wrapper for a place value. It is separated from `Operator<1>` to
249 : : * render it more explicitly in the dump.
250 : : */
251 : : class Assignment : public VisitableImpl<AbstractExpr, Assignment>
252 : : {
253 : : PlaceId rhs;
254 : :
255 : : public:
256 : 113 : explicit Assignment (PlaceId rhs)
257 : 113 : : VisitableImpl<AbstractExpr, Assignment> (ExprKind::ASSIGNMENT), rhs (rhs)
258 : : {}
259 : :
260 : : public:
261 : 113 : WARN_UNUSED_RESULT PlaceId get_rhs () const { return rhs; }
262 : : };
263 : :
264 : : class CallExpr final : public VisitableImpl<AbstractExpr, CallExpr>
265 : : {
266 : : std::vector<PlaceId> arguments;
267 : : PlaceId callable;
268 : :
269 : : public:
270 : 11 : explicit CallExpr (PlaceId callable, std::vector<PlaceId> &&arguments)
271 : 11 : : VisitableImpl (ExprKind::CALL), arguments (arguments), callable (callable)
272 : : {}
273 : :
274 : : public:
275 : 11 : WARN_UNUSED_RESULT const std::vector<PlaceId> &get_arguments () const
276 : : {
277 : 11 : return arguments;
278 : : }
279 : 11 : WARN_UNUSED_RESULT PlaceId get_callable () const { return callable; }
280 : : };
281 : :
282 : : inline bool
283 : 187 : BasicBlock::is_terminated () const
284 : : {
285 : 187 : if (statements.empty ())
286 : : return false;
287 : 172 : switch (statements.back ().get_kind ())
288 : : {
289 : : case Statement::Kind::GOTO:
290 : : case Statement::Kind::RETURN:
291 : : case Statement::Kind::SWITCH:
292 : : return true;
293 : 65 : case Statement::Kind::ASSIGNMENT:
294 : 65 : return statements.back ().get_expr ().get_kind () == ExprKind::CALL;
295 : : default:
296 : : return false;
297 : : }
298 : : }
299 : :
300 : : } // namespace BIR
301 : :
302 : : } // namespace Rust
303 : :
304 : : #endif // RUST_BIR_BASE_H
|