Clean up: Refactoring the hardcoded value of 6 for FindAvailableLoadedValue()'s parameter MaxInstsToScan.

[lvoufo]

Summary

Any idea why this is hardcoded?
Is it okay to switch the value from 6 to 8 (or else) to resolve the following problem?

Right now, in -O2, -early-cse replaces a load with a store, too early for -instcombine to recognize
subsequent duplicate loads as actual duplicates to be removed.

For example, consider the following code snippet:

%i = alloca %struct.A, align 4
%j = alloca %struct.A, align 4
%0 = bitcast %struct.A* %i to i8*
call void @llvm.lifetime.start(i64 4, i8* %0) #3
%call = call i32 @_Z3onev()
%a2.i = getelementptr inbounds %struct.A, %struct.A* %i, i64 0, i32 0
store i32 %call, i32* %a2.i, align 4, !tbaa !1
%1 = bitcast %struct.A* %i to i8*
%2 = call {}* @llvm.invariant.start(i64 4, i8* %1) #3
%3 = bitcast %struct.A* %j to i8*
call void @llvm.lifetime.start(i64 4, i8* %3) #3
%4 = getelementptr inbounds %struct.A, %struct.A* %i, i64 0, i32 0
%5 = getelementptr inbounds %struct.A, %struct.A* %j, i64 0, i32 0
%6 = load i32, i32* %4, align 4
store i32 %6, i32* %5, align 4, !tbaa !6
%7 = bitcast %struct.A* %j to i8*
%8 = call {}* @llvm.invariant.start(i64 4, i8* %7) #3
call void @_Z3bar1A(i32 %6)
call void @_Z3bar1A(i32 %6)
call void @_Z4foo2PK1AS1_(%struct.A* nonnull %j, %struct.A* nonnull %i)
%9 = getelementptr inbounds %struct.A, %struct.A* %i, i64 0, i32 0
%10 = load i32, i32* %9, align 4       ;  <--- duplicate. Should be removed.
call void @_Z3bar1A(i32 %10)

---

After -early-cse, the above becomes

%i = alloca %struct.A, align 4
%j = alloca %struct.A, align 4
%0 = bitcast %struct.A* %i to i8*
call void @llvm.lifetime.start(i64 4, i8* %0) #3
%call = call i32 @_Z3onev()
%a2.i = getelementptr inbounds %struct.A, %struct.A* %i, i64 0, i32 0
store i32 %call, i32* %a2.i, align 4, !tbaa !1
%1 = call {}* @llvm.invariant.start(i64 4, i8* %0) #3
%2 = bitcast %struct.A* %j to i8*
call void @llvm.lifetime.start(i64 4, i8* %2) #3
%3 = getelementptr inbounds %struct.A, %struct.A* %j, i64 0, i32 0
store i32 %call, i32* %3, align 4, !tbaa !6
%4 = call {}* @llvm.invariant.start(i64 4, i8* %2) #3
call void @_Z3bar1A(i32 %call)
call void @_Z3bar1A(i32 %call)
call void @_Z4foo2PK1AS1_(%struct.A* nonnull %j, %struct.A* nonnull %i)
%5 = load i32, i32* %a2.i, align 4       ;  <--- duplicate. Should be removed.
call void @_Z3bar1A(i32 %5)

---

where the first load from %i has been replaced with the store into %a2.i which points to %i.

For -instcombine to remove the duplicate load above, either

• -early-cse should not merge the first load into the store -- thereby treating the load as not a "trivially redundant instruction", or
• -instcombine should allow FindAvailableLoadedValue() to scan more than 6 instructions.

Note that @llvm.invariant.start() calls are ignored in the count, just like @llvm.lifetime.start().

A quick run has found the value of 8 to be the minimal needed, for this example case scenario.

[nlewycky]

A few unconnected issues:

-1-
Please generate the patch with either:

git diff -U999999 other-branch

or

svn diff --diff-cmd=diff -x -U999999

per the instructions at http://llvm.org/docs/Phabricator.html#requesting-a-review-via-the-web-interface . The symptom of not doing this is that I can't easily see the rest of the function around the parts you modified, and that makes it hard to review the code. I need to go find a copy elsewhere to read.

-2-
Does "opt -basicaa -gvn" clean up the redundant load? If so, is it okay that instcombine doesn't?

-3-
My first preference is to not have instcombine do this transform at all, but I have no suggestion for how to make that happen. The xform redundant with all of mem2reg, sroa, early-cse and gvn, but IIRC it exists to fix a pass ordering problem where one iteration of instcombine makes the transform possible, and doing this load removal makes a transform in the next iteration of instcombine possible.

