Unmerge GEPs to reduce register pressure on IndirectBr edges.

[hjyamauchi]

Summary

GEP merging can sometimes increase the number of live values and register
pressure across control edges and cause performance problems particularly if the
increased register pressure results in spills.

This change implements GEP unmerging around an IndirectBr in certain cases to
mitigate the issue. This is in the CodeGenPrepare pass (after all the GEP
merging has happened.)

With this patch, the Python interpreter loop runs faster by ~5%.

[hjyamauchi]

Hi Hal, would you take a look at this change?

[hfinkel]

With this patch, the Python interpreter loop runs faster by ~5%.

On what platform?

Did you try always doing this (instead of just doing it over indirect branches)? You're possibly increasing the critical path by doing the computation this way, and if you have a processor with a good branch predictor maybe this shows up? But if you told me that it generally always helps, I'd not be too surprised either.

You should be careful not to create constants that aren't cheap to represent if you start with ones that are. Specifically, UGEPIIdx->getValue() - GEPIIdx->getValue() might be large (if one of those values is negative). TTI has getIntImmCost, and if both UIdx and Idx are cheap, but (Uidx - Idx) is expensive, we probably don't want to do this.

[hjyamauchi]

Sorry for a delay.

In D36772#848262, @hfinkel wrote:

With this patch, the Python interpreter loop runs faster by ~5%.

On what platform?

x86-64 Haswell.

Did you try always doing this (instead of just doing it over indirect branches)? You're possibly increasing the critical path by doing the computation this way, and if you have a processor with a good branch predictor maybe this shows up? But if you told me that it generally always helps, I'd not be too surprised either.

Good points.

No, I didn't try always doing this. My thoughts follow:

As you point out, I think there may be a tradeoff between potential spills and a potentially longer critical path, and it's not 100% clear which way is better *in general* because that would depend on how the CPU works and it's not easy to tell whether this would actually save spills at this stage, though for the indirectbr in the python interpreter, it's a clear win due to fewer spills (on x86-64).

The benefits of restricting this to relatively rare indirectbr are that (a) it might limit the impact of a potentially longer critical path, if any, and (b) the impact on the compile time should be minimal because it's the first check we do there and the common case doesn't need to go through the subsequent more elaborate checks.

Maybe should query the target and do this only if the number of registers is low (or just x86(-64))?

I wish I could formulate this in a better way. I haven't found a better way so far. If you see a better way, please let me know.

You should be careful not to create constants that aren't cheap to represent if you start with ones that are. Specifically, UGEPIIdx->getValue() - GEPIIdx->getValue() might be large (if one of those values is negative). TTI has getIntImmCost, and if both UIdx and Idx are cheap, but (Uidx - Idx) is expensive, we probably don't want to do this.

Agreed. Will work on this.

[hjyamauchi]

Added getIntImmCost checks. Please take another look.

[eastig]

As this patch can affect ARM targets I am doing some benchmarking.
I've got the LNT benchmarks results for AArch64 (Cortex-A57). There is no difference in performance. I'll have got more results soon.
It's interesting to see what benchmarks has been used to measure the improvements.

[hjyamauchi]

In D36772#852865, @eastig wrote:

As this patch can affect ARM targets I am doing some benchmarking.
I've got the LNT benchmarks results for AArch64 (Cortex-A57). There is no difference in performance. I'll have got more results soon.
It's interesting to see what benchmarks has been used to measure the improvements.

Good to know.

The improvements I saw were measured with python programs (like the following) running on the python 2.7 runtime compiled with LLVM at r309573 on x86-64 Haswell.

for _ in xrange(1, 100000000):
  continue

This patch reduces register spills in the computed goto-based interpreter loop.

[hjyamauchi]

Noted the tradeoff between register pressures and critical path in the comment.

Also rebased.

[hfinkel]

This is looking good. A couple additional things...

lib/CodeGen/CodeGenPrepare.cpp

6224

I don't think this check is necessary. GEPIOp is constrained to be defined in SrcBlock, and it's SrcBlock that has the IndirectBr terminator, so *any* use of GEPIOp outside of SrcBlock keeps it live over the indirect edge. I don't see why we wouldn't unmerge regardless of the parent block here.

6264

You'll also need to make sure that this GEP is not marked as inbounds if GEPI was not.

if (!GEPI->isInBounds()) {
  UGEPI->setIsInBounds(false);
}

because otherwise the result of GEP could be not-in-bounds resulting in UB if that's used as the input to an inbounds UGEPI.

[hjyamauchi]

One comment addressed and another needs clarification.

[hjyamauchi]

lib/CodeGen/CodeGenPrepare.cpp

6264

I'm not very familiar with how inbounds works.

