Store.cpp

Go to the documentation of this file.

/*
 * Copyright 2017 Nico Reißmann <nico.reissmann@gmail.com>
 * See COPYING for terms of redistribution.
 */
 
#include <jlm/llvm/ir/operators/alloca.hpp>
#include <jlm/llvm/ir/operators/IOBarrier.hpp>
#include <jlm/llvm/ir/operators/MemoryStateOperations.hpp>
#include <jlm/llvm/ir/operators/Store.hpp>
#include <jlm/llvm/ir/Trace.hpp>
#include <jlm/llvm/ir/types.hpp>
#include <jlm/rvsdg/simple-node.hpp>
#include <jlm/util/HashSet.hpp>
 
namespace jlm::llvm
{
 
StoreNonVolatileOperation::~StoreNonVolatileOperation() noexcept = default;
 
bool
StoreNonVolatileOperation::operator==(const Operation & other) const noexcept
{
  auto operation = dynamic_cast<const StoreNonVolatileOperation *>(&other);
  return operation && operation->narguments() == narguments()
      && operation->GetStoredType() == GetStoredType()
      && operation->GetAlignment() == GetAlignment();
}
 
std::string
StoreNonVolatileOperation::debug_string() const
{
  return "Store";
}
 
std::unique_ptr<rvsdg::Operation>
StoreNonVolatileOperation::copy() const
{
  return std::make_unique<StoreNonVolatileOperation>(*this);
}
 
static bool
is_store_mux_reducible(const std::vector<jlm::rvsdg::Output *> & operands)
{
  JLM_ASSERT(operands.size() > 2);
 
  const auto memStateMergeNode = rvsdg::TryGetOwnerNode<rvsdg::SimpleNode>(*operands[2]);
  if (!is<MemoryStateMergeOperation>(memStateMergeNode))
    return false;
 
  for (size_t n = 2; n < operands.size(); n++)
  {
    if (rvsdg::TryGetOwnerNode<rvsdg::SimpleNode>(*operands[n]) != memStateMergeNode)
      return false;
  }
 
  return true;
}
 
static bool
is_store_store_reducible(
    const StoreNonVolatileOperation & store2Op,
    const std::vector<jlm::rvsdg::Output *> & operands)
{
  JLM_ASSERT(operands.size() > 2);
 
  // Try tracing a memory state edge to a previous store
  const auto [store1Node, store1Op] =
      rvsdg::TryGetSimpleNodeAndOptionalOp<StoreNonVolatileOperation>(*operands[2]);
  if (!store1Op)
    return false;
 
  const auto & store1Address = *StoreOperation::AddressInput(*store1Node).origin();
  const auto & store2Address = *operands[0];
 
  // only continue if store1 and store2 have the same address
  if (&llvm::traceOutput(store1Address) != &llvm::traceOutput(store2Address))
    return false;
 
  // Check that all memory state inputs come from store1Node, and have no other users
  for (size_t n = 2; n < operands.size(); n++)
  {
    if (rvsdg::TryGetOwnerNode<rvsdg::SimpleNode>(*operands[n]) != store1Node
        || operands[n]->nusers() != 1)
      return false;
  }
 
  // Check that store2 fully overwrites store1
  const auto & store1Type = store1Op->GetStoredType();
  const auto & store2Type = store2Op.GetStoredType();
  if (GetTypeStoreSize(store2Type) < GetTypeStoreSize(store1Type))
    return false;
 
  return true;
}
 
static bool
is_store_alloca_reducible(const std::vector<jlm::rvsdg::Output *> & operands)
{
  if (operands.size() == 3)
    return false;
 
  const auto allocaNode = rvsdg::TryGetOwnerNode<rvsdg::SimpleNode>(*operands[0]);
  if (!is<AllocaOperation>(allocaNode))
    return false;
 
  std::unordered_set states(std::next(std::next(operands.begin())), operands.end());
  if (states.find(allocaNode->output(1)) == states.end())
    return false;
 
  if (allocaNode->output(1)->nusers() != 1)
    return false;
 
  return true;
}
 
static bool
is_multiple_origin_reducible(const std::vector<jlm::rvsdg::Output *> & operands)
{
  const util::HashSet<rvsdg::Output *> states(std::next(operands.begin(), 2), operands.end());
  return states.Size() != operands.size() - 2;
}
 
static std::vector<jlm::rvsdg::Output *>
perform_store_mux_reduction(
    const StoreNonVolatileOperation & op,
    const std::vector<jlm::rvsdg::Output *> & operands)
{
  const auto memStateMergeNode = rvsdg::TryGetOwnerNode<rvsdg::SimpleNode>(*operands[2]);
  auto memStateMergeOperands = jlm::rvsdg::operands(memStateMergeNode);
 
  auto states = StoreNonVolatileOperation::Create(
      operands[0],
      operands[1],
      memStateMergeOperands,
      op.GetAlignment());
  return { MemoryStateMergeOperation::Create(states) };
}
 
static std::vector<jlm::rvsdg::Output *>
perform_store_store_reduction(
    const StoreNonVolatileOperation & op,
    const std::vector<jlm::rvsdg::Output *> & operands)
{
  JLM_ASSERT(is_store_store_reducible(op, operands));
  const auto storeNode = rvsdg::TryGetOwnerNode<rvsdg::SimpleNode>(*operands[2]);
 
  auto storeops = jlm::rvsdg::operands(storeNode);
  std::vector<jlm::rvsdg::Output *> states(std::next(std::next(storeops.begin())), storeops.end());
  return StoreNonVolatileOperation::Create(operands[0], operands[1], states, op.GetAlignment());
}
 
static std::vector<jlm::rvsdg::Output *>
perform_store_alloca_reduction(
    const StoreNonVolatileOperation & op,
    const std::vector<jlm::rvsdg::Output *> & operands)
{
  auto value = operands[1];
  auto address = operands[0];
  auto alloca_state = rvsdg::TryGetOwnerNode<rvsdg::SimpleNode>(*address)->output(1);
  std::unordered_set<jlm::rvsdg::Output *> states(
      std::next(std::next(operands.begin())),
      operands.end());
 
  auto outputs =
      StoreNonVolatileOperation::Create(address, value, { alloca_state }, op.GetAlignment());
  states.erase(alloca_state);
  states.insert(outputs[0]);
  return { states.begin(), states.end() };
}
 
static std::vector<jlm::rvsdg::Output *>
perform_multiple_origin_reduction(
    const StoreNonVolatileOperation & operation,
    const std::vector<jlm::rvsdg::Output *> & operands)
{
  // FIXME: Unify with the duplicate state removal reduction of the LoadNonVolatile operation
 
  JLM_ASSERT(operands.size() > 2);
  const auto address = operands[0];
  const auto value = operands[1];
 
  std::vector<rvsdg::Output *> newInputStates;
  std::unordered_map<rvsdg::Output *, size_t> stateIndexMap;
  for (size_t n = 2; n < operands.size(); n++)
  {
    auto state = operands[n];
    if (stateIndexMap.find(state) == stateIndexMap.end())
    {
      const size_t resultIndex = newInputStates.size();
      newInputStates.push_back(state);
      stateIndexMap[state] = resultIndex;
    }
  }
 
  const auto storeResults =
      StoreNonVolatileOperation::Create(address, value, newInputStates, operation.GetAlignment());
 
  std::vector<rvsdg::Output *> results(operation.nresults(), nullptr);
  for (size_t n = 2; n < operands.size(); n++)
  {
    auto state = operands[n];
    JLM_ASSERT(stateIndexMap.find(state) != stateIndexMap.end());
    results[n - 2] = storeResults[stateIndexMap[state]];
  }
 
  return results;
}
 
std::optional<std::vector<rvsdg::Output *>>
StoreNonVolatileOperation::NormalizeStoreMux(
    const StoreNonVolatileOperation & operation,
    const std::vector<rvsdg::Output *> & operands)
{
  if (is_store_mux_reducible(operands))
    return perform_store_mux_reduction(operation, operands);
 
  return std::nullopt;
}
 
std::optional<std::vector<rvsdg::Output *>>
StoreNonVolatileOperation::NormalizeStoreStore(
    const StoreNonVolatileOperation & operation,
    const std::vector<rvsdg::Output *> & operands)
{
  if (is_store_store_reducible(operation, operands))
    return perform_store_store_reduction(operation, operands);
 
  return std::nullopt;
}
 
std::optional<std::vector<rvsdg::Output *>>
StoreNonVolatileOperation::NormalizeStoreAlloca(
    const StoreNonVolatileOperation & operation,
    const std::vector<rvsdg::Output *> & operands)
{
  if (is_store_alloca_reducible(operands))
    return perform_store_alloca_reduction(operation, operands);
 
  return std::nullopt;
}
 
std::optional<std::vector<rvsdg::Output *>>
StoreNonVolatileOperation::NormalizeDuplicateStates(
    const StoreNonVolatileOperation & operation,
    const std::vector<rvsdg::Output *> & operands)
{
  if (is_multiple_origin_reducible(operands))
    return perform_multiple_origin_reduction(operation, operands);
 
  return std::nullopt;
}
 
std::optional<std::vector<rvsdg::Output *>>
StoreNonVolatileOperation::NormalizeIOBarrierAllocaAddress(
    const StoreNonVolatileOperation & operation,
    const std::vector<rvsdg::Output *> & operands)
{
  JLM_ASSERT(operands.size() >= 2);
  const auto address = operands[0];
  const auto value = operands[1];
 
  auto [ioBarrierNode, ioBarrierOperation] =
      rvsdg::TryGetSimpleNodeAndOptionalOp<IOBarrierOperation>(*address);
  if (!ioBarrierOperation)
    return std::nullopt;
 
  auto & barredAddress = *IOBarrierOperation::BarredInput(*ioBarrierNode).origin();
  const auto & tracedAddress = llvm::traceOutput(barredAddress);
  if (!rvsdg::IsOwnerNodeOperation<AllocaOperation>(tracedAddress))
    return std::nullopt;
 
  auto & storeNode = CreateNode(
      barredAddress,
      *value,
      { std::next(operands.begin(), 2), operands.end() },
      operation.GetAlignment());
 
  return { outputs(&storeNode) };
}
 
std::optional<std::vector<rvsdg::Output *>>
StoreNonVolatileOperation::normalizeStoreAllocaSingleUser(
    const StoreNonVolatileOperation & operation,
    const std::vector<rvsdg::Output *> & operands)
{
  JLM_ASSERT(operands.size() >= 2);
  const auto & address = *operands[0];
 
  // We cannot(!) use the traced address in this normalization as it might result in the wrong
  // number of users. The address can be routed through a structural node where it has multiple
  // users, but the traced address would still just have a single user.
  if (!rvsdg::IsOwnerNodeOperation<AllocaOperation>(address))
    return std::nullopt;
 
  if (address.nusers() != 1)
    return std::nullopt;
 
  std::vector newMemoryStateResults(operands.begin() + 2, operands.end());
  JLM_ASSERT(newMemoryStateResults.size() == operation.NumMemoryStates());
 
  return newMemoryStateResults;
}
 
StoreVolatileOperation::~StoreVolatileOperation() noexcept = default;
 
bool
StoreVolatileOperation::operator==(const Operation & other) const noexcept
{
  auto operation = dynamic_cast<const StoreVolatileOperation *>(&other);
  return operation && operation->NumMemoryStates() == NumMemoryStates()
      && operation->GetStoredType() == GetStoredType()
      && operation->GetAlignment() == GetAlignment();
}
 
std::string
StoreVolatileOperation::debug_string() const
{
  return "StoreVolatile";
}
 
std::unique_ptr<rvsdg::Operation>
StoreVolatileOperation::copy() const
{
  return std::make_unique<StoreVolatileOperation>(*this);
}
 
}