14810743078

Committed 03 May 2025 12:13PM UTC coverage: 83.355%. First build

Build # 14810743078

Build Type

Pull #41

github

Committed by

web-flow

Commit Message

Merge 77687d7ea into 459a9514a

Pull Request Pull Request #41: Handle loop unroll with array access

Run Details

1153 of 1664 branches covered (69.29%)

Branch coverage included in aggregate %.

33 of 35 new or added lines in 3 files covered. (94.29%)

2112 of 2253 relevant lines covered (93.74%)

4269.07 hits per line

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

87.08

/lib/type/Dimeta.cpp

//  llvm-dimeta library
//  Copyright (c) 2022-2025 llvm-dimeta authors
//  Distributed under the BSD 3-Clause license.
//  (See accompanying file LICENSE)
//  SPDX-License-Identifier: BSD-3-Clause
//

#include "Dimeta.h"

#include "DIFinder.h"
#include "DIRootType.h"
#include "DITypeExtractor.h"
#include "DataflowAnalysis.h"
#include "DefUseAnalysis.h"
#include "DimetaData.h"
#include "DimetaParse.h"
#include "MemoryOps.h"
#include "Util.h"
#include "ValuePath.h"
#include "support/Logger.h"

#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/ilist_iterator.h"
#include "llvm/BinaryFormat/Dwarf.h"
#include "llvm/Config/llvm-config.h"
#include "llvm/IR/Argument.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DebugInfoMetadata.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/Value.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"

#include <cassert>
#include <iterator>
#include <string>

namespace llvm {
class DbgVariableIntrinsic;
}  // namespace llvm

#if LLVM_VERSION_MAJOR == 10
// For FindDbgAddrUses:
#include "llvm/Transforms/Utils/Local.h"
#endif

