LoopInvariantCodeMotion.cpp File Reference

#include "flang/Optimizer/Analysis/AliasAnalysis.h"
#include "flang/Optimizer/Dialect/FIROperationMoveOpInterface.h"
#include "flang/Optimizer/Dialect/FIROpsSupport.h"
#include "flang/Optimizer/Dialect/FortranVariableInterface.h"
#include "flang/Optimizer/HLFIR/HLFIROps.h"
#include "flang/Optimizer/Support/Utils.h"
#include "flang/Optimizer/Transforms/Passes.h"
#include "mlir/Dialect/OpenACC/OpenACCUtils.h"
#include "mlir/Interfaces/LoopLikeInterface.h"
#include "mlir/Pass/Pass.h"
#include "mlir/Transforms/LoopInvariantCodeMotionUtils.h"
#include "llvm/ADT/TypeSwitch.h"
#include "llvm/Support/DebugLog.h"
#include <optional>
#include <utility>
#include "flang/Optimizer/Transforms/Passes.h.inc"

Namespaces
namespace	fir

Macros
#define	GEN_PASS_DEF_LOOPINVARIANTCODEMOTION
#define	DEBUG_TYPE   "flang-licm"

Functions
firAliasAnalysis	enableSourceCache ()
aliasAnalysis	addAnalysisImplementation (std::move(firAliasAnalysis))
	if (!onlyInside.empty()) scopeOpName.emplace(onlyInside
&	getContext ())
function	walk ([&](LoopLikeOpInterface loopLike) { if(scopeOpName) { Operation *scope=loopLike->getParentOp();while(scope !=function &&scope->getName() != *scopeOpName) scope=scope->getParentOp();if(scope->getName() != *scopeOpName) { LDBG()<< "Skipping loop-like without "<< *scopeOpName<< " parent";return;} } if(!fir::canMoveOutOf(loopLike, nullptr)) { LDBG()<< "Cannot hoist anything out of loop operation: ";LDBG_OS([&](llvm::raw_ostream &os) { loopLike->print(os, OpPrintingFlags().skipRegions());});return;} Operation *parentOp=loopLike->getParentOp();if(!parentOp) { LDBG()<< "Skipping top-level loop-like operation?";return;} else if(!fir::canMoveFromDescendant(parentOp, loopLike, nullptr)) { LDBG()<< "Cannot hoist anything into operation: ";LDBG_OS([&](llvm::raw_ostream &os) { parentOp->print(os, OpPrintingFlags().skipRegions());});return;} auto isDefinedOutsideRegion=[&](Value value, Region *) { return loopLike.isDefinedOutsideOfLoop(value);};auto canMoveOutOfOp=[&](Operation *regionOwner, Operation *candidate) { if(!fir::canMoveOutOf(regionOwner, candidate)) return false;bool blocked=false;candidate->walk([&](Operation *nested) { if(nested !=candidate &&!fir::canMoveOutOf(regionOwner, nested)) blocked=true;return blocked ? WalkResult::interrupt() :WalkResult::advance();});return !blocked;};auto canMoveOutOfLoop=[&](Operation *op) { if(!canMoveOutOfOp(loopLike, op)) { LDBG()<< "Cannot hoist "<< *op<< " out of the loop";return false;} if(!fir::canMoveFromDescendant(parentOp, loopLike, op)) { LDBG()<< "Cannot hoist "<< *op<< " into the parent of the loop";return false;} return true;};auto moveOutOfRegion=[&](Operation *op, Region *) { loopLike.moveOutOfLoop(op);};moveLoopInvariantCode(loopLike.getLoopRegions(), isDefinedOutsideRegion, [&](Operation *op, Region *) { return canMoveOutOfLoop(op) &&shouldMoveOutOfLoop(op, loopLike, false);}, moveOutOfRegion);if(hoistFromNestedRegions==fir::LICMNestedHoistingMode::None) return;SmallVector< Region * > nestedRegions;for(Region *loopRegion :loopLike.getLoopRegions()) collectNestedRegions(*loopRegion, nestedRegions);if(nestedRegions.empty()) return;auto shouldMoveFromNestedRegion=[&](Operation *op, Region *) { for(Operation *ancestor=op->getParentOp();ancestor !=loopLike.getOperation();ancestor=ancestor->getParentOp()) { if(!ancestor) { return false;} if(!canMoveOutOfOp(ancestor, op)) { LDBG()<< "Cannot hoist "<< *op<< " out of intermediate operation: ";LDBG_OS([&](llvm::raw_ostream &os) { ancestor->print(os, OpPrintingFlags().skipRegions());});return false;} } return canMoveOutOfLoop(op) &&shouldMoveOutOfLoop(op, loopLike, true);};if(hoistFromNestedRegions==fir::LICMNestedHoistingMode::Aggressive) { moveLoopInvariantCode(nestedRegions, isDefinedOutsideRegion, shouldMoveFromNestedRegion, moveOutOfRegion);} else { moveLoopInvariantCode(nestedRegions, isDefinedOutsideRegion, [&](Operation *op, Region *region) { return isCheapToHoistFromNestedRegion(op) &&shouldMoveFromNestedRegion(op, region);}, moveOutOfRegion);} })
	LDBG ()<< "Exit [HL]FIR LoopInvariantCodeMotion()"

