This is an archive of the discontinued LLVM Phabricator instance.

[fir] Add array value copy pass
ClosedPublic

Authored by clementval on Oct 7 2021, 12:06 PM.

Details

Summary

This patch upstream the array value copy pass.

Transform the set of array value primitives to a memory-based array
representation.

The Ops array_load, array_store, array_fetch, and array_update are
used to manage abstract aggregate array values. A simple analysis is done
to determine if there are potential dependences between these operations.
If not, these array operations can be lowered to work directly on the memory
representation. If there is a potential conflict, a temporary is created
along with appropriate copy-in/copy-out operations. Here, a more refined
analysis might be deployed, such as using the affine framework.

This pass is required before code gen to the LLVM IR dialect.

This patch is part of the upstreaming effort from fir-dev branch. The
pass is bringing quite a lot of file with it.

Co-authored-by: Jean Perier <jperier@nvidia.com>
Co-authored-by: Eric Schweitz <eschweitz@nvidia.com>
Co-authored-by: V Donaldson <vdonaldson@nvidia.com>

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
mehdi_amini added inline comments.Oct 26 2021, 9:37 PM
flang/lib/Optimizer/Transforms/ArrayValueCopy.cpp
552

This condition does not seem tested

583

This case seems untested.

597

I can delete the 4 lines above (the if and its body) and the test still passes

617

This condition doesn't seem tested

618

This condition doesn't seem tested.

635

Actually this entire method isn't covered by the test

661

The reverse can be deleted here and the test still pass.

I took a few minutes to evaluate more precisely the level of testing, see inline: we're very far from covering our bases here (and this is far from exhaustive!).

I would suggest going back to first principles in terms of testing and building some solid and minimal tests for the passes you're trying to upstream.
I know you're not necessarily the author of the passes, and I suggest to involve the author(s) of the code ahead of time to improve the testing before attempting to upstream all of this.

I agree with you that this test does not cover 100% of the pass. We have more extensive tests but they cannot be upstream right now since they are using another tool not upstreamed yet. This is the problem with upstreaming small chunk. Of course I'm trying to add tests where I can but this one can have some more. I'll rework on this patch and add more fir to fir tests.

We have more extensive tests but they cannot be upstream right now since they are using another tool not upstreamed yet. This is the problem with upstreaming small chunk.

I'm not really sure what "other tool" is supposed to provide the basic coverage for testing a pass? In general it is "IR in, IR out" just like the test here.

I'm wary by the view that the issue is with the "small chunk" while on the contrary, the "small chunk" is working exactly as intended here: it points as fairly important testing issues for example.

clementval marked 8 inline comments as done.

Add more extensive tests in flang/test/Fir/array-value-copy.fir

flang/test/Fir/array-modify.fir has been merged with the new
test file.

Remove some code in the pass that cannot be tested now with
the current upstreaming state.

clementval marked an inline comment as done.Oct 28 2021, 3:25 AM

The latest update to this patch add a new flang/test/Fir/array-value-copy.fir file that cover the array-value-copy in more details.

flang/lib/Optimizer/Transforms/ArrayValueCopy.cpp
552

Test added in flang/test/Fir/array-value-copy.fir cover this part as well.

583

Test added in flang/test/Fir/array-value-copy.fir cover this code.

597

The test added in flang/test/Fir/array-value-copy.fir that uses array of derived types is covering this part of the code.

617

This will require fir.array_acccess/fir.array_amend to be tested correctly with character arrays. Remove it from this upstreaming patch for now.

618

This will require fir.array_acccess/fir.array_amend to be tested correctly with character arrays. Remove it from this upstreaming patch for now.

635

This will require fir.array_acccess/fir.array_amend to be tested correctly with character arrays. Remove it from this upstreaming patch for now.

661

The test with multidimensional array added in flang/test/Fir/array-value-copy.fir make sure the reverse indices is tested correctly.

833

This cannot be tested currently with what is upstreamed. Remove it for the moment.

860

Test covering fir.array_update conversion have been added in flang/test/Fir/array-value-copy.fir.

clementval marked an inline comment as done.Nov 1 2021, 2:45 AM

@mehdi_amini Can we move on with this one now that we have better test coverage?

Testing is better now, thanks!
I haven't seen a follow up on https://reviews.llvm.org/D111288#inline-1071935 ; but this is a recurring issue that affects this revision as well.

