23299097010

Committed 19 Mar 2026 02:11PM UTC coverage: 73.206% (-0.4%) from 73.626%

Build # 23299097010

Build Type

Pull #49

github

Committed by

web-flow

Commit Message

Merge 2bdb642e6 into cefb3414f

Pull Request Pull Request #49: Initial Fortran Support

Run Details

2176 of 3670 branches covered (59.29%)

Branch coverage included in aggregate %.

388 of 445 new or added lines in 15 files covered. (87.19%)

19 existing lines in 5 files now uncovered.

2578 of 2824 relevant lines covered (91.29%)

14323.15 hits per line

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

70.1

/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) {	4,528✔
66	using namespace llvm;
67
68	auto should_search = [&](const ValuePath&) -> bool { return true; };	23,916✔
69	DefUseChain value_traversal;	4,528✔
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;	4,528!
75	// value_traversal.traverse(call, malloc_forward_anchor_finder, should_search);
76	value_traversal.traverse_custom(call, malloc_forward_anchor_finder, should_search,	9,056!
77	[](const ValuePath& val) -> std::optional<decltype(val.value().value()->users())> {	10,162✔
78	const auto value = val.value();	5,634✔
79	if (!value) {	5,634!
NEW 80	return {};	×
81	}
82	if (auto* store = llvm::dyn_cast<llvm::StoreInst>(value.value())) {	5,722✔
83	return store->getPointerOperand()->users();	88✔
84	}
85	return value.value()->users();	5,546✔
86	});	5,634✔
87
88	// backward: find paths from anchor (store) to alloca/argument/global etc.
89	MallocTargetMatcher malloc_anchor_backtrack;	4,528!
90	MallocBacktrackSearch backtrack_search_dir_fn;	4,528✔
91
92	assert(!malloc_forward_anchor_finder.anchors.empty() && "Anchor should not be empty");	9,056!
93	llvm::SmallVector<ValuePath, 4> ditype_paths;	4,528!
94
95	for (const auto& anchor_path : malloc_forward_anchor_finder.anchors) {	9,060!
96	LOG_DEBUG("Current anchor path " << anchor_path)
97	if (auto* store_inst = dyn_cast_or_null<StoreInst>(anchor_path.value().value_or(nullptr))) {	8,636!
98	if (store_inst->getPointerOperand() == call) {	4,104!
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()) {	4,104!
104	LOG_DEBUG("Backtracking from anchor " << **anchor_path.value())
105	}	4,104✔
106	// dbgs() << "Traverse " << anchor_path.value() << "\n";
107	value_traversal.traverse_custom(anchor_path.value().value(), malloc_anchor_backtrack, should_search,	4,104!
108	backtrack_search_dir_fn);
109	for (const auto& backtrack_path : malloc_anchor_backtrack.types_path) {	8,380!
110	LOG_DEBUG("Found backtrack path " << backtrack_path)
111	ditype_paths.emplace_back(backtrack_path);	4,276!
112	}	4,276✔
113	continue;	4,104✔
114	}
115
116	if (auto* store_inst = dyn_cast_or_null<MemIntrinsic>(anchor_path.value().value_or(nullptr))) {	520!
117	value_traversal.traverse_custom(anchor_path.value().value(), malloc_anchor_backtrack, should_search,	92!
118	backtrack_search_dir_fn);
119	for (const auto& backtrack_path : malloc_anchor_backtrack.types_path) {	184!
120	LOG_DEBUG("Found backtrack path for memintrinsic " << backtrack_path)
121	ditype_paths.emplace_back(backtrack_path);	92!
122	}	92✔
123	continue;	92✔
124	}
125
126	ditype_paths.emplace_back(anchor_path);	336!
127	}	4,532!
128
129	LOG_DEBUG("\n")
130	LOG_DEBUG("Final paths to types:");
131	for (const auto& path : ditype_paths) {	9,232!
132	LOG_DEBUG(" T: " << path);
133	}	4,704✔
134
135	return ditype_paths;	4,528✔
136	}	4,528!
137
138	llvm::SmallVector<ValuePath, 4> path_from_alloca(const llvm::AllocaInst* alloca) {	80✔
139	using namespace llvm;
140
141	auto should_search = [&](const ValuePath&) -> bool { return true; };	160✔
142	DefUseChain value_traversal;	80✔
143
144	MallocAnchorMatcher malloc_forward_anchor_finder;	80!
145	value_traversal.traverse(alloca, malloc_forward_anchor_finder, should_search);	80!
146	return malloc_forward_anchor_finder.anchors;	80!
147	}	80✔
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> {	14,613✔
161	// Backtracks form malloc target (a store) to, e.g., argument/global/etc.
162	using namespace llvm;
163
164	ValueRange result;	14,613✔
165
166	if (auto const_expr = llvm::dyn_cast_or_null<llvm::ConstantExpr>(path.value().value_or(nullptr))) {	14,785!
167	if (const_expr->getOpcode() == Instruction::GetElementPtr) {	172!
168	if (auto op = llvm::dyn_cast<llvm::GEPOperator>(const_expr)) {	320!
169	result.push_back(op->getPointerOperand());	160!
170	}	160✔
171	return result;	160!
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));	14,441!
184	if (inst == nullptr) {	14,441✔
185	return {};	34✔
186	}
187
188	LOG_DEBUG("Backtracking from " << *inst);
189
190	switch (inst->getOpcode()) {	14,407!
191	case Instruction::Store: {
192	result.push_back(llvm::dyn_cast<StoreInst>(inst)->getPointerOperand());	4,104!
193	return result;	4,104!
194	}
195	case Instruction::Load: {
196	result.push_back(llvm::dyn_cast<LoadInst>(inst)->getPointerOperand());	3,683!
197	return result;	3,683!
198	}
199	case Instruction::GetElementPtr: {
200	result.push_back(llvm::dyn_cast<GetElementPtrInst>(inst)->getPointerOperand());	5,982!
201	return result;	5,982!
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);	216!
209	for (auto& incoming : phi->incoming_values()) {	648!
210	LOG_DEBUG(" > Backtracking phi incoming " << *incoming.get());
211	result.push_back(incoming.get());	432!
212	}	432✔
213	return result;	216!
214	}	216✔
215	case Instruction::Call: {
216	LOG_DEBUG("Handle call inst")
217	if (MemCpyInst::classof(inst)) {	92!
218	result.push_back(inst->getOperand(0));	92!
219	}	92✔
220
221	return result;	92!
222	}
223	case Instruction::SExt: {
224	// Used by fortran/07_bounds.f90
225	LOG_DEBUG("Handle SExt inst")
226	result.push_back(llvm::dyn_cast<llvm::SExtInst>(inst)->getOperand(0));	40!
227	return result;	40!
228	}
229	}
230	return {};	×
231	}	14,613✔
232
233	auto MallocTargetMatcher::operator()(const ValuePath& path) -> decltype(DefUseChain::kContinue) {	19,445✔
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();	19,445✔
238
239	if (!current_value) {	19,445!
240	LOG_DEBUG("Current value is null, skipping")
241	return DefUseChain::kSkip;	×
242	}
243
244	const auto* value = current_value.value();	19,445✔
245
246	// Handle path to alloca -> can extract type
247	if (const auto* inst = dyn_cast<Instruction>(value)) {	36,492✔
248	if (isa<IntrinsicInst>(inst)) {	17,047✔
249	if (llvm::MemCpyInst::classof(inst)) {	92!
250	return DefUseChain::kContinue;	92✔
251	}
UNCOV 252	return DefUseChain::kSkip;	×
253	}
254	if (isa<AllocaInst>(inst)) {	16,955✔
255	types_path.emplace_back(path);	2,383✔
256	return DefUseChain::kSkip; // maybe kCancel is better?	2,383✔
257	}
258	}	14,572✔
259
260	if (llvm::isa<llvm::Argument>(value)) {	16,970✔
261	types_path.emplace_back(path);	1,698✔
262	return DefUseChain::kSkip;	1,698✔
263	}
264
265	if (llvm::isa<llvm::GlobalVariable>(value)) {	15,272✔
266	types_path.emplace_back(path);	506✔
267	return DefUseChain::kSkip;	506✔
268	}
269
270	if (llvm::isa<llvm::CallBase>(value)) {	14,766✔
271	types_path.emplace_back(path);	337✔
272	return DefUseChain::kSkip;	337✔
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;	14,429✔
285	}	19,445✔
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) {	11,992✔
296	using namespace llvm;
297
298	const auto current_value = path.value();	11,992✔
299	if (!current_value) {	11,992!
300	return DefUseChain::kSkip;	×
301	}
302
303	const auto* inst = dyn_cast<Instruction>(current_value.value());	11,992✔
304	if (!inst) {	11,992!
305	return DefUseChain::kSkip;	×
306	}
307
308	if (llvm::isa<IntrinsicInst>(inst)) {	11,992✔
309	if (const auto memcpy = llvm::dyn_cast<MemIntrinsic>(inst)) {	344!
310	anchors.push_back(path);	172✔
311	LOG_DEBUG("Found memintrinsic " << *memcpy)
312	return DefUseChain::kSkip;	172✔
313	}
UNCOV 314	return DefUseChain::kSkip;	×
315	}
316
317	switch (inst->getOpcode()) {	11,820!
318	case Instruction::Ret: {
319	anchors.push_back(path);	180✔
320	return DefUseChain::kCancel;	180✔
321	}
322	case Instruction::Store: {
323	const auto* store = cast<StoreInst>(inst);	4,192✔
324	if (store->getPointerOperand() != path.start_value()) {	4,192!
325	for (auto user : store->getPointerOperand()->users()) {	10,084✔
326	if (const auto memcpy = llvm::dyn_cast<MemIntrinsic>(user)) {	5,980✔
327	LOG_DEBUG("Store to target for memintrinsic " << *memcpy)
328	return DefUseChain::kContinue;	88✔
329	}
330	}	5,892✔
331	anchors.push_back(path);	4,104✔
332	} else {	4,104✔
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;	4,104✔
339	}	4,192✔
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,822✔
344	}	4,684✔
345	case Instruction::Call: // NOLINT
346	[[fallthrough]];
347	case Instruction::CallBr:
348	[[fallthrough]];
349	case Instruction::Invoke: {
350	if (path.only_start()) {	4,684✔
351	return DefUseChain::kContinue;	4,528✔
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);	156✔
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;	156✔
385	}
386	}
387	return DefUseChain::kContinue;	942✔
388	}	11,992✔
389
390	namespace fortran {
391
392	inline std::int64_t get_as_int(llvm::Value* shape) {	176✔
393	const auto to_int = [](const llvm::Value* shape) -> std::optional<std::int64_t> {	380✔
394	if (shape == nullptr) {	204!
NEW 395	return {};	×
396	}
397	auto* constant_int = llvm::dyn_cast<llvm::ConstantInt>(shape);	204✔
398	// assert(constant_int && "Expected llvm::ConstantInt");
399	if (constant_int) {	204✔
400	assert(constant_int->getBitWidth() <= 64 && "Value is too wide");	328!
401	const auto type_id = static_cast<std::int64_t>(constant_int->getSExtValue());	164✔
402	return {type_id};	164✔
403	}	164✔
404	return {};	40✔
405	};	204✔
406
407	const auto int_value = to_int(shape);	176✔
408	if (int_value) {	176✔
409	return int_value.value();	136✔
410	}
411
412	std::optional<std::int64_t> global_value;	40✔
413	{
414	DefUseChain value_traversal;	40✔
415	MallocBacktrackSearch backtrack_search_dir_fn;	40✔
416	value_traversal.traverse_custom(	40!
417	shape,	40✔
418	[&](const ValuePath& path) {	160✔
419	LOG_DEBUG("Global value for shape: " << **path.value())
420	if (auto global = llvm::dyn_cast<llvm::GlobalVariable>(*path.value())) {	148!
421	const auto int_value = to_int(global->getInitializer());	28✔
422
423	if (int_value) {	28!
424	LOG_DEBUG("Global int for shape: " << int_value.value())
425	global_value = int_value;	28✔
426	}	28✔
427	return DefUseChain::kCancel;	28✔
428	}	28✔
429	return DefUseChain::kContinue;	92✔
430	},	120✔
431	[&](const ValuePath&) -> bool { return true; }, backtrack_search_dir_fn);	132✔
432	}	40✔
433	return global_value.value_or(-1);	40✔
434	}	176✔
435
436	std::optional<ShapeData> shape_from_value(const llvm::Value* start) {	120✔
437	DefUseChain value_traversal;	120✔
438
439	ShapeData data;	120✔
440	value_traversal.traverse(	120!
441	start,	120✔
442	[&](const ValuePath& path) {	1,404✔
443	if (auto call = llvm::dyn_cast<llvm::CallBase>(*path.value())) {	1,716!
444	if ((call->getCalledFunction() != nullptr) &&	432!
445	util::starts_with_any_of(call->getCalledFunction()->getName(), "_FortranAAllocatableSetBounds",	432✔
446	"_FortranAPointerSetBounds")) {
447	// shape = call->getOperand(3);
448	// LOG_DEBUG("Found shape: " << *shape.value())
449	const auto dim = get_as_int(call->getOperand(3));	88✔
450	data.shapes.emplace_back(ShapeData::IndexDim{get_as_int(call->getOperand(1)), dim});	88✔
451	return DefUseChain::kContinue;	88✔
452	}	88✔
453	}	344✔
454	return DefUseChain::kContinue;	1,196✔
455	},	1,284✔
456	[&](const ValuePath&) -> bool { return true; });	1,404✔
457
458	if (data.shapes.empty()) {	120✔
459	return {};	48✔
460	}
461	return data;	72✔
462	}	120✔
463
464	bool passed_to_fortran_helper(const llvm::Value* start) {	11,013✔
465	DefUseChain value_traversal;	11,013✔
466
467	bool passed{false};	11,013✔
468	value_traversal.traverse(	11,013!
469	start,	11,013✔
470	[&](const ValuePath& path) {	94,936✔
471	if (auto call = llvm::dyn_cast<llvm::CallBase>(*path.value())) {	98,406✔
472	if (call->getCalledFunction() != nullptr) {	14,483!
473	auto fn_name = call->getCalledFunction()->getName();	14,475✔
474	if (util::starts_with_any_of(fn_name, "_FortranA") && fn_name != "_FortranAioOutputAscii") {	14,475✔
475	passed = true;	36✔
476	return DefUseChain::kCancel;	36✔
477	}
478	}	14,475✔
479	}	14,447✔
480	return DefUseChain::kContinue;	83,887✔
481	},	83,923✔
482	[&](const ValuePath&) -> bool { return true; });	94,900✔
483
484	return passed;	11,013✔
485	}	11,013✔
486
487	} // namespace fortran
488
489	namespace experimental {
490	llvm::SmallVector<dataflow::ValuePath, 4> path_from_value(const llvm::Value* start) {	560✔
491	llvm::SmallVector<ValuePath, 4> ditype_paths;	560✔
492	auto should_search = [&](const ValuePath&) -> bool { return true; };	1,327✔
493	DefUseChain value_traversal;	560!
494	MallocTargetMatcher malloc_anchor_backtrack;	560!
495	MallocBacktrackSearch backtrack_search_dir_fn;	560✔
496	value_traversal.traverse_custom(start, malloc_anchor_backtrack, should_search, backtrack_search_dir_fn);	560!
497	for (const auto& backtrack_path : malloc_anchor_backtrack.types_path) {	1,120!
498	LOG_DEBUG("Found backtrack path " << backtrack_path)
499	ditype_paths.emplace_back(backtrack_path);	560!
500	}	560✔
501	return ditype_paths;	560✔
502	}	560!
503	} // namespace experimental
504
505	} // namespace dimeta::dataflow

ahueck / llvm-dimeta / 23299097010

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