| 1 | //===- TosaReduceTransposes.cpp -------------------------------------------===// |
| 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 | // ---------- |
| 10 | // Motivation: |
| 11 | // ---------- |
| 12 | |
| 13 | // Some legalization pathways introduce redundant tosa.TRANSPOSE |
| 14 | // operations that result in avoidable data movement. For example, |
| 15 | // PyTorch -> TOSA contains a lot of unnecessary transposes due |
| 16 | // to conversions between NCHW and NHWC. |
| 17 | |
| 18 | // We wish to remove all the ones that we can, since in general |
| 19 | // it is possible to remove the overwhelming majority. |
| 20 | |
| 21 | // ------------------- |
| 22 | // High-Level Overview: |
| 23 | // ------------------- |
| 24 | |
| 25 | // The pass works through the transpose operators in the program. It begins at |
| 26 | // some transpose operator with an associated permutations tensor. It traverses |
| 27 | // upwards through the dependencies of this transpose and verifies that we |
| 28 | // encounter only operators with the TosaElementwiseOperator trait and terminate |
| 29 | // in either constants, reshapes, or transposes. |
| 30 | |
| 31 | // We then evaluate whether there are any additional restrictions (the |
| 32 | // transposes it terminates in must invert the one we began at, and the reshapes |
| 33 | // must be ones in which we can fold the transpose into), and then we hoist the |
| 34 | // transpose through the intervening operators, folding it at the constants, |
| 35 | // reshapes, and transposes. |
| 36 | |
| 37 | // Finally, we ensure that we do not need both the transposed form (the form |
| 38 | // that had the transpose hoisted through it) and the untransposed form (which |
| 39 | // it was prior), by analyzing the usages of those dependent operators of a |
| 40 | // given transpose we are attempting to hoist and replace. |
| 41 | |
| 42 | // If they are such that it would require both forms to be necessary, then we do |
| 43 | // not replace the hoisted transpose, causing the new chain to be dead. |
| 44 | // Otherwise, we do and the old chain (untransposed form) becomes dead. Only one |
| 45 | // chain will ever then be live, resulting in no duplication. |
| 46 | |
| 47 | // We then perform a simple one-pass DCE, so no canonicalization is necessary. |
| 48 | |
| 49 | // ----------- |
| 50 | // Future Work: |
| 51 | // ----------- |
| 52 | |
| 53 | // (1) Evaluate tradeoffs with permitting ConstOp to be duplicated across |
| 54 | // hoisted |
| 55 | // transposes with different permutation tensors. |
| 56 | |
| 57 | // (2) Expand the class of foldable upstream ReshapeOp we permit beyond |
| 58 | // N -> 1x1x...x1xNx1x...x1x1. |
| 59 | |
| 60 | // (3) Enchance the pass to permit folding arbitrary transpose pairs, beyond |
| 61 | // those that form the identity. |
| 62 | |
| 63 | // (4) Add support for more instructions besides TosaElementwiseOperator as |
| 64 | // the intervening ones (for example, the reduce_* operators). |
| 65 | |
| 66 | // (5) Support hoisting transposes up to an input parameter. |
| 67 | |
| 68 | //===----------------------------------------------------------------------===// |
| 69 | |
| 70 | #include "mlir/Dialect/Func/IR/FuncOps.h" |
| 71 | #include "mlir/Dialect/Tosa/IR/TosaOps.h" |
| 72 | #include "mlir/Dialect/Tosa/Transforms/Passes.h" |
| 73 | #include "mlir/Dialect/Tosa/Utils/ConversionUtils.h" |
| 74 | #include "mlir/IR/Iterators.h" |
| 75 | #include "llvm/ADT/TypeSwitch.h" |
| 76 | #include <set> |
| 77 | #include <stack> |
| 78 | |
| 79 | namespace mlir { |
| 80 | namespace tosa { |
| 81 | #define GEN_PASS_DEF_TOSAREDUCETRANSPOSES |
| 82 | #include "mlir/Dialect/Tosa/Transforms/Passes.h.inc" |
| 83 | } // namespace tosa |
| 84 | } // namespace mlir |
| 85 | |
| 86 | using namespace mlir; |
| 87 | using namespace mlir::tosa; |
| 88 | |
| 89 | //===----------------------------------------------------------------------===// |
| 90 | // TOSA Reduce Transposes Pass. |
| 91 | //===----------------------------------------------------------------------===// |
| 92 | |
| 93 | namespace { |
| 94 | |
| 95 | struct TosaReduceTransposes final |
| 96 | : public tosa::impl::TosaReduceTransposesBase<TosaReduceTransposes> { |
| 97 | void runOnOperation() override; |
| 98 | |
| 99 | private: |
| 100 | // This will collect all the data dependencies for the given Operation |
| 101 | // up to and including ConstOp, ReshapeOp, and TransposeOp. |
| 102 | bool collectFanIn(Operation *op, SetVector<Operation *> &collected); |
| 103 | bool convertDependentOps(SetVector<Operation *> &dependentOps, |
| 104 | DenseMap<Value, Value> &valuesMap, |
| 105 | IRRewriter &rewriter, |
| 106 | ArrayRef<int32_t> hoistedPerms); |
| 107 | |
| 108 | // Checks if the two permutations, when applied consecutively, result |
| 109 | // in the identity. |
| 110 | bool areInvolutionTransposes(ArrayRef<int32_t> perms1, |
| 111 | ArrayRef<int32_t> perms2); |
| 112 | |
| 113 | // This is meant to apply to operations with the TosaElementwiseOperator |
| 114 | // trait. |
| 115 | std::optional<Value> |
| 116 | buildMappedToValue(Operation *op, const DenseMap<Value, Value> &valuesMap, |
| 117 | IRRewriter &rewriter, ArrayRef<int32_t> hoistedPerms); |
| 118 | |
| 119 | // This updates valuesMap when we encounter another TransposeOp as a |
| 120 | // dependency of the hoisted one. %0 = tosa.transpose %arg0 <- applies to |
| 121 | // this %1 = tosa.transpose %0 <- when tracking back from this |
| 122 | std::optional<Value> |
| 123 | buildMappedToValue(TransposeOp transposeOp, |
| 124 | const DenseMap<Value, Value> &valuesMap, |
| 125 | IRRewriter &rewriter, ArrayRef<int32_t> hoistedPerms); |
| 126 | |
| 127 | // Checks if ReshapeOp can have hoisted TransposeOp folded into it. If so, |
| 128 | // it creates new ReshapeOp with that fold. |
| 129 | std::optional<Value> |
| 130 | buildMappedToValue(ReshapeOp reshapeOp, |
| 131 | const DenseMap<Value, Value> &valuesMap, |
| 132 | IRRewriter &rewriter, ArrayRef<int32_t> hoistedPerms); |
| 133 | |
| 134 | // We may have something like: |
| 135 | // %0 = tosa.const |
| 136 | // %1 = tosa.transpose |
| 137 | // %2 = tosa.add %0, %1 |
| 138 | // %3 = tosa.transpose %2 |
| 139 | // that --tosa-layerwise-const-fold wouldn't handle. This use shows up |
| 140 | // in MobilenetV3. |
| 141 | std::optional<Value> |
| 142 | buildMappedToValue(ConstOp constOp, const DenseMap<Value, Value> &valuesMap, |
| 143 | IRRewriter &rewriter, ArrayRef<int32_t> hoistedPerms); |
| 144 | |
| 145 | // Checks which TransposeOp we should "replace", turning their converted |
| 146 | // chains of ops, through which they were propagated, "live", and the old code |
| 147 | // "dead." Attempts to avoid doing so when doing so would result in the old |
| 148 | // code staying "live," resulting in duplication. |
| 149 | std::set<TransposeOp> getGoodReplacements( |
| 150 | ArrayRef<int32_t> perms, |
| 151 | std::vector<std::pair<TransposeOp, SetVector<Operation *>>> |
| 152 | &transposeInfo); |
| 153 | |
| 154 | // Helper function for dependenciesAreValid. |
| 155 | bool userNotContainedInValidTransposeDependencies( |
| 156 | Operation *user, std::set<TransposeOp> &validTransposes, |
| 157 | std::vector<std::pair<TransposeOp, SetVector<Operation *>>> |
| 158 | &transposeInfo); |
| 159 | |
| 160 | // Helper function for getGoodReplacements to check if some TransposeOp's |
| 161 | // dependencies are OK. |
| 162 | bool dependenciesAreValid( |
| 163 | ArrayRef<int32_t> perms, const SetVector<Operation *> &dependentOps, |
| 164 | std::set<TransposeOp> &validTransposes, |
| 165 | std::vector<std::pair<TransposeOp, SetVector<Operation *>>> |
| 166 | &transposeInfo); |
| 167 | |
| 168 | // Applies perms to the DenseElementsAttr. |
| 169 | // If it returns std::nullopt, it also triggers pass failure, since verifier |
| 170 | // guarantees from TOSA are not in place (and otherwise, if used elsewhere, |
| 171 | // it should fail). |
| 172 | // This is a basic API and may benefit from refactor into the core MLIR APIs. |
| 173 | std::optional<DenseElementsAttr> |
| 174 | transposeDenseAttribute(DenseElementsAttr input, ArrayRef<int32_t> perms); |
| 175 | }; |
| 176 | |
| 177 | // Check if shape is of the form 1x1x...x1xNx1x...x1x1 -> 1x1x...x1xNx1x...x1x1 |
| 178 | // Valid examples include: |
| 179 | // - N -> 1x1xNx1 |
| 180 | // - Nx1x1x1 -> 1x1xNx1 |
| 181 | // - 1x1xNx1 -> 1x1xNx1 |
| 182 | static LogicalResult verifyUnitExpandedVectorShape(ArrayRef<int64_t> shape) { |
| 183 | bool nonUnitDimDetected = false; |
| 184 | for (const int64_t dim : shape) { |
| 185 | if (dim != 1) { |
| 186 | if (nonUnitDimDetected) |
| 187 | return failure(); |
| 188 | nonUnitDimDetected = true; |
| 189 | } |
| 190 | } |
| 191 | return success(); |
| 192 | } |
| 193 | |
| 194 | std::optional<DenseElementsAttr> |
| 195 | TosaReduceTransposes::transposeDenseAttribute(DenseElementsAttr input, |
| 196 | ArrayRef<int32_t> perms) { |
| 197 | RankedTensorType oldType = llvm::cast<RankedTensorType>(Val: input.getType()); |
| 198 | ArrayRef<int64_t> oldShape = oldType.getShape(); |
| 199 | int64_t rank = oldType.getRank(); |
| 200 | |
| 201 | // Asserted by TransposeOp verifier and TOSA disallowing tensor with dimension |
| 202 | // 0. If not in place, something is very wrong. |
| 203 | if (rank <= 0 || oldType.getNumElements() <= 0) { |
| 204 | signalPassFailure(); |
| 205 | return std::nullopt; |
| 206 | } |
| 207 | |
| 208 | auto newShape = applyTOSAPermutation(input: oldShape, perms); |
| 209 | RankedTensorType newType = |
| 210 | RankedTensorType::get(shape: newShape, elementType: oldType.getElementType()); |
| 211 | |
| 212 | if (input.isSplat()) { |
| 213 | return input.reshape(newType); |
| 214 | } |
| 215 | |
| 216 | auto rawData = input.getRawData(); |
| 217 | if (!rawData.data()) { |
| 218 | return std::nullopt; |
| 219 | } |
| 220 | |
| 221 | // The algorithm is approximately as follows: |
| 222 | // 1. Determine the strides of both input and output tensors in row-major |
| 223 | // order |
| 224 | // 2. Iterate through the output tensor linearly. |
| 225 | // 3. For each output position, decompose the linear index into |
| 226 | // multi-dimensional coordinates using output strides. |
| 227 | // 4. Use the permutation to map output coordinates to input coordinates and |
| 228 | // calculate the source linear index. |
| 229 | |
| 230 | // Example: perms [2, 0, 1]; input 2x3x4; output 4x2x3 |
| 231 | // for output linear index 11: decompose to output[1][1][2] |
| 232 | // using output strides [6,3,1]. Map to input coordinates using |
| 233 | // perms: dim 0→2, dim 1→0, dim 2→1, giving source position |
| 234 | // calculated as 1*inputStrides[2] + 1*inputStrides[0] + 2*inputStrides[1] |
| 235 | // = 1*1 + 1*12 + 2*4 = 21 |
| 236 | size_t elementSize = llvm::divideCeil(Numerator: oldType.getElementTypeBitWidth(), Denominator: 8); |
| 237 | int64_t numElements = oldType.getNumElements(); |
| 238 | |
| 239 | SmallVector<char> outputBuffer(numElements * elementSize); |
| 240 | const char *inputPtr = rawData.data(); |
| 241 | char *outputPtr = outputBuffer.data(); |
| 242 | |
| 243 | auto calculateStrides = [](ArrayRef<int64_t> shape) -> SmallVector<int64_t> { |
| 244 | int64_t rank = shape.size(); |
| 245 | SmallVector<int64_t> strides(rank); |
| 246 | strides[rank - 1] = 1; |
| 247 | for (int64_t i = rank - 2; i >= 0; --i) { |
| 248 | strides[i] = strides[i + 1] * shape[i + 1]; |
| 249 | } |
| 250 | return strides; |
| 251 | }; |
| 252 | |
| 253 | // Calculate strides for both input and output tensors |
| 254 | SmallVector<int64_t> inputStrides = calculateStrides(oldShape); |
| 255 | SmallVector<int64_t> outputStrides = calculateStrides(newShape); |
| 256 | |
| 257 | auto mapCoordinates = [&](int64_t destLinearIndex) -> int64_t { |
| 258 | int64_t tempDestIndex = destLinearIndex; |
| 259 | int64_t sourceLinearIndex = 0; |
| 260 | |
| 261 | // Decompose linear destination index into multi-dimensional |
| 262 | // coordinates dividing by output strides. |
| 263 | // Simultaneously map these coordinates through the permutation |
| 264 | // to calculate the corresponding source linear index. |
| 265 | for (auto j : llvm::seq<int64_t>(Size: rank)) { |
| 266 | int64_t destCoord = tempDestIndex / outputStrides[j]; |
| 267 | tempDestIndex %= outputStrides[j]; |
| 268 | sourceLinearIndex += destCoord * inputStrides[perms[j]]; |
| 269 | } |
| 270 | |
| 271 | return sourceLinearIndex; |
| 272 | }; |
| 273 | |
| 274 | for (auto destLinearIndex : llvm::seq<int64_t>(Size: numElements)) { |
| 275 | int64_t sourceLinearIndex = mapCoordinates(destLinearIndex); |
| 276 | |
| 277 | // Copy the element from source to destination using type-agnostic byte |
| 278 | // copying. |
| 279 | std::memcpy(dest: outputPtr + destLinearIndex * elementSize, |
| 280 | src: inputPtr + sourceLinearIndex * elementSize, n: elementSize); |
| 281 | } |
| 282 | |
| 283 | return DenseElementsAttr::getFromRawBuffer(type: newType, rawBuffer: outputBuffer); |
| 284 | } |
| 285 | |
| 286 | // The SetVector should only contain ConstOp, ReshapeOp, TransposeOp |
| 287 | // as the sources of the data dependencies, and TosaElementWiseOperator |
| 288 | // after that, if the function returns true. |
| 289 | bool TosaReduceTransposes::collectFanIn(Operation *op, |
| 290 | SetVector<Operation *> &collected) { |
| 291 | // Can occur if defined through the parameter to a func.func. |
| 292 | if (!op) |
| 293 | return false; |
| 294 | |
| 295 | if (!llvm::isa_and_present<tosa::TosaDialect>(Val: op->getDialect())) |
| 296 | return false; |
| 297 | |
| 298 | // Prevent extra work if already seen. |
| 299 | if (collected.contains(key: op)) |
| 300 | return true; |
| 301 | |
| 302 | // Throw it out so later don't have to deal with this. |
| 303 | if (op->getNumResults() != 1 || |
| 304 | !llvm::isa<RankedTensorType>(Val: op->getResult(idx: 0).getType())) |
| 305 | return false; |
| 306 | |
| 307 | // We don't wish to traverse up a ReshapeOp, since generally we can't |
| 308 | // propagate a TransposeOp through it. TransposeOp, ReshapeOp, ConstOp |
| 309 | // will have no in-edges in the data dependency graph we construct for |
| 310 | // the downstream TransposeOp. |
| 311 | if (!llvm::isa<tosa::TransposeOp>(Val: op) && !llvm::isa<tosa::ReshapeOp>(Val: op) && |
| 312 | !llvm::isa<tosa::ConstOp>(Val: op)) { |
| 313 | |
| 314 | if (!llvm::isa<tosa::MulOp>(Val: op) && |
| 315 | !op->hasTrait<OpTrait::tosa::TosaElementwiseOperator>()) |
| 316 | return false; |
| 317 | |
| 318 | for (Value operand : op->getOperands()) { |
| 319 | // If this is a problem in future, think about alternatives to recursion. |
| 320 | if (llvm::isa<tosa::MulOp>(Val: op) && operand == op->getOperand(idx: 2)) { |
| 321 | // do not recurse into MulOp's shift operand |
| 322 | continue; |
| 323 | } |
| 324 | if (!collectFanIn(op: operand.getDefiningOp(), collected)) |
| 325 | return false; |
| 326 | } |
| 327 | } |
| 328 | |
| 329 | // Insert in topological order. |
| 330 | collected.insert(X: op); |
| 331 | |
| 332 | return true; |
| 333 | } |
| 334 | |
| 335 | // Assuming that due to the verification of TransposeOp perms arrays are |
| 336 | // permutations of 0 - perms.size() - 1. |
| 337 | bool TosaReduceTransposes::areInvolutionTransposes(ArrayRef<int32_t> perms1, |
| 338 | ArrayRef<int32_t> perms2) { |
| 339 | if (perms1.size() != perms2.size()) |
| 340 | return false; |
| 341 | int32_t n = perms1.size(); |
| 342 | for (int32_t i = 0; i < n; i++) |
| 343 | if (perms2[perms1[i]] != i) |
| 344 | return false; |
| 345 | return true; |
| 346 | } |
| 347 | |
| 348 | // Primary overload for those with TosaElementwiseOperator trait. |
| 349 | // The other ones handle the case of the operations that occur at the |
| 350 | // roots of the data dependency graph (ConstOp, ReshapeOp, TransposeOp). |
| 351 | std::optional<Value> TosaReduceTransposes::buildMappedToValue( |
| 352 | Operation *op, const DenseMap<Value, Value> &valuesMap, |
| 353 | IRRewriter &rewriter, ArrayRef<int32_t> hoistedPerms) { |
| 354 | if (op->getNumResults() != 1 || |
| 355 | (!llvm::isa<tosa::MulOp>(Val: op) && |
| 356 | !op->hasTrait<OpTrait::tosa::TosaElementwiseOperator>())) |
| 357 | return std::nullopt; |
| 358 | |
| 359 | auto resultType = llvm::cast<RankedTensorType>(Val: op->getResult(idx: 0).getType()); |
| 360 | SmallVector<Value, 3> operands; |
| 361 | for (Value v : op->getOperands()) { |
| 362 | if (valuesMap.contains(Val: v)) { |
| 363 | operands.push_back(Elt: valuesMap.at(Val: v)); |
| 364 | } else if (llvm::isa<tosa::MulOp>(Val: op) && v == op->getOperand(idx: 2)) { |
| 365 | // special case for MulOp's shift operand |
| 366 | operands.push_back(Elt: v); |
| 367 | } else { |
| 368 | return std::nullopt; |
| 369 | } |
| 370 | } |
| 371 | |
| 372 | // Conceptually, we propagate the hoisted TransposeOp through |
| 373 | // these interveaning operations. For example, |
| 374 | |
| 375 | // %0 = tosa.clamp %input : (tensor<2x3xi32>) -> tensor<2x3xi32> |
| 376 | // %1 = tosa.transpose %0 {perms = [1, 0]} : (tensor<2x3xi32>) -> |
| 377 | // tensor<3x2xi32> |
| 378 | |
| 379 | // becomes: |
| 380 | // %0 = tosa.transpose %input {perms = [1, 0]} : (tensor<2x3xi32>) -> |
| 381 | // tensor<3x2xi32> |
| 382 | // %1 = tosa.clamp %0 : (tensor<3x2xi32>) -> tensor<3x2xi32>) |
| 383 | |
| 384 | // We construct this new tosa.clamp here, but it doesn't |
| 385 | // turn "live" until the transpose being hoisted through this chain |
| 386 | // is replaced with the proper value from the new chain. |
| 387 | |
| 388 | Type newResultType = RankedTensorType::get( |
| 389 | shape: applyTOSAPermutation(input: resultType.getShape(), perms: hoistedPerms), |
| 390 | elementType: resultType.getElementType()); |
| 391 | OperationState state(op->getLoc(), op->getName(), operands, newResultType, |
| 392 | op->getDiscardableAttrDictionary().getValue()); |
| 393 | state.propertiesAttr = op->getPropertiesAsAttribute(); |
| 394 | return rewriter.create(state)->getResult(idx: 0); |
| 395 | } |
| 396 | |
| 397 | std::optional<Value> TosaReduceTransposes::buildMappedToValue( |
| 398 | TransposeOp transposeOp, const DenseMap<Value, Value> &valuesMap, |
| 399 | IRRewriter &rewriter, ArrayRef<int32_t> hoistedPerms) { |
| 400 | if (!areInvolutionTransposes(perms1: hoistedPerms, perms2: transposeOp.getPerms())) |
| 401 | return std::nullopt; |
| 402 | return transposeOp.getInput1(); |
| 403 | } |
| 404 | |
| 405 | std::optional<Value> TosaReduceTransposes::buildMappedToValue( |
| 406 | ReshapeOp reshapeOp, const DenseMap<Value, Value> &valuesMap, |
| 407 | IRRewriter &rewriter, ArrayRef<int32_t> hoistedPerms) { |
| 408 | auto reshapeOutput = reshapeOp.getOutput(); |
| 409 | auto reshapeInputType = |
| 410 | llvm::dyn_cast<RankedTensorType>(Val: reshapeOp.getInput1().getType()); |
| 411 | if (!reshapeInputType) |
| 412 | return std::nullopt; |
| 413 | auto reshapeInputShape = reshapeInputType.getShape(); |
| 414 | auto reshapeOutputType = |
| 415 | llvm::cast<RankedTensorType>(Val: reshapeOutput.getType()); |
| 416 | const ArrayRef<int64_t> reshapeOutputShape = reshapeOutputType.getShape(); |
| 417 | |
| 418 | // Instead of inserting a TransposeOp here, we check if we can fold it into |
| 419 | // the ReshapeOp. There is more complex cases where this is possible, and |
| 420 | // this check can be extended. |
| 421 | if (failed(Result: verifyUnitExpandedVectorShape(shape: reshapeInputShape)) || |
| 422 | failed(Result: verifyUnitExpandedVectorShape(shape: reshapeOutputShape))) |
| 423 | return std::nullopt; |
| 424 | |
| 425 | // Do not insert a TransposeOp, instead we fold the reshape and its attribute. |
| 426 | llvm::SmallVector<int64_t> newShape; |
| 427 | if (!tosa::getConstShapeValues(op: reshapeOp.getShape().getDefiningOp(), |
| 428 | result_shape&: newShape)) { |
| 429 | // this mean shape is not constant |
| 430 | return std::nullopt; |
| 431 | } |
| 432 | ImplicitLocOpBuilder builder(reshapeOp.getLoc(), rewriter); |
| 433 | auto foldedReshape = ReshapeOp::create( |
| 434 | builder&: rewriter, location: reshapeOp.getLoc(), |
| 435 | output: RankedTensorType::get( |
| 436 | shape: applyTOSAPermutation(input: reshapeOutputShape, perms: hoistedPerms), |
| 437 | elementType: reshapeOutputType.getElementType()), |
| 438 | input1: reshapeOp.getInput1(), |
| 439 | shape: getTosaConstShape(builder, shape: applyTOSAPermutation(input: llvm::ArrayRef(newShape), |
| 440 | perms: hoistedPerms))); |
| 441 | return foldedReshape->getResult(idx: 0); |
| 442 | } |
| 443 | |
| 444 | std::optional<Value> TosaReduceTransposes::buildMappedToValue( |
| 445 | ConstOp constOp, const DenseMap<Value, Value> &valuesMap, |
| 446 | IRRewriter &rewriter, ArrayRef<int32_t> hoistedPerms) { |
| 447 | auto denseAttr = llvm::dyn_cast<DenseElementsAttr>(Val: constOp.getValues()); |
| 448 | if (!denseAttr) |
| 449 | return std::nullopt; |
| 450 | auto maybeNewDenseAttr = transposeDenseAttribute(input: denseAttr, perms: hoistedPerms); |
| 451 | if (!maybeNewDenseAttr.has_value()) |
| 452 | return std::nullopt; |
| 453 | auto newDenseAttr = maybeNewDenseAttr.value(); |
| 454 | auto newConstOp = ConstOp::create(builder&: rewriter, location: constOp.getLoc(), |
| 455 | output: newDenseAttr.getType(), values: newDenseAttr); |
| 456 | return newConstOp->getResult(idx: 0); |
| 457 | } |
| 458 | |
| 459 | bool TosaReduceTransposes::convertDependentOps( |
| 460 | SetVector<Operation *> &dependentOps, DenseMap<Value, Value> &valuesMap, |
| 461 | IRRewriter &rewriter, ArrayRef<int32_t> hoistedPerms) { |
| 462 | |
| 463 | for (Operation *op : dependentOps) { |
| 464 | if (!op || op->getNumResults() != 1) |
| 465 | return false; |
| 466 | |
| 467 | Value priorValue = op->getResult(idx: 0); |
| 468 | |
| 469 | // It's possible on a prior transposeOp we had the same dependency and |
| 470 | // already resolved it. |
| 471 | if (valuesMap.contains(Val: priorValue)) |
| 472 | continue; |
| 473 | |
| 474 | // Keep converted ops close to the original. |
| 475 | rewriter.setInsertionPointAfter(op); |
| 476 | |
| 477 | std::optional<Value> maybeValue = |
| 478 | llvm::TypeSwitch<Operation *, std::optional<Value>>(op) |
| 479 | .Case<TransposeOp, ReshapeOp, ConstOp>(caseFn: [&](auto transposeOp) { |
| 480 | return buildMappedToValue(transposeOp, valuesMap, rewriter, |
| 481 | hoistedPerms); |
| 482 | }) |
| 483 | .Default(defaultFn: [&](Operation *op) { |
| 484 | return buildMappedToValue(op, valuesMap, rewriter, hoistedPerms); |
| 485 | }); |
| 486 | |
| 487 | if (!maybeValue.has_value()) |
| 488 | return false; |
| 489 | |
| 490 | valuesMap[priorValue] = maybeValue.value(); |
| 491 | } |
| 492 | |
| 493 | return true; |
| 494 | } |
| 495 | |
| 496 | bool TosaReduceTransposes::userNotContainedInValidTransposeDependencies( |
| 497 | Operation *user, std::set<TransposeOp> &validTransposes, |
| 498 | std::vector<std::pair<TransposeOp, SetVector<Operation *>>> |
| 499 | &transposeInfo) { |
| 500 | return llvm::none_of( |
| 501 | Range&: transposeInfo, |
| 502 | P: [&validTransposes, |
| 503 | user](const std::pair<TransposeOp, SetVector<Operation *>> &info) { |
| 504 | const auto &[transposeOp, dependentOps] = info; |
| 505 | return validTransposes.count(x: transposeOp) && |
| 506 | dependentOps.contains(key: user); |
| 507 | }); |
| 508 | } |
| 509 | |
| 510 | // Dependencies are valid for an operation if none of them occur outside |
| 511 | // of the proper fan-in cones of the hoisted TransposeOp with the same perms |
| 512 | // that we can replace. Described in more detail within. |
| 513 | bool TosaReduceTransposes::dependenciesAreValid( |
| 514 | ArrayRef<int32_t> perms, const SetVector<Operation *> &dependentOps, |
| 515 | std::set<TransposeOp> &validTransposes, |
| 516 | std::vector<std::pair<TransposeOp, SetVector<Operation *>>> |
| 517 | &transposeInfo) { |
| 518 | for (Operation *op : dependentOps) { |
| 519 | |
| 520 | // It's OK wherever ConstOp has uses -- in the worst case, we duplicate. |
| 521 | // This can be changed later if we find the memory impact is too high. |
| 522 | if (llvm::isa<ConstOp>(Val: op)) |
| 523 | continue; |
| 524 | |
| 525 | for (OpOperand &use : op->getUses()) { |
| 526 | // Want the uses to be (1) contained in the dependentOps of other |
| 527 | // validTransposes, or (2) to be directly used in a TransposeOp with the |
| 528 | // same perms. For (2) it means the fan-in is a subset of our |
| 529 | // dependentOps, so it is also a validTranspose that will eventually be |
| 530 | // replaced. |
| 531 | Operation *user = use.getOwner(); |
| 532 | if (auto otherTranspose = llvm::dyn_cast<TransposeOp>(Val: user)) { |
| 533 | // Can later think about cases where transpose -> transpose |
| 534 | // or reshape -> transpose, where the transposes are not necessarily |
| 535 | // the same perms as the hoisted, if implementing a more general |
| 536 | // transform. These could be permitted. |
| 537 | if (!llvm::equal(LRange&: perms, RRange: otherTranspose.getPerms())) |
| 538 | return false; |
| 539 | } else if (userNotContainedInValidTransposeDependencies( |
| 540 | user, validTransposes, transposeInfo)) { |
| 541 | return false; |
| 542 | } |
| 543 | } |
| 544 | } |
| 545 | |
| 546 | return true; |
| 547 | } |
| 548 | |
| 549 | // Getting the set of TransposeOp that we can replace without causing |
| 550 | // the old fan-in cones of any TransposeOp to remain "live", i.e, -- not being |
| 551 | // dead code. This is done by iterating the set until convergence, since |
| 552 | // if you are used outside your own fan-in cone, it's possible to be used |
| 553 | // in another fan-in cone of a TransposeOp that is being replaced -- unless |
| 554 | // we find that that one has a usage outside of it too. |
| 555 | std::set<TransposeOp> TosaReduceTransposes::getGoodReplacements( |
| 556 | ArrayRef<int32_t> perms, |
| 557 | std::vector<std::pair<TransposeOp, SetVector<Operation *>>> |
| 558 | &transposeInfo) { |
| 559 | // Initially, we assume they are all good to replace, |
| 560 | // and we whittle them down based on our criteria. |
| 561 | std::set<TransposeOp> ableToReplace; |
| 562 | for (const auto &[transposeOp, _] : transposeInfo) |
| 563 | ableToReplace.insert(x: transposeOp); |
| 564 | |
| 565 | bool gotRid; |
| 566 | do { |
| 567 | gotRid = false; |
| 568 | for (const auto &[transposeOp, dependentOps] : transposeInfo) { |
| 569 | // We don't care about it. Already invalidated. |
| 570 | if (!ableToReplace.count(x: transposeOp)) |
| 571 | continue; |
| 572 | |
| 573 | // Check for validity. |
| 574 | if (!dependenciesAreValid(perms, dependentOps, validTransposes&: ableToReplace, |
| 575 | transposeInfo)) { |
| 576 | ableToReplace.erase(x: transposeOp); |
| 577 | gotRid = true; |
| 578 | break; |
| 579 | } |
| 580 | } |
| 581 | |
| 582 | } while (gotRid); |
| 583 | |
| 584 | return ableToReplace; |
| 585 | } |
| 586 | |
| 587 | void TosaReduceTransposes::runOnOperation() { |
| 588 | // We want to operate only within a single block. |
| 589 | if (!getOperation().getRegion().hasOneBlock()) |
| 590 | return; |
| 591 | |
| 592 | IRRewriter rewriter(&getContext()); |
| 593 | // For each perms, maintain a mapping for converted ops, avoid duplication. |
| 594 | DenseMap<ArrayRef<int32_t>, DenseMap<Value, Value>> permsToValues; |
| 595 | // For each perms, we keep track of which TransposeOp are eligible |
| 596 | // for replacement alongside their dependentOps. |
| 597 | DenseMap<ArrayRef<int32_t>, |
| 598 | std::vector<std::pair<TransposeOp, SetVector<Operation *>>>> |
| 599 | permsToTransposeInfo; |
| 600 | |
| 601 | // Necessary for lifetime, since DenseMap keeps a copy of the ArrayRef. |
| 602 | // Use SmallVector for perms (common-case is <= 4) but std::vector otherwise |
| 603 | // since no guarantee of smallness. |
| 604 | std::vector<SmallVector<int32_t>> collectedPerms; |
| 605 | |
| 606 | // This keeps track of the order across all eligible-for-replacement |
| 607 | // TransposeOp and their perms, a necessity for the final replacements. |
| 608 | std::stack<std::pair<TransposeOp, ArrayRef<int32_t>>> totalTransposeOrder; |
| 609 | |
| 610 | // We want to reserve the space up front, since SmallVector stores some data |
| 611 | // internally and the ArrayRef can reference that, which we don't want to get |
| 612 | // invalidated. |
| 613 | size_t expectedMaxPerms = 0; |
| 614 | getOperation().walk(callback: [&](TransposeOp) { expectedMaxPerms += 1; }); |
| 615 | collectedPerms.reserve(n: expectedMaxPerms); |
| 616 | |
| 617 | getOperation().walk(callback: [&](TransposeOp transposeOp) { |
| 618 | SetVector<Operation *> dependentOps; |
| 619 | collectedPerms.emplace_back(); |
| 620 | SmallVector<int32_t> &perms = collectedPerms.back(); |
| 621 | |
| 622 | // Dynamic shapes are OK, but the incompatible ones will be rejected later. |
| 623 | auto input = transposeOp.getInput1(); |
| 624 | auto output = transposeOp.getOutput(); |
| 625 | |
| 626 | // However, we don't support unranked tensors. |
| 627 | if (!llvm::isa<RankedTensorType>(Val: input.getType()) || |
| 628 | !llvm::isa<RankedTensorType>(Val: output.getType())) |
| 629 | return; |
| 630 | |
| 631 | llvm::append_range(C&: perms, R: transposeOp.getPerms()); |
| 632 | |
| 633 | // We let --canonicalize deal with identity transpose. |
| 634 | if (llvm::equal(LRange: llvm::seq<int32_t>(Begin: 0, End: perms.size()), RRange&: perms)) |
| 635 | return; |
| 636 | |
| 637 | // Can fail if some set of basic invariants is not met that we want to |
| 638 | // perform our conversions. |
| 639 | if (!collectFanIn(op: input.getDefiningOp(), collected&: dependentOps)) |
| 640 | return; |
| 641 | |
| 642 | // Want to associate valuesMap for already converted of the same perms, |
| 643 | // since it's possible multiple hoisted transposes w/ different perms |
| 644 | // converge on an op, which would result in different transformations. |
| 645 | DenseMap<Value, Value> &valuesMap = permsToValues[perms]; |
| 646 | |
| 647 | // Attempt to perform the conversions and placements into IR |
| 648 | // without turning inserted code "live". Also fills out valuesMap. |
| 649 | // Fails if there is an intermediary we do not support. |
| 650 | if (!convertDependentOps(dependentOps, valuesMap, rewriter, hoistedPerms: perms)) |
| 651 | // Some additional operations may have been inserted, but will be |
| 652 | // removed by dead code elimination. |
| 653 | return; |
| 654 | |
| 655 | // This should not happen. If it does -- it's unexpected, |
| 656 | // so we fail the pass. |
| 657 | if (!valuesMap.contains(Val: input)) |
| 658 | return signalPassFailure(); |
| 659 | |
| 660 | // It's possible the types are not compatible (because of dynamic shapes), |
| 661 | // and in these cases, want to resolve dynamic shapes before running the |
| 662 | // pass. |
| 663 | if (output.getType() != valuesMap.at(Val: input).getType()) |
| 664 | return; |
| 665 | |
| 666 | auto &transposeInfo = permsToTransposeInfo[perms]; |
| 667 | |
| 668 | // In general, we might also want to introduce "newDependentOps" |
| 669 | // if there are new usages that don't fall inside the original fan-ins |
| 670 | // (like the TransposeOp we insert for ReshapeOp), |
| 671 | // but in this case, that is specialized enough and overlaps |
| 672 | // with another direct-use TransposeOp case we need to cover anyway. |
| 673 | transposeInfo.emplace_back(args&: transposeOp, args&: dependentOps); |
| 674 | |
| 675 | // This is for the final replacement across all transposes. |
| 676 | totalTransposeOrder.emplace(args&: transposeOp, args&: perms); |
| 677 | }); |
| 678 | |
| 679 | // We want to do a full fan-in analysis on a perms-level, |
| 680 | // since if we do it on a multi-perms level, and they share (due to a shared |
| 681 | // dependency on a Reshape) then we would also get duplicate ops. |
| 682 | // Const is special cased. |
| 683 | std::set<TransposeOp> ableToReplace; |
| 684 | for (auto &[perms, transposeInfo] : permsToTransposeInfo) { |
| 685 | // Gives us back replacements that would never result in any duplicate |
| 686 | // operations being inserted by us in the IR (i.e, our goal is only to |
| 687 | // remove transposes, and not create a "new chain" to do so, but replace |
| 688 | // the existing chains). |
| 689 | // Ideally, --canonicalize is run before this pass, since it helps this |
| 690 | // analysis by removing dead code to allow more potentially acceptable |
| 691 | // transformations. |
| 692 | auto goodReplacementsForPerms = getGoodReplacements(perms, transposeInfo); |
| 693 | ableToReplace.insert(first: goodReplacementsForPerms.begin(), |
| 694 | last: goodReplacementsForPerms.end()); |
| 695 | } |
| 696 | |
| 697 | // We want to do replacement across all transposes |
| 698 | // in reverse order, due to invalidation of valuesMap mappings |
| 699 | // if we did it otherwise. |
| 700 | while (!totalTransposeOrder.empty()) { |
| 701 | auto [transposeOp, perms] = totalTransposeOrder.top(); |
| 702 | totalTransposeOrder.pop(); |
| 703 | |
| 704 | if (ableToReplace.count(x: transposeOp) == 0) |
| 705 | continue; |
| 706 | |
| 707 | auto &valuesMap = permsToValues[perms]; |
| 708 | auto input = transposeOp.getInput1(); |
| 709 | |
| 710 | // The purpose of this reverse iteration |
| 711 | // is to avoid valuesMap invalidation. If it happens, |
| 712 | // something is wrong. |
| 713 | if (!valuesMap.contains(Val: input)) |
| 714 | return signalPassFailure(); |
| 715 | |
| 716 | rewriter.replaceOp(op: transposeOp, newValues: valuesMap.at(Val: input)); |
| 717 | } |
| 718 | |
| 719 | // We can remove all dead code by going in reverse. |
| 720 | // This is because we would remove usages before we |
| 721 | // see the users. |
| 722 | getOperation().walk<WalkOrder::PostOrder, ReverseIterator>( |
| 723 | callback: [&](Operation *op) { |
| 724 | if (isOpTriviallyDead(op)) |
| 725 | rewriter.eraseOp(op); |
| 726 | }); |
| 727 | } |
| 728 | |
| 729 | } // namespace |
| 730 | |