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

[Ziqiang Patrick Huang]

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>