[MachineSink] Use the real post dominator tree

[jingyue]

Summary

Fixes a FIXME in MachineSinking. Instead of using the simple heuristics in
isPostDominatedBy, use the real MachinePostDominatorTree and MachineLoopInfo.
The old heuristics caused instructions to sink unnecessarily, and might create
register pressure.

This is the second try of the fix. The first one (D4814) caused a performance
regression due to failing to sink instructions out of loops (PR21115). This
patch fixes PR21115 by sinking an instruction from a deeper loop to a shallower
one regardless of whether the target block post-dominates the source.

Thanks Alexey Volkov for reporting PR21115!

[jingyue]

Compilation time from llvm-test-suite. Three columns are benchmark name, original compilation time (in seconds), and the slowdown/speedup caused by this change (negative means the new version is faster). I only picked the ones with compilation time longer than one second, because other data points are very noisy.

I don't see a significant regression in compilation time based on these numbers.

clamscan                                              9.6843             -0.7650%
ldecod                                                4.5576              0.6604%
lencod                                                9.8791              1.5637%
SPASS                                                 9.5813              2.0035%
make_dparser                                          2.0540              1.2723%
kc                                                   10.0371             -0.1296%
lua                                                   2.6484              2.4356%
oggenc                                                3.1777              1.0269%
siod                                                  1.4711              1.3638%
sqlite3                                              12.4904              0.4944%
treecc                                                1.3868             -1.7237%
7zip-benchmark                                       27.6821             -0.2909%
smg2000                                               4.7685              2.4668%
bullet                                               20.0863              0.6708%
espresso                                              3.6563              1.7755%
gs                                                    2.9518             -0.8027%
consumer-jpeg                                         3.4321             -0.4087%
consumer-lame                                         2.8166              2.2606%
consumer-typeset                                      7.7711              0.4109%
office-ispell                                         1.1021              0.0816%
paq8p                                                 1.3805              0.0290%
timberwolfmc                                          6.3654             -1.0692%
mybison                                               1.1789              1.8489%
ControlFlow-dbl                                       1.0986              0.1001%
ControlFlow-flt                                       1.0994             -1.3461%
ControlLoops-dbl                                      1.0301             -1.3881%
ControlLoops-flt                                      1.0259             -0.1170%
CrossingThresholds-dbl                                1.0041             -0.6896%
Equivalencing-flt                                     1.0074             -2.5841%
Expansion-dbl                                         1.0220             -0.4315%
Expansion-flt                                         1.0275              0.0097%
GlobalDataFlow-dbl                                    1.0226             -0.2546%
GlobalDataFlow-flt                                    1.0147             -0.2072%
InductionVariable-dbl                                 1.0076             -0.3878%
LinearDependence-dbl                                  1.0397             -0.0866%
LinearDependence-flt                                  1.0477             -1.8301%
LoopRestructuring-flt                                 1.0237             -0.9422%
Reductions-dbl                                        1.0482              0.1239%
Reductions-flt                                        1.0262              2.6349%
pairlocalalign                                        6.6571             -1.3261%
cjpeg                                                 3.3882              2.9228%
tramp3d-v4                                           15.5355              0.0097%
loop_unroll                                           2.6732              0.4218%
simple_types_constant_folding                         2.1412              0.5031%
simple_types_loop_invariant                           1.7099             -0.3104%
spirit                                                3.0955              0.3676%

[jingyue]

Runtime performance per SPEC CINT2006. The four columns are benchmark name, reference time (not useful here), run time, and ratio vs reference (not useful here).

Original

