23296997048

Committed 19 Mar 2026 01:23PM UTC coverage: 64.594% (-9.0%) from 73.626%

Build # 23296997048

Build Type

Pull #49

github

Committed by

web-flow

Commit Message

Merge f45516abb into cefb3414f

Pull Request Pull Request #49: Initial Fortran Support

Run Details

1854 of 3670 branches covered (50.52%)

Branch coverage included in aggregate %.

164 of 435 new or added lines in 15 files covered. (37.7%)

20 existing lines in 6 files now uncovered.

2333 of 2812 relevant lines covered (82.97%)

11668.39 hits per line

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

48.59

/lib/type/DataflowAnalysis.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 "DataflowAnalysis.h"

#include "DefUseAnalysis.h"
#include "Dimeta.h"
#include "Util.h"
#include "support/Logger.h"

#include "llvm/ADT/TinyPtrVector.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DebugInfoMetadata.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Module.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 <cstdint>
#include <llvm/IR/GlobalValue.h>
#include <optional>

namespace llvm {
class Argument;
class GlobalVariable;
class Module;
}  // namespace llvm

namespace dimeta::dataflow {

struct MallocAnchorMatcher {
  llvm::SmallVector<ValuePath, 4> anchors;

  auto operator()(const ValuePath& path) -> decltype(DefUseChain::kContinue);
};

struct MallocTargetMatcher {
  llvm::SmallVector<ValuePath, 4> types_path;

  auto operator()(const ValuePath& path) -> decltype(DefUseChain::kContinue);
};

struct MallocBacktrackSearch {
  using ValueRange = llvm::TinyPtrVector<const llvm::Value*>;

