Add some shortcuts in Value Propagation for alloca

[wmi]

Summary

The is the part1 to solve https://llvm.org/bugs/show_bug.cgi?id=10584

Inlining functions called inside of a large loop can introduce many long stretched variables because the alloca instructions inside callee will be promoted to the entry of the caller. Such long stretched variables could increase the compile time of correlated value propagation (CVP) and register allocation significantly (More significantly for value propagation).

The fact that a lot of alloca instructions are promoted can be used to reduce the compile time of CVP. CVP checks non-null for pointer params of each callsite. If we know the def of param is an alloca instruction, we know it is non-null without querying LVI. Similarly, CVP checks constant pointer for each mem access. If the def of the pointer is an alloca instruction, we know it is not a constant pointer without querying LVI. These shortcuts can reduce the cost of CVP significantly.

[davidxl]

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

322 ↗

(On Diff #50361)

Maybe add a helper function to make this more readable:

if (mayHaveNullValue(...) && ...

324 ↗

(On Diff #50361)

Have a helper function like:

bool isValueNonNull(V) -- which does simple checks.

So the combined check becomes:

if (mayHaveNullValue(...) && (isValueNonNull(V) || LVI ....)) {
}

Note that isValueNonNull can also handle simple cases with gep:

foo() {

 int a[10];
  ...
  bar(&a[5]);
...

}
we know &a[5] can not be null.

test/Transforms/CorrelatedValuePropagation/alloca.ll

4 ↗

(On Diff #50361)

not constant --> not null.

[reames]

Really interesting observations and great idea, but the patch is not structured well. In both cases, we're really talking about generic properties of LVI and we should structure it that way. That should help all callers of LVI, not just these two.

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

180 ↗

(On Diff #50361)

This should be sunk inside LVI. Specifically, at the top of LazyValueInfo::getConstant.

I'm also not entirely sure this is accurate. I could construct a branch of the form:
if (%alloca == %some_constant_pointer) {
} else { }

Inside the if clause, I could find a constant value for the alloca. It's just that we happen to know that the branch can't be true and thus that we'd only be able to simplify in dead code.

At minimum, we should have a better description here. This is effectively a profitability heuristic more than anything else.

324 ↗

(On Diff #50361)

This is the wrong place. Rather than special casing this particular caller, we should really sink this down into LVI. We could do this in one of two ways:

1. Use the non-context sensative form of isKnownNonNull in getPreciateAt when answering a non-null query.
2. Recognize the fact that the only fact we can infer about a pointer typed value is a constant or non-constant result. The only non-constant we can get - I think - is not-null. We can probably short circuit the search in this case.

[davidxl]

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

324 ↗

(On Diff #50361)

I agree with you wrt to the final picture -- but should this be done in stages (to avoid over fixing the problem at hand)? Basically have a local fix now, get it stablized/tested and then move on to a general fix? (I am fine either way)

[wmi]

Addressed David and Philip's comments. Fixed tests under clang/test.

[wmi]

Ping.

[reames]

lib/Analysis/LazyValueInfo.cpp

1381 ↗

(On Diff #50540)

Use stripPointerCasts

1390 ↗

(On Diff #50540)

This bail is reasonable. Needs commented and code cleanup, but otherwise ready to go in. (I am purposely *not* saying LGTM yet.)

1512 ↗

(On Diff #50540)

This check is wrong. Just use ValueTracking

1523 ↗

(On Diff #50540)

if (V->getType()->isPointerTy() &&
C->isNullValue() && isKnownNonNull(V))

Use isKnownNonNull from ValueTracking.

Comment why this is here. In particular, this is only a fastpath, falling through would be correct.

[wmi]

reames, thanks for the helpful comments. Patch updated as suggested.

[reames]

I just checked in a change which may greatly accelerate LVI for the comparison against null case. Can you check to see if after "267642: [LVI] Reduce compile time by lazily scanning blocks if needed." you're still seeing compile time problems?

The not-constant bypass might still be needed. I'm not entirely sure.

[wmi]

Hi Philip,

I tried r267642 using testcases - Groonga and scribus from PR10584.
The result showed r267642 didn't reduce the compile time much. I
looked at r267642 and found a possible reason was that the first
shortcut of nonnull check took effect only when current BB was the
entry BB so we still needed to iterate CFG, right?

scribus13format.cc (scribus):
r266775: 57.89s
r266775 + r267642: 56.05s
r266775 + patch here: 31.17s

expr.c (Groonga):
r266775: 226.03s
r266775 + r267642: 225.32s
r266775 + patch here: 44.10s

Thanks,
Wei.

[wmi]

Sorry for not visiting the patch for a long time. I just evaluated the original testcase on trunk. The compile time issue was still there, and the patch would still help. Philip, maybe it is still worth to consider the patch since the simple shortcut patch will not bring any harm?

[reames]

Sorry for being unresponsive for so long. This has reached the top of my queue again.

I'm still not entirely happy with this patch, mostly because I don't feel I understand *why* it makes such a huge difference, but I've also held this up for much too long. This is a reasonable approach to a real problem and we can iterate in tree if needed.

LGTM.

lib/Analysis/LazyValueInfo.cpp

1380 ↗

(On Diff #54440)

Add
/// Returns true if we can statically tell that this value will never be a "useful" constant. In practice, this means we've got something like an alloca or a malloc call for which a comparison against a constant can only be guarding dead code. Note that we are potentially giving up some precision here (a constant result) in favour of avoiding a expensive search for a easily answered common query.

llvm/trunk/lib/Analysis/LazyValueInfo.cpp

 LazyValueInfo LazyValueAnalysis::run(Function &F, FunctionAnalysisManager &FAM) {
   auto &AC = FAM.getResult<AssumptionAnalysis>(F);
   auto &TLI = FAM.getResult<TargetLibraryAnalysis>(F);
   auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(F);
 
   return LazyValueInfo(&AC, &TLI, DT);
 }
 
+/// Returns true if we can statically tell that this value will never be a
+/// "useful" constant.  In practice, this means we've got something like an
+/// alloca or a malloc call for which a comparison against a constant can
+/// only be guarding dead code.  Note that we are potentially giving up some
+/// precision in dead code (a constant result) in favour of avoiding a
+/// expensive search for a easily answered common query.
+static bool isKnownNonConstant(Value *V) {
+  V = V->stripPointerCasts();
+  // The return val of alloc cannot be a Constant.
+  if (isa<AllocaInst>(V))
+    return true;
+  return false;
+}
+
 Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB,
                                      Instruction *CxtI) {
+  // Bail out early if V is known not to be a Constant.
+  if (isKnownNonConstant(V))
+    return nullptr;
+
   const DataLayout &DL = BB->getModule()->getDataLayout();
   LVILatticeVal Result =
       getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI);
 
   if (Result.isConstant())
     return Result.getConstant();
   if (Result.isConstantRange()) {
     ConstantRange CR = Result.getConstantRange();
LVILatticeVal Result =
       getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
 
   return getPredicateResult(Pred, C, Result, DL, TLI);
 }
 
 LazyValueInfo::Tristate
 LazyValueInfo::getPredicateAt(unsigned Pred, Value *V, Constant *C,
                               Instruction *CxtI) {
+  // Is or is not NonNull are common predicates being queried. If
+  // isKnownNonNull can tell us the result of the predicate, we can
+  // return it quickly. But this is only a fastpath, and falling
+  // through would still be correct.
+  if (V->getType()->isPointerTy() && C->isNullValue() &&
+      isKnownNonNull(V->stripPointerCasts())) {
+    if (Pred == ICmpInst::ICMP_EQ)
+      return LazyValueInfo::False;
+    else if (Pred == ICmpInst::ICMP_NE)
+      return LazyValueInfo::True;
+  }
   const DataLayout &DL = CxtI->getModule()->getDataLayout();
   LVILatticeVal Result = getImpl(PImpl, AC, &DL, DT).getValueAt(V, CxtI);
   Tristate Ret = getPredicateResult(Pred, C, Result, DL, TLI);
   if (Ret != Unknown)
     return Ret;
 
   // Note: The following bit of code is somewhat distinct from the rest of LVI;
   // LVI as a whole tries to compute a lattice value which is conservatively

llvm/trunk/test/Transforms/CorrelatedValuePropagation/alloca.ll

+; RUN: opt -S -correlated-propagation -debug-only=lazy-value-info <%s 2>&1 | FileCheck %s
+;
+; Shortcut in Correlated Value Propagation ensures not to take Lazy Value Info
+; analysis for %a.i and %tmp because %a.i is defined by alloca and %tmp is
+; defined by alloca + bitcast. We know the ret value of alloca is nonnull.
+;
+; CHECK-NOT: LVI Getting edge value   %a.i = alloca i64, align 8 at 'for.body'
+; CHECK-NOT: LVI Getting edge value   %tmp = bitcast i64* %a.i to i8* from 'for.cond' to 'for.body'
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@.str = private unnamed_addr constant [8 x i8] c"a = %l\0A\00", align 1
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.start(i64, i8* nocapture)
+
+declare void @hoo(i64*)
+
+declare i32 @printf(i8* nocapture readonly, ...)
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.end(i64, i8* nocapture)
+
+define void @goo(i32 %N, i64* %b) {
+entry:
+  %a.i = alloca i64, align 8
+  %tmp = bitcast i64* %a.i to i8*
+  %c = getelementptr inbounds i64, i64* %b, i64 0
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.body, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+  %cmp = icmp slt i32 %i.0, %N
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  call void @llvm.lifetime.start(i64 8, i8* %tmp)
+  call void @hoo(i64* %a.i)
+  call void @hoo(i64* %c)
+  %tmp1 = load volatile i64, i64* %a.i, align 8
+  %call.i = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([8 x i8], [8 x i8]* @.str, i64 0, i64 0), i64 %tmp1)
+  call void @llvm.lifetime.end(i64 8, i8* %tmp)
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}