Is an inbounds GEP UB if it takes a non-inbounds GEP as its operand (regardless of whether the index/offset is actually in bounds or not)?

For example,

Before:

%GEPIOp = ...
%GEPI = gep %GEPIOp 2
%UGEPI = gep inbounds %GEPIOp 1

After:

%GEPIOp = ...
%GEPI = gep %GEPIOp 2
%UGEPI = gep inbounds %GEPI -1

Suppose "gep %GEPIOp 2" is not in bounds and "gep inbounds %GEPIOp 1" is in bounds. Both aren't UB.

"gep inbounds %GEPI -1" is UB just because it takes (non-inbounds) "gep %GEPIOp 2" as an operand, even though the offset/index of "gep inbounds %GEPI -1" is actually in bounds?

[hfinkel]

lib/CodeGen/CodeGenPrepare.cpp

6264

Yes, the base pointer needs to be inbounds too. The LangRef says, "If the inbounds keyword is present, the result value of the getelementptr is a poison value if the base pointer is not an in bounds address of an allocated object, or if any of the addresses that would be formed by successive addition of the offsets implied by the indices to the base address with infinitely precise signed arithmetic are not an in bounds address of that allocated object." That's exactly why you need to account for the inbounds here.

[hjyamauchi]

Addressed a comment.

[hfinkel]

LGTM

[hjyamauchi]

Rebased.

[hjyamauchi]

Thanks, Hal.

lib/CodeGen/CodeGenPrepare.cpp

static bool splitMergedValStore(StoreInst &SI, const DataLayout &DL,
   CreateSplitStore(LValue, false);
   CreateSplitStore(HValue, true);
 
   // Delete the old store.
   SI.eraseFromParent();
   return true;
 }
 
