LocalAliasAnalysis.hpp

Go to the documentation of this file.

/*
 * Copyright 2025 Håvard Krogstie <krogstie.havard@gmail.com>
 * See COPYING for terms of redistribution.
 */
 
#ifndef JLM_LLVM_OPT_ALIAS_ANALYSES_LOCALALIASANALYSIS_HPP
#define JLM_LLVM_OPT_ALIAS_ANALYSES_LOCALALIASANALYSIS_HPP
 
#include <jlm/llvm/opt/alias-analyses/AliasAnalysis.hpp>
#include <jlm/rvsdg/simple-node.hpp>
 
#include <optional>
#include <unordered_map>
 
namespace jlm::llvm::aa
{
class LocalAliasAnalysis final : public AliasAnalysis
{
  // When doing origin tracing, give up if the trace set grows larger than this
  static constexpr size_t MaxTraceCollectionSize = 1000;
 
public:
  LocalAliasAnalysis();
  ~LocalAliasAnalysis() noexcept override;
 
  std::string
  ToString() const override;
 
  AliasQueryResponse
  Query(const rvsdg::Output & p1, size_t s1, const rvsdg::Output & p2, size_t s2) override;
 
private:
  struct TracedPointerOrigin;
  struct TraceCollection;
 
  [[nodiscard]] static std::optional<int64_t>
  CalculateGepOffset(const rvsdg::SimpleNode & gepNode);
 
  [[nodiscard]] static TracedPointerOrigin
  TracePointerOriginPrecise(const rvsdg::Output & p);
 
  [[nodiscard]] static AliasQueryResponse
  QueryOffsets(
      std::optional<int64_t> offset1,
      size_t s1,
      std::optional<int64_t> offset2,
      size_t s2);
 
  [[nodiscard]] static bool
  TraceAllPointerOrigins(TracedPointerOrigin p, TraceCollection & traceCollection);
 
  [[nodiscard]] static bool
  IsOriginalOrigin(const rvsdg::Output & pointer);
 
  [[nodiscard]] static bool
  HasOnlyOriginalTopOrigins(TraceCollection & traces);
 
  [[nodiscard]] static std::optional<size_t>
  GetOriginalOriginSize(const rvsdg::Output & pointer);
 
  [[nodiscard]] static std::optional<size_t>
  GetRemainingSize(TracedPointerOrigin trace);
 
  static void
  RemoveTopOriginsWithRemainingSizeBelow(TraceCollection & traces, size_t s);
 
  [[nodiscard]] static size_t
  GetMinimumOffsetFromStart(TraceCollection & traces);
 
  static void
  RemoveTopOriginsSmallerThanSize(TraceCollection & traces, size_t s);
 
  static void
  RemoveTopOriginsWithinTheFirstNBytes(TraceCollection & traces, size_t s, size_t N);
 
  [[nodiscard]] static bool
  DoTraceCollectionsOverlap(TraceCollection & tc1, size_t s1, TraceCollection & tc2, size_t s2);
 
  [[nodiscard]] bool
  IsOriginalOriginFullyTraceable(const rvsdg::Output & pointer);
 
  [[nodiscard]] bool
  HasOnlyFullyTraceableTopOrigins(TraceCollection & traces);
 
  std::unordered_map<const rvsdg::Output *, bool> IsFullyTraceable_;
};
 
}
 
#endif // JLM_LLVM_OPT_ALIAS_ANALYSES_LOCALALIASANALYSIS_HPP