namespace dimeta {

namespace experimental {
std::optional<llvm::DIType*> di_type_for(const llvm::Value* value);
}

llvm::SmallVector<llvm::DIType*, 4> collect_types(const llvm::CallBase* call,
                                                  llvm::ArrayRef<dataflow::ValuePath> paths_to_type) {
  using namespace llvm;
  SmallVector<llvm::DIType*, 4> di_types;
  llvm::transform(paths_to_type, dimeta::util::optional_back_inserter(di_types),
                  [&](const auto& path) { return type::find_type(dataflow::CallValuePath{call, path}); });
  return di_types;
}

auto final_ditype(std::optional<llvm::DIType*> root_ditype) -> std::pair<std::optional<llvm::DIType*>, int> {
  if (!root_ditype) {
    return {{}, 0};
  }
  int level{0};
  llvm::DIType* type = *root_ditype;
  while (llvm::isa<llvm::DIDerivedType>(type)) {
    auto ditype = llvm::dyn_cast<llvm::DIDerivedType>(type);
    if (ditype->getTag() == llvm::dwarf::DW_TAG_pointer_type) {
      ++level;
    }
    // void*-based derived types have basetype=null:
    if (ditype->getBaseType() == nullptr) {
      return {type, level};
    }
    type = ditype->getBaseType();
  }

  return {type, level};
}

std::optional<llvm::DIType*> type_for_malloclike(const llvm::CallBase* call) {
  auto local = difinder::get_array_access_assignment(call);
  if (local) {
    LOG_DEBUG("Call has local variable " << *call)
    // LOG_DEBUG("Call type " << log::ditype_str(local.value()->getType()))
    auto base_type = local.value().var->getType();
    if (local.value().array_access) {
      if (auto* array_type = llvm::dyn_cast<llvm::DICompositeType>(base_type)) {
        LOG_DEBUG("Returning type of access to array " << log::ditype_str(array_type))
        return array_type->getBaseType();
      }
    }
    return base_type;
  }

  const auto ditype_paths = dataflow::type_for_heap_call(call);

  LOG_DEBUG("Found paths, now collecting types")
  const auto ditypes_vector = collect_types(call, ditype_paths);
  if (ditypes_vector.empty()) {
    return {};
  }
  return *ditypes_vector.begin();
}

std::optional<llvm::DIType*> type_for_newlike(const llvm::CallBase* call) {
  auto* heapalloc_md = call->getMetadata("heapallocsite");
  assert(heapalloc_md != nullptr && "Missing required heapallocsite metadata.");
  if (auto* type = llvm::dyn_cast<llvm::DIType>(heapalloc_md)) {
    //    util::DIPrinter printer(llvm::outs(), call->getParent()->getParent()->getParent());
    //    printer.traverseType(type);
    //    llvm::dbgs() << "Final Type: " << *type << "\n";
    return type;
  }
  return {};
}

std::optional<DimetaData> type_for(const llvm::CallBase* call) {
  using namespace llvm;
  const dimeta::memory::MemOps mem_ops;

  auto* cb_fun = call->getCalledFunction();
  if (!cb_fun) {
    return {};
  }

  if (!mem_ops.isAlloc(cb_fun->getName())) {
    LOG_TRACE("Skipping call base: " << cb_fun->getName());
    return {};
  }

  std::optional<llvm::DIType*> extracted_type{};
  int pointer_level_offset{0};

  const auto is_cuda_like = mem_ops.isCudaLike(cb_fun->getName());
  if (is_cuda_like) {
    LOG_DEBUG("Type for cuda-like " << cb_fun->getName())
    extracted_type = experimental::di_type_for(call->getOperand(0));

    // when wrapped in, e.g., cudaMalloc<float>(float**, ...), we remove one pointer level:
    // auto* parent    = call->getFunction();
    // const auto name = std::string{cb_fun->getName()} + "<";
    // LOG_DEBUG(name << " vs. " << util::try_demangle(*makeparent))
    // if (extracted_type && util::try_demangle(*parent).find(name) != std::string::npos) {
    //   LOG_DEBUG("Reset cuda-like pointer level")
    //   auto ditype = llvm::dyn_cast<llvm::DIDerivedType>(extracted_type.value());
    //   if (ditype->getTag() == llvm::dwarf::DW_TAG_pointer_type) {
    //     extracted_type = ditype->getBaseType();
    //   }
    // }
  }

  const auto is_cxx_new = mem_ops.isNewLike(cb_fun->getName());

#ifdef DIMETA_USE_HEAPALLOCSITE
  if (is_cxx_new) {
    if (call->getMetadata("heapallocsite")) {
      LOG_TRACE("Type for new-like " << cb_fun->getName())
      extracted_type = type_for_newlike(call);
      // !heapallocsite gives the type after "new", i.e., new int -> int, new int*[n] -> int*.
      // Our malloc-related algorithm would return int* and int** respectively, however, hence:
      pointer_level_offset += 1;
    } else {
      LOG_DEBUG("new-like allocation does not have heapallocsite metadata.")
    }
  }
#endif

  if (!extracted_type) {
    LOG_DEBUG("Type for malloc-like: " << cb_fun->getName())
    extracted_type = type_for_malloclike(call);
  }
  auto source_loc                        = difinder::find_location(call);
  const auto [final_type, pointer_level] = final_ditype(extracted_type);
  const auto meta = DimetaData{DimetaData::MemLoc::kHeap,           {}, extracted_type, final_type, source_loc,
                               pointer_level + pointer_level_offset};
  return meta;
}

std::optional<DimetaData> type_for(const llvm::AllocaInst* ai) {
  const auto local_di_var = difinder::find_local_variable(ai);

  if (local_di_var) {
    auto extracted_type                    = local_di_var.value()->getType();
    auto source_loc                        = difinder::find_location(ai);
    const auto [final_type, pointer_level] = final_ditype(extracted_type);
    const auto meta =
        DimetaData{DimetaData::MemLoc::kStack, local_di_var, extracted_type, final_type, source_loc, pointer_level};
    return meta;
  }

  LOG_DEBUG("No local_variable for " << *ai)

  return {};
}

std::optional<DimetaData> type_for(const llvm::GlobalVariable* gv) {
  llvm::SmallVector<llvm::DIGlobalVariableExpression*, 2> dbg_info;
  gv->getDebugInfo(dbg_info);
  if (!dbg_info.empty()) {
    auto gv_expr                           = *dbg_info.begin();
    auto gv_type                           = gv_expr->getVariable()->getType();
    const auto [final_type, pointer_level] = final_ditype(gv_type);
    return DimetaData{DimetaData::MemLoc::kGlobal, gv_expr->getVariable(), gv_type, final_type, {}, pointer_level};
  }
  return {};
}

std::optional<CompileUnitTypeList> compile_unit_types(const llvm::Module* module) {
  CompileUnitTypeList list;
  for (auto* compile_unit : module->debug_compile_units()) {
    CompileUnitTypes current_cu;
    current_cu.name = compile_unit->getFilename();
    for (auto* retained_type : compile_unit->getRetainedTypes()) {
      if (auto* type = llvm::dyn_cast<llvm::DIType>(retained_type)) {
        auto dimeta_result = parser::make_dimetadata(type);
        if (!dimeta_result) {
          continue;
        }
        current_cu.types.push_back(dimeta_result->type_);
      }
    }
    list.push_back(current_cu);
  }
  return (list.empty() ? std::optional<CompileUnitTypeList>{} : list);
}

namespace experimental {
std::optional<llvm::DIType*> di_type_for(const llvm::Value* value) {
  auto paths                = dataflow::experimental::path_from_value(value);
  const auto ditypes_vector = collect_types(nullptr, paths);
  if (ditypes_vector.empty()) {
    return {};
  }

  return *ditypes_vector.begin();
}

std::optional<QualifiedType> type_for(const llvm::Value* value) {
  auto paths                = dataflow::experimental::path_from_value(value);
  const auto ditypes_vector = collect_types(nullptr, paths);
  if (ditypes_vector.empty()) {
    return {};
  }

  for (const auto& type : ditypes_vector) {
    auto dimeta_result = parser::make_dimetadata(type);
    if (!dimeta_result) {
      continue;
    }
    return dimeta_result->type_;
  }

  return {};
}

}  // namespace experimental

}  // namespace dimeta