400.perlbench    9770        320       30.5 S                                  
400.perlbench    9770        323       30.3 *                                  
400.perlbench    9770        324       30.2 S                                  
401.bzip2        9650        420       23.0 S                                  
401.bzip2        9650        451       21.4 S                                  
401.bzip2        9650        420       23.0 *                                  
403.gcc          8050        249       32.3 S                                  
403.gcc          8050        256       31.5 S                                  
403.gcc          8050        250       32.1 *                                  
429.mcf          9120        280       32.6 *                                  
429.mcf          9120        283       32.2 S                                  
429.mcf          9120        279       32.7 S                                  
445.gobmk       10490        407       25.8 *                                  
445.gobmk       10490        407       25.8 S                                  
445.gobmk       10490        407       25.8 S                                  
456.hmmer        9330        363       25.7 S                                  
456.hmmer        9330        363       25.7 *                                  
456.hmmer        9330        365       25.6 S                                  
458.sjeng       12100        492       24.6 S                                  
458.sjeng       12100        490       24.7 *                                  
458.sjeng       12100        489       24.7 S                                  
462.libquantum  20720        396       52.4 S                                  
462.libquantum  20720        403       51.4 *                                  
462.libquantum  20720        450       46.0 S                                  
464.h264ref     22130        460       48.1 *                                  
464.h264ref     22130        460       48.1 S                                  
464.h264ref     22130        461       48.0 S                                  
471.omnetpp      6250        230       27.2 *                                  
471.omnetpp      6250        231       27.1 S                                  
471.omnetpp      6250        229       27.3 S                                  
473.astar        7020        336       20.9 *                                  
473.astar        7020        338       20.8 S                                  
473.astar        7020        336       20.9 S                                  
483.xalancbmk    6900        186       37.1 *                                  
483.xalancbmk    6900        196       35.2 S                                  
483.xalancbmk    6900        185       37.2 S

With this change

400.perlbench    9770        307       31.9 S                                  
400.perlbench    9770        307       31.8 S                                  
400.perlbench    9770        307       31.9 *                                  
401.bzip2        9650        419       23.0 *                                  
401.bzip2        9650        419       23.0 S                                  
401.bzip2        9650        419       23.0 S                                  
403.gcc          8050        251       32.0 S                                  
403.gcc          8050        249       32.3 S                                  
403.gcc          8050        251       32.1 *                                  
429.mcf          9120        273       33.4 S                                  
429.mcf          9120        280       32.6 S                                  
429.mcf          9120        276       33.1 *                                  
445.gobmk       10490        406       25.9 S                                  
445.gobmk       10490        406       25.8 *                                  
445.gobmk       10490        410       25.6 S                                  
456.hmmer        9330        360       25.9 S                                  
456.hmmer        9330        361       25.9 *                                  
456.hmmer        9330        361       25.8 S                                  
458.sjeng       12100        483       25.0 S                                  
458.sjeng       12100        485       24.9 *                                  
458.sjeng       12100        486       24.9 S                                  
462.libquantum  20720        364       56.9 S                                  
462.libquantum  20720        376       55.2 *                                  
462.libquantum  20720        381       54.3 S                                  
464.h264ref     22130        457       48.4 S                                  
464.h264ref     22130        456       48.5 *                                  
464.h264ref     22130        455       48.6 S                                  
471.omnetpp      6250        228       27.4 S                                  
471.omnetpp      6250        229       27.3 S                                  
471.omnetpp      6250        228       27.4 *                                  
473.astar        7020        335       21.0 S                                  
473.astar        7020        333       21.1 S                                  
473.astar        7020        333       21.1 *                                  
483.xalancbmk    6900        186       37.2 *                                  
483.xalancbmk    6900        185       37.4 S                                  
483.xalancbmk    6900        186       37.1 S

Each benchmark was run three times and the results look stable across runs. We take the median and compute the slowdown/speedup.

benchmark	original	sink	slowdown
400.perlbench 	323	307	-4.953560372
401.bzip2     	420	419	-0.2380952381
403.gcc       	250	251	0.4
429.mcf       	280	276	-1.428571429
445.gobmk     	407	406	-0.2457002457
456.hmmer     	363	361	-0.5509641873
458.sjeng     	490	485	-1.020408163
462.libquantum	403	376	-6.699751861
464.h264ref   	460	456	-0.8695652174
471.omnetpp   	230	228	-0.8695652174
473.astar     	336	333	-0.8928571429
483.xalancbmk 	186	186	0

We see significant speedup on 400.perlbench and 462.libquantum without any significant regression.

[jingyue]

ping?

[jingyue]

Hi, anyone willing to review this patch? I think the code change is fairly straight-forward, and that the 4% and 6% speedup on perlbench and libquantum is something the community likes :) Thanks!

[hfinkel]

Given that MachineSink does not run at -O0, I think that the compile-time impact (~1.5%) looks reasonable given the advantages of doing this properly. LGTM.

[jingyue]

Thanks a lot, Hal! Committed in r219773.

