[PATCH 120/125] gccrs: borrowck: Regions in BIR

[Arthur Cohen <arthur.cohen@embecosm.com>]

From: Jakub Dupak <dev@jakubdupak.com>

gcc/rust/ChangeLog:

	* checks/errors/borrowck/rust-bir-place.h (struct Lifetime):
	Extended regions and loans.
	(struct Loan): Representation of loan (result of borrowing)
	* checks/errors/borrowck/rust-bir-builder-expr-stmt.cc (ExprStmtBuilder::visit):
	Fix let stmt handling.
	* checks/errors/borrowck/rust-bir-builder-pattern.h: improved
	pattern translation
	* checks/errors/borrowck/rust-bir-builder-internal.h: region binding
	* checks/errors/borrowck/rust-bir-builder-expr-stmt.h (class ExprStmtBuilder):
	Region support.
	(class RenumberCtx): Region support.
	* checks/errors/borrowck/rust-bir-builder.h (class Builder): Region support.
	* checks/errors/borrowck/rust-bir-dump.cc (get_lifetime_name): Region support.
	(renumber_places): Region support.
	(Dump::go): Region support.
	(Dump::visit): Region support.
	(Dump::visit_lifetime): Region support.
	(Dump::visit_scope): Region support.
	* checks/errors/borrowck/rust-bir.h (class AbstractExpr): Region support.
	(struct Function): Region support.
	(class BorrowExpr): Region support.
	(class CallExpr): Region support.

Signed-off-by: Jakub Dupak <dev@jakubdupak.com>
---
 .../borrowck/rust-bir-builder-expr-stmt.cc    |  73 +++---
 .../borrowck/rust-bir-builder-expr-stmt.h     |   7 +-
 .../borrowck/rust-bir-builder-internal.h      | 234 ++++++++++++------
 .../borrowck/rust-bir-builder-pattern.h       | 154 +++++++-----
 .../checks/errors/borrowck/rust-bir-builder.h | 120 +++++++--
 .../checks/errors/borrowck/rust-bir-dump.cc   |  46 ++--
 .../checks/errors/borrowck/rust-bir-place.h   | 202 +++++++++++----
 gcc/rust/checks/errors/borrowck/rust-bir.h    |  49 +++-
 8 files changed, 610 insertions(+), 275 deletions(-)

diff --git a/gcc/rust/checks/errors/borrowck/rust-bir-builder-expr-stmt.cc b/gcc/rust/checks/errors/borrowck/rust-bir-builder-expr-stmt.cc
index 922894cc5d5..d64641177d0 100644
--- a/gcc/rust/checks/errors/borrowck/rust-bir-builder-expr-stmt.cc
+++ b/gcc/rust/checks/errors/borrowck/rust-bir-builder-expr-stmt.cc
@@ -93,8 +93,8 @@ ExprStmtBuilder::visit (HIR::ClosureExpr &expr)
 void
 ExprStmtBuilder::visit (HIR::StructExprStructFields &fields)
 {
-  auto struct_ty
-    = lookup_type (fields)->as<TyTy::ADTType> ()->get_variants ().at (0);
+  auto *p_adt_type = lookup_type (fields)->as<TyTy::ADTType> ();
+  auto struct_ty = p_adt_type->get_variants ().at (0);
   auto init_values = StructBuilder (ctx, struct_ty).build (fields);
   move_all (init_values);
   return_expr (new InitializerExpr (std::move (init_values)),
@@ -119,7 +119,15 @@ void
 ExprStmtBuilder::visit (HIR::BorrowExpr &expr)
 {
   auto operand = visit_expr (*expr.get_expr ());
-  return_expr (new BorrowExpr (operand), lookup_type (expr));
+  if (ctx.place_db[operand].is_constant ())
+    {
+      // Cannot borrow a constant, must create a temporary copy.
+      push_tmp_assignment (operand);
+      operand = translated;
+    }
+
+  // BorrowExpr cannot be annotated with lifetime.
+  return_borrowed (operand, lookup_type (expr));
 }
 
 void
@@ -183,6 +191,7 @@ ExprStmtBuilder::visit (HIR::AssignmentExpr &expr)
   auto lhs = visit_expr (*expr.get_lhs ());
   auto rhs = visit_expr (*expr.get_rhs ());
   push_assignment (lhs, rhs);
+  translated = INVALID_PLACE;
 }
 
 void
@@ -265,6 +274,7 @@ ExprStmtBuilder::visit (HIR::CallExpr &expr)
     }
 
   move_all (arguments);
+
   return_expr (new CallExpr (fn, std::move (arguments)), lookup_type (expr),
 	       true);
 }
@@ -346,7 +356,10 @@ ExprStmtBuilder::visit (HIR::BlockExpr &block)
 				  lookup_type (*block.get_final_expr ()))));
     }
 
-  pop_scope ();
+  if (!unreachable)
+    pop_scope ();
+  else
+    ctx.place_db.pop_scope ();
 }
 
 void
@@ -422,10 +435,12 @@ ExprStmtBuilder::visit (HIR::ReturnExpr &ret)
 {
   if (ret.has_return_expr ())
     {
-      push_assignment (RETURN_VALUE_PLACE, visit_expr (*ret.get_expr ()));
+      push_assignment (RETURN_VALUE_PLACE,
+		       move_place (visit_expr (*ret.get_expr ())));
     }
   unwind_until (ROOT_SCOPE);
   ctx.get_current_bb ().statements.emplace_back (Statement::Kind::RETURN);
+  translated = INVALID_PLACE;
 }
 
 void
@@ -538,16 +553,19 @@ ExprStmtBuilder::visit (HIR::IfExprConseqElse &expr)
   if (else_bb.is_goto_terminated () && else_bb.successors.empty ())
     add_jump (else_end_bb, final_start_bb);
 }
+
 void
 ExprStmtBuilder::visit (HIR::IfLetExpr &expr)
 {
   rust_sorry_at (expr.get_locus (), "if let expressions are not supported");
 }
+
 void
 ExprStmtBuilder::visit (HIR::IfLetExprConseqElse &expr)
 {
   rust_sorry_at (expr.get_locus (), "if let expressions are not supported");
 }
+
 void
 ExprStmtBuilder::visit (HIR::MatchExpr &expr)
 {
@@ -608,8 +626,7 @@ void
 ExprStmtBuilder::visit (HIR::QualifiedPathInExpression &expr)
 {
   // Note: Type is only stored for the expr, not the segment.
-  PlaceId result
-    = resolve_variable_or_fn (expr.get_final_segment (), lookup_type (expr));
+  PlaceId result = resolve_variable_or_fn (expr, lookup_type (expr));
   return_place (result);
 }
 
@@ -617,14 +634,19 @@ void
 ExprStmtBuilder::visit (HIR::PathInExpression &expr)
 {
   // Note: Type is only stored for the expr, not the segment.
-  PlaceId result
-    = resolve_variable_or_fn (expr.get_final_segment (), lookup_type (expr));
+  PlaceId result = resolve_variable_or_fn (expr, lookup_type (expr));
   return_place (result);
 }
 
 void
 ExprStmtBuilder::visit (HIR::LetStmt &stmt)
 {
+  tl::optional<PlaceId> init;
+  tl::optional<TyTy::BaseType *> type_annotation;
+
+  if (stmt.has_type ())
+    type_annotation = lookup_type (*stmt.get_type ());
+
   if (stmt.get_pattern ()->get_pattern_type () == HIR::Pattern::IDENTIFIER)
     {
       // Only if a pattern is just an identifier, no destructuring is needed.
@@ -632,35 +654,30 @@ ExprStmtBuilder::visit (HIR::LetStmt &stmt)
       // (init expr is evaluated before pattern binding) into a
       // variable, so it would emit extra assignment.
       auto var = declare_variable (stmt.get_pattern ()->get_mappings ());
-      auto &var_place = ctx.place_db[var];
-      if (var_place.tyty->get_kind () == TyTy::REF)
-	{
-	  var_place.lifetime = ctx.lookup_lifetime (
-	    optional_from_ptr (
-	      static_cast<HIR::ReferenceType *> (stmt.get_type ().get ()))
-	      .map (&HIR::ReferenceType::get_lifetime));
-	}
+      if (stmt.has_type ())
+	push_user_type_ascription (var, lookup_type (*stmt.get_type ()));
+
       if (stmt.has_init_expr ())
 	(void) visit_expr (*stmt.get_init_expr (), var);
     }
-  else if (stmt.has_init_expr ())
-    {
-      auto init = visit_expr (*stmt.get_init_expr ());
-      PatternBindingBuilder (ctx, init, stmt.get_type ().get ())
-	.go (*stmt.get_pattern ());
-    }
   else
     {
-      rust_sorry_at (stmt.get_locus (), "pattern matching in let statements "
-					"without initializer is not supported");
+      if (stmt.has_init_expr ())
+	init = visit_expr (*stmt.get_init_expr ());
+
+      PatternBindingBuilder (ctx, init, type_annotation)
+	.go (*stmt.get_pattern ());
     }
 }
 
 void
 ExprStmtBuilder::visit (HIR::ExprStmt &stmt)
 {
-  (void) visit_expr (*stmt.get_expr ());
+  PlaceId result = visit_expr (*stmt.get_expr ());
+  // We must read the value for current liveness and we must not store it into
+  // the same place.
+  if (result != INVALID_PLACE)
+    push_tmp_assignment (result);
 }
-
 } // namespace BIR
