[EarlyIfCvt] Don't if-convert if condition has only loop-invariant ops.

[fhahn]

Summary

This patch adds a heuristic to skip if-conversion if the condition has a
high chance of being predictable.

If the condition is in a loop, consider it predictable if the condition
itself or all its operands are loop-invariant. E.g. this considers a load
from a loop-invariant address predictable; we were unable to prove that it
doesn't alias any of the memory-writes in the loop, but it is likely to
read to same value multiple times.

This is a relatively crude heuristic, but it helps to prevent excessive
if-conversion in multiple workloads in practice.

[fhahn]

rebase and ping :)

[apostolakis]

This looks reasonable to me.

[dyung]

Hi @fhahn, your change is causing two test failures on several bots that seem to be the same ones found by the premerge testing. Can you take a look?

https://reviews.llvm.org/B229668
https://lab.llvm.org/buildbot/#/builders/247/builds/4440
https://lab.llvm.org/buildbot/#/builders/249/builds/4169
https://lab.llvm.org/buildbot/#/builders/231/builds/11716
https://lab.llvm.org/buildbot/#/builders/230/builds/12913

[fhahn]

Thanks, PPC tests should be updated!

llvm/lib/CodeGen/EarlyIfConversion.cpp

struct PHIInfo {
     // Latencies from Cond+Branch, TReg, and FReg to DstReg.
     int CondCycles = 0, TCycles = 0, FCycles = 0;
 
     PHIInfo(MachineInstr *phi) : PHI(phi) {}
   };
 
   SmallVector<PHIInfo, 8> PHIs;
 
-private:
   /// The branch condition determined by analyzeBranch.
   SmallVector<MachineOperand, 4> Cond;
 
