On Sat, Jul 29, 2017 at 5:47 PM, Luc Van Oostenryck <luc.vanoostenryck@xxxxxxxxx> wrote: > > We do, more or less. > Once the code is linearized and inlining is done we: > - never add new BBs > - remove some BBs (some removing edges from the CFG) > - do several kinds of branch simplification (that's moving > edge, so technically it's adding edge to the CFG, not sure it > change the dom tree though). > That is merging nodes right? Two nodes combine as one. If we consider the two nodes and one sub graph. The combine sub graph does not reach to new node. In other words, it does not extend its reachability. My guess is that should be fine. Moving block to another place is another story. > > Yes, but this calculation is not correct at all. > - each time a node is removed, the total number of nodes is smaller > and so the next time is a bit faster (this would correspond to a factor > of 2) if N >> M then it does not matter much. > - much more importantly, each time kill_unreachable_bbs() is called > *all* the currently dead BBs are removed at once. So single call > can kill several BBs. Of course, it will be different for each CFG/input > files. Yes, that would be linear to the number of blocks removed. It still need to go through the blocks to clean up the instructions usage etc. >> In the memops finding dominating store is doing a lot worse. That is >> why gcc complete that file almost instantly. Sparse takes 30 seconds >> on my machine. One big problem is it did not cache the dominating >> result. It is redoing the finding again and again. > > Uh? > Which input file your talking about? This ptrlist testing wine source file that takes 23 second for sparse to run. I take a brief look at it, it is doing a lot of dominating search. > > *smile* Feels like linear? > Did you try with several input files, some with big functions? I just try some sparse source file. The largest one is in parse.c. The paper has more detail report on using huge number of nodes. Tested on real code and random generated CFG for really large number of nodes. I am not going repeat it here. BTW, I just find out LLVM was using the exact same algorithm at some point. Not sue what they are using now. They might not build the whole tree any more. Chris -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
