[PATCH Rust front-end v2 26/37] gccrs: Add dead code scan on HIR

[herron.philip@googlemail.com]

From: Thomas Young <wenzhang5800@gmail.com>

In order to find dead code we use a depth first search and keep liveness
variables, after type resolution. In this case, if a function is unused
and it calls another function the 2nd function is now unused since the
caller is not used etc. The algorithm is a depth first search.
---
 .../checks/lints/rust-lint-marklive-base.h    |  45 +++
 gcc/rust/checks/lints/rust-lint-marklive.cc   | 282 ++++++++++++++++
 gcc/rust/checks/lints/rust-lint-marklive.h    | 308 ++++++++++++++++++
 .../checks/lints/rust-lint-scan-deadcode.h    | 154 +++++++++
 4 files changed, 789 insertions(+)
 create mode 100644 gcc/rust/checks/lints/rust-lint-marklive-base.h
 create mode 100644 gcc/rust/checks/lints/rust-lint-marklive.cc
 create mode 100644 gcc/rust/checks/lints/rust-lint-marklive.h
 create mode 100644 gcc/rust/checks/lints/rust-lint-scan-deadcode.h

diff --git a/gcc/rust/checks/lints/rust-lint-marklive-base.h b/gcc/rust/checks/lints/rust-lint-marklive-base.h
new file mode 100644
index 00000000000..97c068188b1
--- /dev/null
+++ b/gcc/rust/checks/lints/rust-lint-marklive-base.h
@@ -0,0 +1,45 @@
+// Copyright (C) 2021-2022 Free Software Foundation, Inc.
+
+// This file is part of GCC.
+
+// GCC is free software; you can redistribute it and/or modify it under
+// the terms of the GNU General Public License as published by the Free
+// Software Foundation; either version 3, or (at your option) any later
+// version.
+
+// GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+// WARRANTY; without even the implied warranty of MERCHANTABILITY or
+// FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+// for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with GCC; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#ifndef RUST_HIR_LIVENESS_BASE
+#define RUST_HIR_LIVENESS_BASE
+
+#include "rust-diagnostics.h"
+#include "rust-lint-marklive.h"
+#include "rust-lint-marklive-base.h"
+#include "rust-hir-visitor.h"
+#include "rust-hir-map.h"
+
+namespace Rust {
+namespace Analysis {
+
+class MarkLiveBase : public HIR::HIRFullVisitorBase
+{
+public:
+  virtual ~MarkLiveBase () {}
+
+protected:
+  MarkLiveBase () : mappings (Analysis::Mappings::get ()) {}
+
+  Analysis::Mappings *mappings;
+};
+
+} // namespace Analysis
+} // namespace Rust
+
+#endif
diff --git a/gcc/rust/checks/lints/rust-lint-marklive.cc b/gcc/rust/checks/lints/rust-lint-marklive.cc
new file mode 100644
index 00000000000..245632b4b4c
--- /dev/null
+++ b/gcc/rust/checks/lints/rust-lint-marklive.cc
@@ -0,0 +1,282 @@
+// Copyright (C) 2021-2022 Free Software Foundation, Inc.
+
+// This file is part of GCC.
+
+// GCC is free software; you can redistribute it and/or modify it under
+// the terms of the GNU General Public License as published by the Free
+// Software Foundation; either version 3, or (at your option) any later
+// version.
+
+// GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+// WARRANTY; without even the implied warranty of MERCHANTABILITY or
+// FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+// for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with GCC; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// The idea is that all reachable symbols are live, codes called
+// from live codes are live, and everything else is dead.
+
+#include "rust-lint-marklive.h"
+#include "rust-hir-full.h"
+#include "rust-name-resolver.h"
+
+namespace Rust {
+namespace Analysis {
+
+// This class trys to find the live symbols which can be used as
+// seeds in MarkLive
+//
+// 1. TODO: explicit live
+//    - Attribute like #[allow(dead_code)]
+//    - Attribute like #[lang=".."], it's not a intra-crate item.
+// 2. TODO: foreign item
+class FindEntryPoint : public MarkLiveBase
+{
+  using Rust::Analysis::MarkLiveBase::visit;
+
+public:
+  static std::vector<HirId> find (HIR::Crate &crate)
+  {
+    FindEntryPoint findEntryPoint;
+    for (auto it = crate.items.begin (); it != crate.items.end (); it++)
+      {
+	it->get ()->accept_vis (findEntryPoint);
+      }
+    return findEntryPoint.getEntryPoint ();
+  }
+
+  // TODO not only fn main can be a entry point.
+  void visit (HIR::Function &function) override
+  {
+    if (function.get_function_name () == "main")
+      {
+	entryPoints.push_back (function.get_mappings ().get_hirid ());
+      }
+  }
+
+private:
+  FindEntryPoint () : MarkLiveBase () {}
+  std::vector<HirId> entryPoints;
+  std::vector<HirId> getEntryPoint () { return entryPoints; }
+};
+
+std::set<HirId>
+MarkLive::Analysis (HIR::Crate &crate)
+{
+  MarkLive marklive (FindEntryPoint::find (crate));
+  marklive.go (crate);
+
+  return marklive.liveSymbols;
+}
+
+// pop a live symbol from worklist every iteration,
+// if it's a function then walk the function body, and
+// 1. save all the live symbols in worklist which is
+//    visited first time
+// 2. save all the live symbols in liveSymbols
+void
+MarkLive::go (HIR::Crate &crate)
+{
+  while (!worklist.empty ())
+    {
+      HirId hirId = worklist.back ();
+      worklist.pop_back ();
+      scannedSymbols.emplace (hirId);
+      HIR::Item *item = mappings->lookup_hir_item (hirId);
+      liveSymbols.emplace (hirId);
+      if (item != nullptr)
+	{
+	  item->accept_vis (*this);
+	}
+      else
+	{ // the item maybe inside a trait impl
+	  HirId parent_impl_id = UNKNOWN_HIRID;
+	  HIR::ImplItem *implItem
+	    = mappings->lookup_hir_implitem (hirId, &parent_impl_id);
+	  if (implItem != nullptr)
+	    implItem->accept_vis (*this);
+	}
+    }
+}
+
+void
+MarkLive::visit (HIR::PathInExpression &expr)
+{
+  // We should iterate every path segment in order to mark the struct which
+  // is used in expression like Foo::bar(), we should mark the Foo alive.
+  expr.iterate_path_segments ([&] (HIR::PathExprSegment &seg) -> bool {
+    return visit_path_segment (seg);
+  });
+
+  // after iterate the path segments, we should mark functions and associated
+  // functions alive.
+  NodeId ast_node_id = expr.get_mappings ().get_nodeid ();
+  NodeId ref_node_id = UNKNOWN_NODEID;
+  find_ref_node_id (ast_node_id, ref_node_id);
+
+  // node back to HIR
+  HirId ref;
+  bool ok = mappings->lookup_node_to_hir (ref_node_id, &ref);
+  rust_assert (ok);
+
+  // it must resolve to some kind of HIR::Item or HIR::InheritImplItem
+  HIR::Item *resolved_item = mappings->lookup_hir_item (ref);
+  if (resolved_item != nullptr)
+    {
+      mark_hir_id (resolved_item->get_mappings ().get_hirid ());
+    }
+  else
+    {
+      HirId parent_impl_id = UNKNOWN_HIRID;
+      HIR::ImplItem *resolved_item
+	= mappings->lookup_hir_implitem (ref, &parent_impl_id);
+      if (resolved_item != nullptr)
+	{
+	  mark_hir_id (resolved_item->get_impl_mappings ().get_hirid ());
+	}
+    }
+}
+
+void
+MarkLive::visit (HIR::MethodCallExpr &expr)
+{
+  expr.get_receiver ()->accept_vis (*this);
+  visit_path_segment (expr.get_method_name ());
+  for (auto &argument : expr.get_arguments ())
+    argument->accept_vis (*this);
+
+  // Trying to find the method definition and mark it alive.
+  NodeId ast_node_id = expr.get_mappings ().get_nodeid ();
+  NodeId ref_node_id = UNKNOWN_NODEID;
+  find_ref_node_id (ast_node_id, ref_node_id);
+
+  // node back to HIR
+  HirId ref;
+  bool ok = mappings->lookup_node_to_hir (ref_node_id, &ref);
+  rust_assert (ok);
+  mark_hir_id (ref);
+}
+
+bool
+MarkLive::visit_path_segment (HIR::PathExprSegment seg)
+{
+  NodeId ast_node_id = seg.get_mappings ().get_nodeid ();
+  NodeId ref_node_id = UNKNOWN_NODEID;
+
+  // There are two different kinds of segment for us.
+  // 1. function segment
+  //      like the symbol "foo" in expression `foo()`.
+  // 2. type segment
+  //      like the symbol "Foo" in expression `Foo{a: 1, b: 2}`
+  //
+  // We should mark them alive all and ignoring other kind of segments.
+  // If the segment we dont care then just return false is fine
+  if (!resolver->lookup_resolved_name (ast_node_id, &ref_node_id))
+    {
+      if (!resolver->lookup_resolved_type (ast_node_id, &ref_node_id))
+	return false;
+    }
+  HirId ref;
+  bool ok = mappings->lookup_node_to_hir (ref_node_id, &ref);
+  rust_assert (ok);
+  mark_hir_id (ref);
+  return true;
+}
+
+void
+MarkLive::visit (HIR::FieldAccessExpr &expr)
+{
+  // visit receiver at first
+  expr.get_receiver_expr ()->accept_vis (*this);
+
+  // resolve the receiver back to ADT type
+  TyTy::BaseType *receiver = nullptr;
+  if (!tyctx->lookup_type (
+	expr.get_receiver_expr ()->get_mappings ().get_hirid (), &receiver))
+    {
+      rust_error_at (expr.get_receiver_expr ()->get_locus (),
+		     "unresolved type for receiver");
+    }
+
+  TyTy::ADTType *adt = nullptr;
+  if (receiver->get_kind () == TyTy::TypeKind::ADT)
+    {
+      adt = static_cast<TyTy::ADTType *> (receiver);
+    }
+  else if (receiver->get_kind () == TyTy::TypeKind::REF)
+    {
+      TyTy::ReferenceType *r = static_cast<TyTy::ReferenceType *> (receiver);
+      TyTy::BaseType *b = r->get_base ();
+      rust_assert (b->get_kind () == TyTy::TypeKind::ADT);
+
+      adt = static_cast<TyTy::ADTType *> (b);
+    }
+
+  rust_assert (adt != nullptr);
+  rust_assert (!adt->is_enum ());
+  rust_assert (adt->number_of_variants () == 1);
+
+  TyTy::VariantDef *variant = adt->get_variants ().at (0);
+
+  // get the field index
+  size_t index;
+  TyTy::StructFieldType *field;
+  bool ok = variant->lookup_field (expr.get_field_name (), &field, &index);
+  rust_assert (ok);
+  if (index >= variant->num_fields ())
+    {
+      rust_error_at (expr.get_receiver_expr ()->get_locus (),
+		     "cannot access struct %s by index: %lu",
+		     adt->get_name ().c_str (), (unsigned long) index);
+      return;
+    }
+
+  // get the field hir id
+  HirId field_id = field->get_ref ();
+  mark_hir_id (field_id);
+}
+
+void
+MarkLive::visit (HIR::TupleIndexExpr &expr)
+{
+  // TODO: unused tuple field detection
+  expr.get_tuple_expr ()->accept_vis (*this);
+}
+
+void
+MarkLive::visit (HIR::TypeAlias &alias)
+{
+  NodeId ast_node_id;
+  resolver->lookup_resolved_type (
+    alias.get_type_aliased ()->get_mappings ().get_nodeid (), &ast_node_id);
+  HirId hir_id;
+  bool ok = mappings->lookup_node_to_hir (ast_node_id, &hir_id);
+  rust_assert (ok);
+  mark_hir_id (hir_id);
+}
+
+void
+MarkLive::mark_hir_id (HirId id)
+{
+  if (scannedSymbols.find (id) == scannedSymbols.end ())
+    {
+      worklist.push_back (id);
+    }
+  liveSymbols.emplace (id);
+}
+
+void
+MarkLive::find_ref_node_id (NodeId ast_node_id, NodeId &ref_node_id)
+{
+  if (!resolver->lookup_resolved_name (ast_node_id, &ref_node_id))
+    {
+      bool ok = resolver->lookup_resolved_type (ast_node_id, &ref_node_id);
+      rust_assert (ok);
+    }
+}
+
+} // namespace Analysis
+} // namespace Rust
diff --git a/gcc/rust/checks/lints/rust-lint-marklive.h b/gcc/rust/checks/lints/rust-lint-marklive.h
new file mode 100644
index 00000000000..119af8b8c95
--- /dev/null
+++ b/gcc/rust/checks/lints/rust-lint-marklive.h
@@ -0,0 +1,308 @@
+// Copyright (C) 2021-2022 Free Software Foundation, Inc.
+
+// This file is part of GCC.
+
+// GCC is free software; you can redistribute it and/or modify it under
+// the terms of the GNU General Public License as published by the Free
+// Software Foundation; either version 3, or (at your option) any later
+// version.
+
+// GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+// WARRANTY; without even the implied warranty of MERCHANTABILITY or
+// FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+// for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with GCC; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#ifndef RUST_HIR_LIVENESS
+#define RUST_HIR_LIVENESS
+
+#include "rust-hir-full-decls.h"
+#include "rust-hir-map.h"
+#include "rust-lint-marklive-base.h"
+#include "rust-name-resolver.h"
+
+namespace Rust {
+namespace Analysis {
+
+class MarkLive : public MarkLiveBase
+{
+  using Rust::Analysis::MarkLiveBase::visit;
+
+public:
+  static std::set<HirId> Analysis (HIR::Crate &crate);
+  void go (HIR::Crate &crate);
+
+  void visit (HIR::PathInExpression &expr) override;
+  void visit (HIR::FieldAccessExpr &expr) override;
+  void visit (HIR::TupleIndexExpr &expr) override;
+  void visit (HIR::MethodCallExpr &expr) override;
+  void visit (HIR::TypeAlias &alias) override;
+
+  void visit (HIR::BorrowExpr &expr) override
+  {
+    expr.get_expr ()->accept_vis (*this);
+  }
+
+  void visit (HIR::DereferenceExpr &expr) override
+  {
+    expr.get_expr ()->accept_vis (*this);
+  }
+
+  void visit (HIR::NegationExpr &expr) override
+  {
+    expr.get_expr ()->accept_vis (*this);
+  }
+
+  void visit (HIR::LazyBooleanExpr &expr) override
+  {
+    expr.get_lhs ()->accept_vis (*this);
+    expr.get_rhs ()->accept_vis (*this);
+  }
+
+  void visit (HIR::TypeCastExpr &expr) override
+  {
+    expr.get_expr ()->accept_vis (*this);
+  }
+
+  void visit (HIR::GroupedExpr &expr) override
+  {
+    expr.get_expr_in_parens ()->accept_vis (*this);
+  }
+
+  void visit (HIR::ArrayExpr &expr) override
+  {
+    expr.get_internal_elements ()->accept_vis (*this);
+  }
+
+  void visit (HIR::ArrayIndexExpr &expr) override
+  {
+    expr.get_array_expr ()->accept_vis (*this);
+    expr.get_index_expr ()->accept_vis (*this);
+  }
+
+  void visit (HIR::ArrayElemsValues &expr) override
+  {
+    for (auto &elem : expr.get_values ())
+      {
+	elem->accept_vis (*this);
+      }
+  }
+
+  void visit (HIR::TupleExpr &expr) override
+  {
+    for (auto &elem : expr.get_tuple_elems ())
+      {
+	elem->accept_vis (*this);
+      }
+  }
+
+  void visit (HIR::BlockExpr &expr) override
+  {
+    for (auto &s : expr.get_statements ())
+      {
+	s->accept_vis (*this);
+      }
+    if (expr.has_expr ())
+      {
+	expr.get_final_expr ()->accept_vis (*this);
+      }
+  }
+
+  void visit (HIR::UnsafeBlockExpr &expr) override
+  {
+    expr.get_block_expr ()->accept_vis (*this);
+  }
+
+  void visit (HIR::LoopExpr &expr) override
+  {
+    expr.get_loop_block ()->accept_vis (*this);
+  }
+
+  void visit (HIR::BreakExpr &expr) override
+  {
+    if (expr.has_break_expr ())
+      expr.get_expr ()->accept_vis (*this);
+  }
+
+  void visit (HIR::WhileLoopExpr &expr) override
+  {
+    expr.get_loop_block ()->accept_vis (*this);
+    expr.get_predicate_expr ()->accept_vis (*this);
+  }
+
+  void visit (HIR::Function &function) override
+  {
+    function.get_definition ()->accept_vis (*this);
+  }
+
+  void visit (HIR::ReturnExpr &expr) override
+  {
+    if (expr.has_return_expr ())
+      expr.get_expr ()->accept_vis (*this);
+  }
+
+  void visit (HIR::WhileLetLoopExpr &expr) override
+  {
+    expr.get_loop_block ()->accept_vis (*this);
+    expr.get_cond ()->accept_vis (*this);
+  }
+
+  void visit (HIR::ForLoopExpr &expr) override
+  {
+    expr.get_loop_block ()->accept_vis (*this);
+    expr.get_iterator_expr ()->accept_vis (*this);
+  }
+
+  void visit (HIR::ExprStmtWithoutBlock &stmt) override
+  {
+    stmt.get_expr ()->accept_vis (*this);
+  }
+
+  void visit (HIR::ExprStmtWithBlock &stmt) override
+  {
+    stmt.get_expr ()->accept_vis (*this);
+  }
+
+  void visit (HIR::CallExpr &expr) override
+  {
+    expr.get_fnexpr ()->accept_vis (*this);
+    for (auto &argument : expr.get_arguments ())
+      argument->accept_vis (*this);
+  }
+
+  void visit (HIR::ArithmeticOrLogicalExpr &expr) override
+  {
+    expr.visit_lhs (*this);
+    expr.visit_rhs (*this);
+  }
+  void visit (HIR::ComparisonExpr &expr) override
+  {
+    expr.get_lhs ()->accept_vis (*this);
+    expr.get_rhs ()->accept_vis (*this);
+  }
+
+  void visit (HIR::AssignmentExpr &expr) override
+  {
+    expr.visit_lhs (*this);
+    expr.visit_rhs (*this);
+  }
+
+  void visit (HIR::CompoundAssignmentExpr &expr) override
+  {
+    expr.visit_lhs (*this);
+    expr.visit_rhs (*this);
+  }
+
+  void visit (HIR::IfExpr &expr) override
+  {
+    expr.get_if_condition ()->accept_vis (*this);
+    expr.get_if_block ()->accept_vis (*this);
+  }
+
+  void visit (HIR::IfExprConseqElse &expr) override
+  {
+    expr.get_if_condition ()->accept_vis (*this);
+    expr.get_if_block ()->accept_vis (*this);
+    expr.get_else_block ()->accept_vis (*this);
+  }
+
+  void visit (HIR::MatchExpr &expr) override
+  {
+    expr.get_scrutinee_expr ()->accept_vis (*this);
+    std::vector<HIR::MatchCase> &cases = expr.get_match_cases ();
+    for (auto &&caz : cases)
+      {
+	auto case_arm = caz.get_arm ();
+	if (case_arm.has_match_arm_guard ())
+	  case_arm.get_guard_expr ()->accept_vis (*this);
+	caz.get_expr ()->accept_vis (*this);
+      }
+  }
+
+  void visit (HIR::IfExprConseqIf &expr) override
+  {
+    expr.get_if_condition ()->accept_vis (*this);
+    expr.get_if_block ()->accept_vis (*this);
+    expr.get_conseq_if_expr ()->accept_vis (*this);
+  }
+
+  void visit (HIR::TraitItemFunc &item) override
+  {
+    item.get_block_expr ()->accept_vis (*this);
+  }
+
+  void visit (HIR::ImplBlock &impl) override
+  {
+    for (auto &&item : impl.get_impl_items ())
+      {
+	item->accept_vis (*this);
+      }
+  }
+
+  void visit (HIR::LetStmt &stmt) override
+  {
+    if (stmt.has_init_expr ())
+      {
+	stmt.get_init_expr ()->accept_vis (*this);
+      }
+  }
+
+  void visit (HIR::StructExprStruct &stct) override
+  {
+    stct.get_struct_name ().accept_vis (*this);
+  }
+
+  void visit (HIR::StructExprStructFields &stct) override
+  {
+    for (auto &field : stct.get_fields ())
+      {
+	field->accept_vis (*this);
+      }
+
+    stct.get_struct_name ().accept_vis (*this);
+    if (stct.has_struct_base ())
+      {
+	stct.struct_base->base_struct->accept_vis (*this);
+      }
+  }
+
+  virtual void visit (HIR::StructExprFieldIdentifierValue &field) override
+  {
+    field.get_value ()->accept_vis (*this);
+  }
+
+  void visit (HIR::StructExprStructBase &stct) override
+  {
+    stct.get_struct_base ()->base_struct->accept_vis (*this);
+  }
+
+  void visit (HIR::Module &module) override
+  {
+    for (auto &item : module.get_items ())
+      item->accept_vis (*this);
+  }
+
+private:
+  std::vector<HirId> worklist;
+  std::set<HirId> liveSymbols;
+  std::set<HirId> scannedSymbols;
+  Analysis::Mappings *mappings;
+  Resolver::Resolver *resolver;
+  Resolver::TypeCheckContext *tyctx;
+  MarkLive (std::vector<HirId> worklist)
+    : worklist (worklist), mappings (Analysis::Mappings::get ()),
+      resolver (Resolver::Resolver::get ()),
+      tyctx (Resolver::TypeCheckContext::get ()){};
+
+  void mark_hir_id (HirId);
+  bool visit_path_segment (HIR::PathExprSegment);
+  void find_ref_node_id (NodeId ast_node_id, NodeId &ref_node_id);
+};
+
+} // namespace Analysis
+} // namespace Rust
+
+#endif
diff --git a/gcc/rust/checks/lints/rust-lint-scan-deadcode.h b/gcc/rust/checks/lints/rust-lint-scan-deadcode.h
new file mode 100644
index 00000000000..591cb30bc24
--- /dev/null
+++ b/gcc/rust/checks/lints/rust-lint-scan-deadcode.h
@@ -0,0 +1,154 @@
+// Copyright (C) 2021-2022 Free Software Foundation, Inc.
+
+// This file is part of GCC.
+
+// GCC is free software; you can redistribute it and/or modify it under
+// the terms of the GNU General Public License as published by the Free
+// Software Foundation; either version 3, or (at your option) any later
+// version.
+
+// GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+// WARRANTY; without even the implied warranty of MERCHANTABILITY or
+// FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+// for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with GCC; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#ifndef RUST_HIR_SCAN_DEADCODE
+#define RUST_HIR_SCAN_DEADCODE
+
+#include "rust-hir-full-decls.h"
+#include "rust-hir-map.h"
+#include "rust-lint-marklive.h"
+#include "rust-name-resolver.h"
+#include "rust-diagnostics.h"
+
+namespace Rust {
+namespace Analysis {
+
+// Scan item symbols and warn the symbol if it is not in the live_symbols set.
+// There are three kinds of item we should handle in this pass.
+// 1. Function item
+// 2. The function item in the impl block without trait
+// 3. StructStruct, e.g., `Struct Foo{one: 1, two: 2}`. Furthermore, the unused
+//    struct fields will be warned too.
+// 4. TupleStruct, e.g., `Struct Foo(i32, i32)`
+class ScanDeadcode : public MarkLiveBase
+{
+  using Rust::Analysis::MarkLiveBase::visit;
+
+public:
+  static void Scan (HIR::Crate &crate)
+  {
+    std::set<HirId> live_symbols = Analysis::MarkLive::Analysis (crate);
+    ScanDeadcode sdc (live_symbols);
+    for (auto it = crate.items.begin (); it != crate.items.end (); it++)
+      {
+	it->get ()->accept_vis (sdc);
+      }
+  };
+
+  void visit (HIR::Function &function) override
+  {
+    HirId hirId = function.get_mappings ().get_hirid ();
+    if (should_warn (hirId))
+      {
+	if (mappings->is_impl_item (hirId))
+	  {
+	    HIR::ImplBlock *implBlock
+	      = mappings->lookup_associated_impl (hirId);
+	    if (!implBlock->has_trait_ref ())
+	      {
+		rust_warning_at (function.get_locus (), 0,
+				 "associated function is never used: %<%s%>",
+				 function.get_function_name ().c_str ());
+	      }
+	  }
+	else
+	  {
+	    rust_warning_at (function.get_locus (), 0,
+			     "function is never used: %<%s%>",
+			     function.get_function_name ().c_str ());
+	  }
+      }
+  }
+
+  void visit (HIR::StructStruct &stct) override
+  {
+    HirId hirId = stct.get_mappings ().get_hirid ();
+    if (should_warn (hirId))
+      {
+	bool name_starts_underscore = stct.get_identifier ().at (0) == '_';
+	if (!name_starts_underscore)
+	  rust_warning_at (stct.get_locus (), 0,
+			   "struct is never constructed: %<%s%>",
+			   stct.get_identifier ().c_str ());
+      }
+    else
+      {
+	// only warn the unused fields when in unwarned struct.
+	for (auto &field : stct.get_fields ())
+	  {
+	    HirId field_hir_id = field.get_mappings ().get_hirid ();
+	    if (should_warn (field_hir_id))
+	      {
+		rust_warning_at (field.get_locus (), 0,
+				 "field is never read: %<%s%>",
+				 field.get_field_name ().c_str ());
+	      }
+	  }
+      }
+  }
+
+  void visit (HIR::TupleStruct &stct) override
+  {
+    // only warn tuple struct unconstructed, and ignoring unused field
+    HirId hirId = stct.get_mappings ().get_hirid ();
+    if (should_warn (hirId))
+      {
+	rust_warning_at (stct.get_locus (), 0,
+			 "struct is never constructed: %<%s%>",
+			 stct.get_identifier ().c_str ());
+      }
+  }
+
+  void visit (HIR::ImplBlock &blc) override
+  {
+    if (blc.has_impl_items ())
+      {
+	for (auto &implItem : blc.get_impl_items ())
+	  {
+	    implItem->accept_vis (*this);
+	  }
+      }
+  }
+
+  void visit (HIR::Module &mod) override
+  {
+    for (auto &item : mod.get_items ())
+      item->accept_vis (*this);
+  }
+
+private:
+  std::set<HirId> live_symbols;
+  Resolver::Resolver *resolver;
+  Analysis::Mappings *mappings;
+
+  ScanDeadcode (std::set<HirId> &live_symbols)
+    : live_symbols (live_symbols), resolver (Resolver::Resolver::get ()),
+      mappings (Analysis::Mappings::get ()){};
+
+  bool should_warn (HirId hirId)
+  {
+    // TODO: There are more condition to check if should warn, i.e visibility,
+    // attributes.
+    return live_symbols.find (hirId) == live_symbols.end ();
+  }
+};
+
+} // namespace Analysis
+} // namespace Rust
+
+#endif
-- 
2.25.1