[LICM] Don't silently ignore constant expressions in promoteLoopAccessesToScalars()

[mkuper]

Summary

Right now, the loop that iterates over the pointers in each alias set ignores constantexpr uses of these pointers - which is unfortunate, since it misses the case where the pointer is a constant, and a constant expression that uses the pointer is present inside the loop.

I'm not too happy with this patch - it seems like there should be a simpler way to do this. Any suggestions are welcome, especially if I'm missing an obvious one.

Also, it is intentionally conservative, since it'll bail even when the constantexpr is harmless (e.g. a bitcast from i32* to float* that goes into a load). Ideally, it should probably just feed the instructions that use the constantexpr into the same loop as the rest of the pointer's users, but I'm afraid that may introduce other edge cases.

This fixes PR26843.

[reames]

I'm a bit confused by this patch. Specifically, it looks like you're expecting ASIV to be @v, whereas the pointer being used is actually "i32* getelementptr inbounds ([4 x i32], [4 x i32]* @v" which should be handled perfectly fine by the loop promotion code. I feel like you've probably misidentified the issue, but I can't tell from your test case what the actually issue is.

Can you explain a bit of your reasoning by which you arrived at this patch?

As a guess, are you possibly seeing @v and "i32* getelementptr inbounds ([4 x i32], [4 x i32]* @v" in a single must alias alias set? If so, that would be a bug somewhere in the aliasing because those two are not must alias.

[sanjoy]

Could it actually be this: https://llvm.org/bugs/show_bug.cgi?id=26860#c1 ?

[reames]

@sanjoy - That looks possible. I'd need to see a dump of the alias sets to see for sure.

[mkuper]

Thanks for looking at it, Philip and Sanjoy.

For the test case, there's a single value in the alias set:

Alias Set Tracker: 1 alias sets for 1 pointer values.
  AliasSet[0xa0b5d8, 1] must alias, Mod       Pointers: (i32* getelementptr inbounds ([4 x i32], [4 x i32]* @v, i32 0, i32 1), 12)

The constant expr that seems to confuse LICM isn't the GEP, it's the bitcast.
Actually, it's possible the GEP is just noise. I'd expect the same to happen when directly bitcasting from @v. I'll check, and simplify the test if that's the case.

[reames]

Ah, that was really helpful. This is definitely an AST bug.
"bitcast (i32* getelementptr inbounds ([4 x i32], [4 x i32]* @v, i32 0, i32 1) to i8*" and "getelementptr inbounds ([4 x i32], [4 x i32]* @v, i32 0, i32 1)" are the same address and thus must be must alias. Both of them should be appearing in the alias set. The fact they're not is very surprising.

[mkuper]

It was so surprising that I figured AST ignores these bitcasts intentionally, and expects the clients to handle them.
Abandoning this patch, I'll look into what's going on in AST.

[sanjoy]

In D17936#373784, @reames wrote:

Ah, that was really helpful. This is definitely an AST bug.
"bitcast (i32* getelementptr inbounds ([4 x i32], [4 x i32]* @v, i32 0, i32 1) to i8*" and "getelementptr inbounds ([4 x i32], [4 x i32]* @v, i32 0, i32 1)" are the same address and thus must be must alias. Both of them should be appearing in the alias set. The fact they're not is very surprising.

The problem is that AST calls MemIntrinsic::getDest to get the pointer it should add, which returns the pointer after stripPointerCasts (though I'm not convinced (either way) that differentiating x and (bitcast x to Y) in AST is a good idea, since they're the same value at runtime).

[mkuper]

Well, apparently it does differentiate them when MemIntrinsics are not involved.
E.g. if the memcpy were a store, we'd get:

AliasSet[0x6ad8c0, 2] must alias, Mod       Pointers: (i32* getelementptr inbounds ([4 x i32], [4 x i32]* @v, i32 0, i32 1), 4), (i8* bitcast (i32* getelementptr inbounds ([4 x i32], [4 x i32]* @v, i32 0, i32 1) to i8*), 1)

So we have to be consistent, at least.

[reames]

The easiest answer is probably to use getRawDest. The use of the stripPointerCasts is inconsistent with the rest of AST and LICM.

[mkuper]

Yeah, I'll just change it to getRawDest().
Turns out the code that handles memset this way is new, so now I doubt there's any code elsewhere that expects pointer casts to be missing.

include/llvm/Transforms/Utils/LoopUtils.h

 /// AliasSet information for all instructions of the loop and loop safety
 /// information as arguments. It returns changed status.
 bool promoteLoopAccessesToScalars(AliasSet &, SmallVectorImpl<BasicBlock*> &,
                                   SmallVectorImpl<Instruction*> &,
                                   PredIteratorCache &, LoopInfo *,
                                   DominatorTree *, Loop *, AliasSetTracker *,
                                   LICMSafetyInfo *);
 
