22099372517

Committed 17 Feb 2026 12:57PM UTC coverage: 88.855% (-1.4%) from 90.245%

Build # 22099372517

Build Type

Pull #183

github

Committed by

web-flow

Commit Message

Merge 794c66344 into 8ae76f97d

Pull Request Pull Request #183: Argument-granular whole program dataflow filtering

Run Details

240 of 374 new or added lines in 10 files covered. (64.17%)

6 existing lines in 2 files now uncovered.

4935 of 5554 relevant lines covered (88.85%)

32876.98 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

60.58

/lib/passes/filter/ACGFilter.cpp

// TypeART library
//
// Copyright (c) 2017-2025 TypeART Authors
// Distributed under the BSD 3-Clause license.
// (See accompanying file LICENSE.txt or copy at
// https://opensource.org/licenses/BSD-3-Clause)
//
// Project home: https://github.com/tudasc/TypeART
//
// SPDX-License-Identifier: BSD-3-Clause
//

#include "ACGFilter.h"

#include "Matcher.h"

#include <llvm/ADT/SmallSet.h>

namespace typeart::filter {

AcgFilterImpl::AcgFilterImpl(metacg::Mcg&& cg, std::unique_ptr<Matcher>&& m, std::unique_ptr<Matcher>&& deep)
    : mcg{std::move(cg)}, matcher{std::move(m)}, deep_matcher{std::move(deep)} {
}

FilterAnalysis AcgFilterImpl::reachesMatching(const ArrayRef<size_t> nodes, const size_t idx) {
  SmallVector<std::pair<size_t, size_t>, 64> workq{};
  SmallSet<size_t, 32> seen{};

  const auto enqueue = [&seen, &workq](const size_t it, const size_t i) {
    if (const auto [_, inserted] = seen.insert(it); inserted) {
      workq.push_back({it, i});
    }
  };

  for (const auto id : nodes) {
    enqueue(id, idx);
    LOG_DEBUG("Starting node with parameter [" << idx << "]: " << mcg.forId(id)->name.value_or(""));
  }

  while (!workq.empty()) {
    // Grab the current node ID and translate it into its corresponding function descriptor to check
    // if its name matches our matcher.
    const auto [current, cur_idx] = workq.pop_back_val();
    LOG_DEBUG("> Inspecting node: " << mcg.forId(current)->name.value_or(""));

    if (const auto fn = mcg.forId(current); fn && fn->name) {
      if (matcher->matchName(*fn->name) == Matcher::MatchResult::Match) {
        // Keep if the function matches the matcher
        LOG_DEBUG("-> Matches matcher, keeping");
        return FilterAnalysis::Keep;
      } else if (const auto r = oracle.matchName(*fn->name); r != Matcher::MatchResult::NoMatch) {
        // Ignore any known skippable functions
        switch (r) {
          case Matcher::MatchResult::ShouldSkip:
          case Matcher::MatchResult::ShouldContinue:
            LOG_DEBUG("-> Known function, skipping");
            continue;

          default:;
        }
      }
    } else if (fn && !fn->has_body) {
      // We have to be conservative if we reach an unknown function without a body
      LOG_DEBUG("-> Function has no body, keeping");
      return FilterAnalysis::Keep;
    }

    const auto outs = mcg.outputs(current, cur_idx);
    if (!outs) {
      LOG_DEBUG("-> Failed to get outputs, possibly leaf");
      continue;
    }

    for (const auto& out : *outs) {
      for (const auto callee : out.callees) {
        // if (!out.by_ref) {
        //   continue;
        // }
        enqueue(callee, out.idx);
        LOG_DEBUG("-> Enqueued callee: " << mcg.forId(callee)->name.value_or(""));
      }
    }
  }

  return FilterAnalysis::Continue;
}

FilterAnalysis AcgFilterImpl::precheck(Value* in, Function* start, const FPath&) {
  if (!start) {
    return FilterAnalysis::Continue;
  }

  FunctionAnalysis analysis{};
  analysis.analyze(start);

  // Filter if we're in a leaf function
  if (analysis.empty()) {
    return FilterAnalysis::Filter;
  }

  if (isTempAlloc(in)) {
    LOG_DEBUG("Alloca is a temporary " << *in);
    return FilterAnalysis::Filter;
  }

  if (AllocaInst* alloc = dyn_cast<AllocaInst>(in)) {
    if (alloc->getAllocatedType()->isStructTy() && omp::OmpContext::allocaReachesTask(alloc)) {
      LOG_DEBUG("Alloca reaches task call " << *alloc)
      return FilterAnalysis::Filter;
    }
  }

  return FilterAnalysis::Continue;
}

FilterAnalysis AcgFilterImpl::indirect(const CallSite current, const Path& p) {
  SmallVector<size_t, 16> callees{};

  const auto arg = *p.getEndPrev();
  assert(arg && "Argument is missing");

  if (!is_contained(current.args(), arg)) {
    return FilterAnalysis::Continue;
  }

  const auto idx = std::distance(current.args().begin(), find(current.args(), arg));

  const auto* callLoc = current.getLocation();
  if (!callLoc) {
    LOG_DEBUG("No call location, continuing");
    return FilterAnalysis::Continue;
  }

  // Resolve the parent scope via debug metadata as it should stay consistent even through inlining
  const auto* parentScope = dyn_cast<DISubprogram>(callLoc->getScope());
  if (!parentScope) {
    LOG_DEBUG("Failed to get parent scope, continuing");
    return FilterAnalysis::Continue;
  }

  const auto parentNode = mcg.byName(parentScope->getName());
  if (!parentNode) {
    LOG_DEBUG("Failed to get parent node, continuing");
    return FilterAnalysis::Continue;
  }

  const auto parent = mcg.forId(*parentNode);
  assert(parent && "Malformed MCG");

  auto md = parent->meta.as<metacg::MdLocals>("localflow");
  if (!md) {
    LOG_DEBUG("Failed to get localflow for node, continuing");
    return FilterAnalysis::Continue;
  }

  for (const auto& local : md->locals) {
    if (local.loc == metacg::SrcLoc{callLoc->getColumn(), callLoc->getLine()}) {
      callees.append(local.callees.begin(), local.callees.end());
    }
  }

  const auto outs = mcg.outputs(*parentNode, idx);
  if (!outs) {
    return FilterAnalysis::Continue;
  }

  for (const auto& out : *outs) {
    callees.append(out.callees.begin(), out.callees.end());
  }

  return reachesMatching(callees, idx);
}

FilterAnalysis AcgFilterImpl::def(const CallSite current, const Path& p) {
  if (deep_matcher && deep_matcher->match(current) == Matcher::MatchResult::Match) {
#if LLVM_VERSION_MAJOR < 15
    auto result = correlate2void(current, p);
#else
    auto result = correlate2pointer(current, p);
#endif
    switch (result) {
      case ArgCorrelation::GlobalMismatch:
        [[fallthrough]];
      case ArgCorrelation::ExactMismatch:
        LOG_DEBUG("Correlated, continue search");
        return FilterAnalysis::Continue;
      default:
        return FilterAnalysis::Keep;
    }
  }
  const auto arg = *p.getEndPrev();
  assert(arg && "Argument is missing");

  if (!is_contained(current.args(), arg)) {
    return FilterAnalysis::Continue;
  }

  // Calculate the argument position
  const auto idx = std::distance(current.args().begin(), find(current.args(), arg));

  if (const auto node = mcg.byName(current.getCalledFunction()->getName()); node) {
    return reachesMatching({*node}, idx);
  } else {
    // Fn not in CG? ask the oracle first, e.g., for __typeart instrumentation:
    const auto oracle_match = oracle.match(current);
    switch (oracle_match) {
      case Matcher::MatchResult::ShouldSkip: {
        return FilterAnalysis::Skip;
      }
      case Matcher::MatchResult::ShouldContinue: {
        return FilterAnalysis::Continue;
      }
      default:
        break;
    }

    // Be conservative if the function is not recorded in the call graph
    LOG_DEBUG("Unrecorded function, keeping: " << current.getCalledFunction()->getName());
    return FilterAnalysis::Keep;
  }
}

FilterAnalysis AcgFilterImpl::decl(const CallSite current, const Path& p) {
  return def(current, p);
}

}  // namespace typeart::filter