-} // namespace Rust
\ No newline at end of file
+} // namespace Rust
diff --git a/gcc/rust/checks/errors/borrowck/rust-bir-builder-expr-stmt.h b/gcc/rust/checks/errors/borrowck/rust-bir-builder-expr-stmt.h
index 0654bcc27b0..1597ff291b0 100644
--- a/gcc/rust/checks/errors/borrowck/rust-bir-builder-expr-stmt.h
+++ b/gcc/rust/checks/errors/borrowck/rust-bir-builder-expr-stmt.h
@@ -30,15 +30,16 @@ namespace BIR {
  * See AbstractExprBuilder for API usage docs (mainly `return_place` and
  * `return_expr`).
  */
-class ExprStmtBuilder : public AbstractExprBuilder, public HIR::HIRStmtVisitor
+class ExprStmtBuilder final : public AbstractExprBuilder,
+			      public HIR::HIRStmtVisitor
 {
 public:
   explicit ExprStmtBuilder (BuilderContext &ctx) : AbstractExprBuilder (ctx) {}
 
   /** Entry point. */
-  PlaceId build (HIR::Expr &expr, PlaceId place = INVALID_PLACE)
+  PlaceId build (HIR::Expr &expr, PlaceId destination = INVALID_PLACE)
   {
-    return visit_expr (expr, place);
+    return visit_expr (expr, destination);
   }
 
 private:
diff --git a/gcc/rust/checks/errors/borrowck/rust-bir-builder-internal.h b/gcc/rust/checks/errors/borrowck/rust-bir-builder-internal.h
index b421ba43fba..2e2a7e2970a 100644
--- a/gcc/rust/checks/errors/borrowck/rust-bir-builder-internal.h
+++ b/gcc/rust/checks/errors/borrowck/rust-bir-builder-internal.h
@@ -26,39 +26,30 @@
 #include "rust-hir-visitor.h"
 #include "rust-name-resolver.h"
 #include "rust-bir.h"
+#include "rust-bir-free-region.h"
 
 namespace Rust {
 
-namespace BIR {
+namespace TyTy {
 
-/** Holds the context of BIR building so that it can be shared/passed between
- * different builders. */
-struct BuilderContext
+using Variance = VarianceAnalysis::Variance;
+
+class RenumberCtx
 {
-  class LifetimeResolver
-  {
-    using Index = uint32_t;
-    using Value = std::string;
+  Polonius::Origin next_region = 0;
 
-    Index next_index = FIRST_NORMAL_LIFETIME_ID;
-    std::unordered_map<Value, Index> value_to_index;
+public:
+  Polonius::Origin get_next_region () { return next_region++; }
+};
 
-  public:
-    Index resolve (const Value &value)
-    {
-      auto found = value_to_index.find (value);
-      if (found != value_to_index.end ())
-	{
-	  return found->second;
-	}
-      value_to_index.emplace (value, next_index);
-      return next_index++;
-    }
+} // namespace TyTy
 
-    /** Returns a new anonymous lifetime. */
-    Index get_anonymous () { return next_index++; }
-  };
+namespace BIR {
 
+/** Holds the context of BIR building so that it can be shared/passed between
+ * different builders. */
+struct BuilderContext
+{
   struct LoopAndLabelCtx
   {
     bool is_loop;      // Loop or labelled block
@@ -93,7 +84,8 @@ struct BuilderContext
    * constants)
    */
   PlaceDB place_db;
-  LifetimeResolver lifetime_interner;
+  RegionBinder region_binder{place_db.expose_next_free_region ()};
+
   // Used for cleaner dump.
   std::vector<PlaceId> arguments;
   /**
@@ -105,6 +97,8 @@ struct BuilderContext
   /** Context for current situation (loop, label, etc.) */
   std::vector<LoopAndLabelCtx> loop_and_label_stack;
 
+  FreeRegions fn_free_regions{{}};
+
 public:
   BuilderContext ()
     : tyctx (*Resolver::TypeCheckContext::get ()),
@@ -115,27 +109,6 @@ public:
 
   BasicBlock &get_current_bb () { return basic_blocks[current_bb]; }
 
-  Lifetime lookup_lifetime (const tl::optional<HIR::Lifetime> &lifetime)
-  {
-    if (!lifetime.has_value ())
-      return {lifetime_interner.get_anonymous ()};
-    switch (lifetime->get_lifetime_type ())
-      {
-	case AST::Lifetime::NAMED: {
-	  return {lifetime_interner.resolve (lifetime->get_name ())};
-	}
-	case AST::Lifetime::STATIC: {
-	  return STATIC_LIFETIME;
-	}
-	case AST::Lifetime::WILDCARD: {
-	  rust_sorry_at (lifetime->get_locus (),
-			 "lifetime elision is not yet implemented");
-	  return NO_LIFETIME;
-	}
-      }
-    rust_unreachable ();
-  };
-
   const LoopAndLabelCtx &lookup_label (NodeId label)
   {
     auto label_match = [label] (const LoopAndLabelCtx &info) {
@@ -165,25 +138,31 @@ protected:
 protected:
   explicit AbstractBuilder (BuilderContext &ctx) : ctx (ctx) {}
 
-  PlaceId declare_variable (const Analysis::NodeMapping &node)
+  PlaceId declare_variable (const Analysis::NodeMapping &node,
+			    bool user_type_annotation = false)
   {
-    return declare_variable (node, lookup_type (node.get_hirid ()));
+    return declare_variable (node, lookup_type (node.get_hirid ()),
+			     user_type_annotation);
   }
 
   PlaceId declare_variable (const Analysis::NodeMapping &node,
-			    TyTy::BaseType *ty)
+			    TyTy::BaseType *ty,
+			    bool user_type_annotation = false)
   {
     const NodeId nodeid = node.get_nodeid ();
 
     // In debug mode, check that the variable is not already declared.
     rust_assert (ctx.place_db.lookup_variable (nodeid) == INVALID_PLACE);
 
-    auto place = ctx.place_db.add_variable (nodeid, ty);
+    auto place_id = ctx.place_db.add_variable (nodeid, ty);
 
     if (ctx.place_db.get_current_scope_id () != 0)
-      push_storage_live (place);
+      push_storage_live (place_id);
+
+    if (user_type_annotation)
+      push_user_type_ascription (place_id, ty);
 
-    return place;
+    return place_id;
   }
 
   void push_new_scope () { ctx.place_db.push_new_scope (); }
@@ -199,18 +178,64 @@ protected:
     ctx.place_db.pop_scope ();
   }
 
+  bool intersection_empty (std::vector<PlaceId> &a, std::vector<PlaceId> &b)
+  {
+    for (auto &place : a)
+      {
+	if (std::find (b.begin (), b.end (), place) != b.end ())
+	  return false;
+      }
+    return true;
+  }
+
   void unwind_until (ScopeId final_scope)
   {
     auto current_scope_id = ctx.place_db.get_current_scope_id ();
     while (current_scope_id != final_scope)
       {
 	auto &scope = ctx.place_db.get_scope (current_scope_id);
+
+	// TODO: Perform stable toposort based on `borrowed_by`.
+
 	std::for_each (scope.locals.rbegin (), scope.locals.rend (),
 		       [&] (PlaceId place) { push_storage_dead (place); });
 	current_scope_id = scope.parent;
       }
   }
 
+  FreeRegions bind_regions (std::vector<TyTy::Region> regions,
+			    FreeRegions parent_free_regions)
+  {
+    std::vector<FreeRegion> free_regions;
+    for (auto &region : regions)
+      {
+	if (region.is_early_bound ())
+	  {
+	    free_regions.push_back (parent_free_regions[region.get_index ()]);
+	  }
+	else if (region.is_static ())
+	  {
+	    free_regions.push_back (0);
+	  }
+	else if (region.is_anonymous ())
+	  {
+	    free_regions.push_back (ctx.place_db.get_next_free_region ());
+	  }
+	else if (region.is_named ())
+	  {
+	    rust_unreachable (); // FIXME
+	  }
+	else
+	  {
+	    rust_sorry_at (UNKNOWN_LOCATION, "Unimplemented");
+	    rust_unreachable ();
+	  }
+      }
+    // This is necesarry because of clash of current gcc and gcc4.8.
+    FreeRegions free_regions_final{std::move (free_regions)};
+    return free_regions_final;
+  }
+
 protected: // Helpers to add BIR statements
   void push_assignment (PlaceId lhs, AbstractExpr *rhs)
   {
@@ -264,15 +289,51 @@ protected: // Helpers to add BIR statements
       Statement::Kind::STORAGE_DEAD, place);
   }
 
+  void push_user_type_ascription (PlaceId place, TyTy::BaseType *ty)
+  {
+    ctx.get_current_bb ().statements.emplace_back (
+      Statement::Kind::USER_TYPE_ASCRIPTION, place, ty);
+  }
+
+  void push_fake_read (PlaceId place)
+  {
+    ctx.get_current_bb ().statements.emplace_back (Statement::Kind::FAKE_READ,
+						   place);
+  }
+
+  PlaceId borrow_place (PlaceId place_id, TyTy::BaseType *ty)
+  {
+    auto mutability = ty->as<const TyTy::ReferenceType> ()->mutability ();
+    auto loan = ctx.place_db.add_loan ({mutability, place_id});
+    push_tmp_assignment (new BorrowExpr (place_id, loan,
+					 ctx.place_db.get_next_free_region ()),
+			 ty);
+    return translated;
+  }
+
   PlaceId move_place (PlaceId arg)
   {
-    if (ctx.place_db[arg].is_lvalue ())
-      {
-	push_tmp_assignment (arg);
-	arg = translated;
-      }
+    auto &place = ctx.place_db[arg];
+
+    if (place.is_constant ())
+      return arg;
+
+    if (place.tyty->is<TyTy::ReferenceType> ())
+      return reborrow_place (arg);
+
+    if (place.is_rvalue ())
+      return arg;
 
-    return arg;
+    push_tmp_assignment (arg);
+    return translated;
+  }
+
+  PlaceId reborrow_place (PlaceId arg)
+  {
+    auto ty = ctx.place_db[arg].tyty->as<TyTy::ReferenceType> ();
+    return borrow_place (ctx.place_db.lookup_or_add_path (Place::DEREF,
+							  ty->get_base (), arg),
+			 ty);
   }
 
   template <typename T> void move_all (T &args)
@@ -348,15 +409,17 @@ protected: // HIR resolution helpers
   template <typename T>
   PlaceId resolve_variable_or_fn (T &variable, TyTy::BaseType *ty)
   {
+    ty = (ty) ? ty : lookup_type (variable);
     // Unlike variables,
     // functions do not have to be declared in PlaceDB before use.
     NodeId variable_id;
     bool ok = ctx.resolver.lookup_resolved_name (
       variable.get_mappings ().get_nodeid (), &variable_id);
     rust_assert (ok);
-    return ctx.place_db.lookup_or_add_variable (variable_id,
-						(ty) ? ty
-						     : lookup_type (variable));
+    if (ty->is<TyTy::FnType> ())
+      return ctx.place_db.get_constant (ty);
+    else
+      return ctx.place_db.lookup_or_add_variable (variable_id, ty);
   }
 
 protected: // Implicit conversions.
@@ -415,10 +478,11 @@ protected: // Implicit conversions.
     if (ctx.place_db[translated].tyty->get_kind () != TyTy::REF)
       {
 	auto ty = ctx.place_db[translated].tyty;
-	push_tmp_assignment (
-	  new BorrowExpr (translated),
-	  new TyTy::ReferenceType (ty->get_ref (), TyTy::TyVar (ty->get_ref ()),
-				   Mutability::Imm));
+	translated
+	  = borrow_place (translated,
+			  new TyTy::ReferenceType (ty->get_ref (),
+						   TyTy::TyVar (ty->get_ref ()),
+						   Mutability::Imm));
       }
   }
 };
@@ -441,8 +505,8 @@ protected:
   {}
 
   /**
-   * Wrapper that provides return value based API inside a visitor which has to
-   * use global state to pass the data around.
+   * Wrapper that provides return value based API inside a visitor which has
+   * to use global state to pass the data around.
    * @param dst_place Place to assign the produced value to, optionally
    * allocated by the caller.
    * */
@@ -461,10 +525,11 @@ protected:
 
   /**
    * Create a return value of a subexpression, which produces an expression.
-   * Use `return_place` for subexpression that only produce a place (look it up)
-   * to avoid needless assignments.
+   * Use `return_place` for subexpression that only produce a place (look it
+   * up) to avoid needless assignments.
    *
-   * @param can_panic mark that expression can panic to insert jump to cleanup.
+   * @param can_panic mark that expression can panic to insert jump to
+   * cleanup.
    */
   void return_expr (AbstractExpr *expr, TyTy::BaseType *ty,
 		    bool can_panic = false)
@@ -482,10 +547,16 @@ protected:
       {
 	start_new_consecutive_bb ();
       }
+
+    if (ty->is<TyTy::ReferenceType> ()
+	|| ctx.place_db[translated].is_constant ())
+      {
+	push_fake_read (translated);
+      }
   }
 
   /** Mark place to be a result of processed subexpression. */
-  void return_place (PlaceId place)
+  void return_place (PlaceId place, bool can_panic = false)
   {
     if (expr_return_place != INVALID_PLACE)
       {
@@ -496,6 +567,16 @@ protected:
       {
 	translated = place;
       }
+
+    if (can_panic)
+      {
+	start_new_consecutive_bb ();
+      }
+
+    if (ctx.place_db[place].is_constant ())
+      {
+	push_fake_read (translated);
+      }
   }
 
   /** Explicitly return a unit value. Expression produces no value. */
@@ -504,6 +585,17 @@ protected:
     translated = ctx.place_db.get_constant (lookup_type (expr));
   }
 
+  PlaceId return_borrowed (PlaceId place_id, TyTy::BaseType *ty)
+  {
+    // TODO: deduplicate with borrow_place
+    auto loan = ctx.place_db.add_loan (
+      {ty->as<const TyTy::ReferenceType> ()->mutability (), place_id});
+    return_expr (new BorrowExpr (place_id, loan,
+				 ctx.place_db.get_next_free_region ()),
+		 ty);
+    return translated;
+  }
+
   PlaceId take_or_create_return_place (TyTy::BaseType *type)
   {
     PlaceId result = INVALID_PLACE;
diff --git a/gcc/rust/checks/errors/borrowck/rust-bir-builder-pattern.h b/gcc/rust/checks/errors/borrowck/rust-bir-builder-pattern.h
index 76943ff1b04..8b5adabcb6e 100644
--- a/gcc/rust/checks/errors/borrowck/rust-bir-builder-pattern.h
+++ b/gcc/rust/checks/errors/borrowck/rust-bir-builder-pattern.h
@@ -20,6 +20,8 @@
 #define RUST_BIR_BUILDER_PATTERN_H
 
 #include "rust-bir-builder-internal.h"
+#include "rust-bir-free-region.h"
+#include "rust-tyty-variance-analysis.h"
 
 namespace Rust {
 namespace BIR {
@@ -32,9 +34,9 @@ class PatternBindingBuilder : protected AbstractBuilder,
 			      public HIR::HIRPatternVisitor
 {
   /** Value of initialization expression. */
-  PlaceId init;
-  /** This is where lifetime annotations are stored. */
-  tl::optional<HIR::Type *> type;
+  tl::optional<PlaceId> init;
+  tl::optional<TyTy::BaseType *> type_annotation;
+  tl::optional<FreeRegions> regions;
 
   /** Emulates recursive stack saving and restoring inside a visitor. */
   class SavedState
@@ -42,24 +44,22 @@ class PatternBindingBuilder : protected AbstractBuilder,
     PatternBindingBuilder *builder;
 
   public:
-    const PlaceId init;
-    const tl::optional<HIR::Type *> type;
+    const tl::optional<PlaceId> init;
+    const tl::optional<FreeRegions> regions;
 
   public:
     explicit SavedState (PatternBindingBuilder *builder)
-      : builder (builder), init (builder->init), type (builder->type)
+      : builder (builder), init (builder->init), regions (builder->regions)
     {}
 
-    ~SavedState ()
-    {
-      builder->init = init;
-      builder->type = type;
-    }
+    ~SavedState () { builder->init = init; }
   };
 
 public:
-  PatternBindingBuilder (BuilderContext &ctx, PlaceId init, HIR::Type *type)
-    : AbstractBuilder (ctx), init (init), type (optional_from_ptr (type))
+  PatternBindingBuilder (BuilderContext &ctx, tl::optional<PlaceId> init,
+			 tl::optional<TyTy::BaseType *> type_annotation)
+    : AbstractBuilder (ctx), init (init), type_annotation (type_annotation),
+      regions (tl::nullopt)
   {}
 
   void go (HIR::Pattern &pattern) { pattern.accept_vis (*this); }
@@ -74,21 +74,15 @@ public:
 					 TyTy::TyVar (node.get_hirid ()),
 					 (is_mut) ? Mutability::Mut
 						  : Mutability::Imm));
-	push_assignment (translated, new BorrowExpr (init));
       }
     else
       {
 	translated = declare_variable (node);
-	push_assignment (translated, init);
       }
-    auto &init_place = ctx.place_db[init];
-    auto &translated_place = ctx.place_db[translated];
-    if (init_place.tyty->get_kind () == TyTy::REF)
+
+    if (init.has_value ())
       {
-	init_place.lifetime = ctx.lookup_lifetime (type.map ([] (HIR::Type *t) {
-	  return static_cast<HIR::ReferenceType *> (t)->get_lifetime ();
-	}));
-	translated_place.lifetime = init_place.lifetime;
+	push_assignment (translated, init.value ());
       }
   }
 
@@ -104,15 +98,15 @@ public:
   {
     SavedState saved (this);
 
-    auto ref_type = type.map (
-      [] (HIR::Type *t) { return static_cast<HIR::ReferenceType *> (t); });
+    init = init.map ([&] (PlaceId id) {
+      return ctx.place_db.lookup_or_add_path (Place::DEREF,
+					      lookup_type (pattern), id);
+    });
+
+    type_annotation = type_annotation.map ([&] (TyTy::BaseType *ty) {
+      return ty->as<TyTy::ReferenceType> ()->get_base ();
+    });
 
-    type = ref_type.map (
-      [] (HIR::ReferenceType *r) { return r->get_base_type ().get (); });
-    init = ctx.place_db.lookup_or_add_path (Place::DEREF, lookup_type (pattern),
-					    saved.init);
-    ctx.place_db[init].lifetime
-      = ctx.lookup_lifetime (ref_type.map (&HIR::ReferenceType::get_lifetime));
     pattern.get_referenced_pattern ()->accept_vis (*this);
   }
 
@@ -120,12 +114,20 @@ public:
   {
     SavedState saved (this);
 
-    type = type.map ([] (HIR::Type *t) {
-      return static_cast<HIR::SliceType *> (t)->get_element_type ().get ();
-    });
     // All indexes are supposed to point to the same place for borrow-checking.
-    init = ctx.place_db.lookup_or_add_path (Place::INDEX, lookup_type (pattern),
-					    saved.init);
+    // init = ctx.place_db.lookup_or_add_path (Place::INDEX, lookup_type
+    // (pattern), saved.init);
+    init = init.map ([&] (PlaceId id) {
+      return ctx.place_db.lookup_or_add_path (Place::INDEX,
+					      lookup_type (pattern), id);
+    });
+
+    type_annotation = type_annotation.map ([&] (TyTy::BaseType *ty) {
+      return ty->as<TyTy::SliceType> ()->get_element_type ();
+    });
+
+    // Regions are unchnaged.
+
     for (auto &item : pattern.get_items ())
       {
 	item->accept_vis (*this);
@@ -142,15 +144,12 @@ public:
   {
     SavedState saved (this);
 
-    auto tyty = ctx.place_db[init].tyty;
+    auto tyty = ctx.place_db[init.value ()].tyty;
     rust_assert (tyty->get_kind () == TyTy::ADT);
     auto adt_ty = static_cast<TyTy::ADTType *> (tyty);
     rust_assert (adt_ty->is_struct_struct ());
     auto struct_ty = adt_ty->get_variants ().at (0);
 
-    auto struct_type = type.map ([] (HIR::Type *t) {
-      return static_cast<HIR::TypePath *> (t)->get_final_segment ().get ();
-    });
     for (auto &field :
 	 pattern.get_struct_pattern_elems ().get_struct_pattern_fields ())
       {
@@ -159,9 +158,22 @@ public:
 	    case HIR::StructPatternField::TUPLE_PAT: {
 	      auto tuple
 		= static_cast<HIR::StructPatternFieldTuplePat *> (field.get ());
-	      init = ctx.place_db.lookup_or_add_path (
-		Place::FIELD, lookup_type (*tuple->get_tuple_pattern ()),
-		saved.init, tuple->get_index ());
+
+	      init = init.map ([&] (PlaceId id) {
+		return ctx.place_db.lookup_or_add_path (
+		  Place::FIELD, lookup_type (*tuple->get_tuple_pattern ()), id,
+		  tuple->get_index ());
+	      });
+
+	      type_annotation = type_annotation.map ([&] (TyTy::BaseType *ty) {
+		return ty->as<TyTy::ADTType> ()
+		  ->get_variants ()
+		  .at (0)
+		  ->get_fields ()
+		  .at (tuple->get_index ())
+		  ->get_field_type ();
+	      });
+
 	      tuple->get_tuple_pattern ()->accept_vis (*this);
 	      break;
 	    }
@@ -177,7 +189,8 @@ public:
 	      init
 		= ctx.place_db.lookup_or_add_path (Place::FIELD,
 						   field_ty->get_field_type (),
-						   saved.init, field_index);
+						   saved.init.value (),
+						   field_index);
 	      ident_field->get_pattern ()->accept_vis (*this);
 	      break;
 	    }
@@ -193,7 +206,8 @@ public:
 	      init
 		= ctx.place_db.lookup_or_add_path (Place::FIELD,
 						   field_ty->get_field_type (),
-						   saved.init, field_index);
+						   saved.init.value (),
+						   field_index);
 	      visit_identifier (ident_field->get_mappings (),
 				ident_field->get_has_ref (),
 				ident_field->is_mut ());
@@ -208,19 +222,32 @@ public:
   {
     for (auto &item : fields)
       {
-	type = saved.type.map ([&] (HIR::Type *t) {
-	  return static_cast<HIR::TupleType *> (t)
-	    ->get_elems ()
+	auto type = lookup_type (*item);
+
+	init = init.map ([&] (PlaceId id) {
+	  return ctx.place_db.lookup_or_add_path (Place::FIELD, type, id,
+						  index);
+	});
+
+	type_annotation = type_annotation.map ([&] (TyTy::BaseType *ty) {
+	  return ty->as<TyTy::TupleType> ()
+	    ->get_fields ()
 	    .at (index)
-	    .get ();
+	    .get_tyty ();
+	});
+
+	regions = regions.map ([&] (FreeRegions regs) {
+	  return bind_regions (Resolver::TypeCheckContext::get ()
+				 ->get_variance_analysis_ctx ()
+				 .query_type_regions (type),
+			       regs);
 	});
-	init
-	  = ctx.place_db.lookup_or_add_path (Place::FIELD, lookup_type (*item),
-					     saved.init, index);
+
 	item->accept_vis (*this);
 	index++;
       }
   }
+
   void visit (HIR::TuplePattern &pattern) override
   {
     SavedState saved (this);
@@ -238,7 +265,7 @@ public:
 	  auto &items = static_cast<HIR::TuplePatternItemsRanged &> (
 	    *pattern.get_items ());
 
-	  auto tyty = ctx.place_db[init].tyty;
+	  auto tyty = ctx.place_db[init.value ()].tyty;
 	  rust_assert (tyty->get_kind () == TyTy::TUPLE);
 
 	  auto skipped = (static_cast<TyTy::TupleType *> (tyty))->num_fields ()
@@ -253,10 +280,22 @@ public:
       }
     init = saved.init;
   }
+
   void visit (HIR::TupleStructPattern &pattern) override
   {
     SavedState saved (this);
 
+    type_annotation = tl::nullopt;
+
+    auto type = lookup_type (pattern);
+
+    regions = regions.map ([&] (FreeRegions regs) {
+      return bind_regions (Resolver::TypeCheckContext::get ()
+			     ->get_variance_analysis_ctx ()
+			     .query_type_regions (type),
+			   regs);
+    });
+
     size_t index = 0;
     switch (pattern.get_items ()->get_item_type ())
       {
@@ -264,9 +303,8 @@ public:
 	  auto &items
 	    = static_cast<HIR::TupleStructItemsRange &> (*pattern.get_items ());
 
-	  auto tyty = ctx.place_db[init].tyty;
-	  rust_assert (tyty->get_kind () == TyTy::ADT);
-	  auto adt_ty = static_cast<TyTy::ADTType *> (tyty);
+	  rust_assert (type->get_kind () == TyTy::ADT);
+	  auto adt_ty = static_cast<TyTy::ADTType *> (type);
 	  rust_assert (adt_ty->is_tuple_struct ());
 
 	  auto skipped = adt_ty->get_variants ().at (0)->get_fields ().size ()
@@ -293,12 +331,6 @@ public:
   void visit (HIR::PathInExpression &expression) override {}
   void visit (HIR::QualifiedPathInExpression &expression) override {}
   void visit (HIR::RangePattern &pattern) override {}
-
-private:
-  template <typename T> tl::optional<T> *get_type ()
-  {
-    return static_cast<T *> (type);
-  }
 };
 } // namespace BIR
 } // namespace Rust
diff --git a/gcc/rust/checks/errors/borrowck/rust-bir-builder.h b/gcc/rust/checks/errors/borrowck/rust-bir-builder.h
index 9bed96c660f..e9108703be1 100644
--- a/gcc/rust/checks/errors/borrowck/rust-bir-builder.h
+++ b/gcc/rust/checks/errors/borrowck/rust-bir-builder.h
@@ -20,72 +20,142 @@
 #define RUST_BIR_BUILDER_H
 
 #include "rust-bir-builder-internal.h"
-#include "rust-hir-visitor.h"
 #include "rust-bir-builder-pattern.h"
-#include "rust-bir-builder-struct.h"
 #include "rust-bir-builder-expr-stmt.h"
 
 namespace Rust {
 namespace BIR {
 
 /** Top-level builder, which compiles a HIR function into a BIR function. */
-class Builder : public AbstractBuilder
+class Builder final : public AbstractBuilder
 {
+  std::vector<std::pair<FreeRegion, FreeRegion>> universal_region_bounds;
+
 public:
   explicit Builder (BuilderContext &ctx) : AbstractBuilder (ctx) {}
 
   Function build (HIR::Function &function)
   {
-    PlaceId return_place
-      = ctx.place_db.add_temporary (lookup_type (*function.get_definition ()));
-    rust_assert (return_place == RETURN_VALUE_PLACE);
+    rust_debug ("BIR::Builder::build function={%s}",
+		function.get_function_name ().as_string ().c_str ());
+
+    auto fn_ty = lookup_type (function)->as<TyTy::FnType> ();
+
+    handle_lifetime_params (fn_ty->get_num_lifetime_params ());
+    handle_lifetime_param_constraints (fn_ty->get_region_constraints ());
+
+    handle_return (fn_ty);
 
     for (auto &param : function.get_function_params ())
-      {
-	handle_param (param);
-      }
+      handle_param (param);
 
     handle_body (*function.get_definition ());
 
-    return Function{std::move (ctx.place_db), std::move (ctx.arguments),
-		    std::move (ctx.basic_blocks)};
-  };
+    return Function{
+      std::move (ctx.place_db),
+      std::move (ctx.arguments),
+      std::move (ctx.basic_blocks),
+      std::move (ctx.fn_free_regions),
+      std::move (universal_region_bounds),
+      function.get_locus (),
+    };
+  }
 
 private:
+  /** Instantiate `num_lifetime_params` free regions. */
+  void handle_lifetime_params (size_t num_lifetime_params)
+  {
+    std::vector<FreeRegion> function_free_regions;
+    for (size_t i = 0; i < num_lifetime_params; i++)
+      {
+	function_free_regions.push_back (ctx.place_db.get_next_free_region ());
+      }
+
+    rust_debug ("\tctx.fn_free_region={%s}",
+		ctx.fn_free_regions.to_string ().c_str ());
+    ctx.fn_free_regions.set_from (std::move (function_free_regions));
+  }
+
+  void handle_lifetime_param_constraints (
+    const TyTy::RegionConstraints &region_constraints)
+  {
+    rust_debug ("\thandle_lifetime_param_constraints");
+
+    for (auto bound : region_constraints.region_region)
+      {
+	rust_assert (bound.first.is_early_bound ());
+	rust_assert (bound.second.is_early_bound ());
+
+	universal_region_bounds.emplace_back (
+	  ctx.fn_free_regions[bound.first.get_index ()],
+	  ctx.fn_free_regions[bound.second.get_index ()]);
+
+	auto last_bound = universal_region_bounds.back ();
+	rust_debug ("\t\t %ld: %ld", last_bound.first, last_bound.second);
+      }
+
+    // TODO: handle type_region constraints
+  }
+
+  void handle_return (TyTy::FnType *fn_ty)
+  {
+    TyTy::BaseType *return_ty = fn_ty->get_return_type ();
+
+    PlaceId return_place = ctx.place_db.add_temporary (return_ty);
+    rust_assert (return_place == RETURN_VALUE_PLACE);
+
+    // Set return place to use functions regions, not the fresh ones.
+    ctx.place_db[return_place].regions
+      = bind_regions (Resolver::TypeCheckContext::get ()
+			->get_variance_analysis_ctx ()
+			.query_type_regions (fn_ty->get_return_type ()),
+		      ctx.fn_free_regions);
+  }
+
   void handle_param (HIR::FunctionParam &param)
   {
+    auto param_type = lookup_type (*param.get_param_name ());
+
     auto &pattern = param.get_param_name ();
     if (pattern->get_pattern_type () == HIR::Pattern::IDENTIFIER
 	&& !static_cast<HIR::IdentifierPattern &> (*pattern).get_is_ref ())
       {
-	// Avoid useless temporary variable for parameter.
+	// Avoid useless temporary variable for parameter to look like MIR.
 	translated = declare_variable (pattern->get_mappings ());
 	ctx.arguments.push_back (translated);
       }
     else
       {
-	translated = ctx.place_db.add_temporary (lookup_type (*pattern));
+	translated = ctx.place_db.add_temporary (param_type);
 	ctx.arguments.push_back (translated);
-	PatternBindingBuilder (ctx, translated, param.get_type ().get ())
+	PatternBindingBuilder (ctx, translated, tl::nullopt)
 	  .go (*param.get_param_name ());
       }
+
+    rust_assert (param.get_type () != nullptr);
+
+    // Set parameter place to use functions regions, not the fresh ones.
+    ctx.place_db[translated].regions
+      = bind_regions (Resolver::TypeCheckContext::get ()
+			->get_variance_analysis_ctx ()
+			.query_type_regions (param_type),
+		      ctx.fn_free_regions);
   }
 
   void handle_body (HIR::BlockExpr &body)
   {
-    translated = ExprStmtBuilder (ctx).build (body);
-    if (body.has_expr () && !lookup_type (body)->is_unit ())
+    translated = ExprStmtBuilder (ctx).build (body, RETURN_VALUE_PLACE);
+    if (!ctx.get_current_bb ().is_terminated ())
       {
-	push_assignment (RETURN_VALUE_PLACE, translated);
+	if (ctx.place_db[RETURN_VALUE_PLACE].tyty->is_unit ())
+	  {
+	    push_assignment (RETURN_VALUE_PLACE,
+			     ctx.place_db.get_constant (
+			       ctx.place_db[RETURN_VALUE_PLACE].tyty));
+	  }
 	ctx.get_current_bb ().statements.emplace_back (Statement::Kind::RETURN);
       }
-    else if (!ctx.get_current_bb ().is_terminated ())
-      {
-	push_assignment (RETURN_VALUE_PLACE,
-			 ctx.place_db.get_constant (lookup_type (body)));
-	ctx.get_current_bb ().statements.emplace_back (Statement::Kind::RETURN);
-      }
-  };
+  }
 };
 
 } // namespace BIR
diff --git a/gcc/rust/checks/errors/borrowck/rust-bir-dump.cc b/gcc/rust/checks/errors/borrowck/rust-bir-dump.cc
index 6f1579df1d9..51dd1436350 100644
--- a/gcc/rust/checks/errors/borrowck/rust-bir-dump.cc
+++ b/gcc/rust/checks/errors/borrowck/rust-bir-dump.cc
@@ -7,14 +7,6 @@ namespace BIR {
 
 constexpr auto indentation = "    ";
 
-uint32_t
-get_lifetime_name (Lifetime lifetime_id)
-{
-  rust_assert (lifetime_id.id >= FIRST_NORMAL_LIFETIME_ID);
-  // Start from 1 as rustc does.
-  return lifetime_id.id - FIRST_NORMAL_LIFETIME_ID + 1;
-}
-
 std::string
 get_tyty_name (TyTy::BaseType *tyty)
 {
@@ -42,7 +34,7 @@ void
 renumber_places (const Function &func, std::vector<PlaceId> &place_map)
 {
   // Renumbering places to avoid gaps in the place id space.
-  // This is needed to match MIR shape.
+  // This is needed to match MIR's shape.
   size_t next_out_id = 0;
 
   for (size_t in_id = FIRST_VARIABLE_PLACE; in_id < func.place_db.size ();
@@ -116,8 +108,8 @@ Dump::go (bool enable_simplify_cfg)
     stream << "_" << place_map[place_id] << ": "
 	   << get_tyty_name (func.place_db[place_id].tyty);
   });
-  stream << ") -> " << get_tyty_name (func.place_db[RETURN_VALUE_PLACE].tyty)
-	 << " {\n";
+  stream << ") -> " << get_tyty_name (func.place_db[RETURN_VALUE_PLACE].tyty);
+  stream << " {\n";
 
   // Print locals declaration.
   visit_scope (0);
@@ -138,16 +130,17 @@ Dump::go (bool enable_simplify_cfg)
       BasicBlock &bb = func.basic_blocks[statement_bb];
       stream << "\n";
       stream << indentation << "bb" << bb_fold_map[statement_bb] << ": {\n";
+      size_t i = 0;
       for (auto &stmt : bb.statements)
 	{
-	  stream << indentation << indentation;
+	  stream << indentation << i++ << indentation;
 	  visit (stmt);
 	  stream << ";\n";
 	}
       if (!bb_terminated)
 	{
 	  stream << indentation << indentation << "goto -> bb"
-		 << bb_fold_map[bb.successors.at (0)] << ";\n";
+		 << bb_fold_map[bb.successors.at (0)] << ";\t\t" << i++ << "\n";
 	}
       stream << indentation << "}\n";
     }
@@ -196,6 +189,18 @@ Dump::visit (const Statement &stmt)
       visit_place (stmt.get_place ());
       stream << ")";
       break;
+    case Statement::Kind::USER_TYPE_ASCRIPTION:
+      visit_place (stmt.get_place ());
+      stream << " = ";
+      stream << "UserTypeAscription(";
+      stream << get_tyty_name (func.place_db[stmt.get_place ()].tyty);
+      stream << ")";
+      break;
+    case Statement::Kind::FAKE_READ:
+      stream << "FakeRead(";
+      visit_place (stmt.get_place ());
+      stream << ")";
+      break;
     }
   statement_place = INVALID_PLACE;
 }
