Fast greedy weighted fusion

Loop fusion is an important compiler strategy for managing memory hierarchy . By fusing loops that use the same data elements, a compiler can reduce th e distance between accesses to the same datum and avoid costly cache misses . Unfortunately the problem of optimal loop fusion for reuse has been shown to be NP-hard, so compilers must resort to heuristics to avoid unreasonabl y long compile times. Greedy strategies are often excellent heuristics that produce high-quality solutions quickly. We present an algorithm for greedy weighted fusion, in which the heaviest edge (the one with the most reuse) is selected for possible fusion on each step. The algorithm is shown to be fast in the sense that it takes O(V(E+V)) time, which is arguably optimal f or producing the greedy solution. In addition, this algorithm has the advan tage that it requires only O(E) edge reweighting operations after fusions. This means that it is suitable for use on the problem of enhancing cache re use, for which the ideal reweighting operation is much more complex than ad dition. If each reweighting operation requires no more than O(V) time, the time bound of the overall fusion process remains at O(V(E+V)).