4373909195

Build Type

github

Committed by GitHub

Commit Message

<a href="https://github.com/tudasc/TypeART/commit/<a class=hub.com/tudasc/TypeART/commit/<a class="double-link" href="https://git"><a class=hub.com/tudasc/TypeART/commit/<a class="double-link" href="https://git"><a class=hub.com/tudasc/TypeART/commit/<a class="double-link" href="https://git"><a class=hub.com/tudasc/TypeART/commit/d487b62b0425803f265e6564a2dfbeebeeca87d0">d487b62b0">&lt;a href=&quot;https://github.com/tudasc/TypeART/commit/</a><a class="double-link" href="https://github.com/tudasc/TypeART/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://git">&lt;a class=</a>hub.com/tudasc/TypeART/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://git">&lt;a class=</a>hub.com/tudasc/TypeART/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://git">&lt;a class=</a>hub.com/tudasc/TypeART/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://git">&lt;a class=</a>hub.com/tudasc/TypeART/commit/d487b62b0425803f265e6564a2dfbeebeeca87d0">d487b62b0</a><a href="https://github.com/tudasc/TypeART/commit/d487b62b0425803f265e6564a2dfbeebeeca87d0">&quot;&gt;&amp;lt;a href=&amp;quot;https://github.com/tudasc/TypeART/commit/&lt;/a&gt;&lt;a class=&quot;double-link&quot; href=&quot;https://github.com/tudasc/TypeART/commit/&amp;lt;a class=&amp;quot;double-link&amp;quot; href=&amp;quot;https://git&quot;&gt;&amp;lt;a class=&lt;/a&gt;hub.com/tudasc/TypeART/commit/&amp;lt;a class=&amp;quot;double-link&amp;quot; href=&amp;quot;https://git&quot;&gt;&amp;lt;a class=&lt;/a&gt;hub.com/tudasc/TypeART/commit/&amp;lt;a class=&amp;quot;double-link&amp;quot; href=&amp;quot;https://git&quot;&gt;&amp;lt;a class=&lt;/a&gt;hub.com/tudasc/TypeART/commit/&amp;lt;a class=&amp;quot;double-link&amp;quot; href=&amp;quot;https://git&quot;&gt;&amp;lt;a class=&lt;/a&gt;hub.com/tudasc/TypeART/commit/&amp;lt;a class=&amp;quot;double-link&amp;quot; href=&amp;quot;https://git&quot;&gt;&amp;lt;a class=&lt;/a&gt;hub.com/tudasc/TypeART/commit/d487b62b0425803f265e6564a2dfbeebeeca87d0&quot;&gt;d487b62b0&lt;/a&gt;&lt;a href=&quot;https://github.com/tudasc/TypeART/commit/d487b62b0425803f265e6564a2dfbeebeeca87d0&quot;&gt;&amp;quot;&amp;gt;&amp;amp;lt;a href=&amp;amp;quot;https://github.com/tudasc/TypeART/commit/&amp;lt;/a&amp;gt;&amp;lt;a class=&amp;quot;dou... (continued)

Pull Request Pull Request #140: Feat/acg

Run Details

340 of 425 new or added lines in 15 files covered. (80.0%)

3767 of 4203 relevant lines covered (89.63%)

286966.72 hits per line

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

75.68

/lib/passes/filter/ACGForwardFilter.cpp

// TypeART library
//
// Copyright (c) 2017-2023 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 "ACGForwardFilter.h"

#include <llvm/IR/InstIterator.h>
#include <llvm/IR/IntrinsicInst.h>

using namespace llvm;