+// Return true if the GEP has two operands, the first operand is of a sequential
+// type, and the second operand is a constant.
+static bool GEPSequentialConstIndexed(GetElementPtrInst *GEP) {
+  gep_type_iterator I = gep_type_begin(*GEP);
+  return GEP->getNumOperands() == 2 &&
+      I.isSequential() &&
+      isa<ConstantInt>(GEP->getOperand(1));
+}
+
+// Try unmerging GEPs to reduce liveness interference (register pressure) across
+// IndirectBr edges. Since IndirectBr edges tend to touch on many blocks,
+// reducing liveness interference across those edges benefits global register
+// allocation. Currently handles only certain cases.
+//
+// For example, unmerge %GEPI and %UGEPI as below.
+//
+// ---------- BEFORE ----------
+// SrcBlock:
+//   ...
+//   %GEPIOp = ...
+//   ...
+//   %GEPI = gep %GEPIOp, Idx
+//   ...
+//   indirectbr ... [ label %DstB0, label %DstB1, ... label %DstBi ... ]
+//   (* %GEPI is alive on the indirectbr edges due to other uses ahead)
+//   (* %GEPIOp is alive on the indirectbr edges only because of it's used by
+//   %UGEPI)
+//
+// DstB0: ... (there may be a gep similar to %UGEPI to be unmerged)
+// DstB1: ... (there may be a gep similar to %UGEPI to be unmerged)
+// ...
+//
+// DstBi:
+//   ...
+//   %UGEPI = gep %GEPIOp, UIdx
+// ...
+// ---------------------------
+//
+// ---------- AFTER ----------
+// SrcBlock:
+//   ... (same as above)
+//    (* %GEPI is still alive on the indirectbr edges)
+//    (* %GEPIOp is no longer alive on the indirectbr edges as a result of the
+//    unmerging)
+// ...
+//
+// DstBi:
+//   ...
+//   %UGEPI = gep %GEPI, (UIdx-Idx)
+//   ...
+// ---------------------------
+//
+// The register pressure on the IndirectBr edges is reduced because %GEPIOp is
+// no longer alive on them.
+//
+// We try to unmerge GEPs here in CodGenPrepare, as opposed to limiting merging
+// of GEPs in the first place in InstCombiner::visitGetElementPtrInst() so as
+// not to disable further simplications and optimizations as a result of GEP
+// merging.
+//
+// Note this unmerging may increase the length of the data flow critical path
+// (the path from %GEPIOp to %UGEPI would go through %GEPI), which is a tradeoff
+// between the register pressure and the length of data-flow critical
+// path. Restricting this to the uncommon IndirectBr case would minimize the
+// impact of potentially longer critical path, if any, and the impact on compile
+// time.
+static bool tryUnmergingGEPsAcrossIndirectBr(GetElementPtrInst *GEPI,
+                                             const TargetTransformInfo *TTI) {
+  BasicBlock *SrcBlock = GEPI->getParent();
+  // Check that SrcBlock ends with an IndirectBr. If not, give up. The common
+  // (non-IndirectBr) cases exit early here.
+  if (!isa<IndirectBrInst>(SrcBlock->getTerminator()))
+    return false;
+  // Check that GEPI is a simple gep with a single constant index.
+  if (!GEPSequentialConstIndexed(GEPI))
+    return false;
+  ConstantInt *GEPIIdx = cast<ConstantInt>(GEPI->getOperand(1));
+  // Check that GEPI is a cheap one.
+  if (TTI->getIntImmCost(GEPIIdx->getValue(), GEPIIdx->getType())
+      > TargetTransformInfo::TCC_Basic)
+    return false;
+  Value *GEPIOp = GEPI->getOperand(0);
+  // Check that GEPIOp is an instruction that's also defined in SrcBlock.
+  if (!isa<Instruction>(GEPIOp))
+    return false;
+  auto *GEPIOpI = cast<Instruction>(GEPIOp);
+  if (GEPIOpI->getParent() != SrcBlock)
+    return false;
+  // Check that GEP is used outside the block, meaning it's alive on the
+  // IndirectBr edge(s).
+  if (find_if(GEPI->users(), [&](User *Usr) {
+        if (auto *I = dyn_cast<Instruction>(Usr)) {
+          if (I->getParent() != SrcBlock) {
+            return true;
+          }
+        }
+        return false;
+      }) == GEPI->users().end())
+    return false;
+  // The second elements of the GEP chains to be unmerged.
+  std::vector<GetElementPtrInst *> UGEPIs;
+  // Check each user of GEPIOp to check if unmerging would make GEPIOp not alive
+  // on IndirectBr edges.
+  for (User *Usr : GEPIOp->users()) {
+    if (Usr == GEPI) continue;
+    // Check if Usr is an Instruction. If not, give up.
+    if (!isa<Instruction>(Usr))
+      return false;
+    auto *UI = cast<Instruction>(Usr);
+    // Check if Usr in the same block as GEPIOp, which is fine, skip.
+    if (UI->getParent() == SrcBlock)
+      continue;
+    // Check if Usr is in a block at the end of one of the IndirectBr edges and
+    // that SrcBlock is the only precedessor of it. If not, give up.
+    if (UI->getParent()->getSinglePredecessor() != SrcBlock)
+      return false;
+    // Check if Usr is a GEP. If not, give up.
+    if (!isa<GetElementPtrInst>(Usr))
+      return false;
+    auto *UGEPI = cast<GetElementPtrInst>(Usr);
+    // Check if UGEPI is a simple gep with a single constant index and GEPIOp is
+    // the pointer operand to it. If so, record it in the vector. If not, give
+    // up.
+    if (!GEPSequentialConstIndexed(UGEPI))
+      return false;
+    if (UGEPI->getOperand(0) != GEPIOp)
+      return false;
+    if (GEPIIdx->getType() !=
+        cast<ConstantInt>(UGEPI->getOperand(1))->getType())
+      return false;
+    ConstantInt *UGEPIIdx = cast<ConstantInt>(UGEPI->getOperand(1));
+    if (TTI->getIntImmCost(UGEPIIdx->getValue(), UGEPIIdx->getType())
+        > TargetTransformInfo::TCC_Basic)
+      return false;
+    UGEPIs.push_back(UGEPI);
+  }
+  if (UGEPIs.size() == 0)
+    return false;
+  // Check the materializing cost of (Uidx-Idx).
+  for (GetElementPtrInst *UGEPI : UGEPIs) {
+    ConstantInt *UGEPIIdx = cast<ConstantInt>(UGEPI->getOperand(1));
+    APInt NewIdx = UGEPIIdx->getValue() - GEPIIdx->getValue();
+    unsigned ImmCost = TTI->getIntImmCost(NewIdx, GEPIIdx->getType());
+    if (ImmCost > TargetTransformInfo::TCC_Basic)
+      return false;
+  }
+  // Now unmerge between GEPI and UGEPIs.
+  for (GetElementPtrInst *UGEPI : UGEPIs) {
+    UGEPI->setOperand(0, GEPI);
+    ConstantInt *UGEPIIdx = cast<ConstantInt>(UGEPI->getOperand(1));
+    Constant *NewUGEPIIdx =
+        ConstantInt::get(GEPIIdx->getType(),
+                         UGEPIIdx->getValue() - GEPIIdx->getValue());
+    UGEPI->setOperand(1, NewUGEPIIdx);
+  }
+  // After unmerging, verify that GEPIOp is actually only used in SrcBlock (not
+  // alive on IndirectBr edges).
+  assert(find_if(GEPIOp->users(), [&](User *Usr) {
+        return cast<Instruction>(Usr)->getParent() != SrcBlock;
+      }) == GEPIOp->users().end() && "GEPIOp is used outside SrcBlock");
+  return true;
+}
+
 bool CodeGenPrepare::optimizeInst(Instruction *I, bool &ModifiedDT) {
   // Bail out if we inserted the instruction to prevent optimizations from
   // stepping on each other's toes.
   if (InsertedInsts.count(I))
     return false;
 
   if (PHINode *P = dyn_cast<PHINode>(I)) {
     // It is possible for very late stage optimizations (such as SimplifyCFG)
if (GEPI->hasAllZeroIndices()) {
       Instruction *NC = new BitCastInst(GEPI->getOperand(0), GEPI->getType(),
                                         GEPI->getName(), GEPI);
       GEPI->replaceAllUsesWith(NC);
       GEPI->eraseFromParent();
       ++NumGEPsElim;
       optimizeInst(NC, ModifiedDT);
       return true;
     }
+    if (tryUnmergingGEPsAcrossIndirectBr(GEPI, TTI)) {
+      return true;
+    }
     return false;
   }
 
   if (CallInst *CI = dyn_cast<CallInst>(I))
     return optimizeCallInst(CI, ModifiedDT);
 
   if (SelectInst *SI = dyn_cast<SelectInst>(I))
     return optimizeSelectInst(SI);

test/Transforms/CodeGenPrepare/gep-unmerging.ll

+; RUN: opt -codegenprepare -S < %s | FileCheck %s
+
+@exit_addr = constant i8* blockaddress(@gep_unmerging, %exit)
+@op1_addr = constant i8* blockaddress(@gep_unmerging, %op1)
+@op2_addr = constant i8* blockaddress(@gep_unmerging, %op2)
+@op3_addr = constant i8* blockaddress(@gep_unmerging, %op3)
+@dummy = global i8 0
+
+define void @gep_unmerging(i1 %pred, i8* %p0) {
+entry:
+  %table = alloca [256 x i8*]
+  %table_0 = getelementptr [256 x i8*], [256 x i8*]* %table, i64 0, i64 0
+  %table_1 = getelementptr [256 x i8*], [256 x i8*]* %table, i64 0, i64 1
+  %table_2 = getelementptr [256 x i8*], [256 x i8*]* %table, i64 0, i64 2
+  %table_3 = getelementptr [256 x i8*], [256 x i8*]* %table, i64 0, i64 3
+  %exit_a = load i8*, i8** @exit_addr
+  %op1_a = load i8*, i8** @op1_addr
+  %op2_a = load i8*, i8** @op2_addr
+  %op3_a = load i8*, i8** @op3_addr
+  store i8* %exit_a, i8** %table_0
+  store i8* %op1_a, i8** %table_1
+  store i8* %op2_a, i8** %table_2
+  store i8* %op3_a, i8** %table_3
+  br label %indirectbr
+
+op1:
+; CHECK-LABEL: op1:
+; CHECK-NEXT: %p1_inc2 = getelementptr i8, i8* %p_postinc, i64 2
+; CHECK-NEXT: %p1_inc1 = getelementptr i8, i8* %p_postinc, i64 1
+  %p1_inc2 = getelementptr i8, i8* %p_preinc, i64 3
+  %p1_inc1 = getelementptr i8, i8* %p_preinc, i64 2
+  %a10 = load i8, i8* %p_postinc
+  %a11 = load i8, i8* %p1_inc1
+  %a12 = add i8 %a10, %a11
+  store i8 %a12, i8* @dummy
+  br i1 %pred, label %indirectbr, label %exit
+
+op2:
+; CHECK-LABEL: op2:
+; CHECK-NEXT: %p2_inc = getelementptr i8, i8* %p_postinc, i64 1
+  %p2_inc = getelementptr i8, i8* %p_preinc, i64 2
+  %a2 = load i8, i8* %p_postinc
+  store i8 %a2, i8* @dummy
+  br i1 %pred, label %indirectbr, label %exit
+
+op3:
+  br i1 %pred, label %indirectbr, label %exit
+
+indirectbr:
+  %p_preinc = phi i8* [%p0, %entry], [%p1_inc2, %op1], [%p2_inc, %op2], [%p_postinc, %op3]
+  %p_postinc = getelementptr i8, i8* %p_preinc, i64 1
+  %next_op = load i8, i8* %p_preinc
+  %p_zext = zext i8 %next_op to i64
+  %slot = getelementptr [256 x i8*], [256 x i8*]* %table, i64 0, i64 %p_zext 
+  %target = load i8*, i8** %slot
+  indirectbr i8* %target, [label %exit, label %op1, label %op2]
+
+exit:
+  ret void
+}