@@ -250,22 +255,12 @@ void
 Dump::visit (const BorrowExpr &expr)
 {
   stream << "&";
-  visit_lifetime (statement_place);
   visit_place (expr.get_place ());
 }
 
 void
 Dump::visit_lifetime (PlaceId place_id)
-{
-  const Place &place = func.place_db[place_id];
-  if (place.lifetime.has_lifetime ())
-    {
-      if (place.lifetime.id == STATIC_LIFETIME_ID)
-	stream << "'static ";
-      else
-	stream << "'#" << get_lifetime_name (place.lifetime) << " ";
-    }
-}
+{}
 
 void
 Dump::visit (const InitializerExpr &expr)
@@ -358,7 +353,8 @@ Dump::visit_scope (ScopeId id, size_t depth)
     {
       indent (depth + 1) << "let _";
       stream << place_map[local] << ": "
-	     << get_tyty_name (func.place_db[local].tyty) << ";\n";
+	     << get_tyty_name (func.place_db[local].tyty);
+      stream << ";\n";
     }
   for (auto &child : scope.children)
     {
diff --git a/gcc/rust/checks/errors/borrowck/rust-bir-place.h b/gcc/rust/checks/errors/borrowck/rust-bir-place.h
index 546890d797c..f22ab112b3e 100644
--- a/gcc/rust/checks/errors/borrowck/rust-bir-place.h
+++ b/gcc/rust/checks/errors/borrowck/rust-bir-place.h
@@ -22,6 +22,11 @@
 #include "rust-mapping-common.h"
 #include "rust-system.h"
 #include "rust-tyty.h"
+#include "rust-bir-free-region.h"
+
+#include "rust-tyty-variance-analysis.h"
+#include "polonius/rust-polonius-ffi.h"
+#include "rust-hir-type-check.h"
 
 namespace Rust {
 namespace BIR {
@@ -33,30 +38,8 @@ 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};
+using Variance = TyTy::VarianceAnalysis::Variance;
+using LoanId = uint32_t;
 
 /**
  * Representation of lvalues and constants in BIR.
@@ -92,25 +75,72 @@ struct Place
   /** Copy trait */
   bool is_copy;
   bool has_drop = false;
-  Lifetime lifetime;
   TyTy::BaseType *tyty;
+  FreeRegions regions{{}};
+  std::vector<LoanId> borrowed_by{};
 
 public:
   Place (Kind kind, uint32_t variable_or_field_index, const Path &path,
-	 bool is_copy, const Lifetime &lifetime, TyTy::BaseType *tyty)
+	 bool is_copy, TyTy::BaseType *tyty)
     : kind (kind), variable_or_field_index (variable_or_field_index),
-      path (path), is_copy (is_copy), lifetime (lifetime), tyty (tyty)
+      path (path), is_copy (is_copy), tyty (tyty)
   {}
 
+  // Place can only be stored in PlaceDB and used via reference. Turn all
+  // accidental copies into errors.
+  Place (const Place &) = delete;
+  Place (Place &&) = default;
+
 public:
-  [[nodiscard]] bool is_lvalue () const
+  WARN_UNUSED_RESULT bool is_lvalue () const
   {
-    return kind == VARIABLE || kind == FIELD || kind == INDEX || kind == DEREF;
+    return kind == VARIABLE || is_path ();
   }
 
-  [[nodiscard]] bool is_rvalue () const { return kind == TEMPORARY; }
+  WARN_UNUSED_RESULT bool is_rvalue () const { return kind == TEMPORARY; }
 
   bool is_constant () const { return kind == CONSTANT; }
+
+  WARN_UNUSED_RESULT bool is_var () const
+  {
+    return kind == VARIABLE || kind == TEMPORARY;
+  }
+
+  WARN_UNUSED_RESULT bool is_path () const
+  {
+    return kind == FIELD || kind == INDEX || kind == DEREF;
+  }
+
+  WARN_UNUSED_RESULT TyTy::BaseType *get_fn_return_ty () const
+  {
+    switch (tyty->get_kind ())
+      {
+      case TyTy::FNPTR:
+	return tyty->as<TyTy::FnPtr> ()->get_return_type ();
+      case TyTy::FNDEF:
+	return tyty->as<TyTy::FnType> ()->get_return_type ();
+      default:
+	rust_assert (false);
+      }
+  }
+
+  WARN_UNUSED_RESULT bool is_indirect () const
+  {
+    // TODO: probably incomplete, check other projections
+    switch (tyty->get_kind ())
+      {
+      case TyTy::REF:
+      case TyTy::POINTER:
+	return true;
+      default:
+	return false;
+      }
+  }
+
+  WARN_UNUSED_RESULT bool should_be_moved () const
+  {
+    return kind == TEMPORARY || (!is_copy && kind != CONSTANT);
+  }
 };
 
 using ScopeId = uint32_t;
