[GlobalMerge] Take into account minsize attribute of global users' parents.

[ab]

Summary

Now that we can look at users, we can trivially do this: when we would have otherwise disabled GlobalMerge (currently -O<3), we can just run it for minsize functions, as it's usually a codesize win (see attached numbers).

I'm a bit uneasy with this minsize/CodeGenOpt::Level hybrid, hence this thread; alternatives welcome. Also, minsize only for now, as we're not quite at re-enabling GM everywhere yet (see PR23579). I'm hoping that if and when we do, we can remove this code path, or turn it into cost model heuristics.

And here are some quick numbers (text section size), for -Oz {no-lto,lto}{AArch64,ARM}:

gm-Oz-aarch64.txt41 KBDownload

gm-Oz-lto-aarch64.txt41 KBDownload

gm-Oz-armv7.txt37 KBDownload

gm-Oz-lto-armv7.txt37 KBDownload

Most interesting is LTO (esp. ARM), where there's quite a few 5-15% size reductions. There aren't many regressions, a few ~1-3%.

[qcolombet]

lib/CodeGen/GlobalMerge.cpp

201

Shouldn’t the size option affect this setting?

lib/Target/ARM/ARMTargetMachine.cpp

350–352

Just for the record, a quick comment.

I am not very fond of the “if not aggressive” then do size only, but based of our offline discussion I agree this is pretty much what we do in the pass manager when creating other passes (like loop unswitch).

Anyhow, I do not have a better alternative.

test/CodeGen/AArch64/global-merge-ignore-single-use-minsize.ll

40

In the previous test case, you have a clear separation between the globals used in minsize functions and the ones used in non-minsize function.

Could you make another test case that mixes both?
I.e.,
G1
G2
G3

minsizefunc {
G1
G3
}

non-minsizefunc {
G1
G2
}

[ab]

lib/CodeGen/GlobalMerge.cpp

201

I'm not sure how, because without users, there's no minsize attribute to look at.

It shouldn't matter anyway, as this is mostly an option for testing (to get the old GlobalMerge behavior back).

lib/Target/ARM/ARMTargetMachine.cpp

350–352

I don't like it either, but I also couldn't come up with a better way ;)

test/CodeGen/AArch64/global-merge-ignore-single-use-minsize.ll

40

Done.

[ab]

• Add mixed minsize/non-minsize user functions

[qcolombet]

Hi Ahmed,

LGTM.

Thanks,
-Quentin

[ab]

Thanks Quentin, r239087.

For the record, I also changed the OnlyOptimizeForSize -O<3 check to be overridden by the debugging flags (-aarch64/-arm-global-merge), to keep it easy to get the "just enable GM" behavior.

-Ahmed

include/llvm/Transforms/Scalar.h

 
 //===----------------------------------------------------------------------===//
 //
 // LoopStrengthReduce - This pass is strength reduces GEP instructions that use
 // a loop's canonical induction variable as one of their indices.
 //
 Pass *createLoopStrengthReducePass();
 
-Pass *createGlobalMergePass(const TargetMachine *TM, unsigned MaximalOffset);
+//===----------------------------------------------------------------------===//
+//
+// GlobalMerge - This pass merges internal (by default) globals into structs
+// to enable reuse of a base pointer by indexed addressing modes.
+// It can also be configured to focus on size optimizations only.
+//
+Pass *createGlobalMergePass(const TargetMachine *TM, unsigned MaximalOffset,
+                            bool OnlyOptimizeForSize = false);
 
 //===----------------------------------------------------------------------===//
 //
 // LoopUnswitch - This pass is a simple loop unswitching pass.
 //
 Pass *createLoopUnswitchPass(bool OptimizeForSize = false);
 
 //===----------------------------------------------------------------------===//

lib/CodeGen/GlobalMerge.cpp

class GlobalMerge : public FunctionPass {
     const TargetMachine *TM;
     const DataLayout *DL;
     // FIXME: Infer the maximum possible offset depending on the actual users
     // (these max offsets are different for the users inside Thumb or ARM
     // functions), see the code that passes in the offset in the ARM backend
     // for more information.
     unsigned MaxOffset;
 
+    /// Whether we should try to optimize for size only.
+    /// Currently, this applies a dead simple heuristic: only consider globals
+    /// used in minsize functions for merging.
+    /// FIXME: This could learn about optsize, and be used in the cost model.
+    bool OnlyOptimizeForSize;
+
     bool doMerge(SmallVectorImpl<GlobalVariable*> &Globals,
                  Module &M, bool isConst, unsigned AddrSpace) const;
     /// \brief Merge everything in \p Globals for which the corresponding bit
     /// in \p GlobalSet is set.
     bool doMerge(SmallVectorImpl<GlobalVariable *> &Globals,
                  const BitVector &GlobalSet, Module &M, bool isConst,
                  unsigned AddrSpace) const;
 
class GlobalMerge : public FunctionPass {
     void collectUsedGlobalVariables(Module &M);
 
