[Attributor] AAValueConstantRange: Value range analysis using constant range

[uenoku]

Summary

This patch introduces AAValueConstantRange, which answers a possible range for integer value in a specific program point.
One of the motivations is propagating existing range metadata. (I think we need to change the situation that range metadata cannot be put to Argument).

The state is a tuple of ConstantRange and it is initialized to (known, assumed) = ([-∞, +∞], empty).

Currently, AAValueConstantRange is created in getAssumedConstant method when AAValueSimplify returns nullptr(worst state).

Supported

• BinaryOperator(add, sub, ...)
• CmpInst(icmp eq, ...)
• !range metadata

AAValueConstantRange is not intended to extend to polyhedral range value analysis.

[uenoku]

Fix typo.

[uenoku]

Add comment

[uenoku]

Remove unused function

[uenoku]

• Add test
• Use SCEV when the value is phi and defined with circular.
• Create AA for CmpInst.

I have found this is broken now, please wait.

[jdoerfert]

Sorry for the wait. I wanted to do a proper initial review and I didn't find the right time.

llvm/include/llvm/Transforms/IPO/Attributor.h

1352

Typo: 'an'

Below, can we make the comments start with three '/'?

1421

I think you need to adjust Assumed too otherwise it might not be a proper subset of Known anymore.

1440

Do we need to intersect the known range here as well?

llvm/lib/Transforms/IPO/Attributor.cpp

2591

I formated the file yesterday, rebase and this should be gone.

4963

If you pass the Attributor changeUseAfterManifest should make this simple.

4968

Can we pass the constant range arguments as const references in the various places.

4975

Shouldn't this imply "an invalid state" (= the worst possible state)? If so, it should never be make it to this point (which you should assert instead).

4991

You should use one of the Attributor::doSthAfterManifest helpers (or a new one). We should avoid modifying values/uses while in the manifest stage.

5079

We should probably provide a helper to make sure the type of a value is OK (I guess integer) and check it in the initialize.

5092

With a check in the initializers this would go away.

5129

I don't think we need to look at all loops here.
The problem is also that getSCEVAtScope might silently fail to actually compute the exit value and instead continue computation with the original one.

I think this is OK already: SE->getUnsignedRange(SE->getSCEV())

5131

Style: With early exits we can minimize indention:
if (!SE || !LI || !I) return false;

5132

We should consider putting some of this in helper methods.

5143

Add a TODO to track the known state as well.

5212

Can you move this case to the beginning Inst * I = ...; if (!I) { ... }, so the rest has one level less of indention?

llvm/test/Transforms/Attributor/value-simplify.ll

193

Please add a FIXME here, should be 7.

[uenoku]

Address comments.

• SCEV is used in initialize.
• getAssumedConstantRange takes a program point (Instruction I) and returns assumed range in that program point.

[uenoku]

llvm/include/llvm/Transforms/IPO/Attributor.h

1421

Fixed.

1440

In my understanding, "Clamp" should only modify the assumption.

llvm/lib/Transforms/IPO/Attributor.cpp

4975

Yes, I changed to assert.

5129

Yes, you are right. I changed to use SE->getUnsignedRange(SE->getSCEV()) as known range. And if a program point (Instrution *I)is given, SCEV->getSCEVAtScope(I->getParent()) is used.

[uenoku]

llvm/lib/Transforms/IPO/Attributor.cpp

5132

I'll do.

[uenoku]

llvm/test/Transforms/Attributor/range.ll

236

I'll add FIXME here because block 4 should be regarded as dead.

[jdoerfert]

I still have to go over the changes properly later, sorry for the wait again.

We should copy the LazyValueInfo analysis test lvi-after-jumpthreading.ll lvi-for-ashr.ll if we can use them to verify the ranges.

Add a TODO that AADereferenceable should use this too.

[uenoku]

Address comment.

• Use LazyValueInfo as known information
• Add test(lvi-*.ll)

[jdoerfert]

I think the final round of comments.

llvm/lib/Transforms/IPO/Attributor.cpp

4906

Nit: I'd move this into the state as a static member (getWorstState) taking a bit width. That makes it consistent with the IntegerStates.

4978

Shouldn't we merge the SCEV and LVI information into the known state during intialization and then be done with it?

4999

As mentioned above, if we merge the SCEV and LVI results into known there is no need to do anything but return the assumed value. The TODO should stay though.

5052

I don't think we have a test which checks the metadata, right? We should create one if possible or add a TODO here explaining why it's not possible yet.

5215

I doubt this works to prevent PHI circles. If you have %phi = phi [0, ...], [%bo1, ...]; ...; %bo0 = add %phi, 1; ...; %bo1 = add %bo0, %bo0 there is a circle but of size 3, which should not cause this check to trigger.

That said, do we really need it? If so, do we have a test to show that?

5224

I don't think we should do that. The Attributor will fix states without dependences and this seems risky given that the genericValueTraversal could look phi nodes and selects and stuff.

5275

As above.

6103

I'm not even sure we need this. Shouldn't AAValueSimplify call AAValueConstantRange if necessary?
Instead, I would create AAValueConstantRange for calls with integer return type (and add a TODO for load instructions). Here we can come up with metadata which is otherwise not derived.

llvm/test/Transforms/Attributor/lvi-after-jumpthreading.ll

34 ↗

(On Diff #235224)

I know I suggested this test but now I wonder:
The LVI test prints some internal stuff after it runs jump-threading, which we have not integrated yet. We should either add a FIXME to integrate jump-threading, add some way of testing the range analysis e.g., through an array access that we can prove dereferenceable, or remove the test.

Now after writing this I realize we actually optimize the branch away! So we should keep the test but maybe add a pointer access with a FIXME for dereferencebaility anyway somewhere.

[uenoku]

llvm/lib/Transforms/IPO/Attributor.cpp

4906

Will do.

4978

I didn't merge the SCEV and LVI information into initialization because I want to utilize the position where the value is used(=CtxI). I mean,

int abs(int u){
  if(u>=0){
    return u;
  }
  else 
    return -u;
}

In this case, the argument u has a different known range in each uses.
Do you have a better way to handle these kinds of flow- and context-sensitive information?

5215

I agree that it seems we don't this check. I'll remove.

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

4978

We can do both, right? I mean you already call the SCEV in some initialize I think. Let's call both in all initializations with the getCtxI() context. If the context changes I'm fine with calling it again though.

[uenoku]

llvm/lib/Transforms/IPO/Attributor.cpp

4978

I understand. Thanks.

[uenoku]

Address comments.

• add a helper function for floating value updateImpl
• add test
  • range metadata (range.ll @test0-range-check)
  • dereferenceable (dereferenceable-1.ll @fill_range_inbounds/not_inbounds)
• query to AAValueConstantRange when AAValueSimplify gives up
• call LVI and SCEV in initialize as known information
• create AA for integer returned value

[uenoku]

llvm/lib/Transforms/IPO/Attributor.cpp

3970

I'll add a comment here later.

5052

I create a test for metadata(range.ll/test0-range-check.ll)

[jdoerfert]

LGTM. Once we use AAValueSimplify more aggressively in other AAs to get simplified values instead of the ones in the IR, this will be triggered automatically :)

llvm/lib/Transforms/IPO/Attributor.cpp

4985

Nit: The second TODO is outdated.

[uenoku]

Minor update.

[uenoku]

Remove outdated todos.

[davezarzycki]

This breaks top-of-tree from building and testing itself with optimizations and without asserts. Can we revert this for now?

FAIL: LLVM :: Transforms/Attributor/liveness.ll (43906 of 60305)
******************** TEST 'LLVM :: Transforms/Attributor/liveness.ll' FAILED ********************
Script:
--
: 'RUN: at line 2';   /tmp/_update_lc/r/bin/opt -attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=4 -S < /home/dave/s/lp/llvm/test/Transforms/Attributor/liveness.ll | /tmp/_update_lc/r/bin/FileCheck /home/dave/s/lp/llvm/test/Transforms/Attributor/liveness.ll --check-prefixes=CHECK,OLDPM
: 'RUN: at line 3';   /tmp/_update_lc/r/bin/opt -passes=attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=4 -S < /home/dave/s/lp/llvm/test/Transforms/Attributor/liveness.ll | /tmp/_update_lc/r/bin/FileCheck /home/dave/s/lp/llvm/test/Transforms/Attributor/liveness.ll --check-prefixes=CHECK,NEWPM
--
Exit Code: 2

Command Output (stderr):
--
Called function must be a pointer!
  call addrspace(1792) void <badref>(i32* nofree readnone undef) #10
in function useless_arg_almost_sink
LLVM ERROR: Broken function found, compilation aborted!
FileCheck error: '-' is empty.
FileCheck command line:  /tmp/_update_lc/r/bin/FileCheck /home/dave/s/lp/llvm/test/Transforms/Attributor/liveness.ll --check-prefixes=CHECK,OLDPM