namespace typeart::filter {
using namespace util::metacg;

namespace detail {

/// follows all enqueued values and visits them once starting with an initial entry

enum VisitResult {
  VR_Continue = 0,
  VR_Stop,
};

template <typename T, typename CB>
inline void solveReachable(const std::vector<T>& Range, CB&& Callback) noexcept {
  llvm::SmallPtrSet<T const*, 32> Visited{};
  llvm::SmallVector<T const*, 64> Worklist{};

  const auto& Enqueue = [&](T const& Entry) noexcept -> bool {
    if (Visited.insert(&Entry).second) {
      Worklist.push_back(&Entry);
      return true;
    }
    return false;
  };

  for (const auto& Item : Range) {
    Enqueue(Item);
  }

  while (!Worklist.empty()) {
    T const* CurrentValue    = Worklist.pop_back_val();
    VisitResult const Status = Callback(*CurrentValue, Enqueue);
    switch (Status) {
      case VR_Continue:
        break;
      case VR_Stop:
        return;
    }
  }
}
}  // namespace detail

static FunctionDescriptor createFunctionNode(const JSONACG::node_type& JSON, const Regex& TargetMatcher) {
  const auto& Signature          = JSON.meta.signature;
  const bool IsTargetOfInterrest = TargetMatcher.match(Signature.identifier);

  return {IsTargetOfInterrest,
          JSON.hasBody,
          {},
          {},
          {Signature.identifier, Signature.paramTypes, Signature.returnType, Signature.isVariadic}};
}

static FunctionDescriptor const& retrieveFunction(const ACGDataMap& DataMap, const StringRef& FunctionName) {
  assert(DataMap.count(FunctionName) && "Found an edge to an undefined callee");
  if (DataMap.count(FunctionName) == 0) {
    throw std::runtime_error("Found an edge to an undefined callee: " + FunctionName.str());
  }
  return DataMap.find(FunctionName)->second;
}

static void insertCallsiteIdentifiers(const JSONACG::node_type& Json, FunctionDescriptor& Data, ACGDataMap& DataMap) {
  llvm::for_each(Json.meta.ipdf.callsites, [&](const auto& CallSites) {
    const auto& CalleeFunction = retrieveFunction(DataMap, CallSites.getKey());

    for (const auto& Identifier : CallSites.getValue()) {
      Data.callsiteCallees.emplace(Identifier.id, &CalleeFunction);
    }
  });
}

static void insertArgumentFlow(const JSONACG::node_type& Json, FunctionDescriptor& Data, ACGDataMap& DataMap) {
  llvm::for_each(Json.meta.ipdf.interFlow, [&](const auto& CallSites) {
    const auto& CalleeFunction = retrieveFunction(DataMap, CallSites.getKey());

    for (const auto& Edge : CallSites.getValue()) {
      FunctionDescriptor::ArgumentEdge const FlowEdge{Edge.formalArgNo, CalleeFunction};
      Data.reachableFormals.emplace(Edge.actualArgNo, FlowEdge);
    }
  });
}

ACGDataMap createDatabase(const Regex& TargetMatcher, JSONACG& MetaCg) {
  ACGDataMap DataMap;

  // insert nodes first, to avoid rehashing and invalidation of references
  llvm::for_each(MetaCg.nodes, [&](const auto& MetaCGNode) {
    DataMap.try_emplace(MetaCGNode.getKey(), createFunctionNode(MetaCGNode.getValue(), TargetMatcher));
  });

  llvm::for_each(DataMap, [&](auto& Entry) {
    insertCallsiteIdentifiers(MetaCg.nodes[Entry.getKey()], Entry.getValue(), DataMap);
    insertArgumentFlow(MetaCg.nodes[Entry.getKey()], Entry.getValue(), DataMap);
  });

  return DataMap;
}

/// tests if an edge can reach a void* argument
bool ACGFilterImpl::isFormalArgumentRelevant(const FunctionDescriptor::ArgumentEdge& Edge) const {
  return Edge.callee.functionSignature.paramIsType(Edge.formalArgumentNumber, VoidType);
}

/// an edge reaches a relevant formal argument
bool ACGFilterImpl::edgeReachesRelevantFormalArgument(const FunctionDescriptor::ArgumentEdge& Edge) const {
  return Edge.callee.isTarget && isFormalArgumentRelevant(Edge);
}

/// declaration with relevant formal argument, could reach indirect the destination
bool ACGFilterImpl::edgeMaybeReachesFormalArgument(const FunctionDescriptor::ArgumentEdge& Edge) const {
  return !Edge.callee.isTarget && !Edge.callee.isDefinition && isFormalArgumentRelevant(Edge);
}

template <typename RangeT>
inline FilterAnalysis ACGFilterImpl::ACGFilterImpl::analyseMaybeCandidates(const RangeT&& MaybeCandidates) const {
  bool HasContinue = false;
  bool HasSkip     = false;

  for (const auto& Candidate : MaybeCandidates) {
    switch (candidateMatcher.match(Candidate)) {
      case Matcher::MatchResult::Match:
        return FilterAnalysis::Keep;

      case Matcher::MatchResult::ShouldContinue:
        HasContinue = true;
        break;

      case Matcher::MatchResult::ShouldSkip:
        HasSkip = true;
        break;

      case Matcher::MatchResult::NoMatch:
        // keep the function if the matcher has no information
        return FilterAnalysis::Keep;
    }
  }

  // prioritize a continue
  if (HasContinue) {
    return FilterAnalysis::Continue;
  }

  if (HasSkip) {
    return FilterAnalysis::Skip;
  }

  // we have nothing found, use the default result
  return FilterAnalysis::Continue;
}

FilterAnalysis ACGFilterImpl::analyseFlowPath(const std::vector<FunctionDescriptor::ArgumentEdge>& InitialEdges) const {
  enum class ReachabilityResult { reaches, maybe_reaches, never_reaches };
  using namespace typeart::filter::detail;

  /// contains declarations which have at least one argument that is reachable and relevant
  StringSet MaybeCandidates;

  ReachabilityResult Result = ReachabilityResult::never_reaches;
  solveReachable(InitialEdges, [&](const FunctionDescriptor::ArgumentEdge& Edge, auto const& Enqueue) -> VisitResult {
    if (edgeReachesRelevantFormalArgument(Edge)) {
      Result = ReachabilityResult::reaches;
      return VR_Stop;
    }

    if (edgeMaybeReachesFormalArgument(Edge)) {
      Result = ReachabilityResult::maybe_reaches;
      MaybeCandidates.insert(Edge.callee.functionSignature.identifier);
    }

    // enqueue all edges that can be reached from the current callee/argument
    const auto& ReachableFormals = make_range(Edge.callee.reachableFormals.equal_range(Edge.formalArgumentNumber));
    for (const auto& [ActualNumber, FormalEdge] : ReachableFormals) {
      Enqueue(FormalEdge);
    }

    return VR_Continue;
  });

  switch (Result) {
    // check also the other call-sites
    case ReachabilityResult::never_reaches:
      return FilterAnalysis::Continue;

    case ReachabilityResult::maybe_reaches:
      return analyseMaybeCandidates(MaybeCandidates.keys());

    case ReachabilityResult::reaches:
      return FilterAnalysis::Keep;
  }
}

/// calculates all outgoing edges for a given parameter value of a callsite
[[nodiscard]] std::vector<FunctionDescriptor::ArgumentEdge> ACGFilterImpl::createEdgesForCallsite(
    const CallBase& Site, const llvm::Value& ActualArgument,
    const std::vector<const FunctionDescriptor*>& CalleesForCallsite) const {
  const auto&& CorrespondingArgs =
      llvm::make_filter_range(Site.args(), [&ActualArgument](const auto& Arg) { return Arg.get() == &ActualArgument; });

  std::vector<FunctionDescriptor::ArgumentEdge> Init;
  for (const auto& CallSiteArg : CorrespondingArgs) {
    for (const auto& Callee : CalleesForCallsite) {
      Init.emplace_back(FunctionDescriptor::ArgumentEdge{
          static_cast<int>(CallSiteArg.getOperandNo()) /*formal*/, *Callee /*callee*/
      });
    }
  }

  return Init;
}

std::string ACGFilterImpl::prepareLogMessage(const CallBase& Site, const Value& ActualArgument,
                                             const StringRef& Msg) const {
  std::string String;
  raw_string_ostream StringStream{String};
  StringStream << "function ";
  Site.getFunction()->printAsOperand(StringStream, false);
  StringStream << ": argument ";
  ActualArgument.printAsOperand(StringStream, false);
  StringStream << ": callsite ";
  Site.print(StringStream, true);
  StringStream << " (";
  Site.getDebugLoc().print(StringStream);
  StringStream << "): " << Msg;

  return String;
}

inline void ACGFilterImpl::logUnusedArgument(const llvm::CallBase& Site, const llvm::Value& ActualArgument) const {
  if (Site.getCalledOperand() == &ActualArgument) {
    LOG_DEBUG(prepareLogMessage(Site, ActualArgument, "Argument is CalledOperand of Callsite"))
    return;
  }

  // this can happen when the IRSearch finds a store-instruction and adds
  // the pointer operand to the successors.
  if (llvm::is_contained(Site.users(), &ActualArgument)) {
    LOG_DEBUG(prepareLogMessage(Site, ActualArgument, "Argument is User of Callsite"))
    return;
  }

  // this is a serious problem within the dataflow analysis
  LOG_ERROR(prepareLogMessage(Site, ActualArgument, "Argument is not used at Callsite"))
}

inline void ACGFilterImpl::logMissingCallees(const llvm::CallBase& Site, const llvm::Value&) const {
  std::string String;
  raw_string_ostream StringStream{String};
  StringStream << "function ";
  Site.getFunction()->printAsOperand(StringStream, false);
  StringStream << ": no callees found for callsite ";
  Site.print(StringStream, true);

  LOG_WARNING(String)
}

inline void ACGFilterImpl::logMissingEdges(const llvm::CallBase& Site, const llvm::Value& ActualArgument) const {
  std::string String;
  raw_string_ostream StringStream{String};
  StringStream << "function ";
  Site.getFunction()->printAsOperand(StringStream, false);
  StringStream << ": no edges found for argument ";
  ActualArgument.printAsOperand(StringStream, false);
  StringStream << " @ ";
  Site.print(StringStream, true);

  LOG_WARNING(String)
}

FilterAnalysis ACGFilterImpl::analyseCallsite(const llvm::CallBase& Site, const Path& Path) const {
  const llvm::Value* ActualArgument = Path.getEndPrev().getValue();
  assert(ActualArgument != nullptr && "Argument should not be null");

  if (!Site.hasArgument(ActualArgument)) {
    logUnusedArgument(Site, *ActualArgument);
    return FilterAnalysis::Continue;
  }

  /// the parent function of the callsite
  const auto& ParentFunctionName = Site.getFunction()->getName();
  if (functionMap.count(ParentFunctionName) == 0) {
    // This can happen when the (parent) function was not analyzed in the first place.
    // Which means that the parent function is not reachable from a program entry point. Either
    // the function is unreachable/dead or it was wrongly not analyzed (unsound). Therefore, we
    // conservative keep the value.
    LOG_INFO("function not in map: " << ParentFunctionName)
    return typeart::filter::FilterAnalysis::Keep;
  }
  const auto& FunctionData = functionMap.lookup(ParentFunctionName);

  const auto& Callees = getCalleesForCallsite(FunctionData, Site);
  if (Callees.empty()) {
    // it is unlikely, but possible that a callsite was not analyzed in the first place.
    // this is often the result of an unsound analysis, therefore we want a conservative fallback
    logMissingCallees(Site, *ActualArgument);
    return FilterAnalysis::Keep;
  }

  const auto InitialEdges = createEdgesForCallsite(Site, *ActualArgument, Callees);
  if (InitialEdges.empty()) {
    // no initial edges is likely an error in the callgraph file, keep the value in those cases
    logMissingEdges(Site, *ActualArgument);
    return FilterAnalysis::Keep;
  }

  return analyseFlowPath(InitialEdges);
}

std::vector<const FunctionDescriptor*> ACGFilterImpl::getCalleesForCallsite(const FunctionDescriptor& FunctionData,
                                                                            const CallBase& Site) const {
  const auto Identifier     = getIdentifierForCallsite(Site);
  const auto& MapEntryRange = make_range(FunctionData.callsiteCallees.equal_range(Identifier));

  const auto& Callees = map_range(MapEntryRange, [](const auto& Entry) { return Entry.second; });

  return {Callees.begin(), Callees.end()};
}

/// identifiers all callsites of a function and stores additionally the highest used identifier as metadata field
/// at the function. if the function metadata field already exists, its value is returned
unsigned ACGFilterImpl::calculateSiteIdentifiersIfAbsent(const Function& Function) {
  if (analyzedFunctions.count(&Function) != 0) {
    return analyzedFunctions[&Function];
  }

  unsigned CallSiteIdentifier = 0;
  for (const auto& Instruction : llvm::instructions(Function)) {
    if (llvm::isa<llvm::CallBase>(&Instruction)) {
      callSiteIdentifiers[&Instruction] = ++CallSiteIdentifier;
    }
  }

  analyzedFunctions[&Function] = CallSiteIdentifier;
  return CallSiteIdentifier;
}

unsigned int ACGFilterImpl::getIdentifierForCallsite(const llvm::CallBase& Site) const {
  const auto FoundAt = callSiteIdentifiers.find(&Site);
  assert((FoundAt != callSiteIdentifiers.end()) && "identifier for callsite is missing");
  return FoundAt->second;
}

FilterAnalysis ACGFilterImpl::precheck(llvm::Value* In, llvm::Function* Start, const FPath& Fpath) {
  assert(Start != nullptr && "pre-check in FilterBase::DFSFuncFilter failed");

  // use the precheck-callback to identify all callsites within a function
  // preferably this would be implemented as a pass, but that would require
  // structural changes for TypeART.
  const auto NumberOfCallSites = calculateSiteIdentifiersIfAbsent(*Start);
  if (NumberOfCallSites == 0) {
    return FilterAnalysis::Filter;
  }

  if (!Fpath.empty()) {
    return FilterAnalysis::Continue;
  }

  // These conditions (temp alloc and alloca reaches task)
  // are only interesting if filter just started (aka fpath is empty)
  if (isTempAlloc(In)) {
    LOG_DEBUG("Alloca is a temporary " << *In);
    return FilterAnalysis::Filter;
  }

  if (auto* alloc = llvm::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::decl(const CallSite& Site, const Path& Path) {
  calculateSiteIdentifiersIfAbsent(*Site->getFunction());
  return analyseCallsite(*llvm::cast<llvm::CallBase>(Site.getInstruction()), Path);
}

FilterAnalysis ACGFilterImpl::def(const CallSite& Site, const Path& Path) {
  calculateSiteIdentifiersIfAbsent(*Site->getFunction());
  return analyseCallsite(*llvm::cast<llvm::CallBase>(Site.getInstruction()), Path);
}

FilterAnalysis ACGFilterImpl::indirect(const CallSite& Site, const Path& Path) {
  calculateSiteIdentifiersIfAbsent(*Site->getFunction());
  return analyseCallsite(*llvm::cast<llvm::CallBase>(Site.getInstruction()), Path);
}

}  // namespace typeart::filter

1	// TypeART library
2	//
3	// Copyright (c) 2017-2023 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 "ACGForwardFilter.h"
14
15	#include <llvm/IR/InstIterator.h>
16	#include <llvm/IR/IntrinsicInst.h>
17
18	using namespace llvm;
19
20	namespace typeart::filter {
21	using namespace util::metacg;
22
23	namespace detail {
24
25	/// follows all enqueued values and visits them once starting with an initial entry
26
27	enum VisitResult {
28	VR_Continue = 0,
29	VR_Stop,
30	};
31
32	template <typename T, typename CB>
33	inline void solveReachable(const std::vector<T>& Range, CB&& Callback) noexcept {	270✔
34	llvm::SmallPtrSet<T const*, 32> Visited{};	270✔
35	llvm::SmallVector<T const*, 64> Worklist{};	270✔
36
37	const auto& Enqueue = [&](T const& Entry) noexcept -> bool {	837✔
38	if (Visited.insert(&Entry).second) {	567✔
39	Worklist.push_back(&Entry);	567✔
40	return true;	567✔
41	}
NEW 42	return false;	×
43	};	567✔
44
45	for (const auto& Item : Range) {	612✔
46	Enqueue(Item);	342✔
47	}
48
49	while (!Worklist.empty()) {	675✔
50	T const* CurrentValue = Worklist.pop_back_val();	495✔
51	VisitResult const Status = Callback(*CurrentValue, Enqueue);	495✔
52	switch (Status) {	495✔
53	case VR_Continue:
54	break;	405✔
55	case VR_Stop:
56	return;	90✔
57	}
58	}
59	}	270✔
60	} // namespace detail
61
62	static FunctionDescriptor createFunctionNode(const JSONACG::node_type& JSON, const Regex& TargetMatcher) {	261✔
63	const auto& Signature = JSON.meta.signature;	261✔
64	const bool IsTargetOfInterrest = TargetMatcher.match(Signature.identifier);	261✔
65
66	return {IsTargetOfInterrest,	1,305✔
67	JSON.hasBody,	261✔
68	{},	261✔
69	{},	261✔
70	{Signature.identifier, Signature.paramTypes, Signature.returnType, Signature.isVariadic}};	261✔
NEW 71	}	×
72
73	static FunctionDescriptor const& retrieveFunction(const ACGDataMap& DataMap, const StringRef& FunctionName) {	360✔
74	assert(DataMap.count(FunctionName) && "Found an edge to an undefined callee");	720✔
75	if (DataMap.count(FunctionName) == 0) {	360✔
NEW 76	throw std::runtime_error("Found an edge to an undefined callee: " + FunctionName.str());	×
77	}
78	return DataMap.find(FunctionName)->second;	360✔
NEW 79	}	×
80
81	static void insertCallsiteIdentifiers(const JSONACG::node_type& Json, FunctionDescriptor& Data, ACGDataMap& DataMap) {	261✔
82	llvm::for_each(Json.meta.ipdf.callsites, [&](const auto& CallSites) {	486✔
83	const auto& CalleeFunction = retrieveFunction(DataMap, CallSites.getKey());	225✔
84
85	for (const auto& Identifier : CallSites.getValue()) {	495✔
86	Data.callsiteCallees.emplace(Identifier.id, &CalleeFunction);	270✔
87	}
88	});	225✔
89	}	261✔
90
91	static void insertArgumentFlow(const JSONACG::node_type& Json, FunctionDescriptor& Data, ACGDataMap& DataMap) {	261✔
92	llvm::for_each(Json.meta.ipdf.interFlow, [&](const auto& CallSites) {	396✔
93	const auto& CalleeFunction = retrieveFunction(DataMap, CallSites.getKey());	135✔
94
95	for (const auto& Edge : CallSites.getValue()) {	288✔
96	FunctionDescriptor::ArgumentEdge const FlowEdge{Edge.formalArgNo, CalleeFunction};	153✔
97	Data.reachableFormals.emplace(Edge.actualArgNo, FlowEdge);	153✔
98	}
99	});	135✔
100	}	261✔
101
102	ACGDataMap createDatabase(const Regex& TargetMatcher, JSONACG& MetaCg) {	72✔
103	ACGDataMap DataMap;	72✔
104
105	// insert nodes first, to avoid rehashing and invalidation of references
106	llvm::for_each(MetaCg.nodes, [&](const auto& MetaCGNode) {	333✔
107	DataMap.try_emplace(MetaCGNode.getKey(), createFunctionNode(MetaCGNode.getValue(), TargetMatcher));	261✔
108	});	261✔
109
110	llvm::for_each(DataMap, [&](auto& Entry) {	333✔
111	insertCallsiteIdentifiers(MetaCg.nodes[Entry.getKey()], Entry.getValue(), DataMap);	261✔
112	insertArgumentFlow(MetaCg.nodes[Entry.getKey()], Entry.getValue(), DataMap);	261✔
113	});	261✔
114
115	return DataMap;	72✔
116	}	72✔
117
118	/// tests if an edge can reach a void* argument
119	bool ACGFilterImpl::isFormalArgumentRelevant(const FunctionDescriptor::ArgumentEdge& Edge) const {	189✔
120	return Edge.callee.functionSignature.paramIsType(Edge.formalArgumentNumber, VoidType);	189✔
NEW 121	}	×
122
123	/// an edge reaches a relevant formal argument
124	bool ACGFilterImpl::edgeReachesRelevantFormalArgument(const FunctionDescriptor::ArgumentEdge& Edge) const {	495✔
125	return Edge.callee.isTarget && isFormalArgumentRelevant(Edge);	495✔
126	}
127
128	/// declaration with relevant formal argument, could reach indirect the destination
129	bool ACGFilterImpl::edgeMaybeReachesFormalArgument(const FunctionDescriptor::ArgumentEdge& Edge) const {	405✔
130	return !Edge.callee.isTarget && !Edge.callee.isDefinition && isFormalArgumentRelevant(Edge);	405✔
131	}
132
133	template <typename RangeT>
134	inline FilterAnalysis ACGFilterImpl::ACGFilterImpl::analyseMaybeCandidates(const RangeT&& MaybeCandidates) const {	36✔
135	bool HasContinue = false;	36✔
136	bool HasSkip = false;	36✔
137
138	for (const auto& Candidate : MaybeCandidates) {	54✔
139	switch (candidateMatcher.match(Candidate)) {	36✔
140	case Matcher::MatchResult::Match:
NEW 141	return FilterAnalysis::Keep;	×
142
143	case Matcher::MatchResult::ShouldContinue:
NEW 144	HasContinue = true;	×
NEW 145	break;	×
146
147	case Matcher::MatchResult::ShouldSkip:
148	HasSkip = true;	18✔
149	break;	18✔
150
151	case Matcher::MatchResult::NoMatch:
152	// keep the function if the matcher has no information
153	return FilterAnalysis::Keep;	18✔
154	}
155	}
156
157	// prioritize a continue
158	if (HasContinue) {	18✔
NEW 159	return FilterAnalysis::Continue;	×
160	}
161
162	if (HasSkip) {	18✔
163	return FilterAnalysis::Skip;	18✔
164	}
165
166	// we have nothing found, use the default result
NEW 167	return FilterAnalysis::Continue;	×
168	}	36✔
169
170	FilterAnalysis ACGFilterImpl::analyseFlowPath(const std::vector<FunctionDescriptor::ArgumentEdge>& InitialEdges) const {	270✔
171	enum class ReachabilityResult { reaches, maybe_reaches, never_reaches };
172	using namespace typeart::filter::detail;
173
174	/// contains declarations which have at least one argument that is reachable and relevant
175	StringSet MaybeCandidates;	270✔
176
177	ReachabilityResult Result = ReachabilityResult::never_reaches;	270✔
178	solveReachable(InitialEdges, [&](const FunctionDescriptor::ArgumentEdge& Edge, auto const& Enqueue) -> VisitResult {	765✔
179	if (edgeReachesRelevantFormalArgument(Edge)) {	495✔
180	Result = ReachabilityResult::reaches;	90✔
181	return VR_Stop;	90✔
182	}
183
184	if (edgeMaybeReachesFormalArgument(Edge)) {	405✔
185	Result = ReachabilityResult::maybe_reaches;	36✔
186	MaybeCandidates.insert(Edge.callee.functionSignature.identifier);	36✔
187	}	36✔
188
189	// enqueue all edges that can be reached from the current callee/argument
190	const auto& ReachableFormals = make_range(Edge.callee.reachableFormals.equal_range(Edge.formalArgumentNumber));	405✔
191	for (const auto& [ActualNumber, FormalEdge] : ReachableFormals) {	630✔
192	Enqueue(FormalEdge);	450✔
193	}
194
195	return VR_Continue;	405✔
196	});	495✔
197
198	switch (Result) {	270✔
199	// check also the other call-sites
200	case ReachabilityResult::never_reaches:
201	return FilterAnalysis::Continue;	144✔
202
203	case ReachabilityResult::maybe_reaches:
204	return analyseMaybeCandidates(MaybeCandidates.keys());	36✔
205
206	case ReachabilityResult::reaches:
207	return FilterAnalysis::Keep;	90✔
NEW 208	}	×
209	}	270✔
210
211	/// calculates all outgoing edges for a given parameter value of a callsite
212	[[nodiscard]] std::vector<FunctionDescriptor::ArgumentEdge> ACGFilterImpl::createEdgesForCallsite(	270✔
213	const CallBase& Site, const llvm::Value& ActualArgument,
214	const std::vector<const FunctionDescriptor*>& CalleesForCallsite) const {
215	const auto&& CorrespondingArgs =	270✔
216	llvm::make_filter_range(Site.args(), [&ActualArgument](const auto& Arg) { return Arg.get() == &ActualArgument; });	891✔
217
218	std::vector<FunctionDescriptor::ArgumentEdge> Init;	270✔
219	for (const auto& CallSiteArg : CorrespondingArgs) {	558✔
220	for (const auto& Callee : CalleesForCallsite) {	630✔
221	Init.emplace_back(FunctionDescriptor::ArgumentEdge{	342✔
222	static_cast<int>(CallSiteArg.getOperandNo()) /formal/, Callee /callee*/	342✔
223	});
224	}
225	}
226
227	return Init;	270✔
228	}	270✔
229
NEW 230	std::string ACGFilterImpl::prepareLogMessage(const CallBase& Site, const Value& ActualArgument,	×
231	const StringRef& Msg) const {
NEW 232	std::string String;	×
NEW 233	raw_string_ostream StringStream{String};	×
NEW 234	StringStream << "function ";	×
NEW 235	Site.getFunction()->printAsOperand(StringStream, false);	×
NEW 236	StringStream << ": argument ";	×
NEW 237	ActualArgument.printAsOperand(StringStream, false);	×
NEW 238	StringStream << ": callsite ";	×
NEW 239	Site.print(StringStream, true);	×
NEW 240	StringStream << " (";	×
NEW 241	Site.getDebugLoc().print(StringStream);	×
NEW 242	StringStream << "): " << Msg;	×
243
NEW 244	return String;	×
NEW 245	}	×
246
247	inline void ACGFilterImpl::logUnusedArgument(const llvm::CallBase& Site, const llvm::Value& ActualArgument) const {	18✔
248	if (Site.getCalledOperand() == &ActualArgument) {	18✔
249	LOG_DEBUG(prepareLogMessage(Site, ActualArgument, "Argument is CalledOperand of Callsite"))
250	return;	9✔
251	}
252
253	// this can happen when the IRSearch finds a store-instruction and adds
254	// the pointer operand to the successors.
255	if (llvm::is_contained(Site.users(), &ActualArgument)) {	9✔
256	LOG_DEBUG(prepareLogMessage(Site, ActualArgument, "Argument is User of Callsite"))
257	return;	9✔
258	}
259
260	// this is a serious problem within the dataflow analysis
NEW 261	LOG_ERROR(prepareLogMessage(Site, ActualArgument, "Argument is not used at Callsite"))	×
262	}	18✔
263
NEW 264	inline void ACGFilterImpl::logMissingCallees(const llvm::CallBase& Site, const llvm::Value&) const {	×
NEW 265	std::string String;	×
NEW 266	raw_string_ostream StringStream{String};	×
NEW 267	StringStream << "function ";	×
NEW 268	Site.getFunction()->printAsOperand(StringStream, false);	×
NEW 269	StringStream << ": no callees found for callsite ";	×
NEW 270	Site.print(StringStream, true);	×
271
NEW 272	LOG_WARNING(String)	×
NEW 273	}	×
274
NEW 275	inline void ACGFilterImpl::logMissingEdges(const llvm::CallBase& Site, const llvm::Value& ActualArgument) const {	×
NEW 276	std::string String;	×
NEW 277	raw_string_ostream StringStream{String};	×
NEW 278	StringStream << "function ";	×
NEW 279	Site.getFunction()->printAsOperand(StringStream, false);	×
NEW 280	StringStream << ": no edges found for argument ";	×
NEW 281	ActualArgument.printAsOperand(StringStream, false);	×
NEW 282	StringStream << " @ ";	×
NEW 283	Site.print(StringStream, true);	×
284
NEW 285	LOG_WARNING(String)	×
NEW 286	}	×
287
288	FilterAnalysis ACGFilterImpl::analyseCallsite(const llvm::CallBase& Site, const Path& Path) const {	297✔
289	const llvm::Value* ActualArgument = Path.getEndPrev().getValue();	297✔
290	assert(ActualArgument != nullptr && "Argument should not be null");	594✔
291
292	if (!Site.hasArgument(ActualArgument)) {	297✔
293	logUnusedArgument(Site, *ActualArgument);	18✔
294	return FilterAnalysis::Continue;	18✔
295	}
296
297	/// the parent function of the callsite
298	const auto& ParentFunctionName = Site.getFunction()->getName();	279✔
299	if (functionMap.count(ParentFunctionName) == 0) {	279✔
300	// This can happen when the (parent) function was not analyzed in the first place.
301	// Which means that the parent function is not reachable from a program entry point. Either
302	// the function is unreachable/dead or it was wrongly not analyzed (unsound). Therefore, we
303	// conservative keep the value.
304	LOG_INFO("function not in map: " << ParentFunctionName)	9✔
305	return typeart::filter::FilterAnalysis::Keep;	9✔
306	}
307	const auto& FunctionData = functionMap.lookup(ParentFunctionName);	270✔
308
309	const auto& Callees = getCalleesForCallsite(FunctionData, Site);	270✔
310	if (Callees.empty()) {	270✔
311	// it is unlikely, but possible that a callsite was not analyzed in the first place.
312	// this is often the result of an unsound analysis, therefore we want a conservative fallback
NEW 313	logMissingCallees(Site, *ActualArgument);	×
NEW 314	return FilterAnalysis::Keep;	×
315	}
316
317	const auto InitialEdges = createEdgesForCallsite(Site, *ActualArgument, Callees);	270✔
318	if (InitialEdges.empty()) {	270✔
319	// no initial edges is likely an error in the callgraph file, keep the value in those cases
NEW 320	logMissingEdges(Site, *ActualArgument);	×
NEW 321	return FilterAnalysis::Keep;	×
322	}
323
324	return analyseFlowPath(InitialEdges);	270✔
325	}	297✔
326
327	std::vector<const FunctionDescriptor*> ACGFilterImpl::getCalleesForCallsite(const FunctionDescriptor& FunctionData,	270✔
328	const CallBase& Site) const {
329	const auto Identifier = getIdentifierForCallsite(Site);	270✔
330	const auto& MapEntryRange = make_range(FunctionData.callsiteCallees.equal_range(Identifier));	270✔
331
332	const auto& Callees = map_range(MapEntryRange, [](const auto& Entry) { return Entry.second; });	594✔
333
334	return {Callees.begin(), Callees.end()};	270✔
NEW 335	}	×
336
337	/// identifiers all callsites of a function and stores additionally the highest used identifier as metadata field
338	/// at the function. if the function metadata field already exists, its value is returned
339	unsigned ACGFilterImpl::calculateSiteIdentifiersIfAbsent(const Function& Function) {	549✔
340	if (analyzedFunctions.count(&Function) != 0) {	549✔
341	return analyzedFunctions[&Function];	468✔
342	}
343
344	unsigned CallSiteIdentifier = 0;	81✔
345	for (const auto& Instruction : llvm::instructions(Function)) {	1,377✔
346	if (llvm::isa<llvm::CallBase>(&Instruction)) {	1,296✔
347	callSiteIdentifiers[&Instruction] = ++CallSiteIdentifier;	369✔
348	}	369✔
349	}
350
351	analyzedFunctions[&Function] = CallSiteIdentifier;	81✔
352	return CallSiteIdentifier;	81✔
353	}	549✔
354
355	unsigned int ACGFilterImpl::getIdentifierForCallsite(const llvm::CallBase& Site) const {	270✔
356	const auto FoundAt = callSiteIdentifiers.find(&Site);	270✔
357	assert((FoundAt != callSiteIdentifiers.end()) && "identifier for callsite is missing");	540✔
358	return FoundAt->second;	270✔
359	}
360
361	FilterAnalysis ACGFilterImpl::precheck(llvm::Value* In, llvm::Function* Start, const FPath& Fpath) {	252✔
362	assert(Start != nullptr && "pre-check in FilterBase::DFSFuncFilter failed");	504✔
363
364	// use the precheck-callback to identify all callsites within a function
365	// preferably this would be implemented as a pass, but that would require
366	// structural changes for TypeART.
367	const auto NumberOfCallSites = calculateSiteIdentifiersIfAbsent(*Start);	252✔
368	if (NumberOfCallSites == 0) {	252✔
369	return FilterAnalysis::Filter;	9✔
370	}
371
372	if (!Fpath.empty()) {	243✔
NEW 373	return FilterAnalysis::Continue;	×
374	}
375
376	// These conditions (temp alloc and alloca reaches task)
377	// are only interesting if filter just started (aka fpath is empty)
378	if (isTempAlloc(In)) {	243✔
379	LOG_DEBUG("Alloca is a temporary " << *In);
NEW 380	return FilterAnalysis::Filter;	×
381	}
382
383	if (auto* alloc = llvm::dyn_cast<AllocaInst>(In)) {	243✔
384	if (alloc->getAllocatedType()->isStructTy() && omp::OmpContext::allocaReachesTask(alloc)) {	243✔
385	LOG_DEBUG("Alloca reaches task call " << *alloc)
NEW 386	return FilterAnalysis::Filter;	×
387	}
388	}	243✔
389
390	return FilterAnalysis::Continue;	243✔
391	}	252✔
392
393	FilterAnalysis ACGFilterImpl::decl(const CallSite& Site, const Path& Path) {	234✔
394	calculateSiteIdentifiersIfAbsent(*Site->getFunction());	234✔
395	return analyseCallsite(*llvm::cast<llvm::CallBase>(Site.getInstruction()), Path);	234✔
396	}
397
398	FilterAnalysis ACGFilterImpl::def(const CallSite& Site, const Path& Path) {	36✔
399	calculateSiteIdentifiersIfAbsent(*Site->getFunction());	36✔
400	return analyseCallsite(*llvm::cast<llvm::CallBase>(Site.getInstruction()), Path);	36✔
401	}
402
403	FilterAnalysis ACGFilterImpl::indirect(const CallSite& Site, const Path& Path) {	27✔
404	calculateSiteIdentifiersIfAbsent(*Site->getFunction());	27✔
405	return analyseCallsite(*llvm::cast<llvm::CallBase>(Site.getInstruction()), Path);	27✔
406	}
407
408	} // namespace typeart::filter

tudasc / TypeART / 4373909195

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