https://gcc.gnu.org/g:dfafead7c2a5f94d62fdd995b626d5a7cd23aaf2
commit dfafead7c2a5f94d62fdd995b626d5a7cd23aaf2
Author: Jakub Dupak <d...@jakubdupak.com>
Date: Wed Oct 18 19:49:59 2023 +0200
borrowck: Create Borrow-checker IR (BIR)
gcc/rust/ChangeLog:
* checks/errors/borrowck/rust-borrow-checker.cc: Include to compile
new code.
* checks/errors/borrowck/rust-bir-place.h: New file.
* checks/errors/borrowck/rust-bir-visitor.h: New file.
* checks/errors/borrowck/rust-bir.h: New file.
Signed-off-by: Jakub Dupak <d...@jakubdupak.com>
Diff:
---
gcc/rust/checks/errors/borrowck/rust-bir-place.h | 257 +++++++++++++++++++++
gcc/rust/checks/errors/borrowck/rust-bir-visitor.h | 62 +++++
gcc/rust/checks/errors/borrowck/rust-bir.h | 200 ++++++++++++++++
.../checks/errors/borrowck/rust-borrow-checker.cc | 2 +
4 files changed, 521 insertions(+)
diff --git a/gcc/rust/checks/errors/borrowck/rust-bir-place.h
b/gcc/rust/checks/errors/borrowck/rust-bir-place.h
new file mode 100644
index 000000000000..ce32f9262ceb
--- /dev/null
+++ b/gcc/rust/checks/errors/borrowck/rust-bir-place.h
@@ -0,0 +1,257 @@
+// Copyright (C) 2020-2023 Free Software Foundation, Inc.
+
+// This file is part of GCC.
+
+// GCC is free software; you can redistribute it and/or modify it under
+// the terms of the GNU General Public License as published by the Free
+// Software Foundation; either version 3, or (at your option) any later
+// version.
+
+// GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+// WARRANTY; without even the implied warranty of MERCHANTABILITY or
+// FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+// for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with GCC; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+#ifndef RUST_BIR_PLACE_H
+#define RUST_BIR_PLACE_H
+
+#include <limits>
+#include "rust-mapping-common.h"
+#include "rust-system.h"
+#include "rust-tyty.h"
+
+namespace Rust {
+namespace BIR {
+
+/** A unique identifier for a place in the BIR. */
+using PlaceId = uint32_t;
+
+static constexpr PlaceId INVALID_PLACE = 0;
+static constexpr PlaceId RETURN_VALUE_PLACE = 1;
+static constexpr PlaceId FIRST_VARIABLE_PLACE = RETURN_VALUE_PLACE;
+
+/**
+ * A unique identifier for a lifetime in the BIR. Only to be used INTERNALLY.
+ */
+using LifetimeID = uint32_t;
+
+constexpr LifetimeID INVALID_LIFETIME_ID = 0;
+constexpr LifetimeID STATIC_LIFETIME_ID = 1;
+constexpr LifetimeID FIRST_NORMAL_LIFETIME_ID = 2;
+
+/** Representation of lifetimes in BIR. */
+struct Lifetime
+{
+ LifetimeID id = INVALID_LIFETIME_ID;
+
+ constexpr Lifetime (LifetimeID id) : id (id) {}
+ constexpr Lifetime (const Lifetime &) = default;
+ WARN_UNUSED_RESULT bool has_lifetime () const
+ {
+ return id != INVALID_LIFETIME_ID;
+ }
+ LifetimeID operator() () const { return id; }
+};
+constexpr Lifetime NO_LIFETIME = {INVALID_LIFETIME_ID};
+constexpr Lifetime STATIC_LIFETIME = {STATIC_LIFETIME_ID};
+
+/**
+ * Representation of lvalues and constants in BIR.
+ * See bir bir design notes (in this directory) and the Polonius book.
+ */
+struct Place
+{
+ enum Kind
+ {
+ INVALID,
+ VARIABLE,
+ TEMPORARY,
+ CONSTANT,
+ FIELD,
+ INDEX,
+ DEREF,
+ };
+
+ Kind kind;
+ uint32_t variable_or_field_index; // NodeId for VARIABLE
+ /** Data for traversing paths in the PlaceDB. */
+ struct Path
+ {
+ PlaceId parent = INVALID_PLACE;
+ PlaceId first_child = INVALID_PLACE;
+ PlaceId next_sibling = INVALID_PLACE;
+
+ Path (PlaceId parent, PlaceId first_child, PlaceId next_sibling)
+ : parent (parent), first_child (first_child), next_sibling (next_sibling)
+ {}
+ Path () = default;
+ } path;
+ /** Copy trait */
+ bool is_copy;
+ /** This place can be moved from safety. */
+ bool is_rvalue;
+ Lifetime lifetime;
+ TyTy::BaseType *tyty;
+
+ Place (Kind kind, uint32_t variable_or_field_index, const Path &path,
+ bool is_copy, bool is_rvalue, const Lifetime &lifetime,
+ TyTy::BaseType *tyty)
+ : kind (kind), variable_or_field_index (variable_or_field_index),
+ path (path), is_copy (is_copy), is_rvalue (is_rvalue),
+ lifetime (lifetime), tyty (tyty)
+ {}
+};
+
+/** Allocated places and keeps track of paths. */
+class PlaceDB
+{
+ // Possible optimizations: separate variables to speedup lookup.
+ std::vector<Place> places;
+ std::unordered_map<TyTy::BaseType *, PlaceId> constants_lookup;
+
+public:
+ PlaceDB ()
+ {
+ // Reserved index for invalid place.
+ places.push_back (
+ {Place::INVALID, 0, {}, false, false, NO_LIFETIME, nullptr});
+ }
+
+ Place &operator[] (PlaceId id) { return places.at (id); }
+ const Place &operator[] (PlaceId id) const { return places.at (id); }
+
+ size_t size () const { return places.size (); }
+
+ PlaceId add_place (Place place, PlaceId last_sibling = 0)
+ {
+ places.push_back (place);
+ PlaceId new_place = places.size () - 1;
+ if (last_sibling == 0)
+ {
+ places[place.path.parent].path.first_child = new_place;
+ }
+ else
+ {
+ places[last_sibling].path.next_sibling = new_place;
+ }
+ return new_place;
+ }
+
+ PlaceId add_variable (NodeId id, TyTy::BaseType *tyty)
+ {
+ return add_place (
+ {Place::VARIABLE, id, {}, is_type_copy (tyty), false, NO_LIFETIME, tyty},
+ 0);
+ }
+
+ PlaceId lookup_variable (NodeId id)
+ {
+ PlaceId current = FIRST_VARIABLE_PLACE;
+
+ while (current != places.size ())
+ {
+ if (places[current].kind == Place::VARIABLE
+ && places[current].variable_or_field_index == id)
+ return current;
+ current++;
+ }
+ return INVALID_PLACE;
+ };
+
+ PlaceId add_temporary (TyTy::BaseType *tyty)
+ {
+ return add_place (
+ {Place::TEMPORARY, 0, {}, is_type_copy (tyty), false, NO_LIFETIME, tyty},
+ 0);
+ }
+
+ WARN_UNUSED_RESULT PlaceId lookup_or_add_path (Place::Kind kind,
+ TyTy::BaseType *tyty,
+ PlaceId parent, size_t id = 0)
+ {
+ PlaceId current = 0;
+ if (parent < places.size ())
+ {
+ current = places[parent].path.first_child;
+ while (current != 0)
+ {
+ if (places[current].kind == kind
+ && places[current].variable_or_field_index == id)
+ {
+ rust_assert (places[current].tyty->is_equal (*tyty));
+ return current;
+ }
+ current = places[current].path.next_sibling;
+ }
+ }
+ return add_place (
+ {kind, id, {parent, 0, 0}, is_type_copy (tyty), false, NO_LIFETIME,
tyty},
+ current);
+ }
+
+ PlaceId get_constant (TyTy::BaseType *tyty)
+ {
+ auto lookup = constants_lookup.find (tyty);
+ if (lookup != constants_lookup.end ())
+ return lookup->second;
+ Lifetime lifetime
+ = tyty->get_kind () == TyTy::REF ? STATIC_LIFETIME : NO_LIFETIME;
+ Place place
+ = {Place::CONSTANT, 0, {}, is_type_copy (tyty), false, lifetime, tyty};
+ places.push_back (place);
+ return places.size () - 1;
+ }
+
+private:
+ static bool is_type_copy (TyTy::BaseType *ty)
+ {
+ switch (ty->get_kind ())
+ {
+ case TyTy::REF:
+ case TyTy::POINTER:
+ case TyTy::SLICE:
+ case TyTy::BOOL:
+ case TyTy::CHAR:
+ case TyTy::INT:
+ case TyTy::UINT:
+ case TyTy::FLOAT:
+ case TyTy::USIZE:
+ case TyTy::ISIZE:
+ case TyTy::FNPTR:
+ case TyTy::FNDEF:
+ case TyTy::NEVER:
+ return true;
+ case TyTy::TUPLE: {
+ auto &fields = ty->as<TyTy::TupleType> ()->get_fields ();
+ return std::all_of (fields.begin (), fields.end (),
+ [] (const TyTy::TyVar &field) {
+ return is_type_copy (field.get_tyty ());
+ });
+ }
+ case TyTy::ARRAY: {
+ return is_type_copy (ty->as<TyTy::ArrayType> ()->get_element_type ());
+ }
+ case TyTy::INFER:
+ case TyTy::PARAM:
+ case TyTy::ERROR:
+ case TyTy::STR:
+ case TyTy::PLACEHOLDER:
+ rust_unreachable ();
+ case TyTy::ADT: // TODO: check trait
+ case TyTy::PROJECTION: // TODO: DUNNO
+ case TyTy::CLOSURE: // TODO: DUNNO
+ case TyTy::DYNAMIC: // TODO: dunno
+ return false;
+ }
+ rust_unreachable ();
+ }
+};
+
+} // namespace BIR
+} // namespace Rust
+
+#endif // RUST_BIR_PLACE_H
diff --git a/gcc/rust/checks/errors/borrowck/rust-bir-visitor.h
b/gcc/rust/checks/errors/borrowck/rust-bir-visitor.h
new file mode 100644
index 000000000000..48b67c0fead4
--- /dev/null
+++ b/gcc/rust/checks/errors/borrowck/rust-bir-visitor.h
@@ -0,0 +1,62 @@
+// Copyright (C) 2020-2023 Free Software Foundation, Inc.
+
+// This file is part of GCC.
+
+// GCC is free software; you can redistribute it and/or modify it under
+// the terms of the GNU General Public License as published by the Free
+// Software Foundation; either version 3, or (at your option) any later
+// version.
+
+// GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+// WARRANTY; without even the implied warranty of MERCHANTABILITY or
+// FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+// for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with GCC; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+#ifndef RUST_BIR_VISITOR_H
+#define RUST_BIR_VISITOR_H
+
+namespace Rust {
+namespace BIR {
+
+class Node;
+class InitializerExpr;
+template <unsigned N> class Operator;
+class Assignment;
+class BorrowExpr;
+class CallExpr;
+
+class Visitor
+{
+public:
+ virtual void visit (Node &node) = 0;
+ virtual void visit (InitializerExpr &expr) = 0;
+ virtual void visit (Operator<1> &expr) = 0;
+ virtual void visit (Operator<2> &expr) = 0;
+ virtual void visit (BorrowExpr &expr) = 0;
+ virtual void visit (Assignment &expr) = 0;
+ virtual void visit (CallExpr &expr) = 0;
+};
+
+class Visitable
+{
+public:
+ virtual void accept_vis (Visitor &visitor) = 0;
+};
+
+template <typename BASE, typename T> class VisitableImpl : public BASE
+{
+public:
+ void accept_vis (Visitor &visitor) override
+ {
+ visitor.visit (static_cast<T &> (*this));
+ }
+};
+
+} // namespace BIR
+} // namespace Rust
+
+#endif // RUST_BIR_VISITOR_H
diff --git a/gcc/rust/checks/errors/borrowck/rust-bir.h
b/gcc/rust/checks/errors/borrowck/rust-bir.h
new file mode 100644
index 000000000000..bcb32c9659b8
--- /dev/null
+++ b/gcc/rust/checks/errors/borrowck/rust-bir.h
@@ -0,0 +1,200 @@
+// Copyright (C) 2020-2023 Free Software Foundation, Inc.
+
+// This file is part of GCC.
+
+// GCC is free software; you can redistribute it and/or modify it under
+// the terms of the GNU General Public License as published by the Free
+// Software Foundation; either version 3, or (at your option) any later
+// version.
+
+// GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+// WARRANTY; without even the implied warranty of MERCHANTABILITY or
+// FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+// for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with GCC; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+#ifndef RUST_BIR_BASE_H
+#define RUST_BIR_BASE_H
+
+#include "rust-bir-place.h"
+#include "rust-bir-visitor.h"
+
+namespace Rust {
+
+namespace BIR {
+
+struct BasicBlock;
+class Node;
+class AbstractExpr;
+
+/**
+ * Top-level entity of the Borrow-checker IR (BIR).
+ * It represents a single function (method, closure, etc.), which is also the
+ * basic unit of Polonius borrow-checking.
+ */
+struct Function
+{
+ PlaceDB place_db;
+ std::vector<PlaceId> arguments; // Only used for dump.
+ std::vector<BasicBlock> basic_blocks;
+};
+
+/** Single "instruction" of BIR. */
+class Node
+{
+public:
+ enum class Kind
+ {
+ ASSIGNMENT, // <place> = <expr>
+ SWITCH, // switch <place>
+ RETURN, // return
+ GOTO, // goto
+ STORAGE_DEAD, // StorageDead(<place>)
+ STORAGE_LIVE, // StorageLive(<place>)
+ };
+
+private:
+ Kind kind;
+ // ASSIGNMENT: lhs
+ // SWITCH: switch_val
+ // StorageDead/StorageLive: place
+ // otherwise: <unused>
+ PlaceId place;
+ // ASSIGNMENT: rhs
+ // otherwise: <unused>
+ std::unique_ptr<AbstractExpr> expr;
+
+public:
+ Node (PlaceId lhs, AbstractExpr *rhs)
+ : kind (Kind::ASSIGNMENT), place (lhs), expr (rhs)
+ {}
+
+ explicit Node (Kind kind, PlaceId place = INVALID_PLACE,
+ AbstractExpr *expr = nullptr)
+ : kind (kind), place (place), expr (expr)
+ {}
+
+public:
+ WARN_UNUSED_RESULT Kind get_kind () const { return kind; }
+ WARN_UNUSED_RESULT PlaceId get_place () const { return place; }
+ WARN_UNUSED_RESULT AbstractExpr &get_expr () const { return *expr; }
+};
+
+/** Unique identifier for a basic block in the BIR. */
+using BasicBlockId = uint32_t;
+
+static constexpr BasicBlockId INVALID_BB
+ = std::numeric_limits<BasicBlockId>::max ();
+
+struct BasicBlock
+{
+ // BIR "instructions".
+ std::vector<Node> statements;
+ // A basic block can end with: goto, return or switch
+ std::vector<BasicBlockId> successors;
+
+public:
+ WARN_UNUSED_RESULT bool is_terminated () const
+ {
+ if (statements.empty ())
+ return false;
+ switch (statements.back ().get_kind ())
+ {
+ case Node::Kind::GOTO:
+ case Node::Kind::RETURN:
+ case Node::Kind::SWITCH:
+ return true;
+ default:
+ return false;
+ }
+ }
+
+ WARN_UNUSED_RESULT bool is_goto_terminated () const
+ {
+ return is_terminated ()
+ && statements.back ().get_kind () == Node::Kind::GOTO;
+ }
+};
+
+// Rhs expression of BIR assignment node (abstract).
+class AbstractExpr : public Visitable
+{
+};
+
+class InitializerExpr : public VisitableImpl<AbstractExpr, InitializerExpr>
+{
+ std::vector<PlaceId> values;
+
+public:
+ explicit InitializerExpr (std::vector<PlaceId> &&values) : values (values) {}
+
+public:
+ std::vector<PlaceId> &get_values () { return values; }
+};
+
+template <unsigned ARITY>
+class Operator : public VisitableImpl<AbstractExpr, Operator<ARITY>>
+{
+ std::array<PlaceId, ARITY> operands;
+
+public:
+ explicit Operator (std::array<PlaceId, ARITY> &&operands)
+ : operands (operands)
+ {}
+
+public:
+ template <size_t I> WARN_UNUSED_RESULT PlaceId get_operand () const
+ {
+ static_assert (I < ARITY, "Index out of bounds");
+ return operands[I];
+ }
+};
+
+class BorrowExpr : public VisitableImpl<AbstractExpr, BorrowExpr>
+{
+ PlaceId place;
+
+public:
+ explicit BorrowExpr (PlaceId place) : place (place) {}
+ WARN_UNUSED_RESULT PlaceId get_place () const { return place; }
+};
+
+/**
+ * This expression is only to be used inside the assignment node and acts as
+ * identity wrapper for a place value. It is separated from `Operator<1>` to
+ * render it more explicitly in the dump.
+ */
+class Assignment : public VisitableImpl<AbstractExpr, Assignment>
+{
+ PlaceId rhs;
+
+public:
+ explicit Assignment (PlaceId rhs) : rhs (rhs) {}
+
+public:
+ WARN_UNUSED_RESULT PlaceId get_rhs () const { return rhs; }
+};
+
+class CallExpr : public VisitableImpl<AbstractExpr, CallExpr>
+{
+ std::vector<PlaceId> arguments;
+ PlaceId callable;
+
+public:
+ explicit CallExpr (PlaceId callable, std::vector<PlaceId> &&arguments)
+ : arguments (arguments), callable (callable)
+ {}
+
+public:
+ const std::vector<PlaceId> &get_arguments () { return arguments; }
+ WARN_UNUSED_RESULT PlaceId get_callable () const { return callable; }
+};
+
+} // namespace BIR
+
+} // namespace Rust
+
+#endif // RUST_BIR_BASE_H
diff --git a/gcc/rust/checks/errors/borrowck/rust-borrow-checker.cc
b/gcc/rust/checks/errors/borrowck/rust-borrow-checker.cc
index 6c2922310423..44d33c57838a 100644
--- a/gcc/rust/checks/errors/borrowck/rust-borrow-checker.cc
+++ b/gcc/rust/checks/errors/borrowck/rust-borrow-checker.cc
@@ -18,6 +18,8 @@
#include "rust-borrow-checker.h"
#include "rust-function-collector.h"
+#include "rust-bir.h"
+#include "rust-bir-visitor.h"
namespace Rust {
namespace HIR {
