This is an archive of the discontinued LLVM Phabricator instance.

[mlir][dataflow] Remove Lattice::isUninitialized().
ClosedPublic

Authored by phisiart on Aug 27 2022, 3:05 PM.

Details

Summary

Currently, for sparse analyses, we always store a Optional<ValueT> in each lattice element. When it's None, we consider the lattice element as uninitialized.

However:

  • Not all lattices have an uninitialized state. For example, Executable and PredecessorState have default values so they are always initialized.
  • In dense analyses, we don't have the concept of an uninitialized state.

Given these inconsistencies, this patch removes Lattice::isUninitialized(). Individual analysis states are now default-constructed. If the default state of an analysis can be considered as "uninitialized" then this analysis should implement the following logic:

  • Special join rule: join(uninitialized, any) == any.
  • Special bail out logic: if any of the input states is uninitialized, exit the transfer function early.

Depends On D132086

Diff Detail

Event Timeline

phisiart created this revision.Aug 27 2022, 3:05 PM
Herald added a project: Restricted Project. · View Herald Transcript
phisiart requested review of this revision.Aug 27 2022, 3:05 PM
phisiart edited the summary of this revision. (Show Details)Aug 27 2022, 3:18 PM
jsetoain resigned from this revision.Aug 29 2022, 4:29 AM
Mogball accepted this revision.Aug 29 2022, 8:52 AM
Mogball added inline comments.
mlir/include/mlir/Analysis/DataFlow/ConstantPropagationAnalysis.h
95

Can you replace Optional<Impl> with just an Attribute and a flag? Or at least do Optional<Attribute> since the dialect value doesn't place a role in the analysis very much.

This revision is now accepted and ready to land.Aug 29 2022, 8:52 AM
Mogball requested changes to this revision.Aug 29 2022, 8:52 AM
This revision now requires changes to proceed.Aug 29 2022, 8:52 AM
phisiart added inline comments.Sep 3 2022, 1:25 AM
mlir/include/mlir/Analysis/DataFlow/ConstantPropagationAnalysis.h
95

I feel like we cannot remove the dialect field here.

Looking at https://github.com/llvm/llvm-project/blob/67d0d7ac0acb0665d6a09f61278fbcf51f0114c2/mlir/lib/Transforms/SCCP.cpp#L54:

Value constant = folder.getOrCreateConstant(builder, dialect,
                                            latticeValue.getConstantValue(),
                                            value.getType(), value.getLoc());

SCCP uses the stored dialect to materializeConstant.

I tried to create a patch that removes dialect from ConstantPropagationAnalysis.h and re-computes the dialect in SCCP by looking at the getDefiningOp() of the current Value to be folded.

However, we cannot do this when the current Value is a block argument. Hence, this test case failed:

// CHECK-LABEL: func @simple_control_flow
func.func @simple_control_flow(%arg0 : i32) -> i32 {
  // CHECK: %[[CST:.*]] = arith.constant 1 : i32

  %cond = arith.constant true
  %1 = arith.constant 1 : i32
  cf.cond_br %cond, ^bb1, ^bb2(%arg0 : i32)

^bb1:
  cf.br ^bb2(%1 : i32)

^bb2(%arg : i32):
  // CHECK: ^bb2(%{{.*}}: i32):
  // CHECK: return %[[CST]] : i32

  return %arg : i32
}

In this test case, ConstantPropagationAnalysis is able to figure out that %arg is a constant, but we also need to know that the dialect is arith so that we can materializeConstant. However, the fact that the dialect is arith can only be propagated through the dataflow from the definition %1.