[phosek]

We're seeing a slightly different test failure on aarch64-linux-gnu:

FAIL: LLVM :: Transforms/Attributor/liveness.ll (27821 of 35033)
******************** TEST 'LLVM :: Transforms/Attributor/liveness.ll' FAILED ********************
Script:
--
: 'RUN: at line 2';   /b/s/w/ir/k/recipe_cleanup/clange57EIw/llvm_build_dir/bin/opt -attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=4 -S < /b/s/w/ir/k/llvm-project/llvm/test/Transforms/Attributor/liveness.ll | /b/s/w/ir/k/recipe_cleanup/clange57EIw/llvm_build_dir/bin/FileCheck /b/s/w/ir/k/llvm-project/llvm/test/Transforms/Attributor/liveness.ll --check-prefixes=CHECK,OLDPM
: 'RUN: at line 3';   /b/s/w/ir/k/recipe_cleanup/clange57EIw/llvm_build_dir/bin/opt -passes=attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=4 -S < /b/s/w/ir/k/llvm-project/llvm/test/Transforms/Attributor/liveness.ll | /b/s/w/ir/k/recipe_cleanup/clange57EIw/llvm_build_dir/bin/FileCheck /b/s/w/ir/k/llvm-project/llvm/test/Transforms/Attributor/liveness.ll --check-prefixes=CHECK,NEWPM
--
Exit Code: 2

Command Output (stderr):
--
opt: /b/s/w/ir/k/llvm-project/llvm/lib/Transforms/IPO/Attributor.cpp:6475: llvm::ChangeStatus llvm::Attributor::rewriteFunctionSignatures(): Assertion `OldFn->getNumUses() == 0 && "Unexpected leftover uses!"' failed.
FileCheck error: '-' is empty.
FileCheck command line:  /b/s/w/ir/k/recipe_cleanup/clange57EIw/llvm_build_dir/bin/FileCheck /b/s/w/ir/k/llvm-project/llvm/test/Transforms/Attributor/liveness.ll --check-prefixes=CHECK,OLDPM

[uenoku]

I have reverted the commit. Sorry for the mess.

I couldn't reproduce those test failures locally.

[uenoku]

It seems the failure occurs when old pm is used.
I couldn't find what is causing this error.

@jdoerfert Could you take a look at this?

[jdoerfert]

In D71620#1802493, @uenoku wrote:

It seems the failure occurs when old pm is used.
I couldn't find what is causing this error.

@jdoerfert Could you take a look at this?

opt: /b/s/w/ir/k/llvm-project/llvm/lib/Transforms/IPO/Attributor.cpp:6475: llvm::ChangeStatus llvm::Attributor::rewriteFunctionSignatures(): Assertion `OldFn->getNumUses() == 0 && "Unexpected leftover uses!"' failed.

Should have been fixed by rGd2d2fb19f7ea.

Called function must be a pointer! call addrspace(1792) void <badref>(i32* nofree readnone undef) #10

I haven't seen this running the test suite. I'll apply your patch and take a look.

[uenoku]

In D71620#1803466, @jdoerfert wrote:

In D71620#1802493, @uenoku wrote:

It seems the failure occurs when old pm is used.
I couldn't find what is causing this error.

@jdoerfert Could you take a look at this?

