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

[Hal Finkel]

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

----- Original Message -----
> From: "Nicholas Paul Johnson" <Nicholas.Paul.Johnson at DEShawResearch.com>
> To: llvmdev at cs.uiuc.edu
> Sent: Wednesday, July 1, 2015 2:08:02 PM
> Subject: [LLVMdev] 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
> 
> 
> 
> 
> 
> 
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 

-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory