MIScheduler + AA: Missed scheduling opportunity in MIsNeedChainEdge. Bug?

Hello,

While tuning the MIScheduler for my target, I discovered a code that unnecessarily restricts the scheduler. I think this is a bug, but I would appreciate a second opinion.

In file ScheduleDAGInstrs.cpp, the function MIsNeedChainEdge determines whether two MachineInstrs are ordered by a memory dependence. It first runs through the standard criteria (Do both instructions access memory? Does at least one store to memory? Is either access volatile? etc.), and finally queries AliasAnalysis if available.

Before reaching alias analysis, however, function isUnsafeMemoryObject pessimizes the result. In particular, isUnsafeMemoryObject returns true unless all of the pointer's underlying objects satisfy IsIdentifiedObject. This forces MIsNeedChainEdge to conservatively report true, even though AliasAnalysis could give a more precise answer in some situations. Further, it is unclear why this test even exists: it does not attempt to compare the underlying object sets to test for an alias, and the volatility check should cover all this-object-is-not-quite-memory situations.

As a simple example of why this matters, suppose that you have a function like this:
  void doit(int *baseptr) {
    baseptr[0] = 1; // store 1
    baseptr[1] = 2; // store 2
  }

In this example, stores 1 and 2 can be freely re-ordered. However, isUnsafeMemoryObject reports true because the underlying objects (formal parameter 'baseptr') do not satisfy IsIdentifiedObject. Nonetheless, BasicAliasAnalysis can show that derived pointers &baseptr[0] and &baseptr[1] are disjoint.

Proposed solution:
- If MIsNeedChainEdge is invoked without alias analysis (AA=nullptr), behavior should be unchanged.
- Otherwise, isUnsafeMemoryObject should not test for identified objects.
- A minimal patch appears at the end of this email.

Thanks,
Nick Johnson
D. E. Shaw Research

