Index: flang/include/flang/CMakeLists.txt =================================================================== --- flang/include/flang/CMakeLists.txt +++ flang/include/flang/CMakeLists.txt @@ -1,3 +1 @@ -if(LINK_WITH_FIR) - add_subdirectory(Optimizer) -endif() +add_subdirectory(Optimizer) Index: flang/include/flang/Optimizer/CMakeLists.txt =================================================================== --- flang/include/flang/Optimizer/CMakeLists.txt +++ flang/include/flang/Optimizer/CMakeLists.txt @@ -1 +1,2 @@ add_subdirectory(Dialect) +add_subdirectory(Transforms) Index: flang/include/flang/Optimizer/Transforms/CMakeLists.txt =================================================================== --- /dev/null +++ flang/include/flang/Optimizer/Transforms/CMakeLists.txt @@ -0,0 +1,6 @@ + +set(LLVM_TARGET_DEFINITIONS Passes.td) +mlir_tablegen(Passes.h.inc -gen-pass-decls) +add_public_tablegen_target(FIROptTransformsPassIncGen) + +add_mlir_doc(Passes -gen-pass-doc OptimizerTransformPasses ./) Index: flang/include/flang/Optimizer/Transforms/Passes.h =================================================================== --- /dev/null +++ flang/include/flang/Optimizer/Transforms/Passes.h @@ -0,0 +1,63 @@ +//===-- Optimizer/Transforms/Passes.h ---------------------------*- C++ -*-===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +#ifndef OPTIMIZER_TRANSFORMS_PASSES_H +#define OPTIMIZER_TRANSFORMS_PASSES_H + +#include "mlir/Pass/Pass.h" +#include "mlir/Pass/PassRegistry.h" +#include + +namespace mlir { +class BlockAndValueMapping; +class Operation; +class Pass; +class Region; +} // namespace mlir + +namespace fir { + +/// Convert fir.select_type to the standard dialect +std::unique_ptr createControlFlowLoweringPass(); + +/// Effects aware CSE pass +std::unique_ptr createCSEPass(); + +/// Convert FIR loop constructs to the Affine dialect +std::unique_ptr createPromoteToAffinePass(); + +/// Convert `fir.do_loop` and `fir.if` to a CFG. This +/// conversion enables the `createLowerToCFGPass` to transform these to CFG +/// form. +std::unique_ptr createFirToCfgPass(); + +/// A pass to convert the FIR dialect from "Mem-SSA" form to "Reg-SSA" +/// form. This pass is a port of LLVM's mem2reg pass, but modified for the FIR +/// dialect as well as the restructuring of MLIR's representation to present PHI +/// nodes as block arguments. +std::unique_ptr createMemToRegPass(); + +/// This pass will preform inlining on FIR. +std::unique_ptr createInlinerPass(); + +/// Is inlining enabled? Check this before instantiating the pass with +/// createInlinerPass(). +bool inlinerIsEnabled(); +bool canLegallyInline(mlir::Operation *op, mlir::Region *reg, + mlir::BlockAndValueMapping &map); + +inline void registerOptTransformPasses() { +using mlir::Pass; +// declarative passes +#define GEN_PASS_REGISTRATION +#include "flang/Optimizer/Transforms/Passes.h.inc" +} + +} // namespace fir + +#endif // OPTIMIZER_TRANSFORMS_PASSES_H Index: flang/include/flang/Optimizer/Transforms/Passes.td =================================================================== --- /dev/null +++ flang/include/flang/Optimizer/Transforms/Passes.td @@ -0,0 +1,51 @@ +//===-- Passes.td - Transforms pass definition file --------*- tablegen -*-===// +// +// 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 file contains definitions for passes within the Optimizer/Transforms/ +// directory. +// +//===----------------------------------------------------------------------===// + +#ifndef FLANG_OPTIMIZER_TRANSFORMS_PASSES +#define FLANG_OPTIMIZER_TRANSFORMS_PASSES + +include "mlir/Pass/PassBase.td" + +def AffineDialectPromotion : FunctionPass<"promote-to-affine"> { + let summary = "Promotes fir.loop and fir.where to affine.for and affine.if where possible"; + let description = [{ + TODO + }]; + let constructor = "fir::createPromoteToAffinePass()"; +} + +def BasicCSE : FunctionPass<"basic-cse"> { + let summary = "Basic common sub-expression elimination"; + let description = [{ + TODO + }]; + let constructor = "fir::createCSEPass()"; +} + +def ControlFlowLowering : FunctionPass<"lower-control-flow"> { + let summary = "Convert affine dialect, fir.select_type to standard dialect"; + let description = [{ + TODO + }]; + let constructor = "fir::createControlFlowLoweringPass()"; +} + +def CFGConversion : FunctionPass<"cfg-conversion"> { + let summary = "Convert FIR structured control flow ops to CFG ops."; + let description = [{ + TODO + }]; + let constructor = "fir::createFirToCfgPass()"; +} + +#endif // FLANG_OPTIMIZER_TRANSFORMS_PASSES Index: flang/lib/Optimizer/CMakeLists.txt =================================================================== --- flang/lib/Optimizer/CMakeLists.txt +++ flang/lib/Optimizer/CMakeLists.txt @@ -10,8 +10,12 @@ Support/InternalNames.cpp Support/KindMapping.cpp + Transforms/Inliner.cpp + Transforms/RewriteLoop.cpp + DEPENDS FIROpsIncGen + FIROptTransformsPassIncGen ${dialect_libs} LINK_LIBS Index: flang/lib/Optimizer/Transforms/Inliner.cpp =================================================================== --- /dev/null +++ flang/lib/Optimizer/Transforms/Inliner.cpp @@ -0,0 +1,36 @@ +//===-- Inliner.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 +// +//===----------------------------------------------------------------------===// + +#include "flang/Optimizer/Dialect/FIRDialect.h" +#include "flang/Optimizer/Dialect/FIROps.h" +#include "flang/Optimizer/Transforms/Passes.h" +#include "mlir/Transforms/Passes.h" +#include "llvm/Support/CommandLine.h" + +static llvm::cl::opt + enableInliningPass("enable-inlining", + llvm::cl::desc("enable FIR inlining pass"), + llvm::cl::init(false)); + +/// Should we inline the callable `op` into region `reg`? +bool fir::canLegallyInline(mlir::Operation *op, mlir::Region *reg, + mlir::BlockAndValueMapping &map) { + // TODO: this should _not_ just return true. + return true; +} + +/// Should an inlining pass be instantiated? +bool fir::inlinerIsEnabled() { return enableInliningPass; } + +/// Instantiate an inlining pass. NB: If inlining is disabled, the compiler will +/// abort if an inlining pass is instantiated. +std::unique_ptr fir::createInlinerPass() { + if (enableInliningPass) + return mlir::createInlinerPass(); + llvm::report_fatal_error("inlining is disabled"); +} Index: flang/lib/Optimizer/Transforms/PassDetail.h =================================================================== --- /dev/null +++ flang/lib/Optimizer/Transforms/PassDetail.h @@ -0,0 +1,22 @@ +//===- PassDetail.h - Optimizer Transforms Pass class details ---*- C++ -*-===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +#ifndef OPTMIZER_TRANSFORMS_PASSDETAIL_H_ +#define OPTMIZER_TRANSFORMS_PASSDETAIL_H_ + +#include "mlir/Pass/Pass.h" +#include "mlir/Pass/PassRegistry.h" + +namespace fir { + +#define GEN_PASS_CLASSES +#include "flang/Optimizer/Transforms/Passes.h.inc" + +} // namespace fir + +#endif // OPTMIZER_TRANSFORMS_PASSDETAIL_H_ Index: flang/lib/Optimizer/Transforms/RewriteLoop.cpp =================================================================== --- /dev/null +++ flang/lib/Optimizer/Transforms/RewriteLoop.cpp @@ -0,0 +1,294 @@ +//===-- RewriteLoop.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 +// +//===----------------------------------------------------------------------===// + +#include "PassDetail.h" +#include "flang/Optimizer/Dialect/FIRDialect.h" +#include "flang/Optimizer/Dialect/FIROps.h" +#include "flang/Optimizer/Transforms/Passes.h" +#include "mlir/Dialect/Affine/IR/AffineOps.h" +#include "mlir/Dialect/StandardOps/IR/Ops.h" +#include "mlir/Pass/Pass.h" +#include "mlir/Transforms/DialectConversion.h" +#include "llvm/Support/CommandLine.h" + +/// disable FIR to scf dialect conversion +static llvm::cl::opt + disableCfgConversion("disable-cfg-conversion", + llvm::cl::desc("disable FIR to CFG pass"), + llvm::cl::init(false)); + +using namespace fir; + +namespace { + +// Conversion of fir control ops to more primitive control-flow. +// +// FIR loops that cannot be converted to the affine dialect will remain as +// `fir.do_loop` operations. These can be converted to control-flow operations. + +/// Convert `fir.do_loop` to CFG +class CfgLoopConv : public mlir::OpRewritePattern { +public: + using OpRewritePattern::OpRewritePattern; + + mlir::LogicalResult + matchAndRewrite(LoopOp loop, mlir::PatternRewriter &rewriter) const override { + auto loc = loop.getLoc(); + + // Create the start and end blocks that will wrap the LoopOp with an + // initalizer and an end point + auto *initBlock = rewriter.getInsertionBlock(); + auto initPos = rewriter.getInsertionPoint(); + auto *endBlock = rewriter.splitBlock(initBlock, initPos); + + // Split the first LoopOp block in two parts. The part before will be the + // conditional block since it already has the induction variable and + // loop-carried values as arguments. + auto *conditionalBlock = &loop.region().front(); + conditionalBlock->addArgument(rewriter.getIndexType()); + auto *firstBlock = + rewriter.splitBlock(conditionalBlock, conditionalBlock->begin()); + auto *lastBlock = &loop.region().back(); + + // Move the blocks from the LoopOp between initBlock and endBlock + rewriter.inlineRegionBefore(loop.region(), endBlock); + + // Get loop values from the LoopOp + auto low = loop.lowerBound(); + auto high = loop.upperBound(); + assert(low && high && "must be a Value"); + auto step = loop.step(); + + // Initalization block + rewriter.setInsertionPointToEnd(initBlock); + auto diff = rewriter.create(loc, high, low); + auto distance = rewriter.create(loc, diff, step); + auto iters = rewriter.create(loc, distance, step); + + llvm::SmallVector loopOperands; + loopOperands.push_back(low); + auto operands = loop.getIterOperands(); + loopOperands.append(operands.begin(), operands.end()); + loopOperands.push_back(iters); + + // TODO: replace with a command line flag + // onetrip flag determines whether loop should be executed once, before + // conditionals are checked + static const bool onetrip = false; + if (onetrip) + rewriter.create(loc, firstBlock, ArrayRef()); + else + rewriter.create(loc, conditionalBlock, loopOperands); + + // Last loop block + auto *terminator = lastBlock->getTerminator(); + rewriter.setInsertionPointToEnd(lastBlock); + auto iv = conditionalBlock->getArgument(0); + mlir::Value steppedIndex = rewriter.create(loc, iv, step); + assert(steppedIndex && "must be a Value"); + auto lastArg = conditionalBlock->getNumArguments() - 1; + auto itersLeft = conditionalBlock->getArgument(lastArg); + auto one = rewriter.create(loc, 1); + mlir::Value itersMinusOne = + rewriter.create(loc, itersLeft, one); + + llvm::SmallVector loopCarried; + loopCarried.push_back(steppedIndex); + loopCarried.append(terminator->operand_begin(), terminator->operand_end()); + loopCarried.push_back(itersMinusOne); + rewriter.create(loc, conditionalBlock, loopCarried); + rewriter.eraseOp(terminator); + + // Conditional block + rewriter.setInsertionPointToEnd(conditionalBlock); + auto zero = rewriter.create(loc, 0); + auto comparison = + rewriter.create(loc, CmpIPredicate::sgt, itersLeft, zero); + + rewriter.create(loc, comparison, firstBlock, + llvm::ArrayRef(), endBlock, + llvm::ArrayRef()); + + // The result of the loop operation is the values of the condition block + // arguments except the induction variable on the last iteration. + rewriter.replaceOp( + loop, conditionalBlock->getArguments().drop_front().drop_back()); + return success(); + } +}; + +/// Convert `fir.if` to control-flow +class CfgIfConv : public mlir::OpRewritePattern { +public: + using OpRewritePattern::OpRewritePattern; + + mlir::LogicalResult + matchAndRewrite(WhereOp where, + mlir::PatternRewriter &rewriter) const override { + auto loc = where.getLoc(); + + // Split the block containing the 'fir.if' into two parts. The part before + // will contain the condition, the part after will be the continuation + // point. + auto *condBlock = rewriter.getInsertionBlock(); + auto opPosition = rewriter.getInsertionPoint(); + auto *remainingOpsBlock = rewriter.splitBlock(condBlock, opPosition); + mlir::Block *continueBlock; + if (where.getNumResults() == 0) { + continueBlock = remainingOpsBlock; + } else { + continueBlock = + rewriter.createBlock(remainingOpsBlock, where.getResultTypes()); + rewriter.create(loc, remainingOpsBlock); + } + + // Move blocks from the "then" region to the region containing 'fir.if', + // place it before the continuation block, and branch to it. + auto &whereRegion = where.whereRegion(); + auto *whereBlock = &whereRegion.front(); + auto *whereTerminator = whereRegion.back().getTerminator(); + auto whereTerminatorOperands = whereTerminator->getOperands(); + rewriter.setInsertionPointToEnd(&whereRegion.back()); + rewriter.create(loc, continueBlock, + whereTerminatorOperands); + rewriter.eraseOp(whereTerminator); + rewriter.inlineRegionBefore(whereRegion, continueBlock); + + // Move blocks from the "else" region (if present) to the region containing + // 'fir.if', place it before the continuation block and branch to it. It + // will be placed after the "then" regions. + auto *otherwiseBlock = continueBlock; + auto &otherwiseRegion = where.otherRegion(); + if (!otherwiseRegion.empty()) { + otherwiseBlock = &otherwiseRegion.front(); + auto *otherwiseTerm = otherwiseRegion.back().getTerminator(); + auto otherwiseTermOperands = otherwiseTerm->getOperands(); + rewriter.setInsertionPointToEnd(&otherwiseRegion.back()); + rewriter.create(loc, continueBlock, + otherwiseTermOperands); + rewriter.eraseOp(otherwiseTerm); + rewriter.inlineRegionBefore(otherwiseRegion, continueBlock); + } + + rewriter.setInsertionPointToEnd(condBlock); + rewriter.create( + loc, where.condition(), whereBlock, llvm::ArrayRef(), + otherwiseBlock, llvm::ArrayRef()); + rewriter.replaceOp(where, continueBlock->getArguments()); + return success(); + } +}; + +/// Convert `fir.iter_while` to control-flow. +class CfgIterWhileConv : public mlir::OpRewritePattern { +public: + using OpRewritePattern::OpRewritePattern; + + mlir::LogicalResult + matchAndRewrite(fir::IterWhileOp whileOp, + mlir::PatternRewriter &rewriter) const override { + auto loc = whileOp.getLoc(); + + // Start by splitting the block containing the 'fir.do_loop' into two parts. + // The part before will get the init code, the part after will be the end + // point. + auto *initBlock = rewriter.getInsertionBlock(); + auto initPosition = rewriter.getInsertionPoint(); + auto *endBlock = rewriter.splitBlock(initBlock, initPosition); + + // Use the first block of the loop body as the condition block since it is + // the block that has the induction variable and loop-carried values as + // arguments. Split out all operations from the first block into a new + // block. Move all body blocks from the loop body region to the region + // containing the loop. + auto *conditionBlock = &whileOp.region().front(); + auto *firstBodyBlock = + rewriter.splitBlock(conditionBlock, conditionBlock->begin()); + auto *lastBodyBlock = &whileOp.region().back(); + rewriter.inlineRegionBefore(whileOp.region(), endBlock); + auto iv = conditionBlock->getArgument(0); + auto iterateVar = conditionBlock->getArgument(1); + + // Append the induction variable stepping logic to the last body block and + // branch back to the condition block. Loop-carried values are taken from + // operands of the loop terminator. + auto *terminator = lastBodyBlock->getTerminator(); + rewriter.setInsertionPointToEnd(lastBodyBlock); + auto step = whileOp.step(); + mlir::Value stepped = rewriter.create(loc, iv, step); + assert(stepped && "must be a Value"); + + llvm::SmallVector loopCarried; + loopCarried.push_back(stepped); + loopCarried.append(terminator->operand_begin(), terminator->operand_end()); + rewriter.create(loc, conditionBlock, loopCarried); + rewriter.eraseOp(terminator); + + // Compute loop bounds before branching to the condition. + rewriter.setInsertionPointToEnd(initBlock); + auto lowerBound = whileOp.lowerBound(); + auto upperBound = whileOp.upperBound(); + assert(lowerBound && upperBound && "must be a Value"); + + // The initial values of loop-carried values is obtained from the operands + // of the loop operation. + llvm::SmallVector destOperands; + destOperands.push_back(lowerBound); + auto iterOperands = whileOp.getIterOperands(); + destOperands.append(iterOperands.begin(), iterOperands.end()); + rewriter.create(loc, conditionBlock, destOperands); + + // With the body block done, we can fill in the condition block. + rewriter.setInsertionPointToEnd(conditionBlock); + auto comp1 = + rewriter.create(loc, CmpIPredicate::slt, iv, upperBound); + // Remember to AND in the early-exit bool. + auto comparison = rewriter.create(loc, comp1, iterateVar); + rewriter.create(loc, comparison, firstBodyBlock, + llvm::ArrayRef(), endBlock, + llvm::ArrayRef()); + // The result of the loop operation is the values of the condition block + // arguments except the induction variable on the last iteration. + rewriter.replaceOp(whileOp, conditionBlock->getArguments().drop_front()); + return success(); + } +}; + +/// Convert FIR structured control flow ops to CFG ops. +class CfgConversion : public CFGConversionBase { +public: + void runOnFunction() override { + if (disableCfgConversion) + return; + + auto *context = &getContext(); + mlir::OwningRewritePatternList patterns; + patterns.insert(context); + mlir::ConversionTarget target(*context); + target.addLegalDialect(); + + // apply the patterns + target.addIllegalOp(); + target.markUnknownOpDynamicallyLegal([](Operation*) { return true; }); + if (mlir::failed(mlir::applyPartialConversion(getFunction(), target, + patterns))) { + mlir::emitError(mlir::UnknownLoc::get(context), + "error in converting to CFG\n"); + signalPassFailure(); + } + } +}; +} // namespace + +/// Convert FIR's structured control flow ops to CFG ops. This +/// conversion enables the `createLowerToCFGPass` to transform these to CFG +/// form. +std::unique_ptr fir::createFirToCfgPass() { + return std::make_unique(); +}