1 //===- SSAUpdaterBulk.cpp - Unit tests for SSAUpdaterBulk -----------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 10 #include "llvm/Transforms/Utils/SSAUpdaterBulk.h" 11 #include "llvm/AsmParser/Parser.h" 12 #include "llvm/IR/BasicBlock.h" 13 #include "llvm/IR/Dominators.h" 14 #include "llvm/IR/IRBuilder.h" 15 #include "llvm/IR/Instructions.h" 16 #include "llvm/IR/LLVMContext.h" 17 #include "llvm/IR/Module.h" 18 #include "gtest/gtest.h" 19 20 using namespace llvm; 21 22 TEST(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 %false 34 // true: 35 // %1 = add i32 %0, 1 36 // %2 = sub i32 %0, 2 37 // br label %merge 38 // false: 39 // %3 = add i32 %0, 3 40 // %4 = sub i32 %0, 4 41 // br label %merge 42 // merge: 43 // %5 = add i32 %1, 5 44 // %6 = add i32 %3, 6 45 // %7 = add i32 %2, %4 46 // %8 = sub i32 %2, %4 47 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, which 73 // SSAUpdater should insert into %merge. 74 // Intentionally don't touch %8 to see that SSAUpdater only changes 75 // 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 109 TEST(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, 1 121 // br i1 true, label %loopmain, label %loopstart 122 // 123 // loopstart: 124 // %2 = add i32 %0, 2 125 // br label %loopmain 126 // 127 // loopmain: 128 // %3 = add i32 %1, 3 129 // br i1 true, label %loopstart, label %afterloop 130 // 131 // afterloop: 132 // %4 = add i32 %2, 4 133 // ret i32 %0 134 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 a 157 // new phi, others should be able to work with existing values. 158 // The phi for %4 should be inserted into LoopMainBB and should look like 159 // 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
