File: DeferredDominanceTest.cpp

package info (click to toggle)
llvm-toolchain-6.0 1:6.0.1-10
  • links: PTS, VCS
  • area: main
  • in suites: buster
  • size: 598,080 kB
  • sloc: cpp: 3,046,253; ansic: 595,057; asm: 271,965; python: 128,926; objc: 106,554; sh: 21,906; lisp: 10,191; pascal: 6,094; ml: 5,544; perl: 5,265; makefile: 2,227; cs: 2,027; xml: 686; php: 212; csh: 117
file content (344 lines) | stat: -rw-r--r-- 12,449 bytes parent folder | download | duplicates (4)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
//===- llvm/unittests/IR/DeferredDominanceTest.cpp - DDT unit tests -------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//

#include "llvm/AsmParser/Parser.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/Support/SourceMgr.h"
#include "gtest/gtest.h"

using namespace llvm;

static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context,
                                              StringRef ModuleStr) {
  SMDiagnostic Err;
  std::unique_ptr<Module> M = parseAssemblyString(ModuleStr, Err, Context);
  assert(M && "Bad LLVM IR?");
  return M;
}

TEST(DeferredDominance, BasicOperations) {
  StringRef FuncName = "f";
  StringRef ModuleString =
      "define i32 @f(i32 %i, i32 *%p) {\n"
      " bb0:\n"
      "   store i32 %i, i32 *%p\n"
      "   switch i32 %i, label %bb1 [\n"
      "     i32 0, label %bb2\n"
      "     i32 1, label %bb2\n"
      "     i32 2, label %bb3\n"
      "   ]\n"
      " bb1:\n"
      "   ret i32 1\n"
      " bb2:\n"
      "   ret i32 2\n"
      " bb3:\n"
      "   ret i32 3\n"
      "}\n";
  // Make the module.
  LLVMContext Context;
  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
  Function *F = M->getFunction(FuncName);
  ASSERT_NE(F, nullptr) << "Couldn't get function " << FuncName << ".";

  // Make the DDT.
  DominatorTree DT(*F);
  DeferredDominance DDT(DT);
  ASSERT_TRUE(DDT.flush().verify());

  Function::iterator FI = F->begin();
  BasicBlock *BB0 = &*FI++;
  BasicBlock *BB1 = &*FI++;
  BasicBlock *BB2 = &*FI++;
  BasicBlock *BB3 = &*FI++;

  // Test discards of invalid self-domination updates. These use the single
  // short-hand interface but are still queued inside DDT.
  DDT.deleteEdge(BB0, BB0);
  DDT.insertEdge(BB1, BB1);

  // Delete edge bb0 -> bb3 and push the update twice to verify duplicate
  // entries are discarded.
  std::vector<DominatorTree::UpdateType> Updates;
  Updates.reserve(4);
  Updates.push_back({DominatorTree::Delete, BB0, BB3});
  Updates.push_back({DominatorTree::Delete, BB0, BB3});

  // Unnecessary Insert: no edge bb1 -> bb2 after change to bb0.
  Updates.push_back({DominatorTree::Insert, BB1, BB2});
  // Unnecessary Delete: edge exists bb0 -> bb1 after change to bb0.
  Updates.push_back({DominatorTree::Delete, BB0, BB1});

  // CFG Change: remove edge bb0 -> bb3 and one duplicate edge bb0 -> bb2.
  EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 4u);
  BB0->getTerminator()->eraseFromParent();
  BranchInst::Create(BB1, BB2, ConstantInt::getTrue(F->getContext()), BB0);
  EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);

  // Deletion of a BasicBlock is an immediate event. We remove all uses to the
  // contained Instructions and change the Terminator to "unreachable" when
  // queued for deletion. Its parent is still F until DDT.flush() is called. We
  // don't defer this action because it can cause problems for other transforms
  // or analysis as it's part of the actual CFG. We only defer updates to the
  // DominatorTree. This code will crash if it is placed before the
  // BranchInst::Create() call above.
  ASSERT_FALSE(isa<UnreachableInst>(BB3->getTerminator()));
  EXPECT_FALSE(DDT.pendingDeletedBB(BB3));
  DDT.deleteBB(BB3);
  EXPECT_TRUE(DDT.pendingDeletedBB(BB3));
  ASSERT_TRUE(isa<UnreachableInst>(BB3->getTerminator()));
  EXPECT_EQ(BB3->getParent(), F);

  // Verify. Updates to DDT must be applied *after* all changes to the CFG
  // (including block deletion).
  DDT.applyUpdates(Updates);
  ASSERT_TRUE(DDT.flush().verify());
}

