Trace.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_RVSDG_TRACE_HPP
#define JLM_RVSDG_TRACE_HPP
 
#include <jlm/rvsdg/node.hpp>
#include <jlm/rvsdg/RegionPredicateTrace.hpp>
 
namespace jlm::rvsdg
{
class GammaNode;
class ThetaNode;
 
class OutputTracer
{
public:
  enum class StructuralNodePolicy
  {
    // Perform a quick check to see if the structural output is trivially invariant,
    // i.e., gets its value directly from a single subregion argument in all subregions.
    // If so, tracing continues from the corresponding input to the structural node.
    traceThroughTriviallyInvariant = 0,
 
    // Performs the same check as above, but tries harder to determine invariance.
    // Tracing continues inside the subregion, to check if it can reach a subregion argument.
    // If all subregions reach the same argument, the structural node is invariant,
    // and tracing continue from the input of the structural node.
    traceThroughIfDetectedInvariant = 1,
 
    // Performs the same checks as above, but can also trace outputs that are not invariant.
    // Tracing can continue inside subregions, such as inside a theta subregion,
    // or inside a gamma subregion when the other subregions are unreachable or
    // provide undefined values.
    // Unlike the previous policies, this means the final return value of the tracer can be
    // inside a region that is not an ancestor of the region where tracing started.
    traceIntoSubregions = 2
  };
 
  virtual ~OutputTracer();
 
  OutputTracer() noexcept;
 
  [[nodiscard]] StructuralNodePolicy
  getStructuralNodePolicy() const noexcept
  {
    return structuralNodePolicy_;
  }
 
  [[nodiscard]] bool
  isDeepInvarianceCheckingEnabled() const noexcept
  {
    return structuralNodePolicy_ >= StructuralNodePolicy::traceThroughIfDetectedInvariant;
  }
 
  [[nodiscard]] bool
  isTracingIntoSubregionsEnabled() const noexcept
  {
    return structuralNodePolicy_ >= StructuralNodePolicy::traceIntoSubregions;
  }
 
  void
  setStructuralNodePolicy(StructuralNodePolicy value) noexcept
  {
    structuralNodePolicy_ = value;
  }
 
  [[nodiscard]] bool
  isInterprocedural() const noexcept
  {
    return isInterprocedural_;
  }
 
  void
  setInterprocedural(bool value) noexcept
  {
    isInterprocedural_ = value;
  }
 
  [[nodiscard]] bool
  isEnteringPhiNodes() const noexcept
  {
    return enterPhiNodes_;
  }
 
  void
  setEnterPhiNodes(bool value) noexcept
  {
    enterPhiNodes_ = value;
  }
 
  [[nodiscard]] bool
  isRegionPredicateCheckingEnabled() const noexcept
  {
    return enableRegionPredicateChecking_;
  }
 
  void
  setRegionPredicateCheckingEnabled(bool value) noexcept
  {
    enableRegionPredicateChecking_ = value;
  }
 
  [[nodiscard]] bool
  isInvarianceCachingEnabled() const noexcept
  {
    return enableInvarianceCaching_;
  }
 
  void
  setInvarianceCaching(bool value) noexcept
  {
    enableInvarianceCaching_ = value;
  }
 
  void
  clearInvarianceCache()
  {
    invariantOutputCache_.clear();
  }
 
  [[nodiscard]] Output &
  trace(Output & output);
 
  [[nodiscard]] Output &
  trace(Output & output, const Region * withinRegion);
 
protected:
  // Enum representing information about the path the tracer took from the starting output
  // to reach the current output being considered
  enum class BackEdgeState
  {
    // Tracing has gone from the starting output to the current output without
    // following any back-edges around the current output.
    // Theta nodes between the current output and the starting output do not matter.
    NoBackEdgeTaken,
 
    // While tracing from the starting output to the current output,
    // the tracer may have followed a back-edge going around the current output.
    // This prevents the use of the region predication checker.
    PossiblyBackEdgeTaken,
  };
 
  class TraceStepResult
  {
  public:
    [[nodiscard]] Output &
    getOutput() const noexcept
    {
      JLM_ASSERT(output_);
      return *output_;
    }
 
    [[nodiscard]] bool
    isStepOutput() const noexcept
    {
      return kind_ == TraceStepResultKind::StepOutput;
    }
 
    [[nodiscard]] bool
    isFinalOutput() const noexcept
    {
      return kind_ == TraceStepResultKind::FinalOutput;
    }
 
    [[nodiscard]] bool
    isDeadEnd() const noexcept
    {
      return kind_ == TraceStepResultKind::DeadEnd;
    }
 
