RegionPredicateTrace.hpp

Go to the documentation of this file.

/*
 * Copyright 2026 Helge Bahmann <hcb@chaoticmind.net>
 * See COPYING for terms of redistribution.
 */
 
#ifndef JLM_RVSDG_REGIONPREDICATETRACE_HPP
#define JLM_RVSDG_REGIONPREDICATETRACE_HPP
 
#include <jlm/rvsdg/control.hpp>
#include <jlm/rvsdg/graph.hpp>
#include <jlm/rvsdg/node.hpp>
#include <jlm/util/HashSet.hpp>
 
#include <unordered_map>
 
namespace jlm::rvsdg
{
 
class PredicateValueRange
{
public:
  static inline PredicateValueRange
  CreateEmpty(const ControlType & type)
  {
    return PredicateValueRange(type.nalternatives(), false);
  }
 
  static inline PredicateValueRange
  CreateUnknown(const ControlType & type)
  {
    return PredicateValueRange(type.nalternatives(), true);
  }
 
  static inline PredicateValueRange
  CreateSingleValue(const ControlValueRepresentation & value)
  {
    auto pred = PredicateValueRange(value.nalternatives(), false);
    pred.values_[value.alternative()] = true;
    return pred;
  }
 
  void
  UpdateUnion(const PredicateValueRange & other)
  {
    auto size = std::min(values_.size(), other.values_.size());
    for (std::size_t n = 0; n < size; ++n)
    {
      values_[n] = values_[n] || other.values_[n];
    }
  }
 
  bool
  AllowsValue(std::size_t alternative) const noexcept
  {
    return values_.size() > alternative && values_[alternative];
  }
 
private:
  inline PredicateValueRange(std::size_t nalternatives, bool init_value)
      : values_(nalternatives, init_value)
  {}
 
  std::vector<bool> values_;
};
 
using PredicateSatRequired = std::vector<std::pair<Input *, std::size_t>>;
 
class RegionPredicateTrace
{
public:
  ~RegionPredicateTrace();
 
  RegionPredicateTrace();
 
  PredicateValueRange
  GetRegionPredicateAssignConstraints(Region & region, Input & predUse);
 
  PredicateSatRequired
  GetRegionSatRequired(Region & region);
 
  bool
  CheckPredicatesSatisfiable(Region & originRegion, Region & targetRegion);
 
private:
  // For a given input, its RegionPredRange provides a map from regions to the
  // set of values than can end up being routed to the input, from results of the region.
  using RegionPredRange = std::unordered_map<Region *, PredicateValueRange>;
  class Observer;
 
  void
  Clear();
 
  void
  ObserveRegion(Region & region);
 
  const PredicateValueRange &
  ComputeAndRecord(
      RegionPredRange & regionPredRange,
      Input & input,
      std::unordered_map<Input *, PredicateValueRange> & visitedInputs,
      const ControlType & type);
 
  PredicateValueRange
  Compute(
      RegionPredRange & regionPredRange,
      Input & input,
      std::unordered_map<Input *, PredicateValueRange> & visitedInputs,
      const ControlType & type);
 
  // For a given input, gives the regions where we know which the set of values
  // the region may provide to the input
  std::unordered_map<Input *, RegionPredRange> predAssignment_;
 
  // For a given target region, what predicates must be satisfied to reach it
  std::unordered_map<Region *, PredicateSatRequired> predSat_;
 
  // Observers registered on region to inform the tracer when caches must be invalidated
  std::unordered_map<Region *, std::unique_ptr<Observer>> observers_;
};
 
class AlternativeRegionPredicateTracer final
{
public:
  AlternativeRegionPredicateTracer();
 
  [[nodiscard]] bool
  isReachableFromRegion(Region & targetRegion, Region & originRegion);
 
  void
  clearCaches();
 
private:
  [[nodiscard]] PredicateValueRange &
  getPossibleValues(Output & output);
 
  [[nodiscard]] PredicateValueRange
  getPossibleValuesInternal(Output & output);
 
  bool
  markRequiredPredicateValue(
      Output & output,
      size_t value,
      std::vector<Region *> & impossibleOrigins);
 
  bool
  markRequiredPredicateValueInternal(
      Output & output,
      size_t value,
      std::vector<Region *> & impossibleOrigins);
 
  [[nodiscard]] bool
  canCurrentOriginSatisfyRequirement(Output & output, size_t value);
 
  // The possible values an output of control type may have.
  std::unordered_map<Output *, PredicateValueRange> predicateValueRanges_;
 
  // Map from (output, required value) to a list of origin regions that cannot provide the value,
  // without control flow taking any back-edges around the origin region.
  std::unordered_map<
      std::pair<Output *, size_t>,
      std::vector<Region *>,
      util::Hash<std::pair<Output *, size_t>>>
      impossibleOriginRegions_;
 
  // The ancestors of the current origin region.
  // Not a cache, updates for every call to \ref isReachableFromRegion.
  util::HashSet<Region *> currentOriginRegionAncestors_;
};
 
}
 
#endif // JLM_RVSDG_REGIONTRACE_HPP