blob: af8ae92fa8b3551289f0a49facacb5e8a8a932ec [file]
// Copyright 2021 The IREE Authors
//
// Licensed 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
#include "iree/compiler/Dialect/Util/Analysis/Constant/ConstExpr.h"
#include "iree/compiler/Dialect/Util/Analysis/Constant/OpOracle.h"
#include "iree/compiler/Dialect/Util/IR/UtilOps.h"
#include "iree/compiler/Dialect/Util/IR/UtilTypes.h"
#include "iree/compiler/Dialect/Util/Transforms/Passes.h"
#include "iree/compiler/Utils/StringUtils.h"
#include "llvm/Support/Debug.h"
#include "mlir/Analysis/SliceAnalysis.h"
#include "mlir/IR/Builders.h"
#include "mlir/IR/IRMapping.h"
#include "mlir/IR/SymbolTable.h"
#define DEBUG_TYPE "iree-constexpr"
namespace mlir::iree_compiler::IREE::Util {
#define GEN_PASS_DEF_HOISTINTOGLOBALSPASS
#include "iree/compiler/Dialect/Util/Transforms/Passes.h.inc"
namespace {
static llvm::cl::opt<std::string> clPrintDotGraphToFile(
"iree-util-hoist-into-globals-print-constexpr-dotgraph-to",
llvm::cl::desc(
"Prints a dot graph representing the const-expr analysis. The red "
"nodes represent roots and the green nodes represent hoisted values."),
llvm::cl::value_desc("filename"));
// Maps an original value in the program to the symbol name of a global.
using HoistedValueMap = llvm::DenseMap<Value, GlobalOp>;
static std::string getHoistedName(Type type) {
std::string str;
llvm::raw_string_ostream os(str);
os << "__hoisted_";
type.print(os);
str = sanitizeSymbolName(str);
if (str.substr(str.size() - 1) == "_")
str = str.substr(0, str.size() - 1); // strip trailing _
return str;
}
// Hoist expressions into globals. It is not expected that such a greedy
// algorithm is great, but it is simple. Naive use of this algorithm very likely
// favors programs that consume more memory at runtime than is strictly
// necessary. Either this algorithm can be made smarter or a follow-on pass
// can sink globals into the program where it is profitable to reduce
// working set size.
class HoistIntoGlobalsPass
: public impl::HoistIntoGlobalsPassBase<HoistIntoGlobalsPass> {
public:
using Base::Base;
void getDependentDialects(DialectRegistry &registry) const override {
registerConstExprDependentDialects(registry);
if (this->registerDependentDialectsFn) {
(*registerDependentDialectsFn)(registry);
}
}
HoistIntoGlobalsPass(const ExprHoistingOptions &options)
: Base(),
registerDependentDialectsFn(options.registerDependentDialectsFn) {
this->maxSizeIncreaseThreshold.setValue(options.maxSizeIncreaseThreshold);
}
void runOnOperation() override {
SymbolTable moduleSymbols(getOperation());
const auto &constExprs = getAnalysis<ConstExprAnalysis>();
ConstExprHoistingPolicy policy(constExprs, this->maxSizeIncreaseThreshold);
policy.initialize();
// Print analysis dot graph if requested.
if (!clPrintDotGraphToFile.empty()) {
std::error_code ec;
llvm::raw_fd_ostream file(clPrintDotGraphToFile, ec);
if (ec) {
getOperation().emitError()
<< "failed to open file for printing dot graph: " << ec.message();
return signalPassFailure();
}
policy.printDotGraph(file);
file.close();
}
// Maps original values to newly materialized values.
HoistedValueMap hoistedMap;
// Walk all operations in the program and hoist any escapes from
// const-expr values into globals. Note that we must walk the const-exprs
// in topological order so that corresponding initializers will be created
// in order without depending on globals that have not been initialized
// yet.
for (auto funcOp : getOperation().getOps<FunctionOpInterface>()) {
// Ignore initializers.
if (isa<IREE::Util::InitializerOpInterface>(funcOp.getOperation()))
continue;
auto walkRes = funcOp.walk<WalkOrder::PreOrder>([&](Operation *iterOp) {
// We only want to look at const-expr ops (non roots) since they may
// have interesting escapes. Early exit here for efficiency.
auto *iterInfo = constExprs.lookup(iterOp);
if (!iterInfo)
return WalkResult::advance();
for (Value constExprResult : iterOp->getResults()) {
auto *resultInfo = constExprs.lookup(constExprResult);
assert(resultInfo && "must have const-expr info");
if (policy.getDecision(resultInfo)->getOutcome() !=
ConstExprHoistingPolicy::ENABLE_HOIST) {
continue;
}
if (failed(hoistConstExpr(constExprResult, hoistedMap, moduleSymbols,
constExprs))) {
return WalkResult::interrupt();
}
}
return WalkResult::advance();
});
if (walkRes.wasInterrupted())
return signalPassFailure();
}
// Apply any remaining RAUW cleanups. We have to do these at the cleanup
// phase since modifying the source program can invalidate the analysis.
// Up to this point, we have only been cloning.
OpBuilder builder(&getContext());
for (auto [originalValue, globalOp] : hoistedMap) {
builder.setInsertionPointAfterValue(originalValue);
auto loadOp = globalOp.createLoadOp(globalOp->getLoc(), builder);
if (!originalValue.getDefiningOp()
->getParentOfType<IREE::Util::InitializerOpInterface>()) {
loadOp.setGlobalImmutable(true);
}
Value loadedValue = loadOp.getLoadedGlobalValue();
// Call user hook to cast back to the original type.
if (auto hoistableType = dyn_cast<IREE::Util::HoistableTypeInterface>(
originalValue.getType())) {
loadedValue = hoistableType.decodeStorageType(
builder, loadedValue.getLoc(), originalValue.getType(),
loadedValue);
}
if (loadedValue.getType() != originalValue.getType()) {
getOperation().emitError()
<< "Unresolved conflict between casted global of type "
<< loadedValue.getType() << " and original type "
<< originalValue.getType();
return signalPassFailure();
}
originalValue.replaceAllUsesWith(loadedValue);
}
cleanupDeadOps(constExprs);
}
Operation *getTopLevelOp(Operation *childOp) {
auto *moduleBlock = getOperation().getBody();
auto *op = childOp;
while (op->getBlock() != moduleBlock)
op = op->getParentOp();
return op;
}
LogicalResult hoistConstExpr(Value originalValue, HoistedValueMap &hoistedMap,
SymbolTable &moduleSymbols,
const ConstExprAnalysis &constExprs) {
IREE::Util::GlobalOp existingGlobal = hoistedMap.lookup(originalValue);
if (existingGlobal)
return success();
// Gather any dialect attributes we may need to preserve.
auto *topLevelOp = getTopLevelOp(originalValue.getDefiningOp());
NamedAttrList dialectAttrs;
IREE::Util::HoistableAttrInterface::gatherHoistableAttrs(topLevelOp,
dialectAttrs);
// No existing mapping - create a new global.
OpBuilder moduleBuilder(topLevelOp);
auto initializerOp =
moduleBuilder.create<IREE::Util::InitializerOp>(originalValue.getLoc());
initializerOp->setDialectAttrs(dialectAttrs);
auto initializerBuilder =
OpBuilder::atBlockEnd(initializerOp.addEntryBlock());
moduleBuilder.setInsertionPoint(initializerOp);
if (failed(cloneConstExprInto(initializerOp.getLoc(), moduleBuilder,
initializerBuilder, originalValue,
dialectAttrs, hoistedMap, moduleSymbols,
constExprs))) {
return failure();
}
existingGlobal = hoistedMap.lookup(originalValue);
(void)existingGlobal;
assert(existingGlobal &&
"hoisting const-expr should have mapped a global for the requested "
"value");
return success();
}
void
cloneProducerTreeInto(OpBuilder &initializerBuilder,
const ConstExprAnalysis::ConstValueInfo *producerInfo,
HoistedValueMap &hoistedMap, IRMapping &cloneMapping,
const ConstExprAnalysis &constExprs) {
if (cloneMapping.contains(producerInfo->constValue))
return;
// We either have a global associated already or we need to traverse
// down and materialize producers.
IREE::Util::GlobalOp existingGlobal =
hoistedMap.lookup(producerInfo->constValue);
if (existingGlobal) {
Value newGlobal =
existingGlobal
.createLoadOp(existingGlobal.getLoc(), initializerBuilder)
.getLoadedGlobalValue();
// Call user hook to cast back to the original type.
if (auto hoistableType = dyn_cast<IREE::Util::HoistableTypeInterface>(
producerInfo->constValue.getType())) {
newGlobal = hoistableType.decodeStorageType(
initializerBuilder, newGlobal.getLoc(),
producerInfo->constValue.getType(), newGlobal);
}
cloneMapping.map(producerInfo->constValue, newGlobal);
return;
}
// Materialize all producers recursively.
for (auto *producerInfo : producerInfo->producers) {
cloneProducerTreeInto(initializerBuilder, producerInfo, hoistedMap,
cloneMapping, constExprs);
}
// And clone the requested op.
Operation *sourceOp = producerInfo->constValue.getDefiningOp();
assert(sourceOp && "must have defining op for const-expr values");
LLVM_DEBUG({
llvm::dbgs() << "[HoistIntoGlobals] + clone op: ";
sourceOp->print(llvm::dbgs(), constExprs.getAsmState());
llvm::dbgs() << "\n";
});
Operation *clonedOp = sourceOp->clone(cloneMapping);
initializerBuilder.insert(clonedOp);
}
// Clones the const expr tree rooted at `constExprValue` into the given
// initializer, noting any new hoisted value mappings that result. At
// a minimum, a mapping will be created for the requested value.
LogicalResult cloneConstExprInto(Location loc, OpBuilder &moduleBuilder,
OpBuilder &initializerBuilder,
Value constExprValue,
NamedAttrList dialectAttrs,
HoistedValueMap &hoistedMap,
SymbolTable &moduleSymbols,
const ConstExprAnalysis &constExprs) {
// Do a depth first traversal of the producers, emitting them in a valid
// def-use order.
Operation *rootOp = constExprValue.getDefiningOp();
assert(rootOp && "const-expr value should have a defining op");
auto *rootInfo = constExprs.lookup(rootOp);
assert(rootInfo && "must have const-value-info for const-expr root op");
// Clone the whole tree as needed.
IRMapping cloneMapping;
cloneProducerTreeInto(initializerBuilder, rootInfo, hoistedMap,
cloneMapping, constExprs);
// And for each result, create a global and store into it.
for (Value origResult : rootOp->getResults()) {
Value clonedResult = cloneMapping.lookup(origResult);
Type globalType = origResult.getType();
// If the original type is registered as hoistable, invoke the interface
// functions for setting the preferred storage type.
auto hoistableType =
dyn_cast<IREE::Util::HoistableTypeInterface>(globalType);
if (hoistableType) {
// Allow the storage type of the global to differ from the local type.
globalType = hoistableType.getPreferredStorageType();
}
auto globalOp = moduleBuilder.create<IREE::Util::GlobalOp>(
loc, getHoistedName(globalType), false, globalType);
moduleSymbols.insert(globalOp);
SymbolTable::setSymbolVisibility(globalOp,
SymbolTable::Visibility::Private);
globalOp->setDialectAttrs(dialectAttrs);
// Save the mapping for the future.
hoistedMap[origResult] = globalOp;
// And store into it.
LLVM_DEBUG({
llvm::dbgs() << "[HoistIntoGlobals] + create global @"
<< globalOp.getSymName() << " = ";
clonedResult.print(llvm::dbgs());
llvm::dbgs() << "\n";
});
if (hoistableType) {
// Allow casting to the global type if it differs from the local type.
clonedResult = hoistableType.encodeStorageType(
initializerBuilder, clonedResult.getLoc(), globalType,
clonedResult);
}
if (clonedResult.getType() != globalType) {
return globalOp.emitError()
<< "unresolved conflict between global of type " << globalType
<< " and stored type " << clonedResult.getType();
}
globalOp.createStoreOp(loc, clonedResult, initializerBuilder);
}
initializerBuilder.create<IREE::Util::ReturnOp>(loc);
return success();
}
void cleanupDeadOps(const ConstExprAnalysis &constExprs) {
llvm::DenseSet<Operation *> allOps;
constExprs.populateConstExprOperations(allOps);
// Since we are mutating the const-expr ops, the ConstExprAnalysis will no
// longer be valid after this point.
SmallVector<Operation *> worklist;
worklist.reserve(allOps.size());
bool madeChanges = true;
while (madeChanges) {
madeChanges = false;
// Prepare worklist.
worklist.clear();
worklist.append(allOps.begin(), allOps.end());
for (Operation *checkOp : worklist) {
if (checkOp->use_empty()) {
// Bingo.
LLVM_DEBUG({
llvm::dbgs() << "[HoistIntoGlobals] erase dead op: ";
checkOp->print(llvm::dbgs(), constExprs.getAsmState());
llvm::dbgs() << "\n";
});
madeChanges = true;
allOps.erase(checkOp);
checkOp->erase();
}
}
}
}
private:
const std::optional<ExprHoistingOptions::RegisterDialectsFn>
registerDependentDialectsFn;
};
} // namespace
std::unique_ptr<Pass>
createHoistIntoGlobalsPass(const ExprHoistingOptions &options) {
return std::make_unique<HoistIntoGlobalsPass>(options);
}
} // namespace mlir::iree_compiler::IREE::Util