    [[nodiscard]] static TraceStepResult
    createStepOutput(Output & output)
    {
      return TraceStepResult(&output, TraceStepResultKind::StepOutput);
    }
 
    [[nodiscard]] static TraceStepResult
    createFinalOutput(Output & output)
    {
      return TraceStepResult(&output, TraceStepResultKind::FinalOutput);
    }
 
    [[nodiscard]] static TraceStepResult
    createDeadEndResult()
    {
      return TraceStepResult(nullptr, TraceStepResultKind::DeadEnd);
    }
 
  private:
    enum class TraceStepResultKind
    {
      // Represents an output found after one or more steps of tracing progress,
      // but not necessarily the final stopping point for tracing.
      StepOutput,
 
      // Represents an output from which no more tracing is possible
      FinalOutput,
 
      // When tracing, the region of the starting output is the target region.
      // During tracing, tracing may enter the subregions of structural nodes.
      // Within such a subregion S, it may be discovered that all possible value origins
      // inside S are in regions from which control flow can never enter the target region.
      // This effectively means tracing never needed to enter S in the first place.
      // This is signalled by returning DeadEnd from the tracing inside S.
      DeadEnd,
    };
 
    TraceStepResult(Output * output, TraceStepResultKind kind)
        : output_(output),
          kind_(kind)
    {}
 
    Output * output_;
    TraceStepResultKind kind_;
  };
 
  [[nodiscard]] TraceStepResult
  traceInternal(Output & output, BackEdgeState backEdgeState, const Region * withinRegion);
 
  [[nodiscard]] TraceStepResult
  traceGammaOutput(GammaNode & gammaNode, Output & output, BackEdgeState backEdgeState);
 
  [[nodiscard]] TraceStepResult
  traceThetaOutput(ThetaNode & thetaNode, Output & output, BackEdgeState backEdgeState);
 
  [[nodiscard]] TraceStepResult
  traceThetaArgument(ThetaNode & thetaNode, Output & output);
 
  [[nodiscard]] virtual TraceStepResult
  traceStep(Output & output, BackEdgeState backEdgeState, const Region * withinRegion);
 
  Output &
  insertInInvarianceCache(const Output & structuralOutput, Input & structuralInput);
 
  Input *
  lookupInInvarianceCache(const Output & structuralOutput);
 
  // The policy determining how tracing handles outputs of gamma and theta nodes
  StructuralNodePolicy structuralNodePolicy_ =
      StructuralNodePolicy::traceThroughIfDetectedInvariant;
 
  // When true, tracing is allowed to continue outside of lambda nodes.
  // When false, tracing will stop at the lambda's context arguments.
  bool isInterprocedural_ = true;
 
  // When true, tracing can go from the output of a \ref PhiNode into its subregion.
  // When false, tracing will stop at the output of the phi node.
  bool enterPhiNodes_ = true;
 
  // When true, gamma subregions are ignored when it is impossible for control flow to go
  // from the gamma subregion to the region containing the output tracing started from
  bool enableRegionPredicateChecking_ = false;
  // The region predicate checker used to disqualify regions
  AlternativeRegionPredicateTracer regionPredicateTracer_;
  // The output from which the current tracing operation started.
  // Used for region predication checks.
  // This is the starting output referenced by the enum \ref BackEdgeState.
  const Output * startingOutput_ = nullptr;
 
  // When true, the tracer can cache the fact that outputs of structural nodes are invariant.
  // Enabling caching means the user of the tracer is responsible for cache invalidation.
  // @see clearInvarianceCache() for details
  bool enableInvarianceCaching_ = false;
  // Maps from a structural output to an input of the same structural node
  // that the output always gets its value from.
  std::unordered_map<const Output *, Input *> invariantOutputCache_{};
};
 
Output &
traceOutputIntraProcedurally(Output & output, bool mayEnterSubregions);
 
inline const Output &
traceOutputIntraProcedurally(const Output & output, bool mayEnterSubregions)
{
  return traceOutputIntraProcedurally(const_cast<Output &>(output), mayEnterSubregions);
}
 
Output &
traceOutput(Output & output, bool mayEnterSubregions, const Region * withinRegion = nullptr);
 
inline const Output &
traceOutput(const Output & output, bool mayEnterSubregions, const Region * withinRegion = nullptr)
{
  return traceOutput(const_cast<Output &>(output), mayEnterSubregions, withinRegion);
}
 
}
 
#endif // JLM_RVSDG_TRACE_HPP