[MIR] Improve PRE condition of MachineCSE optimization

[anton-afanasyev]

Summary

Two equal instrs are partially redundant if their basic blocks are reachable
from one to another but one doesn't dominate another. For this case
one can hoist them to their common dominator block. But such hoisting makes
optimization sense only if their blocks are reachable from one to another
without passing through their common dominator. This change makes this check
preventing PRE from useless instr duplication (leading to hoisting after CSE
elimination).

[lebedev.ri]

(is this missing a test?)

[anton-afanasyev]

In D63934#1562377, @lebedev.ri wrote:

(is this missing a test?)

Oops, sure, I'm to add it.

[anton-afanasyev]

Added test

[anton-afanasyev]

Ping!
This patch fixes https://llvm.org/pr42405 implicitly.

[asbirlea]

llvm/lib/CodeGen/MachineCSE.cpp

824

Unrelated with this patch: Check CMBB != nullptr?

[anton-afanasyev]

llvm/lib/CodeGen/MachineCSE.cpp

824

Good point, I haven't faced this issue, but this is actually potentially a bug. I'm to include fix right to this patch. Thank you!

[anton-afanasyev]

Add small fix

[aymanmus]

Just to make sure I understand the change correctly:
This can still hoist instructions outside of their BB and execute them speculatively even if you can't prove that all possible paths execute the instruction, am I right?

[anton-afanasyev]

In D63934#1575308, @aymanmus wrote:

Just to make sure I understand the change correctly:
This can still hoist instructions outside of their BB and execute them speculatively even if you can't prove that all possible paths execute the instruction, am I right?

Hi @aymanmus, yes, you are right, and this fact is confusing me. You are right -- the speculativeinstruction execution shouldn't be possible after optimization, even if the average performance is growing up. This wasn't intented when I implemented PRE, I'm to take actions for fixing this.

[aymanmus]

Thanks Anton.
Can you please keep us updated with any progress in this regard?

[anton-afanasyev]

In D63934#1584574, @aymanmus wrote:

Thanks Anton.
Can you please keep us updated with any progress in this regard?

Sure. I'm to take one-two days more for fixing effort, otherwise I will have to revert my original commit.

[anton-afanasyev]

Hi all! I've figured out that my current implementation of PRE is incorrect and it needs to be either corrected, restricted or reverted.
The issue is that current PRE can actually hoist instruction executing it speculatively for some CFG paths which potentially leads to perf degradation. However I believe that current heuristic PRE is rather useful if it is restricted enough. Good restriction (apart from this revision) is implemented by @lkail here: https://reviews.llvm.org/D64394, it is based on basic block frequencies comparision.

@asbirlea, @aymanmus, @igorb -- does this restriction solve your particular issues with perf degradation?
Yes, this restriction still allows speculative execution (so one need to forbid hoisting of "illegal" instructions like throwable ones), but this execution consider to be beneficial.

[igorb]

LGTM

llvm/lib/CodeGen/MachineCSE.cpp

bool isProfitableToCSE(unsigned CSReg, unsigned Reg,
                            MachineBasicBlock *CSBB, MachineInstr *MI);
     void EnterScope(MachineBasicBlock *MBB);
     void ExitScope(MachineBasicBlock *MBB);
     bool ProcessBlockCSE(MachineBasicBlock *MBB);
     void ExitScopeIfDone(MachineDomTreeNode *Node,
                          DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren);
     bool PerformCSE(MachineDomTreeNode *Node);
 
+    bool isPotentiallyReachableWithoutPassing(const BasicBlock *BBA,
+                                              const BasicBlock *BBB,
+                                              const BasicBlock *ExclusionBB,
+                                              const DominatorTree *DT,
+                                              const LoopInfo *LI);
+
     bool isPRECandidate(MachineInstr *MI);
     bool ProcessBlockPRE(MachineDominatorTree *MDT, MachineBasicBlock *MBB);
     bool PerformSimplePRE(MachineDominatorTree *DT);
   };
 
 } // end anonymous namespace
 
 char MachineCSE::ID = 0;
