21639007075

Committed 03 Feb 2026 04:44PM UTC coverage: 88.438% (-1.8%) from 90.245%

Build # 21639007075

Build Type

Pull #183

github

Committed by

web-flow

Commit Message

Merge 4594bc77c into 8ae76f97d

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

Run Details

209 of 363 new or added lines in 10 files covered. (57.58%)

8 existing lines in 3 files now uncovered.

4903 of 5544 relevant lines covered (88.44%)

32492.57 hits per line

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

52.53

/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) {
        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 {
    // Be conservative if the function is not recorded in the call graph
    LOG_DEBUG("Unrecorded function, continuing: " << current.getCalledFunction()->getName());
    return FilterAnalysis::Continue;
  }
}

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)	72✔
22	: mcg{std::move(cg)}, matcher{std::move(m)}, deep_matcher{std::move(deep)} {	36✔
23	}	36✔
24
25	FilterAnalysis AcgFilterImpl::reachesMatching(const ArrayRef<size_t> nodes, const size_t idx) {	36✔
26	SmallVector<std::pair<size_t, size_t>, 64> workq{};	36✔
27	SmallSet<size_t, 32> seen{};	36✔
28
29	const auto enqueue = [&seen, &workq](const size_t it, const size_t i) {	72✔
30	if (const auto [_, inserted] = seen.insert(it); inserted) {	60✔
31	workq.push_back({it, i});	36✔
32	}	36✔
33	};	36✔
34
35	for (const auto id : nodes) {	72✔
36	enqueue(id, idx);	36✔
37	LOG_DEBUG("Starting node with parameter [" << idx << "]: " << mcg.forId(id)->name.value_or(""));
38	}
39
40	while (!workq.empty()) {	72✔
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();	96✔
44	LOG_DEBUG("> Inspecting node: " << mcg.forId(current)->name.value_or(""));
45
46	if (const auto fn = mcg.forId(current); fn && fn->name) {	102✔
47	if (matcher->matchName(*fn->name) == Matcher::MatchResult::Match) {	36✔
48	// Keep if the function matches the matcher
49	LOG_DEBUG("-> Matches matcher, keeping");
NEW 50	return FilterAnalysis::Keep;	×
51	} else if (const auto r = oracle.matchName(*fn->name); r != Matcher::MatchResult::NoMatch) {	36✔
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) {	36✔
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);	96✔
69	if (!outs) {	36✔
70	LOG_DEBUG("-> Failed to get outputs, possibly leaf");
71	continue;	36✔
72	}
73
NEW 74	for (const auto& out : *outs) {	×
NEW 75	for (const auto callee : out.callees) {	×
NEW 76	enqueue(callee, out.idx);	×
77	LOG_DEBUG("-> Enqueued callee: " << mcg.forId(callee)->name.value_or(""));
78	}
79	}
80	}	36✔
81
82	return FilterAnalysis::Continue;	36✔
83	}	36✔
84
85	FilterAnalysis AcgFilterImpl::precheck(Value* in, Function* start, const FPath&) {	126✔
86	if (!start) {	126✔
NEW 87	return FilterAnalysis::Continue;	×
88	}
89
90	FunctionAnalysis analysis{};	126✔
91	analysis.analyze(start);	126✔
92
93	// Filter if we're in a leaf function
94	if (analysis.empty()) {	126✔
NEW 95	return FilterAnalysis::Filter;	×
96	}
97
98	if (isTempAlloc(in)) {	126✔
99	LOG_DEBUG("Alloca is a temporary " << *in);
NEW 100	return FilterAnalysis::Filter;	×
101	}
102
103	if (AllocaInst* alloc = dyn_cast<AllocaInst>(in)) {	126✔
104	if (alloc->getAllocatedType()->isStructTy() && omp::OmpContext::allocaReachesTask(alloc)) {	126✔
105	LOG_DEBUG("Alloca reaches task call " << *alloc)
NEW 106	return FilterAnalysis::Filter;	×
107	}
108	}	126✔
109
110	return FilterAnalysis::Continue;	126✔
111	}	126✔
112
NEW 113	FilterAnalysis AcgFilterImpl::indirect(const CallSite current, const Path& p) {	×
NEW 114	SmallVector<size_t, 16> callees{};	×
115
NEW 116	const auto arg = *p.getEndPrev();	×
NEW 117	assert(arg && "Argument is missing");	×
118
NEW 119	if (!is_contained(current.args(), arg)) {	×
NEW 120	return FilterAnalysis::Continue;	×
121	}
122
NEW 123	const auto idx = std::distance(current.args().begin(), find(current.args(), arg));	×
124
NEW 125	const auto* callLoc = current.getLocation();	×
NEW 126	if (!callLoc) {	×
127	LOG_DEBUG("No call location, continuing");
NEW 128	return FilterAnalysis::Continue;	×
129	}
130
131	// Resolve the parent scope via debug metadata as it should stay consistent even through inlining
NEW 132	const auto* parentScope = dyn_cast<DISubprogram>(callLoc->getScope());	×
NEW 133	if (!parentScope) {	×
134	LOG_DEBUG("Failed to get parent scope, continuing");
NEW 135	return FilterAnalysis::Continue;	×
136	}
137
NEW 138	const auto parentNode = mcg.byName(parentScope->getName());	×
NEW 139	if (!parentNode) {	×
140	LOG_DEBUG("Failed to get parent node, continuing");
NEW 141	return FilterAnalysis::Continue;	×
142	}
143
NEW 144	const auto parent = mcg.forId(*parentNode);	×
NEW 145	assert(parent && "Malformed MCG");	×
146
NEW 147	auto md = parent->meta.as<metacg::MdLocals>("localflow");	×
NEW 148	if (!md) {	×
149	LOG_DEBUG("Failed to get localflow for node, continuing");
NEW 150	return FilterAnalysis::Continue;	×
151	}
152
NEW 153	for (const auto& local : md->locals) {	×
NEW 154	if (local.loc == metacg::SrcLoc{callLoc->getColumn(), callLoc->getLine()}) {	×
NEW 155	callees.append(local.callees.begin(), local.callees.end());	×
NEW 156	}	×
157	}
158
NEW 159	const auto outs = mcg.outputs(*parentNode, idx);	×
NEW 160	if (!outs) {	×
NEW 161	return FilterAnalysis::Continue;	×
162	}
163
NEW 164	for (const auto& out : *outs) {	×
NEW 165	callees.append(out.callees.begin(), out.callees.end());	×
166	}
167
NEW 168	return reachesMatching(callees, idx);	×
NEW 169	}	×
170
171	FilterAnalysis AcgFilterImpl::def(const CallSite current, const Path& p) {	126✔
172	if (deep_matcher && deep_matcher->match(current) == Matcher::MatchResult::Match) {	126✔
173	#if LLVM_VERSION_MAJOR < 15
174	auto result = correlate2void(current, p);	30✔
175	#else
176	auto result = correlate2pointer(current, p);	60✔
177	#endif
178	switch (result) {	90✔
179	case ArgCorrelation::GlobalMismatch:
180	[[fallthrough]];
181	case ArgCorrelation::ExactMismatch:
182	LOG_DEBUG("Correlated, continue search");
183	return FilterAnalysis::Continue;	72✔
184	default:
185	return FilterAnalysis::Keep;	18✔
186	}
187	}
188	const auto arg = *p.getEndPrev();	36✔
189	assert(arg && "Argument is missing");	72✔
190
191	if (!is_contained(current.args(), arg)) {	36✔
NEW 192	return FilterAnalysis::Continue;	×
193	}
194
195	// Calculate the argument position
196	const auto idx = std::distance(current.args().begin(), find(current.args(), arg));	36✔
197
198	if (const auto node = mcg.byName(current.getCalledFunction()->getName()); node) {	36✔
199	return reachesMatching({*node}, idx);	36✔
200	} else {
201	// Be conservative if the function is not recorded in the call graph
202	LOG_DEBUG("Unrecorded function, continuing: " << current.getCalledFunction()->getName());
NEW 203	return FilterAnalysis::Continue;	×
204	}
205	}	126✔
206
207	FilterAnalysis AcgFilterImpl::decl(const CallSite current, const Path& p) {	126✔
208	return def(current, p);	126✔
209	}
210
211	} // namespace typeart::filter

tudasc / TypeART / 21639007075

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