3 ms·
From "Copy coalescing by graph recoloring" PLDI'08, which compared several SSA-based copy coalescing techniques (including an expensive, but optimal, ILP-based
by sddfd 9y ago
From "Copy coalescing by graph recoloring" PLDI'08, which compared several SSA-based copy coalescing techniques (including an expensive, but optimal, ILP-based formulation) to
iterated register coalescing (TOPLAS 1996):
> We ran iterated register coalescing [11] (the state of the art in safe coalescing) on these graphs and compared the remaining costs and unsatisfied affinities: Iterated coalescing left 1.28 times more costs non-eliminated and 1.79 times more affinities unsatisfied than the algorithm presented in this paper. To put it another way, from
the cost iterated coalescing left, we were able to optimize 22.5% away (and 44.3% of the affinities). The optimum, as determined by the ILP, is given by 35.9% of the costs (and 51.9% of the affinites) iterated coalescing left over.
- bonzini 9y agoThat does not take into account the extra moves or exchanges introduced by the out-of-SSA transformation, if I understand correctly.
- sddfd 9y agoMy understanding is that they are included. The paper talks about the problem it is addressing in Section 2. The following text is taken from that section and makes me think that extra moves/exchanges introduced by out-of-SSA are included. > Live-range splitting to handle register constraints and φ-functions make use of parallel copy instructions. These parallel copy instructions have of course to be implemented using real processor instructions (in the case of φ-functions this is called SSA destruction [5]). In contrast to traditional approaches, these parallel copies are implemented after register allocation and not before. [...] the goal of coalescing is to minimize the number of instructions to implement parallel copies by trying to give corresponding operands and results the same color.
- bonzini 9y agoThe problem is that actual computers do not have parallel copy instructions. Did they count the cost of simulating them through moves? (I knew the people doing this research, but it was almost 10 years ago so I am a bit rusty).