Create constant GEP first to allow more LICM.

[• hulx2000]

Summary

This patch changes the order of GEPs generated by Split GEPs pass,
specially when one of the GEPs has constant and the base is loop
invariant, then we will generate the GEP with constant first when
beneficial, to expose more cases for LICM.

For no-loop cases, the original way of generating GEPs seems to
expose more CSE cases, so we don't change the logic for no-loop
cases, and only limit our change to the specific case we are
interested in.

[hfinkel]

lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp

747

Please comment on why you're only doing this for NumOfCommonBaseGEPs[ResultPtr] == 1.

750

deoesn't -> doesn't

761

I'd rather you moved this to the bottom of the loop.

762

contain -> contains

763

So -> so

in original -> in the original

767

And just made this a 'continue'

780

Why does this not have Builder.getInt8Ty() as its first argument like the one below? Could you introduce a small lambda function to avoid repeating the logic twice?

1063

Seems like we:

1. End up scanning loops we don't really care about at all (can't we do this lazily later?)
2. Increment NumOfCommonBaseGEPs based on uses is separate loops; should the count be loop specific?

[• hulx2000]

Hi, Hal:

Thanks for review.

This patch is the earlier version of http://reviews.llvm.org/D11051, do you prefer this version better?

Regards

Lawrence Hu

[hfinkel]

In D11443#212039, @hulx2000 wrote:

Hi, Hal:

Thanks for review.

This patch is the earlier version of http://reviews.llvm.org/D11051, do you prefer this version better?

Ah, yes, likely. I'll look at that one.

Regards

Lawrence Hu

[• hulx2000]

A better version is uploaded to http://reviews.llvm.org/D11051

lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp

 // parts and variant parts, LICM can hoist/sink those invariant parts.
 // CGP (CodeGen Prepare) tries to sink address calculations that match the
 // target's addressing modes. A GEP with multiple indices may not match and will
 // not be sunk. If we lower such GEP into smaller parts, CGP may sink some of
 // them. So we end up with a better addressing mode.
 //
 //===----------------------------------------------------------------------===//
 
+#include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
SeparateConstOffsetFromGEP(const TargetMachine *TM = nullptr,
                              bool LowerGEP = false)
       : FunctionPass(ID), DL(nullptr), DT(nullptr), TM(TM), LowerGEP(LowerGEP) {
     initializeSeparateConstOffsetFromGEPPass(*PassRegistry::getPassRegistry());
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<TargetTransformInfoWrapperPass>();
+    AU.addRequired<LoopInfoWrapperPass>();
     AU.setPreservesCFG();
   }
 
   bool doInitialization(Module &M) override {
     DL = &M.getDataLayout();
     return false;
   }
   bool runOnFunction(Function &F) override;
private:
   /// Verified in @i32_add in split-gep.ll
   bool canonicalizeArrayIndicesToPointerSize(GetElementPtrInst *GEP);
   /// Verify F is free of dead code.
   void verifyNoDeadCode(Function &F);
 
   const DataLayout *DL;
   const DominatorTree *DT;
   const TargetMachine *TM;
