Andrew MacLeod wrote: > Kenneth Zadeck wrote: >> >> Birthpoints are not nearly as useful as phi-functions because the >> algorithms that use birthpoints do not generally leave the birthpoints >> in the right places when they are finished. There is a lot of value >> added by the operand of phi-functions. But they do solve the n**2 >> case for DU and UD chains (and because of the better SSA building >> algorithms than were available when Reif and Lewis first proposed >> their technique, will be much faster). >> > I wonder if we could use these factored copies with a threshold value > instead, such that we only use them when they will replace X uses or > defs, something that is tunable and start with high values for X. This > means the copies won't get in the way normally, and will make a big > difference when large/pathological cases come along. Experiments > could then determine a good value for X. > I see where you are going here and it has some advantages and disadvantages:
The big advantage is that we could just blow off any reg that is not always used as a whole register. This will certainly have the advantage that it will be harder to write the killer test case. The disadvantage is that one of the big time hogs with du or ud chains is that they have to be built using the rd problem which is a hog. The ssa builder is really very much faster and the second part of it, the stack based step that for ssa form does the renaming, can be easily adapted to just build chains rather than do renaming. If we leave some variables without birthpoints, we are would still have to run reaching defs to build the chains for those variables. My real point in starting this discussion was to try to interest (sucker) one of the subreg specialists into helping me solve the issue of inserting move at the birthpoint where subregs or strict lower values are used. > The copies will then only interfere with optimizations when the > situation is already horrible. In fact, it wouldn't surprise me if > this could actually *help* a number of passes, including RA, for > larger values of X :-) > > Does RTL have an efficient copy prop? That could then naturally remove > these copies when desired, and then they could be added back in as > needed the next time DU/UD chains are built. If they weren't removed, > the next DU/UD build wouldn't trigger the threshold machinery since > the copy is already there, and we still end up with the same results. > not really and not properly integrated into the ra like real compilers do. i do not know how much of this vlad has addressed in his branch. it does have the ability to delete noop moves, so as long as the move does not become necessary, it will be deleted. >> There is the complication of how to add the noop move in the presence >> of SUBREGs, and given the amount of pain that I suffered in adding the >> > > If we used thresholding, you could try simply punting on these > initially and see what happens, and only deal with it when it becomes > an issue. > > Anyway, just a thought on how to make it less intrusive. Less intrusive is good, but i want it to be real enough so that the "he only solved part of the problem" sideliners do not attack this. > > Andrew