TEST(DeferredDominance, PairedUpdate) {
  StringRef FuncName = "f";
  StringRef ModuleString =
      "define i32 @f(i32 %i, i32 *%p) {\n"
      " bb0:\n"
      "   store i32 %i, i32 *%p\n"
      "   switch i32 %i, label %bb1 [\n"
      "     i32 0, label %bb2\n"
      "     i32 1, label %bb2\n"
      "   ]\n"
      " bb1:\n"
      "   ret i32 1\n"
      " bb2:\n"
      "   ret i32 2\n"
      "}\n";
  // Make the module.
  LLVMContext Context;
  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
  Function *F = M->getFunction(FuncName);
  ASSERT_NE(F, nullptr) << "Couldn't get function " << FuncName << ".";

  // Make the DDT.
  DominatorTree DT(*F);
  DeferredDominance DDT(DT);
  ASSERT_TRUE(DDT.flush().verify());

  Function::iterator FI = F->begin();
  BasicBlock *BB0 = &*FI++;
  BasicBlock *BB1 = &*FI++;
  BasicBlock *BB2 = &*FI++;

  // CFG Change: only edge from bb0 is bb0 -> bb1.
  EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 3u);
  BB0->getTerminator()->eraseFromParent();
  BranchInst::Create(BB1, BB0);
  EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);

  // Must be done after the CFG change. The applyUpdate() routine analyzes the
  // current state of the CFG.
  DDT.deleteEdge(BB0, BB2);

  // CFG Change: bb0 now has bb0 -> bb1 and bb0 -> bb2.
  // With this change no dominance has been altered from the original IR. DT
  // doesn't care if the type of TerminatorInstruction changed, only if the
  // unique edges have.
  EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
  BB0->getTerminator()->eraseFromParent();
  BranchInst::Create(BB1, BB2, ConstantInt::getTrue(F->getContext()), BB0);
  EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);

  // Must be done after the CFG change. The applyUpdate() routine analyzes the
  // current state of the CFG. This DDT update pairs with the previous one and
  // is cancelled out before ever applying updates to DT.
  DDT.insertEdge(BB0, BB2);

  // Test the empty DeletedBB list.
  EXPECT_FALSE(DDT.pendingDeletedBB(BB0));
  EXPECT_FALSE(DDT.pendingDeletedBB(BB1));
  EXPECT_FALSE(DDT.pendingDeletedBB(BB2));

  // The DT has no changes, this flush() simply returns a reference to the
  // internal DT calculated at the beginning of this test.
  ASSERT_TRUE(DDT.flush().verify());
}

TEST(DeferredDominance, ReplaceEntryBB) {
  StringRef FuncName = "f";
  StringRef ModuleString =
      "define i32 @f() {\n"
      "bb0:\n"
      "   br label %bb1\n"
      " bb1:\n"
      "   ret i32 1\n"
      "}\n";
  // Make the module.
  LLVMContext Context;
  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
  Function *F = M->getFunction(FuncName);
  ASSERT_NE(F, nullptr) << "Couldn't get function " << FuncName << ".";

  // Make the DDT.
  DominatorTree DT(*F);
  DeferredDominance DDT(DT);
  ASSERT_TRUE(DDT.flush().verify());

  Function::iterator FI = F->begin();
  BasicBlock *BB0 = &*FI++;
  BasicBlock *BB1 = &*FI++;

  // Add a block as the new function entry BB. We also link it to BB0.
  BasicBlock *NewEntry =
      BasicBlock::Create(F->getContext(), "new_entry", F, BB0);
  BranchInst::Create(BB0, NewEntry);
  EXPECT_EQ(F->begin()->getName(), NewEntry->getName());
  EXPECT_TRUE(&F->getEntryBlock() == NewEntry);

  // Insert the new edge between new_eentry -> bb0. Without this the
  // recalculate() call below will not actually recalculate the DT as there
  // are no changes pending and no blocks deleted.
  DDT.insertEdge(NewEntry, BB0);

  // Changing the Entry BB requires a full recalulation.
  DDT.recalculate(*F);
  ASSERT_TRUE(DDT.flush().verify());

  // CFG Change: remove new_edge -> bb0 and redirect to new_edge -> bb1.
  EXPECT_EQ(NewEntry->getTerminator()->getNumSuccessors(), 1u);
  NewEntry->getTerminator()->eraseFromParent();
  BranchInst::Create(BB1, NewEntry);
  EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);

  // Update the DDT. At this point bb0 now has no predecessors but is still a
  // Child of F.
  DDT.applyUpdates({{DominatorTree::Delete, NewEntry, BB0},
                    {DominatorTree::Insert, NewEntry, BB1}});
  ASSERT_TRUE(DDT.flush().verify());

  // Now remove bb0 from F.
  ASSERT_FALSE(isa<UnreachableInst>(BB0->getTerminator()));
  EXPECT_FALSE(DDT.pendingDeletedBB(BB0));
  DDT.deleteBB(BB0);
  EXPECT_TRUE(DDT.pendingDeletedBB(BB0));
  ASSERT_TRUE(isa<UnreachableInst>(BB0->getTerminator()));
  EXPECT_EQ(BB0->getParent(), F);

  // Perform a full recalculation of the DDT. It is not necessary here but we
  // do this to test the case when there are no pending DT updates but there are
  // pending deleted BBs.
  DDT.recalculate(*F);
  ASSERT_TRUE(DDT.flush().verify());
}

