Bug Summary

File:src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp
Warning:line 933, column 10
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

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//===- BasicBlockUtils.cpp - BasicBlock Utilities --------------------------==//
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// This family of functions perform manipulations on basic blocks, and
10// instructions contained within basic blocks.
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
51using namespace llvm;
52
53#define DEBUG_TYPE"basicblock-utils" "basicblock-utils"
54
55void llvm::DetatchDeadBlocks(
56 ArrayRef<BasicBlock *> BBs,
57 SmallVectorImpl<DominatorTree::UpdateType> *Updates,
58 bool KeepOneInputPHIs) {
59 for (auto *BB : BBs) {
60 // Loop through all of our successors and make sure they know that one
61 // of their predecessors is going away.
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 // Zap all the instructions in the block.
70 while (!BB->empty()) {
71 Instruction &I = BB->back();
72 // If this instruction is used, replace uses with an arbitrary value.
73 // Because control flow can't get here, we don't care what we replace the
74 // value with. Note that since this block is unreachable, and all values
75 // contained within it must dominate their uses, that all uses will
76 // eventually be removed (they are themselves dead).
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 &&((void)0)
83 isa<UnreachableInst>(BB->getTerminator()) &&((void)0)
84 "The successor list of BB isn't empty before "((void)0)
85 "applying corresponding DTU updates.")((void)0);
86 }
87}
88
89void llvm::DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU,
90 bool KeepOneInputPHIs) {
91 DeleteDeadBlocks({BB}, DTU, KeepOneInputPHIs);
92}
93
94void llvm::DeleteDeadBlocks(ArrayRef <BasicBlock *> BBs, DomTreeUpdater *DTU,
95 bool KeepOneInputPHIs) {
96#ifndef NDEBUG1
97 // Make sure that all predecessors of each dead block is also dead.
98 SmallPtrSet<BasicBlock *, 4> Dead(BBs.begin(), BBs.end());
99 assert(Dead.size() == BBs.size() && "Duplicating blocks?")((void)0);
100 for (auto *BB : Dead)
101 for (BasicBlock *Pred : predecessors(BB))
102 assert(Dead.count(Pred) && "All predecessors must be dead!")((void)0);
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
118bool llvm::EliminateUnreachableBlocks(Function &F, DomTreeUpdater *DTU,
119 bool KeepOneInputPHIs) {
120 df_iterator_default_set<BasicBlock*> Reachable;
121
122 // Mark all reachable blocks.
123 for (BasicBlock *BB : depth_first_ext(&F, Reachable))
124 (void)BB/* Mark all reachable blocks */;
125
126 // Collect all dead blocks.
127 std::vector<BasicBlock*> DeadBlocks;
128 for (BasicBlock &BB : F)
129 if (!Reachable.count(&BB))
130 DeadBlocks.push_back(&BB);
131
132 // Delete the dead blocks.
133 DeleteDeadBlocks(DeadBlocks, DTU, KeepOneInputPHIs);
134
135 return !DeadBlocks.empty();
136}
137
138bool 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); // Memdep updates AA itself.
151
152 PN->eraseFromParent();
153 }
154 return true;
155}
156
157bool llvm::DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI,
158 MemorySSAUpdater *MSSAU) {
159 // Recursively deleting a PHI may cause multiple PHIs to be deleted
160 // or RAUW'd undef, so use an array of WeakTrackingVH for the PHIs to delete.
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
173bool 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 // Can't merge if there are multiple predecessors, or no predecessors.
181 BasicBlock *PredBB = BB->getUniquePredecessor();
182 if (!PredBB) return false;
183
184 // Don't break self-loops.
185 if (PredBB == BB) return false;
186 // Don't break unwinding instructions.
187 if (PredBB->getTerminator()->isExceptionalTerminator())
188 return false;
189
190 // Can't merge if there are multiple distinct successors.
191 if (!PredecessorWithTwoSuccessors && PredBB->getUniqueSuccessor() != BB)
192 return false;
193
194 // Currently only allow PredBB to have two predecessors, one being BB.
195 // Update BI to branch to BB's only successor instead of BB.
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 // Can't merge if there is PHI loop.
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 "do { } while (false)
215 << PredBB->getName() << "\n")do { } while (false);
216
217 // Begin by getting rid of unneeded PHIs.
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 // DTU update: Collect all the edges that exit BB.
228 // These dominator edges will be redirected from Pred.
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 // Add insert edges first. Experimentally, for the particular case of two
236 // blocks that can be merged, with a single successor and single predecessor
237 // respectively, it is beneficial to have all insert updates first. Deleting
238 // edges first may lead to unreachable blocks, followed by inserting edges
239 // making the blocks reachable again. Such DT updates lead to high compile
240 // times. We add inserts before deletes here to reduce compile time.
241 for (BasicBlock *SuccOfBB : SuccsOfBB)
242 // This successor of BB may already be a PredBB's successor.
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 // If there's nothing to move, mark the starting instruction as the last
254 // instruction in the block. Terminator instruction is handled separately.
255 if (Start == STI)
256 Start = PTI;
257
258 // Move all definitions in the successor to the predecessor...
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 // Make all PHI nodes that referred to BB now refer to Pred as their
266 // source...
267 BB->replaceAllUsesWith(PredBB);
268
269 if (PredecessorWithTwoSuccessors) {
270 // Delete the unconditional branch from BB.
271 BB->getInstList().pop_back();
272
273 // Update branch in the predecessor.
274 PredBB_BI->setSuccessor(FallThruPath, NewSucc);
275 } else {
276 // Delete the unconditional branch from the predecessor.
277 PredBB->getInstList().pop_back();
278
279 // Move terminator instruction.
280 PredBB->getInstList().splice(PredBB->end(), BB->getInstList());
281
282 // Terminator may be a memory accessing instruction too.
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 // Add unreachable to now empty BB.
289 new UnreachableInst(BB->getContext(), BB);
290
291 // Inherit predecessors name if it exists.
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 // Finally, erase the old block and update dominator info.
305 DeleteDeadBlock(BB, DTU);
306
307 return true;
308}
309
310bool llvm::MergeBlockSuccessorsIntoGivenBlocks(
311 SmallPtrSetImpl<BasicBlock *> &MergeBlocks, Loop *L, DomTreeUpdater *DTU,
312 LoopInfo *LI) {
313 assert(!MergeBlocks.empty() && "MergeBlocks should not be empty")((void)0);
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 &&((void)0)
324 "Expecting BB to be unique predecessor of the Dest block")((void)0);
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/// Remove redundant instructions within sequences of consecutive dbg.value
336/// instructions. This is done using a backward scan to keep the last dbg.value
337/// describing a specific variable/fragment.
338///
339/// BackwardScan strategy:
340/// ----------------------
341/// Given a sequence of consecutive DbgValueInst like this
342///
343/// dbg.value ..., "x", FragmentX1 (*)
344/// dbg.value ..., "y", FragmentY1
345/// dbg.value ..., "x", FragmentX2
346/// dbg.value ..., "x", FragmentX1 (**)
347///
348/// then the instruction marked with (*) can be removed (it is guaranteed to be
349/// obsoleted by the instruction marked with (**) as the latter instruction is
350/// describing the same variable using the same fragment info).
351///
352/// Possible improvements:
353/// - Check fully overlapping fragments and not only identical fragments.
354/// - Support dbg.addr, dbg.declare. dbg.label, and possibly other meta
355/// instructions being part of the sequence of consecutive instructions.
356static 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 // If the same variable fragment is described more than once it is enough
366 // to keep the last one (i.e. the first found since we for reverse
367 // iteration).
368 if (!R.second)
369 ToBeRemoved.push_back(DVI);
370 continue;
371 }
372 // Sequence with consecutive dbg.value instrs ended. Clear the map to
373 // restart identifying redundant instructions if case we find another
374 // dbg.value sequence.
375 VariableSet.clear();
376 }
377
378 for (auto &Instr : ToBeRemoved)
379 Instr->eraseFromParent();
380
381 return !ToBeRemoved.empty();
382}
383
384/// Remove redundant dbg.value instructions using a forward scan. This can
385/// remove a dbg.value instruction that is redundant due to indicating that a
386/// variable has the same value as already being indicated by an earlier
387/// dbg.value.
388///
389/// ForwardScan strategy:
390/// ---------------------
391/// Given two identical dbg.value instructions, separated by a block of
392/// instructions that isn't describing the same variable, like this
393///
394/// dbg.value X1, "x", FragmentX1 (**)
395/// <block of instructions, none being "dbg.value ..., "x", ...">
396/// dbg.value X1, "x", FragmentX1 (*)
397///
398/// then the instruction marked with (*) can be removed. Variable "x" is already
399/// described as being mapped to the SSA value X1.
400///
401/// Possible improvements:
402/// - Keep track of non-overlapping fragments.
403static 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 // Update the map if we found a new value/expression describing the
414 // variable, or if the variable wasn't mapped already.
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 // Found an identical mapping. Remember the instruction for later removal.
422 ToBeRemoved.push_back(DVI);
423 }
424 }
425
426 for (auto &Instr : ToBeRemoved)
427 Instr->eraseFromParent();
428
429 return !ToBeRemoved.empty();
430}
431
432bool llvm::RemoveRedundantDbgInstrs(BasicBlock *BB) {
433 bool MadeChanges = false;
434 // By using the "backward scan" strategy before the "forward scan" strategy we
435 // can remove both dbg.value (2) and (3) in a situation like this:
436 //
437 // (1) dbg.value V1, "x", DIExpression()
438 // ...
439 // (2) dbg.value V2, "x", DIExpression()
440 // (3) dbg.value V1, "x", DIExpression()
441 //
442 // The backward scan will remove (2), it is made obsolete by (3). After
443 // getting (2) out of the way, the foward scan will remove (3) since "x"
444 // already is described as having the value V1 at (1).
445 MadeChanges |= removeRedundantDbgInstrsUsingBackwardScan(BB);
446 MadeChanges |= removeRedundantDbgInstrsUsingForwardScan(BB);
447
448 if (MadeChanges)
449 LLVM_DEBUG(dbgs() << "Removed redundant dbg instrs from: "do { } while (false)
450 << BB->getName() << "\n")do { } while (false);
451 return MadeChanges;
452}
453
454void llvm::ReplaceInstWithValue(BasicBlock::InstListType &BIL,
455 BasicBlock::iterator &BI, Value *V) {
456 Instruction &I = *BI;
457 // Replaces all of the uses of the instruction with uses of the value
458 I.replaceAllUsesWith(V);
459
460 // Make sure to propagate a name if there is one already.
461 if (I.hasName() && !V->hasName())
462 V->takeName(&I);
463
464 // Delete the unnecessary instruction now...
465 BI = BIL.erase(BI);
466}
467
468void llvm::ReplaceInstWithInst(BasicBlock::InstListType &BIL,
469 BasicBlock::iterator &BI, Instruction *I) {
470 assert(I->getParent() == nullptr &&((void)0)
471 "ReplaceInstWithInst: Instruction already inserted into basic block!")((void)0);
472
473 // Copy debug location to newly added instruction, if it wasn't already set
474 // by the caller.
475 if (!I->getDebugLoc())
476 I->setDebugLoc(BI->getDebugLoc());
477
478 // Insert the new instruction into the basic block...
479 BasicBlock::iterator New = BIL.insert(BI, I);
480
481 // Replace all uses of the old instruction, and delete it.
482 ReplaceInstWithValue(BIL, BI, I);
483
484 // Move BI back to point to the newly inserted instruction
485 BI = New;
486}
487
488void llvm::ReplaceInstWithInst(Instruction *From, Instruction *To) {
489 BasicBlock::iterator BI(From);
490 ReplaceInstWithInst(From->getParent()->getInstList(), BI, To);
491}
492
493BasicBlock *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 // If it is a critical edge, and the succesor is an exception block, handle
505 // the split edge logic in this specific function
506 if (Succ->isEHPad())
507 return ehAwareSplitEdge(BB, Succ, nullptr, nullptr, Options, BBName);
508
509 // If this is a critical edge, let SplitKnownCriticalEdge do it.
510 return SplitKnownCriticalEdge(LatchTerm, SuccNum, Options, BBName);
511 }
512
513 // If the edge isn't critical, then BB has a single successor or Succ has a
514 // single pred. Split the block.
515 if (BasicBlock *SP = Succ->getSinglePredecessor()) {
516 // If the successor only has a single pred, split the top of the successor
517 // block.
518 assert(SP == BB && "CFG broken")((void)0);
519 SP = nullptr;
520 return SplitBlock(Succ, &Succ->front(), DT, LI, MSSAU, BBName,
521 /*Before=*/true);
522 }
523
524 // Otherwise, if BB has a single successor, split it at the bottom of the
525 // block.
526 assert(BB->getTerminator()->getNumSuccessors() == 1 &&((void)0)
527 "Should have a single succ!")((void)0);
528 return SplitBlock(BB, BB->getTerminator(), DT, LI, MSSAU, BBName);
529}
530
531void 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")__builtin_unreachable();
540}
541
542void llvm::updatePhiNodes(BasicBlock *DestBB, BasicBlock *OldPred,
543 BasicBlock *NewPred, PHINode *Until) {
544 int BBIdx = 0;
545 for (PHINode &PN : DestBB->phis()) {
546 // We manually update the LandingPadReplacement PHINode and it is the last
547 // PHI Node. So, if we find it, we are done.
548 if (Until == &PN)
549 break;
550
551 // Reuse the previous value of BBIdx if it lines up. In cases where we
552 // have multiple phi nodes with *lots* of predecessors, this is a speed
553 // win because we don't have to scan the PHI looking for TIBB. This
554 // happens because the BB list of PHI nodes are usually in the same
555 // order.
556 if (PN.getIncomingBlock(BBIdx) != OldPred)
557 BBIdx = PN.getBasicBlockIndex(OldPred);
558
559 assert(BBIdx != -1 && "Invalid PHI Index!")((void)0);
560 PN.setIncomingBlock(BBIdx, NewPred);
561 }
562}
563
564BasicBlock *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 // Check if extra modifications will be required to preserve loop-simplify
577 // form after splitting. If it would require splitting blocks with IndirectBr
578 // terminators, bail out if preserving loop-simplify form is requested.
579 if (Options.PreserveLoopSimplify && LI) {
580 if (Loop *BBLoop = LI->getLoopFor(BB)) {
581
582 // The only way that we can break LoopSimplify form by splitting a
583 // critical edge is when there exists some edge from BBLoop to Succ *and*
584 // the only edge into Succ from outside of BBLoop is that of NewBB after
585 // the split. If the first isn't true, then LoopSimplify still holds,
586 // NewBB is the new exit block and it has no non-loop predecessors. If the
587 // second isn't true, then Succ was not in LoopSimplify form prior to
588 // the split as it had a non-loop predecessor. In both of these cases,
589 // the predecessor must be directly in BBLoop, not in a subloop, or again
590 // LoopSimplify doesn't hold.
591 for (BasicBlock *P : predecessors(Succ)) {
592 if (P == BB)
593 continue; // The new block is known.
594 if (LI->getLoopFor(P) != BBLoop) {
595 // Loop is not in LoopSimplify form, no need to re simplify after
596 // splitting edge.
597 LoopPreds.clear();
598 break;
599 }
600 LoopPreds.push_back(P);
601 }
602 // Loop-simplify form can be preserved, if we can split all in-loop
603 // predecessors.
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")__builtin_unreachable();
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 // If one or the other blocks were not in a loop, the new block is not
665 // either, and thus LI doesn't need to be updated.
666 if (Loop *SuccLoop = LI->getLoopFor(Succ)) {
667 if (BBLoop == SuccLoop) {
668 // Both in the same loop, the NewBB joins loop.
669 SuccLoop->addBasicBlockToLoop(NewBB, *LI);
670 } else if (BBLoop->contains(SuccLoop)) {
671 // Edge from an outer loop to an inner loop. Add to the outer loop.
672 BBLoop->addBasicBlockToLoop(NewBB, *LI);
673 } else if (SuccLoop->contains(BBLoop)) {
674 // Edge from an inner loop to an outer loop. Add to the outer loop.
675 SuccLoop->addBasicBlockToLoop(NewBB, *LI);
676 } else {
677 // Edge from two loops with no containment relation. Because these
678 // are natural loops, we know that the destination block must be the
679 // header of its loop (adding a branch into a loop elsewhere would
680 // create an irreducible loop).
681 assert(SuccLoop->getHeader() == Succ &&((void)0)
682 "Should not create irreducible loops!")((void)0);
683 if (Loop *P = SuccLoop->getParentLoop())
684 P->addBasicBlockToLoop(NewBB, *LI);
685 }
686 }
687
688 // If BB is in a loop and Succ is outside of that loop, we may need to
689 // update LoopSimplify form and LCSSA form.
690 if (!BBLoop->contains(Succ)) {
691 assert(!BBLoop->contains(NewBB) &&((void)0)
692 "Split point for loop exit is contained in loop!")((void)0);
693
694 // Update LCSSA form in the newly created exit block.
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
712void llvm::createPHIsForSplitLoopExit(ArrayRef<BasicBlock *> Preds,
713 BasicBlock *SplitBB, BasicBlock *DestBB) {
714 // SplitBB shouldn't have anything non-trivial in it yet.
715 assert((SplitBB->getFirstNonPHI() == SplitBB->getTerminator() ||((void)0)
716 SplitBB->isLandingPad()) &&((void)0)
717 "SplitBB has non-PHI nodes!")((void)0);
718
719 // For each PHI in the destination block.
720 for (PHINode &PN : DestBB->phis()) {
721 int Idx = PN.getBasicBlockIndex(SplitBB);
722 assert(Idx >= 0 && "Invalid Block Index")((void)0);
723 Value *V = PN.getIncomingValue(Idx);
724
725 // If the input is a PHI which already satisfies LCSSA, don't create
726 // a new one.
727 if (const PHINode *VP = dyn_cast<PHINode>(V))
728 if (VP->getParent() == SplitBB)
729 continue;
730
731 // Otherwise a new PHI is needed. Create one and populate it.
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 // Update the original PHI.
739 PN.setIncomingValue(Idx, NewPN);
740 }
741}
742
743unsigned
744llvm::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
758static 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())((void)0);
772 }
773 std::string Name = BBName.str();
774 BasicBlock *New = Old->splitBasicBlock(
775 SplitIt, Name.empty() ? Old->getName() + ".split" : Name);
776
777 // The new block lives in whichever loop the old one did. This preserves
778 // LCSSA as well, because we force the split point to be after any PHI nodes.
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 // Old dominates New. New node dominates all other nodes dominated by Old.
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 // Old dominates New. New node dominates all other nodes dominated by Old.
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 // Move MemoryAccesses still tracked in Old, but part of New now.
807 // Update accesses in successor blocks accordingly.
808 if (MSSAU)
809 MSSAU->moveAllAfterSpliceBlocks(Old, New, &*(New->begin()));
810
811 return New;
812}
813
814BasicBlock *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, /*DTU=*/nullptr, DT, LI, MSSAU, BBName,
819 Before);
820}
821BasicBlock *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, /*DT=*/nullptr, LI, MSSAU, BBName,
826 Before);
827}
828
829BasicBlock *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 /* Before=*/true);
841
842 // The new block lives in whichever loop the old one did. This preserves
843 // LCSSA as well, because we force the split point to be after any PHI nodes.
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 // New dominates Old. The predecessor nodes of the Old node dominate
851 // New node.
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 // Move MemoryAccesses still tracked in Old, but part of New now.
864 // Update accesses in successor blocks accordingly.
865 if (MSSAU) {
866 MSSAU->applyUpdates(DTUpdates, DTU->getDomTree());
867 if (VerifyMemorySSA)
868 MSSAU->getMemorySSA()->verifyMemorySSA();
869 }
870 }
871 return New;
872}
873
874/// Update DominatorTree, LoopInfo, and LCCSA analysis information.
875static 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 // Update dominator tree if available.
881 if (DTU) {
7
←
Assuming 'DTU' is null
→
8
←
Taking false branch
→
882 // Recalculation of DomTree is needed when updating a forward DomTree and
883 // the Entry BB is replaced.
884 if (NewBB->isEntryBlock() && DTU->hasDomTree()) {
885 // The entry block was removed and there is no external interface for
886 // the dominator tree to be notified of this change. In this corner-case
887 // we recalculate the entire tree.
888 DTU->recalculate(*NewBB->getParent());
889 } else {
890 // Split block expects NewBB to have a non-empty set of predecessors.
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
8.1
'DT' is null
) {
9
←
Taking false branch
→
902 if (OldBB == DT->getRootNode()->getBlock()) {
903 assert(NewBB->isEntryBlock())((void)0);
904 DT->setNewRoot(NewBB);
905 } else {
906 // Split block expects NewBB to have a non-empty set of predecessors.
907 DT->splitBlock(NewBB);
908 }
909 }
910
911 // Update MemoryPhis after split if MemorySSA is available
912 if (MSSAU)
10
←
Assuming 'MSSAU' is null
→
11
←
Taking false branch
→
913 MSSAU->wireOldPredecessorsToNewImmediatePredecessor(OldBB, NewBB, Preds);
914
915 // The rest of the logic is only relevant for updating the loop structures.
916 if (!LI)
12
←
Assuming 'LI' is non-null
→
13
←
Taking false branch
→
917 return;
918
919 if (DTU
13.1
'DTU' is null
 && DTU->hasDomTree())
920 DT = &DTU->getDomTree();
921 assert(DT && "DT should be available to update LoopInfo!")((void)0);
922 Loop *L = LI->getLoopFor(OldBB);
923
924 // If we need to preserve loop analyses, collect some information about how
925 // this split will affect loops.
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 // Preds that are not reachable from entry should not be used to identify if
930 // OldBB is a loop entry or if SplitMakesNewLoopHeader. Unreachable blocks
931 // are not within any loops, so we incorrectly mark SplitMakesNewLoopHeader
932 // as true and make the NewBB the header of some loop. This breaks LI.
933 if (!DT->isReachableFromEntry(Pred))
16
←
Called C++ object pointer is null
934 continue;
935 // If we need to preserve LCSSA, determine if any of the preds is a loop
936 // exit.
937 if (PreserveLCSSA)
938 if (Loop *PL = LI->getLoopFor(Pred))
939 if (!PL->contains(OldBB))
940 HasLoopExit = true;
941
942 // If we need to preserve LoopInfo, note whether any of the preds crosses
943 // an interesting loop boundary.
944 if (!L)
945 continue;
946 if (L->contains(Pred))
947 IsLoopEntry = false;
948 else
949 SplitMakesNewLoopHeader = true;
950 }
951
952 // Unless we have a loop for OldBB, nothing else to do here.
953 if (!L)
954 return;
955
956 if (IsLoopEntry) {
957 // Add the new block to the nearest enclosing loop (and not an adjacent
958 // loop). To find this, examine each of the predecessors and determine which
959 // loops enclose them, and select the most-nested loop which contains the
960 // loop containing the block being split.
961 Loop *InnermostPredLoop = nullptr;
962 for (BasicBlock *Pred : Preds) {
963 if (Loop *PredLoop = LI->getLoopFor(Pred)) {
964 // Seek a loop which actually contains the block being split (to avoid
965 // adjacent loops).
966 while (PredLoop && !PredLoop->contains(OldBB))
967 PredLoop = PredLoop->getParentLoop();
968
969 // Select the most-nested of these loops which contains the block.
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/// Update the PHI nodes in OrigBB to include the values coming from NewBB.
987/// This also updates AliasAnalysis, if available.
988static void UpdatePHINodes(BasicBlock *OrigBB, BasicBlock *NewBB,
989 ArrayRef<BasicBlock *> Preds, BranchInst *BI,
990 bool HasLoopExit) {
991 // Otherwise, create a new PHI node in NewBB for each PHI node in OrigBB.
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 // Check to see if all of the values coming in are the same. If so, we
997 // don't need to create a new PHI node, unless it's needed for LCSSA.
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 // If all incoming values for the new PHI would be the same, just don't
1015 // make a new PHI. Instead, just remove the incoming values from the old
1016 // PHI.
1017
1018 // NOTE! This loop walks backwards for a reason! First off, this minimizes
1019 // the cost of removal if we end up removing a large number of values, and
1020 // second off, this ensures that the indices for the incoming values
1021 // aren't invalidated when we remove one.
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 // Add an incoming value to the PHI node in the loop for the preheader
1027 // edge.
1028 PN->addIncoming(InVal, NewBB);
1029 continue;
1030 }
1031
1032 // If the values coming into the block are not the same, we need a new
1033 // PHI.
1034 // Create the new PHI node, insert it into NewBB at the end of the block
1035 PHINode *NewPHI =
1036 PHINode::Create(PN->getType(), Preds.size(), PN->getName() + ".ph", BI);
1037
1038 // NOTE! This loop walks backwards for a reason! First off, this minimizes
1039 // the cost of removal if we end up removing a large number of values, and
1040 // second off, this ensures that the indices for the incoming values aren't
1041 // invalidated when we remove one.
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
1054static 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
1060static BasicBlock *
1061SplitBlockPredecessorsImpl(BasicBlock *BB, ArrayRef<BasicBlock *> Preds,
1062 const char *Suffix, DomTreeUpdater *DTU,
1063 DominatorTree *DT, LoopInfo *LI,
1064 MemorySSAUpdater *MSSAU, bool PreserveLCSSA) {
1065 // Do not attempt to split that which cannot be split.
1066 if (!BB->canSplitPredecessors())
1067 return nullptr;
1068
1069 // For the landingpads we need to act a bit differently.
1070 // Delegate this work to the SplitLandingPadPredecessors.
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 // Create new basic block, insert right before the original block.
1081 BasicBlock *NewBB = BasicBlock::Create(
1082 BB->getContext(), BB->getName() + Suffix, BB->getParent(), BB);
1083
1084 // The new block unconditionally branches to the old block.
1085 BranchInst *BI = BranchInst::Create(BB, NewBB);
1086
1087 Loop *L = nullptr;
1088 BasicBlock *OldLatch = nullptr;
1089 // Splitting the predecessors of a loop header creates a preheader block.
1090 if (LI && LI->isLoopHeader(BB)) {
1091 L = LI->getLoopFor(BB);
1092 // Using the loop start line number prevents debuggers stepping into the
1093 // loop body for this instruction.
1094 BI->setDebugLoc(L->getStartLoc());
1095
1096 // If BB is the header of the Loop, it is possible that the loop is
1097 // modified, such that the current latch does not remain the latch of the
1098 // loop. If that is the case, the loop metadata from the current latch needs
1099 // to be applied to the new latch.
1100 OldLatch = L->getLoopLatch();
1101 } else
1102 BI->setDebugLoc(BB->getFirstNonPHIOrDbg()->getDebugLoc());
1103
1104 // Move the edges from Preds to point to NewBB instead of BB.
1105 for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
1106 // This is slightly more strict than necessary; the minimum requirement
1107 // is that there be no more than one indirectbr branching to BB. And
1108 // all BlockAddress uses would need to be updated.
1109 assert(!isa<IndirectBrInst>(Preds[i]->getTerminator()) &&((void)0)
1110 "Cannot split an edge from an IndirectBrInst")((void)0);
1111 assert(!isa<CallBrInst>(Preds[i]->getTerminator()) &&((void)0)
1112 "Cannot split an edge from a CallBrInst")((void)0);
1113 Preds[i]->getTerminator()->replaceUsesOfWith(BB, NewBB);
1114 }
1115
1116 // Insert a new PHI node into NewBB for every PHI node in BB and that new PHI
1117 // node becomes an incoming value for BB's phi node. However, if the Preds
1118 // list is empty, we need to insert dummy entries into the PHI nodes in BB to
1119 // account for the newly created predecessor.
1120 if (Preds.empty()) {
1121 // Insert dummy values as the incoming value.
1122 for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++I)
1123 cast<PHINode>(I)->addIncoming(UndefValue::get(I->getType()), NewBB);
1124 }
1125
1126 // Update DominatorTree, LoopInfo, and LCCSA analysis information.
1127 bool HasLoopExit = false;
1128 UpdateAnalysisInformation(BB, NewBB, Preds, DTU, DT, LI, MSSAU, PreserveLCSSA,
1129 HasLoopExit);
1130
1131 if (!Preds.empty()) {
1132 // Update the PHI nodes in BB with the values coming from NewBB.
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
1148BasicBlock *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, /*DTU=*/nullptr, DT, LI,
1154 MSSAU, PreserveLCSSA);
1155}
1156BasicBlock *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 /*DT=*/nullptr, LI, MSSAU, PreserveLCSSA);
1164}
1165
1166static 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!")((void)0);
1172
1173 // Create a new basic block for OrigBB's predecessors listed in Preds. Insert
1174 // it right before the original block.
1175 BasicBlock *NewBB1 = BasicBlock::Create(OrigBB->getContext(),
1176 OrigBB->getName() + Suffix1,
1177 OrigBB->getParent(), OrigBB);
1178 NewBBs.push_back(NewBB1);
1179
1180 // The new block unconditionally branches to the old block.
1181 BranchInst *BI1 = BranchInst::Create(OrigBB, NewBB1);
1182 BI1->setDebugLoc(OrigBB->getFirstNonPHI()->getDebugLoc());
1183
1184 // Move the edges from Preds to point to NewBB1 instead of OrigBB.
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 // This is slightly more strict than necessary; the minimum requirement
1187 // is that there be no more than one indirectbr branching to BB. And
1188 // all BlockAddress uses would need to be updated.
1189 assert(!isa<IndirectBrInst>(Preds[i]->getTerminator()) &&((void)0)
1190 "Cannot split an edge from an IndirectBrInst")((void)0);
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 // Update the PHI nodes in OrigBB with the values coming from NewBB1.
1199 UpdatePHINodes(OrigBB, NewBB1, Preds, BI1, HasLoopExit);
1200
1201 // Move the remaining edges from OrigBB to point to NewBB2.
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()) &&((void)0)
1208 "Cannot split an edge from an IndirectBrInst")((void)0);
1209 NewBB2Preds.push_back(Pred);
1210 e = pred_end(OrigBB);
1211 }
1212
1213 BasicBlock *NewBB2 = nullptr;
1214 if (!NewBB2Preds.empty()) {
1215 // Create another basic block for the rest of OrigBB's predecessors.
1216 NewBB2 = BasicBlock::Create(OrigBB->getContext(),
1217 OrigBB->getName() + Suffix2,
1218 OrigBB->getParent(), OrigBB);
1219 NewBBs.push_back(NewBB2);
1220
1221 // The new block unconditionally branches to the old block.
1222 BranchInst *BI2 = BranchInst::Create(OrigBB, NewBB2);
1223 BI2->setDebugLoc(OrigBB->getFirstNonPHI()->getDebugLoc());
1224
1225 // Move the remaining edges from OrigBB to point to NewBB2.
1226 for (BasicBlock *NewBB2Pred : NewBB2Preds)
1227 NewBB2Pred->getTerminator()->replaceUsesOfWith(OrigBB, NewBB2);
1228
1229 // Update DominatorTree, LoopInfo, and LCCSA analysis information.
1230 HasLoopExit = false;
1231 UpdateAnalysisInformation(OrigBB, NewBB2, NewBB2Preds, DTU, DT, LI, MSSAU,
1232 PreserveLCSSA, HasLoopExit);
1233
1234 // Update the PHI nodes in OrigBB with the values coming from NewBB2.
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 // Create a PHI node for the two cloned landingpad instructions only
1249 // if the original landingpad instruction has some uses.
1250 if (!LPad->use_empty()) {
1251 assert(!LPad->getType()->isTokenTy() &&((void)0)
1252 "Split cannot be applied if LPad is token type. Otherwise an "((void)0)
1253 "invalid PHINode of token type would be created.")((void)0);
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 // There is no second clone. Just replace the landing pad with the first
1262 // clone.
1263 LPad->replaceAllUsesWith(Clone1);
1264 LPad->eraseFromParent();
1265 }
1266}
1267
1268void 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 /*DTU=*/nullptr, DT, LI, MSSAU, PreserveLCSSA);
1278}
1279void 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, /*DT=*/nullptr, LI, MSSAU,
1
Passing null pointer value via 7th parameter 'DT'
→
1288 PreserveLCSSA);
1289}
1290
1291ReturnInst *llvm::FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB,
1292 BasicBlock *Pred,
1293 DomTreeUpdater *DTU) {
1294 Instruction *UncondBranch = Pred->getTerminator();
1295 // Clone the return and add it to the end of the predecessor.
1296 Instruction *NewRet = RI->clone();
1297 Pred->getInstList().push_back(NewRet);
1298
1299 // If the return instruction returns a value, and if the value was a
1300 // PHI node in "BB", propagate the right value into the return.
1301 for (Use &Op : NewRet->operands()) {
1302 Value *V = Op;
1303 Instruction *NewBC = nullptr;
1304 if (BitCastInst *BCI = dyn_cast<BitCastInst>(V)) {
1305 // Return value might be bitcasted. Clone and insert it before the
1306 // return instruction.
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 // Update any PHI nodes in the returning block to realize that we no
1339 // longer branch to them.
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
1349static Instruction *
1350SplitBlockAndInsertIfThenImpl(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(/*ifTrue*/ ThenBlock, /*ifFalse*/ 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 // Head dominates ThenBlock.
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
1418Instruction *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 /*DTU=*/nullptr, DT, LI, ThenBlock);
1427}
1428Instruction *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, /*DT=*/nullptr, LI,
1436 ThenBlock);
1437}
1438
1439void 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(/*ifTrue*/ThenBlock, /*ifFalse*/ElseBlock, Cond);
1455 HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights);
1456 ReplaceInstWithInst(HeadOldTerm, HeadNewTerm);
1457}
1458
1459BranchInst *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) // No predecessor
1473 return nullptr;
1474 Pred1 = *PI++;
1475 if (PI == PE) // Only one predecessor
1476 return nullptr;
1477 Pred2 = *PI++;
1478 if (PI != PE) // More than two predecessors
1479 return nullptr;
1480 }
1481
1482 // We can only handle branches. Other control flow will be lowered to
1483 // branches if possible anyway.
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 // Eliminate code duplication by ensuring that Pred1Br is conditional if
1490 // either are.
1491 if (Pred2Br->isConditional()) {
1492 // If both branches are conditional, we don't have an "if statement". In
1493 // reality, we could transform this case, but since the condition will be
1494 // required anyway, we stand no chance of eliminating it, so the xform is
1495 // probably not profitable.
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 // The only thing we have to watch out for here is to make sure that Pred2
1505 // doesn't have incoming edges from other blocks. If it does, the condition
1506 // doesn't dominate BB.
1507 if (!Pred2->getSinglePredecessor())
1508 return nullptr;
1509
1510 // If we found a conditional branch predecessor, make sure that it branches
1511 // to BB and Pred2Br. If it doesn't, this isn't an "if statement".
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 // We know that one arm of the conditional goes to BB, so the other must
1522 // go somewhere unrelated, and this must not be an "if statement".
1523 return nullptr;
1524 }
1525
1526 return Pred1Br;
1527 }
1528
1529 // Ok, if we got here, both predecessors end with an unconditional branch to
1530 // BB. Don't panic! If both blocks only have a single (identical)
1531 // predecessor, and THAT is a conditional branch, then we're all ok!
1532 BasicBlock *CommonPred = Pred1->getSinglePredecessor();
1533 if (CommonPred == nullptr || CommonPred != Pred2->getSinglePredecessor())
1534 return nullptr;
1535
1536 // Otherwise, if this is a conditional branch, then we can use it!
1537 BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator());
1538 if (!BI) return nullptr;
1539
1540 assert(BI->isConditional() && "Two successors but not conditional?")((void)0);
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// After creating a control flow hub, the operands of PHINodes in an outgoing
1552// block Out no longer match the predecessors of that block. Predecessors of Out
1553// that are incoming blocks to the hub are now replaced by just one edge from
1554// the hub. To match this new control flow, the corresponding values from each
1555// PHINode must now be moved a new PHINode in the first guard block of the hub.
1556//
1557// This operation cannot be performed with SSAUpdater, because it involves one
1558// new use: If the block Out is in the list of Incoming blocks, then the newly
1559// created PHI in the Hub will use itself along that edge from Out to Hub.
1560static 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())((void)0);
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
1589using BBPredicates = DenseMap<BasicBlock *, PHINode *>;
1590using BBSetVector = SetVector<BasicBlock *>;
1591
1592// Redirects the terminator of the incoming block to the first guard
1593// block in the hub. The condition of the original terminator (if it
1594// was conditional) and its original successors are returned as a
1595// tuple <condition, succ0, succ1>. The function additionally filters
1596// out successors that are not in the set of outgoing blocks.
1597//
1598// - condition is non-null iff the branch is conditional.
1599// - Succ1 is non-null iff the sole/taken target is an outgoing block.
1600// - Succ2 is non-null iff condition is non-null and the fallthrough
1601// target is an outgoing block.
1602static std::tuple<Value *, BasicBlock *, BasicBlock *>
1603redirectToHub(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)((void)0);
1615 } else {
1616 Succ1 = Branch->getSuccessor(1);
1617 Succ1 = Outgoing.count(Succ1) ? Succ1 : nullptr;
1618 assert(Succ0 || Succ1)((void)0);
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)((void)0);
1630 return std::make_tuple(Condition, Succ0, Succ1);
1631}
1632
1633// Capture the existing control flow as guard predicates, and redirect
1634// control flow from every incoming block to the first guard block in
1635// the hub.
1636//
1637// There is one guard predicate for each outgoing block OutBB. The
1638// predicate is a PHINode with one input for each InBB which
1639// represents whether the hub should transfer control flow to OutBB if
1640// it arrived from InBB. These predicates are NOT ORTHOGONAL. The Hub
1641// evaluates them in the same order as the Outgoing set-vector, and
1642// control branches to the first outgoing block whose predicate
1643// evaluates to true.
1644static 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 // The predicate for the last outgoing is trivially true, and so we
1653 // process only the first N-1 successors.
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")do { } while (false);
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 // Optimization: Consider an incoming block A with both successors
1671 // Succ0 and Succ1 in the set of outgoing blocks. The predicates
1672 // for Succ0 and Succ1 complement each other. If Succ0 is visited
1673 // first in the loop below, control will branch to Succ0 using the
1674 // corresponding predicate. But if that branch is not taken, then
1675 // control must reach Succ1, which means that the predicate for
1676 // Succ1 is always true.
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 // Optimization: When only one successor is an outgoing block,
1686 // the predicate is always true.
1687 if (!Succ0 || !Succ1 || OneSuccessorDone) {
1688 Phi->addIncoming(BoolTrue, In);
1689 continue;
1690 }
1691 assert(Succ0 && Succ1)((void)0);
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// For each outgoing block OutBB, create a guard block in the Hub. The
1705// first guard block was already created outside, and available as the
1706// first element in the vector of guard blocks.
1707//
1708// Each guard block terminates in a conditional branch that transfers
1709// control to the corresponding outgoing block or the next guard
1710// block. The last guard block has two outgoing blocks as successors
1711// since the condition for the final outgoing block is trivially
1712// true. So we create one less block (including the first guard block)
1713// than the number of outgoing blocks.
1714static 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())((void)0);
1722
1723 // To help keep the loop simple, temporarily append the last
1724 // outgoing block to the list of guard blocks.
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))((void)0);
1730 BranchInst::Create(Out, GuardBlocks[i + 1], GuardPredicates[Out],
1731 GuardBlocks[i]);
1732 }
1733
1734 // Remove the last block from the guard list.
1735 GuardBlocks.pop_back();
1736}
1737
1738BasicBlock *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 // Update the PHINodes in each outgoing block to match the new control flow.
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)((void)0);
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}