[LLVMdev] MI DAG constructor indeterminism

[Andrew Trick]

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/20121016/48a22da7/attachment.html>