I was going to reply directly to you; but the re-reply is fine. I don't think your conclusion is wrong, but your analysis is bogus AF. Compiler transforms are usually strongly superpolynomial (quadratic or cubic or some NP-hard demon); a Knuth fast pass is going to traverse the entire IR tree under observation. The thing is, the IR tree under observation is usually pretty small; while it won't fit in the localest cache, it's almost certainly not in main memory after the first sweep. Subsequent trees will be somewhere in the far reaches of memory... but there's an awful lot of work between fetching trees.