blob: a399820a1a3933e540887a7851d09b28df129894 [file]
//===- AllocationPlacement.cpp --------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This pass decides, for each array allocation in a function, whether it should
// live on the stack (fir.alloca) or on the heap (fir.allocmem), and rewrites it
// accordingly. The decision is delegated to the policy in
// flang/Optimizer/Support/AllocationPolicy.h. Two rewrite engines are reused:
// - stack-to-heap uses fir::replaceAllocas (MemoryUtils);
// - heap-to-stack reuses the StackArrays analysis and rewrite, which only
// stackifies fir.allocmem that are provably freed on all paths.
//
//===----------------------------------------------------------------------===//
#include "StackArrays.h"
#include "flang/Optimizer/Dialect/FIRAttr.h"
#include "flang/Optimizer/Dialect/FIRDialect.h"
#include "flang/Optimizer/Dialect/FIROps.h"
#include "flang/Optimizer/Dialect/FIROpsSupport.h"
#include "flang/Optimizer/Dialect/FIRType.h"
#include "flang/Optimizer/Dialect/Support/FIRContext.h"
#include "flang/Optimizer/Support/AllocationPolicy.h"
#include "flang/Optimizer/Support/DataLayout.h"
#include "flang/Optimizer/Transforms/MemoryUtils.h"
#include "flang/Optimizer/Transforms/Passes.h"
#include "mlir/Dialect/Arith/IR/Arith.h"
#include "mlir/Dialect/DLTI/DLTI.h"
#include "mlir/Dialect/Func/IR/FuncOps.h"
#include "mlir/Dialect/LLVMIR/LLVMDialect.h"
#include "mlir/IR/Diagnostics.h"
#include "mlir/Pass/Pass.h"
#include "mlir/Transforms/GreedyPatternRewriteDriver.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/Debug.h"
#include <optional>
namespace fir {
#define GEN_PASS_DEF_ALLOCATIONPLACEMENT
#include "flang/Optimizer/Transforms/Passes.h.inc"
} // namespace fir
#define DEBUG_TYPE "allocation-placement"
namespace {
/// Return true if the allocation is a compiler temporary, i.e. it has no
/// uniqued name (user variables always carry one).
static bool isTemporaryAllocation(mlir::Operation *op) {
std::optional<llvm::StringRef> uniqName;
if (auto alloca = mlir::dyn_cast<fir::AllocaOp>(op))
uniqName = alloca.getUniqName();
else if (auto allocmem = mlir::dyn_cast<fir::AllocMemOp>(op))
uniqName = allocmem.getUniqName();
return !uniqName || uniqName->empty();
}
/// Return the constant byte size of an array allocation, or std::nullopt if it
/// is dynamic or cannot be determined.
static std::optional<std::int64_t>
getConstantByteSize(mlir::Operation *op,
const std::optional<mlir::DataLayout> &dl,
const std::optional<fir::KindMapping> &kindMap) {
if (!dl || !kindMap)
return std::nullopt;
if (auto alloca = mlir::dyn_cast<fir::AllocaOp>(op))
return fir::getAllocaByteSize(alloca, *dl, *kindMap);
if (auto allocmem = mlir::dyn_cast<fir::AllocMemOp>(op)) {
if (allocmem.hasLenParams() || allocmem.hasShapeOperands())
return std::nullopt;
if (auto sizeAndAlignment = fir::getTypeSizeAndAlignment(
op->getLoc(), allocmem.getAllocatedType(), *dl, *kindMap))
return static_cast<std::int64_t>(sizeAndAlignment->first);
}
return std::nullopt;
}
/// Replacement generator used for stack-to-heap conversions (fir.alloca ->
/// fir.allocmem).
static mlir::Value genAllocmem(mlir::OpBuilder &builder, fir::AllocaOp alloca,
bool /*deallocPointsDominateAlloc*/) {
fir::AllocMemOp heap = fir::createAllocMemFromAlloca(builder, alloca);
LLVM_DEBUG(llvm::dbgs() << "allocation placement: replaced " << alloca
<< " with " << heap << '\n');
return heap;
}
static void genFreemem(mlir::Location loc, mlir::OpBuilder &builder,
mlir::Value allocmem) {
[[maybe_unused]] auto free = fir::FreeMemOp::create(builder, loc, allocmem);
LLVM_DEBUG(llvm::dbgs() << "allocation placement: add free " << free
<< " for " << allocmem << '\n');
}
[[maybe_unused]] static llvm::StringRef
placementName(fir::AllocationPlacement placement) {
switch (placement) {
case fir::AllocationPlacement::Stack:
return "stack";
case fir::AllocationPlacement::Heap:
return "heap";
case fir::AllocationPlacement::Leave:
return "leave";
}
return "?";
}
/// Placement made by the passes that legacy mode emulates: the stack-arrays
/// pass under -fstack-arrays, and the memory-allocation-opt pass otherwise.
static fir::AllocationPlacement
decideLegacyPlacement(const fir::AllocationInfo &info, bool stackArrays,
bool dynamicArrayOnHeap) {
using P = fir::AllocationPlacement;
// Character expression buffers retain their historical stack storage, unless
// -fdynamic-heap-array asks for runtime-sized allocations to be on the heap,
// which the memory-allocation-opt pass applied to them.
if (fir::isCharacterTemporary(info))
return !stackArrays && dynamicArrayOnHeap && info.isDynamic ? P::Leave
: P::Stack;
if (stackArrays)
return info.isCurrentlyOnStack || fir::isInOffloadRegion(info.context)
? P::Leave
: P::Stack;
return info.isCurrentlyOnStack && dynamicArrayOnHeap && info.isDynamic
? P::Heap
: P::Leave;
}
/// Return true if \p placement leaves the allocation on the stack.
static bool endsUpOnStack(fir::AllocationPlacement placement,
bool isCurrentlyOnStack) {
return placement == fir::AllocationPlacement::Stack ||
(placement == fir::AllocationPlacement::Leave && isCurrentlyOnStack);
}
class AllocationPlacementPass
: public fir::impl::AllocationPlacementBase<AllocationPlacementPass> {
public:
AllocationPlacementPass() = default;
AllocationPlacementPass(const AllocationPlacementPass &pass)
: fir::impl::AllocationPlacementBase<AllocationPlacementPass>(pass),
placementHook(pass.placementHook) {}
AllocationPlacementPass(fir::AllocationPlacementOptions options)
: fir::impl::AllocationPlacementBase<AllocationPlacementPass>(
std::move(options)) {}
AllocationPlacementPass(fir::AllocationPlacementOptions options,
fir::AllocationPlacementHook hook)
: fir::impl::AllocationPlacementBase<AllocationPlacementPass>(
std::move(options)),
placementHook(std::move(hook)) {}
void runOnOperation() override;
private:
fir::AllocationPlacementHook placementHook;
};
void AllocationPlacementPass::runOnOperation() {
mlir::func::FuncOp func = getOperation();
if (func.empty())
return;
// Start from the policy in effect for the function, which is its own if it
// has one (device procedures do) and the module one otherwise. A pass option
// overrides it only where it was set explicitly.
fir::AllocationPolicy basePolicy = fir::getAllocationPolicy(func);
fir::overrideIfExplicitlySet(basePolicy.stackArrays, stackArrays);
fir::overrideIfExplicitlySet(basePolicy.smallArrayThresholdBytes,
smallArrayThresholdBytes);
fir::overrideIfExplicitlySet(basePolicy.totalStackLimitBytes,
totalStackLimitBytes);
// In legacy mode, a function that opted out of -fstack-arrays in its own
// policy (device code, where the stack is tiny) is handled as if
// -fstack-arrays was not set, so -fdynamic-heap-array applies to it.
if (legacy)
if (std::optional<fir::AllocationPolicy> localPolicy =
fir::getLocalAllocationPolicy(func))
if (!localPolicy->stackArrays)
basePolicy.stackArrays = false;
auto module = func->getParentOfType<mlir::ModuleOp>();
std::optional<mlir::DataLayout> dl =
module ? fir::support::getOrSetMLIRDataLayout(
module, /*allowDefaultLayout=*/false)
: std::nullopt;
std::optional<fir::KindMapping> kindMap;
if (module)
kindMap = fir::getKindMapping(module);
// Walk allocations in deterministic program order, maintaining the running
// per-function stack budget while collecting the conversions to perform.
std::size_t stackBytesUsed = 0;
llvm::DenseSet<mlir::Operation *> allocasToHeap;
llvm::SmallVector<mlir::Operation *> allocmemsToStack;
func.walk([&](mlir::Operation *op) {
auto alloca = mlir::dyn_cast<fir::AllocaOp>(op);
auto allocmem = mlir::dyn_cast<fir::AllocMemOp>(op);
if (!alloca && !allocmem)
return;
if (alloca) {
// Do not touch to fir.alloca that must stay fir.alloca (e.g.
// the temporary alloca for array function results that will
// later be promoted to hidden arguments).
auto attr = alloca->getAttrOfType<fir::MustBeStackAttr>(
fir::MustBeStackAttr::getAttrName());
if (attr && attr.getValue())
return;
}
// Arrays are placed in both directions. Scalar characters are only moved
// from the heap to the stack, when the shared analysis can prove that their
// stack storage is safely reclaimed. Character expression buffers retain
// their historical preference for stack storage independently of the array
// size policy (see fir::isCharacterTemporary). Scalar allocas are left
// alone, except that, like the memory-allocation-opt pass, legacy mode may
// move any allocation with a runtime size to the heap.
mlir::Type inTy = alloca ? alloca.getInType() : allocmem.getAllocatedType();
if (!mlir::isa<fir::SequenceType>(inTy) &&
!(allocmem && fir::isStackArraysCandidateType(inTy)) &&
!(legacy && alloca && alloca.isDynamic()))
return;
fir::AllocationInfo info;
info.op = op;
info.context = op;
info.isCurrentlyOnStack = static_cast<bool>(alloca);
info.isTemporary = isTemporaryAllocation(op);
info.isDynamic =
alloca ? alloca.isDynamic()
: (allocmem.hasLenParams() || allocmem.hasShapeOperands());
info.byteSize = getConstantByteSize(op, dl, kindMap);
info.alignment = alloca ? alloca.getAlignment() : allocmem.getAlignment();
// A hook, if provided, fully overrides the default policy; it may delegate
// back to decideAllocationPlacement after adjusting the policy.
fir::AllocationPlacement placement;
if (placementHook)
placement = placementHook(info, basePolicy, stackBytesUsed);
else if (legacy)
placement = decideLegacyPlacement(info, basePolicy.stackArrays,
dynamicArrayOnHeap);
else
placement =
fir::decideAllocationPlacement(info, basePolicy, stackBytesUsed);
// Account for the decision in the running stack budget, with the same
// figure the decision used (size plus worst-case alignment padding).
if (endsUpOnStack(placement, info.isCurrentlyOnStack))
if (std::optional<std::size_t> bytes = fir::stackBytesNeeded(info))
stackBytesUsed += *bytes;
LLVM_DEBUG({
llvm::dbgs() << "allocation-placement: "
<< (info.isCurrentlyOnStack ? "alloca" : "allocmem") << " "
<< (info.isTemporary ? "temp" : "user") << " ";
if (info.isDynamic)
llvm::dbgs() << "dynamic";
else if (info.byteSize)
llvm::dbgs() << *info.byteSize << "B";
else
llvm::dbgs() << "unknown-size";
llvm::dbgs() << " -> " << placementName(placement) << "\n";
});
if (alloca && placement == fir::AllocationPlacement::Heap)
allocasToHeap.insert(op);
else if (allocmem && placement == fir::AllocationPlacement::Stack)
allocmemsToStack.push_back(op);
});
// Analysis of which fir.allocmem can be safely moved to the stack, and
// where. It is only needed, and only paid for, when some fir.allocmem should
// move to the stack.
const fir::StackArraysAnalysisWrapper::AllocMemMap *candidateOps = nullptr;
if (!allocmemsToStack.empty()) {
auto &analysis = getAnalysis<fir::StackArraysAnalysisWrapper>();
candidateOps = analysis.getCandidateOps(func);
if (!candidateOps) {
signalPassFailure();
return;
}
llvm::erase_if(allocmemsToStack, [&](mlir::Operation *op) {
return !candidateOps->contains(op);
});
}
LLVM_DEBUG(llvm::dbgs() << "allocation-placement: " << func.getSymName()
<< ": " << allocasToHeap.size() << " stack->heap, "
<< allocmemsToStack.size() << " heap->stack, "
<< stackBytesUsed << " stack bytes used\n");
// Heap-to-stack: only provably-safe candidates are converted.
if (!allocmemsToStack.empty()) {
mlir::MLIRContext &context = getContext();
mlir::RewritePatternSet patterns(&context);
mlir::GreedyRewriteConfig config;
// Prevent the pattern driver from merging blocks; otherwise use the default
// configuration (folding on) as the legacy stack-arrays pass did.
config.setRegionSimplificationLevel(
mlir::GreedySimplifyRegionLevel::Disabled);
patterns.insert<fir::AllocMemConversion>(&context, *candidateOps, dl,
kindMap);
if (mlir::failed(mlir::applyOpPatternsGreedily(
allocmemsToStack, std::move(patterns), config))) {
mlir::emitError(func->getLoc(),
"error in allocation placement (heap to stack)\n");
signalPassFailure();
return;
}
}
// Stack-to-heap.
if (!allocasToHeap.empty()) {
mlir::IRRewriter rewriter(&getContext());
auto mustReplace = [&](fir::AllocaOp alloca) {
return allocasToHeap.contains(alloca.getOperation());
};
fir::replaceAllocas(rewriter, func.getOperation(), mustReplace, genAllocmem,
genFreemem);
}
}
} // namespace
std::unique_ptr<mlir::Pass>
fir::createAllocationPlacement(const fir::AllocationPlacementOptions &options,
fir::AllocationPlacementHook placementHook) {
return std::make_unique<AllocationPlacementPass>(options,
std::move(placementHook));
}