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

[Johnson, Nicholas Paul]

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