[SCEV][NFC] Introduce isSafeToExpandAt function to SCEVExpander

[mkazantsev]

Summary

This function checks that:

1. It is safe to expand a SCEV;
2. It is OK to materialize it at the specified location.

For example, attempt to expand a loop's AddRec to the same loop's preheader should fail.

[reames]

relatively minor code comments.

include/llvm/Analysis/ScalarEvolutionExpander.h

30

Adjust this comment to reflect the requirement to check dominance.

i.e. "are safe to speculate anywhere their operands are defined"

lib/Analysis/ScalarEvolutionExpander.cpp

2294

From the comment, this sounds like it's going to be smarted than isSafeToExpand where it's really more restrictive.

Maybe add a TODO about handling cases which aren't *generally* safe to speculate but are safe to speculate *at this particular location*?

[mkazantsev]

lib/Analysis/ScalarEvolutionExpander.cpp

2294

Let's not do it until we know the application for that.

[mkazantsev]

Fixed comments.

[reames]

LGTM

include/llvm/Analysis/ScalarEvolutionExpander.h

 #include "llvm/Analysis/TargetFolder.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/ValueHandle.h"
 
 namespace llvm {
   class TargetTransformInfo;
 
   /// Return true if the given expression is safe to expand in the sense that
   /// all materialized values are safe to speculate.
   bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE);
 
+  // Return true if the given expression is safe to expand at the specified
+  // insertion point. Basically it implies two things:
+  // 1) It is OK to expand the given expression in sense of isSafeToExpand;
+  // 2) All expressions included to S are available at the insertion point.
+  //    For example, if some AddRecs are included into S, it checks that the
+  //    insertion point is dominated by its loop's header.
+  bool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint,
+                        ScalarEvolution &SE);
+
   /// This class uses information about analyze scalars to rewrite expressions
   /// in canonical form.
   ///
   /// Clients should create an instance of this class when rewriting is needed,
   /// and destroy it when finished to allow the release of the associated
   /// memory.
   class SCEVExpander : public SCEVVisitor<SCEVExpander, Value*> {
     ScalarEvolution &SE;

lib/Analysis/ScalarEvolutionExpander.cpp

 }
 
 namespace llvm {
 bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE) {
   SCEVFindUnsafe Search(SE);
   visitAll(S, Search);
   return !Search.IsUnsafe;
 }
+
+bool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint,
+                      ScalarEvolution &SE) {
+  return isSafeToExpand(S, SE) && SE.dominates(S, InsertionPoint->getParent());
+}
 }

unittests/Analysis/ScalarEvolutionTest.cpp

TEST_F(ScalarEvolutionsTest, SCEVFoldSumOfTruncs) {
   const auto *B = SE.getNegativeSCEV(B0);
 
   const auto *Expr = SE.getAddExpr(A, B);
   // Verify that the SCEV was folded to 0
   const auto *ZeroConst = SE.getConstant(Int32Ty, 0);
   EXPECT_EQ(Expr, ZeroConst);
 }
 
+// Check that we can correctly identify the points at which the SCEV of the
+// AddRec can be expanded.
+TEST_F(ScalarEvolutionsTest, SCEVExpanderIsSafeToExpandAt) {
+  /*
+   * Create the following code:
+   * func(i64 addrspace(10)* %arg)
+   * top:
+   *  br label %L.ph
+   * L.ph:
+   *  br label %L
+   * L:
+   *  %phi = phi i64 [i64 0, %L.ph], [ %add, %L2 ]
+   *  %add = add i64 %phi2, 1
+   *  %cond = icmp slt i64 %add, 1000; then becomes 2000.
+   *  br i1 %cond, label %post, label %L2
+   * post:
+   *  ret void
+   *
+   */
+
+  // Create a module with non-integral pointers in it's datalayout
+  Module NIM("nonintegral", Context);
+  std::string DataLayout = M.getDataLayoutStr();
+  if (!DataLayout.empty())
+    DataLayout += "-";
+  DataLayout += "ni:10";
+  NIM.setDataLayout(DataLayout);
+
+  Type *T_int64 = Type::getInt64Ty(Context);
+  Type *T_pint64 = T_int64->getPointerTo(10);
+
+  FunctionType *FTy =
+      FunctionType::get(Type::getVoidTy(Context), {T_pint64}, false);
+  Function *F = cast<Function>(NIM.getOrInsertFunction("foo", FTy));
+
+  BasicBlock *Top = BasicBlock::Create(Context, "top", F);
+  BasicBlock *LPh = BasicBlock::Create(Context, "L.ph", F);
+  BasicBlock *L = BasicBlock::Create(Context, "L", F);
+  BasicBlock *Post = BasicBlock::Create(Context, "post", F);
+
+  IRBuilder<> Builder(Top);
+  Builder.CreateBr(LPh);
+
+  Builder.SetInsertPoint(LPh);
+  Builder.CreateBr(L);
+
+  Builder.SetInsertPoint(L);
+  PHINode *Phi = Builder.CreatePHI(T_int64, 2);
+  auto *Add = cast<Instruction>(
+      Builder.CreateAdd(Phi, ConstantInt::get(T_int64, 1), "add"));
+  auto *Limit = ConstantInt::get(T_int64, 1000);
+  auto *Cond = cast<Instruction>(
+      Builder.CreateICmp(ICmpInst::ICMP_SLT, Add, Limit, "cond"));
+  Builder.CreateCondBr(Cond, L, Post);
+  Phi->addIncoming(ConstantInt::get(T_int64, 0), LPh);
+  Phi->addIncoming(Add, L);
+
+  Builder.SetInsertPoint(Post);
+  Builder.CreateRetVoid();
+
+  ScalarEvolution SE = buildSE(*F);
+  const SCEV *S = SE.getSCEV(Phi);
+  EXPECT_TRUE(isa<SCEVAddRecExpr>(S));
+  const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(S);
+  EXPECT_TRUE(AR->isAffine());
+  EXPECT_FALSE(isSafeToExpandAt(AR, Top->getTerminator(), SE));
+  EXPECT_FALSE(isSafeToExpandAt(AR, LPh->getTerminator(), SE));
+  EXPECT_TRUE(isSafeToExpandAt(AR, L->getTerminator(), SE));
+  EXPECT_TRUE(isSafeToExpandAt(AR, Post->getTerminator(), SE));
+}
+
 }  // end anonymous namespace
 }  // end namespace llvm