Testing is better now, thanks!
I haven't seen a follow up on https://reviews.llvm.org/D111288#inline-1071935 ; but this is a recurring issue that affects this revision as well.

I replied on D111288 about the next steps for auto. I'll update this patch where it makes sense.

clementval updated this revision to Diff 384000.Nov 2 2021, 1:50 AM

Replace some auto occurences + rebase

clementval marked an inline comment as done.Nov 2 2021, 1:55 AM

Testing is better now, thanks!
I haven't seen a follow up on https://reviews.llvm.org/D111288#inline-1071935 ; but this is a recurring issue that affects this revision as well.

@mehdi_amini I have updated this patch and removed some auto occurrences. As mentioned we will post soon a small guideline for Flang doc that precise that we are using the MLIR style in folder related to MLIR (Optimizer, Lower) and precise how we use auto. Don't worry it is not a "use auto everywhere" but rather a clarification of the LLVM guidelines that is somewhat open. I have looked through the MLIR codebase and I think we are pretty much on par with the use of auto.
I hope we can move forward with this patch now.

Thanks for the update, the size makes it tractable now, and the test helps to figure out the corner cases when the code isn't straightforward.

I mostly looked at ArrayCopyAnalysis here.

One thing that can be problematic for future patches: the control flow in general should be handled with the ControlFlowInterface which may not be yet implemented on the relevant FIR ops. But that had a significant impact on the code inside the passes, so likely something to consider prioritizing downstream.

flang/include/flang/Optimizer/Builder/FIRBuilder.h
403

Is there a use for this method? (same for the other above)

417

No definition added for this declaration?

467

Is this method used somewhere? (Same for the two above)

flang/include/flang/Optimizer/Transforms/Factory.h
146

Do you know why this is returning a vector instead of an OperandRange? (this is a question for the ShapeOp definition).

It seems strange to force copy on all the accessors when they may just want to iterate on the Values...

flang/include/flang/Optimizer/Transforms/Passes.td
95

Can you just let me know what fails if you remove any of these?

flang/lib/Optimizer/Builder/FIRBuilder.cpp
289

Why the commented out code? Can it just be removed?

363–459

Is this method used?

flang/lib/Optimizer/Transforms/ArrayValueCopy.cpp
90

I don't understand this comment (I read it 4 times though).

Edit: the comment on the implementation is actually much more clear:

/// Find all the array operations that access the array value that is loaded by
/// the array load operation, `load`.
109

A comment around the constructor (or the member variable definition) would be helpful to say:

If provided, the `loopRegion` is the body of a loop that produces the array of interest.

(or something like that)

117
121

I am very concerned about a recursive algorithm on def-use chain: this is a ticking bomb for a stack overflow in the compiler.
Can you make this an iterative algorithm with an explicit stack?

147

(here and elsewhere)

156

Of all the if above, only the DoLoopOp seems tested. There are some specific cases for the treatment of EmboxOp and ArrayMergeStoreOp that likely should be covered

230

This is the only method actually accessed outside of the class, can you make sure it is the only one in the public section?

Everything else could be private (constructor included)

235

Should this also support other kind of loops? (if so add a TODO)

251

Isn't this whole function isAncestor?

return loopRegion->isAncestor(op->getParentRegion());

Edit: actually, loopRegion may be null here but it isn't obvious from the class invariant. So instead:

return loopRegion && loopRegion->isAncestor(op->getParentRegion());

260
261

Same recursion issue here.

278
279
290
303
304
305

I don't understand how this can happen: an OpOperand does not have a lifetime outside of its owner operation IIRC

309

Make the type explicit (you're doing arithmetic arg - 1 on the next line, I shouldn't have to think about the impact of signedness here)

310

The finalValue() check here is also another case not covered in the test.

finalValue isn't documented in ODS and initArgs isn't documented either, it'd be great if this could be addressed (separately from this revision of course)

310
315
316–320

This loop isn't great when you already have everything to compute offsets.

In general all the special casing for the Loop, branches, and the control flow in general should be handled with the ControlFlowInterface: https://github.com/llvm/llvm-project/blob/main/mlir/include/mlir/Interfaces/ControlFlowInterfaces.td

This would make the code entirely uniform, and any new op that has to do with the control flow would not require to modify the pass.

