MLIR  18.0.0git
LoopInvariantCodeMotionUtils.cpp
Go to the documentation of this file.
1 //===- LoopInvariantCodeMotionUtils.cpp - LICM Utils ------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file contains the implementation of the core LICM algorithm.
10 //
11 //===----------------------------------------------------------------------===//
12 
14 #include "mlir/IR/Operation.h"
17 #include "llvm/Support/Debug.h"
18 #include <queue>
19 
20 #define DEBUG_TYPE "licm"
21 
22 using namespace mlir;
23 
24 /// Checks whether the given op can be hoisted by checking that
25 /// - the op and none of its contained operations depend on values inside of the
26 /// loop (by means of calling definedOutside).
27 /// - the op has no side-effects.
28 static bool canBeHoisted(Operation *op,
29  function_ref<bool(Value)> definedOutside) {
30  // Do not move terminators.
32  return false;
33 
34  // Walk the nested operations and check that all used values are either
35  // defined outside of the loop or in a nested region, but not at the level of
36  // the loop body.
37  auto walkFn = [&](Operation *child) {
38  for (Value operand : child->getOperands()) {
39  // Ignore values defined in a nested region.
40  if (op->isAncestor(operand.getParentRegion()->getParentOp()))
41  continue;
42  if (!definedOutside(operand))
43  return WalkResult::interrupt();
44  }
45  return WalkResult::advance();
46  };
47  return !op->walk(walkFn).wasInterrupted();
48 }
49 
51  ArrayRef<Region *> regions,
52  function_ref<bool(Value, Region *)> isDefinedOutsideRegion,
53  function_ref<bool(Operation *, Region *)> shouldMoveOutOfRegion,
54  function_ref<void(Operation *, Region *)> moveOutOfRegion) {
55  size_t numMoved = 0;
56 
57  for (Region *region : regions) {
58  LLVM_DEBUG(llvm::dbgs() << "Original loop:\n"
59  << *region->getParentOp() << "\n");
60 
61  std::queue<Operation *> worklist;
62  // Add top-level operations in the loop body to the worklist.
63  for (Operation &op : region->getOps())
64  worklist.push(&op);
65 
66  auto definedOutside = [&](Value value) {
67  return isDefinedOutsideRegion(value, region);
68  };
69 
70  while (!worklist.empty()) {
71  Operation *op = worklist.front();
72  worklist.pop();
73  // Skip ops that have already been moved. Check if the op can be hoisted.
74  if (op->getParentRegion() != region)
75  continue;
76 
77  LLVM_DEBUG(llvm::dbgs() << "Checking op: " << *op << "\n");
78  if (!shouldMoveOutOfRegion(op, region) ||
79  !canBeHoisted(op, definedOutside))
80  continue;
81 
82  LLVM_DEBUG(llvm::dbgs() << "Moving loop-invariant op: " << *op << "\n");
83  moveOutOfRegion(op, region);
84  ++numMoved;
85 
86  // Since the op has been moved, we need to check its users within the
87  // top-level of the loop body.
88  for (Operation *user : op->getUsers())
89  if (user->getParentRegion() == region)
90  worklist.push(user);
91  }
92  }
93 
94  return numMoved;
95 }
96 
97 size_t mlir::moveLoopInvariantCode(LoopLikeOpInterface loopLike) {
98  return moveLoopInvariantCode(
99  loopLike.getLoopRegions(),
100  [&](Value value, Region *) {
101  return loopLike.isDefinedOutsideOfLoop(value);
102  },
103  [&](Operation *op, Region *) {
104  return isMemoryEffectFree(op) && isSpeculatable(op);
105  },
106  [&](Operation *op, Region *) { loopLike.moveOutOfLoop(op); });
107 }
static bool canBeHoisted(Operation *op, function_ref< bool(Value)> definedOutside)
Checks whether the given op can be hoisted by checking that.
This class provides the API for ops that are known to be terminators.
Definition: OpDefinition.h:757
Operation is the basic unit of execution within MLIR.
Definition: Operation.h:88
bool hasTrait()
Returns true if the operation was registered with a particular trait, e.g.
Definition: Operation.h:728
std::enable_if_t< llvm::function_traits< std::decay_t< FnT > >::num_args==1, RetT > walk(FnT &&callback)
Walk the operation by calling the callback for each nested operation (including this one),...
Definition: Operation.h:776
bool isAncestor(Operation *other)
Return true if this operation is an ancestor of the other operation.
Definition: Operation.h:263
user_range getUsers()
Returns a range of all users.
Definition: Operation.h:852
Region * getParentRegion()
Returns the region to which the instruction belongs.
Definition: Operation.h:230
This class contains a list of basic blocks and a link to the parent operation it is attached to.
Definition: Region.h:26
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:93
static WalkResult advance()
Definition: Visitors.h:52
static WalkResult interrupt()
Definition: Visitors.h:51
This header declares functions that assist transformations in the MemRef dialect.
size_t moveLoopInvariantCode(ArrayRef< Region * > regions, function_ref< bool(Value, Region *)> isDefinedOutsideRegion, function_ref< bool(Operation *, Region *)> shouldMoveOutOfRegion, function_ref< void(Operation *, Region *)> moveOutOfRegion)
Given a list of regions, perform loop-invariant code motion.