+private:
   /// Instructions in Head that define values used by the conditional blocks.
   /// The hoisted instructions must be inserted after these instructions.
   SmallPtrSet<MachineInstr*, 8> InsertAfter;
 
   /// Register units clobbered by the conditional blocks.
   BitVector ClobberedRegUnits;
 
   // Scratch pad for findInsertionPoint.

 /// Apply cost model and heuristics to the if-conversion in IfConv.
 /// Return true if the conversion is a good idea.
 ///
 bool EarlyIfConverter::shouldConvertIf() {
   // Stress testing mode disables all cost considerations.
   if (Stress)
     return true;
 
+  // Do not try to if-convert if the condition has a high chance of being
+  // predictable.
+  MachineLoop *CurrentLoop = Loops->getLoopFor(IfConv.Head);
+  // If the condition is in a loop, consider it predictable if the condition
+  // itself or all its operands are loop-invariant. E.g. this considers a load
+  // from a loop-invariant address predictable; we were unable to prove that it
+  // doesn't alias any of the memory-writes in the loop, but it is likely to
+  // read to same value multiple times.
+  if (CurrentLoop && any_of(IfConv.Cond, [&](MachineOperand &MO) {
+        if (!MO.isReg() || !MO.isUse())
+          return false;
+        Register Reg = MO.getReg();
+        if (Register::isPhysicalRegister(Reg))
+          return false;
+
+        MachineInstr *Def = MRI->getVRegDef(Reg);
+        return CurrentLoop->isLoopInvariant(*Def) ||
+               all_of(Def->operands(), [&](MachineOperand &Op) {
+                 if (Op.isImm())
+                   return true;
+                 if (!MO.isReg() || !MO.isUse())
+                   return false;
+                 Register Reg = MO.getReg();
+                 if (Register::isPhysicalRegister(Reg))
+                   return false;
+
+                 MachineInstr *Def = MRI->getVRegDef(Reg);
+                 return CurrentLoop->isLoopInvariant(*Def);
+               });
+      }))
+    return false;
+
   if (!MinInstr)
     MinInstr = Traces->getEnsemble(MachineTraceStrategy::TS_MinInstrCount);
 
   MachineTraceMetrics::Trace TBBTrace = MinInstr->getTrace(IfConv.getTPred());
   MachineTraceMetrics::Trace FBBTrace = MinInstr->getTrace(IfConv.getFPred());
   LLVM_DEBUG(dbgs() << "TBB: " << TBBTrace << "FBB: " << FBBTrace);
   unsigned MinCrit = std::min(TBBTrace.getCriticalPath(),
                               FBBTrace.getCriticalPath());

llvm/test/CodeGen/AArch64/early-ifcvt-likely-predictable.mir

body:             |
   ; CHECK-NEXT:   liveins: $x0, $x1, $w2, $x3
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT:   [[COPY:%[0-9]+]]:gpr64common = COPY $x3
   ; CHECK-NEXT:   [[COPY1:%[0-9]+]]:gpr32common = COPY $w2
   ; CHECK-NEXT:   [[COPY2:%[0-9]+]]:gpr64common = COPY $x1
   ; CHECK-NEXT:   [[COPY3:%[0-9]+]]:gpr64common = COPY $x0
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT: bb.1:
-  ; CHECK-NEXT:   successors: %bb.1(0x80000000)
+  ; CHECK-NEXT:   successors: %bb.3(0x30000000), %bb.2(0x50000000)
   ; CHECK-NEXT: {{  $}}
-  ; CHECK-NEXT:   [[LDRBBui:%[0-9]+]]:gpr32common = LDRBBui [[COPY3]], 0 :: (load (s8))
+  ; CHECK-NEXT:   [[LDRBBui:%[0-9]+]]:gpr32 = LDRBBui [[COPY3]], 0 :: (load (s8))
   ; CHECK-NEXT:   [[COPY4:%[0-9]+]]:gpr32all = COPY $wzr
-  ; CHECK-NEXT:   [[COPY5:%[0-9]+]]:gpr32 = COPY [[COPY4]]
+  ; CHECK-NEXT:   [[COPY5:%[0-9]+]]:gpr32all = COPY [[COPY4]]
+  ; CHECK-NEXT:   CBZW killed [[LDRBBui]], %bb.3
+  ; CHECK-NEXT:   B %bb.2
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.2:
+  ; CHECK-NEXT:   successors: %bb.3(0x80000000)
+  ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT:   [[SUBSWri:%[0-9]+]]:gpr32 = SUBSWri [[COPY1]], 4080, 12, implicit-def $nzcv
   ; CHECK-NEXT:   [[MOVi32imm:%[0-9]+]]:gpr32 = MOVi32imm 16711680
   ; CHECK-NEXT:   [[CSELWr:%[0-9]+]]:gpr32common = CSELWr [[COPY1]], killed [[MOVi32imm]], 11, implicit $nzcv
   ; CHECK-NEXT:   [[SUBSWri1:%[0-9]+]]:gpr32 = SUBSWri [[CSELWr]], 0, 0, implicit-def $nzcv
   ; CHECK-NEXT:   [[COPY6:%[0-9]+]]:gpr32 = COPY $wzr
   ; CHECK-NEXT:   [[CSELWr1:%[0-9]+]]:gpr32 = CSELWr [[CSELWr]], [[COPY6]], 12, implicit $nzcv
-  ; CHECK-NEXT:   [[COPY7:%[0-9]+]]:gpr32 = COPY [[CSELWr1]]
+  ; CHECK-NEXT:   [[COPY7:%[0-9]+]]:gpr32all = COPY [[CSELWr1]]
   ; CHECK-NEXT:   [[SUBSWri2:%[0-9]+]]:gpr32 = SUBSWri [[COPY1]], 0, 0, implicit-def $nzcv
   ; CHECK-NEXT:   [[CSELWr2:%[0-9]+]]:gpr32 = CSELWr [[COPY1]], [[COPY6]], 12, implicit $nzcv
-  ; CHECK-NEXT:   [[COPY8:%[0-9]+]]:gpr32 = COPY [[CSELWr2]]
-  ; CHECK-NEXT:   $wzr = SUBSWri [[LDRBBui]], 0, 0, implicit-def $nzcv
-  ; CHECK-NEXT:   [[CSELWr3:%[0-9]+]]:gpr32 = CSELWr [[COPY5]], [[COPY7]], 0, implicit $nzcv
-  ; CHECK-NEXT:   $wzr = SUBSWri [[LDRBBui]], 0, 0, implicit-def $nzcv
-  ; CHECK-NEXT:   [[CSELWr4:%[0-9]+]]:gpr32 = CSELWr [[COPY5]], [[COPY8]], 0, implicit $nzcv
-  ; CHECK-NEXT:   STRBBui [[CSELWr4]], [[COPY2]], 0 :: (store (s8))
-  ; CHECK-NEXT:   STRBBui [[CSELWr3]], [[COPY]], 0 :: (store (s8))
+  ; CHECK-NEXT:   [[COPY8:%[0-9]+]]:gpr32all = COPY [[CSELWr2]]
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.3:
+  ; CHECK-NEXT:   successors: %bb.1(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[PHI:%[0-9]+]]:gpr32 = PHI [[COPY5]], %bb.1, [[COPY7]], %bb.2
+  ; CHECK-NEXT:   [[PHI1:%[0-9]+]]:gpr32 = PHI [[COPY5]], %bb.1, [[COPY8]], %bb.2
+  ; CHECK-NEXT:   STRBBui [[PHI1]], [[COPY2]], 0 :: (store (s8))
+  ; CHECK-NEXT:   STRBBui [[PHI]], [[COPY]], 0 :: (store (s8))
   ; CHECK-NEXT:   B %bb.1
   bb.0:
     liveins: $x0, $x1, $w2, $x3
 
     %20:gpr64common = COPY $x3
     %6:gpr32common = COPY $w2
     %5:gpr64common = COPY $x1
     %4:gpr64common = COPY $x0
body:             |
   ; CHECK-NEXT:   liveins: $x0, $x1, $w2, $x3
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT:   [[COPY:%[0-9]+]]:gpr64common = COPY $x3
   ; CHECK-NEXT:   [[COPY1:%[0-9]+]]:gpr32common = COPY $w2
   ; CHECK-NEXT:   [[COPY2:%[0-9]+]]:gpr64common = COPY $x1
   ; CHECK-NEXT:   [[COPY3:%[0-9]+]]:gpr64common = COPY $x0
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT: bb.1:
-  ; CHECK-NEXT:   successors: %bb.1(0x80000000)
+  ; CHECK-NEXT:   successors: %bb.3(0x30000000), %bb.2(0x50000000)
   ; CHECK-NEXT: {{  $}}
-  ; CHECK-NEXT:   [[LDRBBui:%[0-9]+]]:gpr32common = LDRBBui [[COPY3]], 0 :: (load (s8))
+  ; CHECK-NEXT:   [[LDRBBui:%[0-9]+]]:gpr32 = LDRBBui [[COPY3]], 0 :: (load (s8))
   ; CHECK-NEXT:   [[COPY4:%[0-9]+]]:gpr32all = COPY $wzr
   ; CHECK-NEXT:   [[COPY5:%[0-9]+]]:gpr32all = COPY [[COPY4]]
-  ; CHECK-NEXT:   [[COPY6:%[0-9]+]]:gpr32 = COPY [[LDRBBui]]
+  ; CHECK-NEXT:   [[COPY6:%[0-9]+]]:gpr32all = COPY [[LDRBBui]]
+  ; CHECK-NEXT:   CBZW killed [[LDRBBui]], %bb.3
+  ; CHECK-NEXT:   B %bb.2
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.2:
+  ; CHECK-NEXT:   successors: %bb.3(0x80000000)
+  ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT:   [[SUBSWri:%[0-9]+]]:gpr32 = SUBSWri [[COPY1]], 4080, 12, implicit-def $nzcv
-  ; CHECK-NEXT:   [[COPY7:%[0-9]+]]:gpr32 = COPY [[SUBSWri]]
-  ; CHECK-NEXT:   $wzr = SUBSWri [[LDRBBui]], 0, 0, implicit-def $nzcv
-  ; CHECK-NEXT:   [[CSELWr:%[0-9]+]]:gpr32 = CSELWr [[COPY6]], [[COPY7]], 0, implicit $nzcv
-  ; CHECK-NEXT:   STRBBui [[CSELWr]], [[COPY]], 0 :: (store (s8))
+  ; CHECK-NEXT:   [[COPY7:%[0-9]+]]:gpr32all = COPY [[SUBSWri]]
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.3:
+  ; CHECK-NEXT:   successors: %bb.1(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[PHI:%[0-9]+]]:gpr32 = PHI [[COPY6]], %bb.1, [[COPY7]], %bb.2
+  ; CHECK-NEXT:   STRBBui [[PHI]], [[COPY]], 0 :: (store (s8))
   ; CHECK-NEXT:   B %bb.1
   bb.0:
     liveins: $x0, $x1, $w2, $x3
 
     %20:gpr64common = COPY $x3
     %6:gpr32common = COPY $w2
     %5:gpr64common = COPY $x1
     %4:gpr64common = COPY $x0