I'm fine if you want to handle this later for this pass (please add a big // TODO: this need to be updated to use the control-flow interface), but I'm not sure we should upstream many other passes that would be implemented without going through interfaces.

329–330
361

Seems like we're storing much more than what we need actually, I tried locally to change loadMapSets to store the SmallVector of "accesses" and it is just enough (and it makes subsequent call even easier).

Here is a patch: https://gist.github.com/joker-eph/8f00e79783688bf6349b6b5d9d44a480

372

This is a complex body, worth using braces here

373

In general, early continue reduces indentation:

374–376

If this is a pattern that repeats, it'll be worth having a helper (potentially a method on ArrayLoadOp : Type getUnboxedLoadedType() or something like that)

390

This would be worth a comment I think

417

Seems like this should be an assert

419–422

SmallVector has an operator==, is this different?

439–443

Isn't this entire loop nest + recursion just a walk?

Also, I'd change the signature of the construct method to be:
void ArrayCopyAnalysis::construct(Operation *topLevelOp) {

So that you can just write topLevelOp->walk([&] (Operation *op) {

(the only reason for the current signature was the recursion as far as I can tell)

440
445

It may be worth moving all the temporary storage outside of the walk, and then just calling .clear() before using them here (which is already done inside arrayAccesses() by the way, even though it is for nothing right now). That way they would "grow" only once and the memory can be reused over and over.

449

Where is the guarantee that this cast will always succeed coming from?
The doc for ArrayMergeStoreOp does not mention anything, and there is no verifier for ArrayMergeStoreOp

469

Can this check fail? Right now the contract of arrayAccesses() is to only return these three operations, and conflictOnMerge would fail if there were any other op.
Can this be replace with an assert here?

470

Same (I think) but with a single map lookup if (!useMap.insert({acc, &op}).second) {

475

Seems like this should signal an error? Is this conservative to just "continue" here?

660

In general, use llvm::function_ref instead of std::function when you don't take ownership (this avoid potential heap allocation and copies)

663

Alternatively: auto loadOp = mlir::cast<ArrayLoadOp>(useMap.lookup(op)); and use loadOp everywhere instead of having load and loadOp

674
681
700
795
824

(typo)

clementval marked 51 inline comments as done.Nov 22 2021, 1:05 PM

Thanks for the update, the size makes it tractable now, and the test helps to figure out the corner cases when the code isn't straightforward.

I mostly looked at ArrayCopyAnalysis here.

One thing that can be problematic for future patches: the control flow in general should be handled with the ControlFlowInterface which may not be yet implemented on the relevant FIR ops. But that had a significant impact on the code inside the passes, so likely something to consider prioritizing downstream.

Tried to address most of the comments. I think we will need couple of follow up patches to make it easier to move foward (and sync back in between).

flang/include/flang/Optimizer/Builder/FIRBuilder.h
403

This one is not used currently (removed from this patch). The one above is.

417

Mistake of the rebase. It's the same as the one just above. Removed.

flang/include/flang/Optimizer/Transforms/Factory.h
146

I don't think there is a good reason for this. Will add a TODO so we can address this in a follow up patch since it touches the op definiton and probably other places in the code.

flang/include/flang/Optimizer/Transforms/Passes.td
95

These were artifact from the time it didn't work without it. Looks like it is now fine to remove them.

flang/lib/Optimizer/Builder/FIRBuilder.cpp
289

Yeah will be added later anyway.

flang/lib/Optimizer/Transforms/ArrayValueCopy.cpp
90

Updated.

121

Would it be ok to address this in a follow up patch? I just added a todo right now.

316–320

I think it is better to handle this later (switch to control flow interface) as it will bring lots of changes with it.

361

Thanks for the patch. look like it does the trick.

439–443

Thanks for the inputs here. Replace by a simple walk.

449

ArrayMergeStoreOp verifier has this:

if (!isa<ArrayLoadOp>(op.original().getDefiningOp()))
    return op.emitOpError("operand #0 must be result of a fir.array_load op");
824

Thanks.

clementval added inline comments.Nov 22 2021, 1:05 PM
flang/lib/Optimizer/Transforms/ArrayValueCopy.cpp
156

Added some test and removed the IterWhileOp and EmboxOp special case since they will be added later when we can add better test coverage.

235

From a practical point of view, array operations are normally generated with DoLoopOp so there is no real code that need the other loops. From a purely FIR point of view, of course someone could write some IterWhileOp with array operations but we do not have use cases in mind for that.
I added a comment to make precise this in the code.

261

Same here. Would be great if we can address that in a follow up patch directly after finishing this one.

310

They are loops with finalValue and iterArgs in the tests. Will add the documentation in another path. Added on my todo list.

I think you haven't updated the revision yet.

flang/lib/Optimizer/Transforms/ArrayValueCopy.cpp
121

How to we track that this get addressed though? I'm wary of TODO that will stay here for a while.
Is someone gonna commit to work on this ASAP?

clementval marked 14 inline comments as done.

Address various review comments + rebase

I think you haven't updated the revision yet.

Sorry, it was stuck on the arc lint phase :(

flang/lib/Optimizer/Transforms/ArrayValueCopy.cpp
121

I can work on that in the next 2-3 weeks probably.

Looks fine overall, thanks!

There are still a few minor issues: dead code in particular, but also the code documentation is a bit on the light side for something that really does not seem trivial to me.
(+ some inline comments)

flang/include/flang/Optimizer/Builder/FIRBuilder.h
66

Seems unused in this patch?

355

Unused in this patch?

448

This is unused in this patch?

459

Same

468

Unused as well (and undocumented)

flang/include/flang/Optimizer/Builder/Runtime/RTBuilder.h
360

Can you document all this macro system?
Does it need to in header? In general macros defined in header is "dangerous", should these be prefixed with Fir or something?

364

You could add this in the function body if this is really needed, or what do I misse?

flang/include/flang/Optimizer/Transforms/Factory.h
45

This method isn't used anywhere either

148

I don't see a call-site for this either

191–193

Move this assert with the one a few lines above? They seem related.
Using the assert(!shapeVal || form like above you can avoid the if and the nesting

254

The createLoopNest functions seem unused as well

flang/lib/Optimizer/Builder/FIRBuilder.cpp
365
371

Seems like there should be a llvm_unreachable after this error is emitted

373

I don't quite find what the .match( call resolves to on the fir::ExtendedValue class? Any tip?

375

(same below)

400

Can you comment on what this is supposed to match?

flang/lib/Optimizer/Transforms/ArrayValueCopy.cpp
356

not sure if it is a Value here?

454–463

I commented on this before I believe: you have two map lookup when one would be enough I think:

469

You marked it done, but I don't see it done in the code.

645
672

(previous use of useMap.lookup() in this function spelled out the type)

717

This branch may be worth a comment.

In general the entire pattern is a bit light on documentation.

731

You can reduce the indentation in the code by inverting the else and the then branch:

if (!inEleTy.isa<fir::RecordType>())
   llvm::report_fatal_error("not a legal reference type");

Also, I'm not sure why it isn't an assertion here? If this can't be then shouldn't we degrade more gracefully?

assert(inEleTy.isa<fir::RecordType>());
flang/lib/Optimizer/Transforms/ArrayValueCopy.cpp
121

I have created an issue to capture this in the upstreaming FIR Passes board.
https://github.com/flang-compiler/f18-llvm-project/projects/7
https://github.com/flang-compiler/f18-llvm-project/issues/1268

@clementval if this is just about converting to an iterative version then we can help.

clementval marked 23 inline comments as done.

Address review comments

flang/lib/Optimizer/Builder/FIRBuilder.cpp
373
flang/lib/Optimizer/Transforms/ArrayValueCopy.cpp
121

Yeah this is it. With all the changes (compare to fir-dev) in this patch it would be nice to be able to make a sync before this kind of refactoring.

454–463

Yeah sorry I thought I made the update. Must have been lost in an other branch.

645

Sorry missed this update as well. It's updated.

717

ArrayUpdateOp is actually not supported for reference type anymore since there is a new op for it. This code is removed.

731

Replaced with an assert and remove the if-else

@kiranchandramohan do you plan on reviewing/approving the current version of the patch?

I don't have any more comment than before, there are just a few that are still pending.

flang/include/flang/Optimizer/Builder/FIRBuilder.h
448

Missed this one?

flang/include/flang/Optimizer/Builder/Runtime/RTBuilder.h
360

Marked done, but I don't see a change here?

flang/lib/Optimizer/Builder/FIRBuilder.cpp
30

This is marked done, but you actually extracted it as-is and landed it in https://reviews.llvm.org/D112057 ; can you address that as well (in a separate patch, but I'm wary of losing track of this).

46

Same here: you marked it done without commenting and landed it separately.

373

Thanks!

Something really confusing is that there is another class with the same name, and located in a header with the same filename!
(in include/flang/Lower/Support/BoxValue.h)

flang/lib/Optimizer/Transforms/ArrayValueCopy.cpp
469

Yet again
(line 452 by now)

clementval marked 3 inline comments as done.

Address missed comments

clementval added inline comments.Nov 26 2021, 4:16 AM
flang/include/flang/Optimizer/Builder/FIRBuilder.h
448

My bad. I thought I removed it.

flang/include/flang/Optimizer/Builder/Runtime/RTBuilder.h
360

No idea why it was mark done since I don't even remember reading this one. I have added some comments and prefixed the macros. I kept mkRTKey without prefix since it is used outside.

flang/lib/Optimizer/Builder/FIRBuilder.cpp
30

Sorry, I marked it as done here to be able to navigate more easily in the comments since it was not part of this part anymore. I'll look at it in another patch.

46

Is this really important? If so I'll update it.

flang/lib/Optimizer/Transforms/ArrayValueCopy.cpp
469

My bad. I'm sure I made the change but I probably mixed up my branches and it was not in this update. Updated now.

clementval marked an inline comment as done.Nov 26 2021, 4:17 AM
clementval added inline comments.
flang/lib/Optimizer/Builder/FIRBuilder.cpp
30

@kiranchandramohan do you plan on reviewing/approving the current version of the patch?

I don't have any more comment than before, there are just a few that are still pending.

The patch LGTM. Thanks for going through the patch in detail and pointing out various issues. And thanks to @clementval for addressing most of the issues. I agree that the remaining issues can be dealt with later. I have created a few github issues to follow up on later work.

Nit: The changes in the following files are in other patches or have been merged. How are you planning to handle this?
flang/lib/Optimizer/Dialect/FIRType.cpp
flang/include/flang/Optimizer/Builder/Runtime/RTBuilder.h
flang/include/flang/Optimizer/Builder/Runtime/Assign.h
flang/lib/Optimizer/Builder/Runtime/Assign.cpp

flang/lib/Optimizer/Builder/FIRBuilder.cpp
30
46

Might be easier to read for newcomers.

373

I think there is some refactoring going on, where code in Lower is moved to the Optimizer/Builder directory. I think once all the code is moved the code in Lower can be deleted.

flang/lib/Optimizer/Transforms/ArrayValueCopy.cpp
121

OK. I have moved this to the post-upstream board.

310
316–320
clementval marked an inline comment as done.Nov 29 2021, 4:51 AM

@kiranchandramohan do you plan on reviewing/approving the current version of the patch?

I don't have any more comment than before, there are just a few that are still pending.

The patch LGTM. Thanks for going through the patch in detail and pointing out various issues. And thanks to @clementval for addressing most of the issues. I agree that the remaining issues can be dealt with later. I have created a few github issues to follow up on later work.

Nit: The changes in the following files are in other patches or have been merged. How are you planning to handle this?
flang/lib/Optimizer/Dialect/FIRType.cpp
flang/include/flang/Optimizer/Builder/Runtime/RTBuilder.h
flang/include/flang/Optimizer/Builder/Runtime/Assign.h
flang/lib/Optimizer/Builder/Runtime/Assign.cpp

@kiranchandramohan I'm just gonna rebase on main since some of the patch have landed and I'll merge in the change requested from this review.

@kiranchandramohan I just did a rebase. Let me know if it is still ok for you.

mehdi_amini added inline comments.Nov 29 2021, 11:42 AM
flang/include/flang/Optimizer/Builder/FIRBuilder.h
25

Can you double check that these are needed in this header? It's not clear from the change in this file

Remove extra headers

clementval marked an inline comment as done.Nov 30 2021, 1:23 AM
clementval added inline comments.
flang/include/flang/Optimizer/Builder/FIRBuilder.h
25

Removed

LGTM.

flang/lib/Optimizer/Builder/FIRBuilder.cpp
118

Nit: Is this change necessary?

clementval marked an inline comment as done.

Revert useless change

This revision was landed with ongoing or failed builds.Nov 30 2021, 4:51 AM
This revision was automatically updated to reflect the committed changes.