diff --git a/lib/CodeGen/ScheduleDAGInstrs.cpp b/lib/CodeGen/ScheduleDAGInstrs.cpp
index 390b6d2..fcf43ca 100644
--- a/lib/CodeGen/ScheduleDAGInstrs.cpp
+++ b/lib/CodeGen/ScheduleDAGInstrs.cpp
@@ -475,7 +475,8 @@ static inline bool isGlobalMemoryObject(AliasAnalysis *AA, MachineInstr *MI) {
// to deal with (i.e. volatile object).
static inline bool isUnsafeMemoryObject(MachineInstr *MI,
                                         const MachineFrameInfo *MFI,
- const DataLayout &DL) {
+ const DataLayout &DL,
+ AliasAnalysis *AA) {
   if (!MI || MI->memoperands_empty())
     return true;
   // We purposefully do no check for hasOneMemOperand() here
@@ -497,6 +498,7 @@ static inline bool isUnsafeMemoryObject(MachineInstr *MI,
   if (!V)
     return true;

+ if (!AA) {
     SmallVector<Value *, 4> Objs;
     getUnderlyingObjects(V, Objs, DL);
     for (Value *V : Objs) {
@@ -504,6 +506,7 @@ static inline bool isUnsafeMemoryObject(MachineInstr *MI,
       if (!isIdentifiedObject(V))
         return true;
     }
+ }

   return false;
}
@@ -533,7 +536,7 @@ static bool MIsNeedChainEdge(AliasAnalysis *AA, const MachineFrameInfo *MFI,
   if (!MIa->hasOneMemOperand() || !MIb->hasOneMemOperand())
     return true;

- if (isUnsafeMemoryObject(MIa, MFI, DL) || isUnsafeMemoryObject(MIb, MFI, DL))
+ if (isUnsafeMemoryObject(MIa, MFI, DL, AA) || isUnsafeMemoryObject(MIb, MFI, DL, AA))
     return true;

   // If we are dealing with two "normal" loads, we do not need an edge

I noticed this too and I’m not sure why isUnsafeMemoryObject returns true for such simple array access. But before reaching that check, you should hit

   // Let the target decide if memory accesses cannot possibly overlap.
00527   if ((MIa->[mayLoad](https://urldefense.proofpoint.com/v2/url?u=http-3A__llvm.org_docs_doxygen_html_classllvm-5F1-5F1MachineInstr.html-23a2b48451e9cc8433ed5f8ee30462cc96e&d=AwMFaQ&c=8hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=Qmh_U6A4Y7gzPc4Y8NSCF5_YztpM9EtWVAw3zyHhQT4&s=PmIifiWZh87AXlO5GhAoXOmrpkCj1E0WuwxFXNqqrE8&e=)() || MIa->[mayStore](https://urldefense.proofpoint.com/v2/url?u=http-3A__llvm.org_docs_doxygen_html_classllvm-5F1-5F1MachineInstr.html-23aa5f0eb2aad4a731d5d5133b8cb5e0a98&d=AwMFaQ&c=8hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=Qmh_U6A4Y7gzPc4Y8NSCF5_YztpM9EtWVAw3zyHhQT4&s=xUj8_-S0KyymhUi9f8a8tJqtEHZzY6CmGO6CdLgkTQ8&e=)()) &&
00528       (MIb->[mayLoad](https://urldefense.proofpoint.com/v2/url?u=http-3A__llvm.org_docs_doxygen_html_classllvm-5F1-5F1MachineInstr.html-23a2b48451e9cc8433ed5f8ee30462cc96e&d=AwMFaQ&c=8hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=Qmh_U6A4Y7gzPc4Y8NSCF5_YztpM9EtWVAw3zyHhQT4&s=PmIifiWZh87AXlO5GhAoXOmrpkCj1E0WuwxFXNqqrE8&e=)() || MIb->[mayStore](https://urldefense.proofpoint.com/v2/url?u=http-3A__llvm.org_docs_doxygen_html_classllvm-5F1-5F1MachineInstr.html-23aa5f0eb2aad4a731d5d5133b8cb5e0a98&d=AwMFaQ&c=8hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=Qmh_U6A4Y7gzPc4Y8NSCF5_YztpM9EtWVAw3zyHhQT4&s=xUj8_-S0KyymhUi9f8a8tJqtEHZzY6CmGO6CdLgkTQ8&e=)()))
00529     if (TII->[areMemAccessesTriviallyDisjoint](https://urldefense.proofpoint.com/v2/url?u=http-3A__llvm.org_docs_doxygen_html_classllvm-5F1-5F1TargetInstrInfo.html-23a255c4fa466c5f2ba7e52f67296834de8&d=AwMFaQ&c=8hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=Qmh_U6A4Y7gzPc4Y8NSCF5_YztpM9EtWVAw3zyHhQT4&s=hlB6rEI71Ch7WQ5iXdBZYsPcir4_xbXA0-uzkm7uoOs&e=)(MIa, MIb, AA))
00530       return false;

Here your target could override areMemAcdessesTriviallyDisjoint() function to make it work, at least for the example you gave.

Patrick

Thank you, Patrick, for your reply.

Here your target could override areMemAcdessesTriviallyDisjoint() function to make it work, at least for the example you gave.

If possible, I would prefer to use all of the algorithms already implemented in under the AliasAnalysis interface, rather than re-implement them in areMemAccessesTriviallyDisjoint.

The example demonstrates that the undesired behavior is reachable, but was not meant to exhaustively list all situations that trigger the problem.

Nick Johnson
D. E. Shaw Research

Hi Nick,

I believe you're right, but is the check ever necessary (even when not using AA)? The only logic in between the calls to isUnsafeMemoryObject and the conservative return value when AA is disabled, is this:

  if (!MIa->mayStore() && !MIb->mayStore())
    return false;

and I think that should be true regardless.

To comment on the motivation, I suspect that it has to do with the fact that the scheduling algorithm keeps track of 'pending' loads and stores in sets identified underlying object. If we can't get back to an 'identified' object, then the underlying object might alias with another one, and this scheme breaks down. Thus, getUnderlyingObjectsForInstr has this isIdentifiedObject check. It might be that it was simply copied into isUnsafeMemoryObject unnecessarily.

Also, as you're interested in this area, please test http://reviews.llvm.org/D8705 -- I hope we'll be able to transition to that implementation soon.

-Hal