[LSR] don't attempt to promote ephemeral values to indvars

[jingyue]

Summary

This at least saves compile time. I also encountered a case where
ephemeral values affect whether other variables are promoted, causing
performance issues. It may be a bug in LSR, but I didn't manage to
reduce it yet. Anyhow, I believe it's in general not worth considering
ephemeral values in LSR.

[hfinkel]

LGTM.

include/llvm/Analysis/IVUsers.h

 #define LLVM_ANALYSIS_IVUSERS_H
 
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/ScalarEvolutionNormalization.h"
 #include "llvm/IR/ValueHandle.h"
 
 namespace llvm {
 
+class AssumptionCache;
 class DominatorTree;
 class Instruction;
 class Value;
 class ScalarEvolution;
 class SCEV;
 class IVUsers;
 class DataLayout;
 

 
 private:
   mutable ilist_node<IVStrideUse> Sentinel;
 };
 
 class IVUsers : public LoopPass {
   friend class IVStrideUse;
   Loop *L;
+  AssumptionCache *AC;
   LoopInfo *LI;
   DominatorTree *DT;
   ScalarEvolution *SE;
-  SmallPtrSet<Instruction*,16> Processed;
+  SmallPtrSet<Instruction*, 16> Processed;
 
   /// IVUses - A list of all tracked IV uses of induction variable expressions
   /// we are interested in.
   ilist<IVStrideUse> IVUses;
 
+  // Ephemeral values used by @llvm.assume in this function.
+  SmallPtrSet<const Value *, 32> EphValues;
+
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
   bool runOnLoop(Loop *L, LPPassManager &LPM) override;
 
   void releaseMemory() override;
 
 public:
   static char ID; // Pass ID, replacement for typeid

lib/Analysis/IVUsers.cpp

 //===- IVUsers.cpp - Induction Variable Users -------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements bookkeeping for "interesting" users of expressions
 // computed from induction variables.
 //
 //===----------------------------------------------------------------------===//
 
-#include "llvm/Analysis/IVUsers.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/Analysis/AssumptionCache.h"
+#include "llvm/Analysis/CodeMetrics.h"
+#include "llvm/Analysis/IVUsers.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Type.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 using namespace llvm;
 
 #define DEBUG_TYPE "iv-users"
 
 char IVUsers::ID = 0;
 INITIALIZE_PASS_BEGIN(IVUsers, "iv-users",
                       "Induction Variable Users", false, true)
+INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
 INITIALIZE_PASS_END(IVUsers, "iv-users",
                       "Induction Variable Users", false, true)
 
 Pass *llvm::createIVUsersPass() {
   return new IVUsers();
bool IVUsers::AddUsersImpl(Instruction *I,
 
   // LSR is not APInt clean, do not touch integers bigger than 64-bits.
   // Also avoid creating IVs of non-native types. For example, we don't want a
   // 64-bit IV in 32-bit code just because the loop has one 64-bit cast.
   uint64_t Width = SE->getTypeSizeInBits(I->getType());
   if (Width > 64 || !DL.isLegalInteger(Width))
     return false;
 
+  // Don't attempt to promote ephemeral values to indvars. They will be removed
+  // later anyway.
+  if (EphValues.count(I))
+    return false;
+
   // Get the symbolic expression for this instruction.
   const SCEV *ISE = SE->getSCEV(I);
 
   // If we've come to an uninteresting expression, stop the traversal and
   // call this a user.
   if (!isInteresting(ISE, I, L, SE, LI))
     return false;
 

 }
 
 IVUsers::IVUsers()
     : LoopPass(ID) {
   initializeIVUsersPass(*PassRegistry::getPassRegistry());
 }
 
 void IVUsers::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.addRequired<AssumptionCacheTracker>();
   AU.addRequired<LoopInfoWrapperPass>();
   AU.addRequired<DominatorTreeWrapperPass>();
   AU.addRequired<ScalarEvolution>();
   AU.setPreservesAll();
 }
 
 bool IVUsers::runOnLoop(Loop *l, LPPassManager &LPM) {
 
   L = l;
+  AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
+      *L->getHeader()->getParent());
   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   SE = &getAnalysis<ScalarEvolution>();
 
+  // Collect ephemeral values so that AddUsersIfInteresting skips them.
+  EphValues.clear();
+  CodeMetrics::collectEphemeralValues(L, AC, EphValues);
+
   // Find all uses of induction variables in this loop, and categorize
   // them by stride.  Start by finding all of the PHI nodes in the header for
   // this loop.  If they are induction variables, inspect their uses.
   for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I)
     (void)AddUsersIfInteresting(I);
 
   return false;
 }

test/Transforms/LoopStrengthReduce/ephemeral.ll

+; RUN: opt < %s -loop-reduce -S | FileCheck %s
+
+target datalayout = "e-i64:64-v16:16-v32:32-n16:32:64"
+
+; for (int i = 0; i < n; ++i) {
+;   use(i * 5 + 3);
+;   // i * a + b is ephemeral and shouldn't be promoted by LSR
+;   __builtin_assume(i * a + b >= 0);
+; }
+define void @ephemeral(i32 %a, i32 %b, i32 %n) {
+; CHECK-LABEL: @ephemeral(
+entry:
+  br label %loop
+
+loop:
+  %i = phi i32 [ 0, %entry ], [ %inc, %loop ]
+  ; Only i and i * 5 + 3 should be indvars, not i * a + b.
+; CHECK: phi i32
+; CHECK: phi i32
+; CHECK-NOT: phi i32
+  %inc = add nsw i32 %i, 1
+  %exitcond = icmp eq i32 %inc, %n
+
+  %0 = mul nsw i32 %i, 5
+  %1 = add nsw i32 %0, 3
+  call void @use(i32 %1)
+
+  %2 = mul nsw i32 %i, %a
+  %3 = add nsw i32 %2, %b
+  %4 = icmp sgt i32 %3, -1
+  call void @llvm.assume(i1 %4)
+
+  br i1 %exitcond, label %exit, label %loop
+
+exit:
+  ret void
+}
+
+declare void @use(i32)
+
+declare void @llvm.assume(i1)