//===----------------------------------------------------------------------===//
#include "llvm/Analysis/ScalarEvolution.h"
+#include "llvm/ADT/Optional.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Metadata.h"
#include "llvm/IR/Operator.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
return 0;
}
+/// GetRangeFromMetadata - Helper method to assign a range to V from
+/// metadata present in the IR.
+static Optional<ConstantRange> GetRangeFromMetadata(Value *V) {
+ if (Instruction *I = dyn_cast<Instruction>(V)) {
+ if (MDNode *MD = I->getMetadata(LLVMContext::MD_range)) {
+ ConstantRange TotalRange(
+ cast<IntegerType>(I->getType())->getBitWidth(), false);
+
+ unsigned NumRanges = MD->getNumOperands() / 2;
+ assert(NumRanges >= 1);
+
+ for (unsigned i = 0; i < NumRanges; ++i) {
+ ConstantInt *Lower = cast<ConstantInt>(MD->getOperand(2*i + 0));
+ ConstantInt *Upper = cast<ConstantInt>(MD->getOperand(2*i + 1));
+ ConstantRange Range(Lower->getValue(), Upper->getValue());
+ TotalRange = TotalRange.unionWith(Range);
+ }
+
+ return TotalRange;
+ }
+ }
+
+ return None;
+}
+
/// getUnsignedRange - Determine the unsigned range for a particular SCEV.
///
ConstantRange
}
if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
+ // Check if the IR explicitly contains !range metadata.
+ Optional<ConstantRange> MDRange = GetRangeFromMetadata(U->getValue());
+ if (MDRange.hasValue())
+ ConservativeResult = ConservativeResult.intersectWith(MDRange.getValue());
+
// For a SCEVUnknown, ask ValueTracking.
APInt Zeros(BitWidth, 0), Ones(BitWidth, 0);
computeKnownBits(U->getValue(), Zeros, Ones, DL, 0, AT, nullptr, DT);
}
if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
+ // Check if the IR explicitly contains !range metadata.
+ Optional<ConstantRange> MDRange = GetRangeFromMetadata(U->getValue());
+ if (MDRange.hasValue())
+ ConservativeResult = ConservativeResult.intersectWith(MDRange.getValue());
+
// For a SCEVUnknown, ask ValueTracking.
if (!U->getValue()->getType()->isIntegerTy() && !DL)
return setSignedRange(U, ConservativeResult);
// (interprocedural conditions notwithstanding).
if (!L) return true;
+ if (isKnownPredicateWithRanges(Pred, LHS, RHS)) return true;
+
BasicBlock *Latch = L->getLoopLatch();
if (!Latch)
return false;
// (interprocedural conditions notwithstanding).
if (!L) return false;
+ if (isKnownPredicateWithRanges(Pred, LHS, RHS)) return true;
+
// Starting at the loop predecessor, climb up the predecessor chain, as long
// as there are predecessors that can be found that have unique successors
// leading to the original header.
--- /dev/null
+; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s
+
+define i32 @slt_trip_count_with_range(i32 *%ptr0, i32 *%ptr1) {
+; CHECK-LABEL: slt_trip_count_with_range
+ entry:
+ %limit = load i32* %ptr0, !range !0
+ br label %loop
+
+ loop:
+; CHECK: Loop %loop: max backedge-taken count is 98
+ %index = phi i32 [ 0, %entry ], [ %index.inc, %loop ]
+ %index.inc = add i32 %index, 1
+ %continue = icmp slt i32 %index.inc, %limit
+ br i1 %continue, label %loop, label %loop.exit
+
+ loop.exit:
+ ret i32 0
+}
+
+define i32 @ult_trip_count_with_range(i32 *%ptr0, i32 *%ptr1) {
+; CHECK-LABEL: ult_trip_count_with_range
+ entry:
+ %limit = load i32* %ptr0, !range !0
+ br label %loop
+
+ loop:
+; CHECK: Loop %loop: max backedge-taken count is 98
+ %index = phi i32 [ 0, %entry ], [ %index.inc, %loop ]
+ %index.inc = add i32 %index, 1
+ %continue = icmp ult i32 %index.inc, %limit
+ br i1 %continue, label %loop, label %loop.exit
+
+ loop.exit:
+ ret i32 0
+}
+
+!0 = metadata !{i32 1, i32 100}
--- /dev/null
+;; RUN: opt -S < %s -indvars | FileCheck %s
+
+;; Check if IndVarSimplify understands !range metadata.
+
+declare void @abort()
+
+define i1 @iterate(i32* nocapture readonly %buffer) {
+entry:
+ %length = load i32* %buffer, !range !0
+ br label %loop.preheader
+
+loop.preheader:
+ br label %loop
+
+loop:
+ %idx = phi i32 [ %idx.inc, %loop.next ], [ 0, %loop.preheader ]
+ %oob.pred = icmp slt i32 %idx, %length
+ br i1 %oob.pred, label %loop.next, label %oob
+; CHECK: br i1 true, label %loop.next, label %oob
+
+loop.next:
+ %idx.inc = add i32 %idx, 1
+ %exit.pred = icmp slt i32 %idx.inc, %length
+ br i1 %exit.pred, label %loop, label %abort.loopexit
+
+abort.loopexit:
+ br label %abort
+
+abort:
+ ret i1 false
+
+oob:
+ tail call void @abort()
+ ret i1 false
+}
+
+!0 = metadata !{i32 1, i32 100}