| 1 |
//===- CodeMoverUtils.cpp - Unit tests for CodeMoverUtils ---------------===// |
| 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/CodeMoverUtils.h" |
| 10 |
#include "llvm/Analysis/AliasAnalysis.h" |
| 11 |
#include "llvm/Analysis/AssumptionCache.h" |
| 12 |
#include "llvm/Analysis/DependenceAnalysis.h" |
| 13 |
#include "llvm/Analysis/LoopInfo.h" |
| 14 |
#include "llvm/Analysis/PostDominators.h" |
| 15 |
#include "llvm/Analysis/TargetLibraryInfo.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 "llvm/Transforms/Utils/ScalarEvolutionExpander.h" |
| 21 |
#include "gtest/gtest.h" |
| 22 |
|
| 23 |
using namespace llvm; |
| 24 |
|
| 25 |
static std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) { |
| 26 |
SMDiagnostic Err; |
| 27 |
std::unique_ptr<Module> Mod = parseAssemblyString(IR, Err, C); |
| 28 |
if (!Mod) |
| 29 |
Err.print("CodeMoverUtilsTests", errs()); |
| 30 |
return Mod; |
| 31 |
} |
| 32 |
|
| 33 |
static void run(Module &M, StringRef FuncName, |
| 34 |
function_ref<void(Function &F, DominatorTree &DT, |
| 35 |
PostDominatorTree &PDT, DependenceInfo &DI)> |
| 36 |
Test) { |
| 37 |
auto *F = M.getFunction(FuncName); |
| 38 |
DominatorTree DT(*F); |
| 39 |
PostDominatorTree PDT(*F); |
| 40 |
TargetLibraryInfoImpl TLII; |
| 41 |
TargetLibraryInfo TLI(TLII); |
| 42 |
AssumptionCache AC(*F); |
| 43 |
AliasAnalysis AA(TLI); |
| 44 |
LoopInfo LI(DT); |
| 45 |
ScalarEvolution SE(*F, TLI, AC, DT, LI); |
| 46 |
DependenceInfo DI(F, &AA, &SE, &LI); |
| 47 |
Test(*F, DT, PDT, DI); |
| 48 |
} |
| 49 |
|
| 50 |
static BasicBlock *getBasicBlockByName(Function &F, StringRef Name) { |
| 51 |
for (BasicBlock &BB : F) |
| 52 |
if (BB.getName() == Name) |
| 53 |
return &BB; |
| 54 |
llvm_unreachable("Expected to find basic block!"); |
| 55 |
} |
| 56 |
|
| 57 |
static Instruction *getInstructionByName(Function &F, StringRef Name) { |
| 58 |
for (BasicBlock &BB : F) |
| 59 |
for (Instruction &I : BB) |
| 60 |
if (I.getName() == Name) |
| 61 |
return &I; |
| 62 |
llvm_unreachable("Expected to find instruction!"); |
| 63 |
} |
| 64 |
|
| 65 |
TEST(CodeMoverUtils, IsControlFlowEquivalentSimpleTest) { |
| 66 |
LLVMContext C; |
| 67 |
|
| 68 |
// void foo(int &i, bool cond1, bool cond2) { |
| 69 |
// if (cond1) |
| 70 |
// i = 1; |
| 71 |
// if (cond1) |
| 72 |
// i = 2; |
| 73 |
// if (cond2) |
| 74 |
// i = 3; |
| 75 |
// } |
| 76 |
std::unique_ptr<Module> M = |
| 77 |
parseIR(C, R"(define void @foo(i32* %i, i1 %cond1, i1 %cond2) { |
| 78 |
entry: |
| 79 |
br i1 %cond1, label %if.first, label %if.first.end |
| 80 |
if.first: |
| 81 |
store i32 1, i32* %i, align 4 |
| 82 |
br label %if.first.end |
| 83 |
if.first.end: |
| 84 |
br i1 %cond1, label %if.second, label %if.second.end |
| 85 |
if.second: |
| 86 |
store i32 2, i32* %i, align 4 |
| 87 |
br label %if.second.end |
| 88 |
if.second.end: |
| 89 |
br i1 %cond2, label %if.third, label %if.third.end |
| 90 |
if.third: |
| 91 |
store i32 3, i32* %i, align 4 |
| 92 |
br label %if.third.end |
| 93 |
if.third.end: |
| 94 |
ret void |
| 95 |
})"); |
| 96 |
run(*M, "foo", |
| 97 |
[&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, |
| 98 |
DependenceInfo &DI) { |
| 99 |
BasicBlock *FirstIfBody = getBasicBlockByName(F, "if.first"); |
| 100 |
EXPECT_TRUE( |
| 101 |
isControlFlowEquivalent(*FirstIfBody, *FirstIfBody, DT, PDT)); |
| 102 |
BasicBlock *SecondIfBody = getBasicBlockByName(F, "if.second"); |
| 103 |
EXPECT_TRUE( |
| 104 |
isControlFlowEquivalent(*FirstIfBody, *SecondIfBody, DT, PDT)); |
| 105 |
|
| 106 |
BasicBlock *ThirdIfBody = getBasicBlockByName(F, "if.third"); |
| 107 |
EXPECT_FALSE( |
| 108 |
isControlFlowEquivalent(*FirstIfBody, *ThirdIfBody, DT, PDT)); |
| 109 |
EXPECT_FALSE( |
| 110 |
isControlFlowEquivalent(*SecondIfBody, *ThirdIfBody, DT, PDT)); |
| 111 |
}); |
| 112 |
} |
| 113 |
|
| 114 |
TEST(CodeMoverUtils, IsControlFlowEquivalentOppositeCondTest) { |
| 115 |
LLVMContext C; |
| 116 |
|
| 117 |
// void foo(int &i, unsigned X, unsigned Y) { |
| 118 |
// if (X < Y) |
| 119 |
// i = 1; |
| 120 |
// if (Y > X) |
| 121 |
// i = 2; |
| 122 |
// if (X >= Y) |
| 123 |
// i = 3; |
| 124 |
// else |
| 125 |
// i = 4; |
| 126 |
// if (X == Y) |
| 127 |
// i = 5; |
| 128 |
// if (Y == X) |
| 129 |
// i = 6; |
| 130 |
// else |
| 131 |
// i = 7; |
| 132 |
// if (X != Y) |
| 133 |
// i = 8; |
| 134 |
// else |
| 135 |
// i = 9; |
| 136 |
// } |
| 137 |
std::unique_ptr<Module> M = |
| 138 |
parseIR(C, R"(define void @foo(i32* %i, i32 %X, i32 %Y) { |
| 139 |
entry: |
| 140 |
%cmp1 = icmp ult i32 %X, %Y |
| 141 |
br i1 %cmp1, label %if.first, label %if.first.end |
| 142 |
if.first: |
| 143 |
store i32 1, i32* %i, align 4 |
| 144 |
br label %if.first.end |
| 145 |
if.first.end: |
| 146 |
%cmp2 = icmp ugt i32 %Y, %X |
| 147 |
br i1 %cmp2, label %if.second, label %if.second.end |
| 148 |
if.second: |
| 149 |
store i32 2, i32* %i, align 4 |
| 150 |
br label %if.second.end |
| 151 |
if.second.end: |
| 152 |
%cmp3 = icmp uge i32 %X, %Y |
| 153 |
br i1 %cmp3, label %if.third, label %if.third.else |
| 154 |
if.third: |
| 155 |
store i32 3, i32* %i, align 4 |
| 156 |
br label %if.third.end |
| 157 |
if.third.else: |
| 158 |
store i32 4, i32* %i, align 4 |
| 159 |
br label %if.third.end |
| 160 |
if.third.end: |
| 161 |
%cmp4 = icmp eq i32 %X, %Y |
| 162 |
br i1 %cmp4, label %if.fourth, label %if.fourth.end |
| 163 |
if.fourth: |
| 164 |
store i32 5, i32* %i, align 4 |
| 165 |
br label %if.fourth.end |
| 166 |
if.fourth.end: |
| 167 |
%cmp5 = icmp eq i32 %Y, %X |
| 168 |
br i1 %cmp5, label %if.fifth, label %if.fifth.else |
| 169 |
if.fifth: |
| 170 |
store i32 6, i32* %i, align 4 |
| 171 |
br label %if.fifth.end |
| 172 |
if.fifth.else: |
| 173 |
store i32 7, i32* %i, align 4 |
| 174 |
br label %if.fifth.end |
| 175 |
if.fifth.end: |
| 176 |
%cmp6 = icmp ne i32 %X, %Y |
| 177 |
br i1 %cmp6, label %if.sixth, label %if.sixth.else |
| 178 |
if.sixth: |
| 179 |
store i32 8, i32* %i, align 4 |
| 180 |
br label %if.sixth.end |
| 181 |
if.sixth.else: |
| 182 |
store i32 9, i32* %i, align 4 |
| 183 |
br label %if.sixth.end |
| 184 |
if.sixth.end: |
| 185 |
ret void |
| 186 |
})"); |
| 187 |
run(*M, "foo", |
| 188 |
[&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, |
| 189 |
DependenceInfo &DI) { |
| 190 |
BasicBlock *FirstIfBody = getBasicBlockByName(F, "if.first"); |
| 191 |
BasicBlock *SecondIfBody = getBasicBlockByName(F, "if.second"); |
| 192 |
BasicBlock *ThirdIfBody = getBasicBlockByName(F, "if.third"); |
| 193 |
BasicBlock *ThirdElseBody = getBasicBlockByName(F, "if.third.else"); |
| 194 |
EXPECT_TRUE( |
| 195 |
isControlFlowEquivalent(*FirstIfBody, *ThirdElseBody, DT, PDT)); |
| 196 |
EXPECT_TRUE( |
| 197 |
isControlFlowEquivalent(*SecondIfBody, *ThirdElseBody, DT, PDT)); |
| 198 |
EXPECT_FALSE( |
| 199 |
isControlFlowEquivalent(*ThirdIfBody, *ThirdElseBody, DT, PDT)); |
| 200 |
|
| 201 |
BasicBlock *FourthIfBody = getBasicBlockByName(F, "if.fourth"); |
| 202 |
BasicBlock *FifthIfBody = getBasicBlockByName(F, "if.fifth"); |
| 203 |
BasicBlock *FifthElseBody = getBasicBlockByName(F, "if.fifth.else"); |
| 204 |
EXPECT_FALSE( |
| 205 |
isControlFlowEquivalent(*FifthIfBody, *FifthElseBody, DT, PDT)); |
| 206 |
BasicBlock *SixthIfBody = getBasicBlockByName(F, "if.sixth"); |
| 207 |
EXPECT_TRUE( |
| 208 |
isControlFlowEquivalent(*FifthElseBody, *SixthIfBody, DT, PDT)); |
| 209 |
BasicBlock *SixthElseBody = getBasicBlockByName(F, "if.sixth.else"); |
| 210 |
EXPECT_TRUE( |
| 211 |
isControlFlowEquivalent(*FourthIfBody, *SixthElseBody, DT, PDT)); |
| 212 |
EXPECT_TRUE( |
| 213 |
isControlFlowEquivalent(*FifthIfBody, *SixthElseBody, DT, PDT)); |
| 214 |
}); |
| 215 |
} |
| 216 |
|
| 217 |
TEST(CodeMoverUtils, IsControlFlowEquivalentCondNestTest) { |
| 218 |
LLVMContext C; |
| 219 |
|
| 220 |
// void foo(int &i, bool cond1, bool cond2) { |
| 221 |
// if (cond1) |
| 222 |
// if (cond2) |
| 223 |
// i = 1; |
| 224 |
// if (cond2) |
| 225 |
// if (cond1) |
| 226 |
// i = 2; |
| 227 |
// } |
| 228 |
std::unique_ptr<Module> M = |
| 229 |
parseIR(C, R"(define void @foo(i32* %i, i1 %cond1, i1 %cond2) { |
| 230 |
entry: |
| 231 |
br i1 %cond1, label %if.outer.first, label %if.first.end |
| 232 |
if.outer.first: |
| 233 |
br i1 %cond2, label %if.inner.first, label %if.first.end |
| 234 |
if.inner.first: |
| 235 |
store i32 1, i32* %i, align 4 |
| 236 |
br label %if.first.end |
| 237 |
if.first.end: |
| 238 |
br i1 %cond2, label %if.outer.second, label %if.second.end |
| 239 |
if.outer.second: |
| 240 |
br i1 %cond1, label %if.inner.second, label %if.second.end |
| 241 |
if.inner.second: |
| 242 |
store i32 2, i32* %i, align 4 |
| 243 |
br label %if.second.end |
| 244 |
if.second.end: |
| 245 |
ret void |
| 246 |
})"); |
| 247 |
run(*M, "foo", |
| 248 |
[&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, |
| 249 |
DependenceInfo &DI) { |
| 250 |
BasicBlock *FirstOuterIfBody = getBasicBlockByName(F, "if.outer.first"); |
| 251 |
BasicBlock *FirstInnerIfBody = getBasicBlockByName(F, "if.inner.first"); |
| 252 |
BasicBlock *SecondOuterIfBody = |
| 253 |
getBasicBlockByName(F, "if.outer.second"); |
| 254 |
BasicBlock *SecondInnerIfBody = |
| 255 |
getBasicBlockByName(F, "if.inner.second"); |
| 256 |
EXPECT_TRUE(isControlFlowEquivalent(*FirstInnerIfBody, |
| 257 |
*SecondInnerIfBody, DT, PDT)); |
| 258 |
EXPECT_FALSE(isControlFlowEquivalent(*FirstOuterIfBody, |
| 259 |
*SecondOuterIfBody, DT, PDT)); |
| 260 |
EXPECT_FALSE(isControlFlowEquivalent(*FirstOuterIfBody, |
| 261 |
*SecondInnerIfBody, DT, PDT)); |
| 262 |
EXPECT_FALSE(isControlFlowEquivalent(*FirstInnerIfBody, |
| 263 |
*SecondOuterIfBody, DT, PDT)); |
| 264 |
}); |
| 265 |
} |
| 266 |
|
| 267 |
TEST(CodeMoverUtils, IsControlFlowEquivalentImbalanceTest) { |
| 268 |
LLVMContext C; |
| 269 |
|
| 270 |
// void foo(int &i, bool cond1, bool cond2) { |
| 271 |
// if (cond1) |
| 272 |
// if (cond2) |
| 273 |
// if (cond3) |
| 274 |
// i = 1; |
| 275 |
// if (cond2) |
| 276 |
// if (cond3) |
| 277 |
// i = 2; |
| 278 |
// if (cond1) |
| 279 |
// if (cond1) |
| 280 |
// i = 3; |
| 281 |
// if (cond1) |
| 282 |
// i = 4; |
| 283 |
// } |
| 284 |
std::unique_ptr<Module> M = parseIR( |
| 285 |
C, R"(define void @foo(i32* %i, i1 %cond1, i1 %cond2, i1 %cond3) { |
| 286 |
entry: |
| 287 |
br i1 %cond1, label %if.outer.first, label %if.first.end |
| 288 |
if.outer.first: |
| 289 |
br i1 %cond2, label %if.middle.first, label %if.first.end |
| 290 |
if.middle.first: |
| 291 |
br i1 %cond3, label %if.inner.first, label %if.first.end |
| 292 |
if.inner.first: |
| 293 |
store i32 1, i32* %i, align 4 |
| 294 |
br label %if.first.end |
| 295 |
if.first.end: |
| 296 |
br i1 %cond2, label %if.outer.second, label %if.second.end |
| 297 |
if.outer.second: |
| 298 |
br i1 %cond3, label %if.inner.second, label %if.second.end |
| 299 |
if.inner.second: |
| 300 |
store i32 2, i32* %i, align 4 |
| 301 |
br label %if.second.end |
| 302 |
if.second.end: |
| 303 |
br i1 %cond1, label %if.outer.third, label %if.third.end |
| 304 |
if.outer.third: |
| 305 |
br i1 %cond1, label %if.inner.third, label %if.third.end |
| 306 |
if.inner.third: |
| 307 |
store i32 3, i32* %i, align 4 |
| 308 |
br label %if.third.end |
| 309 |
if.third.end: |
| 310 |
br i1 %cond1, label %if.fourth, label %if.fourth.end |
| 311 |
if.fourth: |
| 312 |
store i32 4, i32* %i, align 4 |
| 313 |
br label %if.fourth.end |
| 314 |
if.fourth.end: |
| 315 |
ret void |
| 316 |
})"); |
| 317 |
run(*M, "foo", |
| 318 |
[&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, |
| 319 |
DependenceInfo &DI) { |
| 320 |
BasicBlock *FirstIfBody = getBasicBlockByName(F, "if.inner.first"); |
| 321 |
BasicBlock *SecondIfBody = getBasicBlockByName(F, "if.inner.second"); |
| 322 |
EXPECT_FALSE( |
| 323 |
isControlFlowEquivalent(*FirstIfBody, *SecondIfBody, DT, PDT)); |
| 324 |
|
| 325 |
BasicBlock *ThirdIfBody = getBasicBlockByName(F, "if.inner.third"); |
| 326 |
BasicBlock *FourthIfBody = getBasicBlockByName(F, "if.fourth"); |
| 327 |
EXPECT_TRUE( |
| 328 |
isControlFlowEquivalent(*ThirdIfBody, *FourthIfBody, DT, PDT)); |
| 329 |
}); |
| 330 |
} |
| 331 |
|
| 332 |
TEST(CodeMoverUtils, IsControlFlowEquivalentPointerTest) { |
| 333 |
LLVMContext C; |
| 334 |
|
| 335 |
// void foo(int &i, int *cond) { |
| 336 |
// if (*cond) |
| 337 |
// i = 1; |
| 338 |
// if (*cond) |
| 339 |
// i = 2; |
| 340 |
// *cond = 1; |
| 341 |
// if (*cond) |
| 342 |
// i = 3; |
| 343 |
// } |
| 344 |
std::unique_ptr<Module> M = |
| 345 |
parseIR(C, R"(define void @foo(i32* %i, i32* %cond) { |
| 346 |
entry: |
| 347 |
%0 = load i32, i32* %cond, align 4 |
| 348 |
%tobool1 = icmp ne i32 %0, 0 |
| 349 |
br i1 %tobool1, label %if.first, label %if.first.end |
| 350 |
if.first: |
| 351 |
store i32 1, i32* %i, align 4 |
| 352 |
br label %if.first.end |
| 353 |
if.first.end: |
| 354 |
%1 = load i32, i32* %cond, align 4 |
| 355 |
%tobool2 = icmp ne i32 %1, 0 |
| 356 |
br i1 %tobool2, label %if.second, label %if.second.end |
| 357 |
if.second: |
| 358 |
store i32 2, i32* %i, align 4 |
| 359 |
br label %if.second.end |
| 360 |
if.second.end: |
| 361 |
store i32 1, i32* %cond, align 4 |
| 362 |
%2 = load i32, i32* %cond, align 4 |
| 363 |
%tobool3 = icmp ne i32 %2, 0 |
| 364 |
br i1 %tobool3, label %if.third, label %if.third.end |
| 365 |
if.third: |
| 366 |
store i32 3, i32* %i, align 4 |
| 367 |
br label %if.third.end |
| 368 |
if.third.end: |
| 369 |
ret void |
| 370 |
})"); |
| 371 |
run(*M, "foo", |
| 372 |
[&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, |
| 373 |
DependenceInfo &DI) { |
| 374 |
BasicBlock *FirstIfBody = getBasicBlockByName(F, "if.first"); |
| 375 |
BasicBlock *SecondIfBody = getBasicBlockByName(F, "if.second"); |
| 376 |
// Limitation: if we can prove cond haven't been modify between %0 and |
| 377 |
// %1, then we can prove FirstIfBody and SecondIfBody are control flow |
| 378 |
// equivalent. |
| 379 |
EXPECT_FALSE( |
| 380 |
isControlFlowEquivalent(*FirstIfBody, *SecondIfBody, DT, PDT)); |
| 381 |
|
| 382 |
BasicBlock *ThirdIfBody = getBasicBlockByName(F, "if.third"); |
| 383 |
EXPECT_FALSE( |
| 384 |
isControlFlowEquivalent(*FirstIfBody, *ThirdIfBody, DT, PDT)); |
| 385 |
EXPECT_FALSE( |
| 386 |
isControlFlowEquivalent(*SecondIfBody, *ThirdIfBody, DT, PDT)); |
| 387 |
}); |
| 388 |
} |
| 389 |
|
| 390 |
TEST(CodeMoverUtils, IsControlFlowEquivalentNotPostdomTest) { |
| 391 |
LLVMContext C; |
| 392 |
|
| 393 |
// void foo(bool cond1, bool cond2) { |
| 394 |
// if (cond1) { |
| 395 |
// if (cond2) |
| 396 |
// return; |
| 397 |
// } else |
| 398 |
// if (cond2) |
| 399 |
// return; |
| 400 |
// return; |
| 401 |
// } |
| 402 |
std::unique_ptr<Module> M = |
| 403 |
parseIR(C, R"(define void @foo(i1 %cond1, i1 %cond2) { |
| 404 |
idom: |
| 405 |
br i1 %cond1, label %succ0, label %succ1 |
| 406 |
succ0: |
| 407 |
br i1 %cond2, label %succ0ret, label %succ0succ1 |
| 408 |
succ0ret: |
| 409 |
ret void |
| 410 |
succ0succ1: |
| 411 |
br label %bb |
| 412 |
succ1: |
| 413 |
br i1 %cond2, label %succ1ret, label %succ1succ1 |
| 414 |
succ1ret: |
| 415 |
ret void |
| 416 |
succ1succ1: |
| 417 |
br label %bb |
| 418 |
bb: |
| 419 |
ret void |
| 420 |
})"); |
| 421 |
run(*M, "foo", |
| 422 |
[&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, |
| 423 |
DependenceInfo &DI) { |
| 424 |
BasicBlock &Idom = F.front(); |
| 425 |
assert(Idom.getName() == "idom" && "Expecting BasicBlock idom"); |
| 426 |
BasicBlock &BB = F.back(); |
| 427 |
assert(BB.getName() == "bb" && "Expecting BasicBlock bb"); |
| 428 |
EXPECT_FALSE(isControlFlowEquivalent(Idom, BB, DT, PDT)); |
| 429 |
}); |
| 430 |
} |
| 431 |
|
| 432 |
TEST(CodeMoverUtils, IsSafeToMoveTest1) { |
| 433 |
LLVMContext C; |
| 434 |
|
| 435 |
// void safecall() noexcept willreturn nosync; |
| 436 |
// void unsafecall(); |
| 437 |
// void foo(int * __restrict__ A, int * __restrict__ B, int * __restrict__ C, |
| 438 |
// long N) { |
| 439 |
// X = N / 1; |
| 440 |
// safecall(); |
| 441 |
// unsafecall1(); |
| 442 |
// unsafecall2(); |
| 443 |
// for (long i = 0; i < N; ++i) { |
| 444 |
// A[5] = 5; |
| 445 |
// A[i] = 0; |
| 446 |
// B[i] = A[i]; |
| 447 |
// C[i] = A[i]; |
| 448 |
// A[6] = 6; |
| 449 |
// } |
| 450 |
// } |
| 451 |
std::unique_ptr<Module> M = parseIR( |
| 452 |
C, R"(define void @foo(i32* noalias %A, i32* noalias %B, i32* noalias %C |
| 453 |
, i64 %N) { |
| 454 |
entry: |
| 455 |
%X = sdiv i64 1, %N |
| 456 |
call void @safecall() |
| 457 |
%cmp1 = icmp slt i64 0, %N |
| 458 |
call void @unsafecall1() |
| 459 |
call void @unsafecall2() |
| 460 |
br i1 %cmp1, label %for.body, label %for.end |
| 461 |
for.body: |
| 462 |
%i = phi i64 [ 0, %entry ], [ %inc, %for.body ] |
| 463 |
%arrayidx_A5 = getelementptr inbounds i32, i32* %A, i64 5 |
| 464 |
store i32 5, i32* %arrayidx_A5, align 4 |
| 465 |
%arrayidx_A = getelementptr inbounds i32, i32* %A, i64 %i |
| 466 |
store i32 0, i32* %arrayidx_A, align 4 |
| 467 |
%load1 = load i32, i32* %arrayidx_A, align 4 |
| 468 |
%arrayidx_B = getelementptr inbounds i32, i32* %B, i64 %i |
| 469 |
store i32 %load1, i32* %arrayidx_B, align 4 |
| 470 |
%load2 = load i32, i32* %arrayidx_A, align 4 |
| 471 |
%arrayidx_C = getelementptr inbounds i32, i32* %C, i64 %i |
| 472 |
store i32 %load2, i32* %arrayidx_C, align 4 |
| 473 |
%arrayidx_A6 = getelementptr inbounds i32, i32* %A, i64 6 |
| 474 |
store i32 6, i32* %arrayidx_A6, align 4 |
| 475 |
%inc = add nsw i64 %i, 1 |
| 476 |
%cmp = icmp slt i64 %inc, %N |
| 477 |
br i1 %cmp, label %for.body, label %for.end |
| 478 |
for.end: |
| 479 |
ret void |
| 480 |
} |
| 481 |
declare void @safecall() nounwind nosync willreturn |
| 482 |
declare void @unsafecall1() |
| 483 |
declare void @unsafecall2())"); |
| 484 |
|
| 485 |
run(*M, "foo", |
| 486 |
[&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, |
| 487 |
DependenceInfo &DI) { |
| 488 |
BasicBlock *Entry = getBasicBlockByName(F, "entry"); |
| 489 |
Instruction *CI_safecall = Entry->front().getNextNode(); |
| 490 |
assert(isa<CallInst>(CI_safecall) && |
| 491 |
"Expecting CI_safecall to be a CallInst"); |
| 492 |
Instruction *CI_unsafecall = CI_safecall->getNextNode()->getNextNode(); |
| 493 |
assert(isa<CallInst>(CI_unsafecall) && |
| 494 |
"Expecting CI_unsafecall to be a CallInst"); |
| 495 |
BasicBlock *ForBody = getBasicBlockByName(F, "for.body"); |
| 496 |
Instruction &PN = ForBody->front(); |
| 497 |
assert(isa<PHINode>(PN) && "Expecting PN to be a PHINode"); |
| 498 |
Instruction *SI_A5 = |
| 499 |
getInstructionByName(F, "arrayidx_A5")->getNextNode(); |
| 500 |
Instruction *SI = getInstructionByName(F, "arrayidx_A")->getNextNode(); |
| 501 |
Instruction *LI1 = getInstructionByName(F, "load1"); |
| 502 |
Instruction *LI2 = getInstructionByName(F, "load2"); |
| 503 |
Instruction *SI_A6 = |
| 504 |
getInstructionByName(F, "arrayidx_A6")->getNextNode(); |
| 505 |
|
| 506 |
// Can move after CI_safecall, as it does not throw, not synchronize, or |
| 507 |
// must return. |
| 508 |
EXPECT_TRUE(isSafeToMoveBefore(*CI_safecall->getPrevNode(), |
| 509 |
*CI_safecall->getNextNode(), DT, &PDT, |
| 510 |
&DI)); |
| 511 |
|
| 512 |
// Cannot move CI_unsafecall, as it may throw. |
| 513 |
EXPECT_FALSE(isSafeToMoveBefore(*CI_unsafecall->getNextNode(), |
| 514 |
*CI_unsafecall, DT, &PDT, &DI)); |
| 515 |
|
| 516 |
// Moving instruction to non control flow equivalent places are not |
| 517 |
// supported. |
| 518 |
EXPECT_FALSE( |
| 519 |
isSafeToMoveBefore(*SI_A5, *Entry->getTerminator(), DT, &PDT, &DI)); |
| 520 |
|
| 521 |
// Moving PHINode is not supported. |
| 522 |
EXPECT_FALSE(isSafeToMoveBefore(PN, *PN.getNextNode()->getNextNode(), |
| 523 |
DT, &PDT, &DI)); |
| 524 |
|
| 525 |
// Cannot move non-PHINode before PHINode. |
| 526 |
EXPECT_FALSE(isSafeToMoveBefore(*PN.getNextNode(), PN, DT, &PDT, &DI)); |
| 527 |
|
| 528 |
// Moving Terminator is not supported. |
| 529 |
EXPECT_FALSE(isSafeToMoveBefore(*Entry->getTerminator(), |
| 530 |
*PN.getNextNode(), DT, &PDT, &DI)); |
| 531 |
|
| 532 |
// Cannot move %arrayidx_A after SI, as SI is its user. |
| 533 |
EXPECT_FALSE(isSafeToMoveBefore(*SI->getPrevNode(), *SI->getNextNode(), |
| 534 |
DT, &PDT, &DI)); |
| 535 |
|
| 536 |
// Cannot move SI before %arrayidx_A, as %arrayidx_A is its operand. |
| 537 |
EXPECT_FALSE( |
| 538 |
isSafeToMoveBefore(*SI, *SI->getPrevNode(), DT, &PDT, &DI)); |
| 539 |
|
| 540 |
// Cannot move LI2 after SI_A6, as there is a flow dependence. |
| 541 |
EXPECT_FALSE( |
| 542 |
isSafeToMoveBefore(*LI2, *SI_A6->getNextNode(), DT, &PDT, &DI)); |
| 543 |
|
| 544 |
// Cannot move SI after LI1, as there is a anti dependence. |
| 545 |
EXPECT_FALSE( |
| 546 |
isSafeToMoveBefore(*SI, *LI1->getNextNode(), DT, &PDT, &DI)); |
| 547 |
|
| 548 |
// Cannot move SI_A5 after SI, as there is a output dependence. |
| 549 |
EXPECT_FALSE(isSafeToMoveBefore(*SI_A5, *LI1, DT, &PDT, &DI)); |
| 550 |
|
| 551 |
// Can move LI2 before LI1, as there is only an input dependence. |
| 552 |
EXPECT_TRUE(isSafeToMoveBefore(*LI2, *LI1, DT, &PDT, &DI)); |
| 553 |
}); |
| 554 |
} |
| 555 |
|
| 556 |
TEST(CodeMoverUtils, IsSafeToMoveTest2) { |
| 557 |
LLVMContext C; |
| 558 |
|
| 559 |
std::unique_ptr<Module> M = |
| 560 |
parseIR(C, R"(define void @foo(i1 %cond, i32 %op0, i32 %op1) { |
| 561 |
entry: |
| 562 |
br i1 %cond, label %if.then.first, label %if.end.first |
| 563 |
if.then.first: |
| 564 |
%add = add i32 %op0, %op1 |
| 565 |
%user = add i32 %add, 1 |
| 566 |
br label %if.end.first |
| 567 |
if.end.first: |
| 568 |
br i1 %cond, label %if.then.second, label %if.end.second |
| 569 |
if.then.second: |
| 570 |
%sub_op0 = add i32 %op0, 1 |
| 571 |
%sub = sub i32 %sub_op0, %op1 |
| 572 |
br label %if.end.second |
| 573 |
if.end.second: |
| 574 |
ret void |
| 575 |
})"); |
| 576 |
|
| 577 |
run(*M, "foo", |
| 578 |
[&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, |
| 579 |
DependenceInfo &DI) { |
| 580 |
Instruction *AddInst = getInstructionByName(F, "add"); |
| 581 |
Instruction *SubInst = getInstructionByName(F, "sub"); |
| 582 |
|
| 583 |
// Cannot move as %user uses %add and %sub doesn't dominates %user. |
| 584 |
EXPECT_FALSE(isSafeToMoveBefore(*AddInst, *SubInst, DT, &PDT, &DI)); |
| 585 |
|
| 586 |
// Cannot move as %sub_op0 is an operand of %sub and %add doesn't |
| 587 |
// dominates %sub_op0. |
| 588 |
EXPECT_FALSE(isSafeToMoveBefore(*SubInst, *AddInst, DT, &PDT, &DI)); |
| 589 |
}); |
| 590 |
} |
| 591 |
|
| 592 |
TEST(CodeMoverUtils, IsSafeToMoveTest3) { |
| 593 |
LLVMContext C; |
| 594 |
|
| 595 |
std::unique_ptr<Module> M = parseIR(C, R"(define void @foo(i64 %N) { |
| 596 |
entry: |
| 597 |
br label %for.body |
| 598 |
for.body: |
| 599 |
%i = phi i64 [ 0, %entry ], [ %inc, %for.latch ] |
| 600 |
%inc = add nsw i64 %i, 1 |
| 601 |
br label %for.latch |
| 602 |
for.latch: |
| 603 |
%cmp = icmp slt i64 %inc, %N |
| 604 |
%add = add i64 100, %N |
| 605 |
%add2 = add i64 %add, %N |
| 606 |
br i1 %cmp, label %for.body, label %for.end |
| 607 |
for.end: |
| 608 |
ret void |
| 609 |
})"); |
| 610 |
|
| 611 |
run(*M, "foo", |
| 612 |
[&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, |
| 613 |
DependenceInfo &DI) { |
| 614 |
Instruction *IncInst = getInstructionByName(F, "inc"); |
| 615 |
Instruction *CmpInst = getInstructionByName(F, "cmp"); |
| 616 |
BasicBlock *BB0 = getBasicBlockByName(F, "for.body"); |
| 617 |
BasicBlock *BB1 = getBasicBlockByName(F, "for.latch"); |
| 618 |
|
| 619 |
// Can move as the incoming block of %inc for %i (%for.latch) dominated |
| 620 |
// by %cmp. |
| 621 |
EXPECT_TRUE(isSafeToMoveBefore(*IncInst, *CmpInst, DT, &PDT, &DI)); |
| 622 |
|
| 623 |
// Can move as the operands of instructions in BB1 either dominate |
| 624 |
// InsertPoint or appear before that instruction, e.g., %add appears |
| 625 |
// before %add2 although %add does not dominate InsertPoint. |
| 626 |
EXPECT_TRUE( |
| 627 |
isSafeToMoveBefore(*BB1, *BB0->getTerminator(), DT, &PDT, &DI)); |
| 628 |
}); |
| 629 |
} |
| 630 |
|
| 631 |
TEST(CodeMoverUtils, IsSafeToMoveTest4) { |
| 632 |
LLVMContext C; |
| 633 |
|
| 634 |
std::unique_ptr<Module> M = |
| 635 |
parseIR(C, R"(define void @foo(i1 %cond, i32 %op0, i32 %op1) { |
| 636 |
entry: |
| 637 |
br i1 %cond, label %if.end.first, label %if.then.first |
| 638 |
if.then.first: |
| 639 |
%add = add i32 %op0, %op1 |
| 640 |
%user = add i32 %add, 1 |
| 641 |
%add2 = add i32 %op0, 1 |
| 642 |
br label %if.end.first |
| 643 |
if.end.first: |
| 644 |
br i1 %cond, label %if.end.second, label %if.then.second |
| 645 |
if.then.second: |
| 646 |
%sub_op0 = add i32 %op0, 1 |
| 647 |
%sub = sub i32 %sub_op0, %op1 |
| 648 |
%sub2 = sub i32 %op0, 1 |
| 649 |
br label %if.end.second |
| 650 |
if.end.second: |
| 651 |
ret void |
| 652 |
})"); |
| 653 |
|
| 654 |
run(*M, "foo", |
| 655 |
[&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, |
| 656 |
DependenceInfo &DI) { |
| 657 |
Instruction *AddInst = getInstructionByName(F, "add"); |
| 658 |
Instruction *AddInst2 = getInstructionByName(F, "add2"); |
| 659 |
Instruction *SubInst = getInstructionByName(F, "sub"); |
| 660 |
Instruction *SubInst2 = getInstructionByName(F, "sub2"); |
| 661 |
|
| 662 |
// Cannot move as %user uses %add and %sub doesn't dominates %user. |
| 663 |
EXPECT_FALSE(isSafeToMoveBefore(*AddInst, *SubInst, DT, &PDT, &DI)); |
| 664 |
|
| 665 |
// Cannot move as %sub_op0 is an operand of %sub and %add doesn't |
| 666 |
// dominates %sub_op0. |
| 667 |
EXPECT_FALSE(isSafeToMoveBefore(*SubInst, *AddInst, DT, &PDT, &DI)); |
| 668 |
|
| 669 |
// Can move as %add2 and %sub2 are control flow equivalent, |
| 670 |
// although %add2 does not strictly dominate %sub2. |
| 671 |
EXPECT_TRUE(isSafeToMoveBefore(*AddInst2, *SubInst2, DT, &PDT, &DI)); |
| 672 |
|
| 673 |
// Can move as %add2 and %sub2 are control flow equivalent, |
| 674 |
// although %add2 does not strictly dominate %sub2. |
| 675 |
EXPECT_TRUE(isSafeToMoveBefore(*SubInst2, *AddInst2, DT, &PDT, &DI)); |
| 676 |
}); |
| 677 |
} |
| 678 |
|
| 679 |
TEST(CodeMoverUtils, IsSafeToMoveTest5) { |
| 680 |
LLVMContext C; |
| 681 |
|
| 682 |
std::unique_ptr<Module> M = |
| 683 |
parseIR(C, R"(define void @dependence(i32* noalias %A, i32* noalias %B){ |
| 684 |
entry: |
| 685 |
store i32 0, i32* %A, align 4 ; storeA0 |
| 686 |
store i32 2, i32* %A, align 4 ; storeA1 |
| 687 |
%tmp0 = load i32, i32* %A, align 4 ; loadA0 |
| 688 |
store i32 1, i32* %B, align 4 ; storeB0 |
| 689 |
%tmp1 = load i32, i32* %A, align 4 ; loadA1 |
| 690 |
store i32 2, i32* %A, align 4 ; storeA2 |
| 691 |
store i32 4, i32* %B, align 4 ; StoreB1 |
| 692 |
%tmp2 = load i32, i32* %A, align 4 ; loadA2 |
| 693 |
%tmp3 = load i32, i32* %A, align 4 ; loadA3 |
| 694 |
%tmp4 = load i32, i32* %B, align 4 ; loadB2 |
| 695 |
%tmp5 = load i32, i32* %B, align 4 ; loadB3 |
| 696 |
ret void |
| 697 |
})"); |
| 698 |
|
| 699 |
run(*M, "dependence", |
| 700 |
[&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, |
| 701 |
DependenceInfo &DI) { |
| 702 |
Instruction *LoadA0 = getInstructionByName(F, "tmp0"); |
| 703 |
Instruction *LoadA1 = getInstructionByName(F, "tmp1"); |
| 704 |
Instruction *LoadA2 = getInstructionByName(F, "tmp2"); |
| 705 |
Instruction *LoadA3 = getInstructionByName(F, "tmp3"); |
| 706 |
Instruction *LoadB2 = getInstructionByName(F, "tmp4"); |
| 707 |
Instruction *LoadB3 = getInstructionByName(F, "tmp5"); |
| 708 |
Instruction *StoreA1 = LoadA0->getPrevNode(); |
| 709 |
Instruction *StoreA0 = StoreA1->getPrevNode(); |
| 710 |
Instruction *StoreB0 = LoadA0->getNextNode(); |
| 711 |
Instruction *StoreB1 = LoadA2->getPrevNode(); |
| 712 |
Instruction *StoreA2 = StoreB1->getPrevNode(); |
| 713 |
|
| 714 |
// Input forward dependency |
| 715 |
EXPECT_TRUE(isSafeToMoveBefore(*LoadA2, *LoadB2, DT, &PDT, &DI)); |
| 716 |
// Input backward dependency |
| 717 |
EXPECT_TRUE(isSafeToMoveBefore(*LoadA3, *LoadA2, DT, &PDT, &DI)); |
| 718 |
|
| 719 |
// Output forward dependency |
| 720 |
EXPECT_FALSE(isSafeToMoveBefore(*StoreA0, *LoadA0, DT, &PDT, &DI)); |
| 721 |
// Output backward dependency |
| 722 |
EXPECT_FALSE(isSafeToMoveBefore(*StoreA1, *StoreA0, DT, &PDT, &DI)); |
| 723 |
|
| 724 |
// Flow forward dependency |
| 725 |
EXPECT_FALSE(isSafeToMoveBefore(*StoreA1, *StoreB0, DT, &PDT, &DI)); |
| 726 |
// Flow backward dependency |
| 727 |
EXPECT_FALSE(isSafeToMoveBefore(*LoadA0, *StoreA1, DT, &PDT, &DI)); |
| 728 |
|
| 729 |
// Anti forward dependency |
| 730 |
EXPECT_FALSE(isSafeToMoveBefore(*LoadA1, *StoreB1, DT, &PDT, &DI)); |
| 731 |
// Anti backward dependency |
| 732 |
EXPECT_FALSE(isSafeToMoveBefore(*StoreA2, *LoadA1, DT, &PDT, &DI)); |
| 733 |
|
| 734 |
// No input backward dependency |
| 735 |
EXPECT_TRUE(isSafeToMoveBefore(*LoadB2, *LoadA3, DT, &PDT, &DI)); |
| 736 |
// No input forward dependency |
| 737 |
EXPECT_TRUE(isSafeToMoveBefore(*LoadA3, *LoadB3, DT, &PDT, &DI)); |
| 738 |
|
| 739 |
// No Output forward dependency |
| 740 |
EXPECT_TRUE(isSafeToMoveBefore(*StoreA2, *LoadA2, DT, &PDT, &DI)); |
| 741 |
// No Output backward dependency |
| 742 |
EXPECT_TRUE(isSafeToMoveBefore(*StoreB1, *StoreA2, DT, &PDT, &DI)); |
| 743 |
|
| 744 |
// No flow forward dependency |
| 745 |
EXPECT_TRUE(isSafeToMoveBefore(*StoreB0, *StoreA2, DT, &PDT, &DI)); |
| 746 |
// No flow backward dependency |
| 747 |
EXPECT_TRUE(isSafeToMoveBefore(*LoadA1, *StoreB0, DT, &PDT, &DI)); |
| 748 |
|
| 749 |
// No anti backward dependency |
| 750 |
EXPECT_TRUE(isSafeToMoveBefore(*StoreB0, *LoadA0, DT, &PDT, &DI)); |
| 751 |
// No anti forward dependency |
| 752 |
EXPECT_TRUE(isSafeToMoveBefore(*LoadA0, *LoadA1, DT, &PDT, &DI)); |
| 753 |
}); |
| 754 |
} |
| 755 |
|
| 756 |
TEST(CodeMoverUtils, IsSafeToMoveTest6) { |
| 757 |
LLVMContext C; |
| 758 |
|
| 759 |
std::unique_ptr<Module> M = parseIR( |
| 760 |
C, R"(define void @dependence(i1 %cond, i32* noalias %A, i32* noalias %B){ |
| 761 |
entry: |
| 762 |
br i1 %cond, label %bb0, label %bb1 |
| 763 |
bb0: |
| 764 |
br label %bb1 |
| 765 |
bb1: |
| 766 |
store i32 0, i32* %A, align 4 ; storeA0 |
| 767 |
br i1 %cond, label %bb2, label %bb3 |
| 768 |
bb2: |
| 769 |
br label %bb3 |
| 770 |
bb3: |
| 771 |
store i32 2, i32* %A, align 4 ; storeA1 |
| 772 |
br i1 %cond, label %bb4, label %bb5 |
| 773 |
bb4: |
| 774 |
br label %bb5 |
| 775 |
bb5: |
| 776 |
%tmp0 = load i32, i32* %A, align 4 ; loadA0 |
| 777 |
br i1 %cond, label %bb6, label %bb7 |
| 778 |
bb6: |
| 779 |
br label %bb7 |
| 780 |
bb7: |
| 781 |
store i32 1, i32* %B, align 4 ; storeB0 |
| 782 |
br i1 %cond, label %bb8, label %bb9 |
| 783 |
bb8: |
| 784 |
br label %bb9 |
| 785 |
bb9: |
| 786 |
%tmp1 = load i32, i32* %A, align 4 ; loadA1 |
| 787 |
br i1 %cond, label %bb10, label %bb11 |
| 788 |
bb10: |
| 789 |
br label %bb11 |
| 790 |
bb11: |
| 791 |
store i32 2, i32* %A, align 4 ; storeA2 |
| 792 |
br i1 %cond, label %bb12, label %bb13 |
| 793 |
bb12: |
| 794 |
br label %bb13 |
| 795 |
bb13: |
| 796 |
store i32 4, i32* %B, align 4 ; StoreB1 |
| 797 |
br i1 %cond, label %bb14, label %bb15 |
| 798 |
bb14: |
| 799 |
br label %bb15 |
| 800 |
bb15: |
| 801 |
%tmp2 = load i32, i32* %A, align 4 ; loadA2 |
| 802 |
br i1 %cond, label %bb16, label %bb17 |
| 803 |
bb16: |
| 804 |
br label %bb17 |
| 805 |
bb17: |
| 806 |
%tmp3 = load i32, i32* %A, align 4 ; loadA3 |
| 807 |
br i1 %cond, label %bb18, label %bb19 |
| 808 |
bb18: |
| 809 |
br label %bb19 |
| 810 |
bb19: |
| 811 |
%tmp4 = load i32, i32* %B, align 4 ; loadB2 |
| 812 |
br i1 %cond, label %bb20, label %bb21 |
| 813 |
bb20: |
| 814 |
br label %bb21 |
| 815 |
bb21: |
| 816 |
%tmp5 = load i32, i32* %B, align 4 ; loadB3 |
| 817 |
ret void |
| 818 |
})"); |
| 819 |
run(*M, "dependence", |
| 820 |
[&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, |
| 821 |
DependenceInfo &DI) { |
| 822 |
BasicBlock *BB1 = getBasicBlockByName(F, "bb1"); |
| 823 |
BasicBlock *BB3 = getBasicBlockByName(F, "bb3"); |
| 824 |
BasicBlock *BB7 = getBasicBlockByName(F, "bb7"); |
| 825 |
BasicBlock *BB11 = getBasicBlockByName(F, "bb11"); |
| 826 |
BasicBlock *BB13 = getBasicBlockByName(F, "bb13"); |
| 827 |
Instruction *LoadA0 = getInstructionByName(F, "tmp0"); |
| 828 |
Instruction *LoadA1 = getInstructionByName(F, "tmp1"); |
| 829 |
Instruction *LoadA2 = getInstructionByName(F, "tmp2"); |
| 830 |
Instruction *LoadA3 = getInstructionByName(F, "tmp3"); |
| 831 |
Instruction *LoadB2 = getInstructionByName(F, "tmp4"); |
| 832 |
Instruction *LoadB3 = getInstructionByName(F, "tmp5"); |
| 833 |
Instruction &StoreA1 = BB3->front(); |
| 834 |
Instruction &StoreA0 = BB1->front(); |
| 835 |
Instruction &StoreB0 = BB7->front(); |
| 836 |
Instruction &StoreB1 = BB13->front(); |
| 837 |
Instruction &StoreA2 = BB11->front(); |
| 838 |
|
| 839 |
// Input forward dependency |
| 840 |
EXPECT_TRUE(isSafeToMoveBefore(*LoadA2, *LoadB2, DT, &PDT, &DI)); |
| 841 |
// Input backward dependency |
| 842 |
EXPECT_TRUE(isSafeToMoveBefore(*LoadA3, *LoadA2, DT, &PDT, &DI)); |
| 843 |
|
| 844 |
// Output forward dependency |
| 845 |
EXPECT_FALSE(isSafeToMoveBefore(StoreA0, *LoadA0, DT, &PDT, &DI)); |
| 846 |
// Output backward dependency |
| 847 |
EXPECT_FALSE(isSafeToMoveBefore(StoreA1, StoreA0, DT, &PDT, &DI)); |
| 848 |
|
| 849 |
// Flow forward dependency |
| 850 |
EXPECT_FALSE(isSafeToMoveBefore(StoreA1, StoreB0, DT, &PDT, &DI)); |
| 851 |
// Flow backward dependency |
| 852 |
EXPECT_FALSE(isSafeToMoveBefore(*LoadA0, StoreA1, DT, &PDT, &DI)); |
| 853 |
|
| 854 |
// Anti forward dependency |
| 855 |
EXPECT_FALSE(isSafeToMoveBefore(*LoadA1, StoreB1, DT, &PDT, &DI)); |
| 856 |
// Anti backward dependency |
| 857 |
EXPECT_FALSE(isSafeToMoveBefore(StoreA2, *LoadA1, DT, &PDT, &DI)); |
| 858 |
|
| 859 |
// No input backward dependency |
| 860 |
EXPECT_TRUE(isSafeToMoveBefore(*LoadB2, *LoadA3, DT, &PDT, &DI)); |
| 861 |
// No input forward dependency |
| 862 |
EXPECT_TRUE(isSafeToMoveBefore(*LoadA3, *LoadB3, DT, &PDT, &DI)); |
| 863 |
|
| 864 |
// No Output forward dependency |
| 865 |
EXPECT_TRUE(isSafeToMoveBefore(StoreA2, *LoadA2, DT, &PDT, &DI)); |
| 866 |
// No Output backward dependency |
| 867 |
EXPECT_TRUE(isSafeToMoveBefore(StoreB1, StoreA2, DT, &PDT, &DI)); |
| 868 |
|
| 869 |
// No flow forward dependency |
| 870 |
EXPECT_TRUE(isSafeToMoveBefore(StoreB0, StoreA2, DT, &PDT, &DI)); |
| 871 |
// No flow backward dependency |
| 872 |
EXPECT_TRUE(isSafeToMoveBefore(*LoadA1, StoreB0, DT, &PDT, &DI)); |
| 873 |
|
| 874 |
// No anti backward dependency |
| 875 |
EXPECT_TRUE(isSafeToMoveBefore(StoreB0, *LoadA0, DT, &PDT, &DI)); |
| 876 |
// No anti forward dependency |
| 877 |
EXPECT_TRUE(isSafeToMoveBefore(*LoadA0, *LoadA1, DT, &PDT, &DI)); |
| 878 |
}); |
| 879 |
} |