[PATCH] D151492: Add fastmath attributes to llvm.call_intrinsic
This revision was automatically updated to reflect the committed changes.
Closed by commit rG9346dc6f675e: Add fastmath attributes to llvm.call_intrinsic
(authored by electriclilies, committed by Mogball).
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D151492/new/
https://reviews.llvm.org/D151492
Files:
mlir/include/mlir/Dialect/LLVMIR/LLVMIntrinsicOps.td
mlir/lib/Target/LLVMIR/Dialect/LLVMIR/LLVMToLLVMIRTranslation.cpp
mlir/test/Dialect/LLVMIR/call-intrin.mlir
Index: mlir/test/Dialect/LLVMIR/call-intrin.mlir
===
--- mlir/test/Dialect/LLVMIR/call-intrin.mlir
+++ mlir/test/Dialect/LLVMIR/call-intrin.mlir
@@ -5,13 +5,13 @@
// CHECK: declare ptr @malloc(i64)
// CHECK: declare void @free(ptr)
// CHECK: define <4 x float> @round_sse41() {
-// CHECK: %1 = call <4 x float> @llvm.x86.sse41.round.ss(<4 x float> , <4 x float> , i32 1)
+// CHECK: %1 = call reassoc <4 x float> @llvm.x86.sse41.round.ss(<4 x float>
, <4 x float> , i32 1)
// CHECK: ret <4 x float> %1
// CHECK: }
llvm.func @round_sse41() -> vector<4xf32> {
%0 = llvm.mlir.constant(1 : i32) : i32
%1 = llvm.mlir.constant(dense<0.2> : vector<4xf32>) : vector<4xf32>
-%res = llvm.call_intrinsic "llvm.x86.sse41.round.ss"(%1, %1, %0) :
(vector<4xf32>, vector<4xf32>, i32) -> vector<4xf32> {}
+%res = llvm.call_intrinsic "llvm.x86.sse41.round.ss"(%1, %1, %0) :
(vector<4xf32>, vector<4xf32>, i32) -> vector<4xf32> {fastmathFlags =
#llvm.fastmath}
llvm.return %res: vector<4xf32>
}
Index: mlir/lib/Target/LLVMIR/Dialect/LLVMIR/LLVMToLLVMIRTranslation.cpp
===
--- mlir/lib/Target/LLVMIR/Dialect/LLVMIR/LLVMToLLVMIRTranslation.cpp
+++ mlir/lib/Target/LLVMIR/Dialect/LLVMIR/LLVMToLLVMIRTranslation.cpp
@@ -95,7 +95,7 @@
/// Builder for LLVM_CallIntrinsicOp
static LogicalResult
-convertCallLLVMIntrinsicOp(CallIntrinsicOp &op, llvm::IRBuilderBase &builder,
+convertCallLLVMIntrinsicOp(CallIntrinsicOp op, llvm::IRBuilderBase &builder,
LLVM::ModuleTranslation &moduleTranslation) {
llvm::Module *module = builder.GetInsertBlock()->getModule();
llvm::Intrinsic::ID id =
@@ -114,6 +114,8 @@
} else {
fn = llvm::Intrinsic::getDeclaration(module, id, {});
}
+ FastmathFlagsInterface itf = op;
+ builder.setFastMathFlags(getFastmathFlags(itf));
auto *inst =
builder.CreateCall(fn, moduleTranslation.lookupValues(op.getOperands()));
Index: mlir/include/mlir/Dialect/LLVMIR/LLVMIntrinsicOps.td
===
--- mlir/include/mlir/Dialect/LLVMIR/LLVMIntrinsicOps.td
+++ mlir/include/mlir/Dialect/LLVMIR/LLVMIntrinsicOps.td
@@ -867,19 +867,24 @@
// CallIntrinsicOp
//======//
-def LLVM_CallIntrinsicOp : LLVM_Op<"call_intrinsic"> {
+def LLVM_CallIntrinsicOp
+: LLVM_Op<"call_intrinsic",
+ [DeclareOpInterfaceMethods]> {
let summary = "Call to an LLVM intrinsic function.";
let description = [{
Call the specified llvm intrinsic. If the intrinsic is overloaded, use
the MLIR function type of this op to determine which intrinsic to call.
}];
- let arguments = (ins StrAttr:$intrin, Variadic:$args);
+ let arguments = (ins StrAttr:$intrin, Variadic:$args,
+ DefaultValuedAttr:$fastmathFlags);
let results = (outs Variadic:$results);
let llvmBuilder = [{
return convertCallLLVMIntrinsicOp(op, builder, moduleTranslation);
}];
let assemblyFormat = [{
-$intrin `(` $args `)` `:` functional-type($args, $results) attr-dict
+$intrin `(` $args `)` `:` functional-type($args, $results)
+ custom(attr-dict)
}];
}
Index: mlir/test/Dialect/LLVMIR/call-intrin.mlir
===
--- mlir/test/Dialect/LLVMIR/call-intrin.mlir
+++ mlir/test/Dialect/LLVMIR/call-intrin.mlir
@@ -5,13 +5,13 @@
// CHECK: declare ptr @malloc(i64)
// CHECK: declare void @free(ptr)
// CHECK: define <4 x float> @round_sse41() {
-// CHECK: %1 = call <4 x float> @llvm.x86.sse41.round.ss(<4 x float> , <4 x float> , i32 1)
+// CHECK: %1 = call reassoc <4 x float> @llvm.x86.sse41.round.ss(<4 x float> , <4 x float> , i32 1)
// CHECK: ret <4 x float> %1
// CHECK: }
llvm.func @round_sse41() -> vector<4xf32> {
%0 = llvm.mlir.constant(1 : i32) : i32
%1 = llvm.mlir.constant(dense<0.2> : vector<4xf32>) : vector<4xf32>
-%res = llvm.call_intrinsic "llvm.x86.sse41.round.ss"(%1, %1, %0) : (vector<4xf32>, vector<4xf32>, i32) -> vector<4xf32> {}
+%res = llvm.call_intrinsic "llvm.x86.sse41.round.ss"(%1, %1, %0) : (vector<4xf32>, vector<4xf32>, i32) -> vector<4xf32> {fastmathFlags = #llvm.fastmath}
llvm.return %res: vector<4xf32>
}
Index: mlir/lib/Target/LLVMIR/Dialect/LLVMIR/LLVMToLLVMIRTra
[PATCH] D151492: Add fastmath attributes to llvm.call_intrinsic
Mogball accepted this revision.
Mogball added inline comments.
This revision is now accepted and ready to land.
Comment at: mlir/include/mlir/Dialect/LLVMIR/LLVMIntrinsicOps.td:878
}];
- let arguments = (ins StrAttr:$intrin, Variadic:$args);
+ let arguments = (ins StrAttr:$intrin, Variadic:$args,
DefaultValuedAttr:$fastmathFlags);
let results = (outs Variadic:$results);
here as well please
Comment at: mlir/include/mlir/Dialect/LLVMIR/LLVMIntrinsicOps.td:883
}];
let assemblyFormat = [{
+$intrin `(` $args `)` `:` functional-type($args, $results)
custom(attr-dict)
and this one
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D151492/new/
https://reviews.llvm.org/D151492
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D151492: Add fastmath attributes to llvm.call_intrinsic
Mogball added inline comments.
Comment at: mlir/lib/Target/LLVMIR/Dialect/LLVMIR/LLVMToLLVMIRTranslation.cpp:98
static LogicalResult
convertCallLLVMIntrinsicOp(CallIntrinsicOp &op, llvm::IRBuilderBase &builder,
LLVM::ModuleTranslation &moduleTranslation) {
Mogball wrote:
> electriclilies wrote:
> > Mogball wrote:
> > > Mogball wrote:
> > > > electriclilies wrote:
> > > > > Mogball wrote:
> > > > > > I think the problem with the cast below is that this is passed by
> > > > > > reference. You should not pass operation handles by reference.
> > > > > I think I can't pass it by value because it's const though..
> > > > where is it const?
> > > if it were const, it wouldn't bind to a non-const reference anyways
> > If I just try to pass the op into the dyn_cast, it gives this error, which
> > says that the op is a const
> > ```
> > /home/lily/modular/third-party/llvm-project/llvm/include/llvm/Support/Casting.h:64:65:
> > error: cannot initialize a parameter of type 'mlir::Operation *' with an
> > rvalue of type 'const mlir::LLVM::CallIntrinsicOp *
> > ```
> did you drop the reference?
```
CallIntrinsicOp &op
```
delete the `&`. You should never do this for ops anyways
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D151492/new/
https://reviews.llvm.org/D151492
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D151492: Add fastmath attributes to llvm.call_intrinsic
Mogball added inline comments.
Comment at: mlir/lib/Target/LLVMIR/Dialect/LLVMIR/LLVMToLLVMIRTranslation.cpp:98
static LogicalResult
convertCallLLVMIntrinsicOp(CallIntrinsicOp &op, llvm::IRBuilderBase &builder,
LLVM::ModuleTranslation &moduleTranslation) {
electriclilies wrote:
> Mogball wrote:
> > Mogball wrote:
> > > electriclilies wrote:
> > > > Mogball wrote:
> > > > > I think the problem with the cast below is that this is passed by
> > > > > reference. You should not pass operation handles by reference.
> > > > I think I can't pass it by value because it's const though..
> > > where is it const?
> > if it were const, it wouldn't bind to a non-const reference anyways
> If I just try to pass the op into the dyn_cast, it gives this error, which
> says that the op is a const
> ```
> /home/lily/modular/third-party/llvm-project/llvm/include/llvm/Support/Casting.h:64:65:
> error: cannot initialize a parameter of type 'mlir::Operation *' with an
> rvalue of type 'const mlir::LLVM::CallIntrinsicOp *
> ```
did you drop the reference?
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D151492/new/
https://reviews.llvm.org/D151492
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D151492: Add fastmath attributes to llvm.call_intrinsic
Mogball added inline comments.
Comment at: mlir/lib/Target/LLVMIR/Dialect/LLVMIR/LLVMToLLVMIRTranslation.cpp:98
static LogicalResult
convertCallLLVMIntrinsicOp(CallIntrinsicOp &op, llvm::IRBuilderBase &builder,
LLVM::ModuleTranslation &moduleTranslation) {
Mogball wrote:
> electriclilies wrote:
> > Mogball wrote:
> > > I think the problem with the cast below is that this is passed by
> > > reference. You should not pass operation handles by reference.
> > I think I can't pass it by value because it's const though..
> where is it const?
if it were const, it wouldn't bind to a non-const reference anyways
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D151492/new/
https://reviews.llvm.org/D151492
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D151492: Add fastmath attributes to llvm.call_intrinsic
Mogball added inline comments.
Comment at: mlir/lib/Target/LLVMIR/Dialect/LLVMIR/LLVMToLLVMIRTranslation.cpp:98
static LogicalResult
convertCallLLVMIntrinsicOp(CallIntrinsicOp &op, llvm::IRBuilderBase &builder,
LLVM::ModuleTranslation &moduleTranslation) {
electriclilies wrote:
> Mogball wrote:
> > I think the problem with the cast below is that this is passed by
> > reference. You should not pass operation handles by reference.
> I think I can't pass it by value because it's const though..
where is it const?
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D151492/new/
https://reviews.llvm.org/D151492
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D151492: Add fastmath attributes to llvm.call_intrinsic
Mogball added inline comments.
Comment at: mlir/include/mlir/Dialect/LLVMIR/LLVMIntrinsicOps.td:870
-def LLVM_CallIntrinsicOp : LLVM_Op<"call_intrinsic"> {
+def LLVM_CallIntrinsicOp : LLVM_Op<"call_intrinsic",
[DeclareOpInterfaceMethods]> {
let summary = "Call to an LLVM intrinsic function.";
please fit this definition into 80 characters wide
Comment at: mlir/lib/Target/LLVMIR/Dialect/LLVMIR/LLVMToLLVMIRTranslation.cpp:98
static LogicalResult
convertCallLLVMIntrinsicOp(CallIntrinsicOp &op, llvm::IRBuilderBase &builder,
LLVM::ModuleTranslation &moduleTranslation) {
I think the problem with the cast below is that this is passed by reference.
You should not pass operation handles by reference.
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D151492/new/
https://reviews.llvm.org/D151492
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops
This revision was automatically updated to reflect the committed changes.
Closed by commit rGb508c5649f5e: [MLIR] Add a utility to sort the operands of
commutative ops (authored by srishti-pm, committed by Mogball).
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D124750/new/
https://reviews.llvm.org/D124750
Files:
mlir/include/mlir/Transforms/CommutativityUtils.h
mlir/lib/Transforms/Utils/CMakeLists.txt
mlir/lib/Transforms/Utils/CommutativityUtils.cpp
mlir/test/Transforms/test-commutativity-utils.mlir
mlir/test/lib/Dialect/Test/TestOps.td
mlir/test/lib/Transforms/CMakeLists.txt
mlir/test/lib/Transforms/TestCommutativityUtils.cpp
mlir/tools/mlir-opt/mlir-opt.cpp
Index: mlir/tools/mlir-opt/mlir-opt.cpp
===
--- mlir/tools/mlir-opt/mlir-opt.cpp
+++ mlir/tools/mlir-opt/mlir-opt.cpp
@@ -57,6 +57,7 @@
void registerVectorizerTestPass();
namespace test {
+void registerCommutativityUtils();
void registerConvertCallOpPass();
void registerInliner();
void registerMemRefBoundCheck();
@@ -149,6 +150,7 @@
registerVectorizerTestPass();
registerTosaTestQuantUtilAPIPass();
+ mlir::test::registerCommutativityUtils();
mlir::test::registerConvertCallOpPass();
mlir::test::registerInliner();
mlir::test::registerMemRefBoundCheck();
Index: mlir/test/lib/Transforms/TestCommutativityUtils.cpp
===
--- /dev/null
+++ mlir/test/lib/Transforms/TestCommutativityUtils.cpp
@@ -0,0 +1,48 @@
+//===- TestCommutativityUtils.cpp - Pass to test the commutativity utility-===//
+//
+// 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 pass tests the functionality of the commutativity utility pattern.
+//
+//===--===//
+
+#include "mlir/Transforms/CommutativityUtils.h"
+
+#include "TestDialect.h"
+#include "mlir/Pass/Pass.h"
+#include "mlir/Transforms/GreedyPatternRewriteDriver.h"
+
+using namespace mlir;
+
+namespace {
+
+struct CommutativityUtils
+: public PassWrapper> {
+ MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(CommutativityUtils)
+
+ StringRef getArgument() const final { return "test-commutativity-utils"; }
+ StringRef getDescription() const final {
+return "Test the functionality of the commutativity utility";
+ }
+
+ void runOnOperation() override {
+auto func = getOperation();
+auto *context = &getContext();
+
+RewritePatternSet patterns(context);
+populateCommutativityUtilsPatterns(patterns);
+
+(void)applyPatternsAndFoldGreedily(func, std::move(patterns));
+ }
+};
+} // namespace
+
+namespace mlir {
+namespace test {
+void registerCommutativityUtils() { PassRegistration(); }
+} // namespace test
+} // namespace mlir
Index: mlir/test/lib/Transforms/CMakeLists.txt
===
--- mlir/test/lib/Transforms/CMakeLists.txt
+++ mlir/test/lib/Transforms/CMakeLists.txt
@@ -1,5 +1,6 @@
# Exclude tests from libMLIR.so
add_mlir_library(MLIRTestTransforms
+ TestCommutativityUtils.cpp
TestConstantFold.cpp
TestControlFlowSink.cpp
TestInlining.cpp
Index: mlir/test/lib/Dialect/Test/TestOps.td
===
--- mlir/test/lib/Dialect/Test/TestOps.td
+++ mlir/test/lib/Dialect/Test/TestOps.td
@@ -1186,11 +1186,21 @@
let hasFolder = 1;
}
+def TestAddIOp : TEST_Op<"addi"> {
+ let arguments = (ins I32:$op1, I32:$op2);
+ let results = (outs I32);
+}
+
def TestCommutativeOp : TEST_Op<"op_commutative", [Commutative]> {
let arguments = (ins I32:$op1, I32:$op2, I32:$op3, I32:$op4);
let results = (outs I32);
}
+def TestLargeCommutativeOp : TEST_Op<"op_large_commutative", [Commutative]> {
+ let arguments = (ins I32:$op1, I32:$op2, I32:$op3, I32:$op4, I32:$op5, I32:$op6, I32:$op7);
+ let results = (outs I32);
+}
+
def TestCommutative2Op : TEST_Op<"op_commutative2", [Commutative]> {
let arguments = (ins I32:$op1, I32:$op2);
let results = (outs I32);
Index: mlir/test/Transforms/test-commutativity-utils.mlir
===
--- /dev/null
+++ mlir/test/Transforms/test-commutativity-utils.mlir
@@ -0,0 +1,116 @@
+// RUN: mlir-opt %s -test-commutativity-utils | FileCheck %s
+
+// CHECK-LABEL: @test_small_pattern_1
+func.func @test_small_pattern_1(%arg0 : i32) -> i32 {
+ // CHECK-NEXT: %[[ARITH_CONST:.*]] = arith.constant
+ %0 = arith.constant 45 : i32
+
+ // CHECK-NEXT: %[[TEST_ADD:.*]] = "test.addi"
+ %1 = "test.addi"(%arg0, %arg0): (i32, i32) -> i32
+
+ // CHECK-NEXT: %[[ARITH_ADD:.*]] = arith.addi
+ %2 = arith
[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops
Mogball added a comment. I'm referring to the nitty gritty details of the while loop inside the comparator. It looks pretty tight to me right now. If the operands are already sorted, worst-case each operand is compared against only its neighbours. Unfortunately, without extra bookkeeping, BFS will still need to iterate when necessary Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D124750/new/ https://reviews.llvm.org/D124750 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops
Mogball accepted this revision. Mogball added a comment. This revision is now accepted and ready to land. Got a few small nits but otherwise LGTM. Thanks for all the hard work! This looks really solid now. I haven't thought too hard about the performance of that while loop but it seems good enough to land for now. Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:246 +// `constCommOperandA`'s "key" is smaller. +auto CommutativeOperandComparator = +[](const std::unique_ptr &constCommOperandA, Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:252 + + std::unique_ptr &commOperandA = + const_cast &>( Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:255 + constCommOperandA); + std::unique_ptr &commOperandB = + const_cast &>( Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D124750/new/ https://reviews.llvm.org/D124750 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops
Mogball added inline comments. Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:238 +// Stores the mapping between an operand and its BFS traversal information. +DenseMap operandToItsBFSMap; + srishti-pm wrote: > Mogball wrote: > > Why can't you sort the OperandBFS directly to avoid the hash map? > Because comparators are not allowed to modify their input arguments. The arguments have to be const references? If so, just const_cast Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D124750/new/ https://reviews.llvm.org/D124750 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops
Mogball added inline comments.
Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:238
+// Stores the mapping between an operand and its BFS traversal information.
+DenseMap operandToItsBFSMap;
+
Why can't you sort the OperandBFS directly to avoid the hash map?
Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:286
+for (unsigned i = 0, e = op->getNumOperands(); i < e; i++) {
+ OperandBFS *bfs = new OperandBFS();
+ bfs->pushAncestor(operands[i].getDefiningOp());
Can you use unique_ptr so that the memory doesn't leak?
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D124750/new/
https://reviews.llvm.org/D124750
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops
Mogball added a comment. I'm not sure how to check the no-op case without constructing at least a queue. Even assuming only 2 commutative operands, if they look the same `depth=1`, then the comparison has to iterate. Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D124750/new/ https://reviews.llvm.org/D124750 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops
Mogball added inline comments.
Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:329-353
+ assert(frontPosition >= 0 && frontPosition < bfsOfOperands.size() &&
+ "`frontPosition` should be valid");
+ unsigned positionOfOperandToShift;
+ bool foundOperandToShift = false;
+ for (auto &indexedBfsOfOperand : llvm::enumerate(bfsOfOperands)) {
+std::unique_ptr &bfsOfOperand = indexedBfsOfOperand.value();
+if (bfsOfOperand->isSorted)
srishti-pm wrote:
> Mogball wrote:
> > srishti-pm wrote:
> > > Mogball wrote:
> > > > There is no way you need this much code. A `std::swap` between the
> > > > current operand and the first unsorted position should be enough.
> > > If I do a swap, the sorting will no longer be stable and I believe that
> > > there was a discussion that concluded with the fact that "we want stable
> > > sorting".
> > That's true, but shifting like this is very slow as well. At this point,
> > you might want to give `std::stable_sort` with a custom comparator that
> > does extra BFS iterations on demand a try.
> So, this is what I think:
>
> The number of commutative operands is not expected to be huge. So, we can
> afford to do shifting. In most cases, we wouldn't have to shift more than 1
> or 2 positions. But, the custom comparator might cost us a lot, considering
> that each BFS could potentially be very large, especially for deep learning
> models. So, doing the BFS traversals again and again for the same operand,
> even though caching will be involved, doesn't sound like a good idea to me.
>
> What are your views?
Very rough estimate: on its own, this function is N. Finding the smallest key
is N, and then finding all matching elements is N. This function is called for
each operand that needs to be moved, but the number of such operands decreases.
So the sort itself averages out to be 3N^2 iterations over the operand list.
Now for traversals, doing BFS on demand inside the comparator doesn't mean it
has to restart every time. It would do extra iterations on top of existing
iteration results only when needed to break ties. In your case, you do an extra
iteration of BFS for all operands if the current smallest key is identical, not
just for the ones needed. It's hard to estimate the number of iterations of
BFS, but certainly it's more in your case. Using `std::stable_sort` would also
bring the complexity down to N logN
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D124750/new/
https://reviews.llvm.org/D124750
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops
Mogball added inline comments.
Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:76
+ // `CONSTANT_OP` and `opName` remains "".
+ type = CONSTANT_OP;
+}
srishti-pm wrote:
> Mogball wrote:
> > Constant ops could be sorted by name as well.
> The only reason we separated constant ops from the non-constant ops was
> because the former are canonicalized to the right (as a stable sort) by
> existing canonicalizations. And, we didn't want our algorithm to conflict
> with these existing canonicalizations. That is the reason I am not sorting
> them by name and just keeping them to the right (as a stable sort).
I know. You can sort them separately from regular ops and also by name and the
overall behaviour would be the same.
Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:269
+ArrayRef> bfsOfOperands,
+bool &hasOneOperandWithKey) {
+ bool keyFound = false;
srishti-pm wrote:
> Mogball wrote:
> > This flag is not necessary because you can just check
> > `bfsOfOperandsWithKey.size() == 1`
> `.size()` is an O(N) operation and that is why I usually try to avoid it. Do
> you still agree we should use it here? I understand that N is an expectedly
> small value.
Size is constant time
Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:278-279
+if (compareKeys(key, currentKey) == 0) {
+ bfsOfOperandsWithKey.push_back(
+ std::make_unique(*bfsOfOperand));
+ if (keyFound)
srishti-pm wrote:
> Mogball wrote:
> > You don't need to make a copy. In fact, I think you should just track the
> > indices.
> I agree. But, we had discussed to store operands instead of indices and
> that's why I did this. I will change this to use indices again (keeping other
> things unchanged).
I mean you can have list (not a set) of indices to shift
Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:329-353
+ assert(frontPosition >= 0 && frontPosition < bfsOfOperands.size() &&
+ "`frontPosition` should be valid");
+ unsigned positionOfOperandToShift;
+ bool foundOperandToShift = false;
+ for (auto &indexedBfsOfOperand : llvm::enumerate(bfsOfOperands)) {
+std::unique_ptr &bfsOfOperand = indexedBfsOfOperand.value();
+if (bfsOfOperand->isSorted)
srishti-pm wrote:
> Mogball wrote:
> > There is no way you need this much code. A `std::swap` between the current
> > operand and the first unsorted position should be enough.
> If I do a swap, the sorting will no longer be stable and I believe that there
> was a discussion that concluded with the fact that "we want stable sorting".
That's true, but shifting like this is very slow as well. At this point, you
might want to give `std::stable_sort` with a custom comparator that does extra
BFS iterations on demand a try.
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D124750/new/
https://reviews.llvm.org/D124750
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops
Mogball added inline comments. Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:523 + shiftTheSmallestUnsortedOperandsToTheSmallestUnsortedPositions( + bfsOfOperands, smallestUnsortedPosition); + And then you'll never need to check `isSorted` again. Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D124750/new/ https://reviews.llvm.org/D124750 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops
Mogball added a comment.
I'm glad the `DenseSet`s are gone, but my three-ish biggest gripes are:
- The algorithm is conceptually simple, but there is way more code than is
necessary to achieve it.
- More comments (excluding "doc" comments) than code is generally not a good
sign
- The implementation is still inefficient in a lot of obvious ways.
Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:10-11
+// This file implements a commutativity utility pattern and a function to
+// populate this pattern. The function is intended to be used inside passes to
+// simplify the matching of commutative operations.
+//
Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:21-38
+/// Stores the "ancestor" of an operand of some op. The operand of any op is
+/// produced by a set of ops and block arguments. Each of these ops and block
+/// arguments is called an "ancestor" of this operand.
+struct Ancestor {
+ /// Stores true when the "ancestor" is an op and false when the "ancestor" is
+ /// a block argument.
+ bool isOp;
This class isn't necessary. `Ancestor` can just be `Operation *`. If it's null,
then we know it's a block argument (the bool flag is redundant).
Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:40
+
+/// Declares various "types" of ancestors.
+enum AncestorType {
Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:65-66
+if (!ancestor.isOp) {
+ // When `ancestor` is a block argument, we assign `type` as
+ // `BLOCK_ARGUMENT` and `opName` remains "".
+ type = BLOCK_ARGUMENT;
My biggest complaint with respect to readability is that there are more
comments than code. This is fine if the comment has a big explanation about the
algorithm and how keys are represented, especially with a nice ASCII diagram as
you have below. But if this constructor had 0 comments except maybe "Only
non-constant ops are sorted by name", it would be perfectly fine.
Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:76
+ // `CONSTANT_OP` and `opName` remains "".
+ type = CONSTANT_OP;
+}
Constant ops could be sorted by name as well.
Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:88-96
+ bool operator<(const AncestorKey &key) const {
+if ((type == BLOCK_ARGUMENT && key.type != BLOCK_ARGUMENT) ||
+(type == NON_CONSTANT_OP && key.type == CONSTANT_OP))
+ return true;
+if ((key.type == BLOCK_ARGUMENT && type != BLOCK_ARGUMENT) ||
+(key.type == NON_CONSTANT_OP && type == CONSTANT_OP))
+ return false;
This should behave the same as the manually written comparator. `operator<` of
`std::tuple` compares the first element and then the next if the first is equal.
Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:110
+ /// operand at a particular point in time.
+ DenseSet visitedAncestors;
+
Since this is a set of pointers expected to be small, you can use `SmallPtrSet`
for a big efficiency boost (linear scan instead of hashing when small).
Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:148-149
+
+ /// Stores true iff the operand has been assigned a sorted position yet.
+ bool isSorted = false;
+
Since you are moving sorted operands into their sorted position and tracking
the unsorted range, you shouldn't even need this flag because you will always
know the sorted and unsorted subranges.
There are multiple loops in which you iterate over the entire operand list but
skip those where this flag is set/unset. In those cases, you can always just
iterate the subrange of interest.
Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:155-159
+Ancestor ancestor(op);
+ancestorQueue.push(ancestor);
+if (ancestor.isOp)
+ visitedAncestors.insert(ancestor.op);
+return;
Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:162-177
+ /// Pop the ancestor from the front of the queue.
+ void popAncestor() {
+assert(!ancestorQueue.empty() &&
+ "to pop the ancestor from the front of the queue, the ancestor "
+ "queue should be non-empty");
+ancestorQueue.pop();
+return;
I would drop these helpers. `std::queue` will already assert if `pop` or
`front` are called on an empty queue.
Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:200-217
+ unsigned keyASize = keyA.size();
+ unsigned keyBSize = keyB.size();
+ unsigned smallestSize = keyASize;
+ if (keyBSize < smallestSize)
+smallestSize = keyBSize;
+
+ for (unsigned i = 0; i < smallestSize; i++) {
Comment at: mlir/lib/Transforms/Utils/Comm
[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops
Mogball added inline comments. Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:178 +using UniquePtrOperandBFS = std::unique_ptr; +using ArrayRefOperandBFS = ArrayRef; + Please remove these. They don't improve readability. Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D124750/new/ https://reviews.llvm.org/D124750 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops
Mogball added a comment. In principle, I think the algorithm is fine. I'm pretty sure you can rewrite bits of it to get rid of the map/sets. I'm only concerned about handling attributes. (e.g. `cmpi slt` vs `cmpi sgt`) Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D124750/new/ https://reviews.llvm.org/D124750 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops
Mogball added inline comments.
Comment at: mlir/include/mlir/Transforms/CommutativityUtils.h:211
+// If `op` is not commutative, do nothing.
+if (!op->template hasTrait())
+ return failure();
Mogball wrote:
> Please move the body `matchAndRewrite` into a source file. It only needs
> `Operation *`. And then all the structs/enum/utility functions in the header
> can be moved there as well.
This could stand to be a `static_assert`
Comment at: mlir/include/mlir/Transforms/CommutativityUtils.h:257
+ // smallest.
+ DenseSet smallestKeyIndices;
+ // Stores the indices of the unassigned operands whose key is the
largest.
Could you not change `getIndicesOfUnassigned...` to populate two lists of
operands and pass these to `assignSortedPositionTo` instead of using a set to
track the indices. You could put the operand index inside `OperandBFS` to keep
track.
Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:24
+bool mlir::hasAtLeastOneUnassignedOperand(
+SmallVector bfsOfOperands) {
+ for (OperandBFS *bfsOfOperand : bfsOfOperands) {
This function doesn't seem like it pays for itself -- `llvm::any_of`?
Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:92
+ // of `bfsOfOperands`.
+ SmallVector smallestKey, largestKey;
+ for (OperandBFS *bfsOfOperand : bfsOfOperands) {
These could all be `ArrayRef`s since you aren't modifying them
Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:167
+ // which is the key associated with a block argument.
+ mlir::BlockArgumentOrOpKey blockArgumentOrOpKey;
+ blockArgumentOrOpKey.type = BLOCK_ARGUMENT;
drop mlir::
Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:201
+ unsigned positionToAssign, Operation *op) {
+ if (keyIndices.contains(indexOfOperand) &&
+ (isTheOnlyKey || bfsOfOperand->ancestorQueue.empty())) {
This function doesn't seem like it pays for itself.
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D124750/new/
https://reviews.llvm.org/D124750
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops
Mogball added a comment.
I haven't thought too hard about the algorithm itself yet. I'm in the camp of
"let's move forward if it works". I have mostly trivial comments.
Comment at: clang/docs/tools/clang-formatted-files.txt:8451
mlir/lib/Transforms/SymbolPrivatize.cpp
+mlir/lib/Transforms/Utils/CommutativityUtils.cpp
mlir/lib/Transforms/Utils/ControlFlowSinkUtils.cpp
I don't think this file needs to be modified.
Comment at: mlir/include/mlir/Transforms/CommutativityUtils.h:24
+/// Declares various types of operations and block argument.
+enum BlockArgumentOrOpType {
+ /// Pertains to a block argument.
Why do all of these need to be exposed publicly? I think this file should only
contain `SortCommutativeOperands`.
Comment at: mlir/include/mlir/Transforms/CommutativityUtils.h:34
+/// Stores the "key" associated with a block argument or an operation.
+struct BlockArgumentOrOpKey {
+ /// Holds `BLOCK_ARGUMENT`, `NON_CONSTANT_OP`, or `CONSTANT_OP`, depending on
`using BlockArgumentOrOpKey = std::pair`
The default `operator<` for `std::pair` should work for you.
Comment at: mlir/include/mlir/Transforms/CommutativityUtils.h:140
+/// operand refers to one which has not been assigned a sorted position yet.
+bool hasAtLeastOneUnassignedOperand(SmallVector
bfsOfOperands);
+
`ArrayRef`
Comment at: mlir/include/mlir/Transforms/CommutativityUtils.h:161
+/// (C) `secondKey` < `firstKey` condition is defined likewise.
+int compareKeys(SmallVector firstKey,
+SmallVector secondKey);
Pass these both by `ArrayRef`
Comment at: mlir/include/mlir/Transforms/CommutativityUtils.h:174
+void getIndicesOfUnassignedOperandsWithSmallestAndLargestKeys(
+SmallVector bfsOfOperands,
+DenseSet &smallestKeyIndices,
`ArrayRef`
Comment at: mlir/include/mlir/Transforms/CommutativityUtils.h:186
+/// progression of the traversal.
+void updateKeys(SmallVector bfsOfOperands);
+
`ArrayRef`
Comment at: mlir/include/mlir/Transforms/CommutativityUtils.h:194
+DenseSet keyIndices, bool isTheOnlyKey,
+SmallVector &sortedOperands,
+unsigned positionToAssign, Operation *op);
`SmallVectorImpl`
Comment at: mlir/include/mlir/Transforms/CommutativityUtils.h:201
+void popFrontAndPushAdjacentUnvisitedAncestors(
+SmallVector bfsOfOperands);
+
`ArrayRef`
Comment at: mlir/include/mlir/Transforms/CommutativityUtils.h:211
+// If `op` is not commutative, do nothing.
+if (!op->template hasTrait())
+ return failure();
Please move the body `matchAndRewrite` into a source file. It only needs
`Operation *`. And then all the structs/enum/utility functions in the header
can be moved there as well.
Comment at: mlir/include/mlir/Transforms/CommutativityUtils.h:226
+for (Value operand : op->getOperands()) {
+ OperandBFS *bfsOfOperand = new OperandBFS();
+ bfsOfOperand->pushAncestor(operand.getDefiningOp());
memory leak?
Comment at: mlir/include/mlir/Transforms/CommutativityUtils.h:242
+// At first, all elements in it are initialized as null.
+SmallVector sortedOperands;
+for (unsigned i = 0; i < numOperands; i++)
`sortedOperands(numOperands, nullptr);`
Comment at: mlir/include/mlir/Transforms/CommutativityUtils.h:275
+ // sorting).
+ for (auto indexedBfsOfOperand : llvm::enumerate(bfsOfOperands)) {
+OperandBFS *bfsOfOperand = indexedBfsOfOperand.value();
Comment at: mlir/include/mlir/Transforms/CommutativityUtils.h:296
+ // to assign it a sorted position if possible (ensuring stable sorting).
+ for (auto indexedBfsOfOperand :
+ llvm::enumerate(llvm::reverse(bfsOfOperands))) {
Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:17
+
+#define DEBUG_TYPE "commutativity-utils"
+
unused?
Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:51
+/// (C) `secondKey` < `firstKey` condition is defined likewise.
+int mlir::compareKeys(SmallVector firstKey,
+ SmallVector secondKey) {
The doc of a public function shouldn't be repeated above the implementation.
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D124750/new/
https://reviews.llvm.org/D124750
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops
Mogball added a comment. I'm open to iterating in tree. Landing this utility first and then try adding it as a canonicalization SGTM. The string could be replaced with an array of tuples (yuck) for now. An enum (constant, block arg, everything else) plus the OperationName. Attributes need to be handled somehow possibly by adding the op's dictionary attribute and using a deep compare. Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D124750/new/ https://reviews.llvm.org/D124750 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops
Mogball added a comment. On the matter of whether this should be a canonicalization, my concern with this is that if an operation has its own preferred ordering of operands that conflicts with the sort, then this will cause canonicalization to loop infinitely. It's not actually the canonicalizer pass that moves constants to the right hand size. It's the folder. And it probably shouldn't be the folder that does this. So I'm open to making this part of canonicalization IF the sorted operand order produced by this utility is the canonical order of operands for commutative operations, so that conflicts and not possible. Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D124750/new/ https://reviews.llvm.org/D124750 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops
Mogball added a comment. I need to look at the algorithm in more detail, but I'm not a fan of using a string key. Concatenating strings to make compound keys is not very efficient and potentially brittle. Can you assign unique IDs and use an array of IDs instead? Comment at: mlir/include/mlir/Transforms/CommutativityUtils.h:24 + +void sortCommutativeOperands(Operation *op, PatternRewriter &rewriter); + Add documentation? Similar to what you have in the patch description. Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D124750/new/ https://reviews.llvm.org/D124750 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D116488: Add a misc-unused-parameters.CommentOutUnusedParameters to clang-tidy
Mogball added inline comments.
Comment at: clang-tools-extra/clang-tidy/misc/UnusedParametersCheck.cpp:157
// will clean this up afterwards.
-MyDiag << FixItHint::CreateReplacement(
-RemovalRange, (Twine(" /*") + Param->getName() + "*/").str());
+if (Options.get("CommentOutUnusedParameters", true))
+ MyDiag << FixItHint::CreateReplacement(
Oh I was thinking that the option would disable editing the parameter at all.
I.e. it would leave unused parameters untouched or remove the parameter from
the function signature altogether (if it can).
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D116488/new/
https://reviews.llvm.org/D116488
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
