#include "llvm/ADT/Optional.h"
+#include "llvm/Analysis/BranchProbabilityInfo.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
/// Create an inductive range check out of BI if possible, else return
/// nullptr.
static InductiveRangeCheck *create(AllocatorTy &Alloc, BranchInst *BI,
- Loop *L, ScalarEvolution &SE);
+ Loop *L, ScalarEvolution &SE,
+ BranchProbabilityInfo &BPI);
};
class InductiveRangeCheckElimination : public LoopPass {
AU.addRequiredID(LoopSimplifyID);
AU.addRequiredID(LCSSAID);
AU.addRequired<ScalarEvolution>();
+ AU.addRequired<BranchProbabilityInfo>();
}
bool runOnLoop(Loop *L, LPPassManager &LPM) override;
return true;
}
+
InductiveRangeCheck *
InductiveRangeCheck::create(InductiveRangeCheck::AllocatorTy &A, BranchInst *BI,
- Loop *L, ScalarEvolution &SE) {
+ Loop *L, ScalarEvolution &SE,
+ BranchProbabilityInfo &BPI) {
if (BI->isUnconditional() || BI->getParent() == L->getLoopLatch())
return nullptr;
+ BranchProbability LikelyTaken(15, 16);
+
+ if (BPI.getEdgeProbability(BI->getParent(), (unsigned) 0) < LikelyTaken)
+ return nullptr;
+
Value *Length = nullptr;
const SCEV *IndexSCEV = nullptr;
InductiveRangeCheck::AllocatorTy IRCAlloc;
SmallVector<InductiveRangeCheck *, 16> RangeChecks;
ScalarEvolution &SE = getAnalysis<ScalarEvolution>();
+ BranchProbabilityInfo &BPI = getAnalysis<BranchProbabilityInfo>();
for (auto BBI : L->getBlocks())
if (BranchInst *TBI = dyn_cast<BranchInst>(BBI->getTerminator()))
if (InductiveRangeCheck *IRC =
- InductiveRangeCheck::create(IRCAlloc, TBI, L, SE))
+ InductiveRangeCheck::create(IRCAlloc, TBI, L, SE, BPI))
RangeChecks.push_back(IRC);
if (RangeChecks.empty())
%idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds.b ]
%idx.next = add i32 %idx, 1
%abc.a = icmp slt i32 %idx, %len.a
- br i1 %abc.a, label %in.bounds.a, label %out.of.bounds
+ br i1 %abc.a, label %in.bounds.a, label %out.of.bounds, !prof !1
in.bounds.a:
%addr.a = getelementptr i32* %arr_a, i32 %idx
store i32 0, i32* %addr.a
%abc.b = icmp slt i32 %idx, %len.b
- br i1 %abc.b, label %in.bounds.b, label %out.of.bounds
+ br i1 %abc.b, label %in.bounds.b, label %out.of.bounds, !prof !1
in.bounds.b:
%addr.b = getelementptr i32* %arr_b, i32 %idx
; CHECK: br i1 %next.postloop, label %loop.postloop, label %exit.loopexit
!0 = !{i32 0, i32 2147483647}
+!1 = !{!"branch_weights", i32 64, i32 4}
--- /dev/null
+; RUN: opt -verify-loop-info -irce-print-changed-loops -irce < %s 2>&1 | FileCheck %s
+
+; CHECK-NOT: constrained Loop
+
+define void @multiple_access_no_preloop(
+ i32* %arr_a, i32* %a_len_ptr, i32* %arr_b, i32* %b_len_ptr, i32 %n) {
+
+ entry:
+ %len.a = load i32* %a_len_ptr, !range !0
+ %len.b = load i32* %b_len_ptr, !range !0
+ %first.itr.check = icmp sgt i32 %n, 0
+ br i1 %first.itr.check, label %loop, label %exit
+
+ loop:
+ %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds.b ]
+ %idx.next = add i32 %idx, 1
+ %abc.a = icmp slt i32 %idx, %len.a
+ br i1 %abc.a, label %in.bounds.a, label %out.of.bounds, !prof !1
+
+ in.bounds.a:
+ %addr.a = getelementptr i32* %arr_a, i32 %idx
+ store i32 0, i32* %addr.a
+ %abc.b = icmp slt i32 %idx, %len.b
+ br i1 %abc.b, label %in.bounds.b, label %out.of.bounds, !prof !1
+
+ in.bounds.b:
+ %addr.b = getelementptr i32* %arr_b, i32 %idx
+ store i32 -1, i32* %addr.b
+ %next = icmp slt i32 %idx.next, %n
+ br i1 %next, label %loop, label %exit
+
+ out.of.bounds:
+ ret void
+
+ exit:
+ ret void
+}
+
+!0 = !{i32 0, i32 2147483647}
+!1 = !{!"branch_weights", i32 1, i32 1}
\ No newline at end of file
%idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ]
%idx.next = add i32 %idx, 1
%abc = icmp slt i32 %idx, %len
- br i1 %abc, label %in.bounds, label %out.of.bounds
+ br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !1
in.bounds:
%addr = getelementptr i32* %arr, i32 %idx
%idx.next = add i32 %idx, 1
%idx.for.abc = add i32 %idx, 4
%abc = icmp slt i32 %idx.for.abc, %len
- br i1 %abc, label %in.bounds, label %out.of.bounds
+ br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !1
in.bounds:
%addr = getelementptr i32* %arr, i32 %idx.for.abc
; CHECK: br i1 %next.postloop, label %loop.postloop, label %exit.loopexit
!0 = !{i32 0, i32 2147483647}
+!1 = !{!"branch_weights", i32 64, i32 4}
%abc.high = icmp slt i32 %array.idx, %len
%abc.low = icmp sge i32 %array.idx, 0
%abc = and i1 %abc.low, %abc.high
- br i1 %abc, label %in.bounds, label %out.of.bounds
+ br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !1
in.bounds:
%addr = getelementptr i32* %arr, i32 %array.idx
; CHECK: br i1 %next.postloop, label %loop.postloop, label %exit.loopexit
!0 = !{i32 0, i32 2147483647}
+!1 = !{!"branch_weights", i32 64, i32 4}
%idx = phi i32 [ 0, %entry ], [ %idx.next, %in.bounds ]
%idx.next = add i32 %idx, 1
%abc = icmp slt i32 %idx, %len
- br i1 %abc, label %in.bounds, label %out.of.bounds
+ br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !1
in.bounds: ; preds = %loop
%addr = getelementptr i32* %arr, i32 %idx
%idx.i = phi i32 [ 0, %loop ], [ %idx.next.i, %in.bounds.i ]
%idx.next.i = add i32 %idx.i, 1
%abc.i = icmp slt i32 %idx.i, %len.i
- br i1 %abc.i, label %in.bounds.i, label %out.of.bounds.i
+ br i1 %abc.i, label %in.bounds.i, label %out.of.bounds.i, !prof !1
in.bounds.i: ; preds = %loop.i
%addr.i = getelementptr i32* %arr, i32 %idx.i
%idx.i.i = phi i32 [ 0, %loop.i ], [ %idx.next.i.i, %in.bounds.i.i ]
%idx.next.i.i = add i32 %idx.i.i, 1
%abc.i.i = icmp slt i32 %idx.i.i, %len.i.i
- br i1 %abc.i.i, label %in.bounds.i.i, label %out.of.bounds.i.i
+ br i1 %abc.i.i, label %in.bounds.i.i, label %out.of.bounds.i.i, !prof !1
in.bounds.i.i: ; preds = %loop.i.i
%addr.i.i = getelementptr i32* %arr, i32 %idx.i.i
%idx.i = phi i32 [ 0, %loop ], [ %idx.next.i, %in.bounds.i ]
%idx.next.i = add i32 %idx.i, 1
%abc.i = icmp slt i32 %idx.i, %len.i
- br i1 %abc.i, label %in.bounds.i, label %out.of.bounds.i
+ br i1 %abc.i, label %in.bounds.i, label %out.of.bounds.i, !prof !1
in.bounds.i: ; preds = %loop.i
%addr.i = getelementptr i32* %arr, i32 %idx.i
%idx.i3 = phi i32 [ 0, %inner_loop.exit ], [ %idx.next.i4, %in.bounds.i9 ]
%idx.next.i4 = add i32 %idx.i3, 1
%abc.i5 = icmp slt i32 %idx.i3, %len.i1
- br i1 %abc.i5, label %in.bounds.i9, label %out.of.bounds.i10
+ br i1 %abc.i5, label %in.bounds.i9, label %out.of.bounds.i10, !prof !1
in.bounds.i9: ; preds = %loop.i6
%addr.i7 = getelementptr i32* %arr, i32 %idx.i3
%idx.i.i = phi i32 [ 0, %loop.i ], [ %idx.next.i.i, %in.bounds.i.i ]
%idx.next.i.i = add i32 %idx.i.i, 1
%abc.i.i = icmp slt i32 %idx.i.i, %len.i.i
- br i1 %abc.i.i, label %in.bounds.i.i, label %out.of.bounds.i.i
+ br i1 %abc.i.i, label %in.bounds.i.i, label %out.of.bounds.i.i, !prof !1
in.bounds.i.i: ; preds = %loop.i.i
%addr.i.i = getelementptr i32* %arr, i32 %idx.i.i
%idx.i.i7 = phi i32 [ 0, %loop.i6 ], [ %idx.next.i.i8, %in.bounds.i.i13 ]
%idx.next.i.i8 = add i32 %idx.i.i7, 1
%abc.i.i9 = icmp slt i32 %idx.i.i7, %len.i.i4
- br i1 %abc.i.i9, label %in.bounds.i.i13, label %out.of.bounds.i.i14
+ br i1 %abc.i.i9, label %in.bounds.i.i13, label %out.of.bounds.i.i14, !prof !1
in.bounds.i.i13: ; preds = %loop.i.i10
%addr.i.i11 = getelementptr i32* %arr, i32 %idx.i.i7
%idx.i = phi i32 [ 0, %loop ], [ %idx.next.i, %in.bounds.i ]
%idx.next.i = add i32 %idx.i, 1
%abc.i = icmp slt i32 %idx.i, %len.i
- br i1 %abc.i, label %in.bounds.i, label %out.of.bounds.i
+ br i1 %abc.i, label %in.bounds.i, label %out.of.bounds.i, !prof !1
in.bounds.i: ; preds = %loop.i
%addr.i = getelementptr i32* %arr, i32 %idx.i
%idx.i.i = phi i32 [ 0, %loop.i4 ], [ %idx.next.i.i, %in.bounds.i.i ]
%idx.next.i.i = add i32 %idx.i.i, 1
%abc.i.i = icmp slt i32 %idx.i.i, %len.i.i
- br i1 %abc.i.i, label %in.bounds.i.i, label %out.of.bounds.i.i
+ br i1 %abc.i.i, label %in.bounds.i.i, label %out.of.bounds.i.i, !prof !1
in.bounds.i.i: ; preds = %loop.i.i
%addr.i.i = getelementptr i32* %arr, i32 %idx.i.i
attributes #0 = { alwaysinline }
!0 = !{i32 0, i32 2147483647}
+!1 = !{!"branch_weights", i32 64, i32 4}