LoopStrengthReduction.hpp

Go to the documentation of this file.

/*
 * Copyright 2026 Andreas Lilleby Hjulstad <andreas.lilleby.hjulstad@gmail.com>
 * See COPYING for terms of redistribution.
 */
 
#ifndef JLM_LLVM_OPT_LOOP_STRENGTH_REDUCTION_HPP
#define JLM_LLVM_OPT_LOOP_STRENGTH_REDUCTION_HPP
 
#include <jlm/llvm/ir/types.hpp>
#include <jlm/llvm/opt/ScalarEvolution.hpp>
#include <jlm/rvsdg/Transformation.hpp>
#include <jlm/util/Statistics.hpp>
 
namespace jlm::llvm
{
class LoopStrengthReduction final : public jlm::rvsdg::Transformation
{
  class Statistics;
  class Context;
 
public:
  ~LoopStrengthReduction() noexcept override;
 
  LoopStrengthReduction();
 
  LoopStrengthReduction(const LoopStrengthReduction &) = delete;
 
  LoopStrengthReduction(LoopStrengthReduction &&) = delete;
 
  LoopStrengthReduction &
  operator=(const LoopStrengthReduction &) = delete;
 
  LoopStrengthReduction &
  operator=(LoopStrengthReduction &&) = delete;
 
  void
  Run(rvsdg::RvsdgModule & rvsdgModule, util::StatisticsCollector & statisticsCollector) override;
 
private:
  void
  ProcessRegion(rvsdg::Region & region);
 
  void
  ReduceStrength(rvsdg::ThetaNode & thetaNode);
 
  bool
  ContainsMul(const rvsdg::Output & output);
 
  bool
  DependsOnInductionVariable(const rvsdg::Output & output);
 
  bool
  IsValidCandidateOperation(const rvsdg::Output & output, const rvsdg::SimpleOperation & operation);
 
  void
  ProcessOutput(
      rvsdg::Output & output,
      rvsdg::ThetaNode & thetaNode,
      util::HashSet<rvsdg::Output *> & candidateOperations,
      util::HashSet<rvsdg::Output *> & visited);
 
  void
  ReplaceCandidateOperation(rvsdg::Output & output, rvsdg::ThetaNode & thetaNode);
 
  std::optional<rvsdg::Output *>
  HoistChrec(const SCEVChainRecurrence & chrec, const rvsdg::ThetaNode & thetaNode, size_t numBits);
 
  std::optional<rvsdg::Output *>
  HoistSCEVExpresssion(const SCEV & scev, rvsdg::ThetaNode & thetaNode, size_t numBits);
 
  std::optional<rvsdg::ThetaNode::LoopVar>
  CreateNewGEPInductionVariable(const SCEVChainRecurrence & chrec, rvsdg::ThetaNode & thetaNode);
 
  std::optional<rvsdg::ThetaNode::LoopVar>
  CreateNewArithmeticInductionVariable(
      const SCEVChainRecurrence & chrec,
      rvsdg::ThetaNode & thetaNode,
      size_t numBits);
 
  std::unordered_map<const rvsdg::Output *, std::unique_ptr<SCEVChainRecurrence>> ChrecMap_;
  std::unordered_map<const rvsdg::Output *, std::unique_ptr<SCEV>> SCEVMap_;
  std::unordered_map<const rvsdg::Output *, bool> DependsOnIVMemo_;
  std::unordered_map<const rvsdg::Output *, bool> ContainsMulMemo_;
 
  std::unique_ptr<Context> Context_;
};
 
}
 
#endif