@@ -128,6 +158,12 @@ struct Scope
   std::vector<PlaceId> locals;
 };
 
+struct Loan
+{
+  Mutability mutability;
+  PlaceId place;
+};
+
 /** Allocated places and keeps track of paths. */
 class PlaceDB
 {
@@ -138,11 +174,15 @@ private:
   std::vector<Scope> scopes;
   ScopeId current_scope = 0;
 
+  std::vector<Loan> loans;
+
+  Polonius::Origin next_free_region = 1;
+
 public:
   PlaceDB ()
   {
     // Reserved index for invalid place.
-    places.push_back ({Place::INVALID, 0, {}, false, NO_LIFETIME, nullptr});
+    places.push_back ({Place::INVALID, 0, {}, false, nullptr});
 
     scopes.emplace_back (); // Root scope.
   }
@@ -150,8 +190,13 @@ public:
   Place &operator[] (PlaceId id) { return places.at (id); }
   const Place &operator[] (PlaceId id) const { return places.at (id); }
 
+  decltype (places)::const_iterator begin () const { return places.begin (); }
+  decltype (places)::const_iterator end () const { return places.end (); }
+
   size_t size () const { return places.size (); }
 
+  const std::vector<Loan> &get_loans () const { return loans; }
+
   ScopeId get_current_scope_id () const { return current_scope; }
 
   const std::vector<Scope> &get_scopes () const { return scopes; }
@@ -160,6 +205,12 @@ public:
 
   const Scope &get_scope (ScopeId id) const { return scopes[id]; }
 
+  FreeRegion get_next_free_region () { return next_free_region++; }
+
+  FreeRegion peek_next_free_region () const { return next_free_region; }
+
+  FreeRegion &expose_next_free_region () { return next_free_region; }
+
   ScopeId push_new_scope ()
   {
     ScopeId new_scope = scopes.size ();
@@ -176,31 +227,42 @@ public:
     return current_scope;
   }
 
-  PlaceId add_place (Place place, PlaceId last_sibling = 0)
+  PlaceId add_place (Place &&place, PlaceId last_sibling = 0)
   {
-    places.push_back (place);
+    places.emplace_back (std::forward<Place &&> (place));
     PlaceId new_place = places.size () - 1;
+    Place &new_place_ref = places[new_place]; // Intentional shadowing.
     if (last_sibling == 0)
       {
-	places[place.path.parent].path.first_child = new_place;
+	places[new_place_ref.path.parent].path.first_child = new_place;
       }
     else
       {
 	places[last_sibling].path.next_sibling = new_place;
       }
 
-    if (place.kind == Place::VARIABLE || place.kind == Place::TEMPORARY)
+    if (new_place_ref.kind == Place::VARIABLE
+	|| new_place_ref.kind == Place::TEMPORARY)
       {
 	scopes[current_scope].locals.push_back (new_place);
       }
 
+    auto variances = Resolver::TypeCheckContext::get ()
+		       ->get_variance_analysis_ctx ()
+		       .query_type_variances (new_place_ref.tyty);
+    std::vector<Polonius::Origin> regions;
+    for (size_t i = 0; i < variances.size (); i++)
+      {
+	regions.push_back (next_free_region++);
+      }
+    new_place_ref.regions.set_from (std::move (regions));
+
     return new_place;
   }
 
   PlaceId add_variable (NodeId id, TyTy::BaseType *tyty)
   {
-    return add_place (
-      {Place::VARIABLE, id, {}, is_type_copy (tyty), NO_LIFETIME, tyty}, 0);
+    return add_place ({Place::VARIABLE, id, {}, is_type_copy (tyty), tyty}, 0);
   }
 
   WARN_UNUSED_RESULT PlaceId lookup_or_add_path (Place::Kind kind,
@@ -222,15 +284,14 @@ public:
 	    current = places[current].path.next_sibling;
 	  }
       }
