DifferencePropagation.hpp

Go to the documentation of this file.

/*
 * Copyright 2024 Håvard Krogstie <krogstie.havard@gmail.com>
 * See COPYING for terms of redistribution.
 */
 
#ifndef JLM_LLVM_OPT_ALIAS_ANALYSES_DIFFERENCEPROPAGATION_HPP
#define JLM_LLVM_OPT_ALIAS_ANALYSES_DIFFERENCEPROPAGATION_HPP
 
#include <jlm/llvm/opt/alias-analyses/PointerObjectSet.hpp>
 
#include <vector>
 
namespace jlm::llvm::aa
{
 
class DifferencePropagation
{
 
public:
  explicit DifferencePropagation(PointerObjectSet & set)
      : Set_(set)
  {}
 
  void
  Initialize()
  {
    NewPointees_.resize(Set_.NumPointerObjects());
    NewPointeesTracked_.resize(Set_.NumPointerObjects(), false);
    PointsToExternalFlagSeen_.resize(Set_.NumPointerObjects(), false);
    PointeesEscapeFlagSeen_.resize(Set_.NumPointerObjects(), false);
  }
 
  [[nodiscard]] bool
  IsInitialized() const noexcept
  {
    return NewPointees_.size() == Set_.NumPointerObjects();
  }
 
  void
  ClearNewPointees(PointerObjectIndex index)
  {
    JLM_ASSERT(IsInitialized());
    JLM_ASSERT(Set_.IsUnificationRoot(index));
 
    NewPointees_[index].Clear();
    NewPointeesTracked_[index] = true;
  };
 
  bool
  AddToPointsToSet(PointerObjectIndex pointer, PointerObjectIndex pointee)
  {
    JLM_ASSERT(IsInitialized());
    JLM_ASSERT(Set_.IsUnificationRoot(pointer));
 
    // If pointees added to the superset are being tracked, use the tracking version
    bool newPointee = Set_.AddToPointsToSet(pointer, pointee);
    if (newPointee && NewPointeesTracked_[pointer])
      return NewPointees_[pointer].insert(pointee);
 
    return newPointee;
  }
 
  bool
  MakePointsToSetSuperset(PointerObjectIndex superset, PointerObjectIndex subset)
  {
    JLM_ASSERT(IsInitialized());
    JLM_ASSERT(Set_.IsUnificationRoot(superset));
 
    // If pointees added to the superset are being tracked, use the tracking version
    if (NewPointeesTracked_[superset])
      return Set_.MakePointsToSetSuperset(superset, subset, NewPointees_[superset]);
    else
      return Set_.MakePointsToSetSuperset(superset, subset);
  }
 
  [[nodiscard]] const util::HashSet<PointerObjectIndex> &
  GetNewPointees(PointerObjectIndex index) const
  {
    JLM_ASSERT(IsInitialized());
    JLM_ASSERT(Set_.IsUnificationRoot(index));
    if (NewPointeesTracked_[index])
      return NewPointees_[index];
    return Set_.GetPointsToSet(index);
  }
 
  void
  OnRemoveAllPointees(PointerObjectIndex index)
  {
    NewPointeesTracked_[index] = false;
    NewPointees_[index].Clear();
  }
 
  [[nodiscard]] bool
  PointsToExternalIsNew(PointerObjectIndex index)
  {
    JLM_ASSERT(IsInitialized());
    JLM_ASSERT(Set_.IsUnificationRoot(index));
    if (!Set_.IsPointingToExternal(index))
      return false;
    return !PointsToExternalFlagSeen_[index];
  }
 
  void
  MarkPointsToExternalAsHandled(PointerObjectIndex index)
  {
    JLM_ASSERT(Set_.IsUnificationRoot(index));
    JLM_ASSERT(Set_.IsPointingToExternal(index));
    PointsToExternalFlagSeen_[index] = true;
  }
 
  [[nodiscard]] bool
  PointeesEscapeIsNew(PointerObjectIndex index)
  {
    JLM_ASSERT(IsInitialized());
    JLM_ASSERT(Set_.IsUnificationRoot(index));
    if (!Set_.HasPointeesEscaping(index))
      return false;
    return !PointeesEscapeFlagSeen_[index];
  }
 
  void
  MarkPointeesEscapeAsHandled(PointerObjectIndex index)
  {
    JLM_ASSERT(Set_.IsUnificationRoot(index));
    JLM_ASSERT(Set_.HasPointeesEscaping(index));
    PointeesEscapeFlagSeen_[index] = true;
  }
 
  void
  OnPointerObjectsUnified(PointerObjectIndex root, PointerObjectIndex nonRoot)
  {
    JLM_ASSERT(IsInitialized());
 
    // After unification, forget everything about tracked differences in points-to sets
    NewPointees_[nonRoot].Clear();
    NewPointees_[root].Clear();
    NewPointeesTracked_[root] = false;
 
    PointsToExternalFlagSeen_[root] =
        PointsToExternalFlagSeen_[root] && PointsToExternalFlagSeen_[nonRoot];
    PointeesEscapeFlagSeen_[root] =
        PointeesEscapeFlagSeen_[root] && PointeesEscapeFlagSeen_[nonRoot];
  }
 
private:
  PointerObjectSet & Set_;
 
  // Only unification roots matter in these vectors
 
  // Tracks all new pointees added to a unification root i,
  // since ClearNewPointees(i) was last called.
  std::vector<util::HashSet<PointerObjectIndex>> NewPointees_;
  // Becomes true for a unification root i when CleanNewPointees(i) is called for the first time.
  // Becomes false again when unification fully resets difference propagation
  std::vector<bool> NewPointeesTracked_;
 
  // These are set to true after the _IsNew have returned true
  // When two PointerObjects a and b are unified, the flag only remains "seen",
  // if the flag has already been "seen" on both a and b.
  std::vector<bool> PointsToExternalFlagSeen_;
  std::vector<bool> PointeesEscapeFlagSeen_;
};
 
}
 
#endif // JLM_LLVM_OPT_ALIAS_ANALYSES_DIFFERENCEPROPAGATION_HPP