| 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, 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 |
} |