  auto operator()(const ValuePath& path) -> std::optional<ValueRange>;
};

llvm::SmallVector<ValuePath, 4> type_for_heap_call(const llvm::CallBase* call) {
  using namespace llvm;

  auto should_search = [&](const ValuePath&) -> bool { return true; };
  DefUseChain value_traversal;

  // forward: find paths to anchor (store, ret, func call etc.) from malloc-like
  LOG_DEBUG("Find heap-call to anchor w.r.t. " << *call)
  // Anchor can be anything like function call "malloc -> .. -> foo(malloc)" or "malloc -> .. -> store" etc.
  MallocAnchorMatcher malloc_forward_anchor_finder;
  // value_traversal.traverse(call, malloc_forward_anchor_finder, should_search);
  value_traversal.traverse_custom(call, malloc_forward_anchor_finder, should_search,
                                  [](const ValuePath& val) -> std::optional<decltype(val.value().value()->users())> {
                                    const auto value = val.value();
                                    if (!value) {
                                      return {};
                                    }
                                    if (auto* store = llvm::dyn_cast<llvm::StoreInst>(value.value())) {
                                      return store->getPointerOperand()->users();
                                    }
                                    return value.value()->users();
                                  });

  // backward: find paths from anchor (store) to alloca/argument/global etc.
  MallocTargetMatcher malloc_anchor_backtrack;
  MallocBacktrackSearch backtrack_search_dir_fn;

  assert(!malloc_forward_anchor_finder.anchors.empty() && "Anchor should not be empty");
  llvm::SmallVector<ValuePath, 4> ditype_paths;

  for (const auto& anchor_path : malloc_forward_anchor_finder.anchors) {
    LOG_DEBUG("Current anchor path " << anchor_path)
    if (auto* store_inst = dyn_cast_or_null<StoreInst>(anchor_path.value().value_or(nullptr))) {
      if (store_inst->getPointerOperand() == call) {
        // see test heap_lulesh_domain_mock.cpp with opt -O3
        LOG_DEBUG("Continue with " << *store_inst)
        continue;
      }
      if (anchor_path.value()) {
        LOG_DEBUG("Backtracking from anchor " << **anchor_path.value())
      }
      //      dbgs() << "Traverse " << anchor_path.value() << "\n";
      value_traversal.traverse_custom(anchor_path.value().value(), malloc_anchor_backtrack, should_search,
                                      backtrack_search_dir_fn);
      for (const auto& backtrack_path : malloc_anchor_backtrack.types_path) {
        LOG_DEBUG("Found backtrack path " << backtrack_path)
        ditype_paths.emplace_back(backtrack_path);
      }
      continue;
    }

    if (auto* store_inst = dyn_cast_or_null<MemIntrinsic>(anchor_path.value().value_or(nullptr))) {
      value_traversal.traverse_custom(anchor_path.value().value(), malloc_anchor_backtrack, should_search,
                                      backtrack_search_dir_fn);
      for (const auto& backtrack_path : malloc_anchor_backtrack.types_path) {
        LOG_DEBUG("Found backtrack path for memintrinsic " << backtrack_path)
        ditype_paths.emplace_back(backtrack_path);
      }
      continue;
    }

    ditype_paths.emplace_back(anchor_path);
  }

  LOG_DEBUG("\n")
  LOG_DEBUG("Final paths to types:");
  for (const auto& path : ditype_paths) {
    LOG_DEBUG("  T: " << path);
  }

  return ditype_paths;
}

llvm::SmallVector<ValuePath, 4> path_from_alloca(const llvm::AllocaInst* alloca) {
  using namespace llvm;

  auto should_search = [&](const ValuePath&) -> bool { return true; };
  DefUseChain value_traversal;

  MallocAnchorMatcher malloc_forward_anchor_finder;
  value_traversal.traverse(alloca, malloc_forward_anchor_finder, should_search);
  return malloc_forward_anchor_finder.anchors;
}

llvm::SmallVector<ValuePath, 4> path_from_instruction(const llvm::Instruction* inst) {
  using namespace llvm;

  auto should_search = [&](const ValuePath&) -> bool { return true; };
  DefUseChain value_traversal;

  MallocAnchorMatcher malloc_forward_anchor_finder;
  value_traversal.traverse(inst, malloc_forward_anchor_finder, should_search);
  return malloc_forward_anchor_finder.anchors;
}

auto MallocBacktrackSearch::operator()(const ValuePath& path) -> std::optional<ValueRange> {
  // Backtracks form malloc target (a store) to, e.g., argument/global/etc.
  using namespace llvm;

  ValueRange result;

  if (auto const_expr = llvm::dyn_cast_or_null<llvm::ConstantExpr>(path.value().value_or(nullptr))) {
    if (const_expr->getOpcode() == Instruction::GetElementPtr) {
      if (auto op = llvm::dyn_cast<llvm::GEPOperator>(const_expr)) {
        result.push_back(op->getPointerOperand());
      }
      return result;
    }
    if (const_expr->getOpcode() == Instruction::BitCast) {
      // #if LLVM_VERSION_MAJOR < 15
      LOG_DEBUG("Found constant bitcast from value" << *const_expr->getOperand(0))
      result.push_back(const_expr->getOperand(0));
      // #endif
      return result;
    }
    LOG_ERROR("Unsupported ConstantExpr for path generation " << *const_expr)
  }

  const auto* inst = dyn_cast_or_null<Instruction>(path.value().value_or(nullptr));
  if (inst == nullptr) {
    return {};
  }

  LOG_DEBUG("Backtracking from " << *inst);

  switch (inst->getOpcode()) {
    case Instruction::Store: {
      result.push_back(llvm::dyn_cast<StoreInst>(inst)->getPointerOperand());
      return result;
    }
    case Instruction::Load: {
      result.push_back(llvm::dyn_cast<LoadInst>(inst)->getPointerOperand());
      return result;
    }
    case Instruction::GetElementPtr: {
      result.push_back(llvm::dyn_cast<GetElementPtrInst>(inst)->getPointerOperand());
      return result;
    }
    case Instruction::BitCast: {
      result.push_back(llvm::dyn_cast<llvm::BitCastInst>(inst)->getOperand(0));
      return result;
    }
    case Instruction::PHI: {
      auto* phi = llvm::dyn_cast<PHINode>(inst);
      for (auto& incoming : phi->incoming_values()) {
        LOG_DEBUG("  > Backtracking phi incoming " << *incoming.get());
        result.push_back(incoming.get());
      }
      return result;
    }
    case Instruction::Call: {
      LOG_DEBUG("Handle call inst")
      if (MemCpyInst::classof(inst)) {
        result.push_back(inst->getOperand(0));
      }

      return result;
    }
    case Instruction::SExt: {
      // Used by fortran/07_bounds.f90
      LOG_DEBUG("Handle SExt inst")
      result.push_back(llvm::dyn_cast<llvm::SExtInst>(inst)->getOperand(0));
      return result;
    }
  }
  return {};
}

auto MallocTargetMatcher::operator()(const ValuePath& path) -> decltype(DefUseChain::kContinue) {
  // This builds the path (backtrack) from store to LHS target (argument, alloca etc.)
  using namespace llvm;

  const auto current_value = path.value();

  if (!current_value) {
    LOG_DEBUG("Current value is null, skipping")
    return DefUseChain::kSkip;
  }

  const auto* value = current_value.value();

  // Handle path to alloca -> can extract type
  if (const auto* inst = dyn_cast<Instruction>(value)) {
    if (isa<IntrinsicInst>(inst)) {
      if (llvm::MemCpyInst::classof(inst)) {
        return DefUseChain::kContinue;
      }
      return DefUseChain::kSkip;
    }
    if (isa<AllocaInst>(inst)) {
      types_path.emplace_back(path);
      return DefUseChain::kSkip;  // maybe kCancel is better?
    }
  }

  if (llvm::isa<llvm::Argument>(value)) {
    types_path.emplace_back(path);
    return DefUseChain::kSkip;
  }

  if (llvm::isa<llvm::GlobalVariable>(value)) {
    types_path.emplace_back(path);
    return DefUseChain::kSkip;
  }

  if (llvm::isa<llvm::CallBase>(value)) {
    types_path.emplace_back(path);
    return DefUseChain::kSkip;
  }

  //  if (const auto* const_expr = llvm::dyn_cast<llvm::ConstantExpr>(value)) {
  //    if (const_expr->isCast()) {
  //      LOG_DEBUG("Matcher adds constantexpr path " << path)
  //      types_path.emplace_back(path);
  //    } else {
  //      LOG_DEBUG("Unsupported: Found constant expr: " << *const_expr);
  //    }
  //  }

  return DefUseChain::kContinue;
}

// const llvm::Module* MallocAnchorMatcher::getModule() const {
//   return getFunction()->getParent();
// }
//
// const llvm::Function* MallocAnchorMatcher::getFunction() const {
//   return base_inst->getParent()->getParent();
// }

auto MallocAnchorMatcher::operator()(const ValuePath& path) -> decltype(DefUseChain::kContinue) {
  using namespace llvm;

  const auto current_value = path.value();
  if (!current_value) {
    return DefUseChain::kSkip;
  }

  const auto* inst = dyn_cast<Instruction>(current_value.value());
  if (!inst) {
    return DefUseChain::kSkip;
  }

  if (llvm::isa<IntrinsicInst>(inst)) {
    if (const auto memcpy = llvm::dyn_cast<MemIntrinsic>(inst)) {
      anchors.push_back(path);
      LOG_DEBUG("Found memintrinsic " << *memcpy)
      return DefUseChain::kSkip;
    }
    return DefUseChain::kSkip;
  }

  switch (inst->getOpcode()) {
    case Instruction::Ret: {
      anchors.push_back(path);
      return DefUseChain::kCancel;
    }
    case Instruction::Store: {
      const auto* store = cast<StoreInst>(inst);
      if (store->getPointerOperand() != path.start_value()) {
        for (auto user : store->getPointerOperand()->users()) {
          if (const auto memcpy = llvm::dyn_cast<MemIntrinsic>(user)) {
            LOG_DEBUG("Store to target for memintrinsic " << *memcpy)
            return DefUseChain::kContinue;
          }
        }
        anchors.push_back(path);
      } else {
        LOG_DEBUG("Store to allocated object, skipping. " << *store)
      }

      // kSkip instead of kCancel, as multiple stores can be present for a "malloc-like" call, see test
      // "heap_lulesh_domain_mock.cpp" at higher optim:
      return DefUseChain::kSkip;
    }
    case Instruction::GetElementPtr: {
      // Currently, we do not care about "new -> gep -> ...",
      // since this may be C++ init of the allocated object
      return DefUseChain::kSkip;
    }
    case Instruction::Call:  // NOLINT
      [[fallthrough]];
    case Instruction::CallBr:
      [[fallthrough]];
    case Instruction::Invoke: {
      if (path.only_start()) {
        return DefUseChain::kContinue;
      }

      // TODO Maybe check if we have a constructor call here, and not take it if it is?
      anchors.push_back(path);

      //        const auto* call_inst = llvm::cast<CallBase>(inst);
      //        const auto* called_f  = call_inst->getCalledFunction();
      //        if (called_f != nullptr) {
      //          outs() << "Matched callbase! " << *called_f << "\n";
      //          // Argument passed to current call:
      //          const auto* arg_val = path.previous_value();
      //          assert(arg_val != nullptr && "Previous value should be argument to some function!");
      //
      //          // Argument number:
      //          const auto* const arg_pos = llvm::find_if(
      //              call_inst->args(), [&arg_val](const auto& arg_use) -> bool { return arg_use.get() == arg_val;
      //              });
      //          if (arg_pos == call_inst->arg_end()) {
      //            return DefUseChain::kContinue;
      //          }
      //          auto arg_num = std::distance(call_inst->arg_begin(), arg_pos);
      //          // Extract debug info from function at arg_num:
      //          if (auto* sub_program = called_f->getSubprogram(); sub_program != nullptr) {
      //            const auto sub_prog_arg_pos = arg_num + 1;
      //            auto types_of_subprog       = sub_program->getType()->getTypeArray();
      //            assert((types_of_subprog.size() > sub_prog_arg_pos) && "Type array smaller than arg num!");
      //            auto* type = types_of_subprog[sub_prog_arg_pos];
      //            util::DIPrinter printer(llvm::outs(), getModule());
      //            printer.traverseType(type);
      //            return DefUseChain::kCancel;
      //          }
      //        }
      return DefUseChain::kContinue;
    }
  }
  return DefUseChain::kContinue;
}

namespace fortran {

inline std::int64_t get_as_int(llvm::Value* shape) {
  const auto to_int = [](const llvm::Value* shape) -> std::optional<std::int64_t> {
    if (shape == nullptr) {
      return {};
    }
    auto* constant_int = llvm::dyn_cast<llvm::ConstantInt>(shape);
    // assert(constant_int && "Expected llvm::ConstantInt");
    if (constant_int) {
      assert(constant_int->getBitWidth() <= 64 && "Value is too wide");
      const auto type_id = static_cast<std::int64_t>(constant_int->getSExtValue());
      return {type_id};
    }
    return {};
  };

  const auto int_value = to_int(shape);
  if (int_value) {
    return int_value.value();
  }

  std::optional<std::int64_t> global_value;
  {
    DefUseChain value_traversal;
    MallocBacktrackSearch backtrack_search_dir_fn;
    value_traversal.traverse_custom(
        shape,
        [&](const ValuePath& path) {
          LOG_DEBUG("Global value for shape: " << **path.value())
          if (auto global = llvm::dyn_cast<llvm::GlobalVariable>(*path.value())) {
            const auto int_value = to_int(global->getInitializer());

            if (int_value) {
              LOG_DEBUG("Global int for shape: " << int_value.value())
              global_value = int_value;
            }
            return DefUseChain::kCancel;
          }
          return DefUseChain::kContinue;
        },
        [&](const ValuePath&) -> bool { return true; }, backtrack_search_dir_fn);
  }
  return global_value.value_or(-1);
}

std::optional<ShapeData> shape_from_value(const llvm::Value* start) {
  DefUseChain value_traversal;

  ShapeData data;
  value_traversal.traverse(
      start,
      [&](const ValuePath& path) {
        if (auto call = llvm::dyn_cast<llvm::CallBase>(*path.value())) {
          if ((call->getCalledFunction() != nullptr) &&
              util::starts_with_any_of(call->getCalledFunction()->getName(), "_FortranAAllocatableSetBounds",
                                       "_FortranAPointerSetBounds")) {
            // shape = call->getOperand(3);
            // LOG_DEBUG("Found shape: " << *shape.value())
            const auto dim = get_as_int(call->getOperand(3));
            data.shapes.emplace_back(ShapeData::IndexDim{get_as_int(call->getOperand(1)), dim});
            return DefUseChain::kContinue;
          }
        }
        return DefUseChain::kContinue;
      },
      [&](const ValuePath&) -> bool { return true; });

  if (data.shapes.empty()) {
    return {};
  }
  return data;
}

bool passed_to_fortran_helper(const llvm::Value* start) {
  DefUseChain value_traversal;

  bool passed{false};
  value_traversal.traverse(
      start,
      [&](const ValuePath& path) {
        if (auto call = llvm::dyn_cast<llvm::CallBase>(*path.value())) {
          if (call->getCalledFunction() != nullptr) {
            auto fn_name = call->getCalledFunction()->getName();
            if (util::starts_with_any_of(fn_name, "_FortranA") && fn_name != "_FortranAioOutputAscii") {
              passed = true;
              return DefUseChain::kCancel;
            }
          }
        }
        return DefUseChain::kContinue;
      },
      [&](const ValuePath&) -> bool { return true; });

  return passed;
}

}  // namespace fortran

namespace experimental {
llvm::SmallVector<dataflow::ValuePath, 4> path_from_value(const llvm::Value* start) {
  llvm::SmallVector<ValuePath, 4> ditype_paths;
  auto should_search = [&](const ValuePath&) -> bool { return true; };
  DefUseChain value_traversal;
  MallocTargetMatcher malloc_anchor_backtrack;
  MallocBacktrackSearch backtrack_search_dir_fn;
  value_traversal.traverse_custom(start, malloc_anchor_backtrack, should_search, backtrack_search_dir_fn);
  for (const auto& backtrack_path : malloc_anchor_backtrack.types_path) {
    LOG_DEBUG("Found backtrack path " << backtrack_path)
    ditype_paths.emplace_back(backtrack_path);
  }
  return ditype_paths;
}
}  // namespace experimental

}  // namespace dimeta::dataflow

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 "DataflowAnalysis.h"
9
10	#include "DefUseAnalysis.h"
11	#include "Dimeta.h"
12	#include "Util.h"
13	#include "support/Logger.h"
14
15	#include "llvm/ADT/TinyPtrVector.h"
16	#include "llvm/ADT/iterator_range.h"
17	#include "llvm/IR/BasicBlock.h"
18	#include "llvm/IR/Constants.h"
19	#include "llvm/IR/DebugInfoMetadata.h"
20	#include "llvm/IR/Function.h"
21	#include "llvm/IR/InstIterator.h"
22	#include "llvm/IR/InstrTypes.h"
23	#include "llvm/IR/Instruction.h"
24	#include "llvm/IR/Instructions.h"
25	#include "llvm/IR/IntrinsicInst.h"
26	#include "llvm/IR/Module.h"
27	#include "llvm/IR/Operator.h"
28	#include "llvm/IR/Value.h"
29	#include "llvm/Support/Casting.h"
30	#include "llvm/Support/Debug.h"
31	#include "llvm/Support/ErrorHandling.h"
32	#include "llvm/Support/raw_ostream.h"
33
34	#include <cassert>
35	#include <cstdint>
36	#include <llvm/IR/GlobalValue.h>
37	#include <optional>
38
39	namespace llvm {
40	class Argument;
41	class GlobalVariable;
42	class Module;
43	} // namespace llvm
44
45	namespace dimeta::dataflow {
46
47	struct MallocAnchorMatcher {
48	llvm::SmallVector<ValuePath, 4> anchors;
49
50	auto operator()(const ValuePath& path) -> decltype(DefUseChain::kContinue);
51	};
52
53	struct MallocTargetMatcher {
54	llvm::SmallVector<ValuePath, 4> types_path;
55
56	auto operator()(const ValuePath& path) -> decltype(DefUseChain::kContinue);
57	};
58
59	struct MallocBacktrackSearch {
60	using ValueRange = llvm::TinyPtrVector<const llvm::Value*>;
61
62	auto operator()(const ValuePath& path) -> std::optional<ValueRange>;
63	};
64
65	llvm::SmallVector<ValuePath, 4> type_for_heap_call(const llvm::CallBase* call) {	3,704✔
66	using namespace llvm;
67
68	auto should_search = [&](const ValuePath&) -> bool { return true; };	19,352✔
69	DefUseChain value_traversal;	3,704✔
70
71	// forward: find paths to anchor (store, ret, func call etc.) from malloc-like
72	LOG_DEBUG("Find heap-call to anchor w.r.t. " << *call)
73	// Anchor can be anything like function call "malloc -> .. -> foo(malloc)" or "malloc -> .. -> store" etc.
74	MallocAnchorMatcher malloc_forward_anchor_finder;	3,704!
75	// value_traversal.traverse(call, malloc_forward_anchor_finder, should_search);
76	value_traversal.traverse_custom(call, malloc_forward_anchor_finder, should_search,	7,408!
77	[](const ValuePath& val) -> std::optional<decltype(val.value().value()->users())> {	8,254✔
78	const auto value = val.value();	4,550✔
79	if (!value) {	4,550!
NEW 80	return {};	×
81	}
82	if (auto* store = llvm::dyn_cast<llvm::StoreInst>(value.value())) {	4,550!
NEW 83	return store->getPointerOperand()->users();	×
84	}
85	return value.value()->users();	4,550✔
86	});	4,550✔
87
88	// backward: find paths from anchor (store) to alloca/argument/global etc.
89	MallocTargetMatcher malloc_anchor_backtrack;	3,704!
90	MallocBacktrackSearch backtrack_search_dir_fn;	3,704✔
91
92	assert(!malloc_forward_anchor_finder.anchors.empty() && "Anchor should not be empty");	7,408!
93	llvm::SmallVector<ValuePath, 4> ditype_paths;	3,704!
94
95	for (const auto& anchor_path : malloc_forward_anchor_finder.anchors) {	7,412!
96	LOG_DEBUG("Current anchor path " << anchor_path)
97	if (auto* store_inst = dyn_cast_or_null<StoreInst>(anchor_path.value().value_or(nullptr))) {	7,124!
98	if (store_inst->getPointerOperand() == call) {	3,416!
99	// see test heap_lulesh_domain_mock.cpp with opt -O3
100	LOG_DEBUG("Continue with " << *store_inst)
UNCOV 101	continue;	×
102	}
103	if (anchor_path.value()) {	3,416!
104	LOG_DEBUG("Backtracking from anchor " << **anchor_path.value())
105	}	3,416✔
106	// dbgs() << "Traverse " << anchor_path.value() << "\n";
107	value_traversal.traverse_custom(anchor_path.value().value(), malloc_anchor_backtrack, should_search,	3,416!
108	backtrack_search_dir_fn);
109	for (const auto& backtrack_path : malloc_anchor_backtrack.types_path) {	6,976!
110	LOG_DEBUG("Found backtrack path " << backtrack_path)
111	ditype_paths.emplace_back(backtrack_path);	3,560!
112	}	3,560✔
113	continue;	3,416✔
114	}
115
116	if (auto* store_inst = dyn_cast_or_null<MemIntrinsic>(anchor_path.value().value_or(nullptr))) {	296!
117	value_traversal.traverse_custom(anchor_path.value().value(), malloc_anchor_backtrack, should_search,	4!
118	backtrack_search_dir_fn);
119	for (const auto& backtrack_path : malloc_anchor_backtrack.types_path) {	8!
120	LOG_DEBUG("Found backtrack path for memintrinsic " << backtrack_path)
121	ditype_paths.emplace_back(backtrack_path);	4!
122	}	4✔
123	continue;	4✔
124	}
125
126	ditype_paths.emplace_back(anchor_path);	288!
127	}	3,708!
128
129	LOG_DEBUG("\n")
130	LOG_DEBUG("Final paths to types:");
131	for (const auto& path : ditype_paths) {	7,556!
132	LOG_DEBUG(" T: " << path);
133	}	3,852✔
134
135	return ditype_paths;	3,704✔
136	}	3,704!
137
138	llvm::SmallVector<ValuePath, 4> path_from_alloca(const llvm::AllocaInst* alloca) {	×
139	using namespace llvm;
140
141	auto should_search = [&](const ValuePath&) -> bool { return true; };	×
142	DefUseChain value_traversal;	×
143
144	MallocAnchorMatcher malloc_forward_anchor_finder;	×
145	value_traversal.traverse(alloca, malloc_forward_anchor_finder, should_search);	×
146	return malloc_forward_anchor_finder.anchors;	×
147	}	×
148
NEW 149	llvm::SmallVector<ValuePath, 4> path_from_instruction(const llvm::Instruction* inst) {	×
150	using namespace llvm;
151
NEW 152	auto should_search = [&](const ValuePath&) -> bool { return true; };	×
NEW 153	DefUseChain value_traversal;	×
154
NEW 155	MallocAnchorMatcher malloc_forward_anchor_finder;	×
NEW 156	value_traversal.traverse(inst, malloc_forward_anchor_finder, should_search);	×
NEW 157	return malloc_forward_anchor_finder.anchors;	×
NEW 158	}	×
159
160	auto MallocBacktrackSearch::operator()(const ValuePath& path) -> std::optional<ValueRange> {	11,659✔
161	// Backtracks form malloc target (a store) to, e.g., argument/global/etc.
162	using namespace llvm;
163
164	ValueRange result;	11,659✔
165
166	if (auto const_expr = llvm::dyn_cast_or_null<llvm::ConstantExpr>(path.value().value_or(nullptr))) {	11,795!
167	if (const_expr->getOpcode() == Instruction::GetElementPtr) {	136!
168	if (auto op = llvm::dyn_cast<llvm::GEPOperator>(const_expr)) {	248!
169	result.push_back(op->getPointerOperand());	124!
170	}	124✔
171	return result;	124!
172	}
173	if (const_expr->getOpcode() == Instruction::BitCast) {	12!
174	// #if LLVM_VERSION_MAJOR < 15
175	LOG_DEBUG("Found constant bitcast from value" << *const_expr->getOperand(0))
176	result.push_back(const_expr->getOperand(0));	12!
177	// #endif
178	return result;	12!
179	}
180	LOG_ERROR("Unsupported ConstantExpr for path generation " << *const_expr)	×
181	}	×
182
183	const auto* inst = dyn_cast_or_null<Instruction>(path.value().value_or(nullptr));	11,523!
184	if (inst == nullptr) {	11,523✔
185	return {};	18✔
186	}
187
188	LOG_DEBUG("Backtracking from " << *inst);
189
190	switch (inst->getOpcode()) {	11,505!
191	case Instruction::Store: {
192	result.push_back(llvm::dyn_cast<StoreInst>(inst)->getPointerOperand());	3,416!
193	return result;	3,416!
194	}
195	case Instruction::Load: {
196	result.push_back(llvm::dyn_cast<LoadInst>(inst)->getPointerOperand());	2,961!
197	return result;	2,961!
198	}
199	case Instruction::GetElementPtr: {
200	result.push_back(llvm::dyn_cast<GetElementPtrInst>(inst)->getPointerOperand());	4,654!
201	return result;	4,654!
202	}
203	case Instruction::BitCast: {
204	result.push_back(llvm::dyn_cast<llvm::BitCastInst>(inst)->getOperand(0));	290!
205	return result;	290!
206	}
207	case Instruction::PHI: {
208	auto* phi = llvm::dyn_cast<PHINode>(inst);	180!
209	for (auto& incoming : phi->incoming_values()) {	540!
210	LOG_DEBUG(" > Backtracking phi incoming " << *incoming.get());
211	result.push_back(incoming.get());	360!
212	}	360✔
213	return result;	180!
214	}	180✔
215	case Instruction::Call: {
216	LOG_DEBUG("Handle call inst")
217	if (MemCpyInst::classof(inst)) {	4!
218	result.push_back(inst->getOperand(0));	4!
219	}	4✔
220
221	return result;	4!
222	}
223	case Instruction::SExt: {
224	// Used by fortran/07_bounds.f90
225	LOG_DEBUG("Handle SExt inst")
NEW 226	result.push_back(llvm::dyn_cast<llvm::SExtInst>(inst)->getOperand(0));	×
NEW 227	return result;	×
228	}
229	}
230	return {};	×
231	}	11,659✔
232
233	auto MallocTargetMatcher::operator()(const ValuePath& path) -> decltype(DefUseChain::kContinue) {	15,543✔
234	// This builds the path (backtrack) from store to LHS target (argument, alloca etc.)
235	using namespace llvm;
236
237	const auto current_value = path.value();	15,543✔
238
239	if (!current_value) {	15,543!
240	LOG_DEBUG("Current value is null, skipping")
241	return DefUseChain::kSkip;	×
242	}
243
244	const auto* value = current_value.value();	15,543✔
245
246	// Handle path to alloca -> can extract type
247	if (const auto* inst = dyn_cast<Instruction>(value)) {	29,240✔
248	if (isa<IntrinsicInst>(inst)) {	13,697!
249	if (llvm::MemCpyInst::classof(inst)) {	4!
250	return DefUseChain::kContinue;	4✔
251	}
UNCOV 252	return DefUseChain::kSkip;	×
253	}
254	if (isa<AllocaInst>(inst)) {	13,693✔
255	types_path.emplace_back(path);	1,909✔
256	return DefUseChain::kSkip; // maybe kCancel is better?	1,909✔
257	}
258	}	11,784✔
259
260	if (llvm::isa<llvm::Argument>(value)) {	13,630✔
261	types_path.emplace_back(path);	1,318✔
262	return DefUseChain::kSkip;	1,318✔
263	}
264
265	if (llvm::isa<llvm::GlobalVariable>(value)) {	12,312✔
266	types_path.emplace_back(path);	374✔
267	return DefUseChain::kSkip;	374✔
268	}
269
270	if (llvm::isa<llvm::CallBase>(value)) {	11,938✔
271	types_path.emplace_back(path);	283✔
272	return DefUseChain::kSkip;	283✔
273	}
274
275	// if (const auto* const_expr = llvm::dyn_cast<llvm::ConstantExpr>(value)) {
276	// if (const_expr->isCast()) {
277	// LOG_DEBUG("Matcher adds constantexpr path " << path)
278	// types_path.emplace_back(path);
279	// } else {
280	// LOG_DEBUG("Unsupported: Found constant expr: " << *const_expr);
281	// }
282	// }
283
284	return DefUseChain::kContinue;	11,655✔
285	}	15,543✔
286
287	// const llvm::Module* MallocAnchorMatcher::getModule() const {
288	// return getFunction()->getParent();
289	// }
290	//
291	// const llvm::Function* MallocAnchorMatcher::getFunction() const {
292	// return base_inst->getParent()->getParent();
293	// }
294
295	auto MallocAnchorMatcher::operator()(const ValuePath& path) -> decltype(DefUseChain::kContinue) {	9,424✔
296	using namespace llvm;
297
298	const auto current_value = path.value();	9,424✔
299	if (!current_value) {	9,424!
300	return DefUseChain::kSkip;	×
301	}
302
303	const auto* inst = dyn_cast<Instruction>(current_value.value());	9,424✔
304	if (!inst) {	9,424!
305	return DefUseChain::kSkip;	×
306	}
307
308	if (llvm::isa<IntrinsicInst>(inst)) {	9,424!
309	if (const auto memcpy = llvm::dyn_cast<MemIntrinsic>(inst)) {	8!
310	anchors.push_back(path);	4✔
311	LOG_DEBUG("Found memintrinsic " << *memcpy)
312	return DefUseChain::kSkip;	4✔
313	}
UNCOV 314	return DefUseChain::kSkip;	×
315	}
316
317	switch (inst->getOpcode()) {	9,420!
318	case Instruction::Ret: {
319	anchors.push_back(path);	156✔
320	return DefUseChain::kCancel;	156✔
321	}
322	case Instruction::Store: {
323	const auto* store = cast<StoreInst>(inst);	3,416✔
324	if (store->getPointerOperand() != path.start_value()) {	3,416!
325	for (auto user : store->getPointerOperand()->users()) {	8,080!
326	if (const auto memcpy = llvm::dyn_cast<MemIntrinsic>(user)) {	4,664!
327	LOG_DEBUG("Store to target for memintrinsic " << *memcpy)
NEW 328	return DefUseChain::kContinue;	×
329	}
330	}	4,664!
331	anchors.push_back(path);	3,416✔
332	} else {	3,416✔
333	LOG_DEBUG("Store to allocated object, skipping. " << *store)
334	}
335
336	// kSkip instead of kCancel, as multiple stores can be present for a "malloc-like" call, see test
337	// "heap_lulesh_domain_mock.cpp" at higher optim:
338	return DefUseChain::kSkip;	3,416✔
339	}	3,416✔
340	case Instruction::GetElementPtr: {
341	// Currently, we do not care about "new -> gep -> ...",
342	// since this may be C++ init of the allocated object
343	return DefUseChain::kSkip;	1,298✔
344	}	3,836✔
345	case Instruction::Call: // NOLINT
346	[[fallthrough]];
347	case Instruction::CallBr:
348	[[fallthrough]];
349	case Instruction::Invoke: {
350	if (path.only_start()) {	3,836✔
351	return DefUseChain::kContinue;	3,704✔
352	}
353
354	// TODO Maybe check if we have a constructor call here, and not take it if it is?
355	anchors.push_back(path);	132✔
356
357	// const auto* call_inst = llvm::cast<CallBase>(inst);
358	// const auto* called_f = call_inst->getCalledFunction();
359	// if (called_f != nullptr) {
360	// outs() << "Matched callbase! " << *called_f << "\n";
361	// // Argument passed to current call:
362	// const auto* arg_val = path.previous_value();
363	// assert(arg_val != nullptr && "Previous value should be argument to some function!");
364	//
365	// // Argument number:
366	// const auto* const arg_pos = llvm::find_if(
367	// call_inst->args(), [&arg_val](const auto& arg_use) -> bool { return arg_use.get() == arg_val;
368	// });
369	// if (arg_pos == call_inst->arg_end()) {
370	// return DefUseChain::kContinue;
371	// }
372	// auto arg_num = std::distance(call_inst->arg_begin(), arg_pos);
373	// // Extract debug info from function at arg_num:
374	// if (auto* sub_program = called_f->getSubprogram(); sub_program != nullptr) {
375	// const auto sub_prog_arg_pos = arg_num + 1;
376	// auto types_of_subprog = sub_program->getType()->getTypeArray();
377	// assert((types_of_subprog.size() > sub_prog_arg_pos) && "Type array smaller than arg num!");
378	// auto* type = types_of_subprog[sub_prog_arg_pos];
379	// util::DIPrinter printer(llvm::outs(), getModule());
380	// printer.traverseType(type);
381	// return DefUseChain::kCancel;
382	// }
383	// }
384	return DefUseChain::kContinue;	132✔
385	}
386	}
387	return DefUseChain::kContinue;	714✔
388	}	9,424✔
389
390	namespace fortran {
391
NEW 392	inline std::int64_t get_as_int(llvm::Value* shape) {	×
NEW 393	const auto to_int = [](const llvm::Value* shape) -> std::optional<std::int64_t> {	×
NEW 394	if (shape == nullptr) {	×
NEW 395	return {};	×
396	}
NEW 397	auto* constant_int = llvm::dyn_cast<llvm::ConstantInt>(shape);	×
398	// assert(constant_int && "Expected llvm::ConstantInt");
NEW 399	if (constant_int) {	×
NEW 400	assert(constant_int->getBitWidth() <= 64 && "Value is too wide");	×
NEW 401	const auto type_id = static_cast<std::int64_t>(constant_int->getSExtValue());	×
NEW 402	return {type_id};	×
NEW 403	}	×
NEW 404	return {};	×
NEW 405	};	×
406
NEW 407	const auto int_value = to_int(shape);	×
NEW 408	if (int_value) {	×
NEW 409	return int_value.value();	×
410	}
411
NEW 412	std::optional<std::int64_t> global_value;	×
413	{
NEW 414	DefUseChain value_traversal;	×
NEW 415	MallocBacktrackSearch backtrack_search_dir_fn;	×
NEW 416	value_traversal.traverse_custom(	×
NEW 417	shape,	×
NEW 418	[&](const ValuePath& path) {	×
419	LOG_DEBUG("Global value for shape: " << **path.value())
NEW 420	if (auto global = llvm::dyn_cast<llvm::GlobalVariable>(*path.value())) {	×
NEW 421	const auto int_value = to_int(global->getInitializer());	×
422
NEW 423	if (int_value) {	×
424	LOG_DEBUG("Global int for shape: " << int_value.value())
NEW 425	global_value = int_value;	×
NEW 426	}	×
NEW 427	return DefUseChain::kCancel;	×
NEW 428	}	×
NEW 429	return DefUseChain::kContinue;	×
NEW 430	},	×
NEW 431	[&](const ValuePath&) -> bool { return true; }, backtrack_search_dir_fn);	×
NEW 432	}	×
NEW 433	return global_value.value_or(-1);	×
NEW 434	}	×
435
NEW 436	std::optional<ShapeData> shape_from_value(const llvm::Value* start) {	×
NEW 437	DefUseChain value_traversal;	×
438
NEW 439	ShapeData data;	×
NEW 440	value_traversal.traverse(	×
NEW 441	start,	×
NEW 442	[&](const ValuePath& path) {	×
NEW 443	if (auto call = llvm::dyn_cast<llvm::CallBase>(*path.value())) {	×
NEW 444	if ((call->getCalledFunction() != nullptr) &&	×
NEW 445	util::starts_with_any_of(call->getCalledFunction()->getName(), "_FortranAAllocatableSetBounds",	×
446	"_FortranAPointerSetBounds")) {
447	// shape = call->getOperand(3);
448	// LOG_DEBUG("Found shape: " << *shape.value())
NEW 449	const auto dim = get_as_int(call->getOperand(3));	×
NEW 450	data.shapes.emplace_back(ShapeData::IndexDim{get_as_int(call->getOperand(1)), dim});	×
451	return DefUseChain::kContinue;
NEW 452	}	×
NEW 453	}	×
NEW 454	return DefUseChain::kContinue;	×
NEW 455	},	×
NEW 456	[&](const ValuePath&) -> bool { return true; });	×
457
NEW 458	if (data.shapes.empty()) {	×
NEW 459	return {};	×
460	}
NEW 461	return data;	×
NEW 462	}	×
463
464	bool passed_to_fortran_helper(const llvm::Value* start) {	9,169✔
465	DefUseChain value_traversal;	9,169✔
466
467	bool passed{false};	9,169✔
468	value_traversal.traverse(	9,169!
469	start,	9,169✔
470	[&](const ValuePath& path) {	78,438✔
471	if (auto call = llvm::dyn_cast<llvm::CallBase>(*path.value())) {	81,372!
472	if (call->getCalledFunction() != nullptr) {	12,103!
473	auto fn_name = call->getCalledFunction()->getName();	12,095✔
474	if (util::starts_with_any_of(fn_name, "_FortranA") && fn_name != "_FortranAioOutputAscii") {	12,095!
NEW 475	passed = true;	×
NEW 476	return DefUseChain::kCancel;	×
477	}
478	}	12,095!
479	}	12,103✔
480	return DefUseChain::kContinue;	69,269✔
481	},	69,269✔
482	[&](const ValuePath&) -> bool { return true; });	78,438✔
483
484	return passed;	9,169✔
485	}	9,169✔
486
487	} // namespace fortran
488
489	namespace experimental {
490	llvm::SmallVector<dataflow::ValuePath, 4> path_from_value(const llvm::Value* start) {	324✔
491	llvm::SmallVector<ValuePath, 4> ditype_paths;	324✔
492	auto should_search = [&](const ValuePath&) -> bool { return true; };	885✔
493	DefUseChain value_traversal;	324!
494	MallocTargetMatcher malloc_anchor_backtrack;	324!
495	MallocBacktrackSearch backtrack_search_dir_fn;	324✔
496	value_traversal.traverse_custom(start, malloc_anchor_backtrack, should_search, backtrack_search_dir_fn);	324!
497	for (const auto& backtrack_path : malloc_anchor_backtrack.types_path) {	648!
498	LOG_DEBUG("Found backtrack path " << backtrack_path)
499	ditype_paths.emplace_back(backtrack_path);	324!
500	}	324✔
501	return ditype_paths;	324✔
502	}	324!
503	} // namespace experimental
504
505	} // namespace dimeta::dataflow

ahueck / llvm-dimeta / 23296997048

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