[LLVMdev] MI DAG constructor indeterminism

[Andrew Trick]

On Oct 17, 2012, at 3:10 PM, Sergei Larin <slarin at codeaurora.org> wrote:

> Andy,
>  
>   So if it is not a feature… then couple questions:
>  
>   First, I also do not see an easy way to restructure work sets in this case – so let’s assume std::map is needed here. Then the way I understand it, there are five objects that cause the indeterminism:
>  
>   std::map<const Value *, SUnit *> AliasMemDefs, NonAliasMemDefs;
>   std::map<const Value *, std::vector<SUnit *> > AliasMemUses, NonAliasMemUses;
>   std::set<SUnit*> RejectMemNodes;
>  
> …since all of them at different point of time are traversed begin to end, and as such are affected by pointer value.
>  
> The case of  “std::set<SUnit*> RejectMemNodes; “  is easy. Something like this will work:
>  
> struct SortSUComp {
>     bool operator()(const SUnit *left, const SUnit *right) const {
>       return left->NodeNum < right->NodeNum;
>     }
>   };
>  
>   typedef std::set<SUnit*, SortSUComp> SortedSUSet;
>   SortedSUSet RejectMemNodes;
>  
> But in case of Value * as a key – is there any unique ID that is deterministic and could be used here? As I understand getValueID () is not unique, or could it be sufficient in this case?
> Something as bulky as temporary sorting queue/vector is also possible, but I do not like it very much.
>  
> Any other ideas?

I don't have any great ideas, but anything is an improvement over std::map/std::set.

AFAIK we don't need to remove individual elements from the map. Is that right? So SetVector and MapVector should work fine. They don't sort by key but maintain a side vector to track insertion order.

-Andy

>  
> Thanks.
>  
> Sergei
>  
> ---
> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by The Linux Foundation
>  
> From: Andrew Trick [mailto:atrick at apple.com] 
> Sent: Tuesday, October 16, 2012 10:44 PM
> To: Sergei Larin
> Cc: 'LLVM Developers Mailing List'
> Subject: Re: [LLVMdev] MI DAG constructor indeterminism
>  
>  
> On Oct 16, 2012, at 1:43 PM, Sergei Larin <slarin at codeaurora.org> wrote:
> 
> 
>  
> Andy,
>  
>   This is less of a question but rather a status quo verification…
>  
>    We currently have certain indeterminism in MI scheduler DAG construction – it is introduces by the use of std::map/std::set during edge traversal.
> Result – a random variation in SUnit edge order (which will remain fixed thereafter). Logically, it is the same DAG, but topologically it is a slightly different one, and if some algorithm is dependent on the order of edge traversal, we can have performance and debugging indeterminism. The way I have discovered it – VLIW scheduler can produce identical cost function for a pair of SUs, making visitation order the tie breaker, which is not deterministic per above discussion. For me it is trivial to fix, but I wonder if this might become a source of well hidden issues in the future.
>  
>   I am at this time not proposing anything – a fix is definitely possible, but I wonder what people think about it before I even consider this a bug.
>  
> This looks like a bug. The edge order could even affect some heuristics and influence codegen.
>  
> I don't have a better idea than using SetVector/MapVector for Value* keys. For SUnits we could just key on NodeNum. Go ahead and file a bug and/or submit a patch.
>  
> Thanks!
> -Andy

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20121017/a71bf2ff/attachment.html>