1	// llvm-dimeta library
2	// Copyright (c) 2022-2025 llvm-dimeta authors
3	// Distributed under the BSD 3-Clause license.
4	// (See accompanying file LICENSE)
5	// SPDX-License-Identifier: BSD-3-Clause
6	//
7
8	#include "Dimeta.h"
9
10	#include "DIFinder.h"
11	#include "DIRootType.h"
12	#include "DITypeExtractor.h"
13	#include "DataflowAnalysis.h"
14	#include "DefUseAnalysis.h"
15	#include "DimetaData.h"
16	#include "DimetaParse.h"
17	#include "MemoryOps.h"
18	#include "Util.h"
19	#include "ValuePath.h"
20	#include "support/Logger.h"
21
22	#include "llvm/ADT/ArrayRef.h"
23	#include "llvm/ADT/STLExtras.h"
24	#include "llvm/ADT/SmallVector.h"
25	#include "llvm/ADT/ilist_iterator.h"
26	#include "llvm/BinaryFormat/Dwarf.h"
27	#include "llvm/Config/llvm-config.h"
28	#include "llvm/IR/Argument.h"
29	#include "llvm/IR/Constants.h"
30	#include "llvm/IR/DebugInfoMetadata.h"
31	#include "llvm/IR/Function.h"
32	#include "llvm/IR/GlobalVariable.h"
33	#include "llvm/IR/InstIterator.h"
34	#include "llvm/IR/InstrTypes.h"
35	#include "llvm/IR/Instructions.h"
36	#include "llvm/IR/IntrinsicInst.h"
37	#include "llvm/IR/Metadata.h"
38	#include "llvm/IR/Operator.h"
39	#include "llvm/IR/Value.h"
40	#include "llvm/Support/Casting.h"
41	#include "llvm/Support/Debug.h"
42	#include "llvm/Support/ErrorHandling.h"
43	#include "llvm/Support/raw_ostream.h"
44
45	#include <cassert>
46	#include <iterator>
47	#include <string>
48
49	namespace llvm {
50	class DbgVariableIntrinsic;
51	} // namespace llvm
52
53	#if LLVM_VERSION_MAJOR == 10
54	// For FindDbgAddrUses:
55	#include "llvm/Transforms/Utils/Local.h"
56	#endif
57
58	namespace dimeta {
59
60	namespace experimental {
61	std::optional<llvm::DIType> di_type_for(const llvm::Value value);
62	}
63
64	llvm::SmallVector<llvm::DIType, 4> collect_types(const llvm::CallBase call,	1,388✔
65	llvm::ArrayRef<dataflow::ValuePath> paths_to_type) {
66	using namespace llvm;
67	SmallVector<llvm::DIType*, 4> di_types;	1,388✔
68	llvm::transform(paths_to_type, dimeta::util::optional_back_inserter(di_types),	2,776✔
69	[&](const auto& path) { return type::find_type(dataflow::CallValuePath{call, path}); });	2,776✔
70	return di_types;	1,388✔
71	}	1,388!
72
73	auto final_ditype(std::optional<llvm::DIType> root_ditype) -> std::pair<std::optional<llvm::DIType>, int> {	5,902✔
74	if (!root_ditype) {	5,902✔
75	return {{}, 0};	10✔
76	}
77	int level{0};	5,892✔
78	llvm::DIType* type = *root_ditype;	5,892✔
79	while (llvm::isa<llvm::DIDerivedType>(type)) {	11,478✔
80	auto ditype = llvm::dyn_cast<llvm::DIDerivedType>(type);	5,650✔
81	if (ditype->getTag() == llvm::dwarf::DW_TAG_pointer_type) {	5,650✔
82	++level;	3,614✔
83	}	3,614✔
84	// void*-based derived types have basetype=null:
85	if (ditype->getBaseType() == nullptr) {	5,650✔
86	return {type, level};	64✔
87	}
88	type = ditype->getBaseType();	5,586✔
89	}	5,650✔
90
91	return {type, level};	5,828✔
92	}	5,902✔
93
94	std::optional<llvm::DIType> type_for_malloclike(const llvm::CallBase call) {	1,296✔
95	auto local = difinder::get_array_access_assignment(call);	1,296✔
96	if (local) {	1,296✔
97	LOG_DEBUG("Call has local variable " << *call)
98	// LOG_DEBUG("Call type " << log::ditype_str(local.value()->getType()))
99	auto base_type = local.value().var->getType();	56✔
100	if (local.value().array_access) {	56✔
101	if (auto* array_type = llvm::dyn_cast<llvm::DICompositeType>(base_type)) {	56!
102	LOG_DEBUG("Returning type of access to array " << log::ditype_str(array_type))
103	return array_type->getBaseType();	28✔
104	}
NEW 105	}	×
106	return base_type;	28✔
107	}	56✔
108
109	const auto ditype_paths = dataflow::type_for_heap_call(call);	1,240✔
110
111	LOG_DEBUG("Found paths, now collecting types")
112	const auto ditypes_vector = collect_types(call, ditype_paths);	1,240✔
113	if (ditypes_vector.empty()) {	1,240✔
114	return {};	10✔
115	}
116	return *ditypes_vector.begin();	1,230✔
117	}	1,296✔
118
119	std::optional<llvm::DIType> type_for_newlike(const llvm::CallBase call) {	392✔
120	auto* heapalloc_md = call->getMetadata("heapallocsite");	392✔
121	assert(heapalloc_md != nullptr && "Missing required heapallocsite metadata.");	784!
122	if (auto* type = llvm::dyn_cast<llvm::DIType>(heapalloc_md)) {	784!
123	// util::DIPrinter printer(llvm::outs(), call->getParent()->getParent()->getParent());
124	// printer.traverseType(type);
125	// llvm::dbgs() << "Final Type: " << *type << "\n";
126	return type;	392✔
127	}
128	return {};	×
129	}	392✔
130
131	std::optional<DimetaData> type_for(const llvm::CallBase* call) {	10,912✔
132	using namespace llvm;
133	const dimeta::memory::MemOps mem_ops;	10,912✔
134
135	auto* cb_fun = call->getCalledFunction();	10,912✔
136	if (!cb_fun) {	10,912!
137	return {};	8✔
138	}
139
140	if (!mem_ops.isAlloc(cb_fun->getName())) {	10,904✔
141	LOG_TRACE("Skipping call base: " << cb_fun->getName());
142	return {};	9,138✔
143	}
144
145	std::optional<llvm::DIType*> extracted_type{};	1,766✔
146	int pointer_level_offset{0};	1,766✔
147
148	const auto is_cuda_like = mem_ops.isCudaLike(cb_fun->getName());	1,766✔
149	if (is_cuda_like) {	1,766✔
150	LOG_DEBUG("Type for cuda-like " << cb_fun->getName())
151	extracted_type = experimental::di_type_for(call->getOperand(0));	78✔
152
153	// when wrapped in, e.g., cudaMalloc<float>(float**, ...), we remove one pointer level:
154	// auto* parent = call->getFunction();
155	// const auto name = std::string{cb_fun->getName()} + "<";
156	// LOG_DEBUG(name << " vs. " << util::try_demangle(*makeparent))
157	// if (extracted_type && util::try_demangle(*parent).find(name) != std::string::npos) {
158	// LOG_DEBUG("Reset cuda-like pointer level")
159	// auto ditype = llvm::dyn_cast<llvm::DIDerivedType>(extracted_type.value());
160	// if (ditype->getTag() == llvm::dwarf::DW_TAG_pointer_type) {
161	// extracted_type = ditype->getBaseType();
162	// }
163	// }
164	}	78✔
165
166	const auto is_cxx_new = mem_ops.isNewLike(cb_fun->getName());	1,766✔
167
168	#ifdef DIMETA_USE_HEAPALLOCSITE
169	if (is_cxx_new) {	1,766✔
170	if (call->getMetadata("heapallocsite")) {	406✔
171	LOG_TRACE("Type for new-like " << cb_fun->getName())
172	extracted_type = type_for_newlike(call);	392✔
173	// !heapallocsite gives the type after "new", i.e., new int -> int, new int[n] -> int.
174	// Our malloc-related algorithm would return int* and int** respectively, however, hence:
175	pointer_level_offset += 1;	392✔
176	} else {	392✔
177	LOG_DEBUG("new-like allocation does not have heapallocsite metadata.")
178	}
179	}	406✔
180	#endif
181
182	if (!extracted_type) {	1,766✔
183	LOG_DEBUG("Type for malloc-like: " << cb_fun->getName())
184	extracted_type = type_for_malloclike(call);	1,296✔
185	}	1,296✔
186	auto source_loc = difinder::find_location(call);	1,766✔
187	const auto [final_type, pointer_level] = final_ditype(extracted_type);	5,298✔
188	const auto meta = DimetaData{DimetaData::MemLoc::kHeap, {}, extracted_type, final_type, source_loc,	5,298✔
189	pointer_level + pointer_level_offset};	1,766✔
190	return meta;	1,766✔
191	}	10,912✔
192
193	std::optional<DimetaData> type_for(const llvm::AllocaInst* ai) {	3,973✔
194	const auto local_di_var = difinder::find_local_variable(ai);	3,973✔
195
196	if (local_di_var) {	3,973✔
197	auto extracted_type = local_di_var.value()->getType();	3,810✔
198	auto source_loc = difinder::find_location(ai);	3,810✔
199	const auto [final_type, pointer_level] = final_ditype(extracted_type);	11,430✔
200	const auto meta =	3,810✔
201	DimetaData{DimetaData::MemLoc::kStack, local_di_var, extracted_type, final_type, source_loc, pointer_level};	11,430✔
202	return meta;	3,810✔
203	}	3,810✔
204
205	LOG_DEBUG("No local_variable for " << *ai)
206
207	return {};	163✔
208	}	3,973✔
209
210	std::optional<DimetaData> type_for(const llvm::GlobalVariable* gv) {	539✔
211	llvm::SmallVector<llvm::DIGlobalVariableExpression*, 2> dbg_info;	539✔
212	gv->getDebugInfo(dbg_info);	539✔
213	if (!dbg_info.empty()) {	539✔
214	auto gv_expr = *dbg_info.begin();	326✔
215	auto gv_type = gv_expr->getVariable()->getType();	326✔
216	const auto [final_type, pointer_level] = final_ditype(gv_type);	978✔
217	return DimetaData{DimetaData::MemLoc::kGlobal, gv_expr->getVariable(), gv_type, final_type, {}, pointer_level};	978✔
218	}	326✔
219	return {};	213✔
220	}	539✔
221
222	std::optional<CompileUnitTypeList> compile_unit_types(const llvm::Module* module) {	1,079✔
223	CompileUnitTypeList list;	1,079✔
224	for (auto* compile_unit : module->debug_compile_units()) {	2,153✔
225	CompileUnitTypes current_cu;	1,074✔
226	current_cu.name = compile_unit->getFilename();	1,074✔
227	for (auto* retained_type : compile_unit->getRetainedTypes()) {	1,771✔
228	if (auto* type = llvm::dyn_cast<llvm::DIType>(retained_type)) {	1,394!
229	auto dimeta_result = parser::make_dimetadata(type);	697✔
230	if (!dimeta_result) {	697!
231	continue;	×
232	}
233	current_cu.types.push_back(dimeta_result->type_);	697✔
234	}	697!
235	}	697!
236	list.push_back(current_cu);	1,074✔
237	}	1,074✔
238	return (list.empty() ? std::optional<CompileUnitTypeList>{} : list);	1,079✔
239	}	1,079✔
240
241	namespace experimental {
242	std::optional<llvm::DIType> di_type_for(const llvm::Value value) {	78✔
243	auto paths = dataflow::experimental::path_from_value(value);	78✔
244	const auto ditypes_vector = collect_types(nullptr, paths);	78✔
245	if (ditypes_vector.empty()) {	78!
246	return {};	×
247	}
248
249	return *ditypes_vector.begin();	78✔
250	}	78✔
251
252	std::optional<QualifiedType> type_for(const llvm::Value* value) {	70✔
253	auto paths = dataflow::experimental::path_from_value(value);	70✔
254	const auto ditypes_vector = collect_types(nullptr, paths);	70✔
255	if (ditypes_vector.empty()) {	70!
256	return {};	×
257	}
258
259	for (const auto& type : ditypes_vector) {	140!
260	auto dimeta_result = parser::make_dimetadata(type);	70✔
261	if (!dimeta_result) {	70!
262	continue;	×
263	}
264	return dimeta_result->type_;	70✔
265	}	70!
266
267	return {};	×
268	}	70✔
269
270	} // namespace experimental
271
272	} // namespace dimeta

ahueck / llvm-dimeta / 14810743078

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