[LICM] Don't require optimized uses

[nikic]

Summary

LICM currently requests optimized use MSSA form. This is wasteful, because LICM doesn't actually care about most uses, only those of invariant pointers in loops. Everything else doesn't need to be optimized.

LICM already uses the clobber walker in most places. This patch adjusts one place that was using getDefiningAccess() to use it as well, so we no longer have a dependence on pre-optimized uses.

This change is not NFC in that the fallback on the defining access when there are too many clobber calls may now fall back to an unoptimized use. In practice, I've not seen any problems with this though. If desired, we could also increase licm-mssa-optimization-cap to a higher value (increasing this from 100 to 200 has no impact on average compile-time -- but also doesn't appear to have any impact on LICM quality either).

This makes for a 0.9% geomean compile-time improvement: http://llvm-compile-time-tracker.com/compare.php?from=6afe972195454a1110ed8d20c6f2a547e6366379&to=fb64abececc685794fff46227eb7f383218150ce&stat=instructions:u

[fhahn]

LGTM given the good wins in compile-time vs the small number of changes in the test set.

If this is the source of regressions we can always adjust the limit

llvm/lib/Transforms/Scalar/LICM.cpp

bool LoopInvariantCodeMotion::runOnLoop(Loop *L, AAResults *AA, LoopInfo *LI,
                                         TargetLibraryInfo *TLI,
                                         TargetTransformInfo *TTI,
                                         ScalarEvolution *SE, MemorySSA *MSSA,
                                         OptimizationRemarkEmitter *ORE,
                                         bool LoopNestMode) {
   bool Changed = false;
 
   assert(L->isLCSSAForm(*DT) && "Loop is not in LCSSA form.");
-  MSSA->ensureOptimizedUses();
 
   // If this loop has metadata indicating that LICM is not to be performed then
   // just exit.
   if (hasDisableLICMTransformsHint(L)) {
     return false;
   }
 
   // Don't sink stores from loops with coroutine suspend instructions.
if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
     // loop), or ordered loads (stored as Defs!), don't move this store.
     // Could do better here, but this is conservatively correct.
     // TODO: Cache set of Uses on the first walk in runOnLoop, update when
     // moving accesses. Can also extend to dominating uses.
     for (auto *BB : CurLoop->getBlocks())
       if (auto *Accesses = MSSA->getBlockAccesses(BB)) {
         for (const auto &MA : *Accesses)
           if (const auto *MU = dyn_cast<MemoryUse>(&MA)) {
-            auto *MD = MU->getDefiningAccess();
+            auto *MD = getClobberingMemoryAccess(*MSSA, BAA, Flags,
+                const_cast<MemoryUse *>(MU));
             if (!MSSA->isLiveOnEntryDef(MD) &&
                 CurLoop->contains(MD->getBlock()))
               return false;
             // Disable hoisting past potentially interfering loads. Optimized
             // Uses may point to an access outside the loop, as getClobbering
             // checks the previous iteration when walking the backedge.
             // FIXME: More precise: no Uses that alias SI.
             if (!Flags.getIsSink() && !MSSA->dominates(SIMD, MU))

llvm/test/Analysis/MemorySSA/pr43427.ll

 ; CHECK: lbl2:
 ; CHECK-NEXT: ; [[NO8:.*]] = MemoryPhi({lbl3,[[NO7:.*]]},{for.end,[[NO2]]})
 ; CHECK-NEXT:  br label %lbl3
 
 ; CHECK: lbl3:
 ; CHECK-NEXT: [[NO7]] = MemoryPhi({lbl2,[[NO8]]},{for.end,2})
 
 ; CHECK: cleanup:
-; CHECK-NEXT: MemoryUse([[NO7]])
+; CHECK-NEXT: MemoryUse([[NO2]])
 ; CHECK-NEXT:  %cleanup.dest = load i32, ptr undef, align 1
 
 ; CHECK: lbl1.backedge:
 ; CHECK-NEXT:  [[NO9]] = MemoryPhi({cleanup,[[NO7]]},{if.else,2})
 ; CHECK-NEXT:   br label %lbl1
 
 ; CHECK: cleanup.cont:
 ; CHECK-NEXT: ; [[NO6:.*]] = MemoryDef([[NO7]])

llvm/test/Analysis/MemorySSA/pr45927.ll

 ; CHECK-NEXT: br i1 false, label %f.exit.thread.i, label %f.exit.i
 
 ; CHECK: f.exit.thread.i:
 ; CHECK-NEXT: %inc.i.lcssa = phi i16 [ %inc.i, %for.cond.i ]
 ; CHECK-NEXT: ; [[NO6:.*]] = MemoryDef([[NO5]])
 ; CHECK-NEXT: store i16 %inc.i.lcssa, ptr @c, align 1
 ; CHECK-NEXT: ; [[NO2:.*]] = MemoryDef([[NO6]])
 ; CHECK-NEXT: store i16 1, ptr @a, align 1
-; CHECK-NEXT: ; MemoryUse([[NO2]])
+; CHECK-NEXT: ; MemoryUse([[NO6]])
 ; CHECK-NEXT: %tmp2 = load i16, ptr @c, align 1
 ; CHECK-NEXT: br label %g.exit
 
 ; CHECK: f.exit.i
 ; CHECK-NEXT: br i1 false, label %g.exit.loopexit, label %for.cond.i
 
 ; CHECK: g.exit.loopexit:
 ; CHECK-NEXT: %inc.i.lcssa2 = phi i16 [ %inc.i, %f.exit.i ]

llvm/test/Analysis/MemorySSA/pr49859.ll

 ; CHECK-NEXT: ; [[NO20:.*]] = MemoryPhi({if.then,[[NO9:.*]]},{for.cond.cleanup,[[NO8:.*]]})
 ; CHECK-NEXT: ; [[NO12:.*]] = MemoryDef([[NO20]])
 ; CHECK-NEXT: call void @llvm.lifetime.end.p0(i64 1, ptr %i)
 final.cleanup:                                          ; preds = %if.then, %for.cond.cleanup
   call  void @llvm.lifetime.end.p0(i64 1, ptr %i) #3
   br label %for.end
 
 ; CHECK: for.end:
-; CHECK-NEXT: ; MemoryUse([[NO12]])
+; CHECK-NEXT: ; MemoryUse([[NO20]])
 ; CHECK-NEXT:  %3 = load i8, ptr %sum, align 1
 for.end:                                          ; preds = %final.cleanup
   %8 = load i8, ptr %sum, align 1
   call  void @llvm.lifetime.start.p0(i64 1, ptr %res.addr.i)
   store i8 %8, ptr %res.addr.i, align 1
   %9 = load i8, ptr %res.addr.i, align 1
   call  void @foo(i8 %9) #3
   call  void @llvm.lifetime.end.p0(i64 1, ptr %res.addr.i)