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-exception 6 // 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 "gtest/gtest.h" 18 19 using namespace llvm; 20 21 TEST(SSAUpdaterBulk, SimpleMerge) { 22 SSAUpdaterBulk Updater; 23 LLVMContext C; 24 Module M("SSAUpdaterTest", C); 25 IRBuilder<> B(C); 26 Type *I32Ty = B.getInt32Ty(); 27 auto *F = Function::Create(FunctionType::get(B.getVoidTy(), {I32Ty}, false), 28 GlobalValue::ExternalLinkage, "F", &M); 29 30 // Generate a simple program: 31 // if: 32 // br i1 true, label %true, label %false 33 // true: 34 // %1 = add i32 %0, 1 35 // %2 = sub i32 %0, 2 36 // br label %merge 37 // false: 38 // %3 = add i32 %0, 3 39 // %4 = sub i32 %0, 4 40 // br label %merge 41 // merge: 42 // %5 = add i32 %1, 5 43 // %6 = add i32 %3, 6 44 // %7 = add i32 %2, %4 45 // %8 = sub i32 %2, %4 46 Argument *FirstArg = &*(F->arg_begin()); 47 BasicBlock *IfBB = BasicBlock::Create(C, "if", F); 48 BasicBlock *TrueBB = BasicBlock::Create(C, "true", F); 49 BasicBlock *FalseBB = BasicBlock::Create(C, "false", F); 50 BasicBlock *MergeBB = BasicBlock::Create(C, "merge", F); 51 52 B.SetInsertPoint(IfBB); 53 B.CreateCondBr(B.getTrue(), TrueBB, FalseBB); 54 55 B.SetInsertPoint(TrueBB); 56 Value *AddOp1 = B.CreateAdd(FirstArg, ConstantInt::get(I32Ty, 1)); 57 Value *SubOp1 = B.CreateSub(FirstArg, ConstantInt::get(I32Ty, 2)); 58 B.CreateBr(MergeBB); 59 60 B.SetInsertPoint(FalseBB); 61 Value *AddOp2 = B.CreateAdd(FirstArg, ConstantInt::get(I32Ty, 3)); 62 Value *SubOp2 = B.CreateSub(FirstArg, ConstantInt::get(I32Ty, 4)); 63 B.CreateBr(MergeBB); 64 65 B.SetInsertPoint(MergeBB->begin()); 66 auto *I1 = cast<Instruction>(B.CreateAdd(AddOp1, ConstantInt::get(I32Ty, 5))); 67 auto *I2 = cast<Instruction>(B.CreateAdd(AddOp2, ConstantInt::get(I32Ty, 6))); 68 auto *I3 = cast<Instruction>(B.CreateAdd(SubOp1, SubOp2)); 69 auto *I4 = cast<Instruction>(B.CreateSub(SubOp1, SubOp2)); 70 71 // Now rewrite uses in instructions %5, %6, %7. They need to use a phi, which 72 // SSAUpdater should insert into %merge. 73 // Intentionally don't touch %8 to see that SSAUpdater only changes 74 // instructions that were explicitly specified. 75 unsigned VarNum = Updater.AddVariable("a", I32Ty); 76 Updater.AddAvailableValue(VarNum, TrueBB, AddOp1); 77 Updater.AddAvailableValue(VarNum, FalseBB, AddOp2); 78 Updater.AddUse(VarNum, &I1->getOperandUse(0)); 79 Updater.AddUse(VarNum, &I2->getOperandUse(0)); 80 81 VarNum = Updater.AddVariable("b", I32Ty); 82 Updater.AddAvailableValue(VarNum, TrueBB, SubOp1); 83 Updater.AddAvailableValue(VarNum, FalseBB, SubOp2); 84 Updater.AddUse(VarNum, &I3->getOperandUse(0)); 85 Updater.AddUse(VarNum, &I3->getOperandUse(1)); 86 87 DominatorTree DT(*F); 88 Updater.RewriteAllUses(&DT); 89 90 // Check how %5 and %6 were rewritten. 91 PHINode *UpdatePhiA = dyn_cast_or_null<PHINode>(I1->getOperand(0)); 92 EXPECT_NE(UpdatePhiA, nullptr); 93 EXPECT_EQ(UpdatePhiA->getIncomingValueForBlock(TrueBB), AddOp1); 94 EXPECT_EQ(UpdatePhiA->getIncomingValueForBlock(FalseBB), AddOp2); 95 EXPECT_EQ(UpdatePhiA, dyn_cast_or_null<PHINode>(I1->getOperand(0))); 96 97 // Check how %7 was rewritten. 98 PHINode *UpdatePhiB = dyn_cast_or_null<PHINode>(I3->getOperand(0)); 99 EXPECT_EQ(UpdatePhiB->getIncomingValueForBlock(TrueBB), SubOp1); 100 EXPECT_EQ(UpdatePhiB->getIncomingValueForBlock(FalseBB), SubOp2); 101 EXPECT_EQ(UpdatePhiB, dyn_cast_or_null<PHINode>(I3->getOperand(1))); 102 103 // Check that %8 was kept untouched. 104 EXPECT_EQ(I4->getOperand(0), SubOp1); 105 EXPECT_EQ(I4->getOperand(1), SubOp2); 106 } 107 108 TEST(SSAUpdaterBulk, Irreducible) { 109 SSAUpdaterBulk Updater; 110 LLVMContext C; 111 Module M("SSAUpdaterTest", C); 112 IRBuilder<> B(C); 113 Type *I32Ty = B.getInt32Ty(); 114 auto *F = Function::Create(FunctionType::get(B.getVoidTy(), {I32Ty}, false), 115 GlobalValue::ExternalLinkage, "F", &M); 116 117 // Generate a small program with a multi-entry loop: 118 // if: 119 // %1 = add i32 %0, 1 120 // br i1 true, label %loopmain, label %loopstart 121 // 122 // loopstart: 123 // %2 = add i32 %0, 2 124 // br label %loopmain 125 // 126 // loopmain: 127 // %3 = add i32 %1, 3 128 // br i1 true, label %loopstart, label %afterloop 129 // 130 // afterloop: 131 // %4 = add i32 %2, 4 132 // ret i32 %0 133 Argument *FirstArg = &*F->arg_begin(); 134 BasicBlock *IfBB = BasicBlock::Create(C, "if", F); 135 BasicBlock *LoopStartBB = BasicBlock::Create(C, "loopstart", F); 136 BasicBlock *LoopMainBB = BasicBlock::Create(C, "loopmain", F); 137 BasicBlock *AfterLoopBB = BasicBlock::Create(C, "afterloop", F); 138 139 B.SetInsertPoint(IfBB); 140 Value *AddOp1 = B.CreateAdd(FirstArg, ConstantInt::get(I32Ty, 1)); 141 B.CreateCondBr(B.getTrue(), LoopMainBB, LoopStartBB); 142 143 B.SetInsertPoint(LoopStartBB); 144 Value *AddOp2 = B.CreateAdd(FirstArg, ConstantInt::get(I32Ty, 2)); 145 B.CreateBr(LoopMainBB); 146 147 B.SetInsertPoint(LoopMainBB); 148 auto *I1 = cast<Instruction>(B.CreateAdd(AddOp1, ConstantInt::get(I32Ty, 3))); 149 B.CreateCondBr(B.getTrue(), LoopStartBB, AfterLoopBB); 150 151 B.SetInsertPoint(AfterLoopBB); 152 auto *I2 = cast<Instruction>(B.CreateAdd(AddOp2, ConstantInt::get(I32Ty, 4))); 153 ReturnInst *Return = B.CreateRet(FirstArg); 154 155 // Now rewrite uses in instructions %3, %4, and 'ret i32 %0'. Only %4 needs a 156 // new phi, others should be able to work with existing values. 157 // The phi for %4 should be inserted into LoopMainBB and should look like 158 // this: 159 // %b = phi i32 [ %2, %loopstart ], [ undef, %if ] 160 // No other rewrites should be made. 161 162 // Add use in %3. 163 unsigned VarNum = Updater.AddVariable("c", I32Ty); 164 Updater.AddAvailableValue(VarNum, IfBB, AddOp1); 165 Updater.AddUse(VarNum, &I1->getOperandUse(0)); 166 167 // Add use in %4. 168 VarNum = Updater.AddVariable("b", I32Ty); 169 Updater.AddAvailableValue(VarNum, LoopStartBB, AddOp2); 170 Updater.AddUse(VarNum, &I2->getOperandUse(0)); 171 172 // Add use in the return instruction. 173 VarNum = Updater.AddVariable("a", I32Ty); 174 Updater.AddAvailableValue(VarNum, &F->getEntryBlock(), FirstArg); 175 Updater.AddUse(VarNum, &Return->getOperandUse(0)); 176 177 // Save all inserted phis into a vector. 178 SmallVector<PHINode *, 8> Inserted; 179 DominatorTree DT(*F); 180 Updater.RewriteAllUses(&DT, &Inserted); 181 182 // Only one phi should have been inserted. 183 EXPECT_EQ(Inserted.size(), 1u); 184 185 // I1 and Return should use the same values as they used before. 186 EXPECT_EQ(I1->getOperand(0), AddOp1); 187 EXPECT_EQ(Return->getOperand(0), FirstArg); 188 189 // I2 should use the new phi. 190 PHINode *UpdatePhi = dyn_cast_or_null<PHINode>(I2->getOperand(0)); 191 EXPECT_NE(UpdatePhi, nullptr); 192 EXPECT_EQ(UpdatePhi->getIncomingValueForBlock(LoopStartBB), AddOp2); 193 EXPECT_EQ(UpdatePhi->getIncomingValueForBlock(IfBB), UndefValue::get(I32Ty)); 194 } 195