| 1 |
//===- LoopRotationUtilsTest.cpp - Unit tests for LoopRotation utility ----===// |
| 2 |
// |
| 3 |
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 4 |
// See https://llvm.org/LICENSE.txt for license information. |
| 5 |
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| 6 |
// |
| 7 |
//===----------------------------------------------------------------------===// |
| 8 |
|
| 9 |
#include "llvm/Transforms/Utils/LoopRotationUtils.h" |
| 10 |
#include "llvm/Analysis/AssumptionCache.h" |
| 11 |
#include "llvm/Analysis/InstructionSimplify.h" |
| 12 |
#include "llvm/Analysis/LoopInfo.h" |
| 13 |
#include "llvm/Analysis/ScalarEvolution.h" |
| 14 |
#include "llvm/Analysis/TargetLibraryInfo.h" |
| 15 |
#include "llvm/Analysis/TargetTransformInfo.h" |
| 16 |
#include "llvm/AsmParser/Parser.h" |
| 17 |
#include "llvm/IR/Dominators.h" |
| 18 |
#include "llvm/IR/LLVMContext.h" |
| 19 |
#include "llvm/Support/SourceMgr.h" |
| 20 |
#include "gtest/gtest.h" |
| 21 |
|
| 22 |
using namespace llvm; |
| 23 |
|
| 24 |
static std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) { |
| 25 |
SMDiagnostic Err; |
| 26 |
std::unique_ptr<Module> Mod = parseAssemblyString(IR, Err, C); |
| 27 |
if (!Mod) |
| 28 |
Err.print("LoopRotationUtilsTest", errs()); |
| 29 |
return Mod; |
| 30 |
} |
| 31 |
|
| 32 |
/// This test contains multi-deopt-exits pattern that might allow loop rotation |
| 33 |
/// to trigger multiple times if multiple rotations are enabled. |
| 34 |
/// At least one rotation should be performed, no matter what loop rotation settings are. |
| 35 |
TEST(LoopRotate, MultiDeoptExit) { |
| 36 |
LLVMContext C; |
| 37 |
|
| 38 |
std::unique_ptr<Module> M = parseIR( |
| 39 |
C, |
| 40 |
R"( |
| 41 |
declare i32 @llvm.experimental.deoptimize.i32(...) |
| 42 |
|
| 43 |
define i32 @test(i32 * nonnull %a, i64 %x) { |
| 44 |
entry: |
| 45 |
br label %for.cond1 |
| 46 |
|
| 47 |
for.cond1: |
| 48 |
%idx = phi i64 [ 0, %entry ], [ %idx.next, %for.tail ] |
| 49 |
%sum = phi i32 [ 0, %entry ], [ %sum.next, %for.tail ] |
| 50 |
%a.idx = getelementptr inbounds i32, i32 *%a, i64 %idx |
| 51 |
%val.a.idx = load i32, i32* %a.idx, align 4 |
| 52 |
%zero.check = icmp eq i32 %val.a.idx, 0 |
| 53 |
br i1 %zero.check, label %deopt.exit, label %for.cond2 |
| 54 |
|
| 55 |
for.cond2: |
| 56 |
%for.check = icmp ult i64 %idx, %x |
| 57 |
br i1 %for.check, label %for.body, label %return |
| 58 |
|
| 59 |
for.body: |
| 60 |
br label %for.tail |
| 61 |
|
| 62 |
for.tail: |
| 63 |
%sum.next = add i32 %sum, %val.a.idx |
| 64 |
%idx.next = add nuw nsw i64 %idx, 1 |
| 65 |
br label %for.cond1 |
| 66 |
|
| 67 |
return: |
| 68 |
ret i32 %sum |
| 69 |
|
| 70 |
deopt.exit: |
| 71 |
%deopt.val = call i32(...) @llvm.experimental.deoptimize.i32() [ "deopt"(i32 %val.a.idx) ] |
| 72 |
ret i32 %deopt.val |
| 73 |
})" |
| 74 |
); |
| 75 |
|
| 76 |
auto *F = M->getFunction("test"); |
| 77 |
DominatorTree DT(*F); |
| 78 |
LoopInfo LI(DT); |
| 79 |
AssumptionCache AC(*F); |
| 80 |
TargetTransformInfo TTI(M->getDataLayout()); |
| 81 |
TargetLibraryInfoImpl TLII; |
| 82 |
TargetLibraryInfo TLI(TLII); |
| 83 |
ScalarEvolution SE(*F, TLI, AC, DT, LI); |
| 84 |
SimplifyQuery SQ(M->getDataLayout()); |
| 85 |
|
| 86 |
Loop *L = *LI.begin(); |
| 87 |
|
| 88 |
bool ret = LoopRotation(L, &LI, &TTI, |
| 89 |
&AC, &DT, |
| 90 |
&SE, nullptr, |
| 91 |
SQ, true, -1, false); |
| 92 |
EXPECT_TRUE(ret); |
| 93 |
} |
| 94 |
|
| 95 |
/// Checking a special case of multi-deopt exit loop that can not perform |
| 96 |
/// required amount of rotations due to the desired header containing |
| 97 |
/// non-duplicatable code. |
| 98 |
/// Similar to MultiDeoptExit test this one should do at least one rotation and |
| 99 |
/// pass no matter what loop rotation settings are. |
| 100 |
TEST(LoopRotate, MultiDeoptExit_Nondup) { |
| 101 |
LLVMContext C; |
| 102 |
|
| 103 |
std::unique_ptr<Module> M = parseIR( |
| 104 |
C, |
| 105 |
R"( |
| 106 |
; Rotation should be done once, attempted twice. |
| 107 |
; Second time fails due to non-duplicatable header. |
| 108 |
|
| 109 |
declare i32 @llvm.experimental.deoptimize.i32(...) |
| 110 |
|
| 111 |
declare void @nondup() |
| 112 |
|
| 113 |
define i32 @test_nondup(i32 * nonnull %a, i64 %x) { |
| 114 |
entry: |
| 115 |
br label %for.cond1 |
| 116 |
|
| 117 |
for.cond1: |
| 118 |
%idx = phi i64 [ 0, %entry ], [ %idx.next, %for.tail ] |
| 119 |
%sum = phi i32 [ 0, %entry ], [ %sum.next, %for.tail ] |
| 120 |
%a.idx = getelementptr inbounds i32, i32 *%a, i64 %idx |
| 121 |
%val.a.idx = load i32, i32* %a.idx, align 4 |
| 122 |
%zero.check = icmp eq i32 %val.a.idx, 0 |
| 123 |
br i1 %zero.check, label %deopt.exit, label %for.cond2 |
| 124 |
|
| 125 |
for.cond2: |
| 126 |
call void @nondup() noduplicate |
| 127 |
%for.check = icmp ult i64 %idx, %x |
| 128 |
br i1 %for.check, label %for.body, label %return |
| 129 |
|
| 130 |
for.body: |
| 131 |
br label %for.tail |
| 132 |
|
| 133 |
for.tail: |
| 134 |
%sum.next = add i32 %sum, %val.a.idx |
| 135 |
%idx.next = add nuw nsw i64 %idx, 1 |
| 136 |
br label %for.cond1 |
| 137 |
|
| 138 |
return: |
| 139 |
ret i32 %sum |
| 140 |
|
| 141 |
deopt.exit: |
| 142 |
%deopt.val = call i32(...) @llvm.experimental.deoptimize.i32() [ "deopt"(i32 %val.a.idx) ] |
| 143 |
ret i32 %deopt.val |
| 144 |
})" |
| 145 |
); |
| 146 |
|
| 147 |
auto *F = M->getFunction("test_nondup"); |
| 148 |
DominatorTree DT(*F); |
| 149 |
LoopInfo LI(DT); |
| 150 |
AssumptionCache AC(*F); |
| 151 |
TargetTransformInfo TTI(M->getDataLayout()); |
| 152 |
TargetLibraryInfoImpl TLII; |
| 153 |
TargetLibraryInfo TLI(TLII); |
| 154 |
ScalarEvolution SE(*F, TLI, AC, DT, LI); |
| 155 |
SimplifyQuery SQ(M->getDataLayout()); |
| 156 |
|
| 157 |
Loop *L = *LI.begin(); |
| 158 |
|
| 159 |
bool ret = LoopRotation(L, &LI, &TTI, |
| 160 |
&AC, &DT, |
| 161 |
&SE, nullptr, |
| 162 |
SQ, true, -1, false); |
| 163 |
/// LoopRotation should properly report "true" as we still perform the first rotation |
| 164 |
/// so we do change the IR. |
| 165 |
EXPECT_TRUE(ret); |
| 166 |
} |