opt: /b/s/w/ir/k/llvm-project/llvm/lib/Transforms/IPO/Attributor.cpp:6475: llvm::ChangeStatus llvm::Attributor::rewriteFunctionSignatures(): Assertion `OldFn->getNumUses() == 0 && "Unexpected leftover uses!"' failed.

Should have been fixed by rGd2d2fb19f7ea.

Called function must be a pointer! call addrspace(1792) void <badref>(i32* nofree readnone undef) #10

I haven't seen this running the test suite. I'll apply your patch and take a look.

Thank you.

[jdoerfert]

I'll push some fixes that should address the issues people saw (I hope) but there is at least one bug that the test suite exposed.

For the code below we should not replace the %add with 1. Can you look into that and add the test?

define dso_local i32 @test() {
entry:
  %call = call i32 @rec(i32 0)
  ret i32 %call
}
define internal i32 @rec(i32 %depth) {
entry:
  %call = call i32 @foo(i32 %depth)
  %tobool = icmp ne i32 %call, 0
  br i1 %tobool, label %if.then, label %if.end

if.then:                                          ; preds = %entry
  br label %return

if.end:                                           ; preds = %entry
  %cmp = icmp slt i32 %depth, 10
  br i1 %cmp, label %if.then1, label %if.end3

if.then1:                                         ; preds = %if.end
  %add = add nsw i32 %depth, 1
  %call2 = call i32 @rec(i32 %add)
  br label %if.end3

if.end3:                                          ; preds = %if.then1, %if.end
  br label %return

return:                                           ; preds = %if.end3, %if.then
  %retval.0 = phi i32 [ 0, %if.then ], [ 1, %if.end3 ]
  ret i32 %retval.0
}
declare dso_local i32 @foo(i32)

[uenoku]

Add the test. Sorry for the delay.

For the code below we should not replace the %add with 1. Can you look into that and add the test?

As far as I see it, %add is not replaced.

[jdoerfert]

LGTM.

llvm/include/llvm/Transforms/IPO/Attributor.h

 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/SCCIterator.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/MustExecute.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/IR/CallSite.h"
+#include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/PassManager.h"
 
 namespace llvm {
 
 struct AbstractAttribute;
 struct InformationCache;
 struct AAIsDead;
 
void joinOR(base_t AssumedValue, base_t KnownValue) override {
     Assumed |= AssumedValue;
   }
   void joinAND(base_t AssumedValue, base_t KnownValue) override {
     Known &= KnownValue;
     Assumed &= AssumedValue;
   }
 };
 
+/// State for a integer range.
+struct IntegerRangeState : public AbstractState {
+
+  // Bitwidth of the associated value.
+  uint32_t BitWidth;
+
+  // State representing assumed range, initially set to empty.
+  ConstantRange Assumed;
+
+  // State representing known range, initially set to [-inf, inf].
+  ConstantRange Known;
+
+  IntegerRangeState(uint32_t BitWidth)
+      : BitWidth(BitWidth), Assumed(ConstantRange::getEmpty(BitWidth)),
+        Known(ConstantRange::getFull(BitWidth)) {}
+
+  /// Return associated values' bit width.
+  uint32_t getBitWidth() const { return BitWidth; }
+
+  /// See AbstractState::isValidState()
+  bool isValidState() const override {
+    return BitWidth > 0 && !Assumed.isFullSet();
+  }
+
+  /// See AbstractState::isAtFixpoint()
+  bool isAtFixpoint() const override { return Assumed == Known; }
+
+  /// See AbstractState::indicateOptimisticFixpoint(...)
+  ChangeStatus indicateOptimisticFixpoint() override {
+    Known = Assumed;
+    return ChangeStatus::CHANGED;
+  }
+
+  /// See AbstractState::indicatePessimisticFixpoint(...)
+  ChangeStatus indicatePessimisticFixpoint() override {
+    Assumed = Known;
+    return ChangeStatus::CHANGED;
+  }
+
+  /// Return the known state encoding
+  ConstantRange getKnown() const { return Known; }
+
+  /// Return the assumed state encoding.
+  ConstantRange getAssumed() const { return Assumed; }
+
+  /// Unite assumed range with the passed state.
+  void unionAssumed(const ConstantRange &R) {
+    // Don't loose a known range.
+    Assumed = Assumed.unionWith(R).intersectWith(Known);
+  }
+
+  /// See IntegerRangeState::unionAssumed(..).
+  void unionAssumed(const IntegerRangeState &R) {
+    unionAssumed(R.getAssumed());
+  }
+
+  /// Unite known range with the passed state.
+  void unionKnown(const ConstantRange &R) {
+    // Don't loose a known range.
+    Known = Known.unionWith(R);
+    Assumed = Assumed.unionWith(Known);
+  }
+
+  /// See IntegerRangeState::unionKnown(..).
+  void unionKnown(const IntegerRangeState &R) { unionKnown(R.getKnown()); }
+
+  /// Intersect known range with the passed state.
+  void intersectKnown(const ConstantRange &R) {
+    Known = Known.intersectWith(R);
+  }
+
+  /// See IntegerRangeState::intersectKnown(..).
+  void intersectKnown(const IntegerRangeState &R) {
+    intersectKnown(R.getKnown());
+  }
+
+  /// Equality for IntegerRangeState.
+  bool operator==(const IntegerRangeState &R) const {
+    return getAssumed() == R.getAssumed() && getKnown() == R.getKnown();
+  }
+
+  /// "Clamp" this state with \p R. The result is subtype dependent but it is
+  /// intended that only information assumed in both states will be assumed in
+  /// this one afterwards.
+  void operator^=(const IntegerRangeState &R) {
+    // NOTE: `^=` operator seems like `intersect` but in this case, we need to
+    // take `union`.
+    unionAssumed(R);
+  }
+
+  void operator&=(const IntegerRangeState &R) {
+    // NOTE: `&=` operator seems like `intersect` but in this case, we need to
+    // take `union`.
+    unionKnown(R);
+    unionAssumed(R);
+  }
+};
 /// Helper struct necessary as the modular build fails if the virtual method
 /// IRAttribute::manifest is defined in the Attributor.cpp.
 struct IRAttributeManifest {
   static ChangeStatus manifestAttrs(Attributor &A, const IRPosition &IRP,
                                     const ArrayRef<Attribute> &DeducedAttrs);
 };
 
 /// Helper to tie a abstract state implementation to an abstract attribute.

 /// Forward declarations of output streams for debug purposes.
 ///
 ///{
 raw_ostream &operator<<(raw_ostream &OS, const AbstractAttribute &AA);
 raw_ostream &operator<<(raw_ostream &OS, ChangeStatus S);
 raw_ostream &operator<<(raw_ostream &OS, IRPosition::Kind);
 raw_ostream &operator<<(raw_ostream &OS, const IRPosition &);
 raw_ostream &operator<<(raw_ostream &OS, const AbstractState &State);
+
 template <typename base_ty, base_ty BestState, base_ty WorstState>
 raw_ostream &
 operator<<(raw_ostream &OS,
            const IntegerStateBase<base_ty, BestState, WorstState> &State);
+raw_ostream &operator<<(raw_ostream &OS, const IntegerRangeState &State);
 ///}
 
 struct AttributorPass : public PassInfoMixin<AttributorPass> {
   PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
 };
 
 Pass *createAttributorLegacyPass();
 
struct AAMemoryBehavior
   /// Create an abstract attribute view for the position \p IRP.
   static AAMemoryBehavior &createForPosition(const IRPosition &IRP,
                                              Attributor &A);
 
   /// Unique ID (due to the unique address)
   static const char ID;
 };
 
+/// An abstract interface for range value analysis.
+struct AAValueConstantRange : public IntegerRangeState,
+                              public AbstractAttribute,
+                              public IRPosition {
+  AAValueConstantRange(const IRPosition &IRP)
+      : IntegerRangeState(
+            IRP.getAssociatedValue().getType()->getIntegerBitWidth()),
+        IRPosition(IRP) {}
+
+  /// Return an IR position, see struct IRPosition.
+  const IRPosition &getIRPosition() const override { return *this; }
+
+  /// See AbstractAttribute::getState(...).
+  IntegerRangeState &getState() override { return *this; }
+  const AbstractState &getState() const override { return *this; }
+
+  /// Create an abstract attribute view for the position \p IRP.
+  static AAValueConstantRange &createForPosition(const IRPosition &IRP,
+                                                 Attributor &A);
+
+  /// Return an assumed range for value in \p U.
+  virtual ConstantRange getAssumedConstantRange(Use *U = nullptr) const = 0;
+
+  /// Return an known range for value in \p U.
+  virtual ConstantRange getKnownConstantRange(Use *U = nullptr) const = 0;
+
+  /// Unique ID (due to the unique address)
+  static const char ID;
+};
+
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H

llvm/lib/Transforms/IPO/Attributor.cpp

 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/EHPersonalities.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/Loads.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
+#include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Support/CommandLine.h"

 PIPE_OPERATOR(AADereferenceable)
 PIPE_OPERATOR(AAAlign)
 PIPE_OPERATOR(AANoCapture)
 PIPE_OPERATOR(AAValueSimplify)
 PIPE_OPERATOR(AANoFree)
 PIPE_OPERATOR(AAHeapToStack)
 PIPE_OPERATOR(AAReachability)
 PIPE_OPERATOR(AAMemoryBehavior)
+PIPE_OPERATOR(AAValueConstantRange)
 
 #undef PIPE_OPERATOR
 } // namespace llvm
 
 // TODO: Determine a good default value.
 //
 // In the LLVM-TS and SPEC2006, 32 seems to not induce compile time overheads
 // (when run with the first 5 abstract attributes). The results also indicate
for (const Instruction *DeadEndI : KnownDeadEnds) {
             if (AANoUnw.isAssumedNoUnwind()) {
               LLVM_DEBUG(dbgs()
                          << "[AAIsDead] Replace invoke with call inst\n");
               CallInst *CI = createCallMatchingInvoke(II);
               CI->insertBefore(II);
               CI->takeName(II);
               replaceAllInstructionUsesWith(*II, *CI);
 
-              // If this is a nounwind + mayreturn invoke we only remove the unwind edge.
-              // This is done by moving the invoke into a new and dead block and connecting
-              // the normal destination of the invoke with a branch that follows the call
-              // replacement we created above.
+              // If this is a nounwind + mayreturn invoke we only remove the
+              // unwind edge. This is done by moving the invoke into a new and
+              // dead block and connecting the normal destination of the invoke
+              // with a branch that follows the call replacement we created
+              // above.
               if (MayReturn) {
-                BasicBlock *NewDeadBB = SplitBlock(BB, II, nullptr, nullptr, nullptr, ".i2c");
+                BasicBlock *NewDeadBB =
+                    SplitBlock(BB, II, nullptr, nullptr, nullptr, ".i2c");
                 assert(isa<BranchInst>(BB->getTerminator()) &&
                        BB->getTerminator()->getNumSuccessors() == 1 &&
                        BB->getTerminator()->getSuccessor(0) == NewDeadBB);
                 new UnreachableInst(I->getContext(), NewDeadBB);
                 BB->getTerminator()->setOperand(0, NormalDestBB);
                 A.deleteAfterManifest(*II);
                 continue;
               }

 
 static Optional<ConstantInt *>
 getAssumedConstant(Attributor &A, const Value &V, AbstractAttribute &AA,
                    bool &UsedAssumedInformation) {
   const auto &ValueSimplifyAA =
       A.getAAFor<AAValueSimplify>(AA, IRPosition::value(V));
   Optional<Value *> SimplifiedV = ValueSimplifyAA.getAssumedSimplifiedValue(A);
   UsedAssumedInformation |= !ValueSimplifyAA.isKnown();
+
   if (!SimplifiedV.hasValue())
     return llvm::None;
   if (isa_and_nonnull<UndefValue>(SimplifiedV.getValue()))
     return llvm::None;
-  return dyn_cast_or_null<ConstantInt>(SimplifiedV.getValue());
+  if (auto *C = dyn_cast<ConstantInt>(SimplifiedV.getValue()))
+    return C;
+
+  if (V.getType()->isIntegerTy()) {
+    const auto &ValueConstantRangeAA =
+        A.getAAFor<AAValueConstantRange>(AA, IRPosition::value(V));
+
+    ConstantRange RangeV = ValueConstantRangeAA.getAssumedConstantRange();
+    if (auto *C = RangeV.getSingleElement())
+      return cast<ConstantInt>(ConstantInt::get(V.getType(), *C));
+    else if (RangeV.isEmptySet())
+      return llvm::None;
+  }
+
+  return nullptr;
 }
 
 static bool
 identifyAliveSuccessors(Attributor &A, const BranchInst &BI,
                         AbstractAttribute &AA,
                         SmallVectorImpl<const Instruction *> &AliveSuccessors) {
   bool UsedAssumedInformation = false;
   if (BI.getNumSuccessors() == 1) {
static bool checkAndUpdate(Attributor &A, const AbstractAttribute &QueryingAA,
     LLVM_DEBUG(dbgs() << "[Attributor][ValueSimplify] " << QueryingValue
                       << " is assumed to be "
                       << QueryingValueSimplifiedUnwrapped << "\n");
 
     AccumulatedSimplifiedValue = QueryingValueSimplified;
     return true;
   }
 
   /// See AbstractAttribute::manifest(...).
   ChangeStatus manifest(Attributor &A) override {
     ChangeStatus Changed = ChangeStatus::UNCHANGED;
 
     if (!SimplifiedAssociatedValue.hasValue() ||
         !SimplifiedAssociatedValue.getValue())
       return Changed;
 
     if (auto *C = dyn_cast<Constant>(SimplifiedAssociatedValue.getValue())) {
void AAMemoryBehaviorFloating::analyzeUseIn(Attributor &A, const Use *U,
 
   // Generally, look at the "may-properties" and adjust the assumed state if we
   // did not trigger special handling before.
   if (UserI->mayReadFromMemory())
     removeAssumedBits(NO_READS);
   if (UserI->mayWriteToMemory())
     removeAssumedBits(NO_WRITES);
 }
+/// ------------------ Value Constant Range Attribute -------------------------
+
+struct AAValueConstantRangeImpl : AAValueConstantRange {
+  using StateType = IntegerRangeState;
+  AAValueConstantRangeImpl(const IRPosition &IRP) : AAValueConstantRange(IRP) {}
+
+  /// See AbstractAttribute::getAsStr().
+  const std::string getAsStr() const override {
+    std::string Str;
+    llvm::raw_string_ostream OS(Str);
+    OS << "range(" << getBitWidth() << ")<";
+    getKnownConstantRange().print(OS);
+    OS << " / ";
+    getAssumedConstantRange().print(OS);
+    OS << ">";
+    return OS.str();
+  }
+
+  /// See AAValueConstantRange::getKnownConstantRange(..).
+  ConstantRange getKnownConstantRange(Use *U = nullptr) const override {
+    // TODO: `U` is passed to make context-sensitivity query but it is not used
+    // now.
+    return getKnown();
+  }
+
+  /// See AAValueConstantRange::getAssumedConstantRange(..).
+  ConstantRange getAssumedConstantRange(Use *U = nullptr) const override {
+    // TODO: `U` is passed to make context-sensitivity query but it is not used
+    // now.
+    return getAssumed();
+  }
+
+  /// Helper function to create MDNode for range metadata.
+  static MDNode *getMDNodeForConstantRange(Type *Ty, LLVMContext &Ctx,
+                                           ConstantRange AssumedConstantRange) {
+    Metadata *LowAndHigh[] = {ConstantAsMetadata::get(ConstantInt::get(
+                                  Ty, AssumedConstantRange.getLower())),
+                              ConstantAsMetadata::get(ConstantInt::get(
+                                  Ty, AssumedConstantRange.getUpper()))};
+    return MDNode::get(Ctx, LowAndHigh);
+  }
+
+  /// Return true if \p Assumed is included in \p KnownRanges.
+  static bool isBetterRange(ConstantRange Assumed, MDNode *KnownRanges) {
+
+    if (Assumed.isFullSet())
+      return false;
+
+    if (!KnownRanges)
+      return true;
+
+    // If multiple ranges are annotated in IR, we give up to annotate assumed
+    // range for now.
+
+    // FIMXE:  If there exists a known range which containts assumed range, we
+    // can say assumed range is better.
+    if (KnownRanges->getNumOperands() > 2)
+      return false;
+
+    ConstantInt *Lower =
+        mdconst::extract<ConstantInt>(KnownRanges->getOperand(0));
+    ConstantInt *Upper =
+        mdconst::extract<ConstantInt>(KnownRanges->getOperand(1));
+
+    ConstantRange Known(Lower->getValue(), Upper->getValue());
+    return Known.contains(Assumed) && Known != Assumed;
+  }
+
+  /// Helper function to set range metadata.
+  static bool setIfBetterRange(Instruction *I,
+                               ConstantRange AssumedConstantRange) {
+    auto *OldRangeMD = I->getMetadata(LLVMContext::MD_range);
+    if (isBetterRange(AssumedConstantRange, OldRangeMD)) {
+      if (!AssumedConstantRange.isEmptySet())
+        I->setMetadata(LLVMContext::MD_range,
+                       getMDNodeForConstantRange(I->getType(), I->getContext(),
+                                                 AssumedConstantRange));
+      else {
+        // TODO: Replace value to undef if range is empty(=undef).
+      }
+      return true;
+    }
+    return false;
+  }
+
+  /// See AbstractAttribute::manifest()
+  ChangeStatus manifest(Attributor &A) override {
+    ChangeStatus Changed = ChangeStatus::UNCHANGED;
+    ConstantRange AssumedConstantRange = getAssumedConstantRange();
+    if (AssumedConstantRange.isFullSet())
+      return ChangeStatus::UNCHANGED;
+
+    auto &V = getAssociatedValue();
+    Constant *C = nullptr;
+    if (AssumedConstantRange.isEmptySet())
+      C = UndefValue::get(V.getType());
+
+    if (AssumedConstantRange.isSingleElement())
+      C = cast<ConstantInt>(ConstantInt::get(
+          V.getType(), *AssumedConstantRange.getSingleElement()));
+
+    if (C) {
+      // We can replace the AssociatedValue with the constant.
+      if (!V.user_empty() && &V != C && V.getType() == C->getType()) {
+        LLVM_DEBUG(dbgs() << "[Attributor][ValueConstantRange] " << V << " -> "
+                          << *C << "\n");
+        replaceAllInstructionUsesWith(V, *C);
+        Changed = ChangeStatus::CHANGED;
+      }
+    } else {
+      if (Instruction *I = dyn_cast<Instruction>(&V))
+        if (isa<CallInst>(I) || isa<LoadInst>(I))
+          if (setIfBetterRange(I, AssumedConstantRange))
+            Changed = ChangeStatus::CHANGED;
+    }
+
+    return Changed;
+  }
+};
+
+struct AAValueConstantRangeArgument final : public AAValueConstantRangeImpl {
+
+  AAValueConstantRangeArgument(const IRPosition &IRP)
+      : AAValueConstantRangeImpl(IRP) {}
+
+  /// See AbstractAttribute::updateImpl(...).
+  ChangeStatus updateImpl(Attributor &A) override {
+    // TODO: Use AAArgumentFromCallSiteArguments
+
+    IntegerRangeState S(getBitWidth());
+    clampCallSiteArgumentStates<AAValueConstantRange, IntegerRangeState>(
+        A, *this, S);
+
+    // TODO: If we know we visited all incoming values, thus no are assumed
+    // dead, we can take the known information from the state T.
+    return clampStateAndIndicateChange<IntegerRangeState>(this->getState(), S);
+  }
+
+  /// See AbstractAttribute::trackStatistics()
+  void trackStatistics() const override {
+    STATS_DECLTRACK_ARG_ATTR(value_range)
+  }
+};
+
+struct AAValueConstantRangeReturned : AAValueConstantRangeImpl {
+  AAValueConstantRangeReturned(const IRPosition &IRP)
+      : AAValueConstantRangeImpl(IRP) {}
+
+  /// See AbstractAttribute::updateImpl(...).
+  ChangeStatus updateImpl(Attributor &A) override {
+    // TODO: Use AAReturnedFromReturnedValues
+
+    // TODO: If we know we visited all returned values, thus no are assumed
+    // dead, we can take the known information from the state T.
+
+    IntegerRangeState S(getBitWidth());
+
+    clampReturnedValueStates<AAValueConstantRange, IntegerRangeState>(A, *this,
+                                                                      S);
+    return clampStateAndIndicateChange<StateType>(this->getState(), S);
+  }
+
+  /// See AbstractAttribute::trackStatistics()
+  void trackStatistics() const override {
+    STATS_DECLTRACK_FNRET_ATTR(value_range)
+  }
+};
+
+struct AAValueConstantRangeFloating : AAValueConstantRangeImpl {
+  AAValueConstantRangeFloating(const IRPosition &IRP)
+      : AAValueConstantRangeImpl(IRP) {}
+
+  /// See AbstractAttribute::initialize(...).
+  void initialize(Attributor &A) override {
+    Value &V = getAssociatedValue();
+
+    if (auto *C = dyn_cast<ConstantInt>(&V)) {
+      unionAssumed(ConstantRange(C->getValue()));
+      indicateOptimisticFixpoint();
+      return;
+    }
+
+    if (isa<UndefValue>(&V)) {
+      indicateOptimisticFixpoint();
+      return;
+    }
+
+    // If it is a load instruction with range metadata, use the metadata.
+    if (LoadInst *LI = dyn_cast<LoadInst>(&V))
+      if (auto *RangeMD = LI->getMetadata(LLVMContext::MD_range))
+        intersectKnown(getConstantRangeFromMetadata(*RangeMD));
+
+    LLVM_DEBUG(dbgs() << "[AAConstantRangeFloating] " << V
+                      << " is initialized to " << getState());
+  }
 
+  /// See AbstractAttribute::updateImpl(...).
+  ChangeStatus updateImpl(Attributor &A) override {
+    auto VisitValueCB = [&](Value &V, IntegerRangeState &T,
+                            bool Stripped) -> bool {
+      if (Instruction *I = dyn_cast<Instruction>(&V)) {
+
+        if (auto *BinOp = dyn_cast<BinaryOperator>(I)) {
+          Value *LHS = BinOp->getOperand(0);
+          Value *RHS = BinOp->getOperand(1);
+
+          if (!LHS->getType()->isIntegerTy() || !RHS->getType()->isIntegerTy())
+            return false;
+
+          auto &LHSAA =
+              A.getAAFor<AAValueConstantRange>(*this, IRPosition::value(*LHS));
+          auto LHSAARange = LHSAA.getAssumedConstantRange();
+
+          auto &RHSAA =
+              A.getAAFor<AAValueConstantRange>(*this, IRPosition::value(*RHS));
+          auto RHSAARange = RHSAA.getAssumedConstantRange();
+
+          // Use SCEV when the value is phi and has loop.
+          //
+          // TODO: Somehow make SCEV use Attributor assumption.
+          //       We may be able to bound a variable range via IPO.
+
+          if (this == &LHSAA || this == &RHSAA) {
+            InformationCache &InfoCache = A.getInfoCache();
+            Function &F = *getAnchorScope();
+            Value *AssociatedV = &getAssociatedValue();
+            ScalarEvolution *SE =
+                InfoCache.getAnalysisResultForFunction<ScalarEvolutionAnalysis>(
+                    F);
+            LoopInfo *LI =
+                InfoCache.getAnalysisResultForFunction<LoopAnalysis>(F);
+            if (SE && LI)
+              if (Instruction *I = dyn_cast<Instruction>(AssociatedV)) {
+                // Query the range to SCEV from an inner loop to an outer loop.
+                // TODO: Make sure that the logic is correct.
+
+                for (Loop *L = LI->getLoopFor(I->getParent()); L;
+                     L = L->getParentLoop())
+                  if (const SCEV *S =
+                          SE->getSCEVAtScope(AssociatedV, L->getParentLoop())) {
+                    LLVM_DEBUG(dbgs() << *AssociatedV << "/" << *L << "/" << *S
+                                      << "\n");
+                    intersectKnown(SE->getUnsignedRange(S));
+                  }
+              }
+            T.indicatePessimisticFixpoint();
+            return false;
+          }
+
+          auto AssumedRange = LHSAARange.binaryOp(
+              Instruction::BinaryOps(I->getOpcode()), RHSAARange);
+
+          T.unionAssumed(AssumedRange);
+
+          // If both lhs and rhs are fixed, we can say the current one is fixed.
+          if (LHSAA.isAtFixpoint() && RHSAA.isAtFixpoint() && !Stripped)
+            T.indicateOptimisticFixpoint();
+
+          return true;
+        } else if (auto *CmpI = dyn_cast<CmpInst>(I)) {
+          Value *LHS = CmpI->getOperand(0);
+          Value *RHS = CmpI->getOperand(1);
+
+          // Give up with other than integers.
+          if (!LHS->getType()->isIntegerTy() || !RHS->getType()->isIntegerTy())
+            return false;
+
+          auto &LHSAA =
+              A.getAAFor<AAValueConstantRange>(*this, IRPosition::value(*LHS));
+          auto &RHSAA =
+              A.getAAFor<AAValueConstantRange>(*this, IRPosition::value(*RHS));
+
+          auto LHSAARange = LHSAA.getAssumedConstantRange();
+          auto RHSAARange = RHSAA.getAssumedConstantRange();
+
+          // If one of them is empty set, we can't decide.
+          if (LHSAARange.isEmptySet() || RHSAARange.isEmptySet())
+            return true;
+
+          bool MustTrue = false, MustFalse = false;
+
+          // TODO: Make sure that the logic below is correct.
+          auto AllowedRegion = ConstantRange::makeAllowedICmpRegion(
+              CmpI->getPredicate(), RHSAARange);
+
+          auto SatisfyingRegion = ConstantRange::makeSatisfyingICmpRegion(
+              CmpI->getPredicate(), RHSAARange);
+
+          if (AllowedRegion.intersectWith(LHSAARange).isEmptySet())
+            MustFalse = true;
+
+          if (SatisfyingRegion.contains(LHSAARange))
+            MustTrue = true;
+
+          assert((!MustTrue || !MustFalse) &&
+                 "Either MustTrue or MustFalse should be false!");
+
+          if (MustTrue)
+            T.unionAssumed(ConstantRange(APInt(/* numBits */ 1, /* val */ 1)));
+          else if (MustFalse)
+            T.unionAssumed(ConstantRange(APInt(/* numBits */ 1, /* val */ 0)));
+          else
+            T.unionAssumed(
+                ConstantRange(/* BitWidth */ 1, /* isFullSet */ true));
+
+          LLVM_DEBUG(dbgs() << "[AAValueConstantRange] " << *CmpI << " "
+                            << LHSAA << " " << RHSAA << "\n");
+
+          // If both lhs and rhs are fixed, we can say the current one is fixed.
+          if (LHSAA.isAtFixpoint() && RHSAA.isAtFixpoint() && !Stripped)
+            T.indicateOptimisticFixpoint();
+
+          return true;
+        } else {
+          // TODO: Add other instructions
+          T.indicatePessimisticFixpoint();
+          return false;
+        }
+      } else {
+        // If the value is not instruction, we query AA to Attributor.
+
+        const auto &AA =
+            A.getAAFor<AAValueConstantRange>(*this, IRPosition::value(V));
+        const IntegerRangeState &NS =
+            static_cast<const IntegerRangeState &>(AA.getState());
+        T ^= NS;
+        return T.isValidState();
+      }
+    };
+
+    IntegerRangeState T(getBitWidth());
+
+    if (!genericValueTraversal<AAValueConstantRange, IntegerRangeState>(
+            A, getIRPosition(), *this, T, VisitValueCB))
+      return indicatePessimisticFixpoint();
+
+    return clampStateAndIndicateChange(getState(), T);
+  }
+
+  /// See AbstractAttribute::trackStatistics()
+  void trackStatistics() const override {
+    STATS_DECLTRACK_FLOATING_ATTR(value_range)
+  }
+};
+
+struct AAValueConstantRangeFunction : AAValueConstantRangeImpl {
+  AAValueConstantRangeFunction(const IRPosition &IRP)
+      : AAValueConstantRangeImpl(IRP) {}
+
+  /// See AbstractAttribute::initialize(...).
+  ChangeStatus updateImpl(Attributor &A) override {
+    llvm_unreachable("AAValueConstantRange(Function|CallSite)::updateImpl will "
+                     "not be called");
+  }
+
+  /// See AbstractAttribute::trackStatistics()
+  void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(value_range) }
+};
+
+struct AAValueConstantRangeCallSite : AAValueConstantRangeFunction {
+  AAValueConstantRangeCallSite(const IRPosition &IRP)
+      : AAValueConstantRangeFunction(IRP) {}
+
+  /// See AbstractAttribute::trackStatistics()
+  void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(value_range) }
+};
+
+struct AAValueConstantRangeCallSiteReturned : AAValueConstantRangeReturned {
+  AAValueConstantRangeCallSiteReturned(const IRPosition &IRP)
+      : AAValueConstantRangeReturned(IRP) {}
+
+  /// See AbstractAttribute::initialize(...).
+  void initialize(Attributor &A) override {
+    // If it is a load instruction with range metadata, use the metadata.
+    if (CallInst *CI = dyn_cast<CallInst>(&getAssociatedValue()))
+      if (auto *RangeMD = CI->getMetadata(LLVMContext::MD_range))
+        intersectKnown(getConstantRangeFromMetadata(*RangeMD));
+  }
+
+  /// See AbstractAttribute::trackStatistics()
+  void trackStatistics() const override {
+    STATS_DECLTRACK_CSRET_ATTR(value_range)
+  }
+};
+struct AAValueConstantRangeCallSiteArgument : AAValueConstantRangeFloating {
+  AAValueConstantRangeCallSiteArgument(const IRPosition &IRP)
+      : AAValueConstantRangeFloating(IRP) {}
+
+  /// See AbstractAttribute::trackStatistics()
+  void trackStatistics() const override {
+    STATS_DECLTRACK_CSARG_ATTR(value_range)
+  }
+};
 /// ----------------------------------------------------------------------------
 ///                               Attributor
 /// ----------------------------------------------------------------------------
 
 bool Attributor::isAssumedDead(const AbstractAttribute &AA,
                                const AAIsDead *LivenessAA) {
   const Instruction *CtxI = AA.getIRPosition().getCtxI();
   if (!CtxI)
default:
       assert((!ImmutableCallSite(&I)) && (!isa<CallBase>(&I)) &&
              "New call site/base instruction type needs to be known int the "
              "Attributor.");
       break;
     case Instruction::Load:
       // The alignment of a pointer is interesting for loads.
     case Instruction::Store:
       // The alignment of a pointer is interesting for stores.
+    case Instruction::ICmp:
     case Instruction::Call:
     case Instruction::CallBr:
     case Instruction::Invoke:
     case Instruction::CleanupRet:
     case Instruction::CatchSwitch:
     case Instruction::Resume:
     case Instruction::Ret:
       IsInterestingOpcode = true;
else
           IRPosition::value(*cast<StoreInst>(I).getPointerOperand()));
     return true;
   };
   Success = checkForAllInstructionsImpl(
       OpcodeInstMap, LoadStorePred, nullptr, AnyDead,
       {(unsigned)Instruction::Load, (unsigned)Instruction::Store});
   (void)Success;
   assert(Success && !AnyDead && "Expected the check call to be successful!");
+
+  auto CmpInstPred = [&](Instruction &I) -> bool {
+    getOrCreateAAFor<AAValueConstantRange>(IRPosition::value(*cast<Value>(&I)));
+    return true;
+  };
+
+  Success = checkForAllInstructionsImpl(OpcodeInstMap, CmpInstPred, nullptr,
+                                        AnyDead, {(unsigned)Instruction::ICmp});
+  (void)Success;
+  assert(Success && !AnyDead && "Expected the check call to be successful!");
 }
 
 /// Helpers to ease debugging through output streams and print calls.
 ///
 ///{
 raw_ostream &llvm::operator<<(raw_ostream &OS, ChangeStatus S) {
   return OS << (S == ChangeStatus::CHANGED ? "changed" : "unchanged");
 }

 
 raw_ostream &llvm::operator<<(raw_ostream &OS, const IRPosition &Pos) {
   const Value &AV = Pos.getAssociatedValue();
   return OS << "{" << Pos.getPositionKind() << ":" << AV.getName() << " ["
             << Pos.getAnchorValue().getName() << "@" << Pos.getArgNo() << "]}";
 }
 
 template <typename base_ty, base_ty BestState, base_ty WorstState>
-raw_ostream &llvm::
-operator<<(raw_ostream &OS,
+raw_ostream &
+llvm::operator<<(raw_ostream &OS,
                  const IntegerStateBase<base_ty, BestState, WorstState> &S) {
   return OS << "(" << S.getKnown() << "-" << S.getAssumed() << ")"
             << static_cast<const AbstractState &>(S);
 }
 
+raw_ostream &llvm::operator<<(raw_ostream &OS, const IntegerRangeState &S) {
+  OS << "range-state(" << S.getBitWidth() << ")<";
+  S.getKnown().print(OS);
+  OS << " / ";
+  S.getAssumed().print(OS);
+  OS << "> && ";
+
+  return OS << (!S.isValidState() ? "top"
+                                  : (S.isAtFixpoint() ? "fix" : "notfixed"))
+            << "\n";
+}
 raw_ostream &llvm::operator<<(raw_ostream &OS, const AbstractState &S) {
   return OS << (!S.isValidState() ? "top" : (S.isAtFixpoint() ? "fix" : ""));
 }
 
 raw_ostream &llvm::operator<<(raw_ostream &OS, const AbstractAttribute &AA) {
   AA.print(OS);
   return OS;
 }

 const char AANoReturn::ID = 0;
 const char AAIsDead::ID = 0;
 const char AADereferenceable::ID = 0;
 const char AAAlign::ID = 0;
 const char AANoCapture::ID = 0;
 const char AAValueSimplify::ID = 0;
 const char AAHeapToStack::ID = 0;
 const char AAMemoryBehavior::ID = 0;
+const char AAValueConstantRange::ID = 0;
 
 // Macro magic to create the static generator function for attributes that
 // follow the naming scheme.
 
 #define SWITCH_PK_INV(CLASS, PK, POS_NAME)                                     \
   case IRPosition::PK:                                                         \
     llvm_unreachable("Cannot create " #CLASS " for a " POS_NAME " position!");
 

 CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoReturn)
 CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAReturnedValues)
 
 CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANonNull)
 CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoAlias)
 CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AADereferenceable)
 CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAAlign)
 CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoCapture)
+CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAValueConstantRange)
 
 CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAValueSimplify)
 CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAIsDead)
 CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoFree)
 
 CREATE_FUNCTION_ONLY_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAHeapToStack)
 CREATE_FUNCTION_ONLY_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAReachability)
 

llvm/test/Transforms/Attributor/IPConstantProp/solve-after-each-resolving-undefs-for-function.ll

 define internal i32 @test1(i1 %c) {
 ; CHECK-LABEL: define {{[^@]+}}@test1
 ; CHECK-SAME: (i1 [[C:%.*]])
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[IF_THEN:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    [[CALL:%.*]] = call i32 @testf(i1 [[C]])
 ; CHECK-NEXT:    [[RES:%.*]] = icmp eq i32 10, 10
-; CHECK-NEXT:    br i1 [[RES]], label [[RET1:%.*]], label [[RET2:%.*]]
+; CHECK-NEXT:    br i1 true, label [[RET1:%.*]], label [[RET2:%.*]]
 ; CHECK:       ret1:
 ; CHECK-NEXT:    ret i32 99
 ; CHECK:       ret2:
-; CHECK-NEXT:    ret i32 0
+; CHECK-NEXT:    unreachable
 ;
 entry:
   br label %if.then
 
 if.then:                                          ; preds = %entry, %if.then
   %call = call i32 @testf(i1 %c)
   %res = icmp eq i32 %call, 10
   br i1 %res, label %ret1, label %ret2
 
 ret1:                                           ; preds = %if.then, %entry
   ret i32 99
 
 ret2:                                           ; preds = %if.then, %entry
   ret i32 0
 }
 
 define i32 @main(i1 %c) {
 ; CHECK-LABEL: define {{[^@]+}}@main
 ; CHECK-SAME: (i1 [[C:%.*]])
 ; CHECK-NEXT:    [[RES:%.*]] = call i32 @test1(i1 [[C]])
-; CHECK-NEXT:    ret i32 [[RES]]
+; CHECK-NEXT:    ret i32 99
 ;
   %res = call i32 @test1(i1 %c)
   ret i32 %res
 }

llvm/test/Transforms/Attributor/range.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -passes=attributor -attributor-disable=false -S < %s | FileCheck %s
+
+define i32 @test0(i32* %p) {
+; CHECK-LABEL: define {{[^@]+}}@test0
+; CHECK-SAME: (i32* nocapture nofree nonnull readonly dereferenceable(4) [[P:%.*]]) #0
+; CHECK-NEXT:    [[A:%.*]] = load i32, i32* [[P:%.*]], !range !0
+; CHECK-NEXT:    ret i32 [[A]]
+;
+  %a = load i32, i32* %p, !range !0
+  ret i32 %a
+}
+declare void @use3(i1, i1, i1)
+; TEST0 icmp test
+; TODO : Add test for unsigned
+define void @test0-icmp-check(i32* %p){
+; CHECK-LABEL: define {{[^@]+}}@test0-icmp-check
+; CHECK-SAME: (i32* nocapture nofree readonly [[P:%.*]])
+; CHECK-NEXT:    [[RET:%.*]] = tail call i32 @test0(i32* nocapture nofree readonly [[P:%.*]]) #0, !range !0
+; CHECK-NEXT:    [[CMP_SLT_1:%.*]] = icmp slt i32 [[RET]], 10
+; CHECK-NEXT:    [[CMP_SLT_2:%.*]] = icmp slt i32 [[RET]], 9
+; CHECK-NEXT:    [[CMP_SLT_3:%.*]] = icmp slt i32 [[RET]], 8
+; CHECK-NEXT:    [[CMP_SLT_4:%.*]] = icmp slt i32 [[RET]], 1
+; CHECK-NEXT:    [[CMP_SLT_5:%.*]] = icmp slt i32 [[RET]], 0
+; CHECK-NEXT:    [[CMP_SLT_6:%.*]] = icmp slt i32 [[RET]], -1
+; CHECK-NEXT:    tail call void @use3(i1 true, i1 [[CMP_SLT_2]], i1 [[CMP_SLT_3]])
+; CHECK-NEXT:    tail call void @use3(i1 [[CMP_SLT_4]], i1 false, i1 false)
+; CHECK-NEXT:    [[CMP_SGT_1:%.*]] = icmp sgt i32 [[RET]], 10
+; CHECK-NEXT:    [[CMP_SGT_2:%.*]] = icmp sgt i32 [[RET]], 9
+; CHECK-NEXT:    [[CMP_SGT_3:%.*]] = icmp sgt i32 [[RET]], 8
+; CHECK-NEXT:    [[CMP_SGT_4:%.*]] = icmp sgt i32 [[RET]], 1
+; CHECK-NEXT:    [[CMP_SGT_5:%.*]] = icmp sgt i32 [[RET]], 0
+; CHECK-NEXT:    [[CMP_SGT_6:%.*]] = icmp sgt i32 [[RET]], -1
+; CHECK-NEXT:    tail call void @use3(i1 false, i1 false, i1 [[CMP_SGT_3]])
+; CHECK-NEXT:    tail call void @use3(i1 [[CMP_SGT_4]], i1 [[CMP_SGT_5]], i1 true)
+; CHECK-NEXT:    [[CMP_LTE_1:%.*]] = icmp sle i32 [[RET]], 10
+; CHECK-NEXT:    [[CMP_LTE_2:%.*]] = icmp sle i32 [[RET]], 9
+; CHECK-NEXT:    [[CMP_LTE_3:%.*]] = icmp sle i32 [[RET]], 8
+; CHECK-NEXT:    [[CMP_LTE_4:%.*]] = icmp sle i32 [[RET]], 1
+; CHECK-NEXT:    [[CMP_LTE_5:%.*]] = icmp sle i32 [[RET]], 0
+; CHECK-NEXT:    [[CMP_LTE_6:%.*]] = icmp sle i32 [[RET]], -1
+; CHECK-NEXT:    tail call void @use3(i1 true, i1 true, i1 [[CMP_LTE_3]])
+; CHECK-NEXT:    tail call void @use3(i1 [[CMP_LTE_4]], i1 [[CMP_LTE_5]], i1 false)
+; CHECK-NEXT:    [[CMP_GTE_1:%.*]] = icmp sge i32 [[RET]], 10
+; CHECK-NEXT:    [[CMP_GTE_2:%.*]] = icmp sge i32 [[RET]], 9
+; CHECK-NEXT:    [[CMP_GTE_3:%.*]] = icmp sge i32 [[RET]], 8
+; CHECK-NEXT:    [[CMP_GTE_4:%.*]] = icmp sge i32 [[RET]], 1
+; CHECK-NEXT:    [[CMP_GTE_5:%.*]] = icmp sge i32 [[RET]], 0
+; CHECK-NEXT:    [[CMP_GTE_6:%.*]] = icmp sge i32 [[RET]], -1
+; CHECK-NEXT:    tail call void @use3(i1 false, i1 [[CMP_GTE_2]], i1 [[CMP_GTE_3]])
+; CHECK-NEXT:    tail call void @use3(i1 [[CMP_GTE_4]], i1 true, i1 true)
+; CHECK-NEXT:    [[CMP_EQ_1:%.*]] = icmp eq i32 [[RET]], 10
+; CHECK-NEXT:    [[CMP_EQ_2:%.*]] = icmp eq i32 [[RET]], 9
+; CHECK-NEXT:    [[CMP_EQ_3:%.*]] = icmp eq i32 [[RET]], 8
+; CHECK-NEXT:    [[CMP_EQ_4:%.*]] = icmp eq i32 [[RET]], 1
+; CHECK-NEXT:    [[CMP_EQ_5:%.*]] = icmp eq i32 [[RET]], 0
+; CHECK-NEXT:    [[CMP_EQ_6:%.*]] = icmp eq i32 [[RET]], -1
+; CHECK-NEXT:    tail call void @use3(i1 false, i1 [[CMP_EQ_2]], i1 [[CMP_EQ_3]])
+; CHECK-NEXT:    tail call void @use3(i1 [[CMP_EQ_4]], i1 [[CMP_EQ_5]], i1 false)
+; CHECK-NEXT:    [[CMP_NE_1:%.*]] = icmp ne i32 [[RET]], 10
+; CHECK-NEXT:    [[CMP_NE_2:%.*]] = icmp ne i32 [[RET]], 9
+; CHECK-NEXT:    [[CMP_NE_3:%.*]] = icmp ne i32 [[RET]], 8
+; CHECK-NEXT:    [[CMP_NE_4:%.*]] = icmp ne i32 [[RET]], 1
+; CHECK-NEXT:    [[CMP_NE_5:%.*]] = icmp ne i32 [[RET]], 0
+; CHECK-NEXT:    [[CMP_NE_6:%.*]] = icmp ne i32 [[RET]], -1
+; CHECK-NEXT:    tail call void @use3(i1 true, i1 [[CMP_NE_2]], i1 [[CMP_NE_3]])
+; CHECK-NEXT:    tail call void @use3(i1 [[CMP_NE_4]], i1 [[CMP_NE_5]], i1 true)
+; CHECK-NEXT:    ret void
+;
+  ; ret = [0, 10), slt
+  %ret = tail call i32 @test0(i32 *%p)
+  %cmp-slt-1 = icmp slt i32 %ret, 10
+  %cmp-slt-2 = icmp slt i32 %ret, 9
+  %cmp-slt-3 = icmp slt i32 %ret, 8
+  %cmp-slt-4 = icmp slt i32 %ret, 1
+  %cmp-slt-5 = icmp slt i32 %ret, 0
+  %cmp-slt-6 = icmp slt i32 %ret, -1
+  tail call void @use3(i1 %cmp-slt-1, i1 %cmp-slt-2, i1 %cmp-slt-3)
+  tail call void @use3(i1 %cmp-slt-4, i1 %cmp-slt-5, i1 %cmp-slt-6)
+
+  ; ret = [0, 10), sgt
+  %cmp-sgt-1 = icmp sgt i32 %ret, 10
+  %cmp-sgt-2 = icmp sgt i32 %ret, 9
+  %cmp-sgt-3 = icmp sgt i32 %ret, 8
+  %cmp-sgt-4 = icmp sgt i32 %ret, 1
+  %cmp-sgt-5 = icmp sgt i32 %ret, 0
+  %cmp-sgt-6 = icmp sgt i32 %ret, -1
+  tail call void @use3(i1 %cmp-sgt-1, i1 %cmp-sgt-2, i1 %cmp-sgt-3)
+  tail call void @use3(i1 %cmp-sgt-4, i1 %cmp-sgt-5, i1 %cmp-sgt-6)
+
+  ; ret = [0, 10), sle
+  %cmp-lte-1 = icmp sle i32 %ret, 10
+  %cmp-lte-2 = icmp sle i32 %ret, 9
+  %cmp-lte-3 = icmp sle i32 %ret, 8
+  %cmp-lte-4 = icmp sle i32 %ret, 1
+  %cmp-lte-5 = icmp sle i32 %ret, 0
+  %cmp-lte-6 = icmp sle i32 %ret, -1
+  tail call void @use3(i1 %cmp-lte-1, i1 %cmp-lte-2, i1 %cmp-lte-3)
+  tail call void @use3(i1 %cmp-lte-4, i1 %cmp-lte-5, i1 %cmp-lte-6)
+
+  ; ret = [0, 10), sge
+  %cmp-gte-1 = icmp sge i32 %ret, 10
+  %cmp-gte-2 = icmp sge i32 %ret, 9
+  %cmp-gte-3 = icmp sge i32 %ret, 8
+  %cmp-gte-4 = icmp sge i32 %ret, 1
+  %cmp-gte-5 = icmp sge i32 %ret, 0
+  %cmp-gte-6 = icmp sge i32 %ret, -1
+  tail call void @use3(i1 %cmp-gte-1, i1 %cmp-gte-2, i1 %cmp-gte-3)
+  tail call void @use3(i1 %cmp-gte-4, i1 %cmp-gte-5, i1 %cmp-gte-6)
+
+  ; ret = [0, 10), eq
+  %cmp-eq-1 = icmp eq i32 %ret, 10
+  %cmp-eq-2 = icmp eq i32 %ret, 9
+  %cmp-eq-3 = icmp eq i32 %ret, 8
+  %cmp-eq-4 = icmp eq i32 %ret, 1
+  %cmp-eq-5 = icmp eq i32 %ret, 0
+  %cmp-eq-6 = icmp eq i32 %ret, -1
+  tail call void @use3(i1 %cmp-eq-1, i1 %cmp-eq-2, i1 %cmp-eq-3)
+  tail call void @use3(i1 %cmp-eq-4, i1 %cmp-eq-5, i1 %cmp-eq-6)
+
+  ; ret = [0, 10), ne
+  %cmp-ne-1 = icmp ne i32 %ret, 10
+  %cmp-ne-2 = icmp ne i32 %ret, 9
+  %cmp-ne-3 = icmp ne i32 %ret, 8
+  %cmp-ne-4 = icmp ne i32 %ret, 1
+  %cmp-ne-5 = icmp ne i32 %ret, 0
+  %cmp-ne-6 = icmp ne i32 %ret, -1
+  tail call void @use3(i1 %cmp-ne-1, i1 %cmp-ne-2, i1 %cmp-ne-3)
+  tail call void @use3(i1 %cmp-ne-4, i1 %cmp-ne-5, i1 %cmp-ne-6)
+
+  ret void
+}
+define i32 @test1(i32* %p) {
+; CHECK-LABEL: define {{[^@]+}}@test1
+; CHECK-SAME: (i32* nocapture nofree nonnull readonly dereferenceable(4) [[P:%.*]]) #0
+; CHECK-NEXT:    [[LOAD_10_100:%.*]] = load i32, i32* [[P:%.*]], !range !1
+; CHECK-NEXT:    [[ADD_10_THEN_20_110:%.*]] = add i32 [[LOAD_10_100]], 10
+; CHECK-NEXT:    [[MUL_10_THEN_200_1091:%.*]] = mul i32 [[ADD_10_THEN_20_110]], 10
+; CHECK-NEXT:    ret i32 [[MUL_10_THEN_200_1091]]
+;
+  %load-10-100 = load i32, i32* %p, !range !1
+  %add-10-then-20-110 = add i32 %load-10-100, 10
+  %mul-10-then-200-1091 = mul i32 %add-10-then-20-110, 10
+  ret i32 %mul-10-then-200-1091
+}
+
+define i1 @test1-check(i32* %p) {
+; CHECK-LABEL: define {{[^@]+}}@test1-check
+; CHECK-SAME: (i32* nocapture nofree readonly [[P:%.*]]) #0
+; CHECK-NEXT:    [[RES:%.*]] = tail call i32 @test1(i32* nocapture nofree readonly [[P:%.*]]) #0, !range !2
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[RES]], 500
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %res = tail call i32 @test1(i32* %p)
+  %cmp = icmp eq i32 %res, 500
+  ret i1 %cmp
+}
+
+;  TEST2
+;  int test2(int *p) { return *p == 0 ? 4 : 3; }
+;  int test2_check(int *p) {
+;    int call = test2(p);
+;    if (call == 5) {
+;      return 2;
+;    } else {
+;      return 3;
+;    }
+;  }
+
+define i32 @test2(i32* %p) {
+; CHECK-LABEL: define {{[^@]+}}@test2
+; CHECK-SAME: (i32* nocapture nofree nonnull readonly align 4 dereferenceable(4) [[P:%.*]]) #0
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[P:%.*]], align 4
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[TMP0]], 0
+; CHECK-NEXT:    [[COND:%.*]] = select i1 [[TOBOOL]], i32 4, i32 3
+; CHECK-NEXT:    ret i32 [[COND]]
+;
+entry:
+  %0 = load i32, i32* %p, align 4
+  %tobool = icmp eq i32 %0, 0
+  %cond = select i1 %tobool, i32 4, i32 3
+  ret i32 %cond
+}
+
+define i32 @test2_check(i32* %p) {
+; CHECK-LABEL: define {{[^@]+}}@test2_check
+; CHECK-SAME: (i32* nocapture nofree readonly [[P:%.*]]) #1
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call i32 @test2(i32* nocapture nofree readonly [[P:%.*]]) #1, !range !3
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[CALL]], 5
+; CHECK-NEXT:    br i1 true, label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    unreachable
+; CHECK:       return:
+; CHECK-NEXT:    ret i32 2
+;
+entry:
+  %call = tail call i32 @test2(i32* %p)
+  %cmp = icmp slt i32 %call, 5
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  br label %return
+
+if.end:                                           ; preds = %entry
+  br label %return
+
+return:                                           ; preds = %if.end, %if.then
+  %retval.0 = phi i32 [ 2, %if.then ], [ 3, %if.end ]
+  ret i32 %retval.0
+}
+
+; TEST 3 SECV test
+
+; void unkown();
+; int r1(unsigned int u){
+;   int sum = 0;
+;   for(int i = 0; i<100;i++){
+;     sum += i;
+;   }
+;   // sum = 50 * 49 / 2
+;   if(sum > 10000){
+;   // dead block
+;     return 20;
+;   }else {
+;     return 10;
+;   }
+; }
+; void f1(int u){
+;   if(r1(u) > 15){
+;   // deadblock
+;     unkown();
+;   }else {
+;     return;
+;   }
+; }
+
+declare dso_local void @unkown()
+
+define internal i32 @r1(i32) local_unnamed_addr #0 {
+; CHECK-LABEL: define {{[^@]+}}@r1
+; CHECK-SAME: (i32 [[TMP0:%.*]]) local_unnamed_addr #2
+; CHECK-NEXT:    br label [[TMP5:%.*]]
+; CHECK:       2:
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp sgt i32 4950, 10000
+; CHECK-NEXT:    br i1 false, label [[TMP4:%.*]], label [[F:%.*]]
+; CHECK:       4:
+; CHECK-NEXT:    unreachable
+; CHECK:       f:
+; CHECK-NEXT:    ret i32 10
+; CHECK:       5:
+; CHECK-NEXT:    [[TMP6:%.*]] = phi i32 [ 0, [[TMP1:%.*]] ], [ 100, [[TMP5]] ]
+; CHECK-NEXT:    [[TMP7:%.*]] = phi i32 [ 0, [[TMP1]] ], [ 4950, [[TMP5]] ]
+; CHECK-NEXT:    [[TMP8:%.*]] = add nuw nsw i32 99, 4851
+; CHECK-NEXT:    [[TMP9:%.*]] = add nuw nsw i32 99, 1
+; CHECK-NEXT:    [[TMP10:%.*]] = icmp eq i32 100, 100
+; CHECK-NEXT:    br i1 true, label [[TMP2:%.*]], label [[TMP5]]
+;
+  br label %5
+
+2:                                                ; preds = %5
+  %3 = icmp sgt i32 %8, 10000
+  br i1 %3, label %4, label %f
+4:
+  ret i32 20
+f:
+  ret i32 10
+5:                                                ; preds = %5, %1
+  %6 = phi i32 [ 0, %1 ], [ %9, %5 ]
+  %7 = phi i32 [ 0, %1 ], [ %8, %5 ]
+  %8 = add nuw nsw i32 %6, %7
+  %9 = add nuw nsw i32 %6, 1
+  %10 = icmp eq i32 %9, 100
+  br i1 %10, label %2, label %5
+}
+
+define void @f1(i32){
+; CHECK-LABEL: define {{[^@]+}}@f1
+; CHECK-SAME: (i32 [[TMP0:%.*]]) #2
+; CHECK-NEXT:    [[TMP2:%.*]] = tail call i32 @r1(i32 undef) #2
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp sgt i32 10, 15
+; CHECK-NEXT:    br i1 false, label [[TMP4:%.*]], label [[TMP5:%.*]]
+; CHECK:       4:
+; CHECK-NEXT:    unreachable
+; CHECK:       5:
+; CHECK-NEXT:    ret void
+;
+  %2 = tail call i32 @r1(i32 %0)
+  %3 = icmp sgt i32 %2, 15
+  br i1 %3, label %4, label %5
+
+4:                                                ; preds = %1
+  tail call void @unkown()
+  br label %5
+
+5:                                                ; preds = %1, %4
+  ret void
+}
+
+
+
+!0 = !{i32 0, i32 10}
+!1 = !{i32 10, i32 100}
+
+; CHECK: !0 = !{i32 0, i32 10}
+; CHECK-NEXT: !1 = !{i32 10, i32 100}
+; CHECK-NEXT: !2 = !{i32 200, i32 1091}
+; CHECK-NEXT: !3 = !{i32 3, i32 5}
+; CHECK-NEXT: !4 = !{i32 10, i32 21}

llvm/test/Transforms/Attributor/value-simplify.ll

 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %r = call i1 @ipccp2i(i1 true)
   ret i1 %r
 }
 
 define internal i32 @ipccp3i(i32 %a) {
 ; CHECK-LABEL: define {{[^@]+}}@ipccp3i
-; CHECK-SAME: (i32 [[A:%.*]]) #1
-; CHECK-NEXT:    [[C:%.*]] = icmp eq i32 [[A:%.*]], 7
-; CHECK-NEXT:    br i1 [[C]], label [[T:%.*]], label [[F:%.*]]
+; CHECK-SAME: (i32 returned [[A:%.*]])
+; CHECK-NEXT:    [[C:%.*]] = icmp eq i32 7, 7
+; CHECK-NEXT:    br i1 true, label [[T:%.*]], label [[F:%.*]]
 ; CHECK:       t:
-; CHECK-NEXT:    ret i32 [[A]]
+; CHECK-NEXT:    ret i32 7
 ; CHECK:       f:
-; CHECK-NEXT:    [[R:%.*]] = call i32 @ipccp3i(i32 5) #1
-; CHECK-NEXT:    ret i32 [[R]]
+; CHECK-NEXT:    unreachable
 ;
   %c = icmp eq i32 %a, 7
   br i1 %c, label %t, label %f
 t:
   ret i32 %a
 f:
   %r = call i32 @ipccp3i(i32 5)
   ret i32 %r
 }
 
 define i32 @ipccp3() {
-; CHECK-LABEL: define {{[^@]+}}@ipccp3() #1
-; CHECK-NEXT:    [[R:%.*]] = call i32 @ipccp3i(i32 7) #1
+; CHECK-LABEL: define {{[^@]+}}@ipccp3()
+; CHECK-NEXT:    [[R:%.*]] = call i32 @ipccp3i(i32 7)
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %r = call i32 @ipccp3i(i32 7)
   ret i32 %r
 }
 
 ; UTC_ARGS: --turn on
 
 ; Do not touch complicated arguments (for now)