-    return add_place ({kind, id, Place::Path{parent, 0, 0}, is_type_copy (tyty),
-		       NO_LIFETIME, tyty},
+    return add_place ({kind, (uint32_t) id, Place::Path{parent, 0, 0},
+		       is_type_copy (tyty), tyty},
 		      current);
   }
 
   PlaceId add_temporary (TyTy::BaseType *tyty)
   {
-    return add_place (
-      {Place::TEMPORARY, 0, {}, is_type_copy (tyty), NO_LIFETIME, tyty}, 0);
+    return add_place ({Place::TEMPORARY, 0, {}, is_type_copy (tyty), tyty}, 0);
   }
 
   PlaceId get_constant (TyTy::BaseType *tyty)
@@ -238,11 +299,7 @@ public:
     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), lifetime, tyty};
-    places.push_back (place);
-    return places.size () - 1;
+    return add_place ({Place::CONSTANT, 0, {}, is_type_copy (tyty), tyty});
   }
 
   PlaceId lookup_variable (NodeId id)
@@ -257,15 +314,46 @@ public:
 	current++;
       }
     return INVALID_PLACE;
-  };
+  }
+
+  LoanId add_loan (Loan &&loan)
+  {
+    LoanId id = loans.size ();
+    loans.push_back (std::forward<Loan &&> (loan));
+    PlaceId borrowed_place = loans.rbegin ()->place;
+    places[loans.rbegin ()->place].borrowed_by.push_back (id);
+    if (places[borrowed_place].kind == Place::DEREF)
+      {
+	places[places[borrowed_place].path.parent].borrowed_by.push_back (id);
+      }
+    return id;
+  }
+
+  PlaceId get_var (PlaceId id) const
+  {
+    if (places[id].is_var ())
+      return id;
+    rust_assert (places[id].is_path ());
+    PlaceId current = id;
+    while (!places[current].is_var ())
+      {
+	current = places[current].path.parent;
+      }
+    return current;
+  }
+
+  void set_next_free_region (Polonius::Origin next_free_region)
+  {
+    this->next_free_region = next_free_region;
+  }
 
   PlaceId lookup_or_add_variable (NodeId id, TyTy::BaseType *tyty)
   {
     auto lookup = lookup_variable (id);
     if (lookup != INVALID_PLACE)
       return lookup;
-    add_place (
-      {Place::VARIABLE, id, {}, is_type_copy (tyty), NO_LIFETIME, tyty});
+
+    add_place ({Place::VARIABLE, id, {}, is_type_copy (tyty), tyty});
     return places.size () - 1;
   };
 
