Line data    Source code

       1              : // Copyright (C) 2020-2026 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