clang -cc1 -cc1 -triple amd64-unknown-openbsd7.0 -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name BasicBlockUtils.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model static -mframe-pointer=all -relaxed-aliasing -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/usr/src/gnu/usr.bin/clang/libLLVM/obj -resource-dir /usr/local/lib/clang/13.0.0 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Analysis -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ASMParser -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/BinaryFormat -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Bitcode -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Bitcode -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Bitstream -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /include/llvm/CodeGen -I /include/llvm/CodeGen/PBQP -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/IR -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/IR -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Coroutines -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ProfileData/Coverage -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/CodeView -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/DWARF -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/MSF -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/PDB -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Demangle -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ExecutionEngine -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ExecutionEngine/JITLink -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ExecutionEngine/Orc -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend/OpenACC -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend/OpenMP -I /include/llvm/CodeGen/GlobalISel -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/IRReader -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/InstCombine -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/Transforms/InstCombine -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/LTO -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Linker -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/MC -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/MC/MCParser -I /include/llvm/CodeGen/MIRParser -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Object -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Option -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Passes -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ProfileData -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Scalar -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ADT -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Support -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/Symbolize -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Target -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Utils -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Vectorize -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/IPO -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include -I /usr/src/gnu/usr.bin/clang/libLLVM/../include -I /usr/src/gnu/usr.bin/clang/libLLVM/obj -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include -D NDEBUG -D __STDC_LIMIT_MACROS -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D LLVM_PREFIX="/usr" -internal-isystem /usr/include/c++/v1 -internal-isystem /usr/local/lib/clang/13.0.0/include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/usr/src/gnu/usr.bin/clang/libLLVM/obj -ferror-limit 19 -fvisibility-inlines-hidden -fwrapv -stack-protector 2 -fno-rtti -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -fno-builtin-malloc -fno-builtin-calloc -fno-builtin-realloc -fno-builtin-valloc -fno-builtin-free -fno-builtin-strdup -fno-builtin-strndup -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /home/ben/Projects/vmm/scan-build/2022-01-12-194120-40624-1 -x c++ /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
9 | |
10 | |
11 | |
12 | |
13 | |
14 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" |
15 | #include "llvm/ADT/ArrayRef.h" |
16 | #include "llvm/ADT/SmallPtrSet.h" |
17 | #include "llvm/ADT/SmallVector.h" |
18 | #include "llvm/ADT/Twine.h" |
19 | #include "llvm/Analysis/CFG.h" |
20 | #include "llvm/Analysis/DomTreeUpdater.h" |
21 | #include "llvm/Analysis/LoopInfo.h" |
22 | #include "llvm/Analysis/MemoryDependenceAnalysis.h" |
23 | #include "llvm/Analysis/MemorySSAUpdater.h" |
24 | #include "llvm/Analysis/PostDominators.h" |
25 | #include "llvm/IR/BasicBlock.h" |
26 | #include "llvm/IR/CFG.h" |
27 | #include "llvm/IR/Constants.h" |
28 | #include "llvm/IR/DebugInfoMetadata.h" |
29 | #include "llvm/IR/Dominators.h" |
30 | #include "llvm/IR/Function.h" |
31 | #include "llvm/IR/InstrTypes.h" |
32 | #include "llvm/IR/Instruction.h" |
33 | #include "llvm/IR/Instructions.h" |
34 | #include "llvm/IR/IntrinsicInst.h" |
35 | #include "llvm/IR/LLVMContext.h" |
36 | #include "llvm/IR/PseudoProbe.h" |
37 | #include "llvm/IR/Type.h" |
38 | #include "llvm/IR/User.h" |
39 | #include "llvm/IR/Value.h" |
40 | #include "llvm/IR/ValueHandle.h" |
41 | #include "llvm/Support/Casting.h" |
42 | #include "llvm/Support/Debug.h" |
43 | #include "llvm/Support/raw_ostream.h" |
44 | #include "llvm/Transforms/Utils/Local.h" |
45 | #include <cassert> |
46 | #include <cstdint> |
47 | #include <string> |
48 | #include <utility> |
49 | #include <vector> |
50 | |
51 | using namespace llvm; |
52 | |
53 | #define DEBUG_TYPE "basicblock-utils" |
54 | |
55 | void llvm::DetatchDeadBlocks( |
56 | ArrayRef<BasicBlock *> BBs, |
57 | SmallVectorImpl<DominatorTree::UpdateType> *Updates, |
58 | bool KeepOneInputPHIs) { |
59 | for (auto *BB : BBs) { |
60 | |
61 | |
62 | SmallPtrSet<BasicBlock *, 4> UniqueSuccessors; |
63 | for (BasicBlock *Succ : successors(BB)) { |
64 | Succ->removePredecessor(BB, KeepOneInputPHIs); |
65 | if (Updates && UniqueSuccessors.insert(Succ).second) |
66 | Updates->push_back({DominatorTree::Delete, BB, Succ}); |
67 | } |
68 | |
69 | |
70 | while (!BB->empty()) { |
71 | Instruction &I = BB->back(); |
72 | |
73 | |
74 | |
75 | |
76 | |
77 | if (!I.use_empty()) |
78 | I.replaceAllUsesWith(UndefValue::get(I.getType())); |
79 | BB->getInstList().pop_back(); |
80 | } |
81 | new UnreachableInst(BB->getContext(), BB); |
82 | assert(BB->getInstList().size() == 1 && |
83 | isa<UnreachableInst>(BB->getTerminator()) && |
84 | "The successor list of BB isn't empty before " |
85 | "applying corresponding DTU updates."); |
86 | } |
87 | } |
88 | |
89 | void llvm::DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU, |
90 | bool KeepOneInputPHIs) { |
91 | DeleteDeadBlocks({BB}, DTU, KeepOneInputPHIs); |
92 | } |
93 | |
94 | void llvm::DeleteDeadBlocks(ArrayRef <BasicBlock *> BBs, DomTreeUpdater *DTU, |
95 | bool KeepOneInputPHIs) { |
96 | #ifndef NDEBUG |
97 | |
98 | SmallPtrSet<BasicBlock *, 4> Dead(BBs.begin(), BBs.end()); |
99 | assert(Dead.size() == BBs.size() && "Duplicating blocks?"); |
100 | for (auto *BB : Dead) |
101 | for (BasicBlock *Pred : predecessors(BB)) |
102 | assert(Dead.count(Pred) && "All predecessors must be dead!"); |
103 | #endif |
104 | |
105 | SmallVector<DominatorTree::UpdateType, 4> Updates; |
106 | DetatchDeadBlocks(BBs, DTU ? &Updates : nullptr, KeepOneInputPHIs); |
107 | |
108 | if (DTU) |
109 | DTU->applyUpdates(Updates); |
110 | |
111 | for (BasicBlock *BB : BBs) |
112 | if (DTU) |
113 | DTU->deleteBB(BB); |
114 | else |
115 | BB->eraseFromParent(); |
116 | } |
117 | |
118 | bool llvm::EliminateUnreachableBlocks(Function &F, DomTreeUpdater *DTU, |
119 | bool KeepOneInputPHIs) { |
120 | df_iterator_default_set<BasicBlock*> Reachable; |
121 | |
122 | |
123 | for (BasicBlock *BB : depth_first_ext(&F, Reachable)) |
124 | (void)BB; |
125 | |
126 | |
127 | std::vector<BasicBlock*> DeadBlocks; |
128 | for (BasicBlock &BB : F) |
129 | if (!Reachable.count(&BB)) |
130 | DeadBlocks.push_back(&BB); |
131 | |
132 | |
133 | DeleteDeadBlocks(DeadBlocks, DTU, KeepOneInputPHIs); |
134 | |
135 | return !DeadBlocks.empty(); |
136 | } |
137 | |
138 | bool llvm::FoldSingleEntryPHINodes(BasicBlock *BB, |
139 | MemoryDependenceResults *MemDep) { |
140 | if (!isa<PHINode>(BB->begin())) |
141 | return false; |
142 | |
143 | while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) { |
144 | if (PN->getIncomingValue(0) != PN) |
145 | PN->replaceAllUsesWith(PN->getIncomingValue(0)); |
146 | else |
147 | PN->replaceAllUsesWith(UndefValue::get(PN->getType())); |
148 | |
149 | if (MemDep) |
150 | MemDep->removeInstruction(PN); |
151 | |
152 | PN->eraseFromParent(); |
153 | } |
154 | return true; |
155 | } |
156 | |
157 | bool llvm::DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI, |
158 | MemorySSAUpdater *MSSAU) { |
159 | |
160 | |
161 | SmallVector<WeakTrackingVH, 8> PHIs; |
162 | for (PHINode &PN : BB->phis()) |
163 | PHIs.push_back(&PN); |
164 | |
165 | bool Changed = false; |
166 | for (unsigned i = 0, e = PHIs.size(); i != e; ++i) |
167 | if (PHINode *PN = dyn_cast_or_null<PHINode>(PHIs[i].operator Value*())) |
168 | Changed |= RecursivelyDeleteDeadPHINode(PN, TLI, MSSAU); |
169 | |
170 | return Changed; |
171 | } |
172 | |
173 | bool llvm::MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU, |
174 | LoopInfo *LI, MemorySSAUpdater *MSSAU, |
175 | MemoryDependenceResults *MemDep, |
176 | bool PredecessorWithTwoSuccessors) { |
177 | if (BB->hasAddressTaken()) |
178 | return false; |
179 | |
180 | |
181 | BasicBlock *PredBB = BB->getUniquePredecessor(); |
182 | if (!PredBB) return false; |
183 | |
184 | |
185 | if (PredBB == BB) return false; |
186 | |
187 | if (PredBB->getTerminator()->isExceptionalTerminator()) |
188 | return false; |
189 | |
190 | |
191 | if (!PredecessorWithTwoSuccessors && PredBB->getUniqueSuccessor() != BB) |
192 | return false; |
193 | |
194 | |
195 | |
196 | BranchInst *PredBB_BI; |
197 | BasicBlock *NewSucc = nullptr; |
198 | unsigned FallThruPath; |
199 | if (PredecessorWithTwoSuccessors) { |
200 | if (!(PredBB_BI = dyn_cast<BranchInst>(PredBB->getTerminator()))) |
201 | return false; |
202 | BranchInst *BB_JmpI = dyn_cast<BranchInst>(BB->getTerminator()); |
203 | if (!BB_JmpI || !BB_JmpI->isUnconditional()) |
204 | return false; |
205 | NewSucc = BB_JmpI->getSuccessor(0); |
206 | FallThruPath = PredBB_BI->getSuccessor(0) == BB ? 0 : 1; |
207 | } |
208 | |
209 | |
210 | for (PHINode &PN : BB->phis()) |
211 | if (llvm::is_contained(PN.incoming_values(), &PN)) |
212 | return false; |
213 | |
214 | LLVM_DEBUG(dbgs() << "Merging: " << BB->getName() << " into " |
215 | << PredBB->getName() << "\n"); |
216 | |
217 | |
218 | SmallVector<AssertingVH<Value>, 4> IncomingValues; |
219 | if (isa<PHINode>(BB->front())) { |
220 | for (PHINode &PN : BB->phis()) |
221 | if (!isa<PHINode>(PN.getIncomingValue(0)) || |
222 | cast<PHINode>(PN.getIncomingValue(0))->getParent() != BB) |
223 | IncomingValues.push_back(PN.getIncomingValue(0)); |
224 | FoldSingleEntryPHINodes(BB, MemDep); |
225 | } |
226 | |
227 | |
228 | |
229 | std::vector<DominatorTree::UpdateType> Updates; |
230 | if (DTU) { |
231 | SmallPtrSet<BasicBlock *, 2> SuccsOfBB(succ_begin(BB), succ_end(BB)); |
232 | SmallPtrSet<BasicBlock *, 2> SuccsOfPredBB(succ_begin(PredBB), |
233 | succ_begin(PredBB)); |
234 | Updates.reserve(Updates.size() + 2 * SuccsOfBB.size() + 1); |
235 | |
236 | |
237 | |
238 | |
239 | |
240 | |
241 | for (BasicBlock *SuccOfBB : SuccsOfBB) |
242 | |
243 | if (!SuccsOfPredBB.contains(SuccOfBB)) |
244 | Updates.push_back({DominatorTree::Insert, PredBB, SuccOfBB}); |
245 | for (BasicBlock *SuccOfBB : SuccsOfBB) |
246 | Updates.push_back({DominatorTree::Delete, BB, SuccOfBB}); |
247 | Updates.push_back({DominatorTree::Delete, PredBB, BB}); |
248 | } |
249 | |
250 | Instruction *PTI = PredBB->getTerminator(); |
251 | Instruction *STI = BB->getTerminator(); |
252 | Instruction *Start = &*BB->begin(); |
253 | |
254 | |
255 | if (Start == STI) |
256 | Start = PTI; |
257 | |
258 | |
259 | PredBB->getInstList().splice(PTI->getIterator(), BB->getInstList(), |
260 | BB->begin(), STI->getIterator()); |
261 | |
262 | if (MSSAU) |
263 | MSSAU->moveAllAfterMergeBlocks(BB, PredBB, Start); |
264 | |
265 | |
266 | |
267 | BB->replaceAllUsesWith(PredBB); |
268 | |
269 | if (PredecessorWithTwoSuccessors) { |
270 | |
271 | BB->getInstList().pop_back(); |
272 | |
273 | |
274 | PredBB_BI->setSuccessor(FallThruPath, NewSucc); |
275 | } else { |
276 | |
277 | PredBB->getInstList().pop_back(); |
278 | |
279 | |
280 | PredBB->getInstList().splice(PredBB->end(), BB->getInstList()); |
281 | |
282 | |
283 | if (MSSAU) |
284 | if (MemoryUseOrDef *MUD = cast_or_null<MemoryUseOrDef>( |
285 | MSSAU->getMemorySSA()->getMemoryAccess(PredBB->getTerminator()))) |
286 | MSSAU->moveToPlace(MUD, PredBB, MemorySSA::End); |
287 | } |
288 | |
289 | new UnreachableInst(BB->getContext(), BB); |
290 | |
291 | |
292 | if (!PredBB->hasName()) |
293 | PredBB->takeName(BB); |
294 | |
295 | if (LI) |
296 | LI->removeBlock(BB); |
297 | |
298 | if (MemDep) |
299 | MemDep->invalidateCachedPredecessors(); |
300 | |
301 | if (DTU) |
302 | DTU->applyUpdates(Updates); |
303 | |
304 | |
305 | DeleteDeadBlock(BB, DTU); |
306 | |
307 | return true; |
308 | } |
309 | |
310 | bool llvm::MergeBlockSuccessorsIntoGivenBlocks( |
311 | SmallPtrSetImpl<BasicBlock *> &MergeBlocks, Loop *L, DomTreeUpdater *DTU, |
312 | LoopInfo *LI) { |
313 | assert(!MergeBlocks.empty() && "MergeBlocks should not be empty"); |
314 | |
315 | bool BlocksHaveBeenMerged = false; |
316 | while (!MergeBlocks.empty()) { |
317 | BasicBlock *BB = *MergeBlocks.begin(); |
318 | BasicBlock *Dest = BB->getSingleSuccessor(); |
319 | if (Dest && (!L || L->contains(Dest))) { |
320 | BasicBlock *Fold = Dest->getUniquePredecessor(); |
321 | (void)Fold; |
322 | if (MergeBlockIntoPredecessor(Dest, DTU, LI)) { |
323 | assert(Fold == BB && |
324 | "Expecting BB to be unique predecessor of the Dest block"); |
325 | MergeBlocks.erase(Dest); |
326 | BlocksHaveBeenMerged = true; |
327 | } else |
328 | MergeBlocks.erase(BB); |
329 | } else |
330 | MergeBlocks.erase(BB); |
331 | } |
332 | return BlocksHaveBeenMerged; |
333 | } |
334 | |
335 | |
336 | |
337 | |
338 | |
339 | |
340 | |
341 | |
342 | |
343 | |
344 | |
345 | |
346 | |
347 | |
348 | |
349 | |
350 | |
351 | |
352 | |
353 | |
354 | |
355 | |
356 | static bool removeRedundantDbgInstrsUsingBackwardScan(BasicBlock *BB) { |
357 | SmallVector<DbgValueInst *, 8> ToBeRemoved; |
358 | SmallDenseSet<DebugVariable> VariableSet; |
359 | for (auto &I : reverse(*BB)) { |
360 | if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(&I)) { |
361 | DebugVariable Key(DVI->getVariable(), |
362 | DVI->getExpression(), |
363 | DVI->getDebugLoc()->getInlinedAt()); |
364 | auto R = VariableSet.insert(Key); |
365 | |
366 | |
367 | |
368 | if (!R.second) |
369 | ToBeRemoved.push_back(DVI); |
370 | continue; |
371 | } |
372 | |
373 | |
374 | |
375 | VariableSet.clear(); |
376 | } |
377 | |
378 | for (auto &Instr : ToBeRemoved) |
379 | Instr->eraseFromParent(); |
380 | |
381 | return !ToBeRemoved.empty(); |
382 | } |
383 | |
384 | |
385 | |
386 | |
387 | |
388 | |
389 | |
390 | |
391 | |
392 | |
393 | |
394 | |
395 | |
396 | |
397 | |
398 | |
399 | |
400 | |
401 | |
402 | |
403 | static bool removeRedundantDbgInstrsUsingForwardScan(BasicBlock *BB) { |
404 | SmallVector<DbgValueInst *, 8> ToBeRemoved; |
405 | DenseMap<DebugVariable, std::pair<SmallVector<Value *, 4>, DIExpression *>> |
406 | VariableMap; |
407 | for (auto &I : *BB) { |
408 | if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(&I)) { |
409 | DebugVariable Key(DVI->getVariable(), |
410 | NoneType(), |
411 | DVI->getDebugLoc()->getInlinedAt()); |
412 | auto VMI = VariableMap.find(Key); |
413 | |
414 | |
415 | SmallVector<Value *, 4> Values(DVI->getValues()); |
416 | if (VMI == VariableMap.end() || VMI->second.first != Values || |
417 | VMI->second.second != DVI->getExpression()) { |
418 | VariableMap[Key] = {Values, DVI->getExpression()}; |
419 | continue; |
420 | } |
421 | |
422 | ToBeRemoved.push_back(DVI); |
423 | } |
424 | } |
425 | |
426 | for (auto &Instr : ToBeRemoved) |
427 | Instr->eraseFromParent(); |
428 | |
429 | return !ToBeRemoved.empty(); |
430 | } |
431 | |
432 | bool llvm::RemoveRedundantDbgInstrs(BasicBlock *BB) { |
433 | bool MadeChanges = false; |
434 | |
435 | |
436 | |
437 | |
438 | |
439 | |
440 | |
441 | |
442 | |
443 | |
444 | |
445 | MadeChanges |= removeRedundantDbgInstrsUsingBackwardScan(BB); |
446 | MadeChanges |= removeRedundantDbgInstrsUsingForwardScan(BB); |
447 | |
448 | if (MadeChanges) |
449 | LLVM_DEBUG(dbgs() << "Removed redundant dbg instrs from: " |
450 | << BB->getName() << "\n"); |
451 | return MadeChanges; |
452 | } |
453 | |
454 | void llvm::ReplaceInstWithValue(BasicBlock::InstListType &BIL, |
455 | BasicBlock::iterator &BI, Value *V) { |
456 | Instruction &I = *BI; |
457 | |
458 | I.replaceAllUsesWith(V); |
459 | |
460 | |
461 | if (I.hasName() && !V->hasName()) |
462 | V->takeName(&I); |
463 | |
464 | |
465 | BI = BIL.erase(BI); |
466 | } |
467 | |
468 | void llvm::ReplaceInstWithInst(BasicBlock::InstListType &BIL, |
469 | BasicBlock::iterator &BI, Instruction *I) { |
470 | assert(I->getParent() == nullptr && |
471 | "ReplaceInstWithInst: Instruction already inserted into basic block!"); |
472 | |
473 | |
474 | |
475 | if (!I->getDebugLoc()) |
476 | I->setDebugLoc(BI->getDebugLoc()); |
477 | |
478 | |
479 | BasicBlock::iterator New = BIL.insert(BI, I); |
480 | |
481 | |
482 | ReplaceInstWithValue(BIL, BI, I); |
483 | |
484 | |
485 | BI = New; |
486 | } |
487 | |
488 | void llvm::ReplaceInstWithInst(Instruction *From, Instruction *To) { |
489 | BasicBlock::iterator BI(From); |
490 | ReplaceInstWithInst(From->getParent()->getInstList(), BI, To); |
491 | } |
492 | |
493 | BasicBlock *llvm::SplitEdge(BasicBlock *BB, BasicBlock *Succ, DominatorTree *DT, |
494 | LoopInfo *LI, MemorySSAUpdater *MSSAU, |
495 | const Twine &BBName) { |
496 | unsigned SuccNum = GetSuccessorNumber(BB, Succ); |
497 | |
498 | Instruction *LatchTerm = BB->getTerminator(); |
499 | |
500 | CriticalEdgeSplittingOptions Options = |
501 | CriticalEdgeSplittingOptions(DT, LI, MSSAU).setPreserveLCSSA(); |
502 | |
503 | if ((isCriticalEdge(LatchTerm, SuccNum, Options.MergeIdenticalEdges))) { |
504 | |
505 | |
506 | if (Succ->isEHPad()) |
507 | return ehAwareSplitEdge(BB, Succ, nullptr, nullptr, Options, BBName); |
508 | |
509 | |
510 | return SplitKnownCriticalEdge(LatchTerm, SuccNum, Options, BBName); |
511 | } |
512 | |
513 | |
514 | |
515 | if (BasicBlock *SP = Succ->getSinglePredecessor()) { |
516 | |
517 | |
518 | assert(SP == BB && "CFG broken"); |
519 | SP = nullptr; |
520 | return SplitBlock(Succ, &Succ->front(), DT, LI, MSSAU, BBName, |
521 | true); |
522 | } |
523 | |
524 | |
525 | |
526 | assert(BB->getTerminator()->getNumSuccessors() == 1 && |
527 | "Should have a single succ!"); |
528 | return SplitBlock(BB, BB->getTerminator(), DT, LI, MSSAU, BBName); |
529 | } |
530 | |
531 | void llvm::setUnwindEdgeTo(Instruction *TI, BasicBlock *Succ) { |
532 | if (auto *II = dyn_cast<InvokeInst>(TI)) |
533 | II->setUnwindDest(Succ); |
534 | else if (auto *CS = dyn_cast<CatchSwitchInst>(TI)) |
535 | CS->setUnwindDest(Succ); |
536 | else if (auto *CR = dyn_cast<CleanupReturnInst>(TI)) |
537 | CR->setUnwindDest(Succ); |
538 | else |
539 | llvm_unreachable("unexpected terminator instruction"); |
540 | } |
541 | |
542 | void llvm::updatePhiNodes(BasicBlock *DestBB, BasicBlock *OldPred, |
543 | BasicBlock *NewPred, PHINode *Until) { |
544 | int BBIdx = 0; |
545 | for (PHINode &PN : DestBB->phis()) { |
546 | |
547 | |
548 | if (Until == &PN) |
549 | break; |
550 | |
551 | |
552 | |
553 | |
554 | |
555 | |
556 | if (PN.getIncomingBlock(BBIdx) != OldPred) |
557 | BBIdx = PN.getBasicBlockIndex(OldPred); |
558 | |
559 | assert(BBIdx != -1 && "Invalid PHI Index!"); |
560 | PN.setIncomingBlock(BBIdx, NewPred); |
561 | } |
562 | } |
563 | |
564 | BasicBlock *llvm::ehAwareSplitEdge(BasicBlock *BB, BasicBlock *Succ, |
565 | LandingPadInst *OriginalPad, |
566 | PHINode *LandingPadReplacement, |
567 | const CriticalEdgeSplittingOptions &Options, |
568 | const Twine &BBName) { |
569 | |
570 | auto *PadInst = Succ->getFirstNonPHI(); |
571 | if (!LandingPadReplacement && !PadInst->isEHPad()) |
572 | return SplitEdge(BB, Succ, Options.DT, Options.LI, Options.MSSAU, BBName); |
573 | |
574 | auto *LI = Options.LI; |
575 | SmallVector<BasicBlock *, 4> LoopPreds; |
576 | |
577 | |
578 | |
579 | if (Options.PreserveLoopSimplify && LI) { |
580 | if (Loop *BBLoop = LI->getLoopFor(BB)) { |
581 | |
582 | |
583 | |
584 | |
585 | |
586 | |
587 | |
588 | |
589 | |
590 | |
591 | for (BasicBlock *P : predecessors(Succ)) { |
592 | if (P == BB) |
593 | continue; |
594 | if (LI->getLoopFor(P) != BBLoop) { |
595 | |
596 | |
597 | LoopPreds.clear(); |
598 | break; |
599 | } |
600 | LoopPreds.push_back(P); |
601 | } |
602 | |
603 | |
604 | if (any_of(LoopPreds, [](BasicBlock *Pred) { |
605 | return isa<IndirectBrInst>(Pred->getTerminator()); |
606 | })) { |
607 | return nullptr; |
608 | } |
609 | } |
610 | } |
611 | |
612 | auto *NewBB = |
613 | BasicBlock::Create(BB->getContext(), BBName, BB->getParent(), Succ); |
614 | setUnwindEdgeTo(BB->getTerminator(), NewBB); |
615 | updatePhiNodes(Succ, BB, NewBB, LandingPadReplacement); |
616 | |
617 | if (LandingPadReplacement) { |
618 | auto *NewLP = OriginalPad->clone(); |
619 | auto *Terminator = BranchInst::Create(Succ, NewBB); |
620 | NewLP->insertBefore(Terminator); |
621 | LandingPadReplacement->addIncoming(NewLP, NewBB); |
622 | } else { |
623 | Value *ParentPad = nullptr; |
624 | if (auto *FuncletPad = dyn_cast<FuncletPadInst>(PadInst)) |
625 | ParentPad = FuncletPad->getParentPad(); |
626 | else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(PadInst)) |
627 | ParentPad = CatchSwitch->getParentPad(); |
628 | else if (auto *CleanupPad = dyn_cast<CleanupPadInst>(PadInst)) |
629 | ParentPad = CleanupPad->getParentPad(); |
630 | else if (auto *LandingPad = dyn_cast<LandingPadInst>(PadInst)) |
631 | ParentPad = LandingPad->getParent(); |
632 | else |
633 | llvm_unreachable("handling for other EHPads not implemented yet"); |
634 | |
635 | auto *NewCleanupPad = CleanupPadInst::Create(ParentPad, {}, BBName, NewBB); |
636 | CleanupReturnInst::Create(NewCleanupPad, Succ, NewBB); |
637 | } |
638 | |
639 | auto *DT = Options.DT; |
640 | auto *MSSAU = Options.MSSAU; |
641 | if (!DT && !LI) |
642 | return NewBB; |
643 | |
644 | if (DT) { |
645 | DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy); |
646 | SmallVector<DominatorTree::UpdateType, 3> Updates; |
647 | |
648 | Updates.push_back({DominatorTree::Insert, BB, NewBB}); |
649 | Updates.push_back({DominatorTree::Insert, NewBB, Succ}); |
650 | Updates.push_back({DominatorTree::Delete, BB, Succ}); |
651 | |
652 | DTU.applyUpdates(Updates); |
653 | DTU.flush(); |
654 | |
655 | if (MSSAU) { |
656 | MSSAU->applyUpdates(Updates, *DT); |
657 | if (VerifyMemorySSA) |
658 | MSSAU->getMemorySSA()->verifyMemorySSA(); |
659 | } |
660 | } |
661 | |
662 | if (LI) { |
663 | if (Loop *BBLoop = LI->getLoopFor(BB)) { |
664 | |
665 | |
666 | if (Loop *SuccLoop = LI->getLoopFor(Succ)) { |
667 | if (BBLoop == SuccLoop) { |
668 | |
669 | SuccLoop->addBasicBlockToLoop(NewBB, *LI); |
670 | } else if (BBLoop->contains(SuccLoop)) { |
671 | |
672 | BBLoop->addBasicBlockToLoop(NewBB, *LI); |
673 | } else if (SuccLoop->contains(BBLoop)) { |
674 | |
675 | SuccLoop->addBasicBlockToLoop(NewBB, *LI); |
676 | } else { |
677 | |
678 | |
679 | |
680 | |
681 | assert(SuccLoop->getHeader() == Succ && |
682 | "Should not create irreducible loops!"); |
683 | if (Loop *P = SuccLoop->getParentLoop()) |
684 | P->addBasicBlockToLoop(NewBB, *LI); |
685 | } |
686 | } |
687 | |
688 | |
689 | |
690 | if (!BBLoop->contains(Succ)) { |
691 | assert(!BBLoop->contains(NewBB) && |
692 | "Split point for loop exit is contained in loop!"); |
693 | |
694 | |
695 | if (Options.PreserveLCSSA) { |
696 | createPHIsForSplitLoopExit(BB, NewBB, Succ); |
697 | } |
698 | |
699 | if (!LoopPreds.empty()) { |
700 | BasicBlock *NewExitBB = SplitBlockPredecessors( |
701 | Succ, LoopPreds, "split", DT, LI, MSSAU, Options.PreserveLCSSA); |
702 | if (Options.PreserveLCSSA) |
703 | createPHIsForSplitLoopExit(LoopPreds, NewExitBB, Succ); |
704 | } |
705 | } |
706 | } |
707 | } |
708 | |
709 | return NewBB; |
710 | } |
711 | |
712 | void llvm::createPHIsForSplitLoopExit(ArrayRef<BasicBlock *> Preds, |
713 | BasicBlock *SplitBB, BasicBlock *DestBB) { |
714 | |
715 | assert((SplitBB->getFirstNonPHI() == SplitBB->getTerminator() || |
716 | SplitBB->isLandingPad()) && |
717 | "SplitBB has non-PHI nodes!"); |
718 | |
719 | |
720 | for (PHINode &PN : DestBB->phis()) { |
721 | int Idx = PN.getBasicBlockIndex(SplitBB); |
722 | assert(Idx >= 0 && "Invalid Block Index"); |
723 | Value *V = PN.getIncomingValue(Idx); |
724 | |
725 | |
726 | |
727 | if (const PHINode *VP = dyn_cast<PHINode>(V)) |
728 | if (VP->getParent() == SplitBB) |
729 | continue; |
730 | |
731 | |
732 | PHINode *NewPN = PHINode::Create( |
733 | PN.getType(), Preds.size(), "split", |
734 | SplitBB->isLandingPad() ? &SplitBB->front() : SplitBB->getTerminator()); |
735 | for (BasicBlock *BB : Preds) |
736 | NewPN->addIncoming(V, BB); |
737 | |
738 | |
739 | PN.setIncomingValue(Idx, NewPN); |
740 | } |
741 | } |
742 | |
743 | unsigned |
744 | llvm::SplitAllCriticalEdges(Function &F, |
745 | const CriticalEdgeSplittingOptions &Options) { |
746 | unsigned NumBroken = 0; |
747 | for (BasicBlock &BB : F) { |
748 | Instruction *TI = BB.getTerminator(); |
749 | if (TI->getNumSuccessors() > 1 && !isa<IndirectBrInst>(TI) && |
750 | !isa<CallBrInst>(TI)) |
751 | for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) |
752 | if (SplitCriticalEdge(TI, i, Options)) |
753 | ++NumBroken; |
754 | } |
755 | return NumBroken; |
756 | } |
757 | |
758 | static BasicBlock *SplitBlockImpl(BasicBlock *Old, Instruction *SplitPt, |
759 | DomTreeUpdater *DTU, DominatorTree *DT, |
760 | LoopInfo *LI, MemorySSAUpdater *MSSAU, |
761 | const Twine &BBName, bool Before) { |
762 | if (Before) { |
763 | DomTreeUpdater LocalDTU(DT, DomTreeUpdater::UpdateStrategy::Lazy); |
764 | return splitBlockBefore(Old, SplitPt, |
765 | DTU ? DTU : (DT ? &LocalDTU : nullptr), LI, MSSAU, |
766 | BBName); |
767 | } |
768 | BasicBlock::iterator SplitIt = SplitPt->getIterator(); |
769 | while (isa<PHINode>(SplitIt) || SplitIt->isEHPad()) { |
770 | ++SplitIt; |
771 | assert(SplitIt != SplitPt->getParent()->end()); |
772 | } |
773 | std::string Name = BBName.str(); |
774 | BasicBlock *New = Old->splitBasicBlock( |
775 | SplitIt, Name.empty() ? Old->getName() + ".split" : Name); |
776 | |
777 | |
778 | |
779 | if (LI) |
780 | if (Loop *L = LI->getLoopFor(Old)) |
781 | L->addBasicBlockToLoop(New, *LI); |
782 | |
783 | if (DTU) { |
784 | SmallVector<DominatorTree::UpdateType, 8> Updates; |
785 | |
786 | SmallPtrSet<BasicBlock *, 8> UniqueSuccessorsOfOld(succ_begin(New), |
787 | succ_end(New)); |
788 | Updates.push_back({DominatorTree::Insert, Old, New}); |
789 | Updates.reserve(Updates.size() + 2 * UniqueSuccessorsOfOld.size()); |
790 | for (BasicBlock *UniqueSuccessorOfOld : UniqueSuccessorsOfOld) { |
791 | Updates.push_back({DominatorTree::Insert, New, UniqueSuccessorOfOld}); |
792 | Updates.push_back({DominatorTree::Delete, Old, UniqueSuccessorOfOld}); |
793 | } |
794 | |
795 | DTU->applyUpdates(Updates); |
796 | } else if (DT) |
797 | |
798 | if (DomTreeNode *OldNode = DT->getNode(Old)) { |
799 | std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end()); |
800 | |
801 | DomTreeNode *NewNode = DT->addNewBlock(New, Old); |
802 | for (DomTreeNode *I : Children) |
803 | DT->changeImmediateDominator(I, NewNode); |
804 | } |
805 | |
806 | |
807 | |
808 | if (MSSAU) |
809 | MSSAU->moveAllAfterSpliceBlocks(Old, New, &*(New->begin())); |
810 | |
811 | return New; |
812 | } |
813 | |
814 | BasicBlock *llvm::SplitBlock(BasicBlock *Old, Instruction *SplitPt, |
815 | DominatorTree *DT, LoopInfo *LI, |
816 | MemorySSAUpdater *MSSAU, const Twine &BBName, |
817 | bool Before) { |
818 | return SplitBlockImpl(Old, SplitPt, nullptr, DT, LI, MSSAU, BBName, |
819 | Before); |
820 | } |
821 | BasicBlock *llvm::SplitBlock(BasicBlock *Old, Instruction *SplitPt, |
822 | DomTreeUpdater *DTU, LoopInfo *LI, |
823 | MemorySSAUpdater *MSSAU, const Twine &BBName, |
824 | bool Before) { |
825 | return SplitBlockImpl(Old, SplitPt, DTU, nullptr, LI, MSSAU, BBName, |
826 | Before); |
827 | } |
828 | |
829 | BasicBlock *llvm::splitBlockBefore(BasicBlock *Old, Instruction *SplitPt, |
830 | DomTreeUpdater *DTU, LoopInfo *LI, |
831 | MemorySSAUpdater *MSSAU, |
832 | const Twine &BBName) { |
833 | |
834 | BasicBlock::iterator SplitIt = SplitPt->getIterator(); |
835 | while (isa<PHINode>(SplitIt) || SplitIt->isEHPad()) |
836 | ++SplitIt; |
837 | std::string Name = BBName.str(); |
838 | BasicBlock *New = Old->splitBasicBlock( |
839 | SplitIt, Name.empty() ? Old->getName() + ".split" : Name, |
840 | true); |
841 | |
842 | |
843 | |
844 | if (LI) |
845 | if (Loop *L = LI->getLoopFor(Old)) |
846 | L->addBasicBlockToLoop(New, *LI); |
847 | |
848 | if (DTU) { |
849 | SmallVector<DominatorTree::UpdateType, 8> DTUpdates; |
850 | |
851 | |
852 | SmallPtrSet<BasicBlock *, 8> UniquePredecessorsOfOld(pred_begin(New), |
853 | pred_end(New)); |
854 | DTUpdates.push_back({DominatorTree::Insert, New, Old}); |
855 | DTUpdates.reserve(DTUpdates.size() + 2 * UniquePredecessorsOfOld.size()); |
856 | for (BasicBlock *UniquePredecessorOfOld : UniquePredecessorsOfOld) { |
857 | DTUpdates.push_back({DominatorTree::Insert, UniquePredecessorOfOld, New}); |
858 | DTUpdates.push_back({DominatorTree::Delete, UniquePredecessorOfOld, Old}); |
859 | } |
860 | |
861 | DTU->applyUpdates(DTUpdates); |
862 | |
863 | |
864 | |
865 | if (MSSAU) { |
866 | MSSAU->applyUpdates(DTUpdates, DTU->getDomTree()); |
867 | if (VerifyMemorySSA) |
868 | MSSAU->getMemorySSA()->verifyMemorySSA(); |
869 | } |
870 | } |
871 | return New; |
872 | } |
873 | |
874 | |
875 | static void UpdateAnalysisInformation(BasicBlock *OldBB, BasicBlock *NewBB, |
876 | ArrayRef<BasicBlock *> Preds, |
877 | DomTreeUpdater *DTU, DominatorTree *DT, |
878 | LoopInfo *LI, MemorySSAUpdater *MSSAU, |
879 | bool PreserveLCSSA, bool &HasLoopExit) { |
880 | |
881 | if (DTU) { |
| |
| |
882 | |
883 | |
884 | if (NewBB->isEntryBlock() && DTU->hasDomTree()) { |
885 | |
886 | |
887 | |
888 | DTU->recalculate(*NewBB->getParent()); |
889 | } else { |
890 | |
891 | SmallVector<DominatorTree::UpdateType, 8> Updates; |
892 | SmallPtrSet<BasicBlock *, 8> UniquePreds(Preds.begin(), Preds.end()); |
893 | Updates.push_back({DominatorTree::Insert, NewBB, OldBB}); |
894 | Updates.reserve(Updates.size() + 2 * UniquePreds.size()); |
895 | for (auto *UniquePred : UniquePreds) { |
896 | Updates.push_back({DominatorTree::Insert, UniquePred, NewBB}); |
897 | Updates.push_back({DominatorTree::Delete, UniquePred, OldBB}); |
898 | } |
899 | DTU->applyUpdates(Updates); |
900 | } |
901 | } else if (DT) { |
| |
902 | if (OldBB == DT->getRootNode()->getBlock()) { |
903 | assert(NewBB->isEntryBlock()); |
904 | DT->setNewRoot(NewBB); |
905 | } else { |
906 | |
907 | DT->splitBlock(NewBB); |
908 | } |
909 | } |
910 | |
911 | |
912 | if (MSSAU) |
| 10 | | Assuming 'MSSAU' is null | |
|
| |
913 | MSSAU->wireOldPredecessorsToNewImmediatePredecessor(OldBB, NewBB, Preds); |
914 | |
915 | |
916 | if (!LI) |
| 12 | | Assuming 'LI' is non-null | |
|
| |
917 | return; |
918 | |
919 | if (DTU && DTU->hasDomTree()) |
920 | DT = &DTU->getDomTree(); |
921 | assert(DT && "DT should be available to update LoopInfo!"); |
922 | Loop *L = LI->getLoopFor(OldBB); |
923 | |
924 | |
925 | |
926 | bool IsLoopEntry = !!L; |
| 14 | | Assuming 'L' is non-null | |
|
927 | bool SplitMakesNewLoopHeader = false; |
928 | for (BasicBlock *Pred : Preds) { |
| 15 | | Assuming '__begin1' is not equal to '__end1' | |
|
929 | |
930 | |
931 | |
932 | |
933 | if (!DT->isReachableFromEntry(Pred)) |
| 16 | | Called C++ object pointer is null |
|
934 | continue; |
935 | |
936 | |
937 | if (PreserveLCSSA) |
938 | if (Loop *PL = LI->getLoopFor(Pred)) |
939 | if (!PL->contains(OldBB)) |
940 | HasLoopExit = true; |
941 | |
942 | |
943 | |
944 | if (!L) |
945 | continue; |
946 | if (L->contains(Pred)) |
947 | IsLoopEntry = false; |
948 | else |
949 | SplitMakesNewLoopHeader = true; |
950 | } |
951 | |
952 | |
953 | if (!L) |
954 | return; |
955 | |
956 | if (IsLoopEntry) { |
957 | |
958 | |
959 | |
960 | |
961 | Loop *InnermostPredLoop = nullptr; |
962 | for (BasicBlock *Pred : Preds) { |
963 | if (Loop *PredLoop = LI->getLoopFor(Pred)) { |
964 | |
965 | |
966 | while (PredLoop && !PredLoop->contains(OldBB)) |
967 | PredLoop = PredLoop->getParentLoop(); |
968 | |
969 | |
970 | if (PredLoop && PredLoop->contains(OldBB) && |
971 | (!InnermostPredLoop || |
972 | InnermostPredLoop->getLoopDepth() < PredLoop->getLoopDepth())) |
973 | InnermostPredLoop = PredLoop; |
974 | } |
975 | } |
976 | |
977 | if (InnermostPredLoop) |
978 | InnermostPredLoop->addBasicBlockToLoop(NewBB, *LI); |
979 | } else { |
980 | L->addBasicBlockToLoop(NewBB, *LI); |
981 | if (SplitMakesNewLoopHeader) |
982 | L->moveToHeader(NewBB); |
983 | } |
984 | } |
985 | |
986 | |
987 | |
988 | static void UpdatePHINodes(BasicBlock *OrigBB, BasicBlock *NewBB, |
989 | ArrayRef<BasicBlock *> Preds, BranchInst *BI, |
990 | bool HasLoopExit) { |
991 | |
992 | SmallPtrSet<BasicBlock *, 16> PredSet(Preds.begin(), Preds.end()); |
993 | for (BasicBlock::iterator I = OrigBB->begin(); isa<PHINode>(I); ) { |
994 | PHINode *PN = cast<PHINode>(I++); |
995 | |
996 | |
997 | |
998 | Value *InVal = nullptr; |
999 | if (!HasLoopExit) { |
1000 | InVal = PN->getIncomingValueForBlock(Preds[0]); |
1001 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { |
1002 | if (!PredSet.count(PN->getIncomingBlock(i))) |
1003 | continue; |
1004 | if (!InVal) |
1005 | InVal = PN->getIncomingValue(i); |
1006 | else if (InVal != PN->getIncomingValue(i)) { |
1007 | InVal = nullptr; |
1008 | break; |
1009 | } |
1010 | } |
1011 | } |
1012 | |
1013 | if (InVal) { |
1014 | |
1015 | |
1016 | |
1017 | |
1018 | |
1019 | |
1020 | |
1021 | |
1022 | for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i) |
1023 | if (PredSet.count(PN->getIncomingBlock(i))) |
1024 | PN->removeIncomingValue(i, false); |
1025 | |
1026 | |
1027 | |
1028 | PN->addIncoming(InVal, NewBB); |
1029 | continue; |
1030 | } |
1031 | |
1032 | |
1033 | |
1034 | |
1035 | PHINode *NewPHI = |
1036 | PHINode::Create(PN->getType(), Preds.size(), PN->getName() + ".ph", BI); |
1037 | |
1038 | |
1039 | |
1040 | |
1041 | |
1042 | for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i) { |
1043 | BasicBlock *IncomingBB = PN->getIncomingBlock(i); |
1044 | if (PredSet.count(IncomingBB)) { |
1045 | Value *V = PN->removeIncomingValue(i, false); |
1046 | NewPHI->addIncoming(V, IncomingBB); |
1047 | } |
1048 | } |
1049 | |
1050 | PN->addIncoming(NewPHI, NewBB); |
1051 | } |
1052 | } |
1053 | |
1054 | static void SplitLandingPadPredecessorsImpl( |
1055 | BasicBlock *OrigBB, ArrayRef<BasicBlock *> Preds, const char *Suffix1, |
1056 | const char *Suffix2, SmallVectorImpl<BasicBlock *> &NewBBs, |
1057 | DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI, |
1058 | MemorySSAUpdater *MSSAU, bool PreserveLCSSA); |
1059 | |
1060 | static BasicBlock * |
1061 | SplitBlockPredecessorsImpl(BasicBlock *BB, ArrayRef<BasicBlock *> Preds, |
1062 | const char *Suffix, DomTreeUpdater *DTU, |
1063 | DominatorTree *DT, LoopInfo *LI, |
1064 | MemorySSAUpdater *MSSAU, bool PreserveLCSSA) { |
1065 | |
1066 | if (!BB->canSplitPredecessors()) |
1067 | return nullptr; |
1068 | |
1069 | |
1070 | |
1071 | if (BB->isLandingPad()) { |
1072 | SmallVector<BasicBlock*, 2> NewBBs; |
1073 | std::string NewName = std::string(Suffix) + ".split-lp"; |
1074 | |
1075 | SplitLandingPadPredecessorsImpl(BB, Preds, Suffix, NewName.c_str(), NewBBs, |
1076 | DTU, DT, LI, MSSAU, PreserveLCSSA); |
1077 | return NewBBs[0]; |
1078 | } |
1079 | |
1080 | |
1081 | BasicBlock *NewBB = BasicBlock::Create( |
1082 | BB->getContext(), BB->getName() + Suffix, BB->getParent(), BB); |
1083 | |
1084 | |
1085 | BranchInst *BI = BranchInst::Create(BB, NewBB); |
1086 | |
1087 | Loop *L = nullptr; |
1088 | BasicBlock *OldLatch = nullptr; |
1089 | |
1090 | if (LI && LI->isLoopHeader(BB)) { |
1091 | L = LI->getLoopFor(BB); |
1092 | |
1093 | |
1094 | BI->setDebugLoc(L->getStartLoc()); |
1095 | |
1096 | |
1097 | |
1098 | |
1099 | |
1100 | OldLatch = L->getLoopLatch(); |
1101 | } else |
1102 | BI->setDebugLoc(BB->getFirstNonPHIOrDbg()->getDebugLoc()); |
1103 | |
1104 | |
1105 | for (unsigned i = 0, e = Preds.size(); i != e; ++i) { |
1106 | |
1107 | |
1108 | |
1109 | assert(!isa<IndirectBrInst>(Preds[i]->getTerminator()) && |
1110 | "Cannot split an edge from an IndirectBrInst"); |
1111 | assert(!isa<CallBrInst>(Preds[i]->getTerminator()) && |
1112 | "Cannot split an edge from a CallBrInst"); |
1113 | Preds[i]->getTerminator()->replaceUsesOfWith(BB, NewBB); |
1114 | } |
1115 | |
1116 | |
1117 | |
1118 | |
1119 | |
1120 | if (Preds.empty()) { |
1121 | |
1122 | for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++I) |
1123 | cast<PHINode>(I)->addIncoming(UndefValue::get(I->getType()), NewBB); |
1124 | } |
1125 | |
1126 | |
1127 | bool HasLoopExit = false; |
1128 | UpdateAnalysisInformation(BB, NewBB, Preds, DTU, DT, LI, MSSAU, PreserveLCSSA, |
1129 | HasLoopExit); |
1130 | |
1131 | if (!Preds.empty()) { |
1132 | |
1133 | UpdatePHINodes(BB, NewBB, Preds, BI, HasLoopExit); |
1134 | } |
1135 | |
1136 | if (OldLatch) { |
1137 | BasicBlock *NewLatch = L->getLoopLatch(); |
1138 | if (NewLatch != OldLatch) { |
1139 | MDNode *MD = OldLatch->getTerminator()->getMetadata("llvm.loop"); |
1140 | NewLatch->getTerminator()->setMetadata("llvm.loop", MD); |
1141 | OldLatch->getTerminator()->setMetadata("llvm.loop", nullptr); |
1142 | } |
1143 | } |
1144 | |
1145 | return NewBB; |
1146 | } |
1147 | |
1148 | BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB, |
1149 | ArrayRef<BasicBlock *> Preds, |
1150 | const char *Suffix, DominatorTree *DT, |
1151 | LoopInfo *LI, MemorySSAUpdater *MSSAU, |
1152 | bool PreserveLCSSA) { |
1153 | return SplitBlockPredecessorsImpl(BB, Preds, Suffix, nullptr, DT, LI, |
1154 | MSSAU, PreserveLCSSA); |
1155 | } |
1156 | BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB, |
1157 | ArrayRef<BasicBlock *> Preds, |
1158 | const char *Suffix, |
1159 | DomTreeUpdater *DTU, LoopInfo *LI, |
1160 | MemorySSAUpdater *MSSAU, |
1161 | bool PreserveLCSSA) { |
1162 | return SplitBlockPredecessorsImpl(BB, Preds, Suffix, DTU, |
1163 | nullptr, LI, MSSAU, PreserveLCSSA); |
1164 | } |
1165 | |
1166 | static void SplitLandingPadPredecessorsImpl( |
1167 | BasicBlock *OrigBB, ArrayRef<BasicBlock *> Preds, const char *Suffix1, |
1168 | const char *Suffix2, SmallVectorImpl<BasicBlock *> &NewBBs, |
1169 | DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI, |
1170 | MemorySSAUpdater *MSSAU, bool PreserveLCSSA) { |
1171 | assert(OrigBB->isLandingPad() && "Trying to split a non-landing pad!"); |
1172 | |
1173 | |
1174 | |
1175 | BasicBlock *NewBB1 = BasicBlock::Create(OrigBB->getContext(), |
1176 | OrigBB->getName() + Suffix1, |
1177 | OrigBB->getParent(), OrigBB); |
1178 | NewBBs.push_back(NewBB1); |
1179 | |
1180 | |
1181 | BranchInst *BI1 = BranchInst::Create(OrigBB, NewBB1); |
1182 | BI1->setDebugLoc(OrigBB->getFirstNonPHI()->getDebugLoc()); |
1183 | |
1184 | |
1185 | for (unsigned i = 0, e = Preds.size(); i != e; ++i) { |
| 3 | | Assuming 'i' is equal to 'e' | |
|
| 4 | | Loop condition is false. Execution continues on line 1194 | |
|
1186 | |
1187 | |
1188 | |
1189 | assert(!isa<IndirectBrInst>(Preds[i]->getTerminator()) && |
1190 | "Cannot split an edge from an IndirectBrInst"); |
1191 | Preds[i]->getTerminator()->replaceUsesOfWith(OrigBB, NewBB1); |
1192 | } |
1193 | |
1194 | bool HasLoopExit = false; |
1195 | UpdateAnalysisInformation(OrigBB, NewBB1, Preds, DTU, DT, LI, MSSAU, |
| 5 | | Passing null pointer value via 5th parameter 'DT' | |
|
| 6 | | Calling 'UpdateAnalysisInformation' | |
|
1196 | PreserveLCSSA, HasLoopExit); |
1197 | |
1198 | |
1199 | UpdatePHINodes(OrigBB, NewBB1, Preds, BI1, HasLoopExit); |
1200 | |
1201 | |
1202 | SmallVector<BasicBlock*, 8> NewBB2Preds; |
1203 | for (pred_iterator i = pred_begin(OrigBB), e = pred_end(OrigBB); |
1204 | i != e; ) { |
1205 | BasicBlock *Pred = *i++; |
1206 | if (Pred == NewBB1) continue; |
1207 | assert(!isa<IndirectBrInst>(Pred->getTerminator()) && |
1208 | "Cannot split an edge from an IndirectBrInst"); |
1209 | NewBB2Preds.push_back(Pred); |
1210 | e = pred_end(OrigBB); |
1211 | } |
1212 | |
1213 | BasicBlock *NewBB2 = nullptr; |
1214 | if (!NewBB2Preds.empty()) { |
1215 | |
1216 | NewBB2 = BasicBlock::Create(OrigBB->getContext(), |
1217 | OrigBB->getName() + Suffix2, |
1218 | OrigBB->getParent(), OrigBB); |
1219 | NewBBs.push_back(NewBB2); |
1220 | |
1221 | |
1222 | BranchInst *BI2 = BranchInst::Create(OrigBB, NewBB2); |
1223 | BI2->setDebugLoc(OrigBB->getFirstNonPHI()->getDebugLoc()); |
1224 | |
1225 | |
1226 | for (BasicBlock *NewBB2Pred : NewBB2Preds) |
1227 | NewBB2Pred->getTerminator()->replaceUsesOfWith(OrigBB, NewBB2); |
1228 | |
1229 | |
1230 | HasLoopExit = false; |
1231 | UpdateAnalysisInformation(OrigBB, NewBB2, NewBB2Preds, DTU, DT, LI, MSSAU, |
1232 | PreserveLCSSA, HasLoopExit); |
1233 | |
1234 | |
1235 | UpdatePHINodes(OrigBB, NewBB2, NewBB2Preds, BI2, HasLoopExit); |
1236 | } |
1237 | |
1238 | LandingPadInst *LPad = OrigBB->getLandingPadInst(); |
1239 | Instruction *Clone1 = LPad->clone(); |
1240 | Clone1->setName(Twine("lpad") + Suffix1); |
1241 | NewBB1->getInstList().insert(NewBB1->getFirstInsertionPt(), Clone1); |
1242 | |
1243 | if (NewBB2) { |
1244 | Instruction *Clone2 = LPad->clone(); |
1245 | Clone2->setName(Twine("lpad") + Suffix2); |
1246 | NewBB2->getInstList().insert(NewBB2->getFirstInsertionPt(), Clone2); |
1247 | |
1248 | |
1249 | |
1250 | if (!LPad->use_empty()) { |
1251 | assert(!LPad->getType()->isTokenTy() && |
1252 | "Split cannot be applied if LPad is token type. Otherwise an " |
1253 | "invalid PHINode of token type would be created."); |
1254 | PHINode *PN = PHINode::Create(LPad->getType(), 2, "lpad.phi", LPad); |
1255 | PN->addIncoming(Clone1, NewBB1); |
1256 | PN->addIncoming(Clone2, NewBB2); |
1257 | LPad->replaceAllUsesWith(PN); |
1258 | } |
1259 | LPad->eraseFromParent(); |
1260 | } else { |
1261 | |
1262 | |
1263 | LPad->replaceAllUsesWith(Clone1); |
1264 | LPad->eraseFromParent(); |
1265 | } |
1266 | } |
1267 | |
1268 | void llvm::SplitLandingPadPredecessors(BasicBlock *OrigBB, |
1269 | ArrayRef<BasicBlock *> Preds, |
1270 | const char *Suffix1, const char *Suffix2, |
1271 | SmallVectorImpl<BasicBlock *> &NewBBs, |
1272 | DominatorTree *DT, LoopInfo *LI, |
1273 | MemorySSAUpdater *MSSAU, |
1274 | bool PreserveLCSSA) { |
1275 | return SplitLandingPadPredecessorsImpl( |
1276 | OrigBB, Preds, Suffix1, Suffix2, NewBBs, |
1277 | nullptr, DT, LI, MSSAU, PreserveLCSSA); |
1278 | } |
1279 | void llvm::SplitLandingPadPredecessors(BasicBlock *OrigBB, |
1280 | ArrayRef<BasicBlock *> Preds, |
1281 | const char *Suffix1, const char *Suffix2, |
1282 | SmallVectorImpl<BasicBlock *> &NewBBs, |
1283 | DomTreeUpdater *DTU, LoopInfo *LI, |
1284 | MemorySSAUpdater *MSSAU, |
1285 | bool PreserveLCSSA) { |
1286 | return SplitLandingPadPredecessorsImpl(OrigBB, Preds, Suffix1, Suffix2, |
| 2 | | Calling 'SplitLandingPadPredecessorsImpl' | |
|
1287 | NewBBs, DTU, nullptr, LI, MSSAU, |
| 1 | Passing null pointer value via 7th parameter 'DT' | |
|
1288 | PreserveLCSSA); |
1289 | } |
1290 | |
1291 | ReturnInst *llvm::FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB, |
1292 | BasicBlock *Pred, |
1293 | DomTreeUpdater *DTU) { |
1294 | Instruction *UncondBranch = Pred->getTerminator(); |
1295 | |
1296 | Instruction *NewRet = RI->clone(); |
1297 | Pred->getInstList().push_back(NewRet); |
1298 | |
1299 | |
1300 | |
1301 | for (Use &Op : NewRet->operands()) { |
1302 | Value *V = Op; |
1303 | Instruction *NewBC = nullptr; |
1304 | if (BitCastInst *BCI = dyn_cast<BitCastInst>(V)) { |
1305 | |
1306 | |
1307 | V = BCI->getOperand(0); |
1308 | NewBC = BCI->clone(); |
1309 | Pred->getInstList().insert(NewRet->getIterator(), NewBC); |
1310 | Op = NewBC; |
1311 | } |
1312 | |
1313 | Instruction *NewEV = nullptr; |
1314 | if (ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(V)) { |
1315 | V = EVI->getOperand(0); |
1316 | NewEV = EVI->clone(); |
1317 | if (NewBC) { |
1318 | NewBC->setOperand(0, NewEV); |
1319 | Pred->getInstList().insert(NewBC->getIterator(), NewEV); |
1320 | } else { |
1321 | Pred->getInstList().insert(NewRet->getIterator(), NewEV); |
1322 | Op = NewEV; |
1323 | } |
1324 | } |
1325 | |
1326 | if (PHINode *PN = dyn_cast<PHINode>(V)) { |
1327 | if (PN->getParent() == BB) { |
1328 | if (NewEV) { |
1329 | NewEV->setOperand(0, PN->getIncomingValueForBlock(Pred)); |
1330 | } else if (NewBC) |
1331 | NewBC->setOperand(0, PN->getIncomingValueForBlock(Pred)); |
1332 | else |
1333 | Op = PN->getIncomingValueForBlock(Pred); |
1334 | } |
1335 | } |
1336 | } |
1337 | |
1338 | |
1339 | |
1340 | BB->removePredecessor(Pred); |
1341 | UncondBranch->eraseFromParent(); |
1342 | |
1343 | if (DTU) |
1344 | DTU->applyUpdates({{DominatorTree::Delete, Pred, BB}}); |
1345 | |
1346 | return cast<ReturnInst>(NewRet); |
1347 | } |
1348 | |
1349 | static Instruction * |
1350 | SplitBlockAndInsertIfThenImpl(Value *Cond, Instruction *SplitBefore, |
1351 | bool Unreachable, MDNode *BranchWeights, |
1352 | DomTreeUpdater *DTU, DominatorTree *DT, |
1353 | LoopInfo *LI, BasicBlock *ThenBlock) { |
1354 | SmallVector<DominatorTree::UpdateType, 8> Updates; |
1355 | BasicBlock *Head = SplitBefore->getParent(); |
1356 | BasicBlock *Tail = Head->splitBasicBlock(SplitBefore->getIterator()); |
1357 | if (DTU) { |
1358 | SmallPtrSet<BasicBlock *, 8> UniqueSuccessorsOfHead(succ_begin(Tail), |
1359 | succ_end(Tail)); |
1360 | Updates.push_back({DominatorTree::Insert, Head, Tail}); |
1361 | Updates.reserve(Updates.size() + 2 * UniqueSuccessorsOfHead.size()); |
1362 | for (BasicBlock *UniqueSuccessorOfHead : UniqueSuccessorsOfHead) { |
1363 | Updates.push_back({DominatorTree::Insert, Tail, UniqueSuccessorOfHead}); |
1364 | Updates.push_back({DominatorTree::Delete, Head, UniqueSuccessorOfHead}); |
1365 | } |
1366 | } |
1367 | Instruction *HeadOldTerm = Head->getTerminator(); |
1368 | LLVMContext &C = Head->getContext(); |
1369 | Instruction *CheckTerm; |
1370 | bool CreateThenBlock = (ThenBlock == nullptr); |
1371 | if (CreateThenBlock) { |
1372 | ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail); |
1373 | if (Unreachable) |
1374 | CheckTerm = new UnreachableInst(C, ThenBlock); |
1375 | else { |
1376 | CheckTerm = BranchInst::Create(Tail, ThenBlock); |
1377 | if (DTU) |
1378 | Updates.push_back({DominatorTree::Insert, ThenBlock, Tail}); |
1379 | } |
1380 | CheckTerm->setDebugLoc(SplitBefore->getDebugLoc()); |
1381 | } else |
1382 | CheckTerm = ThenBlock->getTerminator(); |
1383 | BranchInst *HeadNewTerm = |
1384 | BranchInst::Create( ThenBlock, Tail, Cond); |
1385 | if (DTU) |
1386 | Updates.push_back({DominatorTree::Insert, Head, ThenBlock}); |
1387 | HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights); |
1388 | ReplaceInstWithInst(HeadOldTerm, HeadNewTerm); |
1389 | |
1390 | if (DTU) |
1391 | DTU->applyUpdates(Updates); |
1392 | else if (DT) { |
1393 | if (DomTreeNode *OldNode = DT->getNode(Head)) { |
1394 | std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end()); |
1395 | |
1396 | DomTreeNode *NewNode = DT->addNewBlock(Tail, Head); |
1397 | for (DomTreeNode *Child : Children) |
1398 | DT->changeImmediateDominator(Child, NewNode); |
1399 | |
1400 | |
1401 | if (CreateThenBlock) |
1402 | DT->addNewBlock(ThenBlock, Head); |
1403 | else |
1404 | DT->changeImmediateDominator(ThenBlock, Head); |
1405 | } |
1406 | } |
1407 | |
1408 | if (LI) { |
1409 | if (Loop *L = LI->getLoopFor(Head)) { |
1410 | L->addBasicBlockToLoop(ThenBlock, *LI); |
1411 | L->addBasicBlockToLoop(Tail, *LI); |
1412 | } |
1413 | } |
1414 | |
1415 | return CheckTerm; |
1416 | } |
1417 | |
1418 | Instruction *llvm::SplitBlockAndInsertIfThen(Value *Cond, |
1419 | Instruction *SplitBefore, |
1420 | bool Unreachable, |
1421 | MDNode *BranchWeights, |
1422 | DominatorTree *DT, LoopInfo *LI, |
1423 | BasicBlock *ThenBlock) { |
1424 | return SplitBlockAndInsertIfThenImpl(Cond, SplitBefore, Unreachable, |
1425 | BranchWeights, |
1426 | nullptr, DT, LI, ThenBlock); |
1427 | } |
1428 | Instruction *llvm::SplitBlockAndInsertIfThen(Value *Cond, |
1429 | Instruction *SplitBefore, |
1430 | bool Unreachable, |
1431 | MDNode *BranchWeights, |
1432 | DomTreeUpdater *DTU, LoopInfo *LI, |
1433 | BasicBlock *ThenBlock) { |
1434 | return SplitBlockAndInsertIfThenImpl(Cond, SplitBefore, Unreachable, |
1435 | BranchWeights, DTU, nullptr, LI, |
1436 | ThenBlock); |
1437 | } |
1438 | |
1439 | void llvm::SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore, |
1440 | Instruction **ThenTerm, |
1441 | Instruction **ElseTerm, |
1442 | MDNode *BranchWeights) { |
1443 | BasicBlock *Head = SplitBefore->getParent(); |
1444 | BasicBlock *Tail = Head->splitBasicBlock(SplitBefore->getIterator()); |
1445 | Instruction *HeadOldTerm = Head->getTerminator(); |
1446 | LLVMContext &C = Head->getContext(); |
1447 | BasicBlock *ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail); |
1448 | BasicBlock *ElseBlock = BasicBlock::Create(C, "", Head->getParent(), Tail); |
1449 | *ThenTerm = BranchInst::Create(Tail, ThenBlock); |
1450 | (*ThenTerm)->setDebugLoc(SplitBefore->getDebugLoc()); |
1451 | *ElseTerm = BranchInst::Create(Tail, ElseBlock); |
1452 | (*ElseTerm)->setDebugLoc(SplitBefore->getDebugLoc()); |
1453 | BranchInst *HeadNewTerm = |
1454 | BranchInst::Create(ThenBlock, ElseBlock, Cond); |
1455 | HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights); |
1456 | ReplaceInstWithInst(HeadOldTerm, HeadNewTerm); |
1457 | } |
1458 | |
1459 | BranchInst *llvm::GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, |
1460 | BasicBlock *&IfFalse) { |
1461 | PHINode *SomePHI = dyn_cast<PHINode>(BB->begin()); |
1462 | BasicBlock *Pred1 = nullptr; |
1463 | BasicBlock *Pred2 = nullptr; |
1464 | |
1465 | if (SomePHI) { |
1466 | if (SomePHI->getNumIncomingValues() != 2) |
1467 | return nullptr; |
1468 | Pred1 = SomePHI->getIncomingBlock(0); |
1469 | Pred2 = SomePHI->getIncomingBlock(1); |
1470 | } else { |
1471 | pred_iterator PI = pred_begin(BB), PE = pred_end(BB); |
1472 | if (PI == PE) |
1473 | return nullptr; |
1474 | Pred1 = *PI++; |
1475 | if (PI == PE) |
1476 | return nullptr; |
1477 | Pred2 = *PI++; |
1478 | if (PI != PE) |
1479 | return nullptr; |
1480 | } |
1481 | |
1482 | |
1483 | |
1484 | BranchInst *Pred1Br = dyn_cast<BranchInst>(Pred1->getTerminator()); |
1485 | BranchInst *Pred2Br = dyn_cast<BranchInst>(Pred2->getTerminator()); |
1486 | if (!Pred1Br || !Pred2Br) |
1487 | return nullptr; |
1488 | |
1489 | |
1490 | |
1491 | if (Pred2Br->isConditional()) { |
1492 | |
1493 | |
1494 | |
1495 | |
1496 | if (Pred1Br->isConditional()) |
1497 | return nullptr; |
1498 | |
1499 | std::swap(Pred1, Pred2); |
1500 | std::swap(Pred1Br, Pred2Br); |
1501 | } |
1502 | |
1503 | if (Pred1Br->isConditional()) { |
1504 | |
1505 | |
1506 | |
1507 | if (!Pred2->getSinglePredecessor()) |
1508 | return nullptr; |
1509 | |
1510 | |
1511 | |
1512 | if (Pred1Br->getSuccessor(0) == BB && |
1513 | Pred1Br->getSuccessor(1) == Pred2) { |
1514 | IfTrue = Pred1; |
1515 | IfFalse = Pred2; |
1516 | } else if (Pred1Br->getSuccessor(0) == Pred2 && |
1517 | Pred1Br->getSuccessor(1) == BB) { |
1518 | IfTrue = Pred2; |
1519 | IfFalse = Pred1; |
1520 | } else { |
1521 | |
1522 | |
1523 | return nullptr; |
1524 | } |
1525 | |
1526 | return Pred1Br; |
1527 | } |
1528 | |
1529 | |
1530 | |
1531 | |
1532 | BasicBlock *CommonPred = Pred1->getSinglePredecessor(); |
1533 | if (CommonPred == nullptr || CommonPred != Pred2->getSinglePredecessor()) |
1534 | return nullptr; |
1535 | |
1536 | |
1537 | BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator()); |
1538 | if (!BI) return nullptr; |
1539 | |
1540 | assert(BI->isConditional() && "Two successors but not conditional?"); |
1541 | if (BI->getSuccessor(0) == Pred1) { |
1542 | IfTrue = Pred1; |
1543 | IfFalse = Pred2; |
1544 | } else { |
1545 | IfTrue = Pred2; |
1546 | IfFalse = Pred1; |
1547 | } |
1548 | return BI; |
1549 | } |
1550 | |
1551 | |
1552 | |
1553 | |
1554 | |
1555 | |
1556 | |
1557 | |
1558 | |
1559 | |
1560 | static void reconnectPhis(BasicBlock *Out, BasicBlock *GuardBlock, |
1561 | const SetVector<BasicBlock *> &Incoming, |
1562 | BasicBlock *FirstGuardBlock) { |
1563 | auto I = Out->begin(); |
1564 | while (I != Out->end() && isa<PHINode>(I)) { |
1565 | auto Phi = cast<PHINode>(I); |
1566 | auto NewPhi = |
1567 | PHINode::Create(Phi->getType(), Incoming.size(), |
1568 | Phi->getName() + ".moved", &FirstGuardBlock->back()); |
1569 | for (auto In : Incoming) { |
1570 | Value *V = UndefValue::get(Phi->getType()); |
1571 | if (In == Out) { |
1572 | V = NewPhi; |
1573 | } else if (Phi->getBasicBlockIndex(In) != -1) { |
1574 | V = Phi->removeIncomingValue(In, false); |
1575 | } |
1576 | NewPhi->addIncoming(V, In); |
1577 | } |
1578 | assert(NewPhi->getNumIncomingValues() == Incoming.size()); |
1579 | if (Phi->getNumOperands() == 0) { |
1580 | Phi->replaceAllUsesWith(NewPhi); |
1581 | I = Phi->eraseFromParent(); |
1582 | continue; |
1583 | } |
1584 | Phi->addIncoming(NewPhi, GuardBlock); |
1585 | ++I; |
1586 | } |
1587 | } |
1588 | |
1589 | using BBPredicates = DenseMap<BasicBlock *, PHINode *>; |
1590 | using BBSetVector = SetVector<BasicBlock *>; |
1591 | |
1592 | |
1593 | |
1594 | |
1595 | |
1596 | |
1597 | |
1598 | |
1599 | |
1600 | |
1601 | |
1602 | static std::tuple<Value *, BasicBlock *, BasicBlock *> |
1603 | redirectToHub(BasicBlock *BB, BasicBlock *FirstGuardBlock, |
1604 | const BBSetVector &Outgoing) { |
1605 | auto Branch = cast<BranchInst>(BB->getTerminator()); |
1606 | auto Condition = Branch->isConditional() ? Branch->getCondition() : nullptr; |
1607 | |
1608 | BasicBlock *Succ0 = Branch->getSuccessor(0); |
1609 | BasicBlock *Succ1 = nullptr; |
1610 | Succ0 = Outgoing.count(Succ0) ? Succ0 : nullptr; |
1611 | |
1612 | if (Branch->isUnconditional()) { |
1613 | Branch->setSuccessor(0, FirstGuardBlock); |
1614 | assert(Succ0); |
1615 | } else { |
1616 | Succ1 = Branch->getSuccessor(1); |
1617 | Succ1 = Outgoing.count(Succ1) ? Succ1 : nullptr; |
1618 | assert(Succ0 || Succ1); |
1619 | if (Succ0 && !Succ1) { |
1620 | Branch->setSuccessor(0, FirstGuardBlock); |
1621 | } else if (Succ1 && !Succ0) { |
1622 | Branch->setSuccessor(1, FirstGuardBlock); |
1623 | } else { |
1624 | Branch->eraseFromParent(); |
1625 | BranchInst::Create(FirstGuardBlock, BB); |
1626 | } |
1627 | } |
1628 | |
1629 | assert(Succ0 || Succ1); |
1630 | return std::make_tuple(Condition, Succ0, Succ1); |
1631 | } |
1632 | |
1633 | |
1634 | |
1635 | |
1636 | |
1637 | |
1638 | |
1639 | |
1640 | |
1641 | |
1642 | |
1643 | |
1644 | static void convertToGuardPredicates( |
1645 | BasicBlock *FirstGuardBlock, BBPredicates &GuardPredicates, |
1646 | SmallVectorImpl<WeakVH> &DeletionCandidates, const BBSetVector &Incoming, |
1647 | const BBSetVector &Outgoing) { |
1648 | auto &Context = Incoming.front()->getContext(); |
1649 | auto BoolTrue = ConstantInt::getTrue(Context); |
1650 | auto BoolFalse = ConstantInt::getFalse(Context); |
1651 | |
1652 | |
1653 | |
1654 | for (int i = 0, e = Outgoing.size() - 1; i != e; ++i) { |
1655 | auto Out = Outgoing[i]; |
1656 | LLVM_DEBUG(dbgs() << "Creating guard for " << Out->getName() << "\n"); |
1657 | auto Phi = |
1658 | PHINode::Create(Type::getInt1Ty(Context), Incoming.size(), |
1659 | StringRef("Guard.") + Out->getName(), FirstGuardBlock); |
1660 | GuardPredicates[Out] = Phi; |
1661 | } |
1662 | |
1663 | for (auto In : Incoming) { |
1664 | Value *Condition; |
1665 | BasicBlock *Succ0; |
1666 | BasicBlock *Succ1; |
1667 | std::tie(Condition, Succ0, Succ1) = |
1668 | redirectToHub(In, FirstGuardBlock, Outgoing); |
1669 | |
1670 | |
1671 | |
1672 | |
1673 | |
1674 | |
1675 | |
1676 | |
1677 | bool OneSuccessorDone = false; |
1678 | for (int i = 0, e = Outgoing.size() - 1; i != e; ++i) { |
1679 | auto Out = Outgoing[i]; |
1680 | auto Phi = GuardPredicates[Out]; |
1681 | if (Out != Succ0 && Out != Succ1) { |
1682 | Phi->addIncoming(BoolFalse, In); |
1683 | continue; |
1684 | } |
1685 | |
1686 | |
1687 | if (!Succ0 || !Succ1 || OneSuccessorDone) { |
1688 | Phi->addIncoming(BoolTrue, In); |
1689 | continue; |
1690 | } |
1691 | assert(Succ0 && Succ1); |
1692 | OneSuccessorDone = true; |
1693 | if (Out == Succ0) { |
1694 | Phi->addIncoming(Condition, In); |
1695 | continue; |
1696 | } |
1697 | auto Inverted = invertCondition(Condition); |
1698 | DeletionCandidates.push_back(Condition); |
1699 | Phi->addIncoming(Inverted, In); |
1700 | } |
1701 | } |
1702 | } |
1703 | |
1704 | |
1705 | |
1706 | |
1707 | |
1708 | |
1709 | |
1710 | |
1711 | |
1712 | |
1713 | |
1714 | static void createGuardBlocks(SmallVectorImpl<BasicBlock *> &GuardBlocks, |
1715 | Function *F, const BBSetVector &Outgoing, |
1716 | BBPredicates &GuardPredicates, StringRef Prefix) { |
1717 | for (int i = 0, e = Outgoing.size() - 2; i != e; ++i) { |
1718 | GuardBlocks.push_back( |
1719 | BasicBlock::Create(F->getContext(), Prefix + ".guard", F)); |
1720 | } |
1721 | assert(GuardBlocks.size() == GuardPredicates.size()); |
1722 | |
1723 | |
1724 | |
1725 | GuardBlocks.push_back(Outgoing.back()); |
1726 | |
1727 | for (int i = 0, e = GuardBlocks.size() - 1; i != e; ++i) { |
1728 | auto Out = Outgoing[i]; |
1729 | assert(GuardPredicates.count(Out)); |
1730 | BranchInst::Create(Out, GuardBlocks[i + 1], GuardPredicates[Out], |
1731 | GuardBlocks[i]); |
1732 | } |
1733 | |
1734 | |
1735 | GuardBlocks.pop_back(); |
1736 | } |
1737 | |
1738 | BasicBlock *llvm::CreateControlFlowHub( |
1739 | DomTreeUpdater *DTU, SmallVectorImpl<BasicBlock *> &GuardBlocks, |
1740 | const BBSetVector &Incoming, const BBSetVector &Outgoing, |
1741 | const StringRef Prefix) { |
1742 | auto F = Incoming.front()->getParent(); |
1743 | auto FirstGuardBlock = |
1744 | BasicBlock::Create(F->getContext(), Prefix + ".guard", F); |
1745 | |
1746 | SmallVector<DominatorTree::UpdateType, 16> Updates; |
1747 | if (DTU) { |
1748 | for (auto In : Incoming) { |
1749 | Updates.push_back({DominatorTree::Insert, In, FirstGuardBlock}); |
1750 | for (auto Succ : successors(In)) { |
1751 | if (Outgoing.count(Succ)) |
1752 | Updates.push_back({DominatorTree::Delete, In, Succ}); |
1753 | } |
1754 | } |
1755 | } |
1756 | |
1757 | BBPredicates GuardPredicates; |
1758 | SmallVector<WeakVH, 8> DeletionCandidates; |
1759 | convertToGuardPredicates(FirstGuardBlock, GuardPredicates, DeletionCandidates, |
1760 | Incoming, Outgoing); |
1761 | |
1762 | GuardBlocks.push_back(FirstGuardBlock); |
1763 | createGuardBlocks(GuardBlocks, F, Outgoing, GuardPredicates, Prefix); |
1764 | |
1765 | |
1766 | for (int i = 0, e = GuardBlocks.size(); i != e; ++i) { |
1767 | reconnectPhis(Outgoing[i], GuardBlocks[i], Incoming, FirstGuardBlock); |
1768 | } |
1769 | reconnectPhis(Outgoing.back(), GuardBlocks.back(), Incoming, FirstGuardBlock); |
1770 | |
1771 | if (DTU) { |
1772 | int NumGuards = GuardBlocks.size(); |
1773 | assert((int)Outgoing.size() == NumGuards + 1); |
1774 | for (int i = 0; i != NumGuards - 1; ++i) { |
1775 | Updates.push_back({DominatorTree::Insert, GuardBlocks[i], Outgoing[i]}); |
1776 | Updates.push_back( |
1777 | {DominatorTree::Insert, GuardBlocks[i], GuardBlocks[i + 1]}); |
1778 | } |
1779 | Updates.push_back({DominatorTree::Insert, GuardBlocks[NumGuards - 1], |
1780 | Outgoing[NumGuards - 1]}); |
1781 | Updates.push_back({DominatorTree::Insert, GuardBlocks[NumGuards - 1], |
1782 | Outgoing[NumGuards]}); |
1783 | DTU->applyUpdates(Updates); |
1784 | } |
1785 | |
1786 | for (auto I : DeletionCandidates) { |
1787 | if (I->use_empty()) |
1788 | if (auto Inst = dyn_cast_or_null<Instruction>(I)) |
1789 | Inst->eraseFromParent(); |
1790 | } |
1791 | |
1792 | return FirstGuardBlock; |
1793 | } |