Call Graph of Monomorphized MIR Functions?

Qwaz · November 4, 2019, 5:39pm

Hello,

I'm trying to create a call graph of monomorphized MIR functions including items in dependency crates. What I'm currently doing is roughly as follows:

Create custom compiler calls. I followed MIRI's code here.
Inside after_analysis hook, I called collect_crate_mono_items to find all mono items of the main crate. These are used as entry points of the call graph generation.
Find the MIR body of instances. For this part, I referred to MIRI's find_fn and rustc InterpCx's load_mir.
Check the terminator of each basic block in MIR body. If it is TyKind::FnDef(def_id, substs), invoke Instance::resolve(tcx, tcx.param_env(def_id), def_id, substs) to get the next monomorphized instance. Recurse to step 3.

The problem is in step 4; the compiler fails to handle some cases when Instance::resolve is called and panics. I also tried replacing tcx.param_env(def_id) to ParamEnv::reveal_all(), but the result was same. These are the backtrace of such cases.

Can somebody help me pointing out what is wrong here, please?

...
[2019-11-04T17:25:44Z INFO  crux::call_graph] Instance: Instance { def: Item(DefId(2:30848 ~ core[1906]::fmt[0]::{{impl}}[47]::fmt[0])), substs: [ReErased, std::io::Error] }
[2019-11-04T17:25:44Z INFO  crux::utils] Printing MIR for Instance { def: Item(DefId(2:30848 ~ core[1906]::fmt[0]::{{impl}}[47]::fmt[0])), substs: [ReErased, std::io::Error] }
error: internal compiler error: src/librustc/traits/codegen/mod.rs:53: Encountered error `Unimplemented` selecting `Binder(<T as std::fmt::Debug>)` during codegen

thread 'rustc' panicked at 'Box<Any>', src/librustc_errors/lib.rs:915:9
stack backtrace:
   0: backtrace::backtrace::libunwind::trace
             at /cargo/registry/src/github.com-1ecc6299db9ec823/backtrace-0.3.37/src/backtrace/libunwind.rs:88
...
  20: rustc::util::bug::bug_fmt
  21: rustc::ty::context::GlobalCtxt::enter_local
  22: rustc::traits::codegen::codegen_fulfill_obligation
  23: rustc::ty::query::__query_compute::codegen_fulfill_obligation
  24: rustc::ty::query::<impl rustc::ty::query::config::QueryAccessors for rustc::ty::query::queries::codegen_fulfill_obligation>::compute
  25: rustc::dep_graph::graph::DepGraph::with_task_impl
  26: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt>::get_query
  27: rustc::ty::instance::Instance::resolve
  28: crux::call_graph::CallGraph::collect_all_calls
             at src/call_graph.rs:94
  29: crux::call_graph::CallGraph::traverse
             at src/call_graph.rs:56
...

...
[2019-11-04T17:33:00Z INFO  crux::call_graph] Instance: Instance { def: Item(DefId(1:324 ~ std[9b61]::thread[0]::local[0]::{{impl}}[4]::try_with[0])), substs: [std::cell::RefCell<std::option::Option<std::boxed::Box<dyn std::any::Any + std::marker::Send>>>, [closure@DefId(15:1058 ~ curl[62e6]::panic[0]::catch[0]::{{closure}}[0])], bool] }
[2019-11-04T17:33:00Z INFO  crux::utils] Printing MIR for Instance { def: Item(DefId(1:324 ~ std[9b61]::thread[0]::local[0]::{{impl}}[4]::try_with[0])), substs: [std::cell::RefCell<std::option::Option<std::boxed::Box<dyn std::any::Any + std::marker::Send>>>, [closure@DefId(15:1058 ~ curl[62e6]::panic[0]::catch[0]::{{closure}}[0])], bool] }
[INFO  rustc::traits::codegen] Cache miss: Binder(<std::result::Result<&T, std::thread::AccessError> as std::ops::Try>) => VtableImplData(impl_def_id=DefId(2:5448 ~ core[1906]::result[0]::{{impl}}[36]), substs=[&T, std::thread::AccessError], nested=[(), ()])
[INFO  rustc::traits::fulfill] selecting trait `Binder(TraitPredicate(<R as std::marker::Sized>))` at depth 1 yielded Err
error: internal compiler error: src/librustc/traits/codegen/mod.rs:127: Encountered errors `[FulfillmentError(Obligation(predicate=Binder(TraitPredicate(<R as std::marker::Sized>)), depth=1),Unimplemented)]` resolving bounds after type-checking

