llvm dev - Jul 2015 - [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

I noticed this too and I'm not sure why isUnsafeMemoryObject
<http://llvm.org/docs/doxygen/html/ScheduleDAGInstrs_8cpp.html#a25fe0578f0a0e48d63fcf4ab7a892dd5>
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
<http://llvm.org/docs/doxygen/html/classllvm_1_1MachineInstr.html#a2b48451e9cc8433ed5f8ee30462cc96e>()
|| MIa->mayStore
<http://llvm.org/docs/doxygen/html/classllvm_1_1MachineInstr.html#aa5f0eb2aad4a731d5d5133b8cb5e0a98>())
&&00528       (MIb->mayLoad
<http://llvm.org/docs/doxygen/html/classllvm_1_1MachineInstr.html#a2b48451e9cc8433ed5f8ee30462cc96e>()
|| MIb->mayStore
<http://llvm.org/docs/doxygen/html/classllvm_1_1MachineInstr.html#aa5f0eb2aad4a731d5d5133b8cb5e0a98>()))00529
    if (TII->areMemAccessesTriviallyDisjoint
<http://llvm.org/docs/doxygen/html/classllvm_1_1TargetInstrInfo.html#a255c4fa466c5f2ba7e52f67296834de8>(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

2015-07-01 15:08 GMT-04:00 Johnson, Nicholas Paul <
Nicholas.Paul.Johnson at deshawresearch.com>:
> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150701/b78b4293/attachment.html>

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

----- 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