(Note: I created https://reviews.llvm.org/D133250 to demonstrate how I removed dialect.)

Therefore, I think that we still need to store dialect. Do you have another way of handling this?

The dialect can either be metadata unrelated to the constant, like how it was before. Or you can do what integer range analysis does and materialize a constant block argument using the dialect of the parent op. I think that's the better approach anyways.

The dialect can either be metadata unrelated to the constant, like how it was before. Or you can do what integer range analysis does and materialize a constant block argument using the dialect of the parent op. I think that's the better approach anyways.

How does that work though? The func dialect won't be able to materialize an arith constant (or really any other constant). This also won't work for propagating constants through calls, given that the dialect of the call generally won't be able to materialize the constant either.

Ugh that's true. Integer range inference (the test pass) is broken then. At least I wouldn't have the Impl struct and just have Optional<Attribute> with a Dialect * hanging around as metadata

phisiart added a comment.EditedSep 3 2022, 1:23 PM

Ugh that's true. Integer range inference (the test pass) is broken then. At least I wouldn't have the Impl struct and just have Optional<Attribute> with a Dialect * hanging around as metadata

I think that dialect is part of the state itself, instead of additional metadata.

  1. dialect is only valid when the state is initialized. In other words, if we define ConstantValue as { Optional<Attribute> value; Dialect *dialect; }, then dialect is only valid when value is not None. So we might as well put them together under a single Optional.
  1. dialect participates in the == comparison and join. Consider two ConstantValues with the same value but different dialects, they are still not equal (and thus joining them would still result in UnknownConstant()) because we don't know which dialect to use when materializing the attribute into an op. (Note that the current patch is incorrect - it doesn't compare the dialect.)

How about we change ConstantValue into { bool isInitialized; Attribute value; Dialect *dialect; }?

phisiart retitled this revision from Remove Lattice::isUninitialized(). to [mlir][dataflow] Remove Lattice::isUninitialized()..Sep 3 2022, 1:30 PM

Created https://reviews.llvm.org/D133260 for letting dialect participate in equality comparison. Will rebase this patch on top of that one.

Mogball added a comment.EditedSep 3 2022, 1:40 PM

I don't necessarily agree that the dialect is part of the state. It doesn't make sense that a constant shouldn't be propagated even though it has a known value because the dialect of their source operations differ. Most dialects don't have their own constant operations and will end up sharing the same op in their constant materializer (e.g. arith.constant).

It doesn't make sense to me that the fold result of a math.absi should differ from that of an arith.addi if their attributes are the same but their dialects are different (both dialects use arith.constant).

Otherwise, you might end up in situation where sccp isn't idempotent because the first iteration bottoms out with unequal dialects, which both end up getting materialized as arith.constant, and then another iteration properly propagates the constants into another block, for example

It doesn't make sense to me that the fold result of a math.absi should differ from that of an arith.addi if their attributes are the same but their dialects are different (both dialects use arith.constant).

Oh I see, I had a misunderstanding previously.

  • Previously I thought that if the input to math.absi is { constant = -1; dialect = arith; }, then the output is { constant = 1; dialect = arith; }. But actually it is { constant = 1; dialect = math; }.
  • Previously I thought that if the input to math.absi is { constant = -1; dialect = my_own_dialect; }, then the output should be { constant = 1; dialect = my_own_dialect; }. But actually it is { constant = 1; dialect = math; }.
  • Previously I thought that if the inputs to arith.addi are { constant = 1; dialect = my_own_dialect; } and { constant = 2; dialect = my_own_dialect; }, then the output is { constant = 3; dialect = my_own_dialect; }. But actually it is { constant = 3; dialect = arith; }.

Now it makes sense. Let me drop https://reviews.llvm.org/D133260 and change this patch then.

phisiart updated this revision to Diff 457842.Sep 3 2022, 11:31 PM

Update the definition of ConstantValue into { Optional<Attribute> constant; Dialect *dialect; }.

phisiart marked an inline comment as done.Sep 4 2022, 12:39 AM
Mogball accepted this revision.Sep 5 2022, 12:13 PM

One last comment and LGTM

mlir/include/mlir/Analysis/DataFlow/ConstantPropagationAnalysis.h
87

Can you default initialize this to nullptr so it doesn't have some garbage value?

This revision is now accepted and ready to land.Sep 5 2022, 12:13 PM

Thanks for all the improvements

phisiart updated this revision to Diff 458093.Sep 5 2022, 9:43 PM

Initialize ConstantValue::dialect with nullptr.

phisiart marked an inline comment as done.Sep 5 2022, 9:44 PM
This revision was automatically updated to reflect the committed changes.