[MachineCSE] Add an option to enable global CSE

[• pcwang-thead]

Summary

For some scenarios like optimizing for size, we may want to do
aggressive MachineCSE on the whole function, so we add an option
--enable-aggressive-machine-cse and a target hook to enable this.

[lebedev.ri]

llvm/lib/CodeGen/MachineCSE.cpp

917–919

You can not modify global variables like that

[• pcwang-thead]

Amend commit message.

[• pcwang-thead]

Do not modify global variable EnableGlobalCSE.

[lkail]

Global is not a good name here. MachineCSE is working on the whole function, which is global in compiler's terminology, by walking through the DominatorTree.

llvm/lib/CodeGen/MachineCSE.cpp

466

Why only apply to this heuristics? Since your intention is reducing size, why not always consider profitable if hasOptSize?

[jrtc27]

llvm/lib/CodeGen/MachineCSE.cpp

55

Putting this behaviour behind a cl::opt is a great way to ensure it's never used...

llvm/test/CodeGen/RISCV/enable-global-cse.ll

1 ↗

(On Diff #388880)

This should be a MIR test that runs just MachineCSE

[• pcwang-thead]

In D114361#3146082, @lkail wrote:

Global is not a good name here. MachineCSE is working on the whole function, which is global in compiler's terminology, by walking through the DominatorTree.

Can we name it greedy?

llvm/lib/CodeGen/MachineCSE.cpp

55

LOL.

So is there a better way? Maybe we can add a target hook to enable this?

466

You are right, my thought were limited.

llvm/test/CodeGen/RISCV/enable-global-cse.ll

1 ↗

(On Diff #388880)

Thanks, I will update it later.

[• pcwang-thead]

• Change global to aggressive.
• Return true immediately if aggressive MachineCSE is enabled.
• Change test case to MIR test.

[lkail]

Added dmgreen since embeded-arm should be sensitive to size optimizations.

[dmgreen]

Thanks. What targets have you tested with this? And what kind of codesize differences have you observed?

[• pcwang-thead]

In D114361#3148156, @dmgreen wrote:

Thanks. What targets have you tested with this? And what kind of codesize differences have you observed?

RISCV.
(And it seems that I need to modify other targets' tests)

The differences(in scope of functions):

• Some loads of immediates are redundant.
• Some loads of global symbols are redundant.
• etc.

These redundancies are in nonadjacent(non-local?) blocks , so they can't be eliminated according to Heuristics #1 in MachineCSE::isProfitableToCSE.

[shchenz]

llvm/lib/CodeGen/MachineCSE.cpp

440

If the register pressure is increased, doing more CSEs may introduce register spill/reload and thus it will generate worse code even for optimization for size?

468

Can we estimate the register pressure here to do a more aggressive CSE? If so, we should not limit this only for "optimization for size".

[dmgreen]

RISCV.
(And it seems that I need to modify other targets' tests)

The differences(in scope of functions):

• Some loads of immediates are redundant.
• Some loads of global symbols are redundant.
• etc.

These redundancies are in nonadjacent(non-local?) blocks , so they can't be eliminated according to Heuristics #1 in MachineCSE::isProfitableToCSE.

OK, that's a good start. I was expected something among the lines of "I have tested RISCV on the llvm test suite or some other large codebase under Oz and it reduced the total codesize by 0.16%".

My experiments on ARM and AArch64 are not as great. This seems to increase codesize more than it reduces it, especially on ARM. The AArch64 numbers were dominated by one large increase, with some of the smaller cases being smaller. I would be interested in what the tests in-tree showed too.

You might want to check X86 as it's easy to run. If I was making target independent changed like this I would expect to test at least a couple of architecture combos (say, X86 with Arm and AArch64 for 32bit and 64bit variants), and potentially add target overrides where needed. In this case the default should maybe be kept as before, unless we have some evidence this is beneficial across most architectures.

[craig.topper]

llvm/test/CodeGen/RISCV/enable-agressive-machine-cse.mir

1

Please use update_mir_test_checks.py

[• pcwang-thead]

• Address comments.
• Only apply aggressive CSE to Heuristics 1.
• Make enableAggressiveMachineCSE return false by default.
• Remove RISCV MIR test.

[• pcwang-thead]

OK, that's a good start. I was expected something among the lines of "I have tested RISCV on the llvm test suite or some other large codebase under Oz and it reduced the total codesize by 0.16%".

My experiments on ARM and AArch64 are not as great. This seems to increase codesize more than it reduces it, especially on ARM. The AArch64 numbers were dominated by one large increase, with some of the smaller cases being smaller. I would be interested in what the tests in-tree showed too.

You might want to check X86 as it's easy to run. If I was making target independent changed like this I would expect to test at least a couple of architecture combos (say, X86 with Arm and AArch64 for 32bit and 64bit variants), and potentially add target overrides where needed. In this case the default should maybe be kept as before, unless we have some evidence this is beneficial across most architectures.

Thank you for your nice advice.

I have tested RISCV on SPECINT 2006 under Oz, here is the result:

                code size
400.perlbench    +0.438%
401.bzip2        0%
403.gcc          -1.128%
429.mcf          0%
445.gobmk        -0.221%
456.hmmer        -1.682%
458.sjeng        0%
462.libquantum   0%
464.h264ref      -0.858%
471.omnetpp      -0.616%
473.astar        0%

perlbench got increased code size.

The result may not be convincing with outdated benchmarks, so I tested it on OpenCV codebase.

Most of executable files and libraries had no code size change, while some large files got smaller, like:

opencv_perf_imgproc  -0.069%
opencv_perf_video    -0.288%
opencv_test_calib3d  -0.407%
opencv_test_core     -0.249%
opencv_test_dnn      -0.182%
opencv_test_imgproc  -0.246%
libopencv_imgproc.so -0.247%
……

Besides, third-party libraries used by OpenCV(like libquirc, libwebp, libjpeg-turbo, libtiff, etc.) got smaller code size.
Some small examples of OpenCV increased a few bytes, as a result of increment of register pressure.

I have made aggressive MachineCSE disabled by default, targets may override it if it's profitable.

In fact, I think this work-around can be more elegant via live intervals analysis as @shchenz said. At least, we should do CSE on Extended Basic Blocks instead of local or adjacent blocks.

llvm/lib/CodeGen/MachineCSE.cpp

440

Yes, you are right.

AggressiveMachineCSE should be placed after MayIncreasePressure.

468

Absolutely!

IMO, the key point is that we should do some live range analysis here?

[• pcwang-thead]

ping

[craig.topper]

llvm/lib/CodeGen/MachineCSE.cpp

466

Can this info be cached from runOnMachineFunction? No need to make a virtual call for something that wont' change per instruction.

[• pcwang-thead]

• Rebase.
• Address comment.

llvm/include/llvm/CodeGen/TargetInstrInfo.h

public:
   /// Return true if the instruction is as cheap as a move instruction.
   ///
   /// Targets for different archs need to override this, and different
   /// micro-architectures can also be finely tuned inside.
   virtual bool isAsCheapAsAMove(const MachineInstr &MI) const {
     return MI.isAsCheapAsAMove();
   }
 
+  /// Return true if we want to do aggressive MachineCSE.
+  ///
+  /// By default, aggressive MachineCSE is enabled when optimizing for size.
+  virtual bool enableAggressiveMachineCSE(const MachineFunction &MF) const {
+    return MF.getFunction().hasOptSize();
+  }
+
   /// Return true if the instruction should be sunk by MachineSink.
   ///
   /// MachineSink determines on its own whether the instruction is safe to sink;
   /// this gives the target a hook to override the default behavior with regards
   /// to which instructions should be sunk.
   virtual bool shouldSink(const MachineInstr &MI) const { return true; }
 
   /// Re-issue the specified 'original' instruction at the

llvm/lib/CodeGen/MachineCSE.cpp

 #include <iterator>
 #include <utility>
 #include <vector>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "machine-cse"
 
+static cl::opt<bool> EnableAggressiveMachineCSE(
+    "enable-aggressive-machine-cse", cl::Hidden, cl::init(false),
+    cl::desc("Enable aggressive machine CSE on the whole function."));
+
 STATISTIC(NumCoalesces, "Number of copies coalesced");
 STATISTIC(NumCSEs,      "Number of common subexpression eliminated");
 STATISTIC(NumPREs,      "Number of partial redundant expression"
                         " transformed to fully redundant");
 STATISTIC(NumPhysCSEs,
           "Number of physreg referencing common subexpr eliminated");
 STATISTIC(NumCrossBBCSEs,
           "Number of cross-MBB physreg referencing CS eliminated");
bool MachineCSE::isCSECandidate(MachineInstr *MI) {
   return true;
 }
 
 /// isProfitableToCSE - Return true if it's profitable to eliminate MI with a
 /// common expression that defines Reg. CSBB is basic block where CSReg is
 /// defined.
 bool MachineCSE::isProfitableToCSE(Register CSReg, Register Reg,
                                    MachineBasicBlock *CSBB, MachineInstr *MI) {
+  if (EnableAggressiveMachineCSE ||
+      TII->enableAggressiveMachineCSE(*MI->getMF()))
+    return true;
+
   // FIXME: Heuristics that works around the lack the live range splitting.
 
   // If CSReg is used at all uses of Reg, CSE should not increase register
   // pressure of CSReg.
   bool MayIncreasePressure = true;
   if (Register::isVirtualRegister(CSReg) && Register::isVirtualRegister(Reg)) {
     MayIncreasePressure = false;
     SmallPtrSet<MachineInstr*, 8> CSUses;
     for (MachineInstr &MI : MRI->use_nodbg_instructions(CSReg)) {
       CSUses.insert(&MI);
     }
     for (MachineInstr &MI : MRI->use_nodbg_instructions(Reg)) {
       if (!CSUses.count(&MI)) {
         MayIncreasePressure = true;
         break;
       }
     }
   }
   if (!MayIncreasePressure) return true;
 
   // Heuristics #1: Don't CSE "cheap" computation if the def is not local or in
   // an immediate predecessor. We don't want to increase register pressure and
   // end up causing other computation to be spilled.
   if (TII->isAsCheapAsAMove(*MI)) {
     MachineBasicBlock *BB = MI->getParent();
     if (CSBB != BB && !CSBB->isSuccessor(BB))
       return false;
   }
 
   // Heuristics #2: If the expression doesn't not use a vr and the only use
   // of the redundant computation are copies, do not cse.
   bool HasVRegUse = false;
   for (const MachineOperand &MO : MI->operands()) {
     if (MO.isReg() && MO.isUse() && Register::isVirtualRegister(MO.getReg())) {
       HasVRegUse = true;
bool MachineCSE::isProfitableToHoistInto(MachineBasicBlock *CandidateBB,
   return MBFI->getBlockFreq(CandidateBB) <=
          MBFI->getBlockFreq(MBB) + MBFI->getBlockFreq(MBB1);
 }
 
 bool MachineCSE::runOnMachineFunction(MachineFunction &MF) {
   if (skipFunction(MF.getFunction()))
     return false;
 
   TII = MF.getSubtarget().getInstrInfo();
   TRI = MF.getSubtarget().getRegisterInfo();
   MRI = &MF.getRegInfo();
   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
   DT = &getAnalysis<MachineDominatorTree>();
   MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
   LookAheadLimit = TII->getMachineCSELookAheadLimit();
   bool ChangedPRE, ChangedCSE;
   ChangedPRE = PerformSimplePRE(DT);
   ChangedCSE = PerformCSE(DT->getRootNode());
   return ChangedPRE || ChangedCSE;
 }

llvm/test/CodeGen/RISCV/enable-agressive-machine-cse.mir

+# RUN: llc -mtriple=riscv64 -x mir -run-pass=machine-cse --enable-aggressive-machine-cse -simplify-mir -verify-machineinstrs < %s \
+# RUN: | FileCheck %s
+
+--- |
+  define i1 @foo(i64 %a, i64 %b) {
+  entry:
+    %cmp = icmp slt i64 %a, 2
+    br i1 %cmp, label %return, label %if.end
+
+  if.end:
+    switch i64 %b, label %return [
+      i64 3, label %bb3
+      i64 2, label %bb2
+    ]
+
+  bb2:
+    br label %return
+
+  bb3:
+    br label %return
+
+  return:
+    %ret = phi i1 [ false, %bb2 ], [ false, %bb3 ], [ true, %entry ], [ true, %if.end ]
+    ret i1 %ret
+  }
+
+...
+---
+name:            foo
+tracksRegLiveness: true
+registers:
+  - { id: 0, class: gpr }
+  - { id: 1, class: gpr }
+  - { id: 2, class: gpr }
+  - { id: 3, class: gpr }
+  - { id: 4, class: gpr }
+  - { id: 5, class: gpr }
+  - { id: 6, class: gpr }
+  - { id: 7, class: gpr }
+  - { id: 8, class: gpr }
+  - { id: 9, class: gpr }
+  - { id: 10, class: gpr }
+  - { id: 11, class: gpr }
+liveins:
+  - { reg: '$x10', virtual-reg: '%1' }
+  - { reg: '$x11', virtual-reg: '%2' }
+body:             |
+  bb.0.entry:
+    liveins: $x10, $x11
+
+    %2:gpr = COPY $x11
+    %1:gpr = COPY $x10
+    %3:gpr = ADDI $x0, 1
+    %4:gpr = ADDI $x0, 2
+    BLT %1, killed %4, %bb.5
+    PseudoBR %bb.1
+
+  bb.1.if.end:
+    ; CHECK-NOT: %5:gpr = ADDI $x0, 1
+    ; CHECK: %6:gpr = ADDI $x0, 3
+    ; CHECK: BEQ %2, killed %6, %bb.4
+
+    %5:gpr = ADDI $x0, 1
+    %6:gpr = ADDI $x0, 3
+    BEQ %2, killed %6, %bb.4
+    PseudoBR %bb.2
+
+  bb.2.if.end:
+    ; CHECK-NOT: %7:gpr = ADDI $x0, 2
+    ; CHECK: BNE %2, %4, %bb.5
+
+    %7:gpr = ADDI $x0, 2
+    BNE %2, killed %7, %bb.5
+    PseudoBR %bb.3
+
+  bb.3.bb2:
+    %9:gpr = COPY $x0
+    %8:gpr = COPY %9
+    PseudoBR %bb.5
+
+  bb.4.bb3:
+    %11:gpr = COPY $x0
+    %10:gpr = COPY %11
+
+  bb.5.return:
+    ; CHECK: %0:gpr = PHI %3, %bb.0, %3, %bb.2, %8, %bb.3, %10, %bb.4
+
+    %0:gpr = PHI %3, %bb.0, %5, %bb.2, %8, %bb.3, %10, %bb.4
+    $x10 = COPY %0
+    PseudoRET implicit $x10
+
+...