     /// Keep track of the GlobalVariable that must not be merged away
     SmallPtrSet<const GlobalVariable *, 16> MustKeepGlobalVariables;
 
   public:
     static char ID;             // Pass identification, replacement for typeid.
     explicit GlobalMerge(const TargetMachine *TM = nullptr,
-                         unsigned MaximalOffset = 0)
+                         unsigned MaximalOffset = 0,
+                         bool OnlyOptimizeForSize = false)
         : FunctionPass(ID), TM(TM), DL(TM->getDataLayout()),
-          MaxOffset(MaximalOffset) {
+          MaxOffset(MaximalOffset), OnlyOptimizeForSize(OnlyOptimizeForSize) {
       initializeGlobalMergePass(*PassRegistry::getPassRegistry());
     }
 
     bool doInitialization(Module &M) override;
     bool runOnFunction(Function &F) override;
     bool doFinalization(Module &M) override;
 
     const char *getPassName() const override {
std::stable_sort(Globals.begin(), Globals.end(),
                    [this](const GlobalVariable *GV1, const GlobalVariable *GV2) {
     Type *Ty1 = cast<PointerType>(GV1->getType())->getElementType();
     Type *Ty2 = cast<PointerType>(GV2->getType())->getElementType();
 
     return (DL->getTypeAllocSize(Ty1) < DL->getTypeAllocSize(Ty2));
   });
 
   // If we want to just blindly group all globals together, do so.
   if (!GlobalMergeGroupByUse) {
     BitVector AllGlobals(Globals.size());
     AllGlobals.set();
     return doMerge(Globals, AllGlobals, M, isConst, AddrSpace);
   }
 
   // If we want to be smarter, look at all uses of each global, to try to
   // discover all sets of globals used together, and how many times each of
   // these sets occured.
for (auto &U : GV->uses()) {
       // ...to iterate on all the instruction users of the global.
       // Note that we iterate on Uses and not on Users to be able to getNext().
       for (; UI != UE; UI = UI->getNext()) {
         Instruction *I = dyn_cast<Instruction>(UI->getUser());
         if (!I)
           continue;
 
         Function *ParentFn = I->getParent()->getParent();
+
+        // If we're only optimizing for size, ignore non-minsize functions.
+        if (OnlyOptimizeForSize &&
+            !ParentFn->hasFnAttribute(Attribute::MinSize))
+          continue;
+
         size_t UGSIdx = GlobalUsesByFunction[ParentFn];
 
         // If this is the first global the basic block uses, map it to the set
         // consisting of this global only.
         if (!UGSIdx) {
           // If that set doesn't exist yet, create it.
           if (!CurGVOnlySetIdx) {
             CurGVOnlySetIdx = UsedGlobalSets.size();
bool GlobalMerge::runOnFunction(Function &F) {
   return false;
 }
 
 bool GlobalMerge::doFinalization(Module &M) {
   MustKeepGlobalVariables.clear();
   return false;
 }
 
-Pass *llvm::createGlobalMergePass(const TargetMachine *TM, unsigned Offset) {
-  return new GlobalMerge(TM, Offset);
+Pass *llvm::createGlobalMergePass(const TargetMachine *TM, unsigned Offset,
+                                  bool OnlyOptimizeForSize) {
+  return new GlobalMerge(TM, Offset, OnlyOptimizeForSize);
 }

lib/Target/AArch64/AArch64TargetMachine.cpp

 bool AArch64PassConfig::addPreISel() {
   // Run promote constant before global merge, so that the promoted constants
   // get a chance to be merged
   if (TM->getOptLevel() != CodeGenOpt::None && EnablePromoteConstant)
     addPass(createAArch64PromoteConstantPass());
   // FIXME: On AArch64, this depends on the type.
   // Basically, the addressable offsets are up to 4095 * Ty.getSizeInBytes().
   // and the offset has to be a multiple of the related size in bytes.
-  if ((TM->getOptLevel() == CodeGenOpt::Aggressive &&
+  if ((TM->getOptLevel() != CodeGenOpt::None &&
        EnableGlobalMerge == cl::BOU_UNSET) ||
-      EnableGlobalMerge == cl::BOU_TRUE)
-    addPass(createGlobalMergePass(TM, 4095));
+      EnableGlobalMerge == cl::BOU_TRUE) {
+    bool OnlyOptimizeForSize = TM->getOptLevel() < CodeGenOpt::Aggressive;
+    addPass(createGlobalMergePass(TM, 4095, OnlyOptimizeForSize));
+  }
+
   if (TM->getOptLevel() != CodeGenOpt::None)
     addPass(createAArch64AddressTypePromotionPass());
 
   return false;
 }
 
 bool AArch64PassConfig::addInstSelector() {
   addPass(createAArch64ISelDag(getAArch64TargetMachine(), getOptLevel()));

lib/Target/ARM/ARMTargetMachine.cpp

void ARMPassConfig::addIRPasses() {
   if (Subtarget->hasAnyDataBarrier() && !Subtarget->isThumb1Only())
     if (TM->getOptLevel() != CodeGenOpt::None && EnableAtomicTidy)
       addPass(createCFGSimplificationPass());
 
   TargetPassConfig::addIRPasses();
 }
 
 bool ARMPassConfig::addPreISel() {
-  if ((TM->getOptLevel() == CodeGenOpt::Aggressive &&
+  if ((TM->getOptLevel() != CodeGenOpt::None &&
        EnableGlobalMerge == cl::BOU_UNSET) ||
-      EnableGlobalMerge == cl::BOU_TRUE)
+      EnableGlobalMerge == cl::BOU_TRUE) {
     // FIXME: This is using the thumb1 only constant value for
     // maximal global offset for merging globals. We may want
     // to look into using the old value for non-thumb1 code of
     // 4095 based on the TargetMachine, but this starts to become
     // tricky when doing code gen per function.
-    addPass(createGlobalMergePass(TM, 127));
+    bool OnlyOptimizeForSize = TM->getOptLevel() < CodeGenOpt::Aggressive;
+    addPass(createGlobalMergePass(TM, 127, OnlyOptimizeForSize));
+  }
 
   return false;
 }
 
 bool ARMPassConfig::addInstSelector() {
   addPass(createARMISelDag(getARMTargetMachine(), getOptLevel()));
 
   if (Triple(TM->getTargetTriple()).isOSBinFormatELF() &&

test/CodeGen/AArch64/global-merge-ignore-single-use-minsize.ll

+; RUN: llc -mtriple=aarch64-apple-ios -asm-verbose=false -aarch64-collect-loh=false \
+; RUN:   -O1 -global-merge-group-by-use -global-merge-ignore-single-use \
+; RUN:   %s -o - | FileCheck %s
+
+; Check that, at -O1, we only merge globals used in minsize functions.
+; We assume that globals of the same size aren't reordered inside a set.
+; We use -global-merge-ignore-single-use, and thus only expect one merged set.
+
+@m1 = internal global i32 0, align 4
+@n1 = internal global i32 0, align 4
+
+; CHECK-LABEL: f1:
+define void @f1(i32 %a1, i32 %a2) minsize nounwind {
+; CHECK-NEXT: adrp x8, [[SET:__MergedGlobals]]@PAGE
+; CHECK-NEXT: add x8, x8, [[SET]]@PAGEOFF
+; CHECK-NEXT: stp w0, w1, [x8]
+; CHECK-NEXT: ret
+  store i32 %a1, i32* @m1, align 4
+  store i32 %a2, i32* @n1, align 4
+  ret void
+}
+
+@m2 = internal global i32 0, align 4
+@n2 = internal global i32 0, align 4
+
+; CHECK-LABEL: f2:
+define void @f2(i32 %a1, i32 %a2) nounwind {
+; CHECK-NEXT: adrp x8, _m2@PAGE
+; CHECK-NEXT: adrp x9, _n2@PAGE
+; CHECK-NEXT: str w0, [x8, _m2@PAGEOFF]
+; CHECK-NEXT: str w1, [x9, _n2@PAGEOFF]
+; CHECK-NEXT: ret
+  store i32 %a1, i32* @m2, align 4
+  store i32 %a2, i32* @n2, align 4
+  ret void
+}
+
+; If we have use sets partially overlapping between a minsize and a non-minsize
+; function, explicitly check that we only consider the globals used in the
+; minsize function for merging.
+
+@m3 = internal global i32 0, align 4
+@n3 = internal global i32 0, align 4
+
+; CHECK-LABEL: f3:
+define void @f3(i32 %a1, i32 %a2) minsize nounwind {
+; CHECK-NEXT: adrp x8, [[SET]]@PAGE
+; CHECK-NEXT: add x8, x8, [[SET]]@PAGEOFF
+; CHECK-NEXT: stp w0, w1, [x8, #8]
+; CHECK-NEXT: ret
+  store i32 %a1, i32* @m3, align 4
+  store i32 %a2, i32* @n3, align 4
+  ret void
+}
+
+@n4 = internal global i32 0, align 4
+
+; CHECK-LABEL: f4:
+define void @f4(i32 %a1, i32 %a2) nounwind {
+; CHECK-NEXT: adrp x8, [[SET]]@PAGE
+; CHECK-NEXT: add x8, x8, [[SET]]@PAGEOFF
+; CHECK-NEXT: adrp x9, _n4@PAGE
+; CHECK-NEXT: str w0, [x8, #8]
+; CHECK-NEXT: str w1, [x9, _n4@PAGEOFF]
+; CHECK-NEXT: ret
+  store i32 %a1, i32* @m3, align 4
+  store i32 %a2, i32* @n4, align 4
+  ret void
+}
+
+; CHECK-DAG: .zerofill __DATA,__bss,[[SET]],16,3
+; CHECK-DAG: .zerofill __DATA,__bss,_m2,4,2
+; CHECK-DAG: .zerofill __DATA,__bss,_n2,4,2
+; CHECK-DAG: .zerofill __DATA,__bss,_n4,4,2