On Sun, Jul 30, 2017 at 11:12 AM, Luc Van Oostenryck <luc.vanoostenryck@xxxxxxxxx> wrote: > On Sun, Jul 30, 2017 at 12:15:40AM -0400, Christopher Li wrote: >> 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. > > I was more thinking to things like done in try_to_simplify_bb(). > >> 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. > > Indeed. > >> > - 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. > > Yes, but that's totally independent of how and how often the detection > of dead code is done. At the end, every dead instructions will need > to be cleaned up (the minimum is removing pseudo usage). > >> >> 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. > > Is it possible to have a pathname or a link? It is the very first email I send out: git clone git://source.winehq.org/git/wine.git cd win/dlls/usp10/tests The test command: time sparse -m64 -c -o usp10.o usp10.c -I. -I../../../include -D__WINESRC__ -D_REENTRANT -fPIC -Wall -pipe -fno-strict-aliasing -Wdeclaration-after-statement -Wempty-body -Wignored-qualifiers -Wshift-overflow=2 -Wstrict-prototypes -Wtype-limits -Wunused-but-set-parameter -Wvla -Wwrite-strings -Wpointer-arith -Wlogical-op -gdwarf-2 -gstrict-dwarf -g -O2 I think gcc compile this file very fast but sparse spend a lot of time on it. My impression it is spending time repeat finding dominating stores. I did not look at it very deep, but I know sparse did not cache any dominating information. It do fresh search every time. > It's not the size of the file that matter here, it's the size > (and complexity) of the function(s). Yes, mean the complexity of the functions. How many blocks. My impression parse.c has the largest one I saw so far. I have't done it very scientifically. Other file all have relatively small functions. 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