+/// \brief Check whether a constant expression is used by any instruction
+/// in a given loop.
+bool isConstantExprUsedInLoop(ConstantExpr* CE, Loop *CurLoop);
+
 /// \brief Computes safety information for a loop
 /// checks loop body & header for the possibility of may throw
 /// exception, it takes LICMSafetyInfo and loop as argument.
 /// Updates safety information in LICMSafetyInfo argument.
 void computeLICMSafetyInfo(LICMSafetyInfo *, Loop *);
 
 /// \brief Returns the instructions that use values defined in the loop.
 SmallVector<Instruction *, 8> findDefsUsedOutsideOfLoop(Loop *L);

lib/Transforms/Scalar/LICM.cpp

void replaceLoadWithValue(LoadInst *LI, Value *V) const override {
       AST.copyValue(LI, V);
     }
     void instructionDeleted(Instruction *I) const override {
       AST.deleteValue(I);
     }
   };
 } // end anon namespace
 
+/// Check whether a constant expression is used by any instruction
+/// in a given loop. This, unforunately, requires a recursive lookup.
+bool llvm::isConstantExprUsedInLoop(ConstantExpr *CE, Loop *CurLoop) {
+  SmallVector<ConstantExpr *, 4> WorkList;
+  WorkList.push_back(CE);
+
+  while (!WorkList.empty()) {
+    auto Curr = WorkList.pop_back_val();
+    // We only care if the user is an instruction or a constant expression.
+    // Check if instructions are in the loop, and recurse down ConstantExpr.
+    for (auto U : Curr->users()) {
+      if (auto UI = dyn_cast<Instruction>(U)) {
+        if (CurLoop->contains(UI))
+          return true;
+      } else if (auto UCE = dyn_cast<ConstantExpr>(U))
+        WorkList.push_back(UCE);
+    }
+  }
+
+  return false;
+}
+
 /// Try to promote memory values to scalars by sinking stores out of the
 /// loop and moving loads to before the loop.  We do this by looping over
 /// the stores in the loop, looking for stores to Must pointers which are
 /// loop invariant.
 ///
 bool llvm::promoteLoopAccessesToScalars(AliasSet &AS,
                                         SmallVectorImpl<BasicBlock*>&ExitBlocks,
                                         SmallVectorImpl<Instruction*>&InsertPts,
for (AliasSet::iterator ASI = AS.begin(), E = AS.end(); ASI != E; ++ASI) {
 
     // Check that all of the pointers in the alias set have the same type.  We
     // cannot (yet) promote a memory location that is loaded and stored in
     // different sizes.
     if (SomePtr->getType() != ASIV->getType())
       return Changed;
 
     for (User *U : ASIV->users()) {
+      // If we encounter a constant expression which is used by an instruction
+      // inside the loop, bail.
+      // FIXME: This is somewhat too conservative, but for now, err on the side
+      // of correctness.
+      if (auto UCE = dyn_cast<ConstantExpr>(U))
+        if (isConstantExprUsedInLoop(UCE, CurLoop))
+          return Changed;
+
       // Ignore instructions that are outside the loop.
       Instruction *UI = dyn_cast<Instruction>(U);
       if (!UI || !CurLoop->contains(UI))
         continue;
 
       // If there is an non-load/store instruction in the loop, we can't promote
       // it.
       if (const LoadInst *Load = dyn_cast<LoadInst>(UI)) {

test/Transforms/LICM/pr26843.ll

+; RUN: opt -S -basicaa -licm < %s | FileCheck %s
+
+target datalayout = "e-m:x-p:32:32-i64:64-f80:32-n8:16:32-a:0:32-S32"
+target triple = "i686-pc-windows-msvc18.0.0"
+
+@v = common global [4 x i32] zeroinitializer, align 4 
+
+; Make sure the store to v[1] is not sunk past the memset to v[1]-v[3].
+; CHECK-LABEL: @main
+; CHECK: for.body:
+; CHECK-NEXT: store i32 1, i32* getelementptr inbounds ([4 x i32], [4 x i32]* @v, i32 0, i32 1)
+; CHECK-NEXT: tail call void @llvm.memset
+; CHECK: end:
+; CHECK-NEXT: ret i32 0
+
+define i32 @main(i1 %k) {
+entry:
+  br label %for.body
+ 
+for.body:
+  store i32 1, i32* getelementptr inbounds ([4 x i32], [4 x i32]* @v, i32 0, i32 1), align 4
+  tail call void @llvm.memset.p0i8.i32(i8* bitcast (i32* getelementptr inbounds ([4 x i32], [4 x i32]* @v, i32 0, i32 1) to i8*), i8 0, i32 12, i32 4, i1 false)
+  br label %for.latch
+  
+for.latch:
+  br i1 %k, label %for.body, label %end
+
+end:
+  ret i32 0
+}
+
+declare void @llvm.memset.p0i8.i32(i8* nocapture, i8, i32, i32, i1)