PR86939 shows a problem where IRA (and LRA) adds an unneeded conflict between a pseudo reg and a hard reg leading to an unnecessary copy. The definition of conflict that most register allocators use is that two live ranges conflict if one is "live" at the definition of the other and they have different values (here "live" means live and available). In computing conflicts, IRA/LRA do not try and represent the "...and they have different values" which leads to the unneeded conflict. They also add conflicts when they handle insn operand uses, rather than at operand definitions that the definition above implies and that other allocators I know about do.
The following 2 patches fixes (some) of the problems mentioned above and is enough to fix the performance problem reported in the PR. Firstly, PATCH 1 changes IRA and LRA to compute conflicts when handling definitions, rather than at uses. This change is required by the second patch, since we cannot handle reg to reg copies specially (ie, skip the addition of a conflict) if we've already made them conflict because we noticed they're live simultaneously. Technically, this should only make a difference in the conflicts computed for two live ranges that are both undefined. Not really likely. I also took it upon myself to rename the *_born functions, since the live ranges are not born at the point we call them. They are actually deaths/last uses and we need to add them to the "live" sets (we traverse the basic blocks in reverse). Therefore, I changes the suffix from _born to _live. PATCH 2 adds the special handling of pseudo to/from hard reg copies. Specifically, we ignore the source reg of the copy when adding conflicts for the reg that is being defined in the copy insn. A few things I'd like to point out. Normally, in the other allocators I'm familiar with, we handle conflicts for copies by removing the source reg from the "live" set, even if it doesn't die in the copy. Then when we process the copies definitions, we add conflicts with everything that is live. Since we've removed the source reg, then we've successfully not added a conflict here. Then we process the copies uses which will automatically add the source reg back to the live set. I tried that here too, but given allocno ranges computation, I couldn't do that here. I decided just to create a global var that I can test for when adding conflicts. Also, this patch does not handle pseudo to pseudo copies, since their conflicts are computed by checking their allocno ranges for overlap and I could not determine how to recognize and handle copies during that process. If someone has ideas, please let me know. Finally, I have explicitly disallowed special handling of copies of register pairs, since that is difficult to get right. I tried several solutions before finally just giving up on them. That could be a future work item along with pseudo to pseudo handling if people want. I'll note that I have bootstrapped and regtested PATCH 1 on both powerpc64le-linux and x86_64-linux with not regressions. I have also bootstrapped and regtested PATCH 1 + PATCH 2 on the same two platforms with no regressions. Vlad, Jeff or anyone else, any comments on the approach used here to fix PR86939? If the patches are "ok" as is, I'd like to commit PATCH 1 first and let it bake on trunk for a little while before committing PATCH 2. Peter