+
+  LoopInfo *LI;
+  DenseMap<Value *, int64_t> NumOfCommonBaseGEPs;
   /// Whether to lower a GEP with multiple indices into arithmetic operations or
   /// multiple GEPs with a single index.
   bool LowerGEP;
 };
 }  // anonymous namespace
 
 char SeparateConstOffsetFromGEP::ID = 0;
 INITIALIZE_PASS_BEGIN(

 void SeparateConstOffsetFromGEP::lowerToSingleIndexGEPs(
     GetElementPtrInst *Variadic, int64_t AccumulativeByteOffset) {
   IRBuilder<> Builder(Variadic);
   Type *IntPtrTy = DL->getIntPtrType(Variadic->getType());
 
   Type *I8PtrTy =
       Builder.getInt8PtrTy(Variadic->getType()->getPointerAddressSpace());
   Value *ResultPtr = Variadic->getOperand(0);
+  Loop *L = LI->getLoopFor(Variadic->getParent());
+  bool GenerateConstFirst = false;
+
+  gep_type_iterator GTI = gep_type_begin(*Variadic);
+  if (L && L->isLoopInvariant(ResultPtr) &&
+      NumOfCommonBaseGEPs[ResultPtr] == 1) {
+
+    // We perfer generate GEP with constant offset first if the other GEPs
+    // has loop variant operand and it deoesn't have foldable constant.
+    for (unsigned I = 1, E = Variadic->getNumOperands(); I != E; ++I, ++GTI) {
+      if (isa<SequentialType>(*GTI)) {
+        Value *Idx = Variadic->getOperand(I);
+        // Skip constant
+        if (dyn_cast<ConstantInt>(Idx))
+          continue;
+
+        if (L && L->isLoopInvariant(Idx))
+          continue;
+
+        GenerateConstFirst = true;
+        // If the other offset contain constant too, it could be folded later,
+        // So we keep it in original order.
+        if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Idx))
+          if (dyn_cast<ConstantInt>(BO->getOperand(0)) ||
+              dyn_cast<ConstantInt>(BO->getOperand(1)))
+            GenerateConstFirst = false;
+      }
+    }
+  }
+
   if (ResultPtr->getType() != I8PtrTy)
     ResultPtr = Builder.CreateBitCast(ResultPtr, I8PtrTy);
 
-  gep_type_iterator GTI = gep_type_begin(*Variadic);
+  // Create a GEP with the constant offset index.
+  // Create this first if base is loop invariant, and base is only used
+  // by one GEP, that way it could be moved out of loop by later optimizations
+  if (AccumulativeByteOffset != 0 && GenerateConstFirst) {
+    Value *Offset = ConstantInt::get(IntPtrTy, AccumulativeByteOffset);
+    ResultPtr = Builder.CreateGEP(ResultPtr, Offset, "uglygep");
+  }
+
+  GTI = gep_type_begin(*Variadic);
   // Create an ugly GEP for each sequential index. We don't create GEPs for
   // structure indices, as they are accumulated in the constant offset index.
   for (unsigned I = 1, E = Variadic->getNumOperands(); I != E; ++I, ++GTI) {
     if (isa<SequentialType>(*GTI)) {
       Value *Idx = Variadic->getOperand(I);
       // Skip zero indices.
       if (ConstantInt *CI = dyn_cast<ConstantInt>(Idx))
         if (CI->isZero())
if (isa<SequentialType>(*GTI)) {
       }
       // Create an ugly GEP with a single index for each index.
       ResultPtr =
           Builder.CreateGEP(Builder.getInt8Ty(), ResultPtr, Idx, "uglygep");
     }
   }
 
   // Create a GEP with the constant offset index.
