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           12 :   bool operator== (const BasicBlockId &rhs) const { return value == rhs.value; }
      44           75 :   bool operator!= (const BasicBlockId &rhs) const
      45              :   {
      46           75 :     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         3943 : class Statement
      76              : {
      77              : public:
      78              :   enum class DropStyle
      79              :   {
      80              :     UNCLASSIFIED,
      81              :     STATIC,
      82              :     DEAD,
      83              :     CONDITIONAL,
      84              :   };
      85              : 
      86              :   enum class Kind
      87              :   {
      88              :     ASSIGNMENT,           // <place> = <expr>
      89              :     SWITCH,               // switch <place>
      90              :     RETURN,               // return
      91              :     GOTO,                 // goto
      92              :     DROP,                 // Drop(<place>)
      93              :     STORAGE_DEAD,         // StorageDead(<place>)
      94              :     STORAGE_LIVE,         // StorageLive(<place>)
      95              :     USER_TYPE_ASCRIPTION, // UserTypeAscription(<place>, <tyty>)
      96              :     FAKE_READ,
      97              :   };
      98              : 
      99              : private:
     100              :   Kind kind;
     101              :   // ASSIGNMENT: lhs
     102              :   // SWITCH: switch_val
     103              :   // DROP/StorageDead/StorageLive: place
     104              :   // otherwise: <unused>
     105              :   PlaceId place;
     106              :   // DROP: drop classification
     107              :   DropStyle drop_style = DropStyle::UNCLASSIFIED;
     108              :   // ASSIGNMENT: rhs
     109              :   // otherwise: <unused>
     110              :   std::unique_ptr<AbstractExpr> expr;
     111              :   TyTy::BaseType *type;
     112              :   // stores location of the actual expression from source code
     113              :   // currently only available when kind is ASSIGNMENT | RETURN
     114              :   // FIXME: Add location for other statement kinds
     115              :   location_t location;
     116              : 
     117              : public:
     118          218 :   static Statement make_assignment (PlaceId place, AbstractExpr *rhs,
     119              :                                     location_t location)
     120              :   {
     121          218 :     return Statement (Kind::ASSIGNMENT, place, rhs, nullptr, location);
     122              :   }
     123            7 :   static Statement make_switch (PlaceId place)
     124              :   {
     125            7 :     return Statement (Kind::SWITCH, place);
     126              :   }
     127           49 :   static Statement make_return (location_t location)
     128              :   {
     129           49 :     return Statement (Kind::RETURN, INVALID_PLACE, nullptr, nullptr, location);
     130              :   }
     131            8 :   static Statement make_goto () { return Statement (Kind::GOTO); }
     132          192 :   static Statement make_drop (PlaceId place)
     133              :   {
     134          192 :     return Statement (Kind::DROP, place);
     135              :   }
     136          167 :   static Statement make_storage_dead (PlaceId place)
     137              :   {
     138          167 :     return Statement (Kind::STORAGE_DEAD, place);
     139              :   }
     140          163 :   static Statement make_storage_live (PlaceId place)
     141              :   {
     142          163 :     return Statement (Kind::STORAGE_LIVE, place);
     143              :   }
     144            0 :   static Statement make_user_type_ascription (PlaceId place,
     145              :                                               TyTy::BaseType *type)
     146              :   {
     147            0 :     return Statement (Kind::USER_TYPE_ASCRIPTION, place, nullptr, type);
     148              :   }
     149          105 :   static Statement make_fake_read (PlaceId place)
     150              :   {
     151          105 :     return Statement (Kind::FAKE_READ, place);
     152              :   }
     153              : 
     154              : private:
     155              :   // compelete constructor, used by make_* functions
     156          909 :   Statement (Kind kind, PlaceId place = INVALID_PLACE,
     157              :              AbstractExpr *rhs = nullptr, TyTy::BaseType *type = nullptr,
     158              :              location_t location = UNKNOWN_LOCATION)
     159          909 :     : kind (kind), place (place), expr (rhs), type (type), location (location)
     160              :   {}
     161              : 
     162              : public:
     163         1919 :   WARN_UNUSED_RESULT Kind get_kind () const { return kind; }
     164         1479 :   WARN_UNUSED_RESULT PlaceId get_place () const { return place; }
     165            6 :   WARN_UNUSED_RESULT DropStyle get_drop_style () const { return drop_style; }
     166          152 :   void set_drop_style (DropStyle style) { drop_style = style; }
     167          500 :   WARN_UNUSED_RESULT AbstractExpr &get_expr () const { return *expr; }
     168            0 :   WARN_UNUSED_RESULT TyTy::BaseType *get_type () const { return type; }
     169           30 :   WARN_UNUSED_RESULT location_t get_location () const { return location; }
     170              : };
     171              : 
     172          200 : struct BasicBlock
     173              : {
     174              :   // BIR "instructions".
     175              :   std::vector<Statement> statements;
     176              :   // A basic block can end with: goto, return or switch
     177              :   std::vector<BasicBlockId> successors;
     178              : 
     179              : public:
     180              :   WARN_UNUSED_RESULT bool is_terminated () const;
     181              : 
     182           10 :   WARN_UNUSED_RESULT bool is_goto_terminated () const
     183              :   {
     184           10 :     return is_terminated ()
     185           10 :            && statements.back ().get_kind () == Statement::Kind::GOTO;
     186              :   }
     187              : };
     188              : 
     189              : enum class ExprKind
     190              : {
     191              :   INITIALIZER,
     192              :   OPERATOR,
     193              :   BORROW,
     194              :   ASSIGNMENT,
     195              :   CALL,
     196              : };
     197              : 
     198              : // Rhs expression of BIR assignment statements (abstract).
     199              : class AbstractExpr : public Visitable
     200              : {
     201              :   ExprKind kind;
     202              : 
     203              : public:
     204          218 :   explicit AbstractExpr (ExprKind kind) : kind (kind) {}
     205          273 :   WARN_UNUSED_RESULT ExprKind get_kind () const { return kind; }
     206              : 
     207              :   virtual ~AbstractExpr () {}
     208              : };
     209              : 
     210              : class InitializerExpr : public VisitableImpl<AbstractExpr, InitializerExpr>
     211              : {
     212              :   std::vector<PlaceId> values;
     213              : 
     214              : public:
     215           13 :   explicit InitializerExpr (std::vector<PlaceId> &&values)
     216           13 :     : VisitableImpl<AbstractExpr, InitializerExpr> (ExprKind::INITIALIZER),
     217           13 :       values (values)
     218              :   {}
     219              : 
     220              : public:
     221              :   std::vector<PlaceId> &get_values () { return values; }
     222            2 :   WARN_UNUSED_RESULT const std::vector<PlaceId> &get_values () const
     223              :   {
     224           15 :     return values;
     225              :   }
     226              : };
     227              : 
     228              : template <unsigned ARITY>
     229              : class Operator : public VisitableImpl<AbstractExpr, Operator<ARITY>>
     230              : {
     231              :   std::array<PlaceId, ARITY> operands;
     232              : 
     233              : public:
     234            0 :   explicit Operator (std::array<PlaceId, ARITY> &&operands)
     235            0 :     : VisitableImpl<AbstractExpr, Operator<ARITY>> (ExprKind::OPERATOR),
     236            0 :       operands (operands)
     237              :   {}
     238              : 
     239              : public:
     240              :   template <size_t I> WARN_UNUSED_RESULT PlaceId get_operand () const
     241              :   {
     242              :     static_assert (I < ARITY, "Index out of bounds");
     243              :     return operands[I];
     244              :   }
     245              : };
     246              : 
     247              : class BorrowExpr : public VisitableImpl<AbstractExpr, BorrowExpr>
     248              : {
     249              :   PlaceId place;
     250              :   LoanId loan;
     251              :   Polonius::Origin origin;
     252              : 
     253              : public:
     254           55 :   explicit BorrowExpr (PlaceId place, LoanId loan_id, Polonius::Origin lifetime)
     255           55 :     : VisitableImpl<AbstractExpr, BorrowExpr> (ExprKind::BORROW), place (place),
     256           55 :       loan (loan_id), origin (lifetime)
     257              :   {}
     258           55 :   WARN_UNUSED_RESULT PlaceId get_place () const { return place; }
     259           55 :   WARN_UNUSED_RESULT LoanId get_loan_id () const { return loan; }
     260           77 :   WARN_UNUSED_RESULT Polonius::Origin get_origin () const { return origin; }
     261              : };
     262              : 
     263              : /**
     264              :  * This expression is only to be used inside the assignment statement and acts
     265              :  * as identity wrapper for a place value. It is separated from `Operator<1>` to
     266              :  * render it more explicitly in the dump.
     267              :  */
     268              : class Assignment : public VisitableImpl<AbstractExpr, Assignment>
     269              : {
     270              :   PlaceId rhs;
     271              : 
     272              : public:
     273          134 :   explicit Assignment (PlaceId rhs)
     274          134 :     : VisitableImpl<AbstractExpr, Assignment> (ExprKind::ASSIGNMENT), rhs (rhs)
     275              :   {}
     276              : 
     277              : public:
     278          250 :   WARN_UNUSED_RESULT PlaceId get_rhs () const { return rhs; }
     279              : };
     280              : 
     281              : class CallExpr final : public VisitableImpl<AbstractExpr, CallExpr>
     282              : {
     283              :   std::vector<PlaceId> arguments;
     284              :   PlaceId callable;
     285              : 
     286              : public:
     287           16 :   explicit CallExpr (PlaceId callable, std::vector<PlaceId> &&arguments)
     288           16 :     : VisitableImpl (ExprKind::CALL), arguments (arguments), callable (callable)
     289              :   {}
     290              : 
     291              : public:
     292           13 :   WARN_UNUSED_RESULT const std::vector<PlaceId> &get_arguments () const
     293              :   {
     294           13 :     return arguments;
     295              :   }
     296           16 :   WARN_UNUSED_RESULT PlaceId get_callable () const { return callable; }
     297              : };
     298              : 
     299              : inline bool
     300          221 : BasicBlock::is_terminated () const
     301              : {
     302          221 :   if (statements.empty ())
     303              :     return false;
     304          200 :   switch (statements.back ().get_kind ())
     305              :     {
     306              :     case Statement::Kind::GOTO:
     307              :     case Statement::Kind::RETURN:
     308              :     case Statement::Kind::SWITCH:
     309              :       return true;
     310           84 :     case Statement::Kind::ASSIGNMENT:
     311           84 :       return statements.back ().get_expr ().get_kind () == ExprKind::CALL;
     312              :     default:
     313              :       return false;
     314              :     }
     315              : }
     316              : 
     317              : } // namespace BIR
     318              : 
     319              : } // namespace Rust
     320              : 
     321              : #endif // RUST_BIR_BASE_H