[LLVMdev] MI DAG constructor indeterminism
atrick at apple.com
Tue Oct 16 20:44:15 PDT 2012
On Oct 16, 2012, at 1:43 PM, Sergei Larin <slarin at codeaurora.org> wrote:
> 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.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the llvm-dev