Page MenuHomePhabricator

[llvm][CodeGen] Add a default implementation to check whether two memory accesses are trivially disjoint
Needs ReviewPublic

Authored by csstormq on Jun 6 2022, 3:17 AM.

Details

Reviewers
efriedma
Summary

Add a target independent method using machine memory operands to check whether two instructions can alias. And as a default implementation to TargetInstrInfo::areMemAccessesTriviallyDisjoint function. It's useful for targets whose memory accesses are known at compile time.

Diff Detail

Event Timeline

csstormq created this revision.Jun 6 2022, 3:17 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 6 2022, 3:17 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
csstormq requested review of this revision.Jun 6 2022, 3:17 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 6 2022, 3:17 AM

Most of the existing target-independent code related to memoperand aliasing is in MachineInstr::mayAlias (specifically the MemOperandsHaveAlias helper). Is there some reason you can't just extend that?

csstormq added a comment.EditedJun 6 2022, 7:28 PM

Most of the existing target-independent code related to memoperand aliasing is in MachineInstr::mayAlias (specifically the MemOperandsHaveAlias helper). Is there some reason you can't just extend that?

In our case, we want to do the following two things.

First, in the overloaded SelectionDAGISel::PostprocessISelDAG, we want to break unnecessary chain dependencies between load and store instructions, represented as MachineSDNode, for having a positive affect on pre-RA scheduler.

I am not sure whether it's suit to construct temporary variables of MachineInstr here just for enabling to invoke MachineInstr::mayAlias. So I provide an individual function, called areMemAccessesTriviallyDisjoint, to finish the same work. This function does not care whether both instructions are MachineInstr or not. That's why the parameters of it are machine memory operands.

Second, because the result of pre-RA scheduler whichever we choose is not exactly what we expected, we write a machine pass to adjust slightly the sequence between load and store instructions, represented as MachineInstr. Here, it is natural to invoke MachineInstr::mayAlias. To finish our work, I add a default implementation for TargetInstrInfo::areMemAccessesTriviallyDisjoint as the code shown. So the users of invoking MachineInstr::mayAlias will benefit from it by default.

That's all.

You might want to look at TargetSubtargetInfo::useAA() and TargetSubtargetInfo::enableMachineScheduler(); might be helpful for your target, depending on what you're doing. (Actually, maybe we should consider just turning these on by default for all targets, given the number of targets overriding them.)

If you want to refactor out the relevant bits of MachineInstr::mayAlias into a helper, then enhance it, that would be fine, I guess. It's just weird to have two separate codepaths for checking MachineMemOperands.

csstormq updated this revision to Diff 435043.Jun 7 2022, 9:17 PM

You might want to look at TargetSubtargetInfo::useAA() and TargetSubtargetInfo::enableMachineScheduler(); might be helpful for your target, depending on what you're doing. (Actually, maybe we should consider just turning these on by default for all targets, given the number of targets overriding them.)

I have tried TargetSubtargetInfo::useAA for my target, but it is not helpful for my case.
I will try TargetSubtargetInfo::enableMachineScheduler() later. Thank you for your advice!

If you want to refactor out the relevant bits of MachineInstr::mayAlias into a helper, then enhance it, that would be fine, I guess. It's just weird to have two separate codepaths for checking MachineMemOperands.

I agree with your idea. I have submitted a new patch. Please review it again. At last, whether the title and summary need re edit to accord with the latest patch.

efriedma added inline comments.Jun 9 2022, 6:50 PM
llvm/lib/CodeGen/MachineInstr.cpp
1242

Address spaces are, in general, allowed to overlap. I think there might be a target hook to check if two address spaces are disjoint.

1274

Do we care if all the bits are actually address-significant? For example, on AArch64, there's a setting to tell the processor to ignore the top 16 bits of a pointer.

I guess there are other places we do aliasing checks based on the pointer bits, so maybe this isn't a practical issue.

1345

Do we reach this call isNoAlias() for two different intoptr constants? Does it not handle the case you're trying to deal with?

csstormq added inline comments.Jun 10 2022, 5:54 AM
llvm/lib/CodeGen/MachineInstr.cpp
1242

It makes sense.

1274

I didn't take this into account. Maybe it's better to provide a target hook here.

At present, I don't find that some places, especially the users of MachineInstr::mayAlias, have done similar thing as me. So it will be helpful for some targets like ours, I guess.

1345

I migrate our backend to the latest main branch. And I tried again. I truly reach this call isNoAlias() for two different intoptr constants using gdb step by step, but it still returns false wrongly.

csstormq updated this revision to Diff 435885.Jun 10 2022, 5:57 AM

Addressing code review comments.

efriedma added inline comments.Jun 14 2022, 3:08 PM
llvm/lib/CodeGen/MachineInstr.cpp
1345

Maybe worth looking into modifying BasicAAResult::aliasCheck to make this work? That would also benefit IR-level optimizations.

2482

Instead of repeating the loop from MachineInstr::mayAlias, can we make MemOperandsHaveAlias call areMemOperandsTriviallyDisjoint?

csstormq added inline comments.Jun 14 2022, 11:52 PM
llvm/lib/CodeGen/MachineInstr.cpp
1345

I'm afraid not. In my view, when we reach BasicAAResult::aliasCheck, we can't determine the starting address for memory access because the offset from the base address has lost.

2482

Yes, I will do that as your advice in the next patch.

csstormq updated this revision to Diff 437052.Jun 14 2022, 11:53 PM

Eliminate the duplicate loop over memory operands.

efriedma added inline comments.Jun 16 2022, 12:36 PM
llvm/include/llvm/CodeGen/MachineInstr.h
1842 ↗(On Diff #437052)

Please don't add "virtual" methods to MachineInstr; it doesn't have any derived classes.

If you need some target-specific info, look at TargetLoweringInfo.

1856 ↗(On Diff #437052)

Does areMemAccessesTriviallyDisjoint really need to be in the header?

"Align" is just an integer; don't pass it by const reference.

llvm/lib/CodeGen/MachineInstr.cpp
2418

Probably want to check that the operand of the IntToPtr isn't wider than the pointer type.

Also, getZExtValue() will assert on targets that support pointer widths greater than 64.

2433
2443

I think this is missing a check for whether the address-spaces are different?

csstormq added inline comments.Jun 17 2022, 4:25 AM
llvm/include/llvm/CodeGen/MachineInstr.h
1842 ↗(On Diff #437052)

I moved these virtual functions into TargetMachine. Is this OK?

1856 ↗(On Diff #437052)

As the LLVM document says, the semantics of non-zero address spaces are target-specific. Thus the intent of areMemAccessesTriviallyDisjoint as virtual function is enable to cope with the odd behavior of some targets, although this funciton provides a default implementation for most cases.

llvm/lib/CodeGen/MachineInstr.cpp
2418

Excuse me, is there any problem if I don't check that?

I address the problem of getZExtValue soon.

csstormq updated this revision to Diff 437848.EditedJun 17 2022, 4:39 AM
  1. move virtual functions into TargetMachine
  2. avoid getZExtValue() assert issue
  3. don’t “almost always” use auto
  4. pass "Align" by unsigned integer
  5. invoke mayAddressSpacesOverlap iff the address-spaces are different
  6. check whether two memory accesses are disjoint iff the address-spaces are same