Variables
fir::AliasAnalysis	firAliasAnalysis {cachedAA}
std::function< bool(Operation *, LoopLikeOpInterface, bool)>	shouldMoveOutOfLoop
std::optional< OperationName >	scopeOpName
Operation *	function = getOperation()

Detailed Description

FIR-specific Loop Invariant Code Motion pass. The pass relies on FIR types and interfaces to prove the safety of hoisting invariant operations out of loop-like operations. It may be run on both HLFIR and FIR representations.

Variable Documentation

firAliasAnalysis

fir::AliasAnalysis firAliasAnalysis {cachedAA}

'location' is a memory reference used by a memory access. The type of 'location' defines the data type of the access (e.g. it is considered to be invalid to access 'i64' data using '!fir.ref<i32>‘). / For the given location, this function returns true iff / the Fortran object being accessed is a scalar that / may not be OPTIONAL. / / Note that the ’!fir.ref<!fir.box<>>' accesses are considered / to be scalar, even if the underlying data is an array. / / Note that an access of '!fir.ref<scalar>' may access / an array object. For example: / real :: x(:) / do i=... / = x(10) / 'x(10)' accesses array 'x', and it may be unsafe to hoist / it without proving that '10' is a valid index for the array. / The fact that 'x' is not OPTIONAL does not allow hoisting / on its own. static bool isNonOptionalScalar(Value location) { while (true) { LDBG() << "Checking location:\n" << location; Type dataType = fir::unwrapRefType(location.getType()); if (!isa<fir::BaseBoxType>(location.getType()) && (!dataType || (!isa<fir::BaseBoxType>(dataType) && !fir::isa_trivial(dataType) && !fir::isa_derived(dataType)))) { LDBG() << "Failure: data access is not scalar"; return false; } Operation *defOp = location.getDefiningOp(); if (!defOp) { A compute-region argument forwards a mapped input. Recover its storage provenance before checking whether a speculative scalar read is safe. if (Value operand = acc::getACCOperandForBlockArg(location)) { location = operand; continue; } If this is a function argument auto blockArg = cast<BlockArgument>(location); Block *block = blockArg.getOwner(); if (block && block->isEntryBlock()) if (auto funcOp = dyn_cast_if_present<FunctionOpInterface>(block->getParentOp())) if (!funcOp.getArgAttrOfType<UnitAttr>(blockArg.getArgNumber(), fir::getOptionalAttrName())) { LDBG() << "Success: is non optional scalar dummy"; return true; }

LDBG() << "Failure: no defining operation"; return false; }

Scalars "defined" by fir.address_of or that are new allocations (e.g. fir.alloca, cuf.alloc, etc.) are present. if (isa<fir::AddrOfOp>(defOp) || fir::isNewAllocationResult(cast<OpResult>(location)).value_or(false)) { LDBG() << "Success: is non optional scalar"; return true; }

if (auto varIface = dyn_cast<fir::FortranVariableOpInterface>(defOp)) { if (varIface.isOptional()) { The variable is optional, so do not look further. Note that it is possible to deduce that the optional is actually present, but we are not doing it now. LDBG() << "Failure: is optional"; return false; }

In case of MLIR inlining and ASSOCIATE an [hl]fir.declare may declare a scalar variable that is actually a "view" of an array element. Originally, such [hl]fir.declare would be located inside the loop preventing the hoisting. But if we decide to hoist such [hl]fir.declare in future, we cannot rely on their attributes/types. Use reliable checks based on the variable storage.

If the variable has storage specifier (e.g. it is a member of COMMON, etc.), we can rely that the storage is present, and we can also rely on its FortranVariableOpInterface definition type (which is a scalar due to previous checks). if (auto storageIface = dyn_cast<fir::FortranVariableStorageOpInterface>(defOp)) if (Value storage = storageIface.getStorage()) { LDBG() << "Success: is scalar with existing storage"; return true; }

TODO: we can probably use FIR AliasAnalysis' getSource() method to identify the storage in more cases. location = llvm::TypeSwitch<Operation *, Value>(defOp) .Case<fir::DeclareOp, hlfir::DeclareOp>( [](auto op) { return op.getMemref(); }) .Default([](auto) { return nullptr; });

if (location) continue;

LDBG() << "Failure: cannot reason about variable storage"; return false; } if (auto viewIface = dyn_cast<fir::FortranObjectViewOpInterface>(defOp)) { location = viewIface.getViewSource(cast<OpResult>(location)); } else { LDBG() << "Failure: unknown operation:\n" << *defOp; return false; } } }

/ Returns true iff it is safe to hoist the given load-like operation 'op', / which access given memory 'locations', out of the operation 'loopLike'. / The current safety conditions are: / * The load is known to be unconditionally executed in the loop and the / loop runs at least one iteration, OR / * all the accessed locations are inside scalar non-OPTIONAL / Fortran objects (Fortran descriptors are considered to be scalars). / / When maybeConditionallyExecuted is true, the load may be inside a / conditional region (e.g. scf.if) within the loop, so the trip count / shortcut cannot be used: even if the loop runs, the condition might never / be true and the load might access an invalid location. / TODO: analyze the parent operation to determine whether it truly / conditionally executes its body (e.g. scf.execute_region always does). static bool isSafeToHoistLoad(Operation *op, ArrayRef<Value> locations, LoopLikeOpInterface loopLike, AliasAnalysis &aliasAnalysis, bool maybeConditionallyExecuted) { for (Value location : locations) if (aliasAnalysis.getModRef(loopLike.getOperation(), location).isMod()) { LDBG() << "Failure: reads location:\n" << location << "\nwhich is modified inside the loop"; return false; }

Check that it is safe to read from all the locations before the loop. if (!maybeConditionallyExecuted) { std::optional<llvm::APInt> tripCount = loopLike.getStaticTripCount(); if (tripCount && !tripCount->isZero()) { Loop executes at least one iteration and the load is unconditionally executed in the loop body, so it is safe to hoist. LDBG() << "Success: loop has non-zero iterations"; return true; } }

Check whether the access must always be valid. return llvm::all_of( locations, [&](Value location) { return isNonOptionalScalar(location); }); TODO: consider hoisting under condition of the loop's trip count being non-zero. }

/ Returns true iff the given 'op' is a load-like operation, / and it can be hoisted out of 'loopLike' operation. / See isSafeToHoistLoad for the meaning of maybeConditionallyExecuted. static bool canHoistLoad(Operation *op, LoopLikeOpInterface loopLike, AliasAnalysis &aliasAnalysis, bool maybeConditionallyExecuted) { LDBG() << "Checking operation:\n" << *op; if (auto effectInterface = dyn_cast<MemoryEffectOpInterface>(op)) { SmallVector<MemoryEffects::EffectInstance> effects; effectInterface.getEffects(effects); if (effects.empty()) { LDBG() << "Failure: not a load"; return false; } llvm::SetVector<Value> locations; for (const MemoryEffects::EffectInstance &effect : effects) { Value location = effect.getValue(); if (!isa<MemoryEffects::Read>(effect.getEffect())) { LDBG() << "Failure: has unsupported effects"; return false; } else if (!location) { LDBG() << "Failure: reads from unknown location"; return false; } locations.insert(location); } return isSafeToHoistLoad(op, locations.getArrayRef(), loopLike, aliasAnalysis, maybeConditionallyExecuted); } LDBG() << "Failure: has unknown effects"; return false; }

/ Returns true iff hoisting op out of a nested region is expected to be / inexpensive. This is a cost heuristic only; the safety of the hoisting is / established separately. / / fir.convert and fir.address_of are at most one instruction and are often / free. A load of a trivial non-vector type is a single access, and a load of / a descriptor of known rank is a fixed-size copy. Vector loads may be large, / an assumed-rank descriptor load lowers to a runtime-sized memcpy, and / CHARACTER, derived types and arrays may be arbitrarily large, so those are / left to the aggressive mode. static bool isCheapToHoistFromNestedRegion(Operation *op) { if (isa<fir::ConvertOp, fir::AddrOfOp>(op)) return true; if (auto load = dyn_cast<fir::LoadOp>(op)) { Type resultType = load.getType(); if (isa<fir::BaseBoxType>(resultType)) return !fir::isa_unknown_size_box(resultType); return fir::isa_trivial(resultType) && !fir::isa_vector(resultType); } return false; }

/ Recursively collect regions from operations inside region, skipping / IsolatedFromAbove operations (whose regions form a separate scope) and / LoopLikeOpInterface operations (which have their own LICM invocation). static void collectNestedRegions(Region &region, SmallVectorImpl<Region *> &result) { for (Operation &op : region.getOps()) { if (op.hasTrait<OpTrait::IsIsolatedFromAbove>()) continue; if (isa<LoopLikeOpInterface>(&op)) continue; for (Region &nested : op.getRegions()) { result.push_back(&nested); collectNestedRegions(nested, result); } } }

void LoopInvariantCodeMotion::runOnOperation() { if (disableFlangLICM) { LDBG() << "Skipping [HL]FIR LoopInvariantCodeMotion()"; return; }

LDBG() << "Enter [HL]FIR LoopInvariantCodeMotion()";

Build a recursive-effects cache scoped to this pass run and link it to a fir::AliasAnalysis that will live inside the mlir::AliasAnalysis aggregator. Every query against that AliasAnalysis (direct, or via the aggregator) now routes recursive-effect ops through the cache. The cache's destructor nulls the back-pointer on the registered AliasAnalysis when LICM exits, so the aggregator never dereferences a dead cache.

LICM only hoists pure-read ops out of loops; writes are never moved, ops are never erased, and SSA values are not RAUW'd. That matches the cache's safety invariant for the whole pass run on this function. fir::AliasAnalysisRecursiveEffectsCache cachedAA; auto &aliasAnalysis = getAnalysis<AliasAnalysis>(); Two independent, complementary caches are enabled for this pass:

     the recursive-effects cache (`cachedAA`), which memoizes per-operation