[SCEV] Added a utility method that raising the number 2 to the desired power to SCEV

[dbakunevich]

Summary

The new function has been added to SCEV that allows
to raise the number 2 to the desired power.

[mkazantsev]

Please write a more reasonable patch name

llvm/include/llvm/Analysis/ScalarEvolution.h

659

1. Degree -> Power
2. Does it really have to be long long? I mean, it's neither signed nor practically that huge.

660

This is incorrect for anything greater than 31. (1 << 32) is just zero, no matter the type.

llvm/unittests/Analysis/ScalarEvolutionTest.cpp

1764

Just check that they are constants you expect to see.

[mkazantsev]

llvm/include/llvm/Analysis/ScalarEvolution.h

659

Change return types here to const SCEVConstant *? Can be an NFC follow-up.

[mkazantsev]

llvm/include/llvm/Analysis/ScalarEvolution.h

660

Even if you make it 1LL << 32, it is still wrong. You should use APInt to construct the constant,

[mkazantsev]

llvm/include/llvm/Analysis/ScalarEvolution.h

658

/// Return a SCEV for the constant \p Power of two.

660

You still haven't addressed my previous comment here. Test for Power = 62? You'll see it fails.

[nikic]

Where is this method going to be used?

[dbakunevich]

In D144381#4154615, @nikic wrote:

Where is this method going to be used?

This helper method is planned to be used to improve the SCEV module. In particular, to improve existing optimizations and to write new ones.

llvm/include/llvm/Analysis/ScalarEvolution.h

659

I'll do it in the next NFC patch.

[mkazantsev]

Code is fine with nits now, but I want to see the application before I approve this.

llvm/include/llvm/Analysis/ScalarEvolution.h

660

Assert that Power is less than type width?

llvm/unittests/Analysis/ScalarEvolutionTest.cpp

1750

param not needed

1760

Use Type::getInt64Ty(Ctx)

1761

{ } not needed.

[nikic]

llvm/include/llvm/Analysis/ScalarEvolution.h

661

APInt::getOneBitSet().

[mkazantsev]

I talked to Dmitry offline, and the motivating example is in downstream code. However, I think this utility function is still a good thing to have in general, maybe someone else will use it.

@dbakunevich I propose commit message

[SCEV][NFC] Introduce utility function to get power of 2

[nikic]

I talked to Dmitry offline, and the motivating example is in downstream code. However, I think this utility function is still a good thing to have in general, maybe someone else will use it.

There are two uses of APInt::getOneBitSet() that could make use of this API -- but they specify the bitwidth as an integer, not as a type.

Though TBH I can't say the value of getPowerOfTwo(BitWidth, TZ) over getConstant(APInt::getOneBitSet(BitWidth, TZ)) is particularly large.

llvm/include/llvm/Analysis/ScalarEvolution.h

public:
   const SCEV *getCouldNotCompute();
 
   /// Return a SCEV for the constant 0 of a specific type.
   const SCEV *getZero(Type *Ty) { return getConstant(Ty, 0); }
 
   /// Return a SCEV for the constant 1 of a specific type.
   const SCEV *getOne(Type *Ty) { return getConstant(Ty, 1); }
 
+  /// Return a SCEV for the constant \p Power of two.
+  const SCEV *getPowerOfTwo(Type *Ty, unsigned Power) {
+    assert(Power < getTypeSizeInBits(Ty) && "Power out of range");
+    return getConstant(APInt::getOneBitSet(getTypeSizeInBits(Ty), Power));
+  }
+
   /// Return a SCEV for the constant -1 of a specific type.
   const SCEV *getMinusOne(Type *Ty) {
     return getConstant(Ty, -1, /*isSigned=*/true);
   }
 
   /// Return an expression for a TypeSize.
   const SCEV *getSizeOfExpr(Type *IntTy, TypeSize Size);
 

llvm/unittests/Analysis/ScalarEvolutionTest.cpp

runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
     auto *ScevIV = SE.getSCEV(getInstructionByName(F, "iv"));
     const Loop *L = cast<SCEVAddRecExpr>(ScevIV)->getLoop();
 
     const SCEV *ITC = SE.getConstantMaxTripCountFromArray(L);
     EXPECT_TRUE(isa<SCEVCouldNotCompute>(ITC));
   });
 }
 
+TEST_F(ScalarEvolutionsTest, CheckGetPowerOfTwo) {
+  Module M("CheckGetPowerOfTwo", Context);
+  FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context), {}, false);
+  Function *F = Function::Create(FTy, Function::ExternalLinkage, "foo", M);
+  BasicBlock *Entry = BasicBlock::Create(Context, "entry", F);
+  IRBuilder<> Builder(Entry);
+  Builder.CreateRetVoid();
+  ScalarEvolution SE = buildSE(*F);
+
+  for (unsigned short i = 0; i < 64; ++i)
+    EXPECT_TRUE(
+        dyn_cast<SCEVConstant>(SE.getPowerOfTwo(Type::getInt64Ty(Context), i))
+            ->getValue()
+            ->equalsInt(1ULL << i));
+}
+
 }  // end namespace llvm