bool MachineCSE::isPRECandidate(MachineInstr *MI) {
 
   for (auto use : MI->uses())
     if (use.isReg() && !TRI->isVirtualRegister(use.getReg()))
       return false;
 
   return true;
 }
 
+/// Determine whether block 'To' is reachable from 'From', without passing
+/// through ExclusionBB block, returning true if uncertain.
+bool MachineCSE::isPotentiallyReachableWithoutPassing(
+    const BasicBlock *From, const BasicBlock *To, const BasicBlock *ExclusionBB,
+    const DominatorTree *DT = nullptr, const LoopInfo *LI = nullptr) {
+
+  SmallVector<BasicBlock *, 32> Worklist;
+  SmallPtrSet<BasicBlock *, 1> ExclusionSet;
+  Worklist.push_back(const_cast<BasicBlock *>(From));
+  if (ExclusionBB != nullptr)
+    ExclusionSet.insert(const_cast<BasicBlock *>(ExclusionBB));
+
+  return llvm::isPotentiallyReachableFromMany(
+      Worklist, const_cast<BasicBlock *>(To), &ExclusionSet, DT, LI);
+}
+
 bool MachineCSE::ProcessBlockPRE(MachineDominatorTree *DT,
                                  MachineBasicBlock *MBB) {
   bool Changed = false;
   for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E;) {
     MachineInstr *MI = &*I;
     ++I;
 
     if (!isPRECandidate(MI))
       continue;
 
     if (!PREMap.count(MI)) {
       PREMap[MI] = MBB;
       continue;
     }
 
     auto MBB1 = PREMap[MI];
     assert(
         !DT->properlyDominates(MBB, MBB1) &&
         "MBB cannot properly dominate MBB1 while DFS through dominators tree!");
     auto CMBB = DT->findNearestCommonDominator(MBB, MBB1);
     if (!CMBB->isLegalToHoistInto())
       continue;
 
-    // Two instrs are partial redundant if their basic blocks are reachable
-    // from one to another but one doesn't dominate another.
+    // Two equal instrs are partially redundant if their basic blocks are
+    // reachable from one to another but one doesn't dominate another.
     if (CMBB != MBB1) {
-      auto BB = MBB->getBasicBlock(), BB1 = MBB1->getBasicBlock();
+      auto BB = MBB->getBasicBlock(), BB1 = MBB1->getBasicBlock(),
+           CBB = CMBB->getBasicBlock();
       if (BB != nullptr && BB1 != nullptr &&
-          (isPotentiallyReachable(BB1, BB) ||
-           isPotentiallyReachable(BB, BB1))) {
+          (MachineCSE::isPotentiallyReachableWithoutPassing(BB1, BB, CBB) ||
+           MachineCSE::isPotentiallyReachableWithoutPassing(BB, BB1, CBB))) {
 
         assert(MI->getOperand(0).isDef() &&
                "First operand of instr with one explicit def must be this def");
         unsigned VReg = MI->getOperand(0).getReg();
         unsigned NewReg = MRI->cloneVirtualRegister(VReg);
         if (!isProfitableToCSE(NewReg, VReg, CMBB, MI))
           continue;
         MachineInstr &NewMI =

llvm/test/CodeGen/MIR/AArch64/machine-cse-pre.mir

+# RUN: llc -mtriple=aarch64-none-linux-gnu -run-pass=machine-cse -o - %s | FileCheck %s
+# This test ensures that MachineCSE pass doesn't hoist equal instrs SDIVWr.
+# Such hoisting makes no sense, since these instrs are actually not partially
+# redundant, their basic blocks are reachable from one to another only through
+# their common dominator block.
+
+# CHECK: SDIVWr
+# CHECK: SDIVWr
+
+--- |
+
+  define dso_local void @foo(i32 %segment_index, i32 %num_segments, i16* nocapture %scores, i8* nocapture readonly %arr_segments_ptr) local_unnamed_addr {
+  entry:
+    br label %while.body
+
+  while.body:                                       ; preds = %if.end8, %entry
+    %0 = bitcast i8* %arr_segments_ptr to i16*
+    %1 = load i16, i16* %0, align 2
+    %conv = sext i16 %1 to i32
+    %cmp = icmp sgt i16 %1, 0
+    br i1 %cmp, label %if.then, label %if.else
+
+  if.then:                                          ; preds = %while.body
+    %div = sdiv i32 65535, %conv
+    %mul = shl nsw i32 %div, 3
+    br label %if.end8
+
+  if.else:                                          ; preds = %while.body
+    %2 = trunc i32 %conv to i16
+    %cmp2 = icmp slt i16 %2, 0
+    br i1 %cmp2, label %if.then4, label %if.end8
+
+  if.then4:                                         ; preds = %if.else
+    %div6 = sdiv i32 65535, %conv
+    %mul7 = shl nsw i32 %div6, 3
+    br label %if.end8
+
+  if.end8:                                          ; preds = %if.then4, %if.else, %if.then
+    %ye.0 = phi i32 [ 8, %if.then ], [ %mul7, %if.then4 ], [ 8, %if.else ]
+    %ys.0 = phi i32 [ %mul, %if.then ], [ 8, %if.then4 ], [ 8, %if.else ]
+    %add = add nsw i32 %ys.0, %ye.0
+    %conv9 = trunc i32 %add to i16
+    store i16 %conv9, i16* %scores, align 2
+    br label %while.body
+  }
+
+...
+---
+name:            foo
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+    successors: %bb.1(0x80000000)
+    liveins: $x2, $x3
+
+    %8:gpr64common = COPY $x3
+    %7:gpr64common = COPY $x2
+    %19:gpr32 = MOVi32imm 65535
+
+  bb.1.while.body:
+    successors: %bb.2(0x50000000), %bb.3(0x30000000)
+
+    %9:gpr32common = LDRSHWui %8, 0 :: (load 2 from %ir.0)
+    %0:gpr32 = COPY %9
+    %10:gpr32 = SUBSWri %9, 1, 0, implicit-def $nzcv
+    Bcc 11, %bb.3, implicit $nzcv
+    B %bb.2
+
+  bb.2.if.then:
+    successors: %bb.5(0x80000000)
+
+    %20:gpr32 = SDIVWr %19, %0
+    %21:gpr32 = nsw UBFMWri killed %20, 29, 28
+    %22:gpr32 = MOVi32imm 8
+    %18:gpr32all = COPY %22
+    %1:gpr32all = COPY %21
+    B %bb.5
+
+  bb.3.if.else:
+    successors: %bb.4(0x30000000), %bb.5(0x50000000)
+
+    %12:gpr32 = MOVi32imm 8
+    %11:gpr32all = COPY %12
+    TBZW %0, 31, %bb.5
+    B %bb.4
+
+  bb.4.if.then4:
+    successors: %bb.5(0x80000000)
+
+    %15:gpr32 = SDIVWr %19, %0
+    %16:gpr32 = nsw UBFMWri killed %15, 29, 28
+    %17:gpr32 = MOVi32imm 8
+    %13:gpr32all = COPY %17
+    %2:gpr32all = COPY %16
+
+  bb.5.if.end8:
+    successors: %bb.1(0x80000000)
+
+    %3:gpr32 = PHI %11, %bb.3, %2, %bb.4, %18, %bb.2
+    %4:gpr32 = PHI %11, %bb.3, %13, %bb.4, %1, %bb.2
+    %23:gpr32 = nsw ADDWrr %4, %3
+    STRHHui killed %23, %7, 0 :: (store 2 into %ir.scores)
+    B %bb.1
+
+...