Index: lib/CodeGen/MachineSink.cpp =================================================================== --- lib/CodeGen/MachineSink.cpp +++ lib/CodeGen/MachineSink.cpp @@ -24,6 +24,7 @@ #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" #include "llvm/CodeGen/MachineDominators.h" #include "llvm/CodeGen/MachineLoopInfo.h" +#include "llvm/CodeGen/MachinePostDominators.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" @@ -55,8 +56,9 @@ class MachineSinking : public MachineFunctionPass { const TargetInstrInfo *TII; const TargetRegisterInfo *TRI; - MachineRegisterInfo *MRI; // Machine register information - MachineDominatorTree *DT; // Machine dominator tree + MachineRegisterInfo *MRI; // Machine register information + MachineDominatorTree *DT; // Machine dominator tree + MachinePostDominatorTree *PDT; // Machine post dominator tree MachineLoopInfo *LI; const MachineBlockFrequencyInfo *MBFI; AliasAnalysis *AA; @@ -82,8 +84,10 @@ MachineFunctionPass::getAnalysisUsage(AU); AU.addRequired(); AU.addRequired(); + AU.addRequired(); AU.addRequired(); AU.addPreserved(); + AU.addPreserved(); AU.addPreserved(); if (UseBlockFreqInfo) AU.addRequired(); @@ -251,6 +255,7 @@ TRI = TM.getSubtargetImpl()->getRegisterInfo(); MRI = &MF.getRegInfo(); DT = &getAnalysis(); + PDT = &getAnalysis(); LI = &getAnalysis(); MBFI = UseBlockFreqInfo ? &getAnalysis() : nullptr; AA = &getAnalysis(); @@ -469,23 +474,6 @@ } } -/// isPostDominatedBy - Return true if A is post dominated by B. -static bool isPostDominatedBy(MachineBasicBlock *A, MachineBasicBlock *B) { - - // FIXME - Use real post dominator. - if (A->succ_size() != 2) - return false; - MachineBasicBlock::succ_iterator I = A->succ_begin(); - if (B == *I) - ++I; - MachineBasicBlock *OtherSuccBlock = *I; - if (OtherSuccBlock->succ_size() != 1 || - *(OtherSuccBlock->succ_begin()) != B) - return false; - - return true; -} - /// isProfitableToSinkTo - Return true if it is profitable to sink MI. bool MachineSinking::isProfitableToSinkTo(unsigned Reg, MachineInstr *MI, MachineBasicBlock *MBB, @@ -497,8 +485,13 @@ return false; // It is profitable if SuccToSinkTo does not post dominate current block. - if (!isPostDominatedBy(MBB, SuccToSinkTo)) - return true; + if (!PDT->dominates(SuccToSinkTo, MBB)) + return true; + + // It is profitable to sink an instruction from a deeper loop to a shallower + // loop, even if the latter post-dominates the former (PR21115). + if (LI->getLoopDepth(MBB) > LI->getLoopDepth(SuccToSinkTo)) + return true; // Check if only use in post dominated block is PHI instruction. bool NonPHIUse = false; Index: test/CodeGen/NVPTX/machine-sink.ll =================================================================== --- /dev/null +++ test/CodeGen/NVPTX/machine-sink.ll @@ -0,0 +1,40 @@ +; RUN: llc < %s -march=nvptx -mcpu=sm_20 | FileCheck %s + +target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v16:16:16-v32:32:32-v64:64:64-v128:128:128-n16:32:64" + +@scalar1 = internal addrspace(3) global float 0.000000e+00, align 4 +@scalar2 = internal addrspace(3) global float 0.000000e+00, align 4 + +; We shouldn't sink mul.rn.f32 to BB %merge because BB %merge post-dominates +; BB %entry. Over-sinking created more register pressure on this example. The +; backend would sink the fmuls to BB %merge, but not the loads for being +; conservative on sinking memory accesses. As a result, the loads and +; the two fmuls would be separated to two basic blocks, causing two +; cross-BB live ranges. +define float @post_dominate(float %x, i1 %cond) { +; CHECK-LABEL: post_dominate( +entry: + %0 = load float* addrspacecast (float addrspace(3)* @scalar1 to float*), align 4 + %1 = load float* addrspacecast (float addrspace(3)* @scalar2 to float*), align 4 +; CHECK: ld.shared.f32 +; CHECK: ld.shared.f32 + %2 = fmul float %0, %0 + %3 = fmul float %1, %2 +; CHECK-NOT: bra +; CHECK: mul.rn.f32 +; CHECK: mul.rn.f32 + br i1 %cond, label %then, label %merge + +then: + %z = fadd float %x, %x + br label %then2 + +then2: + %z2 = fadd float %z, %z + br label %merge + +merge: + %y = phi float [ 0.0, %entry ], [ %z2, %then2 ] + %w = fadd float %y, %3 + ret float %w +} Index: test/CodeGen/X86/loop-strength-reduce8.ll =================================================================== --- test/CodeGen/X86/loop-strength-reduce8.ll +++ test/CodeGen/X86/loop-strength-reduce8.ll @@ -1,6 +1,9 @@ ; RUN: llc < %s -mtriple=i386-apple-darwin | FileCheck %s -; CHECK: leal 16(%eax), %edx +; FIXME: The first two instructions, movl and addl, should have been combined to +; "leal 16(%eax), %edx" by the backend (PR20776). +; CHECK: movl %eax, %edx +; CHECK: addl $16, %edx ; CHECK: align ; CHECK: addl $4, %edx ; CHECK: decl %ecx Index: test/CodeGen/X86/sink-out-of-loop.ll =================================================================== --- test/CodeGen/X86/sink-out-of-loop.ll +++ test/CodeGen/X86/sink-out-of-loop.ll @@ -5,7 +5,7 @@ ; MOV32ri outside the loop. ; rdar://11980766 define i32 @sink_succ(i32 %argc, i8** nocapture %argv) nounwind uwtable ssp { -; CHECK: sink_succ +; CHECK-LABEL: sink_succ ; CHECK: [[OUTER_LN1:LBB0_[0-9]+]]: ## %preheader ; CHECK: %exit ; CHECK-NOT: movl @@ -52,3 +52,24 @@ for.end20: ret i32 0 } + +define i32 @sink_out_of_loop(i32 %n, i32* %output) { +; CHECK-LABEL: sink_out_of_loop: +entry: + br label %loop + +loop: + %i = phi i32 [ 0, %entry ], [ %i2, %loop ] + %j = mul i32 %i, %i + %addr = getelementptr i32* %output, i32 %i + store i32 %i, i32* %addr + %i2 = add i32 %i, 1 + %exit_cond = icmp sge i32 %i2, %n + br i1 %exit_cond, label %exit, label %loop + +exit: +; CHECK: BB#2 +; CHECK: imull %eax, %eax +; CHECK: retq + ret i32 %j +}