-  if (AccumulativeByteOffset != 0) {
+  // Only need to do that if din't do that earlier.
+  if (AccumulativeByteOffset != 0 && !GenerateConstFirst) {
     Value *Offset = ConstantInt::get(IntPtrTy, AccumulativeByteOffset);
     ResultPtr =
         Builder.CreateGEP(Builder.getInt8Ty(), ResultPtr, Offset, "uglygep");
   }
   if (ResultPtr->getType() != Variadic->getType())
     ResultPtr = Builder.CreateBitCast(ResultPtr, Variadic->getType());
 
   Variadic->replaceAllUsesWith(ResultPtr);

 bool SeparateConstOffsetFromGEP::runOnFunction(Function &F) {
   if (skipOptnoneFunction(F))
     return false;
 
   if (DisableSeparateConstOffsetFromGEP)
     return false;
 
   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
-
+  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   bool Changed = false;
+  DenseMap<Loop *, bool> LoopVisited;
   for (Function::iterator B = F.begin(), BE = F.end(); B != BE; ++B) {
-    for (BasicBlock::iterator I = B->begin(), IE = B->end(); I != IE; ) {
-      if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I++)) {
-        Changed |= splitGEP(GEP);
-      }
-      // No need to split GEP ConstantExprs because all its indices are constant
-      // already.
-    }
-  }
+
+    // Record number of times the base of a GEP used inside loop.
+    NumOfCommonBaseGEPs.clear();
+    Loop *L = LI->getLoopFor(B);
+    if (L && !LoopVisited[L]) {
+      LoopVisited[L] = true;
+      for (auto BB : L->getBlocks())
+        for (BasicBlock::iterator I = BB->begin(), IE = BB->end(); I != IE;)
+          if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I++))
+            NumOfCommonBaseGEPs[GEP->getOperand(0)]++;
+
+    for (BasicBlock::iterator I = B->begin(), IE = B->end(); I != IE;)
+      if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I++))
+        Changed |= splitGEP(GEP);
 
   if (VerifyNoDeadCode)
     verifyNoDeadCode(F);
 
   return Changed;
 }
 
 void SeparateConstOffsetFromGEP::verifyNoDeadCode(Function &F) {

test/CodeGen/AArch64/aarch64-loop-gep-opt.ll

+; RUN: llc -O3 -aarch64-gep-opt=true  -print-after=codegenprepare -mcpu=cortex-a53 < %s >%t 2>&1 && FileCheck <%t %s
+; REQUIRES: asserts
+target triple = "aarch64--linux-android"
+
+%typeD = type { i32, i32, [256 x i32], [257 x i32] }
+
+; Function Attrs: noreturn nounwind uwtable
+define i32 @test1(%typeD* nocapture %s) {
+entry:
+; CHECK-LABEL: entry:
+; CHECK:    %uglygep = getelementptr i8, i8* %0, i64 1032
+; CHECK:    br label %do.body.i
+
+
+  %tPos = getelementptr inbounds %typeD, %typeD* %s, i64 0, i32 0
+  %k0 = getelementptr inbounds %typeD, %typeD* %s, i64 0, i32 1
+  %.pre = load i32, i32* %tPos, align 4
+  br label %do.body.i
+
+do.body.i:
+; CHECK-LABEL: do.body.i:
+; CHECK:          %uglygep2 = getelementptr i8, i8* %uglygep, i64 %3
+; CHECK-NEXT:     %4 = bitcast i8* %uglygep2 to i32*
+; CHECK-NOT:      %uglygep2 = getelementptr i8, i8* %uglygep, i64 1032
+
+
+  %0 = phi i32 [ 256, %entry ], [ %.be, %do.body.i.backedge ]
+  %1 = phi i32 [ 0, %entry ], [ %.be6, %do.body.i.backedge ]
+  %add.i = add nsw i32 %1, %0
+  %shr.i = ashr i32 %add.i, 1
+  %idxprom.i = sext i32 %shr.i to i64
+  %arrayidx.i = getelementptr inbounds %typeD, %typeD* %s, i64 0, i32 3, i64 %idxprom.i
+  %2 = load i32, i32* %arrayidx.i, align 4
+  %cmp.i = icmp sle i32 %2, %.pre
+  %na.1.i = select i1 %cmp.i, i32 %0, i32 %shr.i
+  %nb.1.i = select i1 %cmp.i, i32 %shr.i, i32 %1
+  %sub.i = sub nsw i32 %na.1.i, %nb.1.i
+  %cmp1.i = icmp eq i32 %sub.i, 1
+  br i1 %cmp1.i, label %fooo.exit, label %do.body.i.backedge
+
+do.body.i.backedge:
+  %.be = phi i32 [ %na.1.i, %do.body.i ], [ 256, %fooo.exit ]
+  %.be6 = phi i32 [ %nb.1.i, %do.body.i ], [ 0, %fooo.exit ]
+  br label %do.body.i
+
+fooo.exit:                              ; preds = %do.body.i
+  store i32 %nb.1.i, i32* %k0, align 4
+  br label %do.body.i.backedge
+}
+