[LLVMdev] ScheduleDAGInstrs.cpp

[Jonas Paulsson]

Hi,

Thank you for your reply. I have tried Tom Stellards patch, but it did not resolve my particular problem.

I have tried to expose this problem on public target without success. I am still however fearing that the scheduler is incorrect.

I have a (bit unoptimized) case where the LLVM I/R code looks something like

%_tmp255 = load i64** %cse6.103
store i64 %_tmp250, i64* %_tmp255
%_tmp256 = load i64** %cse6.103
%_tmp257 = load i64* %_tmp256

which means the same address is loaded twice, first to store a value, and then to load it back.

The MachineInstructions to load an i64 are first pseudos and are then split post regalloc and become

SU(0): addrReg0 = load *fp(-50)   // Two address registers with same value
SU(1): addrReg1 = load *fp(-50)
SU(2): store dataReg0:lo, *addrReg0(2) // Store a register in two parts
SU(3): store dataReg0:hi, *addrReg0
SU(4): dataReg1:lo = load *addrReg1(2) // Load a register in two parts
SU(5): dataReg1:hi = load *addrReg1

Since the addresses are loaded from memory, the underlying Objs become empty for all MIs.

SU(4) and SU(5) get pushed to PendingLoads.
SU(3) becomes AliasChain, and edges are added to SU(4) and SU(5). PendingLoads is cleared.
SU(2) becomes AliasChain. This time TII->areMemAccessesTriviallyDisjoint() return true, since it can see that addrReg0 with and without offset are disjoint. This was not the case between SU(3) and SU(4), since they were different address registers (with the same value). The result is that there is no edge added between SU(2) and SU(3) and not to SU(4) since PendlingLoads was cleared earlier. SU(2) and SU(4) are however a store and a load against the same address.

The problem is that TII->areMemAccessesTriviallyDisjoint() is incomplete and therefore inconsistent depending on if the two memory accesses are trivial to analyze or not.

Since TII->areMemAccessesTriviallyDisjoint() are called when resetting AliasChain, I think it is necessary to call iterateChainSucs() on the old AliasChain, to make sure there are no SUs succeeding the old AliasChain (and are thus not in RejectMemNodes) that have a dependency on the new AliasChain.

Or am I missing something? Very interested in your opinion.

I am thinking of something like

    new_alias_chain:
      // Chain all possibly aliasing memory references through SU.
      if (AliasChain) {
        unsigned ChainLatency = 0;
        if (AliasChain->getInstr()->mayLoad())           ChainLatency = TrueMemOrderLatency;
         addChainDependency(AAForDep, MFI, SU, AliasChain, RejectMemNodes,
                            ChainLatency);
+
+        // Since TII->areMemAccessesTriviallyDisjoint() is not
+        // complete, iterate all chain successors of old
+        // AliasChain. Otherwise, if an address is stored in two
+        // registers, and only one of the registers is trivially
+        // disjoint to old AliasChain, a dependency might be missed.
+        // SU(0: Address A) -> old AliasChain (no edge) SU(2: Address A)
+        // SU(0) and SU(2) get a missed dependency.
+        SmallPtrSet<const SUnit*, 16> Visited;
+        unsigned Depth = 0;
+        for (SUnit::const_succ_iterator J = AliasChain->Succs.begin(),
+               JE = AliasChain->Succs.end(); J != JE; ++J)
+          if (J->isCtrl())
+            iterateChainSucc (AA, MFI, SU, J->getSUnit(),
+                              &ExitSU, &Depth, Visited);
       }
       AliasChain = SU;


Best regards,

Jonas Paulsson

-----Original Message-----
From: Hal Finkel [mailto:hfinkel at anl.gov] 
Sent: den 9 december 2014 19:43
To: Jonas Paulsson
Cc: Mattias Eriksson V; llvmdev at cs.uiuc.edu; Sanjin Sijaric; Tom Stellard; Andrew Trick
Subject: Re: ScheduleDAGInstrs.cpp

Hi Jonas,

Tom Stellard (cc'd) just recently fixed a bug whereby dependencies on the barrier chain would not be added when the SU had no underlying objects (r223717). Does this fix the problem you're highlighting?

I've also cc'd Sanjin who developed the areMemAccessesTriviallyDisjoint() callback (which I'll note is a relatively-recent addition -- added on Sept. 8th of this year).

In short, if r223717 does not resolve the problem, it sounds like you likely found a bug. What target are you using? I'm trying to get some idea of what your areMemAccessesTriviallyDisjoint() callback is doing.

 -Hal

----- Original Message -----
> From: "Jonas Paulsson" <jonas.paulsson at ericsson.com>
> To: hfinkel at anl.gov, llvmdev at cs.uiuc.edu
> Cc: "Mattias Eriksson V" <mattias.v.eriksson at ericsson.com>
> Sent: Monday, December 8, 2014 8:06:27 AM
> Subject: ScheduleDAGInstrs.cpp
>
> Hi,
> 
> Can anyone help me to understand the
> ScheduleDAGInstrs::buildSchedGraph() method?
> 
> 
> 
> I find the handling of AliasChain is disturbing since:
> 
> 
> 
> 1. A new alias chain add deps to all possibly aliasing SUs, and then 
> clears those lists.
> 
> 2. When AliasChain is present, the addChainDependency() method is 
> called,
> 
> but the target hook areMemAccessesTriviallyDisjoint() called inside
> 
> MIsNeedChainEdge() allows this edge to be skipped.
> 
> 
> 
> This means that I get a case where
> 
> 
> 
> SU0
> 
> 
> 
> SU1, AliasChain
> 
> /\
> 
> / \ // Aliasing memory accesses
> 
> SU2
> 
> 
> 
> all SUs have memory operands, but the underlying objects vectors are 
> empty.
> 
> SU1 became AliasChain, added dep to SU2, and cleared the lists for 
> aliasing memory accesses.
> 
> SU0 has a dependency towards SU2, but towards SU1 it is trivially 
> disjoint, and therefore it gets
> 
> no dependency to SU1 and * neither to SU2 *. The AliasChain concept is 
> bypassed.
> 
> 
> 
> I don’t understand how it can first be assumed that an SU becomes 
> AliasChain, and then an SU
> 
> with lower NodeNum that may alias is allowed to skip its dep to the 
> AliasChain?
> 
> The BarrierChain is never skipped because addPred() is called 
> directly, and I don’t see how it is
> 
> safe to skip the AliasChain for aliasing SUs, I think it should always 
> be added? In other words,
> 
> it may be that SU0 has a dep towards SU2 in the example, but not 
> towards SU1, so therefore it
> 
> is not safe to skip this dep.
> 
> 
> 
> Calling addPred() instead of addChainDependency() for AliasChain 
> should fix this, however it
> 
> would lead to overly constrained DAGs compared to putting the edges 
> where they actually should
> 
> be (SU0<-SU2 instead of SU0<-SU1).
> 
> 
> 
> Most thankful for any help,
> 
> 
> 
> Jonas Paulsson
> 
> 
> 
> 

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