530 lines · cpp
1//===- SSAUpdaterBulk.cpp - Unit tests for SSAUpdaterBulk -----------------===//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-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/Transforms/Utils/SSAUpdaterBulk.h"10#include "llvm/AsmParser/Parser.h"11#include "llvm/IR/BasicBlock.h"12#include "llvm/IR/Dominators.h"13#include "llvm/IR/IRBuilder.h"14#include "llvm/IR/Instructions.h"15#include "llvm/IR/LLVMContext.h"16#include "llvm/IR/Module.h"17#include "llvm/Support/SourceMgr.h"18#include "gtest/gtest.h"19 20using namespace llvm;21 22TEST(SSAUpdaterBulk, SimpleMerge) {23 SSAUpdaterBulk Updater;24 LLVMContext C;25 Module M("SSAUpdaterTest", C);26 IRBuilder<> B(C);27 Type *I32Ty = B.getInt32Ty();28 auto *F = Function::Create(FunctionType::get(B.getVoidTy(), {I32Ty}, false),29 GlobalValue::ExternalLinkage, "F", &M);30 31 // Generate a simple program:32 // if:33 // br i1 true, label %true, label %false34 // true:35 // %1 = add i32 %0, 136 // %2 = sub i32 %0, 237 // br label %merge38 // false:39 // %3 = add i32 %0, 340 // %4 = sub i32 %0, 441 // br label %merge42 // merge:43 // %5 = add i32 %1, 544 // %6 = add i32 %3, 645 // %7 = add i32 %2, %446 // %8 = sub i32 %2, %447 Argument *FirstArg = &*(F->arg_begin());48 BasicBlock *IfBB = BasicBlock::Create(C, "if", F);49 BasicBlock *TrueBB = BasicBlock::Create(C, "true", F);50 BasicBlock *FalseBB = BasicBlock::Create(C, "false", F);51 BasicBlock *MergeBB = BasicBlock::Create(C, "merge", F);52 53 B.SetInsertPoint(IfBB);54 B.CreateCondBr(B.getTrue(), TrueBB, FalseBB);55 56 B.SetInsertPoint(TrueBB);57 Value *AddOp1 = B.CreateAdd(FirstArg, ConstantInt::get(I32Ty, 1));58 Value *SubOp1 = B.CreateSub(FirstArg, ConstantInt::get(I32Ty, 2));59 B.CreateBr(MergeBB);60 61 B.SetInsertPoint(FalseBB);62 Value *AddOp2 = B.CreateAdd(FirstArg, ConstantInt::get(I32Ty, 3));63 Value *SubOp2 = B.CreateSub(FirstArg, ConstantInt::get(I32Ty, 4));64 B.CreateBr(MergeBB);65 66 B.SetInsertPoint(MergeBB, MergeBB->begin());67 auto *I1 = cast<Instruction>(B.CreateAdd(AddOp1, ConstantInt::get(I32Ty, 5)));68 auto *I2 = cast<Instruction>(B.CreateAdd(AddOp2, ConstantInt::get(I32Ty, 6)));69 auto *I3 = cast<Instruction>(B.CreateAdd(SubOp1, SubOp2));70 auto *I4 = cast<Instruction>(B.CreateSub(SubOp1, SubOp2));71 72 // Now rewrite uses in instructions %5, %6, %7. They need to use a phi, which73 // SSAUpdater should insert into %merge.74 // Intentionally don't touch %8 to see that SSAUpdater only changes75 // instructions that were explicitly specified.76 unsigned VarNum = Updater.AddVariable("a", I32Ty);77 Updater.AddAvailableValue(VarNum, TrueBB, AddOp1);78 Updater.AddAvailableValue(VarNum, FalseBB, AddOp2);79 Updater.AddUse(VarNum, &I1->getOperandUse(0));80 Updater.AddUse(VarNum, &I2->getOperandUse(0));81 82 VarNum = Updater.AddVariable("b", I32Ty);83 Updater.AddAvailableValue(VarNum, TrueBB, SubOp1);84 Updater.AddAvailableValue(VarNum, FalseBB, SubOp2);85 Updater.AddUse(VarNum, &I3->getOperandUse(0));86 Updater.AddUse(VarNum, &I3->getOperandUse(1));87 88 DominatorTree DT(*F);89 Updater.RewriteAllUses(&DT);90 91 // Check how %5 and %6 were rewritten.92 PHINode *UpdatePhiA = dyn_cast_or_null<PHINode>(I1->getOperand(0));93 EXPECT_NE(UpdatePhiA, nullptr);94 EXPECT_EQ(UpdatePhiA->getIncomingValueForBlock(TrueBB), AddOp1);95 EXPECT_EQ(UpdatePhiA->getIncomingValueForBlock(FalseBB), AddOp2);96 EXPECT_EQ(UpdatePhiA, dyn_cast_or_null<PHINode>(I1->getOperand(0)));97 98 // Check how %7 was rewritten.99 PHINode *UpdatePhiB = dyn_cast_or_null<PHINode>(I3->getOperand(0));100 EXPECT_EQ(UpdatePhiB->getIncomingValueForBlock(TrueBB), SubOp1);101 EXPECT_EQ(UpdatePhiB->getIncomingValueForBlock(FalseBB), SubOp2);102 EXPECT_EQ(UpdatePhiB, dyn_cast_or_null<PHINode>(I3->getOperand(1)));103 104 // Check that %8 was kept untouched.105 EXPECT_EQ(I4->getOperand(0), SubOp1);106 EXPECT_EQ(I4->getOperand(1), SubOp2);107}108 109TEST(SSAUpdaterBulk, Irreducible) {110 SSAUpdaterBulk Updater;111 LLVMContext C;112 Module M("SSAUpdaterTest", C);113 IRBuilder<> B(C);114 Type *I32Ty = B.getInt32Ty();115 auto *F = Function::Create(FunctionType::get(B.getVoidTy(), {I32Ty}, false),116 GlobalValue::ExternalLinkage, "F", &M);117 118 // Generate a small program with a multi-entry loop:119 // if:120 // %1 = add i32 %0, 1121 // br i1 true, label %loopmain, label %loopstart122 //123 // loopstart:124 // %2 = add i32 %0, 2125 // br label %loopmain126 //127 // loopmain:128 // %3 = add i32 %1, 3129 // br i1 true, label %loopstart, label %afterloop130 //131 // afterloop:132 // %4 = add i32 %2, 4133 // ret i32 %0134 Argument *FirstArg = &*F->arg_begin();135 BasicBlock *IfBB = BasicBlock::Create(C, "if", F);136 BasicBlock *LoopStartBB = BasicBlock::Create(C, "loopstart", F);137 BasicBlock *LoopMainBB = BasicBlock::Create(C, "loopmain", F);138 BasicBlock *AfterLoopBB = BasicBlock::Create(C, "afterloop", F);139 140 B.SetInsertPoint(IfBB);141 Value *AddOp1 = B.CreateAdd(FirstArg, ConstantInt::get(I32Ty, 1));142 B.CreateCondBr(B.getTrue(), LoopMainBB, LoopStartBB);143 144 B.SetInsertPoint(LoopStartBB);145 Value *AddOp2 = B.CreateAdd(FirstArg, ConstantInt::get(I32Ty, 2));146 B.CreateBr(LoopMainBB);147 148 B.SetInsertPoint(LoopMainBB);149 auto *I1 = cast<Instruction>(B.CreateAdd(AddOp1, ConstantInt::get(I32Ty, 3)));150 B.CreateCondBr(B.getTrue(), LoopStartBB, AfterLoopBB);151 152 B.SetInsertPoint(AfterLoopBB);153 auto *I2 = cast<Instruction>(B.CreateAdd(AddOp2, ConstantInt::get(I32Ty, 4)));154 ReturnInst *Return = B.CreateRet(FirstArg);155 156 // Now rewrite uses in instructions %3, %4, and 'ret i32 %0'. Only %4 needs a157 // new phi, others should be able to work with existing values.158 // The phi for %4 should be inserted into LoopMainBB and should look like159 // this:160 // %b = phi i32 [ %2, %loopstart ], [ undef, %if ]161 // No other rewrites should be made.162 163 // Add use in %3.164 unsigned VarNum = Updater.AddVariable("c", I32Ty);165 Updater.AddAvailableValue(VarNum, IfBB, AddOp1);166 Updater.AddUse(VarNum, &I1->getOperandUse(0));167 168 // Add use in %4.169 VarNum = Updater.AddVariable("b", I32Ty);170 Updater.AddAvailableValue(VarNum, LoopStartBB, AddOp2);171 Updater.AddUse(VarNum, &I2->getOperandUse(0));172 173 // Add use in the return instruction.174 VarNum = Updater.AddVariable("a", I32Ty);175 Updater.AddAvailableValue(VarNum, &F->getEntryBlock(), FirstArg);176 Updater.AddUse(VarNum, &Return->getOperandUse(0));177 178 // Save all inserted phis into a vector.179 SmallVector<PHINode *, 8> Inserted;180 DominatorTree DT(*F);181 Updater.RewriteAllUses(&DT, &Inserted);182 183 // Only one phi should have been inserted.184 EXPECT_EQ(Inserted.size(), 1u);185 186 // I1 and Return should use the same values as they used before.187 EXPECT_EQ(I1->getOperand(0), AddOp1);188 EXPECT_EQ(Return->getOperand(0), FirstArg);189 190 // I2 should use the new phi.191 PHINode *UpdatePhi = dyn_cast_or_null<PHINode>(I2->getOperand(0));192 EXPECT_NE(UpdatePhi, nullptr);193 EXPECT_EQ(UpdatePhi->getIncomingValueForBlock(LoopStartBB), AddOp2);194 EXPECT_EQ(UpdatePhi->getIncomingValueForBlock(IfBB), UndefValue::get(I32Ty));195}196 197TEST(SSAUpdaterBulk, SingleBBLoop) {198 const char *IR = R"(199 define void @main() {200 entry:201 br label %loop202 loop:203 %i = add i32 0, 1204 %cmp = icmp slt i32 %i, 42205 br i1 %cmp, label %loop, label %exit206 exit:207 ret void208 }209 )";210 211 llvm::LLVMContext Context;212 llvm::SMDiagnostic Err;213 std::unique_ptr<llvm::Module> M = llvm::parseAssemblyString(IR, Err, Context);214 ASSERT_NE(M, nullptr) << "Failed to parse IR: " << Err.getMessage();215 216 Function *F = M->getFunction("main");217 auto *Entry = &F->getEntryBlock();218 auto *Loop = Entry->getSingleSuccessor();219 auto *I = &Loop->front();220 221 // Rewrite first operand of "%i = add i32 0, 1" to use incoming values entry:0222 // or loop:%i (that is the value of %i from the previous iteration).223 SSAUpdaterBulk Updater;224 Type *I32Ty = Type::getInt32Ty(Context);225 unsigned PrevI = Updater.AddVariable("i.prev", I32Ty);226 Updater.AddAvailableValue(PrevI, Entry, ConstantInt::get(I32Ty, 0));227 Updater.AddAvailableValue(PrevI, Loop, I);228 Updater.AddUse(PrevI, &I->getOperandUse(0));229 230 SmallVector<PHINode *, 1> Inserted;231 DominatorTree DT(*F);232 Updater.RewriteAllUses(&DT, &Inserted);233 234#if 0 // Enable for debugging.235 Loop->dump();236 // Output:237 // loop: ; preds = %loop, %entry238 // %i.prev = phi i32 [ %i, %loop ], [ 0, %entry ]239 // %i = add i32 %i.prev, 1240 // %cmp = icmp slt i32 %i, 42241 // br i1 %cmp, label %loop, label %exit242#endif243 244 ASSERT_EQ(Inserted.size(), 1u);245 PHINode *Phi = Inserted[0];246 EXPECT_EQ(Phi, dyn_cast<PHINode>(I->getOperand(0)));247 EXPECT_EQ(Phi->getIncomingValueForBlock(Entry), ConstantInt::get(I32Ty, 0));248 EXPECT_EQ(Phi->getIncomingValueForBlock(Loop), I);249}250 251TEST(SSAUpdaterBulk, TwoBBLoop) {252 const char *IR = R"(253 define void @main() {254 entry:255 br label %loop_header256 loop_header:257 br label %loop258 loop:259 %i = add i32 0, 1260 %cmp = icmp slt i32 %i, 42261 br i1 %cmp, label %loop_header, label %exit262 exit:263 ret void264 }265 )";266 267 llvm::LLVMContext Context;268 llvm::SMDiagnostic Err;269 std::unique_ptr<llvm::Module> M = llvm::parseAssemblyString(IR, Err, Context);270 ASSERT_NE(M, nullptr) << "Failed to parse IR: " << Err.getMessage();271 272 Function *F = M->getFunction("main");273 auto *Entry = &F->getEntryBlock();274 auto *LoopHdr = Entry->getSingleSuccessor();275 auto *Loop = LoopHdr->getSingleSuccessor();276 auto *I = &Loop->front();277 278 // Rewrite first operand of "%i = add i32 0, 1" to use incoming values entry:0279 // or loop:%i (that is the value of %i from the previous iteration).280 SSAUpdaterBulk Updater;281 Type *I32Ty = Type::getInt32Ty(Context);282 unsigned PrevI = Updater.AddVariable("i.prev", I32Ty);283 Updater.AddAvailableValue(PrevI, Entry, ConstantInt::get(I32Ty, 0));284 Updater.AddAvailableValue(PrevI, Loop, I);285 Updater.AddUse(PrevI, &I->getOperandUse(0));286 287 SmallVector<PHINode *, 1> Inserted;288 DominatorTree DT(*F);289 Updater.RewriteAllUses(&DT, &Inserted);290 291#if 0 // Enable for debugging.292 LoopHdr->dump();293 Loop->dump();294 // Output:295 // loop_header: ; preds = %loop, %entry296 // %i.prev = phi i32 [ %i, %loop ], [ 0, %entry ]297 // br label %loop298 // loop: ; preds = %loop_header299 // %i = add i32 %i.prev, 1300 // %cmp = icmp slt i32 %i, 42301 // br i1 %cmp, label %loop_header, label %exit302#endif303 304 ASSERT_EQ(Inserted.size(), 1u);305 PHINode *Phi = Inserted[0];306 EXPECT_EQ(Phi, dyn_cast<PHINode>(I->getOperand(0)));307 EXPECT_EQ(Phi->getParent(), LoopHdr);308 EXPECT_EQ(Phi->getIncomingValueForBlock(Entry), ConstantInt::get(I32Ty, 0));309 EXPECT_EQ(Phi->getIncomingValueForBlock(Loop), I);310}311 312TEST(SSAUpdaterBulk, SimplifyPHIs) {313 const char *IR = R"(314 define void @main(i32 %val, i1 %cond) {315 entry:316 br i1 %cond, label %left, label %right317 left:318 %add = add i32 %val, 1319 br label %exit320 right:321 %sub = sub i32 %val, 1322 br label %exit323 exit:324 %phi = phi i32 [ %sub, %right ], [ %add, %left ]325 %cmp = icmp slt i32 0, 42326 ret void327 }328 )";329 330 llvm::LLVMContext Context;331 llvm::SMDiagnostic Err;332 std::unique_ptr<llvm::Module> M = llvm::parseAssemblyString(IR, Err, Context);333 ASSERT_NE(M, nullptr) << "Failed to parse IR: " << Err.getMessage();334 335 Function *F = M->getFunction("main");336 auto *Entry = &F->getEntryBlock();337 auto *Left = Entry->getTerminator()->getSuccessor(0);338 auto *Right = Entry->getTerminator()->getSuccessor(1);339 auto *Exit = Left->getSingleSuccessor();340 auto *Val = &*F->arg_begin();341 auto *Phi = &Exit->front();342 auto *Cmp = &*std::next(Exit->begin());343 auto *Add = &Left->front();344 auto *Sub = &Right->front();345 346 SSAUpdaterBulk Updater;347 Type *I32Ty = Type::getInt32Ty(Context);348 349 // Use %val directly instead of creating a phi.350 unsigned ValVar = Updater.AddVariable("Val", I32Ty);351 Updater.AddAvailableValue(ValVar, Left, Val);352 Updater.AddAvailableValue(ValVar, Right, Val);353 Updater.AddUse(ValVar, &Cmp->getOperandUse(0));354 355 // Use existing %phi for %add and %sub values.356 unsigned AddSubVar = Updater.AddVariable("AddSub", I32Ty);357 Updater.AddAvailableValue(AddSubVar, Left, Add);358 Updater.AddAvailableValue(AddSubVar, Right, Sub);359 Updater.AddUse(AddSubVar, &Cmp->getOperandUse(1));360 361 auto ExitSizeBefore = Exit->size();362 DominatorTree DT(*F);363 Updater.RewriteAndOptimizeAllUses(DT);364 365 // Output for Exit->dump():366 // exit: ; preds = %right, %left367 // %phi = phi i32 [ %sub, %right ], [ %add, %left ]368 // %cmp = icmp slt i32 %val, %phi369 // ret void370 371 ASSERT_EQ(Exit->size(), ExitSizeBefore);372 ASSERT_EQ(&Exit->front(), Phi);373 EXPECT_EQ(Val, Cmp->getOperand(0));374 EXPECT_EQ(Phi, Cmp->getOperand(1));375}376 377bool EliminateNewDuplicatePHINodes(BasicBlock *BB,378 BasicBlock::phi_iterator FirstExistingPN);379 380// Helper to run both versions on the same input.381static void RunEliminateNewDuplicatePHINode(382 const char *AsmText,383 std::function<void(BasicBlock &,384 bool(BasicBlock *BB, BasicBlock::phi_iterator))>385 Check) {386 LLVMContext C;387 388 SMDiagnostic Err;389 std::unique_ptr<Module> M = parseAssemblyString(AsmText, Err, C);390 if (!M) {391 Err.print("UtilsTests", errs());392 return;393 }394 395 Function *F = M->getFunction("main");396 auto BBIt = llvm::find_if(397 *F, [](const BasicBlock &Block) { return Block.getName() == "testbb"; });398 ASSERT_NE(BBIt, F->end());399 Check(*BBIt, EliminateNewDuplicatePHINodes);400}401 402static BasicBlock::phi_iterator getPhiIt(BasicBlock &BB, unsigned Idx) {403 return std::next(BB.phis().begin(), Idx);404}405 406static PHINode *getPhi(BasicBlock &BB, unsigned Idx) {407 return &*getPhiIt(BB, Idx);408}409 410static int getNumPHIs(BasicBlock &BB) {411 return std::distance(BB.phis().begin(), BB.phis().end());412}413 414TEST(SSAUpdaterBulk, EliminateNewDuplicatePHINodes_OrderExisting) {415 RunEliminateNewDuplicatePHINode(R"(416 define void @main() {417 entry:418 br label %testbb419 testbb:420 %np0 = phi i32 [ 1, %entry ]421 %np1 = phi i32 [ 1, %entry ]422 %ep0 = phi i32 [ 1, %entry ]423 %ep1 = phi i32 [ 1, %entry ]424 %u = add i32 %np0, %np1425 ret void426 }427 )", [](BasicBlock &BB, auto *ENDPN) {428 AssertingVH<PHINode> EP0 = getPhi(BB, 2);429 AssertingVH<PHINode> EP1 = getPhi(BB, 3);430 EXPECT_TRUE(ENDPN(&BB, getPhiIt(BB, 2)));431 // Expected:432 // %ep0 = phi i32 [ 1, %entry ]433 // %ep1 = phi i32 [ 1, %entry ]434 // %u = add i32 %ep0, %ep0435 EXPECT_EQ(getNumPHIs(BB), 2);436 Instruction &Add = *BB.getFirstNonPHIIt();437 EXPECT_EQ(Add.getOperand(0), EP0);438 EXPECT_EQ(Add.getOperand(1), EP0);439 (void)EP1; // Avoid "unused" warning.440 });441}442 443TEST(SSAUpdaterBulk, EliminateNewDuplicatePHINodes_OrderNew) {444 RunEliminateNewDuplicatePHINode(R"(445 define void @main() {446 entry:447 br label %testbb448 testbb:449 %np0 = phi i32 [ 1, %entry ]450 %np1 = phi i32 [ 1, %entry ]451 %ep0 = phi i32 [ 2, %entry ]452 %ep1 = phi i32 [ 2, %entry ]453 %u = add i32 %np0, %np1454 ret void455 }456 )", [](BasicBlock &BB, auto *ENDPN) {457 AssertingVH<PHINode> NP0 = getPhi(BB, 0);458 AssertingVH<PHINode> EP0 = getPhi(BB, 2);459 AssertingVH<PHINode> EP1 = getPhi(BB, 3);460 EXPECT_TRUE(ENDPN(&BB, getPhiIt(BB, 2)));461 // Expected:462 // %np0 = phi i32 [ 1, %entry ]463 // %ep0 = phi i32 [ 2, %entry ]464 // %ep1 = phi i32 [ 2, %entry ]465 // %u = add i32 %np0, %np0466 EXPECT_EQ(getNumPHIs(BB), 3);467 Instruction &Add = *BB.getFirstNonPHIIt();468 EXPECT_EQ(Add.getOperand(0), NP0);469 EXPECT_EQ(Add.getOperand(1), NP0);470 (void)EP0;471 (void)EP1; // Avoid "unused" warning.472 });473}474 475TEST(SSAUpdaterBulk, EliminateNewDuplicatePHINodes_NewRefExisting) {476 RunEliminateNewDuplicatePHINode(R"(477 define void @main() {478 entry:479 br label %testbb480 testbb:481 %np0 = phi i32 [ 1, %entry ], [ %ep0, %testbb ]482 %np1 = phi i32 [ 1, %entry ], [ %ep1, %testbb ]483 %ep0 = phi i32 [ 1, %entry ], [ %ep0, %testbb ]484 %ep1 = phi i32 [ 1, %entry ], [ %ep1, %testbb ]485 %u = add i32 %np0, %np1486 br label %testbb487 }488 )", [](BasicBlock &BB, auto *ENDPN) {489 AssertingVH<PHINode> EP0 = getPhi(BB, 2);490 AssertingVH<PHINode> EP1 = getPhi(BB, 3);491 EXPECT_TRUE(ENDPN(&BB, getPhiIt(BB, 2)));492 // Expected:493 // %ep0 = phi i32 [ 1, %entry ], [ %ep0, %testbb ]494 // %ep1 = phi i32 [ 1, %entry ], [ %ep1, %testbb ]495 // %u = add i32 %ep0, %ep1496 EXPECT_EQ(getNumPHIs(BB), 2);497 Instruction &Add = *BB.getFirstNonPHIIt();498 EXPECT_EQ(Add.getOperand(0), EP0);499 EXPECT_EQ(Add.getOperand(1), EP1);500 });501}502 503TEST(SSAUpdaterBulk, EliminateNewDuplicatePHINodes_ExistingRefNew) {504 RunEliminateNewDuplicatePHINode(R"(505 define void @main() {506 entry:507 br label %testbb508 testbb:509 %np0 = phi i32 [ 1, %entry ], [ %np0, %testbb ]510 %np1 = phi i32 [ 1, %entry ], [ %np1, %testbb ]511 %ep0 = phi i32 [ 1, %entry ], [ %np0, %testbb ]512 %ep1 = phi i32 [ 1, %entry ], [ %np1, %testbb ]513 %u = add i32 %np0, %np1514 br label %testbb515 }516 )", [](BasicBlock &BB, auto *ENDPN) {517 AssertingVH<PHINode> EP0 = getPhi(BB, 2);518 AssertingVH<PHINode> EP1 = getPhi(BB, 3);519 EXPECT_TRUE(ENDPN(&BB, getPhiIt(BB, 2)));520 // Expected:521 // %ep0 = phi i32 [ 1, %entry ], [ %ep0, %testbb ]522 // %ep1 = phi i32 [ 1, %entry ], [ %ep1, %testbb ]523 // %u = add i32 %ep0, %ep1524 EXPECT_EQ(getNumPHIs(BB), 2);525 Instruction &Add = *BB.getFirstNonPHIIt();526 EXPECT_EQ(Add.getOperand(0), EP0);527 EXPECT_EQ(Add.getOperand(1), EP1);528 });529}530