This is an archive of the discontinued LLVM Phabricator instance.

Remove all MMOs from memory operations when tail merging.
ClosedPublic

Authored by apazos on Feb 19 2015, 1:55 PM.

Details

Summary

All,
When tail merging MBBs it's necessary to remove all MMOs from memory operations to ensures later passes conservatively compute dependencies.

A more robust solution would be to add multiple MMOs from the duplicate MIs to the new MI. Currently ScheduleDAGInstrs.cpp ignores all MMOs on instructions with multiple MMOs, so the attached patch is equivalent for the time being. If this patch is approved, I'll file a new PR suggesting the potential enhancement.

Just a few questions:

  1. Does the new clearMemRefs() API need to free any memory?
  2. I couldn't derive a simple test case. Does anyone have a suggestion?

Initial discussion here:
http://lists.cs.uiuc.edu/pipermail/llvmdev/2015-February/082525.html
http://lists.cs.uiuc.edu/pipermail/llvmdev/2015-February/082526.html

Diff Detail

Event Timeline

mcrosier updated this revision to Diff 20338.Feb 19 2015, 1:55 PM
mcrosier retitled this revision from to Remove all MMOs from memory operations when tail merging..
mcrosier updated this object.
mcrosier edited the test plan for this revision. (Show Details)
mcrosier added reviewers: hfinkel, ahatanak, qcolombet.
mcrosier added a subscriber: Unknown Object (MLST).
hfinkel edited edge metadata.Feb 19 2015, 4:16 PM

Does the new clearMemRefs() API need to free any memory?

No. The memory for memrefs is owned by the machine function (it is allocated by MF.allocateMemRefsArray()).

lib/CodeGen/BranchFolding.cpp
735

We can do better than this. Don't remove the MMOs if we're tail merging two instructions that have identical MMOs.

apazos added a subscriber: apazos.Feb 19 2015, 7:28 PM
apazos added inline comments.Feb 19 2015, 8:16 PM
lib/CodeGen/BranchFolding.cpp
735

Thanks for the suggestion Hal. Chad is OOO, I will uplload a new patch so we can continue the discussion.

apazos commandeered this revision.Feb 20 2015, 10:00 AM
apazos updated this revision to Diff 20418.
apazos added a reviewer: mcrosier.
apazos edited edge metadata.

Hal let me know if you think we need to check each field in the MMO, I am just checking for the gep instruction, and not going down the underlying objects nor the flags, AA metadatat fields etc.

hfinkel added inline comments.Feb 20 2015, 10:19 AM
lib/CodeGen/BranchFolding.cpp
745

Yes, please check all of the fields (they can have control dependencies). Also, You can just do V1 != V2, both being null is fine.

apazos updated this revision to Diff 20486.Feb 22 2015, 7:16 PM

Hi Hal,
I added all possible fields so we can agree on what we really need to check.
I think some of the fields we do need to check, like alignment, address space, flags.
Others like AAInfo, Ranges, I just checked the first entry, I did not go down the lists to check each metadata node. Probably we need to do that.
Let me know what you think.

Hi Hal,
I added all possible fields so we can agree on what we really need to check.
I think some of the fields we do need to check, like alignment, address space, flags.
Others like AAInfo, Ranges, I just checked the first entry, I did not go down the lists to check each metadata node. Probably we need to do that.
Let me know what you think.