TEST(DeferredDominance, InheritedPreds) {
  StringRef FuncName = "f";
  StringRef ModuleString =
      "define i32 @f(i32 %i, i32 *%p) {\n"
      " bb0:\n"
      "   store i32 %i, i32 *%p\n"
      "   switch i32 %i, label %bb1 [\n"
      "     i32 2, label %bb2\n"
      "     i32 3, label %bb3\n"
      "   ]\n"
      " bb1:\n"
      "   br label %bb3\n"
      " bb2:\n"
      "   br label %bb3\n"
      " bb3:\n"
      "   ret i32 3\n"
      "}\n";
  // Make the module.
  LLVMContext Context;
  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
  Function *F = M->getFunction(FuncName);
  ASSERT_NE(F, nullptr) << "Couldn't get function " << FuncName << ".";

  // Make the DDT.
  DominatorTree DT(*F);
  DeferredDominance DDT(DT);
  ASSERT_TRUE(DDT.flush().verify());

  Function::iterator FI = F->begin();
  BasicBlock *BB0 = &*FI++;
  BasicBlock *BB1 = &*FI++;
  BasicBlock *BB2 = &*FI++;
  BasicBlock *BB3 = &*FI++;

  // There are several CFG locations where we have:
  //
  //   pred1..predN
  //    |        |
  //    +> curr <+    converted into:   pred1..predN curr
  //        |                            |        |
  //        v                            +> succ <+
  //       succ
  //
  // There is a specific shape of this we have to be careful of:
  //
  //   pred1..predN
  //   ||        |
  //   |+> curr <+    converted into:   pred1..predN curr
  //   |    |                            |        |
  //   |    v                            +> succ <+
  //   +-> succ
  //
  // While the final CFG form is functionally identical the updates to
  // DDT are not. In the first case we must have DDT.insertEdge(Pred1, Succ)
  // while in the latter case we must *NOT* have DDT.insertEdge(Pred1, Succ).

  // CFG Change: bb0 now only has bb0 -> bb1 and bb0 -> bb3. We are preparing to
  // remove bb2.
  EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 3u);
  BB0->getTerminator()->eraseFromParent();
  BranchInst::Create(BB1, BB3, ConstantInt::getTrue(F->getContext()), BB0);
  EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);

  // Remove bb2 from F. This has to happen before the call to applyUpdates() for
  // DDT to detect there is no longer an edge between bb2 -> bb3. The deleteBB()
  // method converts bb2's TI into "unreachable".
  ASSERT_FALSE(isa<UnreachableInst>(BB2->getTerminator()));
  EXPECT_FALSE(DDT.pendingDeletedBB(BB2));
  DDT.deleteBB(BB2);
  EXPECT_TRUE(DDT.pendingDeletedBB(BB2));
  ASSERT_TRUE(isa<UnreachableInst>(BB2->getTerminator()));
  EXPECT_EQ(BB2->getParent(), F);

  // Queue up the DDT updates.
  std::vector<DominatorTree::UpdateType> Updates;
  Updates.reserve(4);
  Updates.push_back({DominatorTree::Delete, BB0, BB2});
  Updates.push_back({DominatorTree::Delete, BB2, BB3});

  // Handle the specific shape case next.
  // CFG Change: bb0 now only branches to bb3. We are preparing to remove bb1.
  EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);
  BB0->getTerminator()->eraseFromParent();
  BranchInst::Create(BB3, BB0);
  EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);

  // Remove bb1 from F. This has to happen before the call to applyUpdates() for
  // DDT to detect there is no longer an edge between bb1 -> bb3. The deleteBB()
  // method converts bb1's TI into "unreachable".
  ASSERT_FALSE(isa<UnreachableInst>(BB1->getTerminator()));
  EXPECT_FALSE(DDT.pendingDeletedBB(BB1));
  DDT.deleteBB(BB1);
  EXPECT_TRUE(DDT.pendingDeletedBB(BB1));
  ASSERT_TRUE(isa<UnreachableInst>(BB1->getTerminator()));
  EXPECT_EQ(BB1->getParent(), F);

  // Update the DDT. In this case we don't call DDT.insertEdge(BB0, BB3) because
  // the edge previously existed at the start of this test when DT was first
  // created.
  Updates.push_back({DominatorTree::Delete, BB0, BB1});
  Updates.push_back({DominatorTree::Delete, BB1, BB3});

  // Verify everything.
  DDT.applyUpdates(Updates);
  ASSERT_TRUE(DDT.flush().verify());
}