thread 'rustc' panicked at 'Box<Any>', src/librustc_errors/lib.rs:915:9
stack backtrace:
   0: backtrace::backtrace::libunwind::trace
             at /cargo/registry/src/github.com-1ecc6299db9ec823/backtrace-0.3.37/src/backtrace/libunwind.rs:88
   1: backtrace::backtrace::trace_unsynchronized
             at /cargo/registry/src/github.com-1ecc6299db9ec823/backtrace-0.3.37/src/backtrace/mod.rs:66
...
  20: rustc::util::bug::bug_fmt
  21: rustc::traits::codegen::<impl rustc::infer::InferCtxt>::drain_fulfillment_cx_or_panic
  22: rustc::ty::context::GlobalCtxt::enter_local
  23: rustc::traits::codegen::codegen_fulfill_obligation
  24: rustc::ty::query::__query_compute::codegen_fulfill_obligation
  25: rustc::ty::query::<impl rustc::ty::query::config::QueryAccessors for rustc::ty::query::queries::codegen_fulfill_obligation>::compute
  26: rustc::dep_graph::graph::DepGraph::with_task_impl
  27: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt>::get_query
  28: rustc::ty::instance::Instance::resolve
  29: crux::call_graph::CallGraph::collect_all_calls
             at src/call_graph.rs:94
  30: crux::call_graph::CallGraph::traverse
             at src/call_graph.rs:56
...

wesleywiser · November 4, 2019, 5:54pm

I think instead of tcx.param_env(def_id) you want to get the ParamEnv of the function instance you're currently processing (ie the caller, not the callee).

The MIR inliner does something similar. I'd recommend taking a look at it. Specifically here

github.com

rust-lang/rust/blob/2477e2493e67527fc282c7239e019f7ebd513a1a/src/librustc_mir/transform/inline.rs#L69


      
          // they do not call us.  Otherwise, we just don't try to
          // inline.
          //
          // We use a queue so that we inline "broadly" before we inline
          // in depth. It is unclear if this is the best heuristic,
          // really, but that's true of all the heuristics in this
          // file. =)
          
          let mut callsites = VecDeque::new();
          
          let param_env = self.tcx.param_env(self.source.def_id());
          
          // Only do inlining into fn bodies.
          let id = self.tcx.hir().as_local_hir_id(self.source.def_id()).unwrap();
          if self.tcx.hir().body_owner_kind(id).is_fn_or_closure()
              && self.source.promoted.is_none()
          {
              for (bb, bb_data) in caller_body.basic_blocks().iter_enumerated() {
                  if let Some(callsite) = self.get_valid_function_call(bb,
                                                                      bb_data,
                                                                      caller_body,

we get the ParamEnv of the callee which we then use here

github.com

rust-lang/rust/blob/2477e2493e67527fc282c7239e019f7ebd513a1a/src/librustc_mir/transform/inline.rs#L181


      
                                     caller_body: &Body<'tcx>,
                                     param_env: ParamEnv<'tcx>,
          ) -> Option<CallSite<'tcx>> {
              // Don't inline calls that are in cleanup blocks.
              if bb_data.is_cleanup { return None; }
          
              // Only consider direct calls to functions
              let terminator = bb_data.terminator();
              if let TerminatorKind::Call { func: ref op, .. } = terminator.kind {
                  if let ty::FnDef(callee_def_id, substs) = op.ty(caller_body, self.tcx).kind {
                      let instance = Instance::resolve(self.tcx,
                                                       param_env,
                                                       callee_def_id,
                                                       substs)?;
          
                      if let InstanceDef::Virtual(..) = instance.def {
                          return None;
                      }
          
                      return Some(CallSite {
                          callee: instance.def_id(),

To resolve the call to an Instance.

bjorn3 · November 4, 2019, 7:06pm

Actually during codegen ParamEnv::reveal_all() is always used.

The problem here is probably that the mir is not monomorphized. For every subst you get from the mir, you need to pass it through tcx.subst_and_normalize_erasing_regions(instance.substs, ParamEnv::reveal_all(), substs) where instance is the Instance of which you are processing the mir.

Qwaz · November 4, 2019, 7:50pm

Thank you so much!

system · February 2, 2020, 7:50pm

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.

Topic		Replies	Views
Resolving function calls from MIR terminators help	9	823	June 5, 2022
Need Help with Dumping MIR and Matching Binary Functions for Machine Learning Task help	1	202	June 30, 2023
Instrumenting MIR to trace program execution help	4	457	February 2, 2022
Implementing a call graph generator as a cargo extension help	1	87	April 1, 2025
Emitting MIR for analysis help	3	2294	January 12, 2023

Call Graph of Monomorphized MIR Functions?

Related topics