Bad regression in coherence checking in winapi

[brson]

Coherence checking from winapi went from negligible time to 126 seconds.

From @retep998 on IRC.

22:28 < WindowsBunnies> acrichto: brson: um, I'm experiencing a bit of a coherence checking regression
22:28 < WindowsBunnies> 126 seconds on coherence checking for winapi using rustc 1.9.0-nightly (21922e1f4 2016-03-21)
22:29 < WindowsBunnies> aturon: I'm poking you because eddyb suspects it was specialization that caused it and you did specialization
22:29  * WindowsBunnies updates to latest nightly to check whether it still occurs
22:38 < WindowsBunnies> Okay, I can confirm that it occurs with latest nightly multirust-rs could get me which is rustc 1.9.0-nightly (d7a71687e 2016-03-24)
22:39 < WindowsBunnies> Here is the -Ztime-passes https://gist.github.com/retep998/d8a276e41112ec4ff539
22:40 < WindowsBunnies> for the record, here is what compile times used to look like some months ago https://gist.github.com/retep998/0e9aaeb53037bb6b89ae
22:42 < WindowsBunnies> time: 147.409; rss: 333MB       coherence checking

I can't offer further information now. cc @rust-lang/lang.

[aturon]

cc me

[nikomatsakis]

Certainly specialization seems like a likely candidate. I wonder if some simple hashing using simplified types could help here? Have to go review what the code does.

[aturon]

At the moment, specialization does essentially no caching, relying instead on selection caching. However, I believe that the coherence part of specialization (where the graph is built) is not able to use this cache as currently written. There are lots of easy opportunities to do better, if this is indeed the culprit.

[aturon]

I confirmed that this is due to specialization. I think, in particular, it's stemming from the move away from using simplified types.

Amusingly, the initial version of the code I wrote for the specialization graph actually did keep the simplified type distinction, but I dropped it because I doubted it was worthwhile here. Looks like I was wrong! I'll work to get a patch together in the next couple of days.

[aturon]

Fix here: #32748