lib/CodeGen/MachineSink.cpp

 #include "llvm/CodeGen/Passes.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #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"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetRegisterInfo.h"
 #include "llvm/Target/TargetSubtargetInfo.h"

 STATISTIC(NumSunk,      "Number of machine instructions sunk");
 STATISTIC(NumSplit,     "Number of critical edges split");
 STATISTIC(NumCoalesces, "Number of copies coalesced");
 
 namespace {
   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;
 
     // Remember which edges have been considered for breaking.
     SmallSet<std::pair<MachineBasicBlock*,MachineBasicBlock*>, 8>
     CEBCandidates;
     // Remember which edges we are about to split.
public:
 
     bool runOnMachineFunction(MachineFunction &MF) override;
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.setPreservesCFG();
       MachineFunctionPass::getAnalysisUsage(AU);
       AU.addRequired<AliasAnalysis>();
       AU.addRequired<MachineDominatorTree>();
+      AU.addRequired<MachinePostDominatorTree>();
       AU.addRequired<MachineLoopInfo>();
       AU.addPreserved<MachineDominatorTree>();
+      AU.addPreserved<MachinePostDominatorTree>();
       AU.addPreserved<MachineLoopInfo>();
       if (UseBlockFreqInfo)
         AU.addRequired<MachineBlockFrequencyInfo>();
     }
 
     void releaseMemory() override {
       CEBCandidates.clear();
     }
bool MachineSinking::runOnMachineFunction(MachineFunction &MF) {
 
   DEBUG(dbgs() << "******** Machine Sinking ********\n");
 
   const TargetMachine &TM = MF.getTarget();
   TII = TM.getSubtargetImpl()->getInstrInfo();
   TRI = TM.getSubtargetImpl()->getRegisterInfo();
   MRI = &MF.getRegInfo();
   DT = &getAnalysis<MachineDominatorTree>();
+  PDT = &getAnalysis<MachinePostDominatorTree>();
   LI = &getAnalysis<MachineLoopInfo>();
   MBFI = UseBlockFreqInfo ? &getAnalysis<MachineBlockFrequencyInfo>() : nullptr;
   AA = &getAnalysis<AliasAnalysis>();
 
   bool EverMadeChange = false;
 
   while (1) {
     bool MadeChange = false;
for (MachineBasicBlock::iterator DE = MI->getParent()->end();
     if (!DI->isDebugValue())
       return;
     if (DI->getOperand(0).isReg() &&
         DI->getOperand(0).getReg() == MI->getOperand(0).getReg())
       DbgValues.push_back(DI);
   }
 }
 
-/// 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,
                                           MachineBasicBlock *SuccToSinkTo) {
   assert (MI && "Invalid MachineInstr!");
   assert (SuccToSinkTo && "Invalid SinkTo Candidate BB");
 
   if (MBB == SuccToSinkTo)
     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))
 
   // Check if only use in post dominated block is PHI instruction.
   bool NonPHIUse = false;
   for (MachineInstr &UseInst : MRI->use_nodbg_instructions(Reg)) {
     MachineBasicBlock *UseBlock = UseInst.getParent();
     if (UseBlock == SuccToSinkTo && !UseInst.isPHI())
       NonPHIUse = true;
   }

test/CodeGen/NVPTX/machine-sink.ll

+; 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
+}

test/CodeGen/X86/loop-strength-reduce8.ll

 ; 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
 ; CHECK: jne     LBB0_2
 
   %struct.CUMULATIVE_ARGS = type { i32, i32, i32, i32, i32, i32, i32 }
   %struct.bitmap_element = type { %struct.bitmap_element*, %struct.bitmap_element*, i32, [2 x i64] }
   %struct.bitmap_head_def = type { %struct.bitmap_element*, %struct.bitmap_element*, i32 }

test/CodeGen/X86/sink-out-of-loop.ll

 ; RUN: llc -mtriple=x86_64-apple-darwin < %s | FileCheck %s
 
 ; A MOV32ri is inside a loop, it has two successors, one successor is inside the
 ; same loop, the other successor is outside the loop. We should be able to sink
 ; 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
 ; CHECK: jne [[OUTER_LN1]]
 ; CHECK: movl
 ; CHECK: [[LN2:LBB0_[0-9]+]]: ## %for.body2
 ; CHECK: jne [[LN2]]
 ; CHECK: ret
for.body2:
   %iv.next = add i64 %iv, 1
   %lftr.wideiv = trunc i64 %iv.next to i32
   %exitcond = icmp eq i32 %lftr.wideiv, 2048
   br i1 %exitcond, label %for.end20, label %for.body2
 
 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
+}