1	// TypeART library
2	//
3	// Copyright (c) 2017-2025 TypeART Authors
4	// Distributed under the BSD 3-Clause license.
5	// (See accompanying file LICENSE.txt or copy at
6	// https://opensource.org/licenses/BSD-3-Clause)
7	//
8	// Project home: https://github.com/tudasc/TypeART
9	//
10	// SPDX-License-Identifier: BSD-3-Clause
11	//
12
13	#include "ACGFilter.h"
14
15	#include "Matcher.h"
16
17	#include <llvm/ADT/SmallSet.h>
18
19	namespace typeart::filter {
20
21	AcgFilterImpl::AcgFilterImpl(metacg::Mcg&& cg, std::unique_ptr<Matcher>&& m, std::unique_ptr<Matcher>&& deep)	162✔
22	: mcg{std::move(cg)}, matcher{std::move(m)}, deep_matcher{std::move(deep)} {	81✔
23	}	81✔
24
25	FilterAnalysis AcgFilterImpl::reachesMatching(const ArrayRef<size_t> nodes, const size_t idx) {	117✔
26	SmallVector<std::pair<size_t, size_t>, 64> workq{};	117✔
27	SmallSet<size_t, 32> seen{};	117✔
28
29	const auto enqueue = [&seen, &workq](const size_t it, const size_t i) {	366✔
30	if (const auto [_, inserted] = seen.insert(it); inserted) {	420✔
31	workq.push_back({it, i});	249✔
32	}	249✔
33	};	249✔
34
35	for (const auto id : nodes) {	234✔
36	enqueue(id, idx);	117✔
37	LOG_DEBUG("Starting node with parameter [" << idx << "]: " << mcg.forId(id)->name.value_or(""));
38	}
39
40	while (!workq.empty()) {	291✔
41	// Grab the current node ID and translate it into its corresponding function descriptor to check
42	// if its name matches our matcher.
43	const auto [current, cur_idx] = workq.pop_back_val();	519✔
44	LOG_DEBUG("> Inspecting node: " << mcg.forId(current)->name.value_or(""));
45
46	if (const auto fn = mcg.forId(current); fn && fn->name) {	693✔
47	if (matcher->matchName(*fn->name) == Matcher::MatchResult::Match) {	249✔
48	// Keep if the function matches the matcher
49	LOG_DEBUG("-> Matches matcher, keeping");
50	return FilterAnalysis::Keep;	75✔
51	} else if (const auto r = oracle.matchName(*fn->name); r != Matcher::MatchResult::NoMatch) {	174✔
52	// Ignore any known skippable functions
NEW 53	switch (r) {	×
54	case Matcher::MatchResult::ShouldSkip:
55	case Matcher::MatchResult::ShouldContinue:
56	LOG_DEBUG("-> Known function, skipping");
NEW 57	continue;	×
58
59	default:;
NEW 60	}	×
NEW 61	}	×
62	} else if (fn && !fn->has_body) {	174✔
63	// We have to be conservative if we reach an unknown function without a body
64	LOG_DEBUG("-> Function has no body, keeping");
NEW 65	return FilterAnalysis::Keep;	×
66	}
67
68	const auto outs = mcg.outputs(current, cur_idx);	444✔
69	if (!outs) {	174✔
70	LOG_DEBUG("-> Failed to get outputs, possibly leaf");
71	continue;	60✔
72	}
73
74	for (const auto& out : *outs) {	228✔
75	for (const auto callee : out.callees) {	246✔
76	// if (!out.by_ref) {
77	// continue;
78	// }
79	enqueue(callee, out.idx);	132✔
80	LOG_DEBUG("-> Enqueued callee: " << mcg.forId(callee)->name.value_or(""));
81	}
82	}
83	}	174✔
84
85	return FilterAnalysis::Continue;	42✔
86	}	117✔
87
88	FilterAnalysis AcgFilterImpl::precheck(Value* in, Function* start, const FPath&) {	261✔
89	if (!start) {	261✔
NEW 90	return FilterAnalysis::Continue;	×
91	}
92
93	FunctionAnalysis analysis{};	261✔
94	analysis.analyze(start);	261✔
95
96	// Filter if we're in a leaf function
97	if (analysis.empty()) {	261✔
NEW 98	return FilterAnalysis::Filter;	×
99	}
100
101	if (isTempAlloc(in)) {	261✔
102	LOG_DEBUG("Alloca is a temporary " << *in);
NEW 103	return FilterAnalysis::Filter;	×
104	}
105
106	if (AllocaInst* alloc = dyn_cast<AllocaInst>(in)) {	261✔
107	if (alloc->getAllocatedType()->isStructTy() && omp::OmpContext::allocaReachesTask(alloc)) {	261✔
108	LOG_DEBUG("Alloca reaches task call " << *alloc)
NEW 109	return FilterAnalysis::Filter;	×
110	}
111	}	261✔
112
113	return FilterAnalysis::Continue;	261✔
114	}	261✔
115
116	FilterAnalysis AcgFilterImpl::indirect(const CallSite current, const Path& p) {	18✔
117	SmallVector<size_t, 16> callees{};	18✔
118
119	const auto arg = *p.getEndPrev();	18✔
120	assert(arg && "Argument is missing");	36✔
121
122	if (!is_contained(current.args(), arg)) {	18✔
123	return FilterAnalysis::Continue;	18✔
124	}
125
NEW 126	const auto idx = std::distance(current.args().begin(), find(current.args(), arg));	×
127
NEW 128	const auto* callLoc = current.getLocation();	×
NEW 129	if (!callLoc) {	×
130	LOG_DEBUG("No call location, continuing");
NEW 131	return FilterAnalysis::Continue;	×
132	}
133
134	// Resolve the parent scope via debug metadata as it should stay consistent even through inlining
NEW 135	const auto* parentScope = dyn_cast<DISubprogram>(callLoc->getScope());	×
NEW 136	if (!parentScope) {	×
137	LOG_DEBUG("Failed to get parent scope, continuing");
NEW 138	return FilterAnalysis::Continue;	×
139	}
140
NEW 141	const auto parentNode = mcg.byName(parentScope->getName());	×
NEW 142	if (!parentNode) {	×
143	LOG_DEBUG("Failed to get parent node, continuing");
NEW 144	return FilterAnalysis::Continue;	×
145	}
146
NEW 147	const auto parent = mcg.forId(*parentNode);	×
NEW 148	assert(parent && "Malformed MCG");	×
149
NEW 150	auto md = parent->meta.as<metacg::MdLocals>("localflow");	×
NEW 151	if (!md) {	×
152	LOG_DEBUG("Failed to get localflow for node, continuing");
NEW 153	return FilterAnalysis::Continue;	×
154	}
155
NEW 156	for (const auto& local : md->locals) {	×
NEW 157	if (local.loc == metacg::SrcLoc{callLoc->getColumn(), callLoc->getLine()}) {	×
NEW 158	callees.append(local.callees.begin(), local.callees.end());	×
NEW 159	}	×
160	}
161
NEW 162	const auto outs = mcg.outputs(*parentNode, idx);	×
NEW 163	if (!outs) {	×
NEW 164	return FilterAnalysis::Continue;	×
165	}
166
NEW 167	for (const auto& out : *outs) {	×
NEW 168	callees.append(out.callees.begin(), out.callees.end());	×
169	}
170
NEW 171	return reachesMatching(callees, idx);	×
172	}	18✔
173
174	FilterAnalysis AcgFilterImpl::def(const CallSite current, const Path& p) {	258✔
175	if (deep_matcher && deep_matcher->match(current) == Matcher::MatchResult::Match) {	258✔
176	#if LLVM_VERSION_MAJOR < 15
177	auto result = correlate2void(current, p);	42✔
178	#else
179	auto result = correlate2pointer(current, p);	99✔
180	#endif
181	switch (result) {	141✔
182	case ArgCorrelation::GlobalMismatch:
183	[[fallthrough]];
184	case ArgCorrelation::ExactMismatch:
185	LOG_DEBUG("Correlated, continue search");
186	return FilterAnalysis::Continue;	72✔
187	default:
188	return FilterAnalysis::Keep;	69✔
189	}
190	}
191	const auto arg = *p.getEndPrev();	117✔
192	assert(arg && "Argument is missing");	234✔
193
194	if (!is_contained(current.args(), arg)) {	117✔
NEW 195	return FilterAnalysis::Continue;	×
196	}
197
198	// Calculate the argument position
199	const auto idx = std::distance(current.args().begin(), find(current.args(), arg));	117✔
200
201	if (const auto node = mcg.byName(current.getCalledFunction()->getName()); node) {	117✔
202	return reachesMatching({*node}, idx);	117✔
203	} else {
204	// Fn not in CG? ask the oracle first, e.g., for __typeart instrumentation:
NEW 205	const auto oracle_match = oracle.match(current);	×
NEW 206	switch (oracle_match) {	×
207	case Matcher::MatchResult::ShouldSkip: {
NEW 208	return FilterAnalysis::Skip;	×
209	}
210	case Matcher::MatchResult::ShouldContinue: {
NEW 211	return FilterAnalysis::Continue;	×
212	}
213	default:
NEW 214	break;	×
215	}
216
217	// Be conservative if the function is not recorded in the call graph
218	LOG_DEBUG("Unrecorded function, keeping: " << current.getCalledFunction()->getName());
NEW 219	return FilterAnalysis::Keep;	×
220	}
221	}	258✔
222
223	FilterAnalysis AcgFilterImpl::decl(const CallSite current, const Path& p) {	126✔
224	return def(current, p);	126✔
225	}
226
227	} // namespace typeart::filter

tudasc / TypeART / 22099372517

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous