MemoryStateOperations.hpp

Go to the documentation of this file.

/*
 * Copyright 2021 Nico Reißmann <nico.reissmann@gmail.com>
 * See COPYING for terms of redistribution.
 */
 
#ifndef JLM_LLVM_IR_OPERATORS_MEMORYSTATEOPERATIONS_HPP
#define JLM_LLVM_IR_OPERATORS_MEMORYSTATEOPERATIONS_HPP
 
#include <jlm/llvm/ir/tac.hpp>
#include <jlm/llvm/ir/types.hpp>
#include <jlm/rvsdg/simple-node.hpp>
#include <jlm/util/BijectiveMap.hpp>
 
namespace jlm::llvm
{
 
using MemoryNodeId = std::size_t;
 
class MemoryStateOperation : public rvsdg::SimpleOperation
{
protected:
  MemoryStateOperation(size_t numOperands, size_t numResults)
      : SimpleOperation(
            { numOperands, MemoryStateType::Create() },
            { numResults, MemoryStateType::Create() })
  {}
};
 
class MemoryStateMergeOperation final : public MemoryStateOperation
{
public:
  ~MemoryStateMergeOperation() noexcept override;
 
  explicit MemoryStateMergeOperation(size_t numOperands)
      : MemoryStateOperation(numOperands, 1)
  {
    if (numOperands == 0)
      throw util::Error("Insufficient number of operands.");
  }
 
  bool
  operator==(const Operation & other) const noexcept override;
 
  [[nodiscard]] std::string
  debug_string() const override;
 
  [[nodiscard]] std::unique_ptr<Operation>
  copy() const override;
 
  static std::optional<std::vector<rvsdg::Output *>>
  NormalizeSingleOperand(
      const MemoryStateMergeOperation & operation,
      const std::vector<rvsdg::Output *> & operands);
 
  static std::optional<std::vector<rvsdg::Output *>>
  NormalizeDuplicateOperands(
      const MemoryStateMergeOperation & operation,
      const std::vector<rvsdg::Output *> & operands);
 
  static std::optional<std::vector<rvsdg::Output *>>
  NormalizeNestedMerges(
      const MemoryStateMergeOperation & operation,
      const std::vector<rvsdg::Output *> & operands);
 
  static std::optional<std::vector<rvsdg::Output *>>
  NormalizeMergeSplit(
      const MemoryStateMergeOperation & operation,
      const std::vector<rvsdg::Output *> & operands);
 
  static rvsdg::SimpleNode &
  CreateNode(const std::vector<rvsdg::Output *> & operands)
  {
    return rvsdg::CreateOpNode<MemoryStateMergeOperation>(operands, operands.size());
  }
 
  static rvsdg::Output *
  Create(const std::vector<rvsdg::Output *> & operands)
  {
    return CreateNode(operands).output(0);
  }
 
  static std::unique_ptr<ThreeAddressCode>
  Create(const std::vector<const Variable *> & operands)
  {
    if (operands.empty())
      throw util::Error("Insufficient number of operands.");
 
    auto operation = std::make_unique<MemoryStateMergeOperation>(operands.size());
    return ThreeAddressCode::create(std::move(operation), operands);
  }
};
 
class MemoryStateJoinOperation final : public MemoryStateOperation
{
public:
  ~MemoryStateJoinOperation() noexcept override;
 
  explicit MemoryStateJoinOperation(const size_t numOperands)
      : MemoryStateOperation(numOperands, 1)
  {
    if (numOperands == 0)
      throw std::logic_error("Insufficient number of operands.");
  }
 
  bool
  operator==(const Operation & other) const noexcept override;
 
  [[nodiscard]] std::string
  debug_string() const override;
 
  [[nodiscard]] std::unique_ptr<Operation>
  copy() const override;
 
  static std::optional<std::vector<rvsdg::Output *>>
  NormalizeSingleOperand(
      const MemoryStateJoinOperation & operation,
      const std::vector<rvsdg::Output *> & operands);
 
  static std::optional<std::vector<rvsdg::Output *>>
  NormalizeDuplicateOperands(
      const MemoryStateJoinOperation & operation,
      const std::vector<rvsdg::Output *> & operands);
 
  static std::optional<std::vector<rvsdg::Output *>>
  NormalizeNestedJoins(
      const MemoryStateJoinOperation & operation,
      const std::vector<rvsdg::Output *> & operands);
 
  static rvsdg::SimpleNode &
  CreateNode(const std::vector<rvsdg::Output *> & operands)
  {
    return rvsdg::CreateOpNode<MemoryStateJoinOperation>(operands, operands.size());
  }
};
 
class MemoryStateSplitOperation final : public MemoryStateOperation
{
public:
  ~MemoryStateSplitOperation() noexcept override;
 
  explicit MemoryStateSplitOperation(const size_t numResults)
      : MemoryStateOperation(1, numResults)
  {
    if (numResults == 0)
      throw util::Error("Insufficient number of results.");
  }
 
  bool
  operator==(const Operation & other) const noexcept override;
 
  [[nodiscard]] std::string
  debug_string() const override;
 
  [[nodiscard]] std::unique_ptr<Operation>
  copy() const override;
 
  static std::optional<std::vector<rvsdg::Output *>>
  NormalizeSingleResult(
      const MemoryStateSplitOperation & operation,
      const std::vector<rvsdg::Output *> & operands);
 
  static std::optional<std::vector<rvsdg::Output *>>
  NormalizeNestedSplits(
      const MemoryStateSplitOperation & operation,
      const std::vector<rvsdg::Output *> & operands);
 
  static std::optional<std::vector<rvsdg::Output *>>
  NormalizeSplitMerge(
      const MemoryStateSplitOperation & operation,
      const std::vector<rvsdg::Output *> & operands);
 
  static rvsdg::SimpleNode &
  CreateNode(rvsdg::Output & operand, const size_t numResults)
  {
    return rvsdg::CreateOpNode<MemoryStateSplitOperation>({ &operand }, numResults);
  }
 
  static std::vector<rvsdg::Output *>
  Create(rvsdg::Output & operand, const size_t numResults)
  {
    return outputs(&CreateNode(operand, numResults));
  }
};
 
class LambdaEntryMemoryStateSplitOperation final : public MemoryStateOperation
{
public:
  ~LambdaEntryMemoryStateSplitOperation() noexcept override;
 
  explicit LambdaEntryMemoryStateSplitOperation(const std::vector<MemoryNodeId> & memoryNodeIds);
 
  bool
  operator==(const Operation & other) const noexcept override;
 
  [[nodiscard]] std::string
  debug_string() const override;
 
  [[nodiscard]] std::unique_ptr<Operation>
  copy() const override;
 
  [[nodiscard]] std::vector<MemoryNodeId>
  getMemoryNodeIds() const noexcept
  {
    std::vector<MemoryNodeId> memoryNodeIds(nresults());
    for (auto [memoryNodeId, index] : memoryNodeIdToIndexMap_)
    {
      JLM_ASSERT(index < nresults());
      memoryNodeIds[index] = memoryNodeId;
    }
 
    return memoryNodeIds;
  }
 
  [[nodiscard]] static rvsdg::Output *
  tryMapMemoryNodeIdToOutput(const rvsdg::SimpleNode & node, MemoryNodeId memoryNodeId);
 
  [[nodiscard]] static MemoryNodeId
  mapOutputToMemoryNodeId(const rvsdg::Output & output);
 
  static std::optional<std::vector<rvsdg::Output *>>
  NormalizeCallEntryMemoryStateMerge(
      const LambdaEntryMemoryStateSplitOperation & lambdaEntrySplitOperation,
      const std::vector<rvsdg::Output *> & operands);
 
  static rvsdg::SimpleNode &
  CreateNode(rvsdg::Output & operand, std::vector<MemoryNodeId> memoryNodeIds)
  {
    return rvsdg::CreateOpNode<LambdaEntryMemoryStateSplitOperation>(
        { &operand },
        std::move(memoryNodeIds));
  }
 
private:
  util::BijectiveMap<MemoryNodeId, size_t> memoryNodeIdToIndexMap_{};
};
 
class LambdaExitMemoryStateMergeOperation final : public MemoryStateOperation
{
public:
  ~LambdaExitMemoryStateMergeOperation() noexcept override;
 
  explicit LambdaExitMemoryStateMergeOperation(const std::vector<MemoryNodeId> & memoryNodeIds);
 
  bool
  operator==(const Operation & other) const noexcept override;
 
  [[nodiscard]] std::string
  debug_string() const override;
 
  [[nodiscard]] std::unique_ptr<Operation>
  copy() const override;
 
  [[nodiscard]] std::vector<MemoryNodeId>
  getMemoryNodeIds() const noexcept
  {
    std::vector<MemoryNodeId> memoryNodeIds(narguments());
    for (auto [memoryNodeId, index] : MemoryNodeIdToIndex_)
    {
      JLM_ASSERT(index < narguments());
      memoryNodeIds[index] = memoryNodeId;
    }
 
    return memoryNodeIds;
  }
 
  [[nodiscard]] static rvsdg::Input *
  tryMapMemoryNodeIdToInput(const rvsdg::SimpleNode & node, MemoryNodeId memoryNodeId);
 
  [[nodiscard]] static MemoryNodeId
  mapInputToMemoryNodeId(const rvsdg::Input & input);
 
  static std::optional<std::vector<rvsdg::Output *>>
  NormalizeLoadFromAlloca(
      const LambdaExitMemoryStateMergeOperation & operation,
      const std::vector<rvsdg::Output *> & operands);
 
  static std::optional<std::vector<rvsdg::Output *>>
  NormalizeStoreToAlloca(
      const LambdaExitMemoryStateMergeOperation & operation,
      const std::vector<rvsdg::Output *> & operands);
 
  static std::optional<std::vector<rvsdg::Output *>>
  NormalizeAlloca(
      const LambdaExitMemoryStateMergeOperation & operation,
      const std::vector<rvsdg::Output *> & operands);
 
  static rvsdg::Node &
  CreateNode(
      rvsdg::Region & region,
      const std::vector<rvsdg::Output *> & operands,
      const std::vector<MemoryNodeId> & memoryNodeIds)
  {
    return operands.empty()
             ? rvsdg::CreateOpNode<LambdaExitMemoryStateMergeOperation>(region, memoryNodeIds)
             : rvsdg::CreateOpNode<LambdaExitMemoryStateMergeOperation>(operands, memoryNodeIds);
  }
 
private:
  util::BijectiveMap<MemoryNodeId, size_t> MemoryNodeIdToIndex_{};
};
 
class CallEntryMemoryStateMergeOperation final : public MemoryStateOperation
{
public:
  ~CallEntryMemoryStateMergeOperation() noexcept override;
 
  explicit CallEntryMemoryStateMergeOperation(const std::vector<MemoryNodeId> & memoryNodeIds);
 
  bool
  operator==(const Operation & other) const noexcept override;
 
  [[nodiscard]] std::string
  debug_string() const override;
 
  [[nodiscard]] std::unique_ptr<Operation>
  copy() const override;
 
  [[nodiscard]] std::vector<MemoryNodeId>
  getMemoryNodeIds() const noexcept
  {
    std::vector<MemoryNodeId> memoryNodeIds(narguments());
    for (auto [memoryNodeId, index] : MemoryNodeIdToIndex_)
    {
      JLM_ASSERT(index < narguments());
      memoryNodeIds[index] = memoryNodeId;
    }
 
    return memoryNodeIds;
  }
 
  [[nodiscard]] static rvsdg::Input *
  tryMapMemoryNodeIdToInput(const rvsdg::SimpleNode & node, MemoryNodeId memoryNodeId);
 
  static rvsdg::SimpleNode &
  CreateNode(
      rvsdg::Region & region,
      const std::vector<rvsdg::Output *> & operands,
      std::vector<MemoryNodeId> memoryNodeIds)
  {
    return operands.empty() ? rvsdg::CreateOpNode<CallEntryMemoryStateMergeOperation>(
                                  region,
                                  std::move(memoryNodeIds))
                            : rvsdg::CreateOpNode<CallEntryMemoryStateMergeOperation>(
                                  operands,
                                  std::move(memoryNodeIds));
  }
 
private:
  util::BijectiveMap<MemoryNodeId, size_t> MemoryNodeIdToIndex_{};
};
 
class CallExitMemoryStateSplitOperation final : public MemoryStateOperation
{
public:
  ~CallExitMemoryStateSplitOperation() noexcept override;
 
  explicit CallExitMemoryStateSplitOperation(const std::vector<MemoryNodeId> & memoryNodeIds);
 
  bool
  operator==(const Operation & other) const noexcept override;
 
  [[nodiscard]] std::string
  debug_string() const override;
 
  [[nodiscard]] std::unique_ptr<Operation>
  copy() const override;
 
  [[nodiscard]] std::vector<MemoryNodeId>
  getMemoryNodeIds() const noexcept
  {
    std::vector<MemoryNodeId> memoryNodeIds(nresults());
    for (auto [memoryNodeId, index] : memoryNodeIdToIndexMap_)
    {
      JLM_ASSERT(index < nresults());
      memoryNodeIds[index] = memoryNodeId;
    }
 
    return memoryNodeIds;
  }
 
  [[nodiscard]] static rvsdg::Output *
  tryMapMemoryNodeIdToOutput(const rvsdg::SimpleNode & node, MemoryNodeId memoryNodeId);
 
  [[nodiscard]] static MemoryNodeId
  mapOutputToMemoryNodeId(const rvsdg::Output & output);
 
  static std::optional<std::vector<rvsdg::Output *>>
  NormalizeLambdaExitMemoryStateMerge(
      const CallExitMemoryStateSplitOperation & callExitSplitOperation,
      const std::vector<rvsdg::Output *> & operands);
 
  static rvsdg::SimpleNode &
  CreateNode(rvsdg::Output & operand, std::vector<MemoryNodeId> memoryNodeIds)
  {
    return rvsdg::CreateOpNode<CallExitMemoryStateSplitOperation>(
        { &operand },
        std::move(memoryNodeIds));
  }
 
private:
  util::BijectiveMap<MemoryNodeId, size_t> memoryNodeIdToIndexMap_{};
};
 
[[nodiscard]] bool
hasMemoryState(const rvsdg::Node & node);
 
}
 
#endif