What you're doing with the Metadata right now is correct; you're comparing the pointers to the metadata, and those should be unique by contents (you won't have two different metadata pointers that have the same contents).

hfinkel added inline comments.Feb 23 2015, 11:29 AM
lib/CodeGen/BranchFolding.cpp
752

I think function is good, except for this part. Comparing the value's underlying objects won't be sufficient if AA is being used (I think its probably fine otherwise, but I don't really want use-of-AA-dependent behavior here). I think we, realistically, have two options (which as I explained earlier, are more-or-less the same in effect currently):

  1. If V1 != V2, strip the MMOs.
  2. If V1 != V2, add multiple MMOs.

I think that doing (1) is fine for now, but I'd actually like to see us add multiple MMOs (option 2), and let the scheduler deal with that (which it does not currently).

apazos updated this revision to Diff 20913.Feb 27 2015, 4:50 PM

Hi Hal,

Yes, for now we can have the V1 != V2 solution to resolve the benchmark miscompares resulting from BranchFolding.

I have updated the patch with a few new fixes:
(1) I was potentially removing MMOs from all LD/ST instructions inside the common tail.
I should have been more conservative and remove MMOs from the corresponding LD/ST instructions between a block and the common tail.
(2) The "CommonTailLen" includes matching instructions between a block and the common tail, but it can also include additional debug instructions.
I have to discount these debug instructions.

hfinkel added inline comments.Mar 4 2015, 11:34 AM
lib/CodeGen/BranchFolding.cpp
740

Can you please add an == operator to the class; this logic needs to be maintained with the MMO class, and should not live here.

apazos updated this revision to Diff 21393.Mar 6 2015, 1:46 PM

I have added operator == and != to MachineMemOperrand.h.

mcrosier edited edge metadata.Mar 6 2015, 2:13 PM

In addition to adding the == and != operators to MachineMemOperrand.h, this patch set
address a few issues from the previous patch:

  1. When comparing MMO Values, both being null is considered identical, per Hal's review.
  1. When iterating over the MBB, only compare instructions in the common block against the equivalent instruction in the non-common block. Previously, we were comparing all instruction in the common block against all instructions in the non-common block which can remove MMOs that are not necessary.
  1. The "SameTails" can have CommonTailLen of different values relating to the same common block, and might have different number of matching instructions and some extra debug instructions that have to be discounted.

Ana, please feel free to add additional comments.

include/llvm/CodeGen/MachineMemOperand.h
204 ↗(On Diff #21393)

What about something like:
return LHS.getValue() == RHS.getValue() &&

LHS.getPseudoValue() == RHS.getPseudoValue() &&
LHS.getSize() != RHS.getSize() &&
LHS.getOffset() != RHS.getOffset() &&
...
...;
lib/CodeGen/BranchFolding.cpp
764

Directly use MBB->rend(), rather than MBBIE? This would remove the need for the void cast.

apazos updated this revision to Diff 21408.Mar 6 2015, 4:58 PM
apazos edited edge metadata.

Hi Chad, thanks for the suggestions. I incorporated what I agreed with.

The patch you commented on had only the operator change. But the previous patch to that one had the other changes you listed (refer o previous patch commit message):

(1) I was potentially removing MMOs from all LD/ST instructions inside the common tail.
I should have been more conservative and remove MMOs from the corresponding LD/ST instructions between a block and the common tail.
(2) The "CommonTailLen" includes matching instructions between a block and the common tail, but it can also include additional debug instructions.
I have to discount these debug instructions.

Thanks!

hfinkel added inline comments.Mar 7 2015, 8:10 PM
include/llvm/CodeGen/MachineMemOperand.h
203 ↗(On Diff #21408)

Line too long?

215 ↗(On Diff #21408)

Line too long?

lib/CodeGen/BranchFolding.cpp
737

I think this loop is just:

return std::equal(I1, E1, I2);
apazos updated this revision to Diff 21505.Mar 9 2015, 1:12 PM

Hi Hal,
I fixed the line format.
As for using std:equal, I do not think it works because it will compare *I1 != *I2 instead of I1 != I2 which we need to compare MemoryOperand references.

hfinkel accepted this revision.Mar 9 2015, 1:45 PM
hfinkel edited edge metadata.

LGTM. Make sure you mention in the commit message that no reduced test case is available.

As for using std:equal, I do not think it works because it will compare *I1 != *I2 instead of I1 != I2 which we need to compare MemoryOperand references.

Ah, yes, you're right (you could write a custom predicate, but that does not seem worthwhile).

This revision is now accepted and ready to land.Mar 9 2015, 1:45 PM
mcrosier closed this revision.Mar 10 2015, 9:26 AM

Committed in r231799.