My second preference is to not rely on a threshold. It's subject to problems like this one, where minor changes that aren't relevant to the semantic behaviour of the program will change the code we generate. We shouldn't have those. One possibility is to track loads as we scan forwards, much like early-cse does. It's a fair amount of code, but actually quite cheap in compile time especially when compared to everything else instcombine does. The idea is that you load, you add it to a map, when you perform an action which may write memory (non-readonly call, or store) you wipe the map. This way, you never need to scan backwards.

My third preference is to query a system designed to do this with caching of queries, such as MemoryDependenceAnalysis (still scans backwards) or MemorySSA (not ready yet). Yes, this makes Instcombine a real clone of the PRE half of GVN instead of just a half-way pretending piece that doesn't really do things right.

Fixing any of the above is a serious project that would take quite some time.

And finally we can bump 6 to 8.

include/llvm/Analysis/Loads.h

41–43

The usual way to do this in LLVM is "cl::opt". Take a look at UnrollCount for an example.

64

Using a cl::opt means you won't get to have a default here (unless you pick a sigil value like -1 to indicate "use the default"). However, I think every caller of this function passes in 6 today, so the default argument is dead anyways.

However, I'm not sure why this should be a caller-controlled value at all.

[lvoufo]

Updating diff to suggested/preferred formatting.

[lvoufo]

In D12886#246629, @nlewycky wrote:

A few unconnected issues:

-1-
Please generate the patch with either:

git diff -U999999 other-branch

or

svn diff --diff-cmd=diff -x -U999999

per the instructions at http://llvm.org/docs/Phabricator.html#requesting-a-review-via-the-web-interface . The symptom of not doing this is that I can't easily see the rest of the function around the parts you modified, and that makes it hard to review the code. I need to go find a copy elsewhere to read.

Ok. Done.

-2-
Does "opt -basicaa -gvn" clean up the redundant load? If so, is it okay that instcombine doesn't?

It does not. Neither "-basicaa -gvn", nor "-basicaa -early-cse -gvn", "nor -basicaa -early-cse -gvn -instcombine", ...
the issue is that the load is actually eliminated with "-O1", but not with "-O2". Examining the passes in -O2, I was able to reduce the problem area down to "-basicaa -instcombine -inline -early-cse -instcombine" (on a lowered sample *.cc program, lowered with optimizations turned off).

-3-
My first preference is to not have instcombine do this transform at all, but I have no suggestion for how to make that happen. The xform redundant with all of mem2reg, sroa, early-cse and gvn, but IIRC it exists to fix a pass ordering problem where one iteration of instcombine makes the transform possible, and doing this load removal makes a transform in the next iteration of instcombine possible.

That may be so, but regardless of why it is the way it is at the moment, how it is affects compilation with -O2.
What is -instcombine designed for in the first place?
W.r.t. load instructions, I view it as a place where duplicate loads are combined so long as they are now too far apart from one another.

My second preference is to not rely on a threshold. It's subject to problems like this one, where minor changes that aren't relevant to the semantic behaviour of the program will change the code we generate. We shouldn't have those. One possibility is to track loads as we scan forwards, much like early-cse does. It's a fair amount of code, but actually quite cheap in compile time especially when compared to everything else instcombine does. The idea is that you load, you add it to a map, when you perform an action which may write memory (non-readonly call, or store) you wipe the map. This way, you never need to scan backwards.

A good starting point would be to a least understand the origin of the current semantics. What does '6' mean? Why '6'? Why not something else? Any documentation available?

My third preference is to query a system designed to do this with caching of queries, such as MemoryDependenceAnalysis (still scans backwards) or MemorySSA (not ready yet). Yes, this makes Instcombine a real clone of the PRE half of GVN instead of just a half-way pretending piece that doesn't really do things right.

Fixing any of the above is a serious project that would take quite some time.

And finally we can bump 6 to 8.

Ok. Could do this temporarily, and explore more future-proof solutions afterwards.

[lvoufo]

include/llvm/Analysis/Loads.h

41–43

Okay. Will do.

64

Not sure. DEF_MAX_INSTS_TO_SCAN was simply meant to highlight the very fact that the same value is reused everywhere anyway.

[lvoufo]

