[GlobalISel][Localizer] Don't localize phi operands which are used more than once in the phi.

[aemerson]

Summary

The current algorithm just tries to localize defs as far as they can go, and in the case of G_PHI operands, it clones the def into the predecessor block for each incoming edge. When multiple edges have the same register value, this can cause unnecessary code bloat, and inhibit later optimizations.

This change checks if a given phi operand is unique in the phi, if not the def of that register is not localized to the predecessor.

llvm/include/llvm/CodeGen/GlobalISel/Localizer.h

private:
   static bool isLocalUse(MachineOperand &MOUse, const MachineInstr &Def,
                          MachineBasicBlock *&InsertMBB);
 
   /// Initialize the field members using \p MF.
   void init(MachineFunction &MF);
 
   typedef SmallSetVector<MachineInstr *, 32> LocalizedSetVecT;
 
+  /// If \p Op is a phi operand and not unique in that phi, that is,
+  /// there are other operands in the phi with the same register,
+  /// return true.
+  bool isNonUniquePhiValue(MachineOperand &Op) const;
+
   /// Do inter-block localization from the entry block.
   bool localizeInterBlock(MachineFunction &MF,
                           LocalizedSetVecT &LocalizedInstrs);
 
   /// Do intra-block localization of already localized instructions.
   bool localizeIntraBlock(LocalizedSetVecT &LocalizedInstrs);
 
 public:

llvm/lib/CodeGen/GlobalISel/Localizer.cpp

 //===- Localizer.cpp ---------------------- Localize some instrs -*- C++ -*-==//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 /// \file
 /// This file implements the Localizer class.
 //===----------------------------------------------------------------------===//
 
 #include "llvm/CodeGen/GlobalISel/Localizer.h"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/TargetLowering.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Support/Debug.h"
 
 #define DEBUG_TYPE "localizer"
 
bool Localizer::isLocalUse(MachineOperand &MOUse, const MachineInstr &Def,
                            MachineBasicBlock *&InsertMBB) {
   MachineInstr &MIUse = *MOUse.getParent();
   InsertMBB = MIUse.getParent();
   if (MIUse.isPHI())
     InsertMBB = MIUse.getOperand(MIUse.getOperandNo(&MOUse) + 1).getMBB();
   return InsertMBB == Def.getParent();
 }
 
+bool Localizer::isNonUniquePhiValue(MachineOperand &Op) const {
+  MachineInstr *MI = Op.getParent();
+  if (!MI->isPHI())
+    return false;
+
+  Register SrcReg = Op.getReg();
+  for (unsigned Idx = 1; Idx < MI->getNumOperands(); Idx += 2) {
+    auto &MO = MI->getOperand(Idx);
+    if (&MO != &Op && MO.isReg() && MO.getReg() == SrcReg)
+      return true;
+  }
+  return false;
+}
+
 bool Localizer::localizeInterBlock(MachineFunction &MF,
                                    LocalizedSetVecT &LocalizedInstrs) {
   bool Changed = false;
   DenseMap<std::pair<MachineBasicBlock *, unsigned>, unsigned> MBBWithLocalDef;
 
   // Since the IRTranslator only emits constants into the entry block, and the
   // rest of the GISel pipeline generally emits constants close to their users,
   // we only localize instructions in the entry block here. This might change if
for (auto MOIt = MRI->use_begin(Reg), MOItEnd = MRI->use_end();
                         << " #Opd: " << MIUse.getOperandNo(&MOUse) << '\n');
       if (isLocalUse(MOUse, MI, InsertMBB)) {
         // Even if we're in the same block, if the block is very large we could
         // still have many long live ranges. Try to do intra-block localization
         // too.
         LocalizedInstrs.insert(&MI);
         continue;
       }
+
+      // If the use is a phi operand that's not unique, don't try to localize.
+      // If we do, we can cause unnecessary instruction bloat by duplicating
+      // into each predecessor block, when the existing one is sufficient and
+      // allows for easier optimization later.
+      if (isNonUniquePhiValue(MOUse))
+        continue;
+
       LLVM_DEBUG(dbgs() << "Fixing non-local use\n");
       Changed = true;
       auto MBBAndReg = std::make_pair(InsertMBB, Reg);
       auto NewVRegIt = MBBWithLocalDef.find(MBBAndReg);
       if (NewVRegIt == MBBWithLocalDef.end()) {
         // Create the localized instruction.
         MachineInstr *LocalizedMI = MF.CloneMachineInstr(&MI);
         LocalizedInstrs.insert(LocalizedMI);

llvm/test/CodeGen/AArch64/GlobalISel/localizer.mir

if.then:
     br label %if.end
 
   if.end:
     ret i32 0
   }
 
   define void @test_inttoptr() { ret void }
   define void @many_local_use_intra_block() { ret void }
-
+  define void @non_local_phi_use_nonunique() { ret void }
 ...
 
 ---
 name:            local_use
 legalized:       true
 regBankSelected: true
 body:             |
   bb.0:
bb.0:
     %1:gpr(s32) = G_CONSTANT i32 2
     %2:gpr(s32) = G_ADD %0, %0
     %3:gpr(s32) = G_ADD %0, %0
     %4:gpr(s32) = G_ADD %0, %0
     %5:gpr(s32) = G_ADD %0, %0
     %6:gpr(s32) = G_ADD %0, %0
     %7:gpr(s32) = G_ADD %1, %1
 ...
+
+---
+name:            non_local_phi_use_nonunique
+legalized:       true
+regBankSelected: true
+tracksRegLiveness: true
+body:             |
+  ; CHECK-LABEL: name: non_local_phi_use_nonunique
+  ; CHECK: bb.0:
+  ; CHECK:   successors: %bb.1(0x40000000), %bb.2(0x40000000)
+  ; CHECK:   [[C:%[0-9]+]]:gpr(s32) = G_CONSTANT i32 1
+  ; CHECK:   [[ADD:%[0-9]+]]:gpr(s32) = G_ADD [[C]], [[C]]
+  ; CHECK:   %cmp:gpr(s32) = G_ICMP intpred(eq), [[ADD]](s32), [[C]]
+  ; CHECK:   %cond:gpr(s1) = G_TRUNC %cmp(s32)
+  ; CHECK:   G_BRCOND %cond(s1), %bb.1
+  ; CHECK:   G_BR %bb.2
+  ; CHECK: bb.1:
+  ; CHECK:   successors: %bb.2(0x80000000)
+  ; CHECK: bb.2:
+  ; CHECK:   [[PHI:%[0-9]+]]:gpr(s32) = G_PHI [[C]](s32), %bb.1
+  ; CHECK:   [[ADD1:%[0-9]+]]:gpr(s32) = G_ADD [[PHI]], [[PHI]]
+
+  ; Don't localize the 1 into bb.1, because there are multiple edges
+  ; using that register.
+
+  bb.0:
+    successors: %bb.1, %bb.2
+
+    %0:gpr(s32) = G_CONSTANT i32 1
+    %1:gpr(s32) = G_ADD %0, %0
+    %cmp:gpr(s32) = G_ICMP intpred(eq), %1(s32), %0
+    %cond:gpr(s1) = G_TRUNC %cmp(s32)
+    G_BRCOND %cond(s1), %bb.1
+    G_BR %bb.2
+
+  bb.1:
+    successors: %bb.2
+
+  bb.2:
+    %3:gpr(s32) = G_PHI %0(s32), %bb.1, %0(s32), %bb.0
+    %2:gpr(s32) = G_ADD %3, %3
+...