@@ -298,6 +386,7 @@ private:
     switch (ty->get_kind ())
       {
       case TyTy::REF:
+	return ty->as<TyTy::ReferenceType> ()->mutability () == Mutability::Imm;
       case TyTy::POINTER:
       case TyTy::SLICE:
       case TyTy::BOOL:
@@ -335,6 +424,21 @@ private:
       }
     rust_unreachable ();
   }
+
+  /** Check whether given place is not out-of-scope. */
+  WARN_UNUSED_RESULT bool is_in_scope (PlaceId place) const
+  {
+    for (ScopeId scope = current_scope; scope != INVALID_SCOPE;
+	 scope = scopes[scope].parent)
+      {
+	auto &scope_ref = scopes[scope];
+	if (std::find (scope_ref.locals.begin (), scope_ref.locals.end (),
+		       place)
+	    != scope_ref.locals.end ())
+	  return true;
+      }
+    return false;
+  }
 };
 
 } // namespace BIR
diff --git a/gcc/rust/checks/errors/borrowck/rust-bir.h b/gcc/rust/checks/errors/borrowck/rust-bir.h
index d21cb90abf5..4c298f14773 100644
--- a/gcc/rust/checks/errors/borrowck/rust-bir.h
+++ b/gcc/rust/checks/errors/borrowck/rust-bir.h
@@ -22,6 +22,9 @@
 #include "rust-bir-place.h"
 #include "rust-bir-visitor.h"
 
+#include "polonius/rust-polonius-ffi.h"
+#include "rust-tyty-variance-analysis.h"
+
 namespace Rust {
 
 namespace BIR {
@@ -30,6 +33,8 @@ struct BasicBlock;
 class Statement;
 class AbstractExpr;
 
+using LoanId = uint32_t;
+
 /**
  * Top-level entity of the Borrow-checker IR (BIR).
  * It represents a single function (method, closure, etc.), which is the
@@ -40,6 +45,9 @@ struct Function
   PlaceDB place_db;
   std::vector<PlaceId> arguments;
   std::vector<BasicBlock> basic_blocks;
+  FreeRegions universal_regions;
+  std::vector<std::pair<FreeRegion, FreeRegion>> universal_region_bounds;
+  location_t location;
 };
 
 /** Single statement of BIR. */
@@ -48,12 +56,14 @@ class Statement
 public:
   enum class Kind
   {
-    ASSIGNMENT,	  // <place> = <expr>
-    SWITCH,	  // switch <place>
-    RETURN,	  // return
-    GOTO,	  // goto
-    STORAGE_DEAD, // StorageDead(<place>)
-    STORAGE_LIVE, // StorageLive(<place>)
+    ASSIGNMENT,		  // <place> = <expr>
+    SWITCH,		  // switch <place>
+    RETURN,		  // return
+    GOTO,		  // goto
+    STORAGE_DEAD,	  // StorageDead(<place>)
+    STORAGE_LIVE,	  // StorageLive(<place>)
+    USER_TYPE_ASCRIPTION, // UserTypeAscription(<place>, <tyty>)
+    FAKE_READ,
   };
 
 private:
@@ -66,6 +76,7 @@ private:
   // ASSIGNMENT: rhs
   // otherwise: <unused>
   std::unique_ptr<AbstractExpr> expr;
+  TyTy::BaseType *type;
 
 public:
   Statement (PlaceId lhs, AbstractExpr *rhs)
@@ -77,10 +88,15 @@ public:
     : kind (kind), place (place), expr (expr)
   {}
 
+  explicit Statement (Kind kind, PlaceId place, TyTy::BaseType *type)
+    : kind (kind), place (place), type (type)
+  {}
+
 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; }
+  WARN_UNUSED_RESULT TyTy::BaseType *get_type () const { return type; }
 };
 
 /** Unique identifier for a basic block in the BIR. */