Using cl::opt now.
This patch should focus only on the refactoring and documentation of the value 6.
I will change the value to 8 or consider alternative options (e.g. messing with -gvn instead of -instcombine)
in a separate patch (likely the initial const optimization patch that I'm working on).

[lvoufo]

• Typo fixes.
• Any news on the documentation?
• Is this ready to go?
• What would make this ready to go (or not)?

[lvoufo]

-2-
Does "opt -basicaa -gvn" clean up the redundant load? If so, is it okay that instcombine doesn't?

Now it does, as of Diff 35065 of D11826. But it still does not make it okay imo since once might still expect
something like "-basicaa -instcombine -inline -early-cse -instcombine" to remove redundant loads when
"-basicaa -instcombine -early-cse -instcombine" does.

[nlewycky]

LGTM with changes.

lib/Analysis/Loads.cpp

174 ↗

(On Diff #34950)

max-insts-to-scan is too generic, this name applies across the whole of llvm. Maybe "available-load-scan-limit"?

175–177 ↗

(On Diff #34950)

Mention FindAvailableLoadedValue, don't mention -instcombine.

[Eugene.Zelenko]

Committed in rL248022.

include/llvm/Analysis/Loads.h

 
 /// isSafeToLoadUnconditionally - Return true if we know that executing a load
 /// from this value cannot trap.  If it is not obviously safe to load from the
 /// specified pointer, we do a quick local scan of the basic block containing
 /// ScanFrom, to determine if the address is already accessed.
 bool isSafeToLoadUnconditionally(Value *V, Instruction *ScanFrom,
                                  unsigned Align);
 
+/// DEF_MAX_INSTS_TO_SCAN - the default number of maximum instructions
+/// to scan in the block, used by FindAvailableLoadedValue().
+/// FindAvailableLoadedValue() was introduced in r60148, to improve jump
+/// threading in part by eliminating partially redundant loads.
+/// At that point, the value of MaxInstsToScan was already set to '6'
+/// without documented explanation.
+/// FIXME: Ask r60148 author for details, and complete this documentation.
+/// NOTE: As of now, every use of FindAvailableLoadedValue() uses this default
+/// value of '6'.
+#ifndef DEF_MAX_INSTS_TO_SCAN
+#define DEF_MAX_INSTS_TO_SCAN 6
+#endif
+
 /// FindAvailableLoadedValue - Scan the ScanBB block backwards (starting at
 /// the instruction before ScanFrom) checking to see if we have the value at
 /// the memory address *Ptr locally available within a small number of
 ///  instructions. If the value is available, return it.
 ///
-/// If not, return the iterator for the last validated instruction that the 
+/// If not, return the iterator for the last validated instruction that the
 /// value would be live through.  If we scanned the entire block and didn't
 /// find something that invalidates *Ptr or provides it, ScanFrom would be
-/// left at begin() and this returns null.  ScanFrom could also be left 
+/// left at begin() and this returns null.  ScanFrom could also be left
 ///
 /// MaxInstsToScan specifies the maximum instructions to scan in the block.
 /// If it is set to 0, it will scan the whole block. You can also optionally
 /// specify an alias analysis implementation, which makes this more precise.
 ///
 /// If AATags is non-null and a load or store is found, the AA tags from the
 /// load or store are recorded there.  If there are no AA tags or if no access
 /// is found, it is left unmodified.
 Value *FindAvailableLoadedValue(Value *Ptr, BasicBlock *ScanBB,
                                 BasicBlock::iterator &ScanFrom,
-                                unsigned MaxInstsToScan = 6,
+                                unsigned MaxInstsToScan = DEF_MAX_INSTS_TO_SCAN,
                                 AliasAnalysis *AA = nullptr,
                                 AAMDNodes *AATags = nullptr);
 
 }
 
 #endif

lib/Analysis/Lint.cpp

Value *Lint::findValueImpl(Value *V, bool OffsetOk,
   V = OffsetOk ? GetUnderlyingObject(V, *DL) : V->stripPointerCasts();
   if (LoadInst *L = dyn_cast<LoadInst>(V)) {
     BasicBlock::iterator BBI = L;
     BasicBlock *BB = L->getParent();
     SmallPtrSet<BasicBlock *, 4> VisitedBlocks;
     for (;;) {
       if (!VisitedBlocks.insert(BB).second)
         break;
-      if (Value *U = FindAvailableLoadedValue(L->getPointerOperand(),
-                                              BB, BBI, 6, AA))
+      if (Value *U =
+          FindAvailableLoadedValue(L->getPointerOperand(),
+                                   BB, BBI, DEF_MAX_INSTS_TO_SCAN, AA))
         return findValueImpl(U, OffsetOk, Visited);
       if (BBI != BB->begin()) break;
       BB = BB->getUniquePredecessor();
       if (!BB) break;
       BBI = BB->end();
     }
   } else if (PHINode *PN = dyn_cast<PHINode>(V)) {
     if (Value *W = PN->hasConstantValue())

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

Instruction *InstCombiner::visitLoadInst(LoadInst &LI) {
   if (Instruction *Res = unpackLoadToAggregate(*this, LI))
     return Res;
 
   // Do really simple store-to-load forwarding and load CSE, to catch cases
   // where there are several consecutive memory accesses to the same location,
   // separated by a few arithmetic operations.
   BasicBlock::iterator BBI = &LI;
   AAMDNodes AATags;
-  if (Value *AvailableVal = FindAvailableLoadedValue(Op, LI.getParent(), BBI,
-                                                     6, AA, &AATags)) {
+  if (Value *AvailableVal =
+      FindAvailableLoadedValue(Op, LI.getParent(), BBI,
+                               DEF_MAX_INSTS_TO_SCAN, AA, &AATags)) {
     if (LoadInst *NLI = dyn_cast<LoadInst>(AvailableVal)) {
       unsigned KnownIDs[] = {
         LLVMContext::MD_tbaa,
         LLVMContext::MD_alias_scope,
         LLVMContext::MD_noalias,
         LLVMContext::MD_range,
         LLVMContext::MD_invariant_load,
         LLVMContext::MD_nonnull,
if (SelectInst *SI = dyn_cast<SelectInst>(Op)) {
         LoadInst *V2 = Builder->CreateLoad(SI->getOperand(2),
                                            SI->getOperand(2)->getName()+".val");
         V1->setAlignment(Align);
         V2->setAlignment(Align);
         return SelectInst::Create(SI->getCondition(), V1, V2);
       }
 
       // load (select (cond, null, P)) -> load P
-      if (isa<ConstantPointerNull>(SI->getOperand(1)) && 
+      if (isa<ConstantPointerNull>(SI->getOperand(1)) &&
           LI.getPointerAddressSpace() == 0) {
         LI.setOperand(0, SI->getOperand(2));
         return &LI;
       }
 
       // load (select (cond, P, null)) -> load P
       if (isa<ConstantPointerNull>(SI->getOperand(2)) &&
           LI.getPointerAddressSpace() == 0) {

lib/Transforms/Scalar/JumpThreading.cpp

if (!CondInst) {
     return false;
   }
 
 
   if (CmpInst *CondCmp = dyn_cast<CmpInst>(CondInst)) {
     // If we're branching on a conditional, LVI might be able to determine
     // it's value at the branch instruction.  We only handle comparisons
     // against a constant at this time.
-    // TODO: This should be extended to handle switches as well.  
+    // TODO: This should be extended to handle switches as well.
     BranchInst *CondBr = dyn_cast<BranchInst>(BB->getTerminator());
     Constant *CondConst = dyn_cast<Constant>(CondCmp->getOperand(1));
     if (CondBr && CondConst && CondBr->isConditional()) {
       LazyValueInfo::Tristate Ret =
         LVI->getPredicateAt(CondCmp->getPredicate(), CondCmp->getOperand(0),
                             CondConst, CondBr);
       if (Ret != LazyValueInfo::Unknown) {
         unsigned ToRemove = Ret == LazyValueInfo::True ? 1 : 0;
if (Instruction *PtrOp = dyn_cast<Instruction>(LoadedPtr))
     if (PtrOp->getParent() == LoadBB)
       return false;
 
   // Scan a few instructions up from the load, to see if it is obviously live at
   // the entry to its block.
   BasicBlock::iterator BBIt = LI;
 
   if (Value *AvailableVal =
-        FindAvailableLoadedValue(LoadedPtr, LoadBB, BBIt, 6)) {
+        FindAvailableLoadedValue(LoadedPtr, LoadBB, BBIt)) {
     // If the value if the load is locally available within the block, just use
     // it.  This frequently occurs for reg2mem'd allocas.
     //cerr << "LOAD ELIMINATED:\n" << *BBIt << *LI << "\n";
 
     // If the returned value is the load itself, replace with an undef. This can
     // only happen in dead loops.
     if (AvailableVal == LI) AvailableVal = UndefValue::get(LI->getType());
     if (AvailableVal->getType() != LI->getType())
for (pred_iterator PI = pred_begin(LoadBB), PE = pred_end(LoadBB);
 
     // If we already scanned this predecessor, skip it.
     if (!PredsScanned.insert(PredBB).second)
       continue;
 
     // Scan the predecessor to see if the value is available in the pred.
     BBIt = PredBB->end();
     AAMDNodes ThisAATags;
-    Value *PredAvailable = FindAvailableLoadedValue(LoadedPtr, PredBB, BBIt, 6,
+    Value *PredAvailable = FindAvailableLoadedValue(LoadedPtr, PredBB, BBIt,
+                                                    DEF_MAX_INSTS_TO_SCAN,
                                                     nullptr, &ThisAATags);
     if (!PredAvailable) {
       OneUnavailablePred = PredBB;
       continue;
     }
 
     // If AA tags disagree or are not present, forget about them.
     if (AATags != ThisAATags) AATags = AAMDNodes();