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              : #include "optional.h"
      25              : 
      26              : #include "polonius/rust-polonius-ffi.h"
      27              : #include "rust-tyty-variance-analysis.h"
      28              : 
      29              : namespace Rust {
      30              : 
      31              : namespace BIR {
      32              : 
      33              : struct BasicBlock;
      34              : struct BasicBlockId;
      35              : using BasicBlocks = IndexVec<BasicBlockId, BasicBlock>;
      36              : class Statement;
      37              : class AbstractExpr;
      38              : 
      39              : /** Unique identifier for a basic block in the BIR. */
      40              : struct BasicBlockId
      41              : {
      42              :   uint32_t value;
      43              :   // some overloads for comparision
      44           31 :   bool operator== (const BasicBlockId &rhs) const { return value == rhs.value; }
      45           31 :   bool operator!= (const BasicBlockId &rhs) const
      46              :   {
      47           31 :     return !(operator== (rhs));
      48              :   }
      49              :   bool operator< (const BasicBlockId &rhs) const { return value < rhs.value; }
      50              :   bool operator> (const BasicBlockId &rhs) const { return value > rhs.value; }
      51              :   bool operator<= (const BasicBlockId &rhs) const { return !(operator> (rhs)); }
      52              :   bool operator>= (const BasicBlockId &rhs) const { return !(operator< (rhs)); }
      53              : };
      54              : 
      55              : static constexpr BasicBlockId INVALID_BB
      56              :   = {std::numeric_limits<uint32_t>::max ()};
      57              : static constexpr BasicBlockId ENTRY_BASIC_BLOCK = {0};
      58              : 
      59              : /**
      60              :  * Top-level entity of the Borrow-checker IR (BIR).
      61              :  * It represents a single function (method, closure, etc.), which is the
      62              :  * basic unit of borrow-checking.
      63              :  */
      64              : struct Function
      65              : {
      66              :   PlaceDB place_db;
      67              :   std::vector<PlaceId> arguments;
      68              :   BasicBlocks basic_blocks;
      69              :   FreeRegions universal_regions;
      70              :   std::vector<std::pair<FreeRegion, FreeRegion>> universal_region_bounds;
      71              :   std::unordered_map<Polonius::Origin, HIR::LifetimeParam *> region_hir_map;
      72              :   location_t location;
      73              : };
      74              : 
      75              : /** Single statement of BIR. */
      76         5109 : class Statement
      77              : {
      78              : public:
      79              :   enum class DropStyle
      80              :   {
      81              :     UNCLASSIFIED,
      82              :     STATIC,
      83              :     DEAD,
      84              :     CONDITIONAL,
      85              :   };
      86              : 
      87              :   enum class Kind
      88              :   {
      89              :     ASSIGNMENT,           // <place> = <expr>
      90              :     SWITCH,               // switch <place>
      91              :     RETURN,               // return
      92              :     GOTO,                 // goto
      93              :     DROP,                 // Drop(<place>)
      94              :     STORAGE_DEAD,         // StorageDead(<place>)
      95              :     STORAGE_LIVE,         // StorageLive(<place>)
      96              :     USER_TYPE_ASCRIPTION, // UserTypeAscription(<place>, <tyty>)
      97              :     FAKE_READ,
      98              :   };
      99              : 
     100              : private:
     101              :   Kind kind;
     102              :   // ASSIGNMENT: lhs
     103              :   // SWITCH: switch_val
     104              :   // DROP/StorageDead/StorageLive: place
     105              :   // otherwise: <unused>
     106              :   PlaceId place;
     107              :   // DROP: drop classification
     108              :   DropStyle drop_style = DropStyle::UNCLASSIFIED;
     109              :   // ASSIGNMENT: rhs
     110              :   // otherwise: <unused>
     111              :   std::unique_ptr<AbstractExpr> expr;
     112              :   TyTy::BaseType *type;
     113              :   // stores location of the actual expression from source code
     114              :   // currently only available when kind is ASSIGNMENT | RETURN
     115              :   // FIXME: Add location for other statement kinds
     116              :   location_t location;
     117              :   // HIR expression which consumes the RHS of an assignment.  This is used to
     118              :   // attach backend drop-flag updates to the corresponding expression.
     119              :   tl::optional<HirId> move_site;
     120              : 
     121              : public:
     122          279 :   static Statement make_assignment (PlaceId place, AbstractExpr *rhs,
     123              :                                     location_t location,
     124              :                                     tl::optional<HirId> move_site = tl::nullopt)
     125              :   {
     126          279 :     return Statement (Kind::ASSIGNMENT, place, rhs, nullptr, location,
     127          279 :                       move_site);
     128              :   }
     129           14 :   static Statement make_switch (PlaceId place)
     130              :   {
     131           14 :     return Statement (Kind::SWITCH, place);
     132              :   }
     133           59 :   static Statement make_return (location_t location)
     134              :   {
     135           59 :     return Statement (Kind::RETURN, INVALID_PLACE, nullptr, nullptr, location);
     136              :   }
     137           17 :   static Statement make_goto () { return Statement (Kind::GOTO); }
     138          250 :   static Statement make_drop (PlaceId place)
     139              :   {
     140          250 :     return Statement (Kind::DROP, place);
     141              :   }
     142          218 :   static Statement make_storage_dead (PlaceId place)
     143              :   {
     144          218 :     return Statement (Kind::STORAGE_DEAD, place);
     145              :   }
     146          214 :   static Statement make_storage_live (PlaceId place)
     147              :   {
     148          214 :     return Statement (Kind::STORAGE_LIVE, place);
     149              :   }
     150            0 :   static Statement make_user_type_ascription (PlaceId place,
     151              :                                               TyTy::BaseType *type)
     152              :   {
     153            0 :     return Statement (Kind::USER_TYPE_ASCRIPTION, place, nullptr, type);
     154              :   }
     155          138 :   static Statement make_fake_read (PlaceId place)
     156              :   {
     157          138 :     return Statement (Kind::FAKE_READ, place);
     158              :   }
     159              : 
     160              : private:
     161              :   // compelete constructor, used by make_* functions
     162         1189 :   Statement (Kind kind, PlaceId place = INVALID_PLACE,
     163              :              AbstractExpr *rhs = nullptr, TyTy::BaseType *type = nullptr,
     164              :              location_t location = UNKNOWN_LOCATION,
     165              :              tl::optional<HirId> move_site = tl::nullopt)
     166         1189 :     : kind (kind), place (place), expr (rhs), type (type), location (location),
     167         1189 :       move_site (move_site)
     168              :   {}
     169              : 
     170              : public:
     171         5429 :   WARN_UNUSED_RESULT Kind get_kind () const { return kind; }
     172         3662 :   WARN_UNUSED_RESULT PlaceId get_place () const { return place; }
     173           19 :   WARN_UNUSED_RESULT DropStyle get_drop_style () const { return drop_style; }
     174          246 :   void set_drop_style (DropStyle style) { drop_style = style; }
     175         1041 :   WARN_UNUSED_RESULT AbstractExpr &get_expr () const { return *expr; }
     176            0 :   WARN_UNUSED_RESULT TyTy::BaseType *get_type () const { return type; }
     177           32 :   WARN_UNUSED_RESULT location_t get_location () const { return location; }
     178         1182 :   WARN_UNUSED_RESULT const tl::optional<HirId> &get_move_site () const
     179              :   {
     180         1182 :     return move_site;
     181              :   }
     182              : };
     183              : 
     184          299 : struct BasicBlock
     185              : {
     186              :   // BIR "instructions".
     187              :   std::vector<Statement> statements;
     188              :   // A basic block can end with: goto, return or switch
     189              :   std::vector<BasicBlockId> successors;
     190              : 
     191              : public:
     192              :   WARN_UNUSED_RESULT bool is_terminated () const;
     193              : 
     194           19 :   WARN_UNUSED_RESULT bool is_goto_terminated () const
     195              :   {
     196           19 :     return is_terminated ()
     197           19 :            && statements.back ().get_kind () == Statement::Kind::GOTO;
     198              :   }
     199              : };
     200              : 
     201              : enum class ExprKind
     202              : {
     203              :   INITIALIZER,
     204              :   OPERATOR,
     205              :   BORROW,
     206              :   ASSIGNMENT,
     207              :   CALL,
     208              : };
     209              : 
     210              : // Rhs expression of BIR assignment statements (abstract).
     211              : class AbstractExpr : public Visitable
     212              : {
     213              :   ExprKind kind;
     214              : 
     215              : public:
     216          279 :   explicit AbstractExpr (ExprKind kind) : kind (kind) {}
     217          740 :   WARN_UNUSED_RESULT ExprKind get_kind () const { return kind; }
     218              : 
     219              :   virtual ~AbstractExpr () {}
     220              : };
     221              : 
     222              : class InitializerExpr : public VisitableImpl<AbstractExpr, InitializerExpr>
     223              : {
     224              :   std::vector<PlaceId> values;
     225              : 
     226              : public:
     227           27 :   explicit InitializerExpr (std::vector<PlaceId> &&values)
     228           27 :     : VisitableImpl<AbstractExpr, InitializerExpr> (ExprKind::INITIALIZER),
     229           27 :       values (values)
     230              :   {}
     231              : 
     232              : public:
     233              :   std::vector<PlaceId> &get_values () { return values; }
     234            5 :   WARN_UNUSED_RESULT const std::vector<PlaceId> &get_values () const
     235              :   {
     236           32 :     return values;
     237              :   }
     238              : };
     239              : 
     240              : template <unsigned ARITY>
     241              : class Operator : public VisitableImpl<AbstractExpr, Operator<ARITY>>
     242              : {
     243              :   std::array<PlaceId, ARITY> operands;
     244              : 
     245              : public:
     246            0 :   explicit Operator (std::array<PlaceId, ARITY> &&operands)
     247            0 :     : VisitableImpl<AbstractExpr, Operator<ARITY>> (ExprKind::OPERATOR),
     248            0 :       operands (operands)
     249              :   {}
     250              : 
     251              : public:
     252              :   template <size_t I> WARN_UNUSED_RESULT PlaceId get_operand () const
     253              :   {
     254              :     static_assert (I < ARITY, "Index out of bounds");
     255              :     return operands[I];
     256              :   }
     257              : };
     258              : 
     259              : class BorrowExpr : public VisitableImpl<AbstractExpr, BorrowExpr>
     260              : {
     261              :   PlaceId place;
     262              :   LoanId loan;
     263              :   Polonius::Origin origin;
     264              : 
     265              : public:
     266           55 :   explicit BorrowExpr (PlaceId place, LoanId loan_id, Polonius::Origin lifetime)
     267           55 :     : VisitableImpl<AbstractExpr, BorrowExpr> (ExprKind::BORROW), place (place),
     268           55 :       loan (loan_id), origin (lifetime)
     269              :   {}
     270           55 :   WARN_UNUSED_RESULT PlaceId get_place () const { return place; }
     271           55 :   WARN_UNUSED_RESULT LoanId get_loan_id () const { return loan; }
     272           77 :   WARN_UNUSED_RESULT Polonius::Origin get_origin () const { return origin; }
     273              : };
     274              : 
     275              : /**
     276              :  * This expression is only to be used inside the assignment statement and acts
     277              :  * as identity wrapper for a place value. It is separated from `Operator<1>` to
     278              :  * render it more explicitly in the dump.
     279              :  */
     280              : class Assignment : public VisitableImpl<AbstractExpr, Assignment>
     281              : {
     282              :   PlaceId rhs;
     283              : 
     284              : public:
     285          173 :   explicit Assignment (PlaceId rhs)
     286          173 :     : VisitableImpl<AbstractExpr, Assignment> (ExprKind::ASSIGNMENT), rhs (rhs)
     287              :   {}
     288              : 
     289              : public:
     290          595 :   WARN_UNUSED_RESULT PlaceId get_rhs () const { return rhs; }
     291              : };
     292              : 
     293              : class CallExpr final : public VisitableImpl<AbstractExpr, CallExpr>
     294              : {
     295              :   std::vector<PlaceId> arguments;
     296              :   PlaceId callable;
     297              : 
     298              : public:
     299           24 :   explicit CallExpr (PlaceId callable, std::vector<PlaceId> &&arguments)
     300           24 :     : VisitableImpl (ExprKind::CALL), arguments (arguments), callable (callable)
     301              :   {}
     302              : 
     303              : public:
     304           20 :   WARN_UNUSED_RESULT const std::vector<PlaceId> &get_arguments () const
     305              :   {
     306           20 :     return arguments;
     307              :   }
     308           24 :   WARN_UNUSED_RESULT PlaceId get_callable () const { return callable; }
     309              : };
     310              : 
     311              : inline bool
     312          292 : BasicBlock::is_terminated () const
     313              : {
     314          292 :   if (statements.empty ())
     315              :     return false;
     316          268 :   switch (statements.back ().get_kind ())
     317              :     {
     318              :     case Statement::Kind::GOTO:
     319              :     case Statement::Kind::RETURN:
     320              :     case Statement::Kind::SWITCH:
     321              :       return true;
     322          122 :     case Statement::Kind::ASSIGNMENT:
     323          122 :       return statements.back ().get_expr ().get_kind () == ExprKind::CALL;
     324              :     default:
     325              :       return false;
     326              :     }
     327              : }
     328              : 
     329              : } // namespace BIR
     330              : 
     331              : } // namespace Rust
     332              : 
     333              : #endif // RUST_BIR_BASE_H