@@ -122,7 +138,7 @@ class AbstractExpr : public Visitable
 
 public:
   explicit AbstractExpr (ExprKind kind) : kind (kind) {}
-  [[nodiscard]] ExprKind get_kind () const { return kind; }
+  WARN_UNUSED_RESULT ExprKind get_kind () const { return kind; }
 };
 
 class InitializerExpr : public VisitableImpl<AbstractExpr, InitializerExpr>
@@ -165,12 +181,17 @@ public:
 class BorrowExpr : public VisitableImpl<AbstractExpr, BorrowExpr>
 {
   PlaceId place;
+  LoanId loan;
+  Polonius::Origin origin;
 
 public:
-  explicit BorrowExpr (PlaceId place)
-    : VisitableImpl<AbstractExpr, BorrowExpr> (ExprKind::BORROW), place (place)
+  explicit BorrowExpr (PlaceId place, LoanId loan_id, Polonius::Origin lifetime)
+    : VisitableImpl<AbstractExpr, BorrowExpr> (ExprKind::BORROW), place (place),
+      loan (loan_id), origin (lifetime)
   {}
   WARN_UNUSED_RESULT PlaceId get_place () const { return place; }
+  WARN_UNUSED_RESULT LoanId get_loan () const { return loan; }
+  WARN_UNUSED_RESULT Polonius::Origin get_origin () const { return origin; }
 };
 
 /**
@@ -191,19 +212,21 @@ public:
   WARN_UNUSED_RESULT PlaceId get_rhs () const { return rhs; }
 };
 
-class CallExpr : public VisitableImpl<AbstractExpr, CallExpr>
+class CallExpr final : public VisitableImpl<AbstractExpr, CallExpr>
 {
   std::vector<PlaceId> arguments;
   PlaceId callable;
 
 public:
   explicit CallExpr (PlaceId callable, std::vector<PlaceId> &&arguments)
-    : VisitableImpl<AbstractExpr, CallExpr> (ExprKind::CALL),
-      arguments (arguments), callable (callable)
+    : VisitableImpl (ExprKind::CALL), arguments (arguments), callable (callable)
   {}
 
 public:
-  const std::vector<PlaceId> &get_arguments () const { return arguments; }
+  WARN_UNUSED_RESULT const std::vector<PlaceId> &get_arguments () const
+  {
+    return arguments;
+  }
   WARN_UNUSED_RESULT PlaceId get_callable () const { return callable; }
 };
 
-- 
2.45.2