From f542649f1b374b1bae845e4e4f6d1e82f90a9e31 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Sun, 25 Jul 2004 07:11:19 +0000 Subject: [PATCH] This patch makes use of the infrastructure implemented before to safely and aggressively coallesce live ranges even if they overlap. Consider this LLVM code for example: int %test(int %X) { %Y = mul int %X, 1 ;; Codegens to Y = X %Z = add int %X, %Y ret int %Z } The mul is just there to get a copy into the code stream. This produces this machine code: (0x869e5a8, LLVM BB @0x869b9a0): %reg1024 = mov , 1, %NOREG, 0 ;; "X" %reg1025 = mov %reg1024 ;; "Y" (subsumed by X) %reg1026 = add %reg1024, %reg1025 %EAX = mov %reg1026 ret Note that the life times of reg1024 and reg1025 overlap, even though they contain the same value. This results in this machine code: test: mov %EAX, DWORD PTR [%ESP + 4] mov %ECX, %EAX add %EAX, %ECX ret Another, worse case involves loops and PHI nodes. Consider this trivial loop: testcase: int %test2(int %X) { entry: br label %Loop Loop: %Y = phi int [%X, %entry], [%Z, %Loop] %Z = add int %Y, 1 %cond = seteq int %Z, 100 br bool %cond, label %Out, label %Loop Out: ret int %Z } Because of interactions between the PHI elimination pass and the register allocator, this got compiled to this code: test2: mov %ECX, DWORD PTR [%ESP + 4] .LBBtest2_1: *** mov %EAX, %ECX inc %EAX cmp %EAX, 100 *** mov %ECX, %EAX jne .LBBtest2_1 ret Or on powerpc, this code: _test2: mflr r0 stw r0, 8(r1) stwu r1, -60(r1) .LBB_test2_1: addi r2, r3, 1 cmpwi cr0, r2, 100 *** or r3, r2, r2 bne cr0, .LBB_test2_1 *** or r3, r2, r2 lwz r0, 68(r1) mtlr r0 addi r1, r1, 60 blr 0 With this improvement in place, we now generate this code for these two testcases, which is what we want: test: mov %EAX, DWORD PTR [%ESP + 4] add %EAX, %EAX ret test2: mov %EAX, DWORD PTR [%ESP + 4] .LBBtest2_1: inc %EAX cmp %EAX, 100 jne .LBBtest2_1 # Loop ret Or on PPC: _test2: mflr r0 stw r0, 8(r1) stwu r1, -60(r1) .LBB_test2_1: addi r3, r3, 1 cmpwi cr0, r3, 100 bne cr0, .LBB_test2_1 lwz r0, 68(r1) mtlr r0 addi r1, r1, 60 blr 0 Static numbers for spill code loads/stores/reg-reg copies (smaller is better): em3d: before: 47/25/26 after: 44/22/24 164.gzip: before: 433/245/310 after: 403/231/278 175.vpr: before: 3721/2189/1581 after: 4144/2081/1423 176.gcc: before: 26195/8866/9235 after: 25942/8082/8275 186.crafty: before: 4295/2587/3079 after: 4119/2519/2916 252.eon: before: 12754/7585/5803 after: 12508/7425/5643 256.bzip2: before: 463/226/315 after: 482:241/309 Runtime perf number samples on X86: gzip: before: 41.09 after: 39.86 bzip2: runtime: before: 56.71s after: 57.07s gcc: before: 6.16 after: 6.12 eon: before: 2.03s after: 2.00s git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15194 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/LiveInterval.cpp | 44 +++++++++++++++++++++++++++++++++++- 1 file changed, 43 insertions(+), 1 deletion(-) diff --git a/lib/CodeGen/LiveInterval.cpp b/lib/CodeGen/LiveInterval.cpp index 29bee9bd6bf..53265111048 100644 --- a/lib/CodeGen/LiveInterval.cpp +++ b/lib/CodeGen/LiveInterval.cpp @@ -60,6 +60,7 @@ bool LiveInterval::overlaps(const LiveInterval& other) const { Ranges::const_iterator ie = ranges.end(); Ranges::const_iterator j = other.ranges.begin(); Ranges::const_iterator je = other.ranges.end(); + if (i->start < j->start) { i = std::upper_bound(i, ie, j->start); if (i != ranges.begin()) --i; @@ -92,7 +93,48 @@ bool LiveInterval::overlaps(const LiveInterval& other) const { /// or if the destination of the copy is a single assignment value, and it /// only overlaps with one value in the source interval. bool LiveInterval::joinable(const LiveInterval &other, unsigned CopyIdx) const { - return overlaps(other); + const LiveRange *SourceLR = other.getLiveRangeContaining(CopyIdx-1); + const LiveRange *DestLR = getLiveRangeContaining(CopyIdx); + assert(SourceLR && DestLR && "Not joining due to a copy?"); + unsigned OtherValIdx = SourceLR->ValId; + unsigned ThisValIdx = DestLR->ValId; + + Ranges::const_iterator i = ranges.begin(); + Ranges::const_iterator ie = ranges.end(); + Ranges::const_iterator j = other.ranges.begin(); + Ranges::const_iterator je = other.ranges.end(); + + if (i->start < j->start) { + i = std::upper_bound(i, ie, j->start); + if (i != ranges.begin()) --i; + } else if (j->start < i->start) { + j = std::upper_bound(j, je, i->start); + if (j != other.ranges.begin()) --j; + } + + while (i != ie && j != je) { + if (i->start == j->start) { + // If this is not the allowed value merge, we cannot join. + if (i->ValId != ThisValIdx || j->ValId != OtherValIdx) + return true; + } else if (i->start < j->start) { + if (i->end > j->start) { + if (i->ValId != ThisValIdx || j->ValId != OtherValIdx) + return true; + } + } else { + if (j->end > i->start) { + if (i->ValId != ThisValIdx || j->ValId != OtherValIdx) + return true; + } + } + if (i->end < j->end) + ++i; + else + ++j; + } + + return false; } -- 2.34.1