| 1 |
//===- InjectorIRStrategyTest.cpp - Tests for injector strategy -----------===// |
| 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/ADT/DenseMap.h" |
| 10 |
#include "llvm/ADT/StringRef.h" |
| 11 |
#include "llvm/AsmParser/Parser.h" |
| 12 |
#include "llvm/AsmParser/SlotMapping.h" |
| 13 |
#include "llvm/FuzzMutate/IRMutator.h" |
| 14 |
#include "llvm/FuzzMutate/Operations.h" |
| 15 |
#include "llvm/FuzzMutate/RandomIRBuilder.h" |
| 16 |
#include "llvm/IR/FMF.h" |
| 17 |
#include "llvm/IR/Instructions.h" |
| 18 |
#include "llvm/IR/LLVMContext.h" |
| 19 |
#include "llvm/IR/Module.h" |
| 20 |
#include "llvm/IR/Verifier.h" |
| 21 |
#include "llvm/Support/SourceMgr.h" |
| 22 |
#include <random> |
| 23 |
|
| 24 |
#include "gtest/gtest.h" |
| 25 |
|
| 26 |
using namespace llvm; |
| 27 |
|
| 28 |
static constexpr int Seed = 5; |
| 29 |
|
| 30 |
namespace { |
| 31 |
|
| 32 |
std::unique_ptr<IRMutator> createInjectorMutator() { |
| 33 |
std::vector<TypeGetter> Types{ |
| 34 |
Type::getInt1Ty, Type::getInt8Ty, Type::getInt16Ty, Type::getInt32Ty, |
| 35 |
Type::getInt64Ty, Type::getFloatTy, Type::getDoubleTy}; |
| 36 |
|
| 37 |
std::vector<std::unique_ptr<IRMutationStrategy>> Strategies; |
| 38 |
Strategies.push_back(std::make_unique<InjectorIRStrategy>( |
| 39 |
InjectorIRStrategy::getDefaultOps())); |
| 40 |
|
| 41 |
return std::make_unique<IRMutator>(std::move(Types), std::move(Strategies)); |
| 42 |
} |
| 43 |
|
| 44 |
template <class Strategy> std::unique_ptr<IRMutator> createMutator() { |
| 45 |
std::vector<TypeGetter> Types{ |
| 46 |
Type::getInt1Ty, Type::getInt8Ty, Type::getInt16Ty, Type::getInt32Ty, |
| 47 |
Type::getInt64Ty, Type::getFloatTy, Type::getDoubleTy}; |
| 48 |
|
| 49 |
std::vector<std::unique_ptr<IRMutationStrategy>> Strategies; |
| 50 |
Strategies.push_back(std::make_unique<Strategy>()); |
| 51 |
|
| 52 |
return std::make_unique<IRMutator>(std::move(Types), std::move(Strategies)); |
| 53 |
} |
| 54 |
|
| 55 |
std::unique_ptr<Module> parseAssembly(const char *Assembly, |
| 56 |
LLVMContext &Context) { |
| 57 |
|
| 58 |
SMDiagnostic Error; |
| 59 |
std::unique_ptr<Module> M = parseAssemblyString(Assembly, Error, Context); |
| 60 |
|
| 61 |
std::string ErrMsg; |
| 62 |
raw_string_ostream OS(ErrMsg); |
| 63 |
Error.print("", OS); |
| 64 |
|
| 65 |
assert(M && !verifyModule(*M, &errs())); |
| 66 |
return M; |
| 67 |
} |
| 68 |
|
| 69 |
void IterateOnSource(StringRef Source, IRMutator &Mutator) { |
| 70 |
LLVMContext Ctx; |
| 71 |
|
| 72 |
for (int i = 0; i < 10; ++i) { |
| 73 |
auto M = parseAssembly(Source.data(), Ctx); |
| 74 |
ASSERT_TRUE(M && !verifyModule(*M, &errs())); |
| 75 |
|
| 76 |
Mutator.mutateModule(*M, Seed, Source.size(), Source.size() + 100); |
| 77 |
EXPECT_TRUE(!verifyModule(*M, &errs())); |
| 78 |
} |
| 79 |
} |
| 80 |
|
| 81 |
TEST(InjectorIRStrategyTest, EmptyModule) { |
| 82 |
// Test that we can inject into empty module |
| 83 |
|
| 84 |
LLVMContext Ctx; |
| 85 |
auto M = std::make_unique<Module>("M", Ctx); |
| 86 |
ASSERT_TRUE(M && !verifyModule(*M, &errs())); |
| 87 |
|
| 88 |
auto Mutator = createInjectorMutator(); |
| 89 |
ASSERT_TRUE(Mutator); |
| 90 |
|
| 91 |
Mutator->mutateModule(*M, Seed, 1, 1); |
| 92 |
EXPECT_TRUE(!verifyModule(*M, &errs())); |
| 93 |
} |
| 94 |
|
| 95 |
TEST(InstDeleterIRStrategyTest, EmptyFunction) { |
| 96 |
// Test that we don't crash even if we can't remove from one of the functions. |
| 97 |
|
| 98 |
StringRef Source = "" |
| 99 |
"define <8 x i32> @func1() {\n" |
| 100 |
"ret <8 x i32> undef\n" |
| 101 |
"}\n" |
| 102 |
"\n" |
| 103 |
"define i32 @func2() {\n" |
| 104 |
"%A9 = alloca i32\n" |
| 105 |
"%L6 = load i32, i32* %A9\n" |
| 106 |
"ret i32 %L6\n" |
| 107 |
"}\n"; |
| 108 |
|
| 109 |
auto Mutator = createMutator<InstDeleterIRStrategy>(); |
| 110 |
ASSERT_TRUE(Mutator); |
| 111 |
|
| 112 |
IterateOnSource(Source, *Mutator); |
| 113 |
} |
| 114 |
|
| 115 |
TEST(InstDeleterIRStrategyTest, PhiNodes) { |
| 116 |
// Test that inst deleter works correctly with the phi nodes. |
| 117 |
|
| 118 |
LLVMContext Ctx; |
| 119 |
StringRef Source = "\n\ |
| 120 |
define i32 @earlyreturncrash(i32 %x) {\n\ |
| 121 |
entry:\n\ |
| 122 |
switch i32 %x, label %sw.epilog [\n\ |
| 123 |
i32 1, label %sw.bb1\n\ |
| 124 |
]\n\ |
| 125 |
\n\ |
| 126 |
sw.bb1:\n\ |
| 127 |
br label %sw.epilog\n\ |
| 128 |
\n\ |
| 129 |
sw.epilog:\n\ |
| 130 |
%a.0 = phi i32 [ 7, %entry ], [ 9, %sw.bb1 ]\n\ |
| 131 |
%b.0 = phi i32 [ 10, %entry ], [ 4, %sw.bb1 ]\n\ |
| 132 |
ret i32 %a.0\n\ |
| 133 |
}"; |
| 134 |
|
| 135 |
auto Mutator = createMutator<InstDeleterIRStrategy>(); |
| 136 |
ASSERT_TRUE(Mutator); |
| 137 |
|
| 138 |
IterateOnSource(Source, *Mutator); |
| 139 |
} |
| 140 |
|
| 141 |
static void checkModifyNoUnsignedAndNoSignedWrap(StringRef Opc) { |
| 142 |
LLVMContext Ctx; |
| 143 |
std::string Source = std::string("\n\ |
| 144 |
define i32 @test(i32 %x) {\n\ |
| 145 |
%a = ") + Opc.str() + |
| 146 |
std::string(" i32 %x, 10\n\ |
| 147 |
ret i32 %a\n\ |
| 148 |
}"); |
| 149 |
|
| 150 |
auto Mutator = createMutator<InstModificationIRStrategy>(); |
| 151 |
ASSERT_TRUE(Mutator); |
| 152 |
|
| 153 |
auto M = parseAssembly(Source.data(), Ctx); |
| 154 |
auto &F = *M->begin(); |
| 155 |
auto *AddI = &*F.begin()->begin(); |
| 156 |
ASSERT_TRUE(M && !verifyModule(*M, &errs())); |
| 157 |
bool FoundNUW = false; |
| 158 |
bool FoundNSW = false; |
| 159 |
for (int i = 0; i < 100; ++i) { |
| 160 |
Mutator->mutateModule(*M, Seed + i, Source.size(), Source.size() + 100); |
| 161 |
EXPECT_TRUE(!verifyModule(*M, &errs())); |
| 162 |
FoundNUW |= AddI->hasNoUnsignedWrap(); |
| 163 |
FoundNSW |= AddI->hasNoSignedWrap(); |
| 164 |
} |
| 165 |
|
| 166 |
// The mutator should have added nuw and nsw during some mutations. |
| 167 |
EXPECT_TRUE(FoundNUW); |
| 168 |
EXPECT_TRUE(FoundNSW); |
| 169 |
} |
| 170 |
TEST(InstModificationIRStrategyTest, Add) { |
| 171 |
checkModifyNoUnsignedAndNoSignedWrap("add"); |
| 172 |
} |
| 173 |
|
| 174 |
TEST(InstModificationIRStrategyTest, Sub) { |
| 175 |
checkModifyNoUnsignedAndNoSignedWrap("sub"); |
| 176 |
} |
| 177 |
|
| 178 |
TEST(InstModificationIRStrategyTest, Mul) { |
| 179 |
checkModifyNoUnsignedAndNoSignedWrap("mul"); |
| 180 |
} |
| 181 |
|
| 182 |
TEST(InstModificationIRStrategyTest, Shl) { |
| 183 |
checkModifyNoUnsignedAndNoSignedWrap("shl"); |
| 184 |
} |
| 185 |
|
| 186 |
TEST(InstModificationIRStrategyTest, ICmp) { |
| 187 |
LLVMContext Ctx; |
| 188 |
StringRef Source = "\n\ |
| 189 |
define i1 @test(i32 %x) {\n\ |
| 190 |
%a = icmp eq i32 %x, 10\n\ |
| 191 |
ret i1 %a\n\ |
| 192 |
}"; |
| 193 |
|
| 194 |
auto Mutator = createMutator<InstModificationIRStrategy>(); |
| 195 |
ASSERT_TRUE(Mutator); |
| 196 |
|
| 197 |
auto M = parseAssembly(Source.data(), Ctx); |
| 198 |
auto &F = *M->begin(); |
| 199 |
CmpInst *CI = cast<CmpInst>(&*F.begin()->begin()); |
| 200 |
ASSERT_TRUE(M && !verifyModule(*M, &errs())); |
| 201 |
bool FoundNE = false; |
| 202 |
for (int i = 0; i < 100; ++i) { |
| 203 |
Mutator->mutateModule(*M, Seed + i, Source.size(), Source.size() + 100); |
| 204 |
EXPECT_TRUE(!verifyModule(*M, &errs())); |
| 205 |
FoundNE |= CI->getPredicate() == CmpInst::ICMP_NE; |
| 206 |
} |
| 207 |
|
| 208 |
EXPECT_TRUE(FoundNE); |
| 209 |
} |
| 210 |
|
| 211 |
TEST(InstModificationIRStrategyTest, GEP) { |
| 212 |
LLVMContext Ctx; |
| 213 |
StringRef Source = "\n\ |
| 214 |
define i32* @test(i32* %ptr) {\n\ |
| 215 |
%gep = getelementptr i32, i32* %ptr, i32 10\n\ |
| 216 |
ret i32* %gep\n\ |
| 217 |
}"; |
| 218 |
|
| 219 |
auto Mutator = createMutator<InstModificationIRStrategy>(); |
| 220 |
ASSERT_TRUE(Mutator); |
| 221 |
|
| 222 |
auto M = parseAssembly(Source.data(), Ctx); |
| 223 |
auto &F = *M->begin(); |
| 224 |
GetElementPtrInst *GEP = cast<GetElementPtrInst>(&*F.begin()->begin()); |
| 225 |
ASSERT_TRUE(M && !verifyModule(*M, &errs())); |
| 226 |
bool FoundInbounds = false; |
| 227 |
for (int i = 0; i < 100; ++i) { |
| 228 |
Mutator->mutateModule(*M, Seed + i, Source.size(), Source.size() + 100); |
| 229 |
EXPECT_TRUE(!verifyModule(*M, &errs())); |
| 230 |
FoundInbounds |= GEP->isInBounds(); |
| 231 |
} |
| 232 |
|
| 233 |
EXPECT_TRUE(FoundInbounds); |
| 234 |
} |
| 235 |
|
| 236 |
/// The caller has to guarantee that function argument are used in the SAME |
| 237 |
/// place as the operand. |
| 238 |
void VerfyOperandShuffled(StringRef Source, std::pair<int, int> ShuffleItems) { |
| 239 |
LLVMContext Ctx; |
| 240 |
auto Mutator = createMutator<InstModificationIRStrategy>(); |
| 241 |
ASSERT_TRUE(Mutator); |
| 242 |
|
| 243 |
auto M = parseAssembly(Source.data(), Ctx); |
| 244 |
auto &F = *M->begin(); |
| 245 |
Instruction *Inst = &*F.begin()->begin(); |
| 246 |
ASSERT_TRUE(M && !verifyModule(*M, &errs())); |
| 247 |
ASSERT_TRUE(Inst->getOperand(ShuffleItems.first) == |
| 248 |
dyn_cast<Value>(F.getArg(ShuffleItems.first))); |
| 249 |
ASSERT_TRUE(Inst->getOperand(ShuffleItems.second) == |
| 250 |
dyn_cast<Value>(F.getArg(ShuffleItems.second))); |
| 251 |
|
| 252 |
Mutator->mutateModule(*M, 0, Source.size(), Source.size() + 100); |
| 253 |
ASSERT_TRUE(!verifyModule(*M, &errs())); |
| 254 |
|
| 255 |
ASSERT_TRUE(Inst->getOperand(ShuffleItems.first) == |
| 256 |
dyn_cast<Value>(F.getArg(ShuffleItems.second))); |
| 257 |
ASSERT_TRUE(Inst->getOperand(ShuffleItems.second) == |
| 258 |
dyn_cast<Value>(F.getArg(ShuffleItems.first))); |
| 259 |
} |
| 260 |
|
| 261 |
TEST(InstModificationIRStrategyTest, ShuffleAnd) { |
| 262 |
StringRef Source = "\n\ |
| 263 |
define i32 @test(i32 %0, i32 %1) {\n\ |
| 264 |
%add = and i32 %0, %1\n\ |
| 265 |
ret i32 %add\n\ |
| 266 |
}"; |
| 267 |
VerfyOperandShuffled(Source, {0, 1}); |
| 268 |
} |
| 269 |
TEST(InstModificationIRStrategyTest, ShuffleSelect) { |
| 270 |
StringRef Source = "\n\ |
| 271 |
define i32 @test(i1 %0, i32 %1, i32 %2) {\n\ |
| 272 |
%select = select i1 %0, i32 %1, i32 %2\n\ |
| 273 |
ret i32 %select\n\ |
| 274 |
}"; |
| 275 |
VerfyOperandShuffled(Source, {1, 2}); |
| 276 |
} |
| 277 |
|
| 278 |
void VerfyDivDidntShuffle(StringRef Source) { |
| 279 |
LLVMContext Ctx; |
| 280 |
auto Mutator = createMutator<InstModificationIRStrategy>(); |
| 281 |
ASSERT_TRUE(Mutator); |
| 282 |
|
| 283 |
auto M = parseAssembly(Source.data(), Ctx); |
| 284 |
auto &F = *M->begin(); |
| 285 |
Instruction *Inst = &*F.begin()->begin(); |
| 286 |
ASSERT_TRUE(M && !verifyModule(*M, &errs())); |
| 287 |
|
| 288 |
EXPECT_TRUE(isa<Constant>(Inst->getOperand(0))); |
| 289 |
EXPECT_TRUE(Inst->getOperand(1) == dyn_cast<Value>(F.getArg(0))); |
| 290 |
|
| 291 |
Mutator->mutateModule(*M, Seed, Source.size(), Source.size() + 100); |
| 292 |
EXPECT_TRUE(!verifyModule(*M, &errs())); |
| 293 |
|
| 294 |
// Didn't shuffle. |
| 295 |
EXPECT_TRUE(isa<Constant>(Inst->getOperand(0))); |
| 296 |
EXPECT_TRUE(Inst->getOperand(1) == dyn_cast<Value>(F.getArg(0))); |
| 297 |
} |
| 298 |
TEST(InstModificationIRStrategyTest, DidntShuffleSDiv) { |
| 299 |
StringRef Source = "\n\ |
| 300 |
define i32 @test(i32 %0) {\n\ |
| 301 |
%div = sdiv i32 0, %0\n\ |
| 302 |
ret i32 %div\n\ |
| 303 |
}"; |
| 304 |
VerfyDivDidntShuffle(Source); |
| 305 |
} |
| 306 |
TEST(InstModificationIRStrategyTest, DidntShuffleFRem) { |
| 307 |
StringRef Source = "\n\ |
| 308 |
define <2 x double> @test(<2 x double> %0) {\n\ |
| 309 |
%div = frem <2 x double> <double 0.0, double 0.0>, %0\n\ |
| 310 |
ret <2 x double> %div\n\ |
| 311 |
}"; |
| 312 |
VerfyDivDidntShuffle(Source); |
| 313 |
} |
| 314 |
TEST(InstModificationIRStrategy, Exact) { |
| 315 |
LLVMContext Ctx; |
| 316 |
StringRef Source = "\n\ |
| 317 |
define i32 @test(i32 %a, i32 %b) {\n\ |
| 318 |
%c = ashr i32 %a, %b \n\ |
| 319 |
ret i32 %c\n\ |
| 320 |
}"; |
| 321 |
|
| 322 |
auto Mutator = createMutator<InstModificationIRStrategy>(); |
| 323 |
ASSERT_TRUE(Mutator); |
| 324 |
|
| 325 |
std::unique_ptr<Module> M = parseAssembly(Source.data(), Ctx); |
| 326 |
std::mt19937 mt(Seed); |
| 327 |
std::uniform_int_distribution<int> RandInt(INT_MIN, INT_MAX); |
| 328 |
auto &F = *M->begin(); |
| 329 |
BinaryOperator *AShr = cast<BinaryOperator>(&*F.begin()->begin()); |
| 330 |
bool FoundExact = false; |
| 331 |
for (int i = 0; i < 100; ++i) { |
| 332 |
Mutator->mutateModule(*M, RandInt(mt), Source.size(), Source.size() + 100); |
| 333 |
ASSERT_FALSE(verifyModule(*M, &errs())); |
| 334 |
FoundExact |= AShr->isExact(); |
| 335 |
} |
| 336 |
|
| 337 |
EXPECT_TRUE(FoundExact); |
| 338 |
} |
| 339 |
TEST(InstModificationIRStrategy, FastMath) { |
| 340 |
LLVMContext Ctx; |
| 341 |
StringRef Source = "\n\ |
| 342 |
declare [4 x <4 x double>] @vecdouble(double) \n\ |
| 343 |
define double @test(i1 %C, double %a, double %b) { \n\ |
| 344 |
Entry: \n\ |
| 345 |
br i1 %C, label %True, label %False \n\ |
| 346 |
True: \n\ |
| 347 |
br label %Exit \n\ |
| 348 |
False: \n\ |
| 349 |
br label %Exit \n\ |
| 350 |
Exit: \n\ |
| 351 |
%PHIi32 = phi i32 [1, %True], [2, %False] \n\ |
| 352 |
%PHIdouble = phi double [%a, %True], [%b, %False] \n\ |
| 353 |
%Call = call [4 x <4 x double>] @vecdouble(double %PHIdouble) \n\ |
| 354 |
%c = fneg double %PHIdouble \n\ |
| 355 |
%s = select i1 %C, double %a, double %b \n\ |
| 356 |
%d = fadd double %s, %c \n\ |
| 357 |
ret double %d \n\ |
| 358 |
}"; |
| 359 |
|
| 360 |
auto Mutator = createMutator<InstModificationIRStrategy>(); |
| 361 |
ASSERT_TRUE(Mutator); |
| 362 |
|
| 363 |
std::unique_ptr<Module> M = parseAssembly(Source.data(), Ctx); |
| 364 |
std::mt19937 mt(Seed); |
| 365 |
std::uniform_int_distribution<int> RandInt(INT_MIN, INT_MAX); |
| 366 |
DenseMap<Instruction *, bool> FPOpsHasFastMath; |
| 367 |
for (auto &F : *M) { |
| 368 |
for (auto &BB : F) { |
| 369 |
for (auto &I : BB) { |
| 370 |
Type *Ty = I.getType(); |
| 371 |
if (Ty->isFPOrFPVectorTy() || Ty->isArrayTy()) { |
| 372 |
FPOpsHasFastMath[&I] = false; |
| 373 |
} |
| 374 |
} |
| 375 |
} |
| 376 |
} |
| 377 |
ASSERT_TRUE(M && !verifyModule(*M, &errs())); |
| 378 |
for (int i = 0; i < 300; ++i) { |
| 379 |
Mutator->mutateModule(*M, RandInt(mt), Source.size(), Source.size() + 100); |
| 380 |
for (auto p : FPOpsHasFastMath) |
| 381 |
FPOpsHasFastMath[p.first] |= p.first->getFastMathFlags().any(); |
| 382 |
ASSERT_FALSE(verifyModule(*M, &errs())); |
| 383 |
} |
| 384 |
for (auto p : FPOpsHasFastMath) |
| 385 |
ASSERT_TRUE(p.second); |
| 386 |
} |
| 387 |
|
| 388 |
template <class Strategy> |
| 389 |
static void mutateAndVerifyModule(StringRef Source, int repeat = 100) { |
| 390 |
LLVMContext Ctx; |
| 391 |
auto Mutator = createMutator<Strategy>(); |
| 392 |
ASSERT_TRUE(Mutator); |
| 393 |
|
| 394 |
auto M = parseAssembly(Source.data(), Ctx); |
| 395 |
std::mt19937 mt(Seed); |
| 396 |
std::uniform_int_distribution<int> RandInt(INT_MIN, INT_MAX); |
| 397 |
for (int i = 0; i < repeat; i++) { |
| 398 |
Mutator->mutateModule(*M, RandInt(mt), Source.size(), Source.size() + 1024); |
| 399 |
ASSERT_FALSE(verifyModule(*M, &errs())); |
| 400 |
} |
| 401 |
} |
| 402 |
|
| 403 |
TEST(InsertCFGStrategy, CFG) { |
| 404 |
StringRef Source = "\n\ |
| 405 |
define i32 @test(i1 %C1, i1 %C2, i1 %C3, i16 %S1, i16 %S2, i32 %I1) { \n\ |
| 406 |
Entry: \n\ |
| 407 |
%I2 = add i32 %I1, 1 \n\ |
| 408 |
%C = and i1 %C1, %C2 \n\ |
| 409 |
br label %Body \n\ |
| 410 |
Body: \n\ |
| 411 |
%IB = add i32 %I1, %I2 \n\ |
| 412 |
%CB = and i1 %C1, %C \n\ |
| 413 |
br label %Exit \n\ |
| 414 |
Exit: \n\ |
| 415 |
%IE = add i32 %IB, %I2 \n\ |
| 416 |
%CE = and i1 %CB, %C \n\ |
| 417 |
ret i32 %IE \n\ |
| 418 |
}"; |
| 419 |
mutateAndVerifyModule<InsertCFGStrategy>(Source); |
| 420 |
} |
| 421 |
|
| 422 |
TEST(InsertPHIStrategy, PHI) { |
| 423 |
StringRef Source = "\n\ |
| 424 |
define void @test(i1 %C1, i1 %C2, i32 %I, double %FP) { \n\ |
| 425 |
Entry: \n\ |
| 426 |
%C = and i1 %C1, %C2 \n\ |
| 427 |
br i1 %C, label %LoopHead, label %Exit \n\ |
| 428 |
LoopHead: ; pred Entry, LoopBody \n\ |
| 429 |
switch i32 %I, label %Default [ \n\ |
| 430 |
i32 1, label %OnOne \n\ |
| 431 |
i32 2, label %OnTwo \n\ |
| 432 |
i32 3, label %OnThree \n\ |
| 433 |
] \n\ |
| 434 |
Default: \n\ |
| 435 |
br label %LoopBody \n\ |
| 436 |
OnOne: ; pred LoopHead \n\ |
| 437 |
%DFP = fmul double %FP, 2.0 \n\ |
| 438 |
%OnOneCond = fcmp ogt double %DFP, %FP \n\ |
| 439 |
br i1 %OnOneCond, label %LoopBody, label %Exit \n\ |
| 440 |
OnTwo: ; pred Entry \n\ |
| 441 |
br i1 %C1, label %OnThree, label %LoopBody \n\ |
| 442 |
OnThree: ; pred Entry, OnTwo, OnThree \n\ |
| 443 |
br i1 %C2, label %OnThree, label %LoopBody \n\ |
| 444 |
LoopBody: ; pred Default, OnOne, OnTwo, OnThree \n\ |
| 445 |
br label %LoopHead \n\ |
| 446 |
Exit: ; pred Entry, OnOne \n\ |
| 447 |
ret void \n\ |
| 448 |
}"; |
| 449 |
mutateAndVerifyModule<InsertPHIStrategy>(Source); |
| 450 |
} |
| 451 |
|
| 452 |
TEST(InsertPHIStrategy, PHIWithSameIncomingBlock) { |
| 453 |
LLVMContext Ctx; |
| 454 |
StringRef Source = "\n\ |
| 455 |
define void @test(i32 %I) { \n\ |
| 456 |
Entry: \n\ |
| 457 |
switch i32 %I, label %Exit [ \n\ |
| 458 |
i32 1, label %IdentCase \n\ |
| 459 |
i32 2, label %IdentCase \n\ |
| 460 |
i32 3, label %IdentCase \n\ |
| 461 |
i32 4, label %IdentCase \n\ |
| 462 |
] \n\ |
| 463 |
IdentCase: \n\ |
| 464 |
br label %Exit \n\ |
| 465 |
Exit: \n\ |
| 466 |
ret void \n\ |
| 467 |
}"; |
| 468 |
auto IPS = std::make_unique<InsertPHIStrategy>(); |
| 469 |
RandomIRBuilder IB(Seed, {IntegerType::getInt32Ty(Ctx)}); |
| 470 |
auto M = parseAssembly(Source.data(), Ctx); |
| 471 |
Function &F = *M->begin(); |
| 472 |
for (auto &BB : F) { |
| 473 |
IPS->mutate(BB, IB); |
| 474 |
ASSERT_FALSE(verifyModule(*M, &errs())); |
| 475 |
} |
| 476 |
} |
| 477 |
|
| 478 |
TEST(SinkInstructionStrategy, Operand) { |
| 479 |
StringRef Source = "\n\ |
| 480 |
define i32 @test(i1 %C1, i1 %C2, i1 %C3, i32 %I, i32 %J) { \n\ |
| 481 |
Entry: \n\ |
| 482 |
%I100 = add i32 %I, 100 \n\ |
| 483 |
switch i32 %I100, label %BB0 [ \n\ |
| 484 |
i32 42, label %BB1 \n\ |
| 485 |
] \n\ |
| 486 |
BB0: \n\ |
| 487 |
%IAJ = add i32 %I, %J \n\ |
| 488 |
%ISJ = sub i32 %I, %J \n\ |
| 489 |
br label %Exit \n\ |
| 490 |
BB1: \n\ |
| 491 |
%IJ = mul i32 %I, %J \n\ |
| 492 |
%C = and i1 %C2, %C3 \n\ |
| 493 |
br i1 %C, label %BB0, label %Exit \n\ |
| 494 |
Exit: \n\ |
| 495 |
ret i32 %I \n\ |
| 496 |
}"; |
| 497 |
mutateAndVerifyModule<SinkInstructionStrategy>(Source); |
| 498 |
} |
| 499 |
|
| 500 |
static void VerifyBlockShuffle(StringRef Source) { |
| 501 |
LLVMContext Ctx; |
| 502 |
auto Mutator = createMutator<ShuffleBlockStrategy>(); |
| 503 |
ASSERT_TRUE(Mutator); |
| 504 |
|
| 505 |
std::unique_ptr<Module> M = parseAssembly(Source.data(), Ctx); |
| 506 |
Function *F = &*M->begin(); |
| 507 |
DenseMap<BasicBlock *, int> PreShuffleInstCnt; |
| 508 |
for (BasicBlock &BB : *F) { |
| 509 |
PreShuffleInstCnt.insert({&BB, BB.size()}); |
| 510 |
} |
| 511 |
std::mt19937 mt(Seed); |
| 512 |
std::uniform_int_distribution<int> RandInt(INT_MIN, INT_MAX); |
| 513 |
for (int i = 0; i < 100; i++) { |
| 514 |
Mutator->mutateModule(*M, RandInt(mt), Source.size(), Source.size() + 1024); |
| 515 |
for (BasicBlock &BB : *F) { |
| 516 |
int PostShuffleIntCnt = BB.size(); |
| 517 |
EXPECT_EQ(PostShuffleIntCnt, PreShuffleInstCnt[&BB]); |
| 518 |
} |
| 519 |
EXPECT_FALSE(verifyModule(*M, &errs())); |
| 520 |
} |
| 521 |
} |
| 522 |
|
| 523 |
TEST(ShuffleBlockStrategy, ShuffleBlocks) { |
| 524 |
StringRef Source = "\n\ |
| 525 |
define i64 @test(i1 %0, i1 %1, i1 %2, i32 %3, i32 %4) { \n\ |
| 526 |
Entry: \n\ |
| 527 |
%A = alloca i32, i32 8, align 4 \n\ |
| 528 |
%E.1 = and i32 %3, %4 \n\ |
| 529 |
%E.2 = add i32 %4 , 1 \n\ |
| 530 |
%A.GEP.1 = getelementptr i32, ptr %A, i32 0 \n\ |
| 531 |
%A.GEP.2 = getelementptr i32, ptr %A.GEP.1, i32 1 \n\ |
| 532 |
%L.2 = load i32, ptr %A.GEP.2 \n\ |
| 533 |
%L.1 = load i32, ptr %A.GEP.1 \n\ |
| 534 |
%E.3 = sub i32 %E.2, %L.1 \n\ |
| 535 |
%Cond.1 = icmp eq i32 %E.3, %E.2 \n\ |
| 536 |
%Cond.2 = and i1 %0, %1 \n\ |
| 537 |
%Cond = or i1 %Cond.1, %Cond.2 \n\ |
| 538 |
br i1 %Cond, label %BB0, label %BB1 \n\ |
| 539 |
BB0: \n\ |
| 540 |
%Add = add i32 %L.1, %L.2 \n\ |
| 541 |
%Sub = sub i32 %L.1, %L.2 \n\ |
| 542 |
%Sub.1 = sub i32 %Sub, 12 \n\ |
| 543 |
%Cast.1 = bitcast i32 %4 to float \n\ |
| 544 |
%Add.2 = add i32 %3, 1 \n\ |
| 545 |
%Cast.2 = bitcast i32 %Add.2 to float \n\ |
| 546 |
%FAdd = fadd float %Cast.1, %Cast.2 \n\ |
| 547 |
%Add.3 = add i32 %L.2, %L.1 \n\ |
| 548 |
%Cast.3 = bitcast float %FAdd to i32 \n\ |
| 549 |
%Sub.2 = sub i32 %Cast.3, %Sub.1 \n\ |
| 550 |
%SExt = sext i32 %Cast.3 to i64 \n\ |
| 551 |
%A.GEP.3 = getelementptr i64, ptr %A, i32 1 \n\ |
| 552 |
store i64 %SExt, ptr %A.GEP.3 \n\ |
| 553 |
br label %Exit \n\ |
| 554 |
BB1: \n\ |
| 555 |
%PHI.1 = phi i32 [0, %Entry] \n\ |
| 556 |
%SExt.1 = sext i1 %Cond.2 to i32 \n\ |
| 557 |
%SExt.2 = sext i1 %Cond.1 to i32 \n\ |
| 558 |
%E.164 = zext i32 %E.1 to i64 \n\ |
| 559 |
%E.264 = zext i32 %E.2 to i64 \n\ |
| 560 |
%E.1264 = mul i64 %E.164, %E.264 \n\ |
| 561 |
%E.12 = trunc i64 %E.1264 to i32 \n\ |
| 562 |
%A.GEP.4 = getelementptr i32, ptr %A, i32 2 \n\ |
| 563 |
%A.GEP.5 = getelementptr i32, ptr %A.GEP.4, i32 2 \n\ |
| 564 |
store i32 %E.12, ptr %A.GEP.5 \n\ |
| 565 |
br label %Exit \n\ |
| 566 |
Exit: \n\ |
| 567 |
%PHI.2 = phi i32 [%Add, %BB0], [%E.3, %BB1] \n\ |
| 568 |
%PHI.3 = phi i64 [%SExt, %BB0], [%E.1264, %BB1] \n\ |
| 569 |
%ZExt = zext i32 %PHI.2 to i64 \n\ |
| 570 |
%Add.5 = add i64 %PHI.3, 3 \n\ |
| 571 |
ret i64 %Add.5 \n\ |
| 572 |
}"; |
| 573 |
VerifyBlockShuffle(Source); |
| 574 |
} |
| 575 |
|
| 576 |
TEST(ShuffleBlockStrategy, ShuffleLoop) { |
| 577 |
StringRef Source = "\n\ |
| 578 |
define i32 @foo(i32 %Left, i32 %Right) { \n\ |
| 579 |
Entry: \n\ |
| 580 |
%LPtr = alloca i32, align 4 \n\ |
| 581 |
%RPtr = alloca i32, align 4 \n\ |
| 582 |
%RetValPtr = alloca i32, align 4 \n\ |
| 583 |
store i32 %Left, ptr %LPtr, align 4 \n\ |
| 584 |
store i32 %Right, ptr %RPtr, align 4 \n\ |
| 585 |
store i32 0, ptr %RetValPtr, align 4 \n\ |
| 586 |
br label %LoopHead \n\ |
| 587 |
LoopHead: \n\ |
| 588 |
%L = load i32, ptr %LPtr, align 4 \n\ |
| 589 |
%R = load i32, ptr %RPtr, align 4 \n\ |
| 590 |
%C = icmp slt i32 %L, %R \n\ |
| 591 |
br i1 %C, label %LoopBody, label %Exit \n\ |
| 592 |
LoopBody: \n\ |
| 593 |
%OldL = load i32, ptr %LPtr, align 4 \n\ |
| 594 |
%NewL = add nsw i32 %OldL, 1 \n\ |
| 595 |
store i32 %NewL, ptr %LPtr, align 4 \n\ |
| 596 |
%OldRetVal = load i32, ptr %RetValPtr, align 4 \n\ |
| 597 |
%NewRetVal = add nsw i32 %OldRetVal, 1 \n\ |
| 598 |
store i32 %NewRetVal, ptr %RetValPtr, align 4 \n\ |
| 599 |
br label %LoopHead \n\ |
| 600 |
Exit: \n\ |
| 601 |
%RetVal = load i32, ptr %RetValPtr, align 4 \n\ |
| 602 |
ret i32 %RetVal \n\ |
| 603 |
}"; |
| 604 |
VerifyBlockShuffle(Source); |
| 605 |
} |
| 606 |
} // namespace |