File: | build/source/llvm/lib/Transforms/Utils/Local.cpp |
Warning: | line 1917, column 31 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===- Local.cpp - Functions to perform local transformations -------------===// | |||
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 various local transformations to the | |||
10 | // program. | |||
11 | // | |||
12 | //===----------------------------------------------------------------------===// | |||
13 | ||||
14 | #include "llvm/Transforms/Utils/Local.h" | |||
15 | #include "llvm/ADT/APInt.h" | |||
16 | #include "llvm/ADT/DenseMap.h" | |||
17 | #include "llvm/ADT/DenseMapInfo.h" | |||
18 | #include "llvm/ADT/DenseSet.h" | |||
19 | #include "llvm/ADT/Hashing.h" | |||
20 | #include "llvm/ADT/STLExtras.h" | |||
21 | #include "llvm/ADT/SetVector.h" | |||
22 | #include "llvm/ADT/SmallPtrSet.h" | |||
23 | #include "llvm/ADT/SmallVector.h" | |||
24 | #include "llvm/ADT/Statistic.h" | |||
25 | #include "llvm/Analysis/AssumeBundleQueries.h" | |||
26 | #include "llvm/Analysis/ConstantFolding.h" | |||
27 | #include "llvm/Analysis/DomTreeUpdater.h" | |||
28 | #include "llvm/Analysis/InstructionSimplify.h" | |||
29 | #include "llvm/Analysis/MemoryBuiltins.h" | |||
30 | #include "llvm/Analysis/MemorySSAUpdater.h" | |||
31 | #include "llvm/Analysis/TargetLibraryInfo.h" | |||
32 | #include "llvm/Analysis/ValueTracking.h" | |||
33 | #include "llvm/Analysis/VectorUtils.h" | |||
34 | #include "llvm/BinaryFormat/Dwarf.h" | |||
35 | #include "llvm/IR/Argument.h" | |||
36 | #include "llvm/IR/Attributes.h" | |||
37 | #include "llvm/IR/BasicBlock.h" | |||
38 | #include "llvm/IR/CFG.h" | |||
39 | #include "llvm/IR/Constant.h" | |||
40 | #include "llvm/IR/ConstantRange.h" | |||
41 | #include "llvm/IR/Constants.h" | |||
42 | #include "llvm/IR/DIBuilder.h" | |||
43 | #include "llvm/IR/DataLayout.h" | |||
44 | #include "llvm/IR/DebugInfo.h" | |||
45 | #include "llvm/IR/DebugInfoMetadata.h" | |||
46 | #include "llvm/IR/DebugLoc.h" | |||
47 | #include "llvm/IR/DerivedTypes.h" | |||
48 | #include "llvm/IR/Dominators.h" | |||
49 | #include "llvm/IR/EHPersonalities.h" | |||
50 | #include "llvm/IR/Function.h" | |||
51 | #include "llvm/IR/GetElementPtrTypeIterator.h" | |||
52 | #include "llvm/IR/GlobalObject.h" | |||
53 | #include "llvm/IR/IRBuilder.h" | |||
54 | #include "llvm/IR/InstrTypes.h" | |||
55 | #include "llvm/IR/Instruction.h" | |||
56 | #include "llvm/IR/Instructions.h" | |||
57 | #include "llvm/IR/IntrinsicInst.h" | |||
58 | #include "llvm/IR/Intrinsics.h" | |||
59 | #include "llvm/IR/IntrinsicsWebAssembly.h" | |||
60 | #include "llvm/IR/LLVMContext.h" | |||
61 | #include "llvm/IR/MDBuilder.h" | |||
62 | #include "llvm/IR/Metadata.h" | |||
63 | #include "llvm/IR/Module.h" | |||
64 | #include "llvm/IR/PatternMatch.h" | |||
65 | #include "llvm/IR/ProfDataUtils.h" | |||
66 | #include "llvm/IR/Type.h" | |||
67 | #include "llvm/IR/Use.h" | |||
68 | #include "llvm/IR/User.h" | |||
69 | #include "llvm/IR/Value.h" | |||
70 | #include "llvm/IR/ValueHandle.h" | |||
71 | #include "llvm/Support/Casting.h" | |||
72 | #include "llvm/Support/Debug.h" | |||
73 | #include "llvm/Support/ErrorHandling.h" | |||
74 | #include "llvm/Support/KnownBits.h" | |||
75 | #include "llvm/Support/raw_ostream.h" | |||
76 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" | |||
77 | #include "llvm/Transforms/Utils/ValueMapper.h" | |||
78 | #include <algorithm> | |||
79 | #include <cassert> | |||
80 | #include <cstdint> | |||
81 | #include <iterator> | |||
82 | #include <map> | |||
83 | #include <optional> | |||
84 | #include <utility> | |||
85 | ||||
86 | using namespace llvm; | |||
87 | using namespace llvm::PatternMatch; | |||
88 | ||||
89 | #define DEBUG_TYPE"local" "local" | |||
90 | ||||
91 | STATISTIC(NumRemoved, "Number of unreachable basic blocks removed")static llvm::Statistic NumRemoved = {"local", "NumRemoved", "Number of unreachable basic blocks removed" }; | |||
92 | STATISTIC(NumPHICSEs, "Number of PHI's that got CSE'd")static llvm::Statistic NumPHICSEs = {"local", "NumPHICSEs", "Number of PHI's that got CSE'd" }; | |||
93 | ||||
94 | static cl::opt<bool> PHICSEDebugHash( | |||
95 | "phicse-debug-hash", | |||
96 | #ifdef EXPENSIVE_CHECKS | |||
97 | cl::init(true), | |||
98 | #else | |||
99 | cl::init(false), | |||
100 | #endif | |||
101 | cl::Hidden, | |||
102 | cl::desc("Perform extra assertion checking to verify that PHINodes's hash " | |||
103 | "function is well-behaved w.r.t. its isEqual predicate")); | |||
104 | ||||
105 | static cl::opt<unsigned> PHICSENumPHISmallSize( | |||
106 | "phicse-num-phi-smallsize", cl::init(32), cl::Hidden, | |||
107 | cl::desc( | |||
108 | "When the basic block contains not more than this number of PHI nodes, " | |||
109 | "perform a (faster!) exhaustive search instead of set-driven one.")); | |||
110 | ||||
111 | // Max recursion depth for collectBitParts used when detecting bswap and | |||
112 | // bitreverse idioms. | |||
113 | static const unsigned BitPartRecursionMaxDepth = 48; | |||
114 | ||||
115 | //===----------------------------------------------------------------------===// | |||
116 | // Local constant propagation. | |||
117 | // | |||
118 | ||||
119 | /// ConstantFoldTerminator - If a terminator instruction is predicated on a | |||
120 | /// constant value, convert it into an unconditional branch to the constant | |||
121 | /// destination. This is a nontrivial operation because the successors of this | |||
122 | /// basic block must have their PHI nodes updated. | |||
123 | /// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch | |||
124 | /// conditions and indirectbr addresses this might make dead if | |||
125 | /// DeleteDeadConditions is true. | |||
126 | bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions, | |||
127 | const TargetLibraryInfo *TLI, | |||
128 | DomTreeUpdater *DTU) { | |||
129 | Instruction *T = BB->getTerminator(); | |||
130 | IRBuilder<> Builder(T); | |||
131 | ||||
132 | // Branch - See if we are conditional jumping on constant | |||
133 | if (auto *BI = dyn_cast<BranchInst>(T)) { | |||
134 | if (BI->isUnconditional()) return false; // Can't optimize uncond branch | |||
135 | ||||
136 | BasicBlock *Dest1 = BI->getSuccessor(0); | |||
137 | BasicBlock *Dest2 = BI->getSuccessor(1); | |||
138 | ||||
139 | if (Dest2 == Dest1) { // Conditional branch to same location? | |||
140 | // This branch matches something like this: | |||
141 | // br bool %cond, label %Dest, label %Dest | |||
142 | // and changes it into: br label %Dest | |||
143 | ||||
144 | // Let the basic block know that we are letting go of one copy of it. | |||
145 | assert(BI->getParent() && "Terminator not inserted in block!")(static_cast <bool> (BI->getParent() && "Terminator not inserted in block!" ) ? void (0) : __assert_fail ("BI->getParent() && \"Terminator not inserted in block!\"" , "llvm/lib/Transforms/Utils/Local.cpp", 145, __extension__ __PRETTY_FUNCTION__ )); | |||
146 | Dest1->removePredecessor(BI->getParent()); | |||
147 | ||||
148 | // Replace the conditional branch with an unconditional one. | |||
149 | BranchInst *NewBI = Builder.CreateBr(Dest1); | |||
150 | ||||
151 | // Transfer the metadata to the new branch instruction. | |||
152 | NewBI->copyMetadata(*BI, {LLVMContext::MD_loop, LLVMContext::MD_dbg, | |||
153 | LLVMContext::MD_annotation}); | |||
154 | ||||
155 | Value *Cond = BI->getCondition(); | |||
156 | BI->eraseFromParent(); | |||
157 | if (DeleteDeadConditions) | |||
158 | RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI); | |||
159 | return true; | |||
160 | } | |||
161 | ||||
162 | if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition())) { | |||
163 | // Are we branching on constant? | |||
164 | // YES. Change to unconditional branch... | |||
165 | BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2; | |||
166 | BasicBlock *OldDest = Cond->getZExtValue() ? Dest2 : Dest1; | |||
167 | ||||
168 | // Let the basic block know that we are letting go of it. Based on this, | |||
169 | // it will adjust it's PHI nodes. | |||
170 | OldDest->removePredecessor(BB); | |||
171 | ||||
172 | // Replace the conditional branch with an unconditional one. | |||
173 | BranchInst *NewBI = Builder.CreateBr(Destination); | |||
174 | ||||
175 | // Transfer the metadata to the new branch instruction. | |||
176 | NewBI->copyMetadata(*BI, {LLVMContext::MD_loop, LLVMContext::MD_dbg, | |||
177 | LLVMContext::MD_annotation}); | |||
178 | ||||
179 | BI->eraseFromParent(); | |||
180 | if (DTU) | |||
181 | DTU->applyUpdates({{DominatorTree::Delete, BB, OldDest}}); | |||
182 | return true; | |||
183 | } | |||
184 | ||||
185 | return false; | |||
186 | } | |||
187 | ||||
188 | if (auto *SI = dyn_cast<SwitchInst>(T)) { | |||
189 | // If we are switching on a constant, we can convert the switch to an | |||
190 | // unconditional branch. | |||
191 | auto *CI = dyn_cast<ConstantInt>(SI->getCondition()); | |||
192 | BasicBlock *DefaultDest = SI->getDefaultDest(); | |||
193 | BasicBlock *TheOnlyDest = DefaultDest; | |||
194 | ||||
195 | // If the default is unreachable, ignore it when searching for TheOnlyDest. | |||
196 | if (isa<UnreachableInst>(DefaultDest->getFirstNonPHIOrDbg()) && | |||
197 | SI->getNumCases() > 0) { | |||
198 | TheOnlyDest = SI->case_begin()->getCaseSuccessor(); | |||
199 | } | |||
200 | ||||
201 | bool Changed = false; | |||
202 | ||||
203 | // Figure out which case it goes to. | |||
204 | for (auto It = SI->case_begin(), End = SI->case_end(); It != End;) { | |||
205 | // Found case matching a constant operand? | |||
206 | if (It->getCaseValue() == CI) { | |||
207 | TheOnlyDest = It->getCaseSuccessor(); | |||
208 | break; | |||
209 | } | |||
210 | ||||
211 | // Check to see if this branch is going to the same place as the default | |||
212 | // dest. If so, eliminate it as an explicit compare. | |||
213 | if (It->getCaseSuccessor() == DefaultDest) { | |||
214 | MDNode *MD = getValidBranchWeightMDNode(*SI); | |||
215 | unsigned NCases = SI->getNumCases(); | |||
216 | // Fold the case metadata into the default if there will be any branches | |||
217 | // left, unless the metadata doesn't match the switch. | |||
218 | if (NCases > 1 && MD) { | |||
219 | // Collect branch weights into a vector. | |||
220 | SmallVector<uint32_t, 8> Weights; | |||
221 | extractBranchWeights(MD, Weights); | |||
222 | ||||
223 | // Merge weight of this case to the default weight. | |||
224 | unsigned Idx = It->getCaseIndex(); | |||
225 | // TODO: Add overflow check. | |||
226 | Weights[0] += Weights[Idx + 1]; | |||
227 | // Remove weight for this case. | |||
228 | std::swap(Weights[Idx + 1], Weights.back()); | |||
229 | Weights.pop_back(); | |||
230 | SI->setMetadata(LLVMContext::MD_prof, | |||
231 | MDBuilder(BB->getContext()). | |||
232 | createBranchWeights(Weights)); | |||
233 | } | |||
234 | // Remove this entry. | |||
235 | BasicBlock *ParentBB = SI->getParent(); | |||
236 | DefaultDest->removePredecessor(ParentBB); | |||
237 | It = SI->removeCase(It); | |||
238 | End = SI->case_end(); | |||
239 | ||||
240 | // Removing this case may have made the condition constant. In that | |||
241 | // case, update CI and restart iteration through the cases. | |||
242 | if (auto *NewCI = dyn_cast<ConstantInt>(SI->getCondition())) { | |||
243 | CI = NewCI; | |||
244 | It = SI->case_begin(); | |||
245 | } | |||
246 | ||||
247 | Changed = true; | |||
248 | continue; | |||
249 | } | |||
250 | ||||
251 | // Otherwise, check to see if the switch only branches to one destination. | |||
252 | // We do this by reseting "TheOnlyDest" to null when we find two non-equal | |||
253 | // destinations. | |||
254 | if (It->getCaseSuccessor() != TheOnlyDest) | |||
255 | TheOnlyDest = nullptr; | |||
256 | ||||
257 | // Increment this iterator as we haven't removed the case. | |||
258 | ++It; | |||
259 | } | |||
260 | ||||
261 | if (CI && !TheOnlyDest) { | |||
262 | // Branching on a constant, but not any of the cases, go to the default | |||
263 | // successor. | |||
264 | TheOnlyDest = SI->getDefaultDest(); | |||
265 | } | |||
266 | ||||
267 | // If we found a single destination that we can fold the switch into, do so | |||
268 | // now. | |||
269 | if (TheOnlyDest) { | |||
270 | // Insert the new branch. | |||
271 | Builder.CreateBr(TheOnlyDest); | |||
272 | BasicBlock *BB = SI->getParent(); | |||
273 | ||||
274 | SmallSet<BasicBlock *, 8> RemovedSuccessors; | |||
275 | ||||
276 | // Remove entries from PHI nodes which we no longer branch to... | |||
277 | BasicBlock *SuccToKeep = TheOnlyDest; | |||
278 | for (BasicBlock *Succ : successors(SI)) { | |||
279 | if (DTU && Succ != TheOnlyDest) | |||
280 | RemovedSuccessors.insert(Succ); | |||
281 | // Found case matching a constant operand? | |||
282 | if (Succ == SuccToKeep) { | |||
283 | SuccToKeep = nullptr; // Don't modify the first branch to TheOnlyDest | |||
284 | } else { | |||
285 | Succ->removePredecessor(BB); | |||
286 | } | |||
287 | } | |||
288 | ||||
289 | // Delete the old switch. | |||
290 | Value *Cond = SI->getCondition(); | |||
291 | SI->eraseFromParent(); | |||
292 | if (DeleteDeadConditions) | |||
293 | RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI); | |||
294 | if (DTU) { | |||
295 | std::vector<DominatorTree::UpdateType> Updates; | |||
296 | Updates.reserve(RemovedSuccessors.size()); | |||
297 | for (auto *RemovedSuccessor : RemovedSuccessors) | |||
298 | Updates.push_back({DominatorTree::Delete, BB, RemovedSuccessor}); | |||
299 | DTU->applyUpdates(Updates); | |||
300 | } | |||
301 | return true; | |||
302 | } | |||
303 | ||||
304 | if (SI->getNumCases() == 1) { | |||
305 | // Otherwise, we can fold this switch into a conditional branch | |||
306 | // instruction if it has only one non-default destination. | |||
307 | auto FirstCase = *SI->case_begin(); | |||
308 | Value *Cond = Builder.CreateICmpEQ(SI->getCondition(), | |||
309 | FirstCase.getCaseValue(), "cond"); | |||
310 | ||||
311 | // Insert the new branch. | |||
312 | BranchInst *NewBr = Builder.CreateCondBr(Cond, | |||
313 | FirstCase.getCaseSuccessor(), | |||
314 | SI->getDefaultDest()); | |||
315 | SmallVector<uint32_t> Weights; | |||
316 | if (extractBranchWeights(*SI, Weights) && Weights.size() == 2) { | |||
317 | uint32_t DefWeight = Weights[0]; | |||
318 | uint32_t CaseWeight = Weights[1]; | |||
319 | // The TrueWeight should be the weight for the single case of SI. | |||
320 | NewBr->setMetadata(LLVMContext::MD_prof, | |||
321 | MDBuilder(BB->getContext()) | |||
322 | .createBranchWeights(CaseWeight, DefWeight)); | |||
323 | } | |||
324 | ||||
325 | // Update make.implicit metadata to the newly-created conditional branch. | |||
326 | MDNode *MakeImplicitMD = SI->getMetadata(LLVMContext::MD_make_implicit); | |||
327 | if (MakeImplicitMD) | |||
328 | NewBr->setMetadata(LLVMContext::MD_make_implicit, MakeImplicitMD); | |||
329 | ||||
330 | // Delete the old switch. | |||
331 | SI->eraseFromParent(); | |||
332 | return true; | |||
333 | } | |||
334 | return Changed; | |||
335 | } | |||
336 | ||||
337 | if (auto *IBI = dyn_cast<IndirectBrInst>(T)) { | |||
338 | // indirectbr blockaddress(@F, @BB) -> br label @BB | |||
339 | if (auto *BA = | |||
340 | dyn_cast<BlockAddress>(IBI->getAddress()->stripPointerCasts())) { | |||
341 | BasicBlock *TheOnlyDest = BA->getBasicBlock(); | |||
342 | SmallSet<BasicBlock *, 8> RemovedSuccessors; | |||
343 | ||||
344 | // Insert the new branch. | |||
345 | Builder.CreateBr(TheOnlyDest); | |||
346 | ||||
347 | BasicBlock *SuccToKeep = TheOnlyDest; | |||
348 | for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) { | |||
349 | BasicBlock *DestBB = IBI->getDestination(i); | |||
350 | if (DTU && DestBB != TheOnlyDest) | |||
351 | RemovedSuccessors.insert(DestBB); | |||
352 | if (IBI->getDestination(i) == SuccToKeep) { | |||
353 | SuccToKeep = nullptr; | |||
354 | } else { | |||
355 | DestBB->removePredecessor(BB); | |||
356 | } | |||
357 | } | |||
358 | Value *Address = IBI->getAddress(); | |||
359 | IBI->eraseFromParent(); | |||
360 | if (DeleteDeadConditions) | |||
361 | // Delete pointer cast instructions. | |||
362 | RecursivelyDeleteTriviallyDeadInstructions(Address, TLI); | |||
363 | ||||
364 | // Also zap the blockaddress constant if there are no users remaining, | |||
365 | // otherwise the destination is still marked as having its address taken. | |||
366 | if (BA->use_empty()) | |||
367 | BA->destroyConstant(); | |||
368 | ||||
369 | // If we didn't find our destination in the IBI successor list, then we | |||
370 | // have undefined behavior. Replace the unconditional branch with an | |||
371 | // 'unreachable' instruction. | |||
372 | if (SuccToKeep) { | |||
373 | BB->getTerminator()->eraseFromParent(); | |||
374 | new UnreachableInst(BB->getContext(), BB); | |||
375 | } | |||
376 | ||||
377 | if (DTU) { | |||
378 | std::vector<DominatorTree::UpdateType> Updates; | |||
379 | Updates.reserve(RemovedSuccessors.size()); | |||
380 | for (auto *RemovedSuccessor : RemovedSuccessors) | |||
381 | Updates.push_back({DominatorTree::Delete, BB, RemovedSuccessor}); | |||
382 | DTU->applyUpdates(Updates); | |||
383 | } | |||
384 | return true; | |||
385 | } | |||
386 | } | |||
387 | ||||
388 | return false; | |||
389 | } | |||
390 | ||||
391 | //===----------------------------------------------------------------------===// | |||
392 | // Local dead code elimination. | |||
393 | // | |||
394 | ||||
395 | /// isInstructionTriviallyDead - Return true if the result produced by the | |||
396 | /// instruction is not used, and the instruction has no side effects. | |||
397 | /// | |||
398 | bool llvm::isInstructionTriviallyDead(Instruction *I, | |||
399 | const TargetLibraryInfo *TLI) { | |||
400 | if (!I->use_empty()) | |||
401 | return false; | |||
402 | return wouldInstructionBeTriviallyDead(I, TLI); | |||
403 | } | |||
404 | ||||
405 | bool llvm::wouldInstructionBeTriviallyDeadOnUnusedPaths( | |||
406 | Instruction *I, const TargetLibraryInfo *TLI) { | |||
407 | // Instructions that are "markers" and have implied meaning on code around | |||
408 | // them (without explicit uses), are not dead on unused paths. | |||
409 | if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) | |||
410 | if (II->getIntrinsicID() == Intrinsic::stacksave || | |||
411 | II->getIntrinsicID() == Intrinsic::launder_invariant_group || | |||
412 | II->isLifetimeStartOrEnd()) | |||
413 | return false; | |||
414 | return wouldInstructionBeTriviallyDead(I, TLI); | |||
415 | } | |||
416 | ||||
417 | bool llvm::wouldInstructionBeTriviallyDead(Instruction *I, | |||
418 | const TargetLibraryInfo *TLI) { | |||
419 | if (I->isTerminator()) | |||
420 | return false; | |||
421 | ||||
422 | // We don't want the landingpad-like instructions removed by anything this | |||
423 | // general. | |||
424 | if (I->isEHPad()) | |||
425 | return false; | |||
426 | ||||
427 | // We don't want debug info removed by anything this general, unless | |||
428 | // debug info is empty. | |||
429 | if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(I)) { | |||
430 | if (DDI->getAddress()) | |||
431 | return false; | |||
432 | return true; | |||
433 | } | |||
434 | if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(I)) { | |||
435 | if (DVI->hasArgList() || DVI->getValue(0)) | |||
436 | return false; | |||
437 | return true; | |||
438 | } | |||
439 | if (DbgLabelInst *DLI = dyn_cast<DbgLabelInst>(I)) { | |||
440 | if (DLI->getLabel()) | |||
441 | return false; | |||
442 | return true; | |||
443 | } | |||
444 | ||||
445 | if (auto *CB = dyn_cast<CallBase>(I)) | |||
446 | if (isRemovableAlloc(CB, TLI)) | |||
447 | return true; | |||
448 | ||||
449 | if (!I->willReturn()) { | |||
450 | auto *II = dyn_cast<IntrinsicInst>(I); | |||
451 | if (!II) | |||
452 | return false; | |||
453 | ||||
454 | // TODO: These intrinsics are not safe to remove, because this may remove | |||
455 | // a well-defined trap. | |||
456 | switch (II->getIntrinsicID()) { | |||
457 | case Intrinsic::wasm_trunc_signed: | |||
458 | case Intrinsic::wasm_trunc_unsigned: | |||
459 | case Intrinsic::ptrauth_auth: | |||
460 | case Intrinsic::ptrauth_resign: | |||
461 | return true; | |||
462 | default: | |||
463 | return false; | |||
464 | } | |||
465 | } | |||
466 | ||||
467 | if (!I->mayHaveSideEffects()) | |||
468 | return true; | |||
469 | ||||
470 | // Special case intrinsics that "may have side effects" but can be deleted | |||
471 | // when dead. | |||
472 | if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { | |||
473 | // Safe to delete llvm.stacksave and launder.invariant.group if dead. | |||
474 | if (II->getIntrinsicID() == Intrinsic::stacksave || | |||
475 | II->getIntrinsicID() == Intrinsic::launder_invariant_group) | |||
476 | return true; | |||
477 | ||||
478 | if (II->isLifetimeStartOrEnd()) { | |||
479 | auto *Arg = II->getArgOperand(1); | |||
480 | // Lifetime intrinsics are dead when their right-hand is undef. | |||
481 | if (isa<UndefValue>(Arg)) | |||
482 | return true; | |||
483 | // If the right-hand is an alloc, global, or argument and the only uses | |||
484 | // are lifetime intrinsics then the intrinsics are dead. | |||
485 | if (isa<AllocaInst>(Arg) || isa<GlobalValue>(Arg) || isa<Argument>(Arg)) | |||
486 | return llvm::all_of(Arg->uses(), [](Use &Use) { | |||
487 | if (IntrinsicInst *IntrinsicUse = | |||
488 | dyn_cast<IntrinsicInst>(Use.getUser())) | |||
489 | return IntrinsicUse->isLifetimeStartOrEnd(); | |||
490 | return false; | |||
491 | }); | |||
492 | return false; | |||
493 | } | |||
494 | ||||
495 | // Assumptions are dead if their condition is trivially true. Guards on | |||
496 | // true are operationally no-ops. In the future we can consider more | |||
497 | // sophisticated tradeoffs for guards considering potential for check | |||
498 | // widening, but for now we keep things simple. | |||
499 | if ((II->getIntrinsicID() == Intrinsic::assume && | |||
500 | isAssumeWithEmptyBundle(cast<AssumeInst>(*II))) || | |||
501 | II->getIntrinsicID() == Intrinsic::experimental_guard) { | |||
502 | if (ConstantInt *Cond = dyn_cast<ConstantInt>(II->getArgOperand(0))) | |||
503 | return !Cond->isZero(); | |||
504 | ||||
505 | return false; | |||
506 | } | |||
507 | ||||
508 | if (auto *FPI = dyn_cast<ConstrainedFPIntrinsic>(I)) { | |||
509 | std::optional<fp::ExceptionBehavior> ExBehavior = | |||
510 | FPI->getExceptionBehavior(); | |||
511 | return *ExBehavior != fp::ebStrict; | |||
512 | } | |||
513 | } | |||
514 | ||||
515 | if (auto *Call = dyn_cast<CallBase>(I)) { | |||
516 | if (Value *FreedOp = getFreedOperand(Call, TLI)) | |||
517 | if (Constant *C = dyn_cast<Constant>(FreedOp)) | |||
518 | return C->isNullValue() || isa<UndefValue>(C); | |||
519 | if (isMathLibCallNoop(Call, TLI)) | |||
520 | return true; | |||
521 | } | |||
522 | ||||
523 | // Non-volatile atomic loads from constants can be removed. | |||
524 | if (auto *LI = dyn_cast<LoadInst>(I)) | |||
525 | if (auto *GV = dyn_cast<GlobalVariable>( | |||
526 | LI->getPointerOperand()->stripPointerCasts())) | |||
527 | if (!LI->isVolatile() && GV->isConstant()) | |||
528 | return true; | |||
529 | ||||
530 | return false; | |||
531 | } | |||
532 | ||||
533 | /// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a | |||
534 | /// trivially dead instruction, delete it. If that makes any of its operands | |||
535 | /// trivially dead, delete them too, recursively. Return true if any | |||
536 | /// instructions were deleted. | |||
537 | bool llvm::RecursivelyDeleteTriviallyDeadInstructions( | |||
538 | Value *V, const TargetLibraryInfo *TLI, MemorySSAUpdater *MSSAU, | |||
539 | std::function<void(Value *)> AboutToDeleteCallback) { | |||
540 | Instruction *I = dyn_cast<Instruction>(V); | |||
541 | if (!I || !isInstructionTriviallyDead(I, TLI)) | |||
542 | return false; | |||
543 | ||||
544 | SmallVector<WeakTrackingVH, 16> DeadInsts; | |||
545 | DeadInsts.push_back(I); | |||
546 | RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, TLI, MSSAU, | |||
547 | AboutToDeleteCallback); | |||
548 | ||||
549 | return true; | |||
550 | } | |||
551 | ||||
552 | bool llvm::RecursivelyDeleteTriviallyDeadInstructionsPermissive( | |||
553 | SmallVectorImpl<WeakTrackingVH> &DeadInsts, const TargetLibraryInfo *TLI, | |||
554 | MemorySSAUpdater *MSSAU, | |||
555 | std::function<void(Value *)> AboutToDeleteCallback) { | |||
556 | unsigned S = 0, E = DeadInsts.size(), Alive = 0; | |||
557 | for (; S != E; ++S) { | |||
558 | auto *I = dyn_cast<Instruction>(DeadInsts[S]); | |||
559 | if (!I || !isInstructionTriviallyDead(I)) { | |||
560 | DeadInsts[S] = nullptr; | |||
561 | ++Alive; | |||
562 | } | |||
563 | } | |||
564 | if (Alive == E) | |||
565 | return false; | |||
566 | RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, TLI, MSSAU, | |||
567 | AboutToDeleteCallback); | |||
568 | return true; | |||
569 | } | |||
570 | ||||
571 | void llvm::RecursivelyDeleteTriviallyDeadInstructions( | |||
572 | SmallVectorImpl<WeakTrackingVH> &DeadInsts, const TargetLibraryInfo *TLI, | |||
573 | MemorySSAUpdater *MSSAU, | |||
574 | std::function<void(Value *)> AboutToDeleteCallback) { | |||
575 | // Process the dead instruction list until empty. | |||
576 | while (!DeadInsts.empty()) { | |||
577 | Value *V = DeadInsts.pop_back_val(); | |||
578 | Instruction *I = cast_or_null<Instruction>(V); | |||
579 | if (!I) | |||
580 | continue; | |||
581 | assert(isInstructionTriviallyDead(I, TLI) &&(static_cast <bool> (isInstructionTriviallyDead(I, TLI) && "Live instruction found in dead worklist!") ? void (0) : __assert_fail ("isInstructionTriviallyDead(I, TLI) && \"Live instruction found in dead worklist!\"" , "llvm/lib/Transforms/Utils/Local.cpp", 582, __extension__ __PRETTY_FUNCTION__ )) | |||
582 | "Live instruction found in dead worklist!")(static_cast <bool> (isInstructionTriviallyDead(I, TLI) && "Live instruction found in dead worklist!") ? void (0) : __assert_fail ("isInstructionTriviallyDead(I, TLI) && \"Live instruction found in dead worklist!\"" , "llvm/lib/Transforms/Utils/Local.cpp", 582, __extension__ __PRETTY_FUNCTION__ )); | |||
583 | assert(I->use_empty() && "Instructions with uses are not dead.")(static_cast <bool> (I->use_empty() && "Instructions with uses are not dead." ) ? void (0) : __assert_fail ("I->use_empty() && \"Instructions with uses are not dead.\"" , "llvm/lib/Transforms/Utils/Local.cpp", 583, __extension__ __PRETTY_FUNCTION__ )); | |||
584 | ||||
585 | // Don't lose the debug info while deleting the instructions. | |||
586 | salvageDebugInfo(*I); | |||
587 | ||||
588 | if (AboutToDeleteCallback) | |||
589 | AboutToDeleteCallback(I); | |||
590 | ||||
591 | // Null out all of the instruction's operands to see if any operand becomes | |||
592 | // dead as we go. | |||
593 | for (Use &OpU : I->operands()) { | |||
594 | Value *OpV = OpU.get(); | |||
595 | OpU.set(nullptr); | |||
596 | ||||
597 | if (!OpV->use_empty()) | |||
598 | continue; | |||
599 | ||||
600 | // If the operand is an instruction that became dead as we nulled out the | |||
601 | // operand, and if it is 'trivially' dead, delete it in a future loop | |||
602 | // iteration. | |||
603 | if (Instruction *OpI = dyn_cast<Instruction>(OpV)) | |||
604 | if (isInstructionTriviallyDead(OpI, TLI)) | |||
605 | DeadInsts.push_back(OpI); | |||
606 | } | |||
607 | if (MSSAU) | |||
608 | MSSAU->removeMemoryAccess(I); | |||
609 | ||||
610 | I->eraseFromParent(); | |||
611 | } | |||
612 | } | |||
613 | ||||
614 | bool llvm::replaceDbgUsesWithUndef(Instruction *I) { | |||
615 | SmallVector<DbgVariableIntrinsic *, 1> DbgUsers; | |||
616 | findDbgUsers(DbgUsers, I); | |||
617 | for (auto *DII : DbgUsers) | |||
618 | DII->setKillLocation(); | |||
619 | return !DbgUsers.empty(); | |||
620 | } | |||
621 | ||||
622 | /// areAllUsesEqual - Check whether the uses of a value are all the same. | |||
623 | /// This is similar to Instruction::hasOneUse() except this will also return | |||
624 | /// true when there are no uses or multiple uses that all refer to the same | |||
625 | /// value. | |||
626 | static bool areAllUsesEqual(Instruction *I) { | |||
627 | Value::user_iterator UI = I->user_begin(); | |||
628 | Value::user_iterator UE = I->user_end(); | |||
629 | if (UI == UE) | |||
630 | return true; | |||
631 | ||||
632 | User *TheUse = *UI; | |||
633 | for (++UI; UI != UE; ++UI) { | |||
634 | if (*UI != TheUse) | |||
635 | return false; | |||
636 | } | |||
637 | return true; | |||
638 | } | |||
639 | ||||
640 | /// RecursivelyDeleteDeadPHINode - If the specified value is an effectively | |||
641 | /// dead PHI node, due to being a def-use chain of single-use nodes that | |||
642 | /// either forms a cycle or is terminated by a trivially dead instruction, | |||
643 | /// delete it. If that makes any of its operands trivially dead, delete them | |||
644 | /// too, recursively. Return true if a change was made. | |||
645 | bool llvm::RecursivelyDeleteDeadPHINode(PHINode *PN, | |||
646 | const TargetLibraryInfo *TLI, | |||
647 | llvm::MemorySSAUpdater *MSSAU) { | |||
648 | SmallPtrSet<Instruction*, 4> Visited; | |||
649 | for (Instruction *I = PN; areAllUsesEqual(I) && !I->mayHaveSideEffects(); | |||
650 | I = cast<Instruction>(*I->user_begin())) { | |||
651 | if (I->use_empty()) | |||
652 | return RecursivelyDeleteTriviallyDeadInstructions(I, TLI, MSSAU); | |||
653 | ||||
654 | // If we find an instruction more than once, we're on a cycle that | |||
655 | // won't prove fruitful. | |||
656 | if (!Visited.insert(I).second) { | |||
657 | // Break the cycle and delete the instruction and its operands. | |||
658 | I->replaceAllUsesWith(PoisonValue::get(I->getType())); | |||
659 | (void)RecursivelyDeleteTriviallyDeadInstructions(I, TLI, MSSAU); | |||
660 | return true; | |||
661 | } | |||
662 | } | |||
663 | return false; | |||
664 | } | |||
665 | ||||
666 | static bool | |||
667 | simplifyAndDCEInstruction(Instruction *I, | |||
668 | SmallSetVector<Instruction *, 16> &WorkList, | |||
669 | const DataLayout &DL, | |||
670 | const TargetLibraryInfo *TLI) { | |||
671 | if (isInstructionTriviallyDead(I, TLI)) { | |||
672 | salvageDebugInfo(*I); | |||
673 | ||||
674 | // Null out all of the instruction's operands to see if any operand becomes | |||
675 | // dead as we go. | |||
676 | for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { | |||
677 | Value *OpV = I->getOperand(i); | |||
678 | I->setOperand(i, nullptr); | |||
679 | ||||
680 | if (!OpV->use_empty() || I == OpV) | |||
681 | continue; | |||
682 | ||||
683 | // If the operand is an instruction that became dead as we nulled out the | |||
684 | // operand, and if it is 'trivially' dead, delete it in a future loop | |||
685 | // iteration. | |||
686 | if (Instruction *OpI = dyn_cast<Instruction>(OpV)) | |||
687 | if (isInstructionTriviallyDead(OpI, TLI)) | |||
688 | WorkList.insert(OpI); | |||
689 | } | |||
690 | ||||
691 | I->eraseFromParent(); | |||
692 | ||||
693 | return true; | |||
694 | } | |||
695 | ||||
696 | if (Value *SimpleV = simplifyInstruction(I, DL)) { | |||
697 | // Add the users to the worklist. CAREFUL: an instruction can use itself, | |||
698 | // in the case of a phi node. | |||
699 | for (User *U : I->users()) { | |||
700 | if (U != I) { | |||
701 | WorkList.insert(cast<Instruction>(U)); | |||
702 | } | |||
703 | } | |||
704 | ||||
705 | // Replace the instruction with its simplified value. | |||
706 | bool Changed = false; | |||
707 | if (!I->use_empty()) { | |||
708 | I->replaceAllUsesWith(SimpleV); | |||
709 | Changed = true; | |||
710 | } | |||
711 | if (isInstructionTriviallyDead(I, TLI)) { | |||
712 | I->eraseFromParent(); | |||
713 | Changed = true; | |||
714 | } | |||
715 | return Changed; | |||
716 | } | |||
717 | return false; | |||
718 | } | |||
719 | ||||
720 | /// SimplifyInstructionsInBlock - Scan the specified basic block and try to | |||
721 | /// simplify any instructions in it and recursively delete dead instructions. | |||
722 | /// | |||
723 | /// This returns true if it changed the code, note that it can delete | |||
724 | /// instructions in other blocks as well in this block. | |||
725 | bool llvm::SimplifyInstructionsInBlock(BasicBlock *BB, | |||
726 | const TargetLibraryInfo *TLI) { | |||
727 | bool MadeChange = false; | |||
728 | const DataLayout &DL = BB->getModule()->getDataLayout(); | |||
729 | ||||
730 | #ifndef NDEBUG | |||
731 | // In debug builds, ensure that the terminator of the block is never replaced | |||
732 | // or deleted by these simplifications. The idea of simplification is that it | |||
733 | // cannot introduce new instructions, and there is no way to replace the | |||
734 | // terminator of a block without introducing a new instruction. | |||
735 | AssertingVH<Instruction> TerminatorVH(&BB->back()); | |||
736 | #endif | |||
737 | ||||
738 | SmallSetVector<Instruction *, 16> WorkList; | |||
739 | // Iterate over the original function, only adding insts to the worklist | |||
740 | // if they actually need to be revisited. This avoids having to pre-init | |||
741 | // the worklist with the entire function's worth of instructions. | |||
742 | for (BasicBlock::iterator BI = BB->begin(), E = std::prev(BB->end()); | |||
743 | BI != E;) { | |||
744 | assert(!BI->isTerminator())(static_cast <bool> (!BI->isTerminator()) ? void (0) : __assert_fail ("!BI->isTerminator()", "llvm/lib/Transforms/Utils/Local.cpp" , 744, __extension__ __PRETTY_FUNCTION__)); | |||
745 | Instruction *I = &*BI; | |||
746 | ++BI; | |||
747 | ||||
748 | // We're visiting this instruction now, so make sure it's not in the | |||
749 | // worklist from an earlier visit. | |||
750 | if (!WorkList.count(I)) | |||
751 | MadeChange |= simplifyAndDCEInstruction(I, WorkList, DL, TLI); | |||
752 | } | |||
753 | ||||
754 | while (!WorkList.empty()) { | |||
755 | Instruction *I = WorkList.pop_back_val(); | |||
756 | MadeChange |= simplifyAndDCEInstruction(I, WorkList, DL, TLI); | |||
757 | } | |||
758 | return MadeChange; | |||
759 | } | |||
760 | ||||
761 | //===----------------------------------------------------------------------===// | |||
762 | // Control Flow Graph Restructuring. | |||
763 | // | |||
764 | ||||
765 | void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, | |||
766 | DomTreeUpdater *DTU) { | |||
767 | ||||
768 | // If BB has single-entry PHI nodes, fold them. | |||
769 | while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) { | |||
770 | Value *NewVal = PN->getIncomingValue(0); | |||
771 | // Replace self referencing PHI with poison, it must be dead. | |||
772 | if (NewVal == PN) NewVal = PoisonValue::get(PN->getType()); | |||
773 | PN->replaceAllUsesWith(NewVal); | |||
774 | PN->eraseFromParent(); | |||
775 | } | |||
776 | ||||
777 | BasicBlock *PredBB = DestBB->getSinglePredecessor(); | |||
778 | assert(PredBB && "Block doesn't have a single predecessor!")(static_cast <bool> (PredBB && "Block doesn't have a single predecessor!" ) ? void (0) : __assert_fail ("PredBB && \"Block doesn't have a single predecessor!\"" , "llvm/lib/Transforms/Utils/Local.cpp", 778, __extension__ __PRETTY_FUNCTION__ )); | |||
779 | ||||
780 | bool ReplaceEntryBB = PredBB->isEntryBlock(); | |||
781 | ||||
782 | // DTU updates: Collect all the edges that enter | |||
783 | // PredBB. These dominator edges will be redirected to DestBB. | |||
784 | SmallVector<DominatorTree::UpdateType, 32> Updates; | |||
785 | ||||
786 | if (DTU) { | |||
787 | // To avoid processing the same predecessor more than once. | |||
788 | SmallPtrSet<BasicBlock *, 2> SeenPreds; | |||
789 | Updates.reserve(Updates.size() + 2 * pred_size(PredBB) + 1); | |||
790 | for (BasicBlock *PredOfPredBB : predecessors(PredBB)) | |||
791 | // This predecessor of PredBB may already have DestBB as a successor. | |||
792 | if (PredOfPredBB != PredBB) | |||
793 | if (SeenPreds.insert(PredOfPredBB).second) | |||
794 | Updates.push_back({DominatorTree::Insert, PredOfPredBB, DestBB}); | |||
795 | SeenPreds.clear(); | |||
796 | for (BasicBlock *PredOfPredBB : predecessors(PredBB)) | |||
797 | if (SeenPreds.insert(PredOfPredBB).second) | |||
798 | Updates.push_back({DominatorTree::Delete, PredOfPredBB, PredBB}); | |||
799 | Updates.push_back({DominatorTree::Delete, PredBB, DestBB}); | |||
800 | } | |||
801 | ||||
802 | // Zap anything that took the address of DestBB. Not doing this will give the | |||
803 | // address an invalid value. | |||
804 | if (DestBB->hasAddressTaken()) { | |||
805 | BlockAddress *BA = BlockAddress::get(DestBB); | |||
806 | Constant *Replacement = | |||
807 | ConstantInt::get(Type::getInt32Ty(BA->getContext()), 1); | |||
808 | BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement, | |||
809 | BA->getType())); | |||
810 | BA->destroyConstant(); | |||
811 | } | |||
812 | ||||
813 | // Anything that branched to PredBB now branches to DestBB. | |||
814 | PredBB->replaceAllUsesWith(DestBB); | |||
815 | ||||
816 | // Splice all the instructions from PredBB to DestBB. | |||
817 | PredBB->getTerminator()->eraseFromParent(); | |||
818 | DestBB->splice(DestBB->begin(), PredBB); | |||
819 | new UnreachableInst(PredBB->getContext(), PredBB); | |||
820 | ||||
821 | // If the PredBB is the entry block of the function, move DestBB up to | |||
822 | // become the entry block after we erase PredBB. | |||
823 | if (ReplaceEntryBB) | |||
824 | DestBB->moveAfter(PredBB); | |||
825 | ||||
826 | if (DTU) { | |||
827 | assert(PredBB->size() == 1 &&(static_cast <bool> (PredBB->size() == 1 && isa <UnreachableInst>(PredBB->getTerminator()) && "The successor list of PredBB isn't empty before " "applying corresponding DTU updates." ) ? void (0) : __assert_fail ("PredBB->size() == 1 && isa<UnreachableInst>(PredBB->getTerminator()) && \"The successor list of PredBB isn't empty before \" \"applying corresponding DTU updates.\"" , "llvm/lib/Transforms/Utils/Local.cpp", 830, __extension__ __PRETTY_FUNCTION__ )) | |||
828 | isa<UnreachableInst>(PredBB->getTerminator()) &&(static_cast <bool> (PredBB->size() == 1 && isa <UnreachableInst>(PredBB->getTerminator()) && "The successor list of PredBB isn't empty before " "applying corresponding DTU updates." ) ? void (0) : __assert_fail ("PredBB->size() == 1 && isa<UnreachableInst>(PredBB->getTerminator()) && \"The successor list of PredBB isn't empty before \" \"applying corresponding DTU updates.\"" , "llvm/lib/Transforms/Utils/Local.cpp", 830, __extension__ __PRETTY_FUNCTION__ )) | |||
829 | "The successor list of PredBB isn't empty before "(static_cast <bool> (PredBB->size() == 1 && isa <UnreachableInst>(PredBB->getTerminator()) && "The successor list of PredBB isn't empty before " "applying corresponding DTU updates." ) ? void (0) : __assert_fail ("PredBB->size() == 1 && isa<UnreachableInst>(PredBB->getTerminator()) && \"The successor list of PredBB isn't empty before \" \"applying corresponding DTU updates.\"" , "llvm/lib/Transforms/Utils/Local.cpp", 830, __extension__ __PRETTY_FUNCTION__ )) | |||
830 | "applying corresponding DTU updates.")(static_cast <bool> (PredBB->size() == 1 && isa <UnreachableInst>(PredBB->getTerminator()) && "The successor list of PredBB isn't empty before " "applying corresponding DTU updates." ) ? void (0) : __assert_fail ("PredBB->size() == 1 && isa<UnreachableInst>(PredBB->getTerminator()) && \"The successor list of PredBB isn't empty before \" \"applying corresponding DTU updates.\"" , "llvm/lib/Transforms/Utils/Local.cpp", 830, __extension__ __PRETTY_FUNCTION__ )); | |||
831 | DTU->applyUpdatesPermissive(Updates); | |||
832 | DTU->deleteBB(PredBB); | |||
833 | // Recalculation of DomTree is needed when updating a forward DomTree and | |||
834 | // the Entry BB is replaced. | |||
835 | if (ReplaceEntryBB && DTU->hasDomTree()) { | |||
836 | // The entry block was removed and there is no external interface for | |||
837 | // the dominator tree to be notified of this change. In this corner-case | |||
838 | // we recalculate the entire tree. | |||
839 | DTU->recalculate(*(DestBB->getParent())); | |||
840 | } | |||
841 | } | |||
842 | ||||
843 | else { | |||
844 | PredBB->eraseFromParent(); // Nuke BB if DTU is nullptr. | |||
845 | } | |||
846 | } | |||
847 | ||||
848 | /// Return true if we can choose one of these values to use in place of the | |||
849 | /// other. Note that we will always choose the non-undef value to keep. | |||
850 | static bool CanMergeValues(Value *First, Value *Second) { | |||
851 | return First == Second || isa<UndefValue>(First) || isa<UndefValue>(Second); | |||
852 | } | |||
853 | ||||
854 | /// Return true if we can fold BB, an almost-empty BB ending in an unconditional | |||
855 | /// branch to Succ, into Succ. | |||
856 | /// | |||
857 | /// Assumption: Succ is the single successor for BB. | |||
858 | static bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) { | |||
859 | assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!")(static_cast <bool> (*succ_begin(BB) == Succ && "Succ is not successor of BB!") ? void (0) : __assert_fail ( "*succ_begin(BB) == Succ && \"Succ is not successor of BB!\"" , "llvm/lib/Transforms/Utils/Local.cpp", 859, __extension__ __PRETTY_FUNCTION__ )); | |||
860 | ||||
861 | LLVM_DEBUG(dbgs() << "Looking to fold " << BB->getName() << " into "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("local")) { dbgs() << "Looking to fold " << BB-> getName() << " into " << Succ->getName() << "\n"; } } while (false) | |||
862 | << Succ->getName() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("local")) { dbgs() << "Looking to fold " << BB-> getName() << " into " << Succ->getName() << "\n"; } } while (false); | |||
863 | // Shortcut, if there is only a single predecessor it must be BB and merging | |||
864 | // is always safe | |||
865 | if (Succ->getSinglePredecessor()) return true; | |||
866 | ||||
867 | // Make a list of the predecessors of BB | |||
868 | SmallPtrSet<BasicBlock*, 16> BBPreds(pred_begin(BB), pred_end(BB)); | |||
869 | ||||
870 | // Look at all the phi nodes in Succ, to see if they present a conflict when | |||
871 | // merging these blocks | |||
872 | for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { | |||
873 | PHINode *PN = cast<PHINode>(I); | |||
874 | ||||
875 | // If the incoming value from BB is again a PHINode in | |||
876 | // BB which has the same incoming value for *PI as PN does, we can | |||
877 | // merge the phi nodes and then the blocks can still be merged | |||
878 | PHINode *BBPN = dyn_cast<PHINode>(PN->getIncomingValueForBlock(BB)); | |||
879 | if (BBPN && BBPN->getParent() == BB) { | |||
880 | for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) { | |||
881 | BasicBlock *IBB = PN->getIncomingBlock(PI); | |||
882 | if (BBPreds.count(IBB) && | |||
883 | !CanMergeValues(BBPN->getIncomingValueForBlock(IBB), | |||
884 | PN->getIncomingValue(PI))) { | |||
885 | LLVM_DEBUG(dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("local")) { dbgs() << "Can't fold, phi node " << PN->getName() << " in " << Succ->getName() << " is conflicting with " << BBPN->getName() << " with regard to common predecessor " << IBB-> getName() << "\n"; } } while (false) | |||
886 | << "Can't fold, phi node " << PN->getName() << " in "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("local")) { dbgs() << "Can't fold, phi node " << PN->getName() << " in " << Succ->getName() << " is conflicting with " << BBPN->getName() << " with regard to common predecessor " << IBB-> getName() << "\n"; } } while (false) | |||
887 | << Succ->getName() << " is conflicting with "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("local")) { dbgs() << "Can't fold, phi node " << PN->getName() << " in " << Succ->getName() << " is conflicting with " << BBPN->getName() << " with regard to common predecessor " << IBB-> getName() << "\n"; } } while (false) | |||
888 | << BBPN->getName() << " with regard to common predecessor "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("local")) { dbgs() << "Can't fold, phi node " << PN->getName() << " in " << Succ->getName() << " is conflicting with " << BBPN->getName() << " with regard to common predecessor " << IBB-> getName() << "\n"; } } while (false) | |||
889 | << IBB->getName() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("local")) { dbgs() << "Can't fold, phi node " << PN->getName() << " in " << Succ->getName() << " is conflicting with " << BBPN->getName() << " with regard to common predecessor " << IBB-> getName() << "\n"; } } while (false); | |||
890 | return false; | |||
891 | } | |||
892 | } | |||
893 | } else { | |||
894 | Value* Val = PN->getIncomingValueForBlock(BB); | |||
895 | for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) { | |||
896 | // See if the incoming value for the common predecessor is equal to the | |||
897 | // one for BB, in which case this phi node will not prevent the merging | |||
898 | // of the block. | |||
899 | BasicBlock *IBB = PN->getIncomingBlock(PI); | |||
900 | if (BBPreds.count(IBB) && | |||
901 | !CanMergeValues(Val, PN->getIncomingValue(PI))) { | |||
902 | LLVM_DEBUG(dbgs() << "Can't fold, phi node " << PN->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("local")) { dbgs() << "Can't fold, phi node " << PN->getName() << " in " << Succ->getName() << " is conflicting with regard to common " << "predecessor " << IBB->getName() << "\n"; } } while (false) | |||
903 | << " in " << Succ->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("local")) { dbgs() << "Can't fold, phi node " << PN->getName() << " in " << Succ->getName() << " is conflicting with regard to common " << "predecessor " << IBB->getName() << "\n"; } } while (false) | |||
904 | << " is conflicting with regard to common "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("local")) { dbgs() << "Can't fold, phi node " << PN->getName() << " in " << Succ->getName() << " is conflicting with regard to common " << "predecessor " << IBB->getName() << "\n"; } } while (false) | |||
905 | << "predecessor " << IBB->getName() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("local")) { dbgs() << "Can't fold, phi node " << PN->getName() << " in " << Succ->getName() << " is conflicting with regard to common " << "predecessor " << IBB->getName() << "\n"; } } while (false); | |||
906 | return false; | |||
907 | } | |||
908 | } | |||
909 | } | |||
910 | } | |||
911 | ||||
912 | return true; | |||
913 | } | |||
914 | ||||
915 | using PredBlockVector = SmallVector<BasicBlock *, 16>; | |||
916 | using IncomingValueMap = DenseMap<BasicBlock *, Value *>; | |||
917 | ||||
918 | /// Determines the value to use as the phi node input for a block. | |||
919 | /// | |||
920 | /// Select between \p OldVal any value that we know flows from \p BB | |||
921 | /// to a particular phi on the basis of which one (if either) is not | |||
922 | /// undef. Update IncomingValues based on the selected value. | |||
923 | /// | |||
924 | /// \param OldVal The value we are considering selecting. | |||
925 | /// \param BB The block that the value flows in from. | |||
926 | /// \param IncomingValues A map from block-to-value for other phi inputs | |||
927 | /// that we have examined. | |||
928 | /// | |||
929 | /// \returns the selected value. | |||
930 | static Value *selectIncomingValueForBlock(Value *OldVal, BasicBlock *BB, | |||
931 | IncomingValueMap &IncomingValues) { | |||
932 | if (!isa<UndefValue>(OldVal)) { | |||
933 | assert((!IncomingValues.count(BB) ||(static_cast <bool> ((!IncomingValues.count(BB) || IncomingValues .find(BB)->second == OldVal) && "Expected OldVal to match incoming value from BB!" ) ? void (0) : __assert_fail ("(!IncomingValues.count(BB) || IncomingValues.find(BB)->second == OldVal) && \"Expected OldVal to match incoming value from BB!\"" , "llvm/lib/Transforms/Utils/Local.cpp", 935, __extension__ __PRETTY_FUNCTION__ )) | |||
934 | IncomingValues.find(BB)->second == OldVal) &&(static_cast <bool> ((!IncomingValues.count(BB) || IncomingValues .find(BB)->second == OldVal) && "Expected OldVal to match incoming value from BB!" ) ? void (0) : __assert_fail ("(!IncomingValues.count(BB) || IncomingValues.find(BB)->second == OldVal) && \"Expected OldVal to match incoming value from BB!\"" , "llvm/lib/Transforms/Utils/Local.cpp", 935, __extension__ __PRETTY_FUNCTION__ )) | |||
935 | "Expected OldVal to match incoming value from BB!")(static_cast <bool> ((!IncomingValues.count(BB) || IncomingValues .find(BB)->second == OldVal) && "Expected OldVal to match incoming value from BB!" ) ? void (0) : __assert_fail ("(!IncomingValues.count(BB) || IncomingValues.find(BB)->second == OldVal) && \"Expected OldVal to match incoming value from BB!\"" , "llvm/lib/Transforms/Utils/Local.cpp", 935, __extension__ __PRETTY_FUNCTION__ )); | |||
936 | ||||
937 | IncomingValues.insert(std::make_pair(BB, OldVal)); | |||
938 | return OldVal; | |||
939 | } | |||
940 | ||||
941 | IncomingValueMap::const_iterator It = IncomingValues.find(BB); | |||
942 | if (It != IncomingValues.end()) return It->second; | |||
943 | ||||
944 | return OldVal; | |||
945 | } | |||
946 | ||||
947 | /// Create a map from block to value for the operands of a | |||
948 | /// given phi. | |||
949 | /// | |||
950 | /// Create a map from block to value for each non-undef value flowing | |||
951 | /// into \p PN. | |||
952 | /// | |||
953 | /// \param PN The phi we are collecting the map for. | |||
954 | /// \param IncomingValues [out] The map from block to value for this phi. | |||
955 | static void gatherIncomingValuesToPhi(PHINode *PN, | |||
956 | IncomingValueMap &IncomingValues) { | |||
957 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { | |||
958 | BasicBlock *BB = PN->getIncomingBlock(i); | |||
959 | Value *V = PN->getIncomingValue(i); | |||
960 | ||||
961 | if (!isa<UndefValue>(V)) | |||
962 | IncomingValues.insert(std::make_pair(BB, V)); | |||
963 | } | |||
964 | } | |||
965 | ||||
966 | /// Replace the incoming undef values to a phi with the values | |||
967 | /// from a block-to-value map. | |||
968 | /// | |||
969 | /// \param PN The phi we are replacing the undefs in. | |||
970 | /// \param IncomingValues A map from block to value. | |||
971 | static void replaceUndefValuesInPhi(PHINode *PN, | |||
972 | const IncomingValueMap &IncomingValues) { | |||
973 | SmallVector<unsigned> TrueUndefOps; | |||
974 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { | |||
975 | Value *V = PN->getIncomingValue(i); | |||
976 | ||||
977 | if (!isa<UndefValue>(V)) continue; | |||
978 | ||||
979 | BasicBlock *BB = PN->getIncomingBlock(i); | |||
980 | IncomingValueMap::const_iterator It = IncomingValues.find(BB); | |||
981 | ||||
982 | // Keep track of undef/poison incoming values. Those must match, so we fix | |||
983 | // them up below if needed. | |||
984 | // Note: this is conservatively correct, but we could try harder and group | |||
985 | // the undef values per incoming basic block. | |||
986 | if (It == IncomingValues.end()) { | |||
987 | TrueUndefOps.push_back(i); | |||
988 | continue; | |||
989 | } | |||
990 | ||||
991 | // There is a defined value for this incoming block, so map this undef | |||
992 | // incoming value to the defined value. | |||
993 | PN->setIncomingValue(i, It->second); | |||
994 | } | |||
995 | ||||
996 | // If there are both undef and poison values incoming, then convert those | |||
997 | // values to undef. It is invalid to have different values for the same | |||
998 | // incoming block. | |||
999 | unsigned PoisonCount = count_if(TrueUndefOps, [&](unsigned i) { | |||
1000 | return isa<PoisonValue>(PN->getIncomingValue(i)); | |||
1001 | }); | |||
1002 | if (PoisonCount != 0 && PoisonCount != TrueUndefOps.size()) { | |||
1003 | for (unsigned i : TrueUndefOps) | |||
1004 | PN->setIncomingValue(i, UndefValue::get(PN->getType())); | |||
1005 | } | |||
1006 | } | |||
1007 | ||||
1008 | /// Replace a value flowing from a block to a phi with | |||
1009 | /// potentially multiple instances of that value flowing from the | |||
1010 | /// block's predecessors to the phi. | |||
1011 | /// | |||
1012 | /// \param BB The block with the value flowing into the phi. | |||
1013 | /// \param BBPreds The predecessors of BB. | |||
1014 | /// \param PN The phi that we are updating. | |||
1015 | static void redirectValuesFromPredecessorsToPhi(BasicBlock *BB, | |||
1016 | const PredBlockVector &BBPreds, | |||
1017 | PHINode *PN) { | |||
1018 | Value *OldVal = PN->removeIncomingValue(BB, false); | |||
1019 | assert(OldVal && "No entry in PHI for Pred BB!")(static_cast <bool> (OldVal && "No entry in PHI for Pred BB!" ) ? void (0) : __assert_fail ("OldVal && \"No entry in PHI for Pred BB!\"" , "llvm/lib/Transforms/Utils/Local.cpp", 1019, __extension__ __PRETTY_FUNCTION__ )); | |||
1020 | ||||
1021 | IncomingValueMap IncomingValues; | |||
1022 | ||||
1023 | // We are merging two blocks - BB, and the block containing PN - and | |||
1024 | // as a result we need to redirect edges from the predecessors of BB | |||
1025 | // to go to the block containing PN, and update PN | |||
1026 | // accordingly. Since we allow merging blocks in the case where the | |||
1027 | // predecessor and successor blocks both share some predecessors, | |||
1028 | // and where some of those common predecessors might have undef | |||
1029 | // values flowing into PN, we want to rewrite those values to be | |||
1030 | // consistent with the non-undef values. | |||
1031 | ||||
1032 | gatherIncomingValuesToPhi(PN, IncomingValues); | |||
1033 | ||||
1034 | // If this incoming value is one of the PHI nodes in BB, the new entries | |||
1035 | // in the PHI node are the entries from the old PHI. | |||
1036 | if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) { | |||
1037 | PHINode *OldValPN = cast<PHINode>(OldVal); | |||
1038 | for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i) { | |||
1039 | // Note that, since we are merging phi nodes and BB and Succ might | |||
1040 | // have common predecessors, we could end up with a phi node with | |||
1041 | // identical incoming branches. This will be cleaned up later (and | |||
1042 | // will trigger asserts if we try to clean it up now, without also | |||
1043 | // simplifying the corresponding conditional branch). | |||
1044 | BasicBlock *PredBB = OldValPN->getIncomingBlock(i); | |||
1045 | Value *PredVal = OldValPN->getIncomingValue(i); | |||
1046 | Value *Selected = selectIncomingValueForBlock(PredVal, PredBB, | |||
1047 | IncomingValues); | |||
1048 | ||||
1049 | // And add a new incoming value for this predecessor for the | |||
1050 | // newly retargeted branch. | |||
1051 | PN->addIncoming(Selected, PredBB); | |||
1052 | } | |||
1053 | } else { | |||
1054 | for (unsigned i = 0, e = BBPreds.size(); i != e; ++i) { | |||
1055 | // Update existing incoming values in PN for this | |||
1056 | // predecessor of BB. | |||
1057 | BasicBlock *PredBB = BBPreds[i]; | |||
1058 | Value *Selected = selectIncomingValueForBlock(OldVal, PredBB, | |||
1059 | IncomingValues); | |||
1060 | ||||
1061 | // And add a new incoming value for this predecessor for the | |||
1062 | // newly retargeted branch. | |||
1063 | PN->addIncoming(Selected, PredBB); | |||
1064 | } | |||
1065 | } | |||
1066 | ||||
1067 | replaceUndefValuesInPhi(PN, IncomingValues); | |||
1068 | } | |||
1069 | ||||
1070 | bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, | |||
1071 | DomTreeUpdater *DTU) { | |||
1072 | assert(BB != &BB->getParent()->getEntryBlock() &&(static_cast <bool> (BB != &BB->getParent()-> getEntryBlock() && "TryToSimplifyUncondBranchFromEmptyBlock called on entry block!" ) ? void (0) : __assert_fail ("BB != &BB->getParent()->getEntryBlock() && \"TryToSimplifyUncondBranchFromEmptyBlock called on entry block!\"" , "llvm/lib/Transforms/Utils/Local.cpp", 1073, __extension__ __PRETTY_FUNCTION__ )) | |||
1073 | "TryToSimplifyUncondBranchFromEmptyBlock called on entry block!")(static_cast <bool> (BB != &BB->getParent()-> getEntryBlock() && "TryToSimplifyUncondBranchFromEmptyBlock called on entry block!" ) ? void (0) : __assert_fail ("BB != &BB->getParent()->getEntryBlock() && \"TryToSimplifyUncondBranchFromEmptyBlock called on entry block!\"" , "llvm/lib/Transforms/Utils/Local.cpp", 1073, __extension__ __PRETTY_FUNCTION__ )); | |||
1074 | ||||
1075 | // We can't eliminate infinite loops. | |||
1076 | BasicBlock *Succ = cast<BranchInst>(BB->getTerminator())->getSuccessor(0); | |||
1077 | if (BB == Succ) return false; | |||
1078 | ||||
1079 | // Check to see if merging these blocks would cause conflicts for any of the | |||
1080 | // phi nodes in BB or Succ. If not, we can safely merge. | |||
1081 | if (!CanPropagatePredecessorsForPHIs(BB, Succ)) return false; | |||
1082 | ||||
1083 | // Check for cases where Succ has multiple predecessors and a PHI node in BB | |||
1084 | // has uses which will not disappear when the PHI nodes are merged. It is | |||
1085 | // possible to handle such cases, but difficult: it requires checking whether | |||
1086 | // BB dominates Succ, which is non-trivial to calculate in the case where | |||
1087 | // Succ has multiple predecessors. Also, it requires checking whether | |||
1088 | // constructing the necessary self-referential PHI node doesn't introduce any | |||
1089 | // conflicts; this isn't too difficult, but the previous code for doing this | |||
1090 | // was incorrect. | |||
1091 | // | |||
1092 | // Note that if this check finds a live use, BB dominates Succ, so BB is | |||
1093 | // something like a loop pre-header (or rarely, a part of an irreducible CFG); | |||
1094 | // folding the branch isn't profitable in that case anyway. | |||
1095 | if (!Succ->getSinglePredecessor()) { | |||
1096 | BasicBlock::iterator BBI = BB->begin(); | |||
1097 | while (isa<PHINode>(*BBI)) { | |||
1098 | for (Use &U : BBI->uses()) { | |||
1099 | if (PHINode* PN = dyn_cast<PHINode>(U.getUser())) { | |||
1100 | if (PN->getIncomingBlock(U) != BB) | |||
1101 | return false; | |||
1102 | } else { | |||
1103 | return false; | |||
1104 | } | |||
1105 | } | |||
1106 | ++BBI; | |||
1107 | } | |||
1108 | } | |||
1109 | ||||
1110 | // 'BB' and 'BB->Pred' are loop latches, bail out to presrve inner loop | |||
1111 | // metadata. | |||
1112 | // | |||
1113 | // FIXME: This is a stop-gap solution to preserve inner-loop metadata given | |||
1114 | // current status (that loop metadata is implemented as metadata attached to | |||
1115 | // the branch instruction in the loop latch block). To quote from review | |||
1116 | // comments, "the current representation of loop metadata (using a loop latch | |||
1117 | // terminator attachment) is known to be fundamentally broken. Loop latches | |||
1118 | // are not uniquely associated with loops (both in that a latch can be part of | |||
1119 | // multiple loops and a loop may have multiple latches). Loop headers are. The | |||
1120 | // solution to this problem is also known: Add support for basic block | |||
1121 | // metadata, and attach loop metadata to the loop header." | |||
1122 | // | |||
1123 | // Why bail out: | |||
1124 | // In this case, we expect 'BB' is the latch for outer-loop and 'BB->Pred' is | |||
1125 | // the latch for inner-loop (see reason below), so bail out to prerserve | |||
1126 | // inner-loop metadata rather than eliminating 'BB' and attaching its metadata | |||
1127 | // to this inner-loop. | |||
1128 | // - The reason we believe 'BB' and 'BB->Pred' have different inner-most | |||
1129 | // loops: assuming 'BB' and 'BB->Pred' are from the same inner-most loop L, | |||
1130 | // then 'BB' is the header and latch of 'L' and thereby 'L' must consist of | |||
1131 | // one self-looping basic block, which is contradictory with the assumption. | |||
1132 | // | |||
1133 | // To illustrate how inner-loop metadata is dropped: | |||
1134 | // | |||
1135 | // CFG Before | |||
1136 | // | |||
1137 | // BB is while.cond.exit, attached with loop metdata md2. | |||
1138 | // BB->Pred is for.body, attached with loop metadata md1. | |||
1139 | // | |||
1140 | // entry | |||
1141 | // | | |||
1142 | // v | |||
1143 | // ---> while.cond -------------> while.end | |||
1144 | // | | | |||
1145 | // | v | |||
1146 | // | while.body | |||
1147 | // | | | |||
1148 | // | v | |||
1149 | // | for.body <---- (md1) | |||
1150 | // | | |______| | |||
1151 | // | v | |||
1152 | // | while.cond.exit (md2) | |||
1153 | // | | | |||
1154 | // |_______| | |||
1155 | // | |||
1156 | // CFG After | |||
1157 | // | |||
1158 | // while.cond1 is the merge of while.cond.exit and while.cond above. | |||
1159 | // for.body is attached with md2, and md1 is dropped. | |||
1160 | // If LoopSimplify runs later (as a part of loop pass), it could create | |||
1161 | // dedicated exits for inner-loop (essentially adding `while.cond.exit` | |||
1162 | // back), but won't it won't see 'md1' nor restore it for the inner-loop. | |||
1163 | // | |||
1164 | // entry | |||
1165 | // | | |||
1166 | // v | |||
1167 | // ---> while.cond1 -------------> while.end | |||
1168 | // | | | |||
1169 | // | v | |||
1170 | // | while.body | |||
1171 | // | | | |||
1172 | // | v | |||
1173 | // | for.body <---- (md2) | |||
1174 | // |_______| |______| | |||
1175 | if (Instruction *TI = BB->getTerminator()) | |||
1176 | if (TI->hasMetadata(LLVMContext::MD_loop)) | |||
1177 | for (BasicBlock *Pred : predecessors(BB)) | |||
1178 | if (Instruction *PredTI = Pred->getTerminator()) | |||
1179 | if (PredTI->hasMetadata(LLVMContext::MD_loop)) | |||
1180 | return false; | |||
1181 | ||||
1182 | LLVM_DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("local")) { dbgs() << "Killing Trivial BB: \n" << *BB; } } while (false); | |||
1183 | ||||
1184 | SmallVector<DominatorTree::UpdateType, 32> Updates; | |||
1185 | if (DTU) { | |||
1186 | // To avoid processing the same predecessor more than once. | |||
1187 | SmallPtrSet<BasicBlock *, 8> SeenPreds; | |||
1188 | // All predecessors of BB will be moved to Succ. | |||
1189 | SmallPtrSet<BasicBlock *, 8> PredsOfSucc(pred_begin(Succ), pred_end(Succ)); | |||
1190 | Updates.reserve(Updates.size() + 2 * pred_size(BB) + 1); | |||
1191 | for (auto *PredOfBB : predecessors(BB)) | |||
1192 | // This predecessor of BB may already have Succ as a successor. | |||
1193 | if (!PredsOfSucc.contains(PredOfBB)) | |||
1194 | if (SeenPreds.insert(PredOfBB).second) | |||
1195 | Updates.push_back({DominatorTree::Insert, PredOfBB, Succ}); | |||
1196 | SeenPreds.clear(); | |||
1197 | for (auto *PredOfBB : predecessors(BB)) | |||
1198 | if (SeenPreds.insert(PredOfBB).second) | |||
1199 | Updates.push_back({DominatorTree::Delete, PredOfBB, BB}); | |||
1200 | Updates.push_back({DominatorTree::Delete, BB, Succ}); | |||
1201 | } | |||
1202 | ||||
1203 | if (isa<PHINode>(Succ->begin())) { | |||
1204 | // If there is more than one pred of succ, and there are PHI nodes in | |||
1205 | // the successor, then we need to add incoming edges for the PHI nodes | |||
1206 | // | |||
1207 | const PredBlockVector BBPreds(predecessors(BB)); | |||
1208 | ||||
1209 | // Loop over all of the PHI nodes in the successor of BB. | |||
1210 | for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { | |||
1211 | PHINode *PN = cast<PHINode>(I); | |||
1212 | ||||
1213 | redirectValuesFromPredecessorsToPhi(BB, BBPreds, PN); | |||
1214 | } | |||
1215 | } | |||
1216 | ||||
1217 | if (Succ->getSinglePredecessor()) { | |||
1218 | // BB is the only predecessor of Succ, so Succ will end up with exactly | |||
1219 | // the same predecessors BB had. | |||
1220 | ||||
1221 | // Copy over any phi, debug or lifetime instruction. | |||
1222 | BB->getTerminator()->eraseFromParent(); | |||
1223 | Succ->splice(Succ->getFirstNonPHI()->getIterator(), BB); | |||
1224 | } else { | |||
1225 | while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) { | |||
1226 | // We explicitly check for such uses in CanPropagatePredecessorsForPHIs. | |||
1227 | assert(PN->use_empty() && "There shouldn't be any uses here!")(static_cast <bool> (PN->use_empty() && "There shouldn't be any uses here!" ) ? void (0) : __assert_fail ("PN->use_empty() && \"There shouldn't be any uses here!\"" , "llvm/lib/Transforms/Utils/Local.cpp", 1227, __extension__ __PRETTY_FUNCTION__ )); | |||
1228 | PN->eraseFromParent(); | |||
1229 | } | |||
1230 | } | |||
1231 | ||||
1232 | // If the unconditional branch we replaced contains llvm.loop metadata, we | |||
1233 | // add the metadata to the branch instructions in the predecessors. | |||
1234 | unsigned LoopMDKind = BB->getContext().getMDKindID("llvm.loop"); | |||
1235 | Instruction *TI = BB->getTerminator(); | |||
1236 | if (TI) | |||
1237 | if (MDNode *LoopMD = TI->getMetadata(LoopMDKind)) | |||
1238 | for (BasicBlock *Pred : predecessors(BB)) | |||
1239 | Pred->getTerminator()->setMetadata(LoopMDKind, LoopMD); | |||
1240 | ||||
1241 | // Everything that jumped to BB now goes to Succ. | |||
1242 | BB->replaceAllUsesWith(Succ); | |||
1243 | if (!Succ->hasName()) Succ->takeName(BB); | |||
1244 | ||||
1245 | // Clear the successor list of BB to match updates applying to DTU later. | |||
1246 | if (BB->getTerminator()) | |||
1247 | BB->back().eraseFromParent(); | |||
1248 | new UnreachableInst(BB->getContext(), BB); | |||
1249 | assert(succ_empty(BB) && "The successor list of BB isn't empty before "(static_cast <bool> (succ_empty(BB) && "The successor list of BB isn't empty before " "applying corresponding DTU updates.") ? void (0) : __assert_fail ("succ_empty(BB) && \"The successor list of BB isn't empty before \" \"applying corresponding DTU updates.\"" , "llvm/lib/Transforms/Utils/Local.cpp", 1250, __extension__ __PRETTY_FUNCTION__ )) | |||
1250 | "applying corresponding DTU updates.")(static_cast <bool> (succ_empty(BB) && "The successor list of BB isn't empty before " "applying corresponding DTU updates.") ? void (0) : __assert_fail ("succ_empty(BB) && \"The successor list of BB isn't empty before \" \"applying corresponding DTU updates.\"" , "llvm/lib/Transforms/Utils/Local.cpp", 1250, __extension__ __PRETTY_FUNCTION__ )); | |||
1251 | ||||
1252 | if (DTU) | |||
1253 | DTU->applyUpdates(Updates); | |||
1254 | ||||
1255 | DeleteDeadBlock(BB, DTU); | |||
1256 | ||||
1257 | return true; | |||
1258 | } | |||
1259 | ||||
1260 | static bool EliminateDuplicatePHINodesNaiveImpl(BasicBlock *BB) { | |||
1261 | // This implementation doesn't currently consider undef operands | |||
1262 | // specially. Theoretically, two phis which are identical except for | |||
1263 | // one having an undef where the other doesn't could be collapsed. | |||
1264 | ||||
1265 | bool Changed = false; | |||
1266 | ||||
1267 | // Examine each PHI. | |||
1268 | // Note that increment of I must *NOT* be in the iteration_expression, since | |||
1269 | // we don't want to immediately advance when we restart from the beginning. | |||
1270 | for (auto I = BB->begin(); PHINode *PN = dyn_cast<PHINode>(I);) { | |||
1271 | ++I; | |||
1272 | // Is there an identical PHI node in this basic block? | |||
1273 | // Note that we only look in the upper square's triangle, | |||
1274 | // we already checked that the lower triangle PHI's aren't identical. | |||
1275 | for (auto J = I; PHINode *DuplicatePN = dyn_cast<PHINode>(J); ++J) { | |||
1276 | if (!DuplicatePN->isIdenticalToWhenDefined(PN)) | |||
1277 | continue; | |||
1278 | // A duplicate. Replace this PHI with the base PHI. | |||
1279 | ++NumPHICSEs; | |||
1280 | DuplicatePN->replaceAllUsesWith(PN); | |||
1281 | DuplicatePN->eraseFromParent(); | |||
1282 | Changed = true; | |||
1283 | ||||
1284 | // The RAUW can change PHIs that we already visited. | |||
1285 | I = BB->begin(); | |||
1286 | break; // Start over from the beginning. | |||
1287 | } | |||
1288 | } | |||
1289 | return Changed; | |||
1290 | } | |||
1291 | ||||
1292 | static bool EliminateDuplicatePHINodesSetBasedImpl(BasicBlock *BB) { | |||
1293 | // This implementation doesn't currently consider undef operands | |||
1294 | // specially. Theoretically, two phis which are identical except for | |||
1295 | // one having an undef where the other doesn't could be collapsed. | |||
1296 | ||||
1297 | struct PHIDenseMapInfo { | |||
1298 | static PHINode *getEmptyKey() { | |||
1299 | return DenseMapInfo<PHINode *>::getEmptyKey(); | |||
1300 | } | |||
1301 | ||||
1302 | static PHINode *getTombstoneKey() { | |||
1303 | return DenseMapInfo<PHINode *>::getTombstoneKey(); | |||
1304 | } | |||
1305 | ||||
1306 | static bool isSentinel(PHINode *PN) { | |||
1307 | return PN == getEmptyKey() || PN == getTombstoneKey(); | |||
1308 | } | |||
1309 | ||||
1310 | // WARNING: this logic must be kept in sync with | |||
1311 | // Instruction::isIdenticalToWhenDefined()! | |||
1312 | static unsigned getHashValueImpl(PHINode *PN) { | |||
1313 | // Compute a hash value on the operands. Instcombine will likely have | |||
1314 | // sorted them, which helps expose duplicates, but we have to check all | |||
1315 | // the operands to be safe in case instcombine hasn't run. | |||
1316 | return static_cast<unsigned>(hash_combine( | |||
1317 | hash_combine_range(PN->value_op_begin(), PN->value_op_end()), | |||
1318 | hash_combine_range(PN->block_begin(), PN->block_end()))); | |||
1319 | } | |||
1320 | ||||
1321 | static unsigned getHashValue(PHINode *PN) { | |||
1322 | #ifndef NDEBUG | |||
1323 | // If -phicse-debug-hash was specified, return a constant -- this | |||
1324 | // will force all hashing to collide, so we'll exhaustively search | |||
1325 | // the table for a match, and the assertion in isEqual will fire if | |||
1326 | // there's a bug causing equal keys to hash differently. | |||
1327 | if (PHICSEDebugHash) | |||
1328 | return 0; | |||
1329 | #endif | |||
1330 | return getHashValueImpl(PN); | |||
1331 | } | |||
1332 | ||||
1333 | static bool isEqualImpl(PHINode *LHS, PHINode *RHS) { | |||
1334 | if (isSentinel(LHS) || isSentinel(RHS)) | |||
1335 | return LHS == RHS; | |||
1336 | return LHS->isIdenticalTo(RHS); | |||
1337 | } | |||
1338 | ||||
1339 | static bool isEqual(PHINode *LHS, PHINode *RHS) { | |||
1340 | // These comparisons are nontrivial, so assert that equality implies | |||
1341 | // hash equality (DenseMap demands this as an invariant). | |||
1342 | bool Result = isEqualImpl(LHS, RHS); | |||
1343 | assert(!Result || (isSentinel(LHS) && LHS == RHS) ||(static_cast <bool> (!Result || (isSentinel(LHS) && LHS == RHS) || getHashValueImpl(LHS) == getHashValueImpl(RHS )) ? void (0) : __assert_fail ("!Result || (isSentinel(LHS) && LHS == RHS) || getHashValueImpl(LHS) == getHashValueImpl(RHS)" , "llvm/lib/Transforms/Utils/Local.cpp", 1344, __extension__ __PRETTY_FUNCTION__ )) | |||
1344 | getHashValueImpl(LHS) == getHashValueImpl(RHS))(static_cast <bool> (!Result || (isSentinel(LHS) && LHS == RHS) || getHashValueImpl(LHS) == getHashValueImpl(RHS )) ? void (0) : __assert_fail ("!Result || (isSentinel(LHS) && LHS == RHS) || getHashValueImpl(LHS) == getHashValueImpl(RHS)" , "llvm/lib/Transforms/Utils/Local.cpp", 1344, __extension__ __PRETTY_FUNCTION__ )); | |||
1345 | return Result; | |||
1346 | } | |||
1347 | }; | |||
1348 | ||||
1349 | // Set of unique PHINodes. | |||
1350 | DenseSet<PHINode *, PHIDenseMapInfo> PHISet; | |||
1351 | PHISet.reserve(4 * PHICSENumPHISmallSize); | |||
1352 | ||||
1353 | // Examine each PHI. | |||
1354 | bool Changed = false; | |||
1355 | for (auto I = BB->begin(); PHINode *PN = dyn_cast<PHINode>(I++);) { | |||
1356 | auto Inserted = PHISet.insert(PN); | |||
1357 | if (!Inserted.second) { | |||
1358 | // A duplicate. Replace this PHI with its duplicate. | |||
1359 | ++NumPHICSEs; | |||
1360 | PN->replaceAllUsesWith(*Inserted.first); | |||
1361 | PN->eraseFromParent(); | |||
1362 | Changed = true; | |||
1363 | ||||
1364 | // The RAUW can change PHIs that we already visited. Start over from the | |||
1365 | // beginning. | |||
1366 | PHISet.clear(); | |||
1367 | I = BB->begin(); | |||
1368 | } | |||
1369 | } | |||
1370 | ||||
1371 | return Changed; | |||
1372 | } | |||
1373 | ||||
1374 | bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) { | |||
1375 | if ( | |||
1376 | #ifndef NDEBUG | |||
1377 | !PHICSEDebugHash && | |||
1378 | #endif | |||
1379 | hasNItemsOrLess(BB->phis(), PHICSENumPHISmallSize)) | |||
1380 | return EliminateDuplicatePHINodesNaiveImpl(BB); | |||
1381 | return EliminateDuplicatePHINodesSetBasedImpl(BB); | |||
1382 | } | |||
1383 | ||||
1384 | /// If the specified pointer points to an object that we control, try to modify | |||
1385 | /// the object's alignment to PrefAlign. Returns a minimum known alignment of | |||
1386 | /// the value after the operation, which may be lower than PrefAlign. | |||
1387 | /// | |||
1388 | /// Increating value alignment isn't often possible though. If alignment is | |||
1389 | /// important, a more reliable approach is to simply align all global variables | |||
1390 | /// and allocation instructions to their preferred alignment from the beginning. | |||
1391 | static Align tryEnforceAlignment(Value *V, Align PrefAlign, | |||
1392 | const DataLayout &DL) { | |||
1393 | V = V->stripPointerCasts(); | |||
1394 | ||||
1395 | if (AllocaInst *AI = dyn_cast<AllocaInst>(V)) { | |||
1396 | // TODO: Ideally, this function would not be called if PrefAlign is smaller | |||
1397 | // than the current alignment, as the known bits calculation should have | |||
1398 | // already taken it into account. However, this is not always the case, | |||
1399 | // as computeKnownBits() has a depth limit, while stripPointerCasts() | |||
1400 | // doesn't. | |||
1401 | Align CurrentAlign = AI->getAlign(); | |||
1402 | if (PrefAlign <= CurrentAlign) | |||
1403 | return CurrentAlign; | |||
1404 | ||||
1405 | // If the preferred alignment is greater than the natural stack alignment | |||
1406 | // then don't round up. This avoids dynamic stack realignment. | |||
1407 | if (DL.exceedsNaturalStackAlignment(PrefAlign)) | |||
1408 | return CurrentAlign; | |||
1409 | AI->setAlignment(PrefAlign); | |||
1410 | return PrefAlign; | |||
1411 | } | |||
1412 | ||||
1413 | if (auto *GO = dyn_cast<GlobalObject>(V)) { | |||
1414 | // TODO: as above, this shouldn't be necessary. | |||
1415 | Align CurrentAlign = GO->getPointerAlignment(DL); | |||
1416 | if (PrefAlign <= CurrentAlign) | |||
1417 | return CurrentAlign; | |||
1418 | ||||
1419 | // If there is a large requested alignment and we can, bump up the alignment | |||
1420 | // of the global. If the memory we set aside for the global may not be the | |||
1421 | // memory used by the final program then it is impossible for us to reliably | |||
1422 | // enforce the preferred alignment. | |||
1423 | if (!GO->canIncreaseAlignment()) | |||
1424 | return CurrentAlign; | |||
1425 | ||||
1426 | if (GO->isThreadLocal()) { | |||
1427 | unsigned MaxTLSAlign = GO->getParent()->getMaxTLSAlignment() / CHAR_BIT8; | |||
1428 | if (MaxTLSAlign && PrefAlign > Align(MaxTLSAlign)) | |||
1429 | PrefAlign = Align(MaxTLSAlign); | |||
1430 | } | |||
1431 | ||||
1432 | GO->setAlignment(PrefAlign); | |||
1433 | return PrefAlign; | |||
1434 | } | |||
1435 | ||||
1436 | return Align(1); | |||
1437 | } | |||
1438 | ||||
1439 | Align llvm::getOrEnforceKnownAlignment(Value *V, MaybeAlign PrefAlign, | |||
1440 | const DataLayout &DL, | |||
1441 | const Instruction *CxtI, | |||
1442 | AssumptionCache *AC, | |||
1443 | const DominatorTree *DT) { | |||
1444 | assert(V->getType()->isPointerTy() &&(static_cast <bool> (V->getType()->isPointerTy() && "getOrEnforceKnownAlignment expects a pointer!") ? void (0) : __assert_fail ("V->getType()->isPointerTy() && \"getOrEnforceKnownAlignment expects a pointer!\"" , "llvm/lib/Transforms/Utils/Local.cpp", 1445, __extension__ __PRETTY_FUNCTION__ )) | |||
1445 | "getOrEnforceKnownAlignment expects a pointer!")(static_cast <bool> (V->getType()->isPointerTy() && "getOrEnforceKnownAlignment expects a pointer!") ? void (0) : __assert_fail ("V->getType()->isPointerTy() && \"getOrEnforceKnownAlignment expects a pointer!\"" , "llvm/lib/Transforms/Utils/Local.cpp", 1445, __extension__ __PRETTY_FUNCTION__ )); | |||
1446 | ||||
1447 | KnownBits Known = computeKnownBits(V, DL, 0, AC, CxtI, DT); | |||
1448 | unsigned TrailZ = Known.countMinTrailingZeros(); | |||
1449 | ||||
1450 | // Avoid trouble with ridiculously large TrailZ values, such as | |||
1451 | // those computed from a null pointer. | |||
1452 | // LLVM doesn't support alignments larger than (1 << MaxAlignmentExponent). | |||
1453 | TrailZ = std::min(TrailZ, +Value::MaxAlignmentExponent); | |||
1454 | ||||
1455 | Align Alignment = Align(1ull << std::min(Known.getBitWidth() - 1, TrailZ)); | |||
1456 | ||||
1457 | if (PrefAlign && *PrefAlign > Alignment) | |||
1458 | Alignment = std::max(Alignment, tryEnforceAlignment(V, *PrefAlign, DL)); | |||
1459 | ||||
1460 | // We don't need to make any adjustment. | |||
1461 | return Alignment; | |||
1462 | } | |||
1463 | ||||
1464 | ///===---------------------------------------------------------------------===// | |||
1465 | /// Dbg Intrinsic utilities | |||
1466 | /// | |||
1467 | ||||
1468 | /// See if there is a dbg.value intrinsic for DIVar for the PHI node. | |||
1469 | static bool PhiHasDebugValue(DILocalVariable *DIVar, | |||
1470 | DIExpression *DIExpr, | |||
1471 | PHINode *APN) { | |||
1472 | // Since we can't guarantee that the original dbg.declare intrinsic | |||
1473 | // is removed by LowerDbgDeclare(), we need to make sure that we are | |||
1474 | // not inserting the same dbg.value intrinsic over and over. | |||
1475 | SmallVector<DbgValueInst *, 1> DbgValues; | |||
1476 | findDbgValues(DbgValues, APN); | |||
1477 | for (auto *DVI : DbgValues) { | |||
1478 | assert(is_contained(DVI->getValues(), APN))(static_cast <bool> (is_contained(DVI->getValues(), APN )) ? void (0) : __assert_fail ("is_contained(DVI->getValues(), APN)" , "llvm/lib/Transforms/Utils/Local.cpp", 1478, __extension__ __PRETTY_FUNCTION__ )); | |||
1479 | if ((DVI->getVariable() == DIVar) && (DVI->getExpression() == DIExpr)) | |||
1480 | return true; | |||
1481 | } | |||
1482 | return false; | |||
1483 | } | |||
1484 | ||||
1485 | /// Check if the alloc size of \p ValTy is large enough to cover the variable | |||
1486 | /// (or fragment of the variable) described by \p DII. | |||
1487 | /// | |||
1488 | /// This is primarily intended as a helper for the different | |||
1489 | /// ConvertDebugDeclareToDebugValue functions. The dbg.declare/dbg.addr that is | |||
1490 | /// converted describes an alloca'd variable, so we need to use the | |||
1491 | /// alloc size of the value when doing the comparison. E.g. an i1 value will be | |||
1492 | /// identified as covering an n-bit fragment, if the store size of i1 is at | |||
1493 | /// least n bits. | |||
1494 | static bool valueCoversEntireFragment(Type *ValTy, DbgVariableIntrinsic *DII) { | |||
1495 | const DataLayout &DL = DII->getModule()->getDataLayout(); | |||
1496 | TypeSize ValueSize = DL.getTypeAllocSizeInBits(ValTy); | |||
1497 | if (std::optional<uint64_t> FragmentSize = DII->getFragmentSizeInBits()) { | |||
1498 | assert(!ValueSize.isScalable() &&(static_cast <bool> (!ValueSize.isScalable() && "Fragments don't work on scalable types.") ? void (0) : __assert_fail ("!ValueSize.isScalable() && \"Fragments don't work on scalable types.\"" , "llvm/lib/Transforms/Utils/Local.cpp", 1499, __extension__ __PRETTY_FUNCTION__ )) | |||
1499 | "Fragments don't work on scalable types.")(static_cast <bool> (!ValueSize.isScalable() && "Fragments don't work on scalable types.") ? void (0) : __assert_fail ("!ValueSize.isScalable() && \"Fragments don't work on scalable types.\"" , "llvm/lib/Transforms/Utils/Local.cpp", 1499, __extension__ __PRETTY_FUNCTION__ )); | |||
1500 | return ValueSize.getFixedValue() >= *FragmentSize; | |||
1501 | } | |||
1502 | // We can't always calculate the size of the DI variable (e.g. if it is a | |||
1503 | // VLA). Try to use the size of the alloca that the dbg intrinsic describes | |||
1504 | // intead. | |||
1505 | if (DII->isAddressOfVariable()) { | |||
1506 | // DII should have exactly 1 location when it is an address. | |||
1507 | assert(DII->getNumVariableLocationOps() == 1 &&(static_cast <bool> (DII->getNumVariableLocationOps( ) == 1 && "address of variable must have exactly 1 location operand." ) ? void (0) : __assert_fail ("DII->getNumVariableLocationOps() == 1 && \"address of variable must have exactly 1 location operand.\"" , "llvm/lib/Transforms/Utils/Local.cpp", 1508, __extension__ __PRETTY_FUNCTION__ )) | |||
1508 | "address of variable must have exactly 1 location operand.")(static_cast <bool> (DII->getNumVariableLocationOps( ) == 1 && "address of variable must have exactly 1 location operand." ) ? void (0) : __assert_fail ("DII->getNumVariableLocationOps() == 1 && \"address of variable must have exactly 1 location operand.\"" , "llvm/lib/Transforms/Utils/Local.cpp", 1508, __extension__ __PRETTY_FUNCTION__ )); | |||
1509 | if (auto *AI = | |||
1510 | dyn_cast_or_null<AllocaInst>(DII->getVariableLocationOp(0))) { | |||
1511 | if (std::optional<TypeSize> FragmentSize = | |||
1512 | AI->getAllocationSizeInBits(DL)) { | |||
1513 | return TypeSize::isKnownGE(ValueSize, *FragmentSize); | |||
1514 | } | |||
1515 | } | |||
1516 | } | |||
1517 | // Could not determine size of variable. Conservatively return false. | |||
1518 | return false; | |||
1519 | } | |||
1520 | ||||
1521 | /// Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value | |||
1522 | /// that has an associated llvm.dbg.declare or llvm.dbg.addr intrinsic. | |||
1523 | void llvm::ConvertDebugDeclareToDebugValue(DbgVariableIntrinsic *DII, | |||
1524 | StoreInst *SI, DIBuilder &Builder) { | |||
1525 | assert(DII->isAddressOfVariable() || isa<DbgAssignIntrinsic>(DII))(static_cast <bool> (DII->isAddressOfVariable() || isa <DbgAssignIntrinsic>(DII)) ? void (0) : __assert_fail ( "DII->isAddressOfVariable() || isa<DbgAssignIntrinsic>(DII)" , "llvm/lib/Transforms/Utils/Local.cpp", 1525, __extension__ __PRETTY_FUNCTION__ )); | |||
1526 | auto *DIVar = DII->getVariable(); | |||
1527 | assert(DIVar && "Missing variable")(static_cast <bool> (DIVar && "Missing variable" ) ? void (0) : __assert_fail ("DIVar && \"Missing variable\"" , "llvm/lib/Transforms/Utils/Local.cpp", 1527, __extension__ __PRETTY_FUNCTION__ )); | |||
1528 | auto *DIExpr = DII->getExpression(); | |||
1529 | Value *DV = SI->getValueOperand(); | |||
1530 | ||||
1531 | DebugLoc NewLoc = getDebugValueLoc(DII); | |||
1532 | ||||
1533 | // If the alloca describes the variable itself, i.e. the expression in the | |||
1534 | // dbg.declare doesn't start with a dereference, we can perform the | |||
1535 | // conversion if the value covers the entire fragment of DII. | |||
1536 | // If the alloca describes the *address* of DIVar, i.e. DIExpr is | |||
1537 | // *just* a DW_OP_deref, we use DV as is for the dbg.value. | |||
1538 | // We conservatively ignore other dereferences, because the following two are | |||
1539 | // not equivalent: | |||
1540 | // dbg.declare(alloca, ..., !Expr(deref, plus_uconstant, 2)) | |||
1541 | // dbg.value(DV, ..., !Expr(deref, plus_uconstant, 2)) | |||
1542 | // The former is adding 2 to the address of the variable, whereas the latter | |||
1543 | // is adding 2 to the value of the variable. As such, we insist on just a | |||
1544 | // deref expression. | |||
1545 | bool CanConvert = | |||
1546 | DIExpr->isDeref() || (!DIExpr->startsWithDeref() && | |||
1547 | valueCoversEntireFragment(DV->getType(), DII)); | |||
1548 | if (CanConvert) { | |||
1549 | Builder.insertDbgValueIntrinsic(DV, DIVar, DIExpr, NewLoc, SI); | |||
1550 | return; | |||
1551 | } | |||
1552 | ||||
1553 | // FIXME: If storing to a part of the variable described by the dbg.declare, | |||
1554 | // then we want to insert a dbg.value for the corresponding fragment. | |||
1555 | LLVM_DEBUG(dbgs() << "Failed to convert dbg.declare to dbg.value: " << *DIIdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("local")) { dbgs() << "Failed to convert dbg.declare to dbg.value: " << *DII << '\n'; } } while (false) | |||
1556 | << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("local")) { dbgs() << "Failed to convert dbg.declare to dbg.value: " << *DII << '\n'; } } while (false); | |||
1557 | // For now, when there is a store to parts of the variable (but we do not | |||
1558 | // know which part) we insert an dbg.value intrinsic to indicate that we | |||
1559 | // know nothing about the variable's content. | |||
1560 | DV = UndefValue::get(DV->getType()); | |||
1561 | Builder.insertDbgValueIntrinsic(DV, DIVar, DIExpr, NewLoc, SI); | |||
1562 | } | |||
1563 | ||||
1564 | /// Inserts a llvm.dbg.value intrinsic before a load of an alloca'd value | |||
1565 | /// that has an associated llvm.dbg.declare or llvm.dbg.addr intrinsic. | |||
1566 | void llvm::ConvertDebugDeclareToDebugValue(DbgVariableIntrinsic *DII, | |||
1567 | LoadInst *LI, DIBuilder &Builder) { | |||
1568 | auto *DIVar = DII->getVariable(); | |||
1569 | auto *DIExpr = DII->getExpression(); | |||
1570 | assert(DIVar && "Missing variable")(static_cast <bool> (DIVar && "Missing variable" ) ? void (0) : __assert_fail ("DIVar && \"Missing variable\"" , "llvm/lib/Transforms/Utils/Local.cpp", 1570, __extension__ __PRETTY_FUNCTION__ )); | |||
1571 | ||||
1572 | if (!valueCoversEntireFragment(LI->getType(), DII)) { | |||
1573 | // FIXME: If only referring to a part of the variable described by the | |||
1574 | // dbg.declare, then we want to insert a dbg.value for the corresponding | |||
1575 | // fragment. | |||
1576 | LLVM_DEBUG(dbgs() << "Failed to convert dbg.declare to dbg.value: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("local")) { dbgs() << "Failed to convert dbg.declare to dbg.value: " << *DII << '\n'; } } while (false) | |||
1577 | << *DII << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("local")) { dbgs() << "Failed to convert dbg.declare to dbg.value: " << *DII << '\n'; } } while (false); | |||
1578 | return; | |||
1579 | } | |||
1580 | ||||
1581 | DebugLoc NewLoc = getDebugValueLoc(DII); | |||
1582 | ||||
1583 | // We are now tracking the loaded value instead of the address. In the | |||
1584 | // future if multi-location support is added to the IR, it might be | |||
1585 | // preferable to keep tracking both the loaded value and the original | |||
1586 | // address in case the alloca can not be elided. | |||
1587 | Instruction *DbgValue = Builder.insertDbgValueIntrinsic( | |||
1588 | LI, DIVar, DIExpr, NewLoc, (Instruction *)nullptr); | |||
1589 | DbgValue->insertAfter(LI); | |||
1590 | } | |||
1591 | ||||
1592 | /// Inserts a llvm.dbg.value intrinsic after a phi that has an associated | |||
1593 | /// llvm.dbg.declare or llvm.dbg.addr intrinsic. | |||
1594 | void llvm::ConvertDebugDeclareToDebugValue(DbgVariableIntrinsic *DII, | |||
1595 | PHINode *APN, DIBuilder &Builder) { | |||
1596 | auto *DIVar = DII->getVariable(); | |||
1597 | auto *DIExpr = DII->getExpression(); | |||
1598 | assert(DIVar && "Missing variable")(static_cast <bool> (DIVar && "Missing variable" ) ? void (0) : __assert_fail ("DIVar && \"Missing variable\"" , "llvm/lib/Transforms/Utils/Local.cpp", 1598, __extension__ __PRETTY_FUNCTION__ )); | |||
1599 | ||||
1600 | if (PhiHasDebugValue(DIVar, DIExpr, APN)) | |||
1601 | return; | |||
1602 | ||||
1603 | if (!valueCoversEntireFragment(APN->getType(), DII)) { | |||
1604 | // FIXME: If only referring to a part of the variable described by the | |||
1605 | // dbg.declare, then we want to insert a dbg.value for the corresponding | |||
1606 | // fragment. | |||
1607 | LLVM_DEBUG(dbgs() << "Failed to convert dbg.declare to dbg.value: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("local")) { dbgs() << "Failed to convert dbg.declare to dbg.value: " << *DII << '\n'; } } while (false) | |||
1608 | << *DII << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("local")) { dbgs() << "Failed to convert dbg.declare to dbg.value: " << *DII << '\n'; } } while (false); | |||
1609 | return; | |||
1610 | } | |||
1611 | ||||
1612 | BasicBlock *BB = APN->getParent(); | |||
1613 | auto InsertionPt = BB->getFirstInsertionPt(); | |||
1614 | ||||
1615 | DebugLoc NewLoc = getDebugValueLoc(DII); | |||
1616 | ||||
1617 | // The block may be a catchswitch block, which does not have a valid | |||
1618 | // insertion point. | |||
1619 | // FIXME: Insert dbg.value markers in the successors when appropriate. | |||
1620 | if (InsertionPt != BB->end()) | |||
1621 | Builder.insertDbgValueIntrinsic(APN, DIVar, DIExpr, NewLoc, &*InsertionPt); | |||
1622 | } | |||
1623 | ||||
1624 | /// Determine whether this alloca is either a VLA or an array. | |||
1625 | static bool isArray(AllocaInst *AI) { | |||
1626 | return AI->isArrayAllocation() || | |||
1627 | (AI->getAllocatedType() && AI->getAllocatedType()->isArrayTy()); | |||
1628 | } | |||
1629 | ||||
1630 | /// Determine whether this alloca is a structure. | |||
1631 | static bool isStructure(AllocaInst *AI) { | |||
1632 | return AI->getAllocatedType() && AI->getAllocatedType()->isStructTy(); | |||
1633 | } | |||
1634 | ||||
1635 | /// LowerDbgDeclare - Lowers llvm.dbg.declare intrinsics into appropriate set | |||
1636 | /// of llvm.dbg.value intrinsics. | |||
1637 | bool llvm::LowerDbgDeclare(Function &F) { | |||
1638 | bool Changed = false; | |||
1639 | DIBuilder DIB(*F.getParent(), /*AllowUnresolved*/ false); | |||
1640 | SmallVector<DbgDeclareInst *, 4> Dbgs; | |||
1641 | for (auto &FI : F) | |||
1642 | for (Instruction &BI : FI) | |||
1643 | if (auto DDI = dyn_cast<DbgDeclareInst>(&BI)) | |||
1644 | Dbgs.push_back(DDI); | |||
1645 | ||||
1646 | if (Dbgs.empty()) | |||
1647 | return Changed; | |||
1648 | ||||
1649 | for (auto &I : Dbgs) { | |||
1650 | DbgDeclareInst *DDI = I; | |||
1651 | AllocaInst *AI = dyn_cast_or_null<AllocaInst>(DDI->getAddress()); | |||
1652 | // If this is an alloca for a scalar variable, insert a dbg.value | |||
1653 | // at each load and store to the alloca and erase the dbg.declare. | |||
1654 | // The dbg.values allow tracking a variable even if it is not | |||
1655 | // stored on the stack, while the dbg.declare can only describe | |||
1656 | // the stack slot (and at a lexical-scope granularity). Later | |||
1657 | // passes will attempt to elide the stack slot. | |||
1658 | if (!AI || isArray(AI) || isStructure(AI)) | |||
1659 | continue; | |||
1660 | ||||
1661 | // A volatile load/store means that the alloca can't be elided anyway. | |||
1662 | if (llvm::any_of(AI->users(), [](User *U) -> bool { | |||
1663 | if (LoadInst *LI = dyn_cast<LoadInst>(U)) | |||
1664 | return LI->isVolatile(); | |||
1665 | if (StoreInst *SI = dyn_cast<StoreInst>(U)) | |||
1666 | return SI->isVolatile(); | |||
1667 | return false; | |||
1668 | })) | |||
1669 | continue; | |||
1670 | ||||
1671 | SmallVector<const Value *, 8> WorkList; | |||
1672 | WorkList.push_back(AI); | |||
1673 | while (!WorkList.empty()) { | |||
1674 | const Value *V = WorkList.pop_back_val(); | |||
1675 | for (const auto &AIUse : V->uses()) { | |||
1676 | User *U = AIUse.getUser(); | |||
1677 | if (StoreInst *SI = dyn_cast<StoreInst>(U)) { | |||
1678 | if (AIUse.getOperandNo() == 1) | |||
1679 | ConvertDebugDeclareToDebugValue(DDI, SI, DIB); | |||
1680 | } else if (LoadInst *LI = dyn_cast<LoadInst>(U)) { | |||
1681 | ConvertDebugDeclareToDebugValue(DDI, LI, DIB); | |||
1682 | } else if (CallInst *CI = dyn_cast<CallInst>(U)) { | |||
1683 | // This is a call by-value or some other instruction that takes a | |||
1684 | // pointer to the variable. Insert a *value* intrinsic that describes | |||
1685 | // the variable by dereferencing the alloca. | |||
1686 | if (!CI->isLifetimeStartOrEnd()) { | |||
1687 | DebugLoc NewLoc = getDebugValueLoc(DDI); | |||
1688 | auto *DerefExpr = | |||
1689 | DIExpression::append(DDI->getExpression(), dwarf::DW_OP_deref); | |||
1690 | DIB.insertDbgValueIntrinsic(AI, DDI->getVariable(), DerefExpr, | |||
1691 | NewLoc, CI); | |||
1692 | } | |||
1693 | } else if (BitCastInst *BI = dyn_cast<BitCastInst>(U)) { | |||
1694 | if (BI->getType()->isPointerTy()) | |||
1695 | WorkList.push_back(BI); | |||
1696 | } | |||
1697 | } | |||
1698 | } | |||
1699 | DDI->eraseFromParent(); | |||
1700 | Changed = true; | |||
1701 | } | |||
1702 | ||||
1703 | if (Changed) | |||
1704 | for (BasicBlock &BB : F) | |||
1705 | RemoveRedundantDbgInstrs(&BB); | |||
1706 | ||||
1707 | return Changed; | |||
1708 | } | |||
1709 | ||||
1710 | /// Propagate dbg.value intrinsics through the newly inserted PHIs. | |||
1711 | void llvm::insertDebugValuesForPHIs(BasicBlock *BB, | |||
1712 | SmallVectorImpl<PHINode *> &InsertedPHIs) { | |||
1713 | assert(BB && "No BasicBlock to clone dbg.value(s) from.")(static_cast <bool> (BB && "No BasicBlock to clone dbg.value(s) from." ) ? void (0) : __assert_fail ("BB && \"No BasicBlock to clone dbg.value(s) from.\"" , "llvm/lib/Transforms/Utils/Local.cpp", 1713, __extension__ __PRETTY_FUNCTION__ )); | |||
1714 | if (InsertedPHIs.size() == 0) | |||
1715 | return; | |||
1716 | ||||
1717 | // Map existing PHI nodes to their dbg.values. | |||
1718 | ValueToValueMapTy DbgValueMap; | |||
1719 | for (auto &I : *BB) { | |||
1720 | if (auto DbgII = dyn_cast<DbgVariableIntrinsic>(&I)) { | |||
1721 | for (Value *V : DbgII->location_ops()) | |||
1722 | if (auto *Loc = dyn_cast_or_null<PHINode>(V)) | |||
1723 | DbgValueMap.insert({Loc, DbgII}); | |||
1724 | } | |||
1725 | } | |||
1726 | if (DbgValueMap.size() == 0) | |||
1727 | return; | |||
1728 | ||||
1729 | // Map a pair of the destination BB and old dbg.value to the new dbg.value, | |||
1730 | // so that if a dbg.value is being rewritten to use more than one of the | |||
1731 | // inserted PHIs in the same destination BB, we can update the same dbg.value | |||
1732 | // with all the new PHIs instead of creating one copy for each. | |||
1733 | MapVector<std::pair<BasicBlock *, DbgVariableIntrinsic *>, | |||
1734 | DbgVariableIntrinsic *> | |||
1735 | NewDbgValueMap; | |||
1736 | // Then iterate through the new PHIs and look to see if they use one of the | |||
1737 | // previously mapped PHIs. If so, create a new dbg.value intrinsic that will | |||
1738 | // propagate the info through the new PHI. If we use more than one new PHI in | |||
1739 | // a single destination BB with the same old dbg.value, merge the updates so | |||
1740 | // that we get a single new dbg.value with all the new PHIs. | |||
1741 | for (auto *PHI : InsertedPHIs) { | |||
1742 | BasicBlock *Parent = PHI->getParent(); | |||
1743 | // Avoid inserting an intrinsic into an EH block. | |||
1744 | if (Parent->getFirstNonPHI()->isEHPad()) | |||
1745 | continue; | |||
1746 | for (auto *VI : PHI->operand_values()) { | |||
1747 | auto V = DbgValueMap.find(VI); | |||
1748 | if (V != DbgValueMap.end()) { | |||
1749 | auto *DbgII = cast<DbgVariableIntrinsic>(V->second); | |||
1750 | auto NewDI = NewDbgValueMap.find({Parent, DbgII}); | |||
1751 | if (NewDI == NewDbgValueMap.end()) { | |||
1752 | auto *NewDbgII = cast<DbgVariableIntrinsic>(DbgII->clone()); | |||
1753 | NewDI = NewDbgValueMap.insert({{Parent, DbgII}, NewDbgII}).first; | |||
1754 | } | |||
1755 | DbgVariableIntrinsic *NewDbgII = NewDI->second; | |||
1756 | // If PHI contains VI as an operand more than once, we may | |||
1757 | // replaced it in NewDbgII; confirm that it is present. | |||
1758 | if (is_contained(NewDbgII->location_ops(), VI)) | |||
1759 | NewDbgII->replaceVariableLocationOp(VI, PHI); | |||
1760 | } | |||
1761 | } | |||
1762 | } | |||
1763 | // Insert thew new dbg.values into their destination blocks. | |||
1764 | for (auto DI : NewDbgValueMap) { | |||
1765 | BasicBlock *Parent = DI.first.first; | |||
1766 | auto *NewDbgII = DI.second; | |||
1767 | auto InsertionPt = Parent->getFirstInsertionPt(); | |||
1768 | assert(InsertionPt != Parent->end() && "Ill-formed basic block")(static_cast <bool> (InsertionPt != Parent->end() && "Ill-formed basic block") ? void (0) : __assert_fail ("InsertionPt != Parent->end() && \"Ill-formed basic block\"" , "llvm/lib/Transforms/Utils/Local.cpp", 1768, __extension__ __PRETTY_FUNCTION__ )); | |||
1769 | NewDbgII->insertBefore(&*InsertionPt); | |||
1770 | } | |||
1771 | } | |||
1772 | ||||
1773 | bool llvm::replaceDbgDeclare(Value *Address, Value *NewAddress, | |||
1774 | DIBuilder &Builder, uint8_t DIExprFlags, | |||
1775 | int Offset) { | |||
1776 | auto DbgAddrs = FindDbgAddrUses(Address); | |||
1777 | for (DbgVariableIntrinsic *DII : DbgAddrs) { | |||
1778 | const DebugLoc &Loc = DII->getDebugLoc(); | |||
1779 | auto *DIVar = DII->getVariable(); | |||
1780 | auto *DIExpr = DII->getExpression(); | |||
1781 | assert(DIVar && "Missing variable")(static_cast <bool> (DIVar && "Missing variable" ) ? void (0) : __assert_fail ("DIVar && \"Missing variable\"" , "llvm/lib/Transforms/Utils/Local.cpp", 1781, __extension__ __PRETTY_FUNCTION__ )); | |||
1782 | DIExpr = DIExpression::prepend(DIExpr, DIExprFlags, Offset); | |||
1783 | // Insert llvm.dbg.declare immediately before DII, and remove old | |||
1784 | // llvm.dbg.declare. | |||
1785 | Builder.insertDeclare(NewAddress, DIVar, DIExpr, Loc, DII); | |||
1786 | DII->eraseFromParent(); | |||
1787 | } | |||
1788 | return !DbgAddrs.empty(); | |||
1789 | } | |||
1790 | ||||
1791 | static void replaceOneDbgValueForAlloca(DbgValueInst *DVI, Value *NewAddress, | |||
1792 | DIBuilder &Builder, int Offset) { | |||
1793 | const DebugLoc &Loc = DVI->getDebugLoc(); | |||
1794 | auto *DIVar = DVI->getVariable(); | |||
1795 | auto *DIExpr = DVI->getExpression(); | |||
1796 | assert(DIVar && "Missing variable")(static_cast <bool> (DIVar && "Missing variable" ) ? void (0) : __assert_fail ("DIVar && \"Missing variable\"" , "llvm/lib/Transforms/Utils/Local.cpp", 1796, __extension__ __PRETTY_FUNCTION__ )); | |||
1797 | ||||
1798 | // This is an alloca-based llvm.dbg.value. The first thing it should do with | |||
1799 | // the alloca pointer is dereference it. Otherwise we don't know how to handle | |||
1800 | // it and give up. | |||
1801 | if (!DIExpr || DIExpr->getNumElements() < 1 || | |||
1802 | DIExpr->getElement(0) != dwarf::DW_OP_deref) | |||
1803 | return; | |||
1804 | ||||
1805 | // Insert the offset before the first deref. | |||
1806 | // We could just change the offset argument of dbg.value, but it's unsigned... | |||
1807 | if (Offset) | |||
1808 | DIExpr = DIExpression::prepend(DIExpr, 0, Offset); | |||
1809 | ||||
1810 | Builder.insertDbgValueIntrinsic(NewAddress, DIVar, DIExpr, Loc, DVI); | |||
1811 | DVI->eraseFromParent(); | |||
1812 | } | |||
1813 | ||||
1814 | void llvm::replaceDbgValueForAlloca(AllocaInst *AI, Value *NewAllocaAddress, | |||
1815 | DIBuilder &Builder, int Offset) { | |||
1816 | if (auto *L = LocalAsMetadata::getIfExists(AI)) | |||
1817 | if (auto *MDV = MetadataAsValue::getIfExists(AI->getContext(), L)) | |||
1818 | for (Use &U : llvm::make_early_inc_range(MDV->uses())) | |||
1819 | if (auto *DVI = dyn_cast<DbgValueInst>(U.getUser())) | |||
1820 | replaceOneDbgValueForAlloca(DVI, NewAllocaAddress, Builder, Offset); | |||
1821 | } | |||
1822 | ||||
1823 | /// Where possible to salvage debug information for \p I do so. | |||
1824 | /// If not possible mark undef. | |||
1825 | void llvm::salvageDebugInfo(Instruction &I) { | |||
1826 | SmallVector<DbgVariableIntrinsic *, 1> DbgUsers; | |||
1827 | findDbgUsers(DbgUsers, &I); | |||
1828 | salvageDebugInfoForDbgValues(I, DbgUsers); | |||
1829 | } | |||
1830 | ||||
1831 | /// Salvage the address component of \p DAI. | |||
1832 | static void salvageDbgAssignAddress(DbgAssignIntrinsic *DAI) { | |||
1833 | Instruction *I = dyn_cast<Instruction>(DAI->getAddress()); | |||
1834 | // Only instructions can be salvaged at the moment. | |||
1835 | if (!I) | |||
1836 | return; | |||
1837 | ||||
1838 | assert(!DAI->getAddressExpression()->getFragmentInfo().has_value() &&(static_cast <bool> (!DAI->getAddressExpression()-> getFragmentInfo().has_value() && "address-expression shouldn't have fragment info" ) ? void (0) : __assert_fail ("!DAI->getAddressExpression()->getFragmentInfo().has_value() && \"address-expression shouldn't have fragment info\"" , "llvm/lib/Transforms/Utils/Local.cpp", 1839, __extension__ __PRETTY_FUNCTION__ )) | |||
1839 | "address-expression shouldn't have fragment info")(static_cast <bool> (!DAI->getAddressExpression()-> getFragmentInfo().has_value() && "address-expression shouldn't have fragment info" ) ? void (0) : __assert_fail ("!DAI->getAddressExpression()->getFragmentInfo().has_value() && \"address-expression shouldn't have fragment info\"" , "llvm/lib/Transforms/Utils/Local.cpp", 1839, __extension__ __PRETTY_FUNCTION__ )); | |||
1840 | ||||
1841 | // The address component of a dbg.assign cannot be variadic. | |||
1842 | uint64_t CurrentLocOps = 0; | |||
1843 | SmallVector<Value *, 4> AdditionalValues; | |||
1844 | SmallVector<uint64_t, 16> Ops; | |||
1845 | Value *NewV = salvageDebugInfoImpl(*I, CurrentLocOps, Ops, AdditionalValues); | |||
1846 | ||||
1847 | // Check if the salvage failed. | |||
1848 | if (!NewV) | |||
1849 | return; | |||
1850 | ||||
1851 | DIExpression *SalvagedExpr = DIExpression::appendOpsToArg( | |||
1852 | DAI->getAddressExpression(), Ops, 0, /*StackValue=*/false); | |||
1853 | assert(!SalvagedExpr->getFragmentInfo().has_value() &&(static_cast <bool> (!SalvagedExpr->getFragmentInfo( ).has_value() && "address-expression shouldn't have fragment info" ) ? void (0) : __assert_fail ("!SalvagedExpr->getFragmentInfo().has_value() && \"address-expression shouldn't have fragment info\"" , "llvm/lib/Transforms/Utils/Local.cpp", 1854, __extension__ __PRETTY_FUNCTION__ )) | |||
1854 | "address-expression shouldn't have fragment info")(static_cast <bool> (!SalvagedExpr->getFragmentInfo( ).has_value() && "address-expression shouldn't have fragment info" ) ? void (0) : __assert_fail ("!SalvagedExpr->getFragmentInfo().has_value() && \"address-expression shouldn't have fragment info\"" , "llvm/lib/Transforms/Utils/Local.cpp", 1854, __extension__ __PRETTY_FUNCTION__ )); | |||
1855 | ||||
1856 | // Salvage succeeds if no additional values are required. | |||
1857 | if (AdditionalValues.empty()) { | |||
1858 | DAI->setAddress(NewV); | |||
1859 | DAI->setAddressExpression(SalvagedExpr); | |||
1860 | } else { | |||
1861 | DAI->setKillAddress(); | |||
1862 | } | |||
1863 | } | |||
1864 | ||||
1865 | void llvm::salvageDebugInfoForDbgValues( | |||
1866 | Instruction &I, ArrayRef<DbgVariableIntrinsic *> DbgUsers) { | |||
1867 | // These are arbitrary chosen limits on the maximum number of values and the | |||
1868 | // maximum size of a debug expression we can salvage up to, used for | |||
1869 | // performance reasons. | |||
1870 | const unsigned MaxDebugArgs = 16; | |||
1871 | const unsigned MaxExpressionSize = 128; | |||
1872 | bool Salvaged = false; | |||
1873 | ||||
1874 | for (auto *DII : DbgUsers) { | |||
1875 | if (auto *DAI
| |||
1876 | if (DAI->getAddress() == &I) { | |||
1877 | salvageDbgAssignAddress(DAI); | |||
1878 | Salvaged = true; | |||
1879 | } | |||
1880 | if (DAI->getValue() != &I) | |||
1881 | continue; | |||
1882 | } | |||
1883 | ||||
1884 | // Do not add DW_OP_stack_value for DbgDeclare and DbgAddr, because they | |||
1885 | // are implicitly pointing out the value as a DWARF memory location | |||
1886 | // description. | |||
1887 | bool StackValue = isa<DbgValueInst>(DII); | |||
1888 | auto DIILocation = DII->location_ops(); | |||
1889 | assert((static_cast <bool> (is_contained(DIILocation, &I) && "DbgVariableIntrinsic must use salvaged instruction as its location" ) ? void (0) : __assert_fail ("is_contained(DIILocation, &I) && \"DbgVariableIntrinsic must use salvaged instruction as its location\"" , "llvm/lib/Transforms/Utils/Local.cpp", 1891, __extension__ __PRETTY_FUNCTION__ )) | |||
1890 | is_contained(DIILocation, &I) &&(static_cast <bool> (is_contained(DIILocation, &I) && "DbgVariableIntrinsic must use salvaged instruction as its location" ) ? void (0) : __assert_fail ("is_contained(DIILocation, &I) && \"DbgVariableIntrinsic must use salvaged instruction as its location\"" , "llvm/lib/Transforms/Utils/Local.cpp", 1891, __extension__ __PRETTY_FUNCTION__ )) | |||
1891 | "DbgVariableIntrinsic must use salvaged instruction as its location")(static_cast <bool> (is_contained(DIILocation, &I) && "DbgVariableIntrinsic must use salvaged instruction as its location" ) ? void (0) : __assert_fail ("is_contained(DIILocation, &I) && \"DbgVariableIntrinsic must use salvaged instruction as its location\"" , "llvm/lib/Transforms/Utils/Local.cpp", 1891, __extension__ __PRETTY_FUNCTION__ )); | |||
1892 | SmallVector<Value *, 4> AdditionalValues; | |||
1893 | // `I` may appear more than once in DII's location ops, and each use of `I` | |||
1894 | // must be updated in the DIExpression and potentially have additional | |||
1895 | // values added; thus we call salvageDebugInfoImpl for each `I` instance in | |||
1896 | // DIILocation. | |||
1897 | Value *Op0 = nullptr; | |||
1898 | DIExpression *SalvagedExpr = DII->getExpression(); | |||
1899 | auto LocItr = find(DIILocation, &I); | |||
1900 | while (SalvagedExpr
| |||
1901 | SmallVector<uint64_t, 16> Ops; | |||
1902 | unsigned LocNo = std::distance(DIILocation.begin(), LocItr); | |||
1903 | uint64_t CurrentLocOps = SalvagedExpr->getNumLocationOperands(); | |||
1904 | Op0 = salvageDebugInfoImpl(I, CurrentLocOps, Ops, AdditionalValues); | |||
1905 | if (!Op0) | |||
1906 | break; | |||
1907 | SalvagedExpr = | |||
1908 | DIExpression::appendOpsToArg(SalvagedExpr, Ops, LocNo, StackValue); | |||
1909 | LocItr = std::find(++LocItr, DIILocation.end(), &I); | |||
1910 | } | |||
1911 | // salvageDebugInfoImpl should fail on examining the first element of | |||
1912 | // DbgUsers, or none of them. | |||
1913 | if (!Op0
| |||
1914 | break; | |||
1915 | ||||
1916 | DII->replaceVariableLocationOp(&I, Op0); | |||
1917 | bool IsValidSalvageExpr = SalvagedExpr->getNumElements() <= MaxExpressionSize; | |||
| ||||
1918 | if (AdditionalValues.empty() && IsValidSalvageExpr) { | |||
1919 | DII->setExpression(SalvagedExpr); | |||
1920 | } else if (isa<DbgValueInst>(DII) && !isa<DbgAssignIntrinsic>(DII) && | |||
1921 | IsValidSalvageExpr && | |||
1922 | DII->getNumVariableLocationOps() + AdditionalValues.size() <= | |||
1923 | MaxDebugArgs) { | |||
1924 | DII->addVariableLocationOps(AdditionalValues, SalvagedExpr); | |||
1925 | } else { | |||
1926 | // Do not salvage using DIArgList for dbg.addr/dbg.declare, as it is | |||
1927 | // not currently supported in those instructions. Do not salvage using | |||
1928 | // DIArgList for dbg.assign yet. FIXME: support this. | |||
1929 | // Also do not salvage if the resulting DIArgList would contain an | |||
1930 | // unreasonably large number of values. | |||
1931 | DII->setKillLocation(); | |||
1932 | } | |||
1933 | LLVM_DEBUG(dbgs() << "SALVAGE: " << *DII << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("local")) { dbgs() << "SALVAGE: " << *DII << '\n'; } } while (false); | |||
1934 | Salvaged = true; | |||
1935 | } | |||
1936 | ||||
1937 | if (Salvaged) | |||
1938 | return; | |||
1939 | ||||
1940 | for (auto *DII : DbgUsers) | |||
1941 | DII->setKillLocation(); | |||
1942 | } | |||
1943 | ||||
1944 | Value *getSalvageOpsForGEP(GetElementPtrInst *GEP, const DataLayout &DL, | |||
1945 | uint64_t CurrentLocOps, | |||
1946 | SmallVectorImpl<uint64_t> &Opcodes, | |||
1947 | SmallVectorImpl<Value *> &AdditionalValues) { | |||
1948 | unsigned BitWidth = DL.getIndexSizeInBits(GEP->getPointerAddressSpace()); | |||
1949 | // Rewrite a GEP into a DIExpression. | |||
1950 | MapVector<Value *, APInt> VariableOffsets; | |||
1951 | APInt ConstantOffset(BitWidth, 0); | |||
1952 | if (!GEP->collectOffset(DL, BitWidth, VariableOffsets, ConstantOffset)) | |||
1953 | return nullptr; | |||
1954 | if (!VariableOffsets.empty() && !CurrentLocOps) { | |||
1955 | Opcodes.insert(Opcodes.begin(), {dwarf::DW_OP_LLVM_arg, 0}); | |||
1956 | CurrentLocOps = 1; | |||
1957 | } | |||
1958 | for (auto Offset : VariableOffsets) { | |||
1959 | AdditionalValues.push_back(Offset.first); | |||
1960 | assert(Offset.second.isStrictlyPositive() &&(static_cast <bool> (Offset.second.isStrictlyPositive() && "Expected strictly positive multiplier for offset." ) ? void (0) : __assert_fail ("Offset.second.isStrictlyPositive() && \"Expected strictly positive multiplier for offset.\"" , "llvm/lib/Transforms/Utils/Local.cpp", 1961, __extension__ __PRETTY_FUNCTION__ )) | |||
1961 | "Expected strictly positive multiplier for offset.")(static_cast <bool> (Offset.second.isStrictlyPositive() && "Expected strictly positive multiplier for offset." ) ? void (0) : __assert_fail ("Offset.second.isStrictlyPositive() && \"Expected strictly positive multiplier for offset.\"" , "llvm/lib/Transforms/Utils/Local.cpp", 1961, __extension__ __PRETTY_FUNCTION__ )); | |||
1962 | Opcodes.append({dwarf::DW_OP_LLVM_arg, CurrentLocOps++, dwarf::DW_OP_constu, | |||
1963 | Offset.second.getZExtValue(), dwarf::DW_OP_mul, | |||
1964 | dwarf::DW_OP_plus}); | |||
1965 | } | |||
1966 | DIExpression::appendOffset(Opcodes, ConstantOffset.getSExtValue()); | |||
1967 | return GEP->getOperand(0); | |||
1968 | } | |||
1969 | ||||
1970 | uint64_t getDwarfOpForBinOp(Instruction::BinaryOps Opcode) { | |||
1971 | switch (Opcode) { | |||
1972 | case Instruction::Add: | |||
1973 | return dwarf::DW_OP_plus; | |||
1974 | case Instruction::Sub: | |||
1975 | return dwarf::DW_OP_minus; | |||
1976 | case Instruction::Mul: | |||
1977 | return dwarf::DW_OP_mul; | |||
1978 | case Instruction::SDiv: | |||
1979 | return dwarf::DW_OP_div; | |||
1980 | case Instruction::SRem: | |||
1981 | return dwarf::DW_OP_mod; | |||
1982 | case Instruction::Or: | |||
1983 | return dwarf::DW_OP_or; | |||
1984 | case Instruction::And: | |||
1985 | return dwarf::DW_OP_and; | |||
1986 | case Instruction::Xor: | |||
1987 | return dwarf::DW_OP_xor; | |||
1988 | case Instruction::Shl: | |||
1989 | return dwarf::DW_OP_shl; | |||
1990 | case Instruction::LShr: | |||
1991 | return dwarf::DW_OP_shr; | |||
1992 | case Instruction::AShr: | |||
1993 | return dwarf::DW_OP_shra; | |||
1994 | default: | |||
1995 | // TODO: Salvage from each kind of binop we know about. | |||
1996 | return 0; | |||
1997 | } | |||
1998 | } | |||
1999 | ||||
2000 | Value *getSalvageOpsForBinOp(BinaryOperator *BI, uint64_t CurrentLocOps, | |||
2001 | SmallVectorImpl<uint64_t> &Opcodes, | |||
2002 | SmallVectorImpl<Value *> &AdditionalValues) { | |||
2003 | // Handle binary operations with constant integer operands as a special case. | |||
2004 | auto *ConstInt = dyn_cast<ConstantInt>(BI->getOperand(1)); | |||
2005 | // Values wider than 64 bits cannot be represented within a DIExpression. | |||
2006 | if (ConstInt
| |||
2007 | return nullptr; | |||
2008 | ||||
2009 | Instruction::BinaryOps BinOpcode = BI->getOpcode(); | |||
2010 | // Push any Constant Int operand onto the expression stack. | |||
2011 | if (ConstInt
| |||
2012 | uint64_t Val = ConstInt->getSExtValue(); | |||
2013 | // Add or Sub Instructions with a constant operand can potentially be | |||
2014 | // simplified. | |||
2015 | if (BinOpcode == Instruction::Add || BinOpcode == Instruction::Sub) { | |||
2016 | uint64_t Offset = BinOpcode == Instruction::Add ? Val : -int64_t(Val); | |||
2017 | DIExpression::appendOffset(Opcodes, Offset); | |||
2018 | return BI->getOperand(0); | |||
2019 | } | |||
2020 | Opcodes.append({dwarf::DW_OP_constu, Val}); | |||
2021 | } else { | |||
2022 | if (!CurrentLocOps) { | |||
2023 | Opcodes.append({dwarf::DW_OP_LLVM_arg, 0}); | |||
2024 | CurrentLocOps = 1; | |||
2025 | } | |||
2026 | Opcodes.append({dwarf::DW_OP_LLVM_arg, CurrentLocOps}); | |||
2027 | AdditionalValues.push_back(BI->getOperand(1)); | |||
2028 | } | |||
2029 | ||||
2030 | // Add salvaged binary operator to expression stack, if it has a valid | |||
2031 | // representation in a DIExpression. | |||
2032 | uint64_t DwarfBinOp = getDwarfOpForBinOp(BinOpcode); | |||
2033 | if (!DwarfBinOp) | |||
2034 | return nullptr; | |||
2035 | Opcodes.push_back(DwarfBinOp); | |||
2036 | return BI->getOperand(0); | |||
2037 | } | |||
2038 | ||||
2039 | Value *llvm::salvageDebugInfoImpl(Instruction &I, uint64_t CurrentLocOps, | |||
2040 | SmallVectorImpl<uint64_t> &Ops, | |||
2041 | SmallVectorImpl<Value *> &AdditionalValues) { | |||
2042 | auto &M = *I.getModule(); | |||
2043 | auto &DL = M.getDataLayout(); | |||
2044 | ||||
2045 | if (auto *CI
| |||
2046 | Value *FromValue = CI->getOperand(0); | |||
2047 | // No-op casts are irrelevant for debug info. | |||
2048 | if (CI->isNoopCast(DL)) { | |||
2049 | return FromValue; | |||
2050 | } | |||
2051 | ||||
2052 | Type *Type = CI->getType(); | |||
2053 | if (Type->isPointerTy()) | |||
2054 | Type = DL.getIntPtrType(Type); | |||
2055 | // Casts other than Trunc, SExt, or ZExt to scalar types cannot be salvaged. | |||
2056 | if (Type->isVectorTy() || | |||
2057 | !(isa<TruncInst>(&I) || isa<SExtInst>(&I) || isa<ZExtInst>(&I) || | |||
2058 | isa<IntToPtrInst>(&I) || isa<PtrToIntInst>(&I))) | |||
2059 | return nullptr; | |||
2060 | ||||
2061 | llvm::Type *FromType = FromValue->getType(); | |||
2062 | if (FromType->isPointerTy()) | |||
2063 | FromType = DL.getIntPtrType(FromType); | |||
2064 | ||||
2065 | unsigned FromTypeBitSize = FromType->getScalarSizeInBits(); | |||
2066 | unsigned ToTypeBitSize = Type->getScalarSizeInBits(); | |||
2067 | ||||
2068 | auto ExtOps = DIExpression::getExtOps(FromTypeBitSize, ToTypeBitSize, | |||
2069 | isa<SExtInst>(&I)); | |||
2070 | Ops.append(ExtOps.begin(), ExtOps.end()); | |||
2071 | return FromValue; | |||
2072 | } | |||
2073 | ||||
2074 | if (auto *GEP
| |||
2075 | return getSalvageOpsForGEP(GEP, DL, CurrentLocOps, Ops, AdditionalValues); | |||
2076 | if (auto *BI
| |||
2077 | return getSalvageOpsForBinOp(BI, CurrentLocOps, Ops, AdditionalValues); | |||
2078 | ||||
2079 | // *Not* to do: we should not attempt to salvage load instructions, | |||
2080 | // because the validity and lifetime of a dbg.value containing | |||
2081 | // DW_OP_deref becomes difficult to analyze. See PR40628 for examples. | |||
2082 | return nullptr; | |||
2083 | } | |||
2084 | ||||
2085 | /// A replacement for a dbg.value expression. | |||
2086 | using DbgValReplacement = std::optional<DIExpression *>; | |||
2087 | ||||
2088 | /// Point debug users of \p From to \p To using exprs given by \p RewriteExpr, | |||
2089 | /// possibly moving/undefing users to prevent use-before-def. Returns true if | |||
2090 | /// changes are made. | |||
2091 | static bool rewriteDebugUsers( | |||
2092 | Instruction &From, Value &To, Instruction &DomPoint, DominatorTree &DT, | |||
2093 | function_ref<DbgValReplacement(DbgVariableIntrinsic &DII)> RewriteExpr) { | |||
2094 | // Find debug users of From. | |||
2095 | SmallVector<DbgVariableIntrinsic *, 1> Users; | |||
2096 | findDbgUsers(Users, &From); | |||
2097 | if (Users.empty()) | |||
2098 | return false; | |||
2099 | ||||
2100 | // Prevent use-before-def of To. | |||
2101 | bool Changed = false; | |||
2102 | SmallPtrSet<DbgVariableIntrinsic *, 1> UndefOrSalvage; | |||
2103 | if (isa<Instruction>(&To)) { | |||
2104 | bool DomPointAfterFrom = From.getNextNonDebugInstruction() == &DomPoint; | |||
2105 | ||||
2106 | for (auto *DII : Users) { | |||
2107 | // It's common to see a debug user between From and DomPoint. Move it | |||
2108 | // after DomPoint to preserve the variable update without any reordering. | |||
2109 | if (DomPointAfterFrom && DII->getNextNonDebugInstruction() == &DomPoint) { | |||
2110 | LLVM_DEBUG(dbgs() << "MOVE: " << *DII << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("local")) { dbgs() << "MOVE: " << *DII << '\n'; } } while (false); | |||
2111 | DII->moveAfter(&DomPoint); | |||
2112 | Changed = true; | |||
2113 | ||||
2114 | // Users which otherwise aren't dominated by the replacement value must | |||
2115 | // be salvaged or deleted. | |||
2116 | } else if (!DT.dominates(&DomPoint, DII)) { | |||
2117 | UndefOrSalvage.insert(DII); | |||
2118 | } | |||
2119 | } | |||
2120 | } | |||
2121 | ||||
2122 | // Update debug users without use-before-def risk. | |||
2123 | for (auto *DII : Users) { | |||
2124 | if (UndefOrSalvage.count(DII)) | |||
2125 | continue; | |||
2126 | ||||
2127 | DbgValReplacement DVR = RewriteExpr(*DII); | |||
2128 | if (!DVR) | |||
2129 | continue; | |||
2130 | ||||
2131 | DII->replaceVariableLocationOp(&From, &To); | |||
2132 | DII->setExpression(*DVR); | |||
2133 | LLVM_DEBUG(dbgs() << "REWRITE: " << *DII << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("local")) { dbgs() << "REWRITE: " << *DII << '\n'; } } while (false); | |||
2134 | Changed = true; | |||
2135 | } | |||
2136 | ||||
2137 | if (!UndefOrSalvage.empty()) { | |||
2138 | // Try to salvage the remaining debug users. | |||
2139 | salvageDebugInfo(From); | |||
2140 | Changed = true; | |||
2141 | } | |||
2142 | ||||
2143 | return Changed; | |||
2144 | } | |||
2145 | ||||
2146 | /// Check if a bitcast between a value of type \p FromTy to type \p ToTy would | |||
2147 | /// losslessly preserve the bits and semantics of the value. This predicate is | |||
2148 | /// symmetric, i.e swapping \p FromTy and \p ToTy should give the same result. | |||
2149 | /// | |||
2150 | /// Note that Type::canLosslesslyBitCastTo is not suitable here because it | |||
2151 | /// allows semantically unequivalent bitcasts, such as <2 x i64> -> <4 x i32>, | |||
2152 | /// and also does not allow lossless pointer <-> integer conversions. | |||
2153 | static bool isBitCastSemanticsPreserving(const DataLayout &DL, Type *FromTy, | |||
2154 | Type *ToTy) { | |||
2155 | // Trivially compatible types. | |||
2156 | if (FromTy == ToTy) | |||
2157 | return true; | |||
2158 | ||||
2159 | // Handle compatible pointer <-> integer conversions. | |||
2160 | if (FromTy->isIntOrPtrTy() && ToTy->isIntOrPtrTy()) { | |||
2161 | bool SameSize = DL.getTypeSizeInBits(FromTy) == DL.getTypeSizeInBits(ToTy); | |||
2162 | bool LosslessConversion = !DL.isNonIntegralPointerType(FromTy) && | |||
2163 | !DL.isNonIntegralPointerType(ToTy); | |||
2164 | return SameSize && LosslessConversion; | |||
2165 | } | |||
2166 | ||||
2167 | // TODO: This is not exhaustive. | |||
2168 | return false; | |||
2169 | } | |||
2170 | ||||
2171 | bool llvm::replaceAllDbgUsesWith(Instruction &From, Value &To, | |||
2172 | Instruction &DomPoint, DominatorTree &DT) { | |||
2173 | // Exit early if From has no debug users. | |||
2174 | if (!From.isUsedByMetadata()) | |||
| ||||
2175 | return false; | |||
2176 | ||||
2177 | assert(&From != &To && "Can't replace something with itself")(static_cast <bool> (&From != &To && "Can't replace something with itself" ) ? void (0) : __assert_fail ("&From != &To && \"Can't replace something with itself\"" , "llvm/lib/Transforms/Utils/Local.cpp", 2177, __extension__ __PRETTY_FUNCTION__ )); | |||
2178 | ||||
2179 | Type *FromTy = From.getType(); | |||
2180 | Type *ToTy = To.getType(); | |||
2181 | ||||
2182 | auto Identity = [&](DbgVariableIntrinsic &DII) -> DbgValReplacement { | |||
2183 | return DII.getExpression(); | |||
2184 | }; | |||
2185 | ||||
2186 | // Handle no-op conversions. | |||
2187 | Module &M = *From.getModule(); | |||
2188 | const DataLayout &DL = M.getDataLayout(); | |||
2189 | if (isBitCastSemanticsPreserving(DL, FromTy, ToTy)) | |||
2190 | return rewriteDebugUsers(From, To, DomPoint, DT, Identity); | |||
2191 | ||||
2192 | // Handle integer-to-integer widening and narrowing. | |||
2193 | // FIXME: Use DW_OP_convert when it's available everywhere. | |||
2194 | if (FromTy->isIntegerTy() && ToTy->isIntegerTy()) { | |||
2195 | uint64_t FromBits = FromTy->getPrimitiveSizeInBits(); | |||
2196 | uint64_t ToBits = ToTy->getPrimitiveSizeInBits(); | |||
2197 | assert(FromBits != ToBits && "Unexpected no-op conversion")(static_cast <bool> (FromBits != ToBits && "Unexpected no-op conversion" ) ? void (0) : __assert_fail ("FromBits != ToBits && \"Unexpected no-op conversion\"" , "llvm/lib/Transforms/Utils/Local.cpp", 2197, __extension__ __PRETTY_FUNCTION__ )); | |||
2198 | ||||
2199 | // When the width of the result grows, assume that a debugger will only | |||
2200 | // access the low `FromBits` bits when inspecting the source variable. | |||
2201 | if (FromBits < ToBits) | |||
2202 | return rewriteDebugUsers(From, To, DomPoint, DT, Identity); | |||
2203 | ||||
2204 | // The width of the result has shrunk. Use sign/zero extension to describe | |||
2205 | // the source variable's high bits. | |||
2206 | auto SignOrZeroExt = [&](DbgVariableIntrinsic &DII) -> DbgValReplacement { | |||
2207 | DILocalVariable *Var = DII.getVariable(); | |||
2208 | ||||
2209 | // Without knowing signedness, sign/zero extension isn't possible. | |||
2210 | auto Signedness = Var->getSignedness(); | |||
2211 | if (!Signedness) | |||
2212 | return std::nullopt; | |||
2213 | ||||
2214 | bool Signed = *Signedness == DIBasicType::Signedness::Signed; | |||
2215 | return DIExpression::appendExt(DII.getExpression(), ToBits, FromBits, | |||
2216 | Signed); | |||
2217 | }; | |||
2218 | return rewriteDebugUsers(From, To, DomPoint, DT, SignOrZeroExt); | |||
2219 | } | |||
2220 | ||||
2221 | // TODO: Floating-point conversions, vectors. | |||
2222 | return false; | |||
2223 | } | |||
2224 | ||||
2225 | std::pair<unsigned, unsigned> | |||
2226 | llvm::removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB) { | |||
2227 | unsigned NumDeadInst = 0; | |||
2228 | unsigned NumDeadDbgInst = 0; | |||
2229 | // Delete the instructions backwards, as it has a reduced likelihood of | |||
2230 | // having to update as many def-use and use-def chains. | |||
2231 | Instruction *EndInst = BB->getTerminator(); // Last not to be deleted. | |||
2232 | while (EndInst != &BB->front()) { | |||
2233 | // Delete the next to last instruction. | |||
2234 | Instruction *Inst = &*--EndInst->getIterator(); | |||
2235 | if (!Inst->use_empty() && !Inst->getType()->isTokenTy()) | |||
2236 | Inst->replaceAllUsesWith(PoisonValue::get(Inst->getType())); | |||
2237 | if (Inst->isEHPad() || Inst->getType()->isTokenTy()) { | |||
2238 | EndInst = Inst; | |||
2239 | continue; | |||
2240 | } | |||
2241 | if (isa<DbgInfoIntrinsic>(Inst)) | |||
2242 | ++NumDeadDbgInst; | |||
2243 | else | |||
2244 | ++NumDeadInst; | |||
2245 | Inst->eraseFromParent(); | |||
2246 | } | |||
2247 | return {NumDeadInst, NumDeadDbgInst}; | |||
2248 | } | |||
2249 | ||||
2250 | unsigned llvm::changeToUnreachable(Instruction *I, bool PreserveLCSSA, | |||
2251 | DomTreeUpdater *DTU, | |||
2252 | MemorySSAUpdater *MSSAU) { | |||
2253 | BasicBlock *BB = I->getParent(); | |||
2254 | ||||
2255 | if (MSSAU) | |||
2256 | MSSAU->changeToUnreachable(I); | |||
2257 | ||||
2258 | SmallSet<BasicBlock *, 8> UniqueSuccessors; | |||
2259 | ||||
2260 | // Loop over all of the successors, removing BB's entry from any PHI | |||
2261 | // nodes. | |||
2262 | for (BasicBlock *Successor : successors(BB)) { | |||
2263 | Successor->removePredecessor(BB, PreserveLCSSA); | |||
2264 | if (DTU) | |||
2265 | UniqueSuccessors.insert(Successor); | |||
2266 | } | |||
2267 | auto *UI = new UnreachableInst(I->getContext(), I); | |||
2268 | UI->setDebugLoc(I->getDebugLoc()); | |||
2269 | ||||
2270 | // All instructions after this are dead. | |||
2271 | unsigned NumInstrsRemoved = 0; | |||
2272 | BasicBlock::iterator BBI = I->getIterator(), BBE = BB->end(); | |||
2273 | while (BBI != BBE) { | |||
2274 | if (!BBI->use_empty()) | |||
2275 | BBI->replaceAllUsesWith(PoisonValue::get(BBI->getType())); | |||
2276 | BBI++->eraseFromParent(); | |||
2277 | ++NumInstrsRemoved; | |||
2278 | } | |||
2279 | if (DTU) { | |||
2280 | SmallVector<DominatorTree::UpdateType, 8> Updates; | |||
2281 | Updates.reserve(UniqueSuccessors.size()); | |||
2282 | for (BasicBlock *UniqueSuccessor : UniqueSuccessors) | |||
2283 | Updates.push_back({DominatorTree::Delete, BB, UniqueSuccessor}); | |||
2284 | DTU->applyUpdates(Updates); | |||
2285 | } | |||
2286 | return NumInstrsRemoved; | |||
2287 | } | |||
2288 | ||||
2289 | CallInst *llvm::createCallMatchingInvoke(InvokeInst *II) { | |||
2290 | SmallVector<Value *, 8> Args(II->args()); | |||
2291 | SmallVector<OperandBundleDef, 1> OpBundles; | |||
2292 | II->getOperandBundlesAsDefs(OpBundles); | |||
2293 | CallInst *NewCall = CallInst::Create(II->getFunctionType(), | |||
2294 | II->getCalledOperand(), Args, OpBundles); | |||
2295 | NewCall->setCallingConv(II->getCallingConv()); | |||
2296 | NewCall->setAttributes(II->getAttributes()); | |||
2297 | NewCall->setDebugLoc(II->getDebugLoc()); | |||
2298 | NewCall->copyMetadata(*II); | |||
2299 | ||||
2300 | // If the invoke had profile metadata, try converting them for CallInst. | |||
2301 | uint64_t TotalWeight; | |||
2302 | if (NewCall->extractProfTotalWeight(TotalWeight)) { | |||
2303 | // Set the total weight if it fits into i32, otherwise reset. | |||
2304 | MDBuilder MDB(NewCall->getContext()); | |||
2305 | auto NewWeights = uint32_t(TotalWeight) != TotalWeight | |||
2306 | ? nullptr | |||
2307 | : MDB.createBranchWeights({uint32_t(TotalWeight)}); | |||
2308 | NewCall->setMetadata(LLVMContext::MD_prof, NewWeights); | |||
2309 | } | |||
2310 | ||||
2311 | return NewCall; | |||
2312 | } | |||
2313 | ||||
2314 | // changeToCall - Convert the specified invoke into a normal call. | |||
2315 | CallInst *llvm::changeToCall(InvokeInst *II, DomTreeUpdater *DTU) { | |||
2316 | CallInst *NewCall = createCallMatchingInvoke(II); | |||
2317 | NewCall->takeName(II); | |||
2318 | NewCall->insertBefore(II); | |||
2319 | II->replaceAllUsesWith(NewCall); | |||
2320 | ||||
2321 | // Follow the call by a branch to the normal destination. | |||
2322 | BasicBlock *NormalDestBB = II->getNormalDest(); | |||
2323 | BranchInst::Create(NormalDestBB, II); | |||
2324 | ||||
2325 | // Update PHI nodes in the unwind destination | |||
2326 | BasicBlock *BB = II->getParent(); | |||
2327 | BasicBlock *UnwindDestBB = II->getUnwindDest(); | |||
2328 | UnwindDestBB->removePredecessor(BB); | |||
2329 | II->eraseFromParent(); | |||
2330 | if (DTU) | |||
2331 | DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDestBB}}); | |||
2332 | return NewCall; | |||
2333 | } | |||
2334 | ||||
2335 | BasicBlock *llvm::changeToInvokeAndSplitBasicBlock(CallInst *CI, | |||
2336 | BasicBlock *UnwindEdge, | |||
2337 | DomTreeUpdater *DTU) { | |||
2338 | BasicBlock *BB = CI->getParent(); | |||
2339 | ||||
2340 | // Convert this function call into an invoke instruction. First, split the | |||
2341 | // basic block. | |||
2342 | BasicBlock *Split = SplitBlock(BB, CI, DTU, /*LI=*/nullptr, /*MSSAU*/ nullptr, | |||
2343 | CI->getName() + ".noexc"); | |||
2344 | ||||
2345 | // Delete the unconditional branch inserted by SplitBlock | |||
2346 | BB->back().eraseFromParent(); | |||
2347 | ||||
2348 | // Create the new invoke instruction. | |||
2349 | SmallVector<Value *, 8> InvokeArgs(CI->args()); | |||
2350 | SmallVector<OperandBundleDef, 1> OpBundles; | |||
2351 | ||||
2352 | CI->getOperandBundlesAsDefs(OpBundles); | |||
2353 | ||||
2354 | // Note: we're round tripping operand bundles through memory here, and that | |||
2355 | // can potentially be avoided with a cleverer API design that we do not have | |||
2356 | // as of this time. | |||
2357 | ||||
2358 | InvokeInst *II = | |||
2359 | InvokeInst::Create(CI->getFunctionType(), CI->getCalledOperand(), Split, | |||
2360 | UnwindEdge, InvokeArgs, OpBundles, CI->getName(), BB); | |||
2361 | II->setDebugLoc(CI->getDebugLoc()); | |||
2362 | II->setCallingConv(CI->getCallingConv()); | |||
2363 | II->setAttributes(CI->getAttributes()); | |||
2364 | II->setMetadata(LLVMContext::MD_prof, CI->getMetadata(LLVMContext::MD_prof)); | |||
2365 | ||||
2366 | if (DTU) | |||
2367 | DTU->applyUpdates({{DominatorTree::Insert, BB, UnwindEdge}}); | |||
2368 | ||||
2369 | // Make sure that anything using the call now uses the invoke! This also | |||
2370 | // updates the CallGraph if present, because it uses a WeakTrackingVH. | |||
2371 | CI->replaceAllUsesWith(II); | |||
2372 | ||||
2373 | // Delete the original call | |||
2374 | Split->front().eraseFromParent(); | |||
2375 | return Split; | |||
2376 | } | |||
2377 | ||||
2378 | static bool markAliveBlocks(Function &F, | |||
2379 | SmallPtrSetImpl<BasicBlock *> &Reachable, | |||
2380 | DomTreeUpdater *DTU = nullptr) { | |||
2381 | SmallVector<BasicBlock*, 128> Worklist; | |||
2382 | BasicBlock *BB = &F.front(); | |||
2383 | Worklist.push_back(BB); | |||
2384 | Reachable.insert(BB); | |||
2385 | bool Changed = false; | |||
2386 | do { | |||
2387 | BB = Worklist.pop_back_val(); | |||
2388 | ||||
2389 | // Do a quick scan of the basic block, turning any obviously unreachable | |||
2390 | // instructions into LLVM unreachable insts. The instruction combining pass | |||
2391 | // canonicalizes unreachable insts into stores to null or undef. | |||
2392 | for (Instruction &I : *BB) { | |||
2393 | if (auto *CI = dyn_cast<CallInst>(&I)) { | |||
2394 | Value *Callee = CI->getCalledOperand(); | |||
2395 | // Handle intrinsic calls. | |||
2396 | if (Function *F = dyn_cast<Function>(Callee)) { | |||
2397 | auto IntrinsicID = F->getIntrinsicID(); | |||
2398 | // Assumptions that are known to be false are equivalent to | |||
2399 | // unreachable. Also, if the condition is undefined, then we make the | |||
2400 | // choice most beneficial to the optimizer, and choose that to also be | |||
2401 | // unreachable. | |||
2402 | if (IntrinsicID == Intrinsic::assume) { | |||
2403 | if (match(CI->getArgOperand(0), m_CombineOr(m_Zero(), m_Undef()))) { | |||
2404 | // Don't insert a call to llvm.trap right before the unreachable. | |||
2405 | changeToUnreachable(CI, false, DTU); | |||
2406 | Changed = true; | |||
2407 | break; | |||
2408 | } | |||
2409 | } else if (IntrinsicID == Intrinsic::experimental_guard) { | |||
2410 | // A call to the guard intrinsic bails out of the current | |||
2411 | // compilation unit if the predicate passed to it is false. If the | |||
2412 | // predicate is a constant false, then we know the guard will bail | |||
2413 | // out of the current compile unconditionally, so all code following | |||
2414 | // it is dead. | |||
2415 | // | |||
2416 | // Note: unlike in llvm.assume, it is not "obviously profitable" for | |||
2417 | // guards to treat `undef` as `false` since a guard on `undef` can | |||
2418 | // still be useful for widening. | |||
2419 | if (match(CI->getArgOperand(0), m_Zero())) | |||
2420 | if (!isa<UnreachableInst>(CI->getNextNode())) { | |||
2421 | changeToUnreachable(CI->getNextNode(), false, DTU); | |||
2422 | Changed = true; | |||
2423 | break; | |||
2424 | } | |||
2425 | } | |||
2426 | } else if ((isa<ConstantPointerNull>(Callee) && | |||
2427 | !NullPointerIsDefined(CI->getFunction(), | |||
2428 | cast<PointerType>(Callee->getType()) | |||
2429 | ->getAddressSpace())) || | |||
2430 | isa<UndefValue>(Callee)) { | |||
2431 | changeToUnreachable(CI, false, DTU); | |||
2432 | Changed = true; | |||
2433 | break; | |||
2434 | } | |||
2435 | if (CI->doesNotReturn() && !CI->isMustTailCall()) { | |||
2436 | // If we found a call to a no-return function, insert an unreachable | |||
2437 | // instruction after it. Make sure there isn't *already* one there | |||
2438 | // though. | |||
2439 | if (!isa<UnreachableInst>(CI->getNextNode())) { | |||
2440 | // Don't insert a call to llvm.trap right before the unreachable. | |||
2441 | changeToUnreachable(CI->getNextNode(), false, DTU); | |||
2442 | Changed = true; | |||
2443 | } | |||
2444 | break; | |||
2445 | } | |||
2446 | } else if (auto *SI = dyn_cast<StoreInst>(&I)) { | |||
2447 | // Store to undef and store to null are undefined and used to signal | |||
2448 | // that they should be changed to unreachable by passes that can't | |||
2449 | // modify the CFG. | |||
2450 | ||||
2451 | // Don't touch volatile stores. | |||
2452 | if (SI->isVolatile()) continue; | |||
2453 | ||||
2454 | Value *Ptr = SI->getOperand(1); | |||
2455 | ||||
2456 | if (isa<UndefValue>(Ptr) || | |||
2457 | (isa<ConstantPointerNull>(Ptr) && | |||
2458 | !NullPointerIsDefined(SI->getFunction(), | |||
2459 | SI->getPointerAddressSpace()))) { | |||
2460 | changeToUnreachable(SI, false, DTU); | |||
2461 | Changed = true; | |||
2462 | break; | |||
2463 | } | |||
2464 | } | |||
2465 | } | |||
2466 | ||||
2467 | Instruction *Terminator = BB->getTerminator(); | |||
2468 | if (auto *II = dyn_cast<InvokeInst>(Terminator)) { | |||
2469 | // Turn invokes that call 'nounwind' functions into ordinary calls. | |||
2470 | Value *Callee = II->getCalledOperand(); | |||
2471 | if ((isa<ConstantPointerNull>(Callee) && | |||
2472 | !NullPointerIsDefined(BB->getParent())) || | |||
2473 | isa<UndefValue>(Callee)) { | |||
2474 | changeToUnreachable(II, false, DTU); | |||
2475 | Changed = true; | |||
2476 | } else { | |||
2477 | if (II->doesNotReturn() && | |||
2478 | !isa<UnreachableInst>(II->getNormalDest()->front())) { | |||
2479 | // If we found an invoke of a no-return function, | |||
2480 | // create a new empty basic block with an `unreachable` terminator, | |||
2481 | // and set it as the normal destination for the invoke, | |||
2482 | // unless that is already the case. | |||
2483 | // Note that the original normal destination could have other uses. | |||
2484 | BasicBlock *OrigNormalDest = II->getNormalDest(); | |||
2485 | OrigNormalDest->removePredecessor(II->getParent()); | |||
2486 | LLVMContext &Ctx = II->getContext(); | |||
2487 | BasicBlock *UnreachableNormalDest = BasicBlock::Create( | |||
2488 | Ctx, OrigNormalDest->getName() + ".unreachable", | |||
2489 | II->getFunction(), OrigNormalDest); | |||
2490 | new UnreachableInst(Ctx, UnreachableNormalDest); | |||
2491 | II->setNormalDest(UnreachableNormalDest); | |||
2492 | if (DTU) | |||
2493 | DTU->applyUpdates( | |||
2494 | {{DominatorTree::Delete, BB, OrigNormalDest}, | |||
2495 | {DominatorTree::Insert, BB, UnreachableNormalDest}}); | |||
2496 | Changed = true; | |||
2497 | } | |||
2498 | if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(&F)) { | |||
2499 | if (II->use_empty() && !II->mayHaveSideEffects()) { | |||
2500 | // jump to the normal destination branch. | |||
2501 | BasicBlock *NormalDestBB = II->getNormalDest(); | |||
2502 | BasicBlock *UnwindDestBB = II->getUnwindDest(); | |||
2503 | BranchInst::Create(NormalDestBB, II); | |||
2504 | UnwindDestBB->removePredecessor(II->getParent()); | |||
2505 | II->eraseFromParent(); | |||
2506 | if (DTU) | |||
2507 | DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDestBB}}); | |||
2508 | } else | |||
2509 | changeToCall(II, DTU); | |||
2510 | Changed = true; | |||
2511 | } | |||
2512 | } | |||
2513 | } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Terminator)) { | |||
2514 | // Remove catchpads which cannot be reached. | |||
2515 | struct CatchPadDenseMapInfo { | |||
2516 | static CatchPadInst *getEmptyKey() { | |||
2517 | return DenseMapInfo<CatchPadInst *>::getEmptyKey(); | |||
2518 | } | |||
2519 | ||||
2520 | static CatchPadInst *getTombstoneKey() { | |||
2521 | return DenseMapInfo<CatchPadInst *>::getTombstoneKey(); | |||
2522 | } | |||
2523 | ||||
2524 | static unsigned getHashValue(CatchPadInst *CatchPad) { | |||
2525 | return static_cast<unsigned>(hash_combine_range( | |||
2526 | CatchPad->value_op_begin(), CatchPad->value_op_end())); | |||
2527 | } | |||
2528 | ||||
2529 | static bool isEqual(CatchPadInst *LHS, CatchPadInst *RHS) { | |||
2530 | if (LHS == getEmptyKey() || LHS == getTombstoneKey() || | |||
2531 | RHS == getEmptyKey() || RHS == getTombstoneKey()) | |||
2532 | return LHS == RHS; | |||
2533 | return LHS->isIdenticalTo(RHS); | |||
2534 | } | |||
2535 | }; | |||
2536 | ||||
2537 | SmallDenseMap<BasicBlock *, int, 8> NumPerSuccessorCases; | |||
2538 | // Set of unique CatchPads. | |||
2539 | SmallDenseMap<CatchPadInst *, detail::DenseSetEmpty, 4, | |||
2540 | CatchPadDenseMapInfo, detail::DenseSetPair<CatchPadInst *>> | |||
2541 | HandlerSet; | |||
2542 | detail::DenseSetEmpty Empty; | |||
2543 | for (CatchSwitchInst::handler_iterator I = CatchSwitch->handler_begin(), | |||
2544 | E = CatchSwitch->handler_end(); | |||
2545 | I != E; ++I) { | |||
2546 | BasicBlock *HandlerBB = *I; | |||
2547 | if (DTU) | |||
2548 | ++NumPerSuccessorCases[HandlerBB]; | |||
2549 | auto *CatchPad = cast<CatchPadInst>(HandlerBB->getFirstNonPHI()); | |||
2550 | if (!HandlerSet.insert({CatchPad, Empty}).second) { | |||
2551 | if (DTU) | |||
2552 | --NumPerSuccessorCases[HandlerBB]; | |||
2553 | CatchSwitch->removeHandler(I); | |||
2554 | --I; | |||
2555 | --E; | |||
2556 | Changed = true; | |||
2557 | } | |||
2558 | } | |||
2559 | if (DTU) { | |||
2560 | std::vector<DominatorTree::UpdateType> Updates; | |||
2561 | for (const std::pair<BasicBlock *, int> &I : NumPerSuccessorCases) | |||
2562 | if (I.second == 0) | |||
2563 | Updates.push_back({DominatorTree::Delete, BB, I.first}); | |||
2564 | DTU->applyUpdates(Updates); | |||
2565 | } | |||
2566 | } | |||
2567 | ||||
2568 | Changed |= ConstantFoldTerminator(BB, true, nullptr, DTU); | |||
2569 | for (BasicBlock *Successor : successors(BB)) | |||
2570 | if (Reachable.insert(Successor).second) | |||
2571 | Worklist.push_back(Successor); | |||
2572 | } while (!Worklist.empty()); | |||
2573 | return Changed; | |||
2574 | } | |||
2575 | ||||
2576 | Instruction *llvm::removeUnwindEdge(BasicBlock *BB, DomTreeUpdater *DTU) { | |||
2577 | Instruction *TI = BB->getTerminator(); | |||
2578 | ||||
2579 | if (auto *II = dyn_cast<InvokeInst>(TI)) | |||
2580 | return changeToCall(II, DTU); | |||
2581 | ||||
2582 | Instruction *NewTI; | |||
2583 | BasicBlock *UnwindDest; | |||
2584 | ||||
2585 | if (auto *CRI = dyn_cast<CleanupReturnInst>(TI)) { | |||
2586 | NewTI = CleanupReturnInst::Create(CRI->getCleanupPad(), nullptr, CRI); | |||
2587 | UnwindDest = CRI->getUnwindDest(); | |||
2588 | } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(TI)) { | |||
2589 | auto *NewCatchSwitch = CatchSwitchInst::Create( | |||
2590 | CatchSwitch->getParentPad(), nullptr, CatchSwitch->getNumHandlers(), | |||
2591 | CatchSwitch->getName(), CatchSwitch); | |||
2592 | for (BasicBlock *PadBB : CatchSwitch->handlers()) | |||
2593 | NewCatchSwitch->addHandler(PadBB); | |||
2594 | ||||
2595 | NewTI = NewCatchSwitch; | |||
2596 | UnwindDest = CatchSwitch->getUnwindDest(); | |||
2597 | } else { | |||
2598 | llvm_unreachable("Could not find unwind successor")::llvm::llvm_unreachable_internal("Could not find unwind successor" , "llvm/lib/Transforms/Utils/Local.cpp", 2598); | |||
2599 | } | |||
2600 | ||||
2601 | NewTI->takeName(TI); | |||
2602 | NewTI->setDebugLoc(TI->getDebugLoc()); | |||
2603 | UnwindDest->removePredecessor(BB); | |||
2604 | TI->replaceAllUsesWith(NewTI); | |||
2605 | TI->eraseFromParent(); | |||
2606 | if (DTU) | |||
2607 | DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDest}}); | |||
2608 | return NewTI; | |||
2609 | } | |||
2610 | ||||
2611 | /// removeUnreachableBlocks - Remove blocks that are not reachable, even | |||
2612 | /// if they are in a dead cycle. Return true if a change was made, false | |||
2613 | /// otherwise. | |||
2614 | bool llvm::removeUnreachableBlocks(Function &F, DomTreeUpdater *DTU, | |||
2615 | MemorySSAUpdater *MSSAU) { | |||
2616 | SmallPtrSet<BasicBlock *, 16> Reachable; | |||
2617 | bool Changed = markAliveBlocks(F, Reachable, DTU); | |||
2618 | ||||
2619 | // If there are unreachable blocks in the CFG... | |||
2620 | if (Reachable.size() == F.size()) | |||
2621 | return Changed; | |||
2622 | ||||
2623 | assert(Reachable.size() < F.size())(static_cast <bool> (Reachable.size() < F.size()) ? void (0) : __assert_fail ("Reachable.size() < F.size()", "llvm/lib/Transforms/Utils/Local.cpp" , 2623, __extension__ __PRETTY_FUNCTION__)); | |||
2624 | ||||
2625 | // Are there any blocks left to actually delete? | |||
2626 | SmallSetVector<BasicBlock *, 8> BlocksToRemove; | |||
2627 | for (BasicBlock &BB : F) { | |||
2628 | // Skip reachable basic blocks | |||
2629 | if (Reachable.count(&BB)) | |||
2630 | continue; | |||
2631 | // Skip already-deleted blocks | |||
2632 | if (DTU && DTU->isBBPendingDeletion(&BB)) | |||
2633 | continue; | |||
2634 | BlocksToRemove.insert(&BB); | |||
2635 | } | |||
2636 | ||||
2637 | if (BlocksToRemove.empty()) | |||
2638 | return Changed; | |||
2639 | ||||
2640 | Changed = true; | |||
2641 | NumRemoved += BlocksToRemove.size(); | |||
2642 | ||||
2643 | if (MSSAU) | |||
2644 | MSSAU->removeBlocks(BlocksToRemove); | |||
2645 | ||||
2646 | DeleteDeadBlocks(BlocksToRemove.takeVector(), DTU); | |||
2647 | ||||
2648 | return Changed; | |||
2649 | } | |||
2650 | ||||
2651 | void llvm::combineMetadata(Instruction *K, const Instruction *J, | |||
2652 | ArrayRef<unsigned> KnownIDs, bool DoesKMove) { | |||
2653 | SmallVector<std::pair<unsigned, MDNode *>, 4> Metadata; | |||
2654 | K->dropUnknownNonDebugMetadata(KnownIDs); | |||
2655 | K->getAllMetadataOtherThanDebugLoc(Metadata); | |||
2656 | for (const auto &MD : Metadata) { | |||
2657 | unsigned Kind = MD.first; | |||
2658 | MDNode *JMD = J->getMetadata(Kind); | |||
2659 | MDNode *KMD = MD.second; | |||
2660 | ||||
2661 | switch (Kind) { | |||
2662 | default: | |||
2663 | K->setMetadata(Kind, nullptr); // Remove unknown metadata | |||
2664 | break; | |||
2665 | case LLVMContext::MD_dbg: | |||
2666 | llvm_unreachable("getAllMetadataOtherThanDebugLoc returned a MD_dbg")::llvm::llvm_unreachable_internal("getAllMetadataOtherThanDebugLoc returned a MD_dbg" , "llvm/lib/Transforms/Utils/Local.cpp", 2666); | |||
2667 | case LLVMContext::MD_DIAssignID: | |||
2668 | K->mergeDIAssignID(J); | |||
2669 | break; | |||
2670 | case LLVMContext::MD_tbaa: | |||
2671 | K->setMetadata(Kind, MDNode::getMostGenericTBAA(JMD, KMD)); | |||
2672 | break; | |||
2673 | case LLVMContext::MD_alias_scope: | |||
2674 | K->setMetadata(Kind, MDNode::getMostGenericAliasScope(JMD, KMD)); | |||
2675 | break; | |||
2676 | case LLVMContext::MD_noalias: | |||
2677 | case LLVMContext::MD_mem_parallel_loop_access: | |||
2678 | K->setMetadata(Kind, MDNode::intersect(JMD, KMD)); | |||
2679 | break; | |||
2680 | case LLVMContext::MD_access_group: | |||
2681 | K->setMetadata(LLVMContext::MD_access_group, | |||
2682 | intersectAccessGroups(K, J)); | |||
2683 | break; | |||
2684 | case LLVMContext::MD_range: | |||
2685 | ||||
2686 | // If K does move, use most generic range. Otherwise keep the range of | |||
2687 | // K. | |||
2688 | if (DoesKMove) | |||
2689 | // FIXME: If K does move, we should drop the range info and nonnull. | |||
2690 | // Currently this function is used with DoesKMove in passes | |||
2691 | // doing hoisting/sinking and the current behavior of using the | |||
2692 | // most generic range is correct in those cases. | |||
2693 | K->setMetadata(Kind, MDNode::getMostGenericRange(JMD, KMD)); | |||
2694 | break; | |||
2695 | case LLVMContext::MD_fpmath: | |||
2696 | K->setMetadata(Kind, MDNode::getMostGenericFPMath(JMD, KMD)); | |||
2697 | break; | |||
2698 | case LLVMContext::MD_invariant_load: | |||
2699 | // Only set the !invariant.load if it is present in both instructions. | |||
2700 | K->setMetadata(Kind, JMD); | |||
2701 | break; | |||
2702 | case LLVMContext::MD_nonnull: | |||
2703 | // If K does move, keep nonull if it is present in both instructions. | |||
2704 | if (DoesKMove) | |||
2705 | K->setMetadata(Kind, JMD); | |||
2706 | break; | |||
2707 | case LLVMContext::MD_invariant_group: | |||
2708 | // Preserve !invariant.group in K. | |||
2709 | break; | |||
2710 | case LLVMContext::MD_align: | |||
2711 | K->setMetadata(Kind, | |||
2712 | MDNode::getMostGenericAlignmentOrDereferenceable(JMD, KMD)); | |||
2713 | break; | |||
2714 | case LLVMContext::MD_dereferenceable: | |||
2715 | case LLVMContext::MD_dereferenceable_or_null: | |||
2716 | K->setMetadata(Kind, | |||
2717 | MDNode::getMostGenericAlignmentOrDereferenceable(JMD, KMD)); | |||
2718 | break; | |||
2719 | case LLVMContext::MD_preserve_access_index: | |||
2720 | // Preserve !preserve.access.index in K. | |||
2721 | break; | |||
2722 | case LLVMContext::MD_noundef: | |||
2723 | // If K does move, keep noundef if it is present in both instructions. | |||
2724 | if (DoesKMove) | |||
2725 | K->setMetadata(Kind, JMD); | |||
2726 | break; | |||
2727 | case LLVMContext::MD_nontemporal: | |||
2728 | // Preserve !nontemporal if it is present on both instructions. | |||
2729 | K->setMetadata(Kind, JMD); | |||
2730 | break; | |||
2731 | } | |||
2732 | } | |||
2733 | // Set !invariant.group from J if J has it. If both instructions have it | |||
2734 | // then we will just pick it from J - even when they are different. | |||
2735 | // Also make sure that K is load or store - f.e. combining bitcast with load | |||
2736 | // could produce bitcast with invariant.group metadata, which is invalid. | |||
2737 | // FIXME: we should try to preserve both invariant.group md if they are | |||
2738 | // different, but right now instruction can only have one invariant.group. | |||
2739 | if (auto *JMD = J->getMetadata(LLVMContext::MD_invariant_group)) | |||
2740 | if (isa<LoadInst>(K) || isa<StoreInst>(K)) | |||
2741 | K->setMetadata(LLVMContext::MD_invariant_group, JMD); | |||
2742 | } | |||
2743 | ||||
2744 | void llvm::combineMetadataForCSE(Instruction *K, const Instruction *J, | |||
2745 | bool KDominatesJ) { | |||
2746 | unsigned KnownIDs[] = { | |||
2747 | LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope, | |||
2748 | LLVMContext::MD_noalias, LLVMContext::MD_range, | |||
2749 | LLVMContext::MD_invariant_load, LLVMContext::MD_nonnull, | |||
2750 | LLVMContext::MD_invariant_group, LLVMContext::MD_align, | |||
2751 | LLVMContext::MD_dereferenceable, | |||
2752 | LLVMContext::MD_dereferenceable_or_null, | |||
2753 | LLVMContext::MD_access_group, LLVMContext::MD_preserve_access_index, | |||
2754 | LLVMContext::MD_nontemporal, LLVMContext::MD_noundef}; | |||
2755 | combineMetadata(K, J, KnownIDs, KDominatesJ); | |||
2756 | } | |||
2757 | ||||
2758 | void llvm::copyMetadataForLoad(LoadInst &Dest, const LoadInst &Source) { | |||
2759 | SmallVector<std::pair<unsigned, MDNode *>, 8> MD; | |||
2760 | Source.getAllMetadata(MD); | |||
2761 | MDBuilder MDB(Dest.getContext()); | |||
2762 | Type *NewType = Dest.getType(); | |||
2763 | const DataLayout &DL = Source.getModule()->getDataLayout(); | |||
2764 | for (const auto &MDPair : MD) { | |||
2765 | unsigned ID = MDPair.first; | |||
2766 | MDNode *N = MDPair.second; | |||
2767 | // Note, essentially every kind of metadata should be preserved here! This | |||
2768 | // routine is supposed to clone a load instruction changing *only its type*. | |||
2769 | // The only metadata it makes sense to drop is metadata which is invalidated | |||
2770 | // when the pointer type changes. This should essentially never be the case | |||
2771 | // in LLVM, but we explicitly switch over only known metadata to be | |||
2772 | // conservatively correct. If you are adding metadata to LLVM which pertains | |||
2773 | // to loads, you almost certainly want to add it here. | |||
2774 | switch (ID) { | |||
2775 | case LLVMContext::MD_dbg: | |||
2776 | case LLVMContext::MD_tbaa: | |||
2777 | case LLVMContext::MD_prof: | |||
2778 | case LLVMContext::MD_fpmath: | |||
2779 | case LLVMContext::MD_tbaa_struct: | |||
2780 | case LLVMContext::MD_invariant_load: | |||
2781 | case LLVMContext::MD_alias_scope: | |||
2782 | case LLVMContext::MD_noalias: | |||
2783 | case LLVMContext::MD_nontemporal: | |||
2784 | case LLVMContext::MD_mem_parallel_loop_access: | |||
2785 | case LLVMContext::MD_access_group: | |||
2786 | case LLVMContext::MD_noundef: | |||
2787 | // All of these directly apply. | |||
2788 | Dest.setMetadata(ID, N); | |||
2789 | break; | |||
2790 | ||||
2791 | case LLVMContext::MD_nonnull: | |||
2792 | copyNonnullMetadata(Source, N, Dest); | |||
2793 | break; | |||
2794 | ||||
2795 | case LLVMContext::MD_align: | |||
2796 | case LLVMContext::MD_dereferenceable: | |||
2797 | case LLVMContext::MD_dereferenceable_or_null: | |||
2798 | // These only directly apply if the new type is also a pointer. | |||
2799 | if (NewType->isPointerTy()) | |||
2800 | Dest.setMetadata(ID, N); | |||
2801 | break; | |||
2802 | ||||
2803 | case LLVMContext::MD_range: | |||
2804 | copyRangeMetadata(DL, Source, N, Dest); | |||
2805 | break; | |||
2806 | } | |||
2807 | } | |||
2808 | } | |||
2809 | ||||
2810 | void llvm::patchReplacementInstruction(Instruction *I, Value *Repl) { | |||
2811 | auto *ReplInst = dyn_cast<Instruction>(Repl); | |||
2812 | if (!ReplInst) | |||
2813 | return; | |||
2814 | ||||
2815 | // Patch the replacement so that it is not more restrictive than the value | |||
2816 | // being replaced. | |||
2817 | // Note that if 'I' is a load being replaced by some operation, | |||
2818 | // for example, by an arithmetic operation, then andIRFlags() | |||
2819 | // would just erase all math flags from the original arithmetic | |||
2820 | // operation, which is clearly not wanted and not needed. | |||
2821 | if (!isa<LoadInst>(I)) | |||
2822 | ReplInst->andIRFlags(I); | |||
2823 | ||||
2824 | // FIXME: If both the original and replacement value are part of the | |||
2825 | // same control-flow region (meaning that the execution of one | |||
2826 | // guarantees the execution of the other), then we can combine the | |||
2827 | // noalias scopes here and do better than the general conservative | |||
2828 | // answer used in combineMetadata(). | |||
2829 | ||||
2830 | // In general, GVN unifies expressions over different control-flow | |||
2831 | // regions, and so we need a conservative combination of the noalias | |||
2832 | // scopes. | |||
2833 | static const unsigned KnownIDs[] = { | |||
2834 | LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope, | |||
2835 | LLVMContext::MD_noalias, LLVMContext::MD_range, | |||
2836 | LLVMContext::MD_fpmath, LLVMContext::MD_invariant_load, | |||
2837 | LLVMContext::MD_invariant_group, LLVMContext::MD_nonnull, | |||
2838 | LLVMContext::MD_access_group, LLVMContext::MD_preserve_access_index, | |||
2839 | LLVMContext::MD_noundef, LLVMContext::MD_nontemporal}; | |||
2840 | combineMetadata(ReplInst, I, KnownIDs, false); | |||
2841 | } | |||
2842 | ||||
2843 | template <typename RootType, typename DominatesFn> | |||
2844 | static unsigned replaceDominatedUsesWith(Value *From, Value *To, | |||
2845 | const RootType &Root, | |||
2846 | const DominatesFn &Dominates) { | |||
2847 | assert(From->getType() == To->getType())(static_cast <bool> (From->getType() == To->getType ()) ? void (0) : __assert_fail ("From->getType() == To->getType()" , "llvm/lib/Transforms/Utils/Local.cpp", 2847, __extension__ __PRETTY_FUNCTION__ )); | |||
2848 | ||||
2849 | unsigned Count = 0; | |||
2850 | for (Use &U : llvm::make_early_inc_range(From->uses())) { | |||
2851 | if (!Dominates(Root, U)) | |||
2852 | continue; | |||
2853 | U.set(To); | |||
2854 | LLVM_DEBUG(dbgs() << "Replace dominated use of '" << From->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("local")) { dbgs() << "Replace dominated use of '" << From->getName() << "' as " << *To << " in " << *U << "\n"; } } while (false) | |||
2855 | << "' as " << *To << " in " << *U << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("local")) { dbgs() << "Replace dominated use of '" << From->getName() << "' as " << *To << " in " << *U << "\n"; } } while (false); | |||
2856 | ++Count; | |||
2857 | } | |||
2858 | return Count; | |||
2859 | } | |||
2860 | ||||
2861 | unsigned llvm::replaceNonLocalUsesWith(Instruction *From, Value *To) { | |||
2862 | assert(From->getType() == To->getType())(static_cast <bool> (From->getType() == To->getType ()) ? void (0) : __assert_fail ("From->getType() == To->getType()" , "llvm/lib/Transforms/Utils/Local.cpp", 2862, __extension__ __PRETTY_FUNCTION__ )); | |||
2863 | auto *BB = From->getParent(); | |||
2864 | unsigned Count = 0; | |||
2865 | ||||
2866 | for (Use &U : llvm::make_early_inc_range(From->uses())) { | |||
2867 | auto *I = cast<Instruction>(U.getUser()); | |||
2868 | if (I->getParent() == BB) | |||
2869 | continue; | |||
2870 | U.set(To); | |||
2871 | ++Count; | |||
2872 | } | |||
2873 | return Count; | |||
2874 | } | |||
2875 | ||||
2876 | unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To, | |||
2877 | DominatorTree &DT, | |||
2878 | const BasicBlockEdge &Root) { | |||
2879 | auto Dominates = [&DT](const BasicBlockEdge &Root, const Use &U) { | |||
2880 | return DT.dominates(Root, U); | |||
2881 | }; | |||
2882 | return ::replaceDominatedUsesWith(From, To, Root, Dominates); | |||
2883 | } | |||
2884 | ||||
2885 | unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To, | |||
2886 | DominatorTree &DT, | |||
2887 | const BasicBlock *BB) { | |||
2888 | auto Dominates = [&DT](const BasicBlock *BB, const Use &U) { | |||
2889 | return DT.dominates(BB, U); | |||
2890 | }; | |||
2891 | return ::replaceDominatedUsesWith(From, To, BB, Dominates); | |||
2892 | } | |||
2893 | ||||
2894 | bool llvm::callsGCLeafFunction(const CallBase *Call, | |||
2895 | const TargetLibraryInfo &TLI) { | |||
2896 | // Check if the function is specifically marked as a gc leaf function. | |||
2897 | if (Call->hasFnAttr("gc-leaf-function")) | |||
2898 | return true; | |||
2899 | if (const Function *F = Call->getCalledFunction()) { | |||
2900 | if (F->hasFnAttribute("gc-leaf-function")) | |||
2901 | return true; | |||
2902 | ||||
2903 | if (auto IID = F->getIntrinsicID()) { | |||
2904 | // Most LLVM intrinsics do not take safepoints. | |||
2905 | return IID != Intrinsic::experimental_gc_statepoint && | |||
2906 | IID != Intrinsic::experimental_deoptimize && | |||
2907 | IID != Intrinsic::memcpy_element_unordered_atomic && | |||
2908 | IID != Intrinsic::memmove_element_unordered_atomic; | |||
2909 | } | |||
2910 | } | |||
2911 | ||||
2912 | // Lib calls can be materialized by some passes, and won't be | |||
2913 | // marked as 'gc-leaf-function.' All available Libcalls are | |||
2914 | // GC-leaf. | |||
2915 | LibFunc LF; | |||
2916 | if (TLI.getLibFunc(*Call, LF)) { | |||
2917 | return TLI.has(LF); | |||
2918 | } | |||
2919 | ||||
2920 | return false; | |||
2921 | } | |||
2922 | ||||
2923 | void llvm::copyNonnullMetadata(const LoadInst &OldLI, MDNode *N, | |||
2924 | LoadInst &NewLI) { | |||
2925 | auto *NewTy = NewLI.getType(); | |||
2926 | ||||
2927 | // This only directly applies if the new type is also a pointer. | |||
2928 | if (NewTy->isPointerTy()) { | |||
2929 | NewLI.setMetadata(LLVMContext::MD_nonnull, N); | |||
2930 | return; | |||
2931 | } | |||
2932 | ||||
2933 | // The only other translation we can do is to integral loads with !range | |||
2934 | // metadata. | |||
2935 | if (!NewTy->isIntegerTy()) | |||
2936 | return; | |||
2937 | ||||
2938 | MDBuilder MDB(NewLI.getContext()); | |||
2939 | const Value *Ptr = OldLI.getPointerOperand(); | |||
2940 | auto *ITy = cast<IntegerType>(NewTy); | |||
2941 | auto *NullInt = ConstantExpr::getPtrToInt( | |||
2942 | ConstantPointerNull::get(cast<PointerType>(Ptr->getType())), ITy); | |||
2943 | auto *NonNullInt = ConstantExpr::getAdd(NullInt, ConstantInt::get(ITy, 1)); | |||
2944 | NewLI.setMetadata(LLVMContext::MD_range, | |||
2945 | MDB.createRange(NonNullInt, NullInt)); | |||
2946 | } | |||
2947 | ||||
2948 | void llvm::copyRangeMetadata(const DataLayout &DL, const LoadInst &OldLI, | |||
2949 | MDNode *N, LoadInst &NewLI) { | |||
2950 | auto *NewTy = NewLI.getType(); | |||
2951 | // Simply copy the metadata if the type did not change. | |||
2952 | if (NewTy == OldLI.getType()) { | |||
2953 | NewLI.setMetadata(LLVMContext::MD_range, N); | |||
2954 | return; | |||
2955 | } | |||
2956 | ||||
2957 | // Give up unless it is converted to a pointer where there is a single very | |||
2958 | // valuable mapping we can do reliably. | |||
2959 | // FIXME: It would be nice to propagate this in more ways, but the type | |||
2960 | // conversions make it hard. | |||
2961 | if (!NewTy->isPointerTy()) | |||
2962 | return; | |||
2963 | ||||
2964 | unsigned BitWidth = DL.getPointerTypeSizeInBits(NewTy); | |||
2965 | if (!getConstantRangeFromMetadata(*N).contains(APInt(BitWidth, 0))) { | |||
2966 | MDNode *NN = MDNode::get(OldLI.getContext(), std::nullopt); | |||
2967 | NewLI.setMetadata(LLVMContext::MD_nonnull, NN); | |||
2968 | } | |||
2969 | } | |||
2970 | ||||
2971 | void llvm::dropDebugUsers(Instruction &I) { | |||
2972 | SmallVector<DbgVariableIntrinsic *, 1> DbgUsers; | |||
2973 | findDbgUsers(DbgUsers, &I); | |||
2974 | for (auto *DII : DbgUsers) | |||
2975 | DII->eraseFromParent(); | |||
2976 | } | |||
2977 | ||||
2978 | void llvm::hoistAllInstructionsInto(BasicBlock *DomBlock, Instruction *InsertPt, | |||
2979 | BasicBlock *BB) { | |||
2980 | // Since we are moving the instructions out of its basic block, we do not | |||
2981 | // retain their original debug locations (DILocations) and debug intrinsic | |||
2982 | // instructions. | |||
2983 | // | |||
2984 | // Doing so would degrade the debugging experience and adversely affect the | |||
2985 | // accuracy of profiling information. | |||
2986 | // | |||
2987 | // Currently, when hoisting the instructions, we take the following actions: | |||
2988 | // - Remove their debug intrinsic instructions. | |||
2989 | // - Set their debug locations to the values from the insertion point. | |||
2990 | // | |||
2991 | // As per PR39141 (comment #8), the more fundamental reason why the dbg.values | |||
2992 | // need to be deleted, is because there will not be any instructions with a | |||
2993 | // DILocation in either branch left after performing the transformation. We | |||
2994 | // can only insert a dbg.value after the two branches are joined again. | |||
2995 | // | |||
2996 | // See PR38762, PR39243 for more details. | |||
2997 | // | |||
2998 | // TODO: Extend llvm.dbg.value to take more than one SSA Value (PR39141) to | |||
2999 | // encode predicated DIExpressions that yield different results on different | |||
3000 | // code paths. | |||
3001 | ||||
3002 | for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); II != IE;) { | |||
3003 | Instruction *I = &*II; | |||
3004 | I->dropUndefImplyingAttrsAndUnknownMetadata(); | |||
3005 | if (I->isUsedByMetadata()) | |||
3006 | dropDebugUsers(*I); | |||
3007 | if (I->isDebugOrPseudoInst()) { | |||
3008 | // Remove DbgInfo and pseudo probe Intrinsics. | |||
3009 | II = I->eraseFromParent(); | |||
3010 | continue; | |||
3011 | } | |||
3012 | I->setDebugLoc(InsertPt->getDebugLoc()); | |||
3013 | ++II; | |||
3014 | } | |||
3015 | DomBlock->splice(InsertPt->getIterator(), BB, BB->begin(), | |||
3016 | BB->getTerminator()->getIterator()); | |||
3017 | } | |||
3018 | ||||
3019 | namespace { | |||
3020 | ||||
3021 | /// A potential constituent of a bitreverse or bswap expression. See | |||
3022 | /// collectBitParts for a fuller explanation. | |||
3023 | struct BitPart { | |||
3024 | BitPart(Value *P, unsigned BW) : Provider(P) { | |||
3025 | Provenance.resize(BW); | |||
3026 | } | |||
3027 | ||||
3028 | /// The Value that this is a bitreverse/bswap of. | |||
3029 | Value *Provider; | |||
3030 | ||||
3031 | /// The "provenance" of each bit. Provenance[A] = B means that bit A | |||
3032 | /// in Provider becomes bit B in the result of this expression. | |||
3033 | SmallVector<int8_t, 32> Provenance; // int8_t means max size is i128. | |||
3034 | ||||
3035 | enum { Unset = -1 }; | |||
3036 | }; | |||
3037 | ||||
3038 | } // end anonymous namespace | |||
3039 | ||||
3040 | /// Analyze the specified subexpression and see if it is capable of providing | |||
3041 | /// pieces of a bswap or bitreverse. The subexpression provides a potential | |||
3042 | /// piece of a bswap or bitreverse if it can be proved that each non-zero bit in | |||
3043 | /// the output of the expression came from a corresponding bit in some other | |||
3044 | /// value. This function is recursive, and the end result is a mapping of | |||
3045 | /// bitnumber to bitnumber. It is the caller's responsibility to validate that | |||
3046 | /// the bitnumber to bitnumber mapping is correct for a bswap or bitreverse. | |||
3047 | /// | |||
3048 | /// For example, if the current subexpression if "(shl i32 %X, 24)" then we know | |||
3049 | /// that the expression deposits the low byte of %X into the high byte of the | |||
3050 | /// result and that all other bits are zero. This expression is accepted and a | |||
3051 | /// BitPart is returned with Provider set to %X and Provenance[24-31] set to | |||
3052 | /// [0-7]. | |||
3053 | /// | |||
3054 | /// For vector types, all analysis is performed at the per-element level. No | |||
3055 | /// cross-element analysis is supported (shuffle/insertion/reduction), and all | |||
3056 | /// constant masks must be splatted across all elements. | |||
3057 | /// | |||
3058 | /// To avoid revisiting values, the BitPart results are memoized into the | |||
3059 | /// provided map. To avoid unnecessary copying of BitParts, BitParts are | |||
3060 | /// constructed in-place in the \c BPS map. Because of this \c BPS needs to | |||
3061 | /// store BitParts objects, not pointers. As we need the concept of a nullptr | |||
3062 | /// BitParts (Value has been analyzed and the analysis failed), we an Optional | |||
3063 | /// type instead to provide the same functionality. | |||
3064 | /// | |||
3065 | /// Because we pass around references into \c BPS, we must use a container that | |||
3066 | /// does not invalidate internal references (std::map instead of DenseMap). | |||
3067 | static const std::optional<BitPart> & | |||
3068 | collectBitParts(Value *V, bool MatchBSwaps, bool MatchBitReversals, | |||
3069 | std::map<Value *, std::optional<BitPart>> &BPS, int Depth, | |||
3070 | bool &FoundRoot) { | |||
3071 | auto I = BPS.find(V); | |||
3072 | if (I != BPS.end()) | |||
3073 | return I->second; | |||
3074 | ||||
3075 | auto &Result = BPS[V] = std::nullopt; | |||
3076 | auto BitWidth = V->getType()->getScalarSizeInBits(); | |||
3077 | ||||
3078 | // Can't do integer/elements > 128 bits. | |||
3079 | if (BitWidth > 128) | |||
3080 | return Result; | |||
3081 | ||||
3082 | // Prevent stack overflow by limiting the recursion depth | |||
3083 | if (Depth == BitPartRecursionMaxDepth) { | |||
3084 | LLVM_DEBUG(dbgs() << "collectBitParts max recursion depth reached.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("local")) { dbgs() << "collectBitParts max recursion depth reached.\n" ; } } while (false); | |||
3085 | return Result; | |||
3086 | } | |||
3087 | ||||
3088 | if (auto *I = dyn_cast<Instruction>(V)) { | |||
3089 | Value *X, *Y; | |||
3090 | const APInt *C; | |||
3091 | ||||
3092 | // If this is an or instruction, it may be an inner node of the bswap. | |||
3093 | if (match(V, m_Or(m_Value(X), m_Value(Y)))) { | |||
3094 | // Check we have both sources and they are from the same provider. | |||
3095 | const auto &A = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS, | |||
3096 | Depth + 1, FoundRoot); | |||
3097 | if (!A || !A->Provider) | |||
3098 | return Result; | |||
3099 | ||||
3100 | const auto &B = collectBitParts(Y, MatchBSwaps, MatchBitReversals, BPS, | |||
3101 | Depth + 1, FoundRoot); | |||
3102 | if (!B || A->Provider != B->Provider) | |||
3103 | return Result; | |||
3104 | ||||
3105 | // Try and merge the two together. | |||
3106 | Result = BitPart(A->Provider, BitWidth); | |||
3107 | for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx) { | |||
3108 | if (A->Provenance[BitIdx] != BitPart::Unset && | |||
3109 | B->Provenance[BitIdx] != BitPart::Unset && | |||
3110 | A->Provenance[BitIdx] != B->Provenance[BitIdx]) | |||
3111 | return Result = std::nullopt; | |||
3112 | ||||
3113 | if (A->Provenance[BitIdx] == BitPart::Unset) | |||
3114 | Result->Provenance[BitIdx] = B->Provenance[BitIdx]; | |||
3115 | else | |||
3116 | Result->Provenance[BitIdx] = A->Provenance[BitIdx]; | |||
3117 | } | |||
3118 | ||||
3119 | return Result; | |||
3120 | } | |||
3121 | ||||
3122 | // If this is a logical shift by a constant, recurse then shift the result. | |||
3123 | if (match(V, m_LogicalShift(m_Value(X), m_APInt(C)))) { | |||
3124 | const APInt &BitShift = *C; | |||
3125 | ||||
3126 | // Ensure the shift amount is defined. | |||
3127 | if (BitShift.uge(BitWidth)) | |||
3128 | return Result; | |||
3129 | ||||
3130 | // For bswap-only, limit shift amounts to whole bytes, for an early exit. | |||
3131 | if (!MatchBitReversals && (BitShift.getZExtValue() % 8) != 0) | |||
3132 | return Result; | |||
3133 | ||||
3134 | const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS, | |||
3135 | Depth + 1, FoundRoot); | |||
3136 | if (!Res) | |||
3137 | return Result; | |||
3138 | Result = Res; | |||
3139 | ||||
3140 | // Perform the "shift" on BitProvenance. | |||
3141 | auto &P = Result->Provenance; | |||
3142 | if (I->getOpcode() == Instruction::Shl) { | |||
3143 | P.erase(std::prev(P.end(), BitShift.getZExtValue()), P.end()); | |||
3144 | P.insert(P.begin(), BitShift.getZExtValue(), BitPart::Unset); | |||
3145 | } else { | |||
3146 | P.erase(P.begin(), std::next(P.begin(), BitShift.getZExtValue())); | |||
3147 | P.insert(P.end(), BitShift.getZExtValue(), BitPart::Unset); | |||
3148 | } | |||
3149 | ||||
3150 | return Result; | |||
3151 | } | |||
3152 | ||||
3153 | // If this is a logical 'and' with a mask that clears bits, recurse then | |||
3154 | // unset the appropriate bits. | |||
3155 | if (match(V, m_And(m_Value(X), m_APInt(C)))) { | |||
3156 | const APInt &AndMask = *C; | |||
3157 | ||||
3158 | // Check that the mask allows a multiple of 8 bits for a bswap, for an | |||
3159 | // early exit. | |||
3160 | unsigned NumMaskedBits = AndMask.popcount(); | |||
3161 | if (!MatchBitReversals && (NumMaskedBits % 8) != 0) | |||
3162 | return Result; | |||
3163 | ||||
3164 | const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS, | |||
3165 | Depth + 1, FoundRoot); | |||
3166 | if (!Res) | |||
3167 | return Result; | |||
3168 | Result = Res; | |||
3169 | ||||
3170 | for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx) | |||
3171 | // If the AndMask is zero for this bit, clear the bit. | |||
3172 | if (AndMask[BitIdx] == 0) | |||
3173 | Result->Provenance[BitIdx] = BitPart::Unset; | |||
3174 | return Result; | |||
3175 | } | |||
3176 | ||||
3177 | // If this is a zext instruction zero extend the result. | |||
3178 | if (match(V, m_ZExt(m_Value(X)))) { | |||
3179 | const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS, | |||
3180 | Depth + 1, FoundRoot); | |||
3181 | if (!Res) | |||
3182 | return Result; | |||
3183 | ||||
3184 | Result = BitPart(Res->Provider, BitWidth); | |||
3185 | auto NarrowBitWidth = X->getType()->getScalarSizeInBits(); | |||
3186 | for (unsigned BitIdx = 0; BitIdx < NarrowBitWidth; ++BitIdx) | |||
3187 | Result->Provenance[BitIdx] = Res->Provenance[BitIdx]; | |||
3188 | for (unsigned BitIdx = NarrowBitWidth; BitIdx < BitWidth; ++BitIdx) | |||
3189 | Result->Provenance[BitIdx] = BitPart::Unset; | |||
3190 | return Result; | |||
3191 | } | |||
3192 | ||||
3193 | // If this is a truncate instruction, extract the lower bits. | |||
3194 | if (match(V, m_Trunc(m_Value(X)))) { | |||
3195 | const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS, | |||
3196 | Depth + 1, FoundRoot); | |||
3197 | if (!Res) | |||
3198 | return Result; | |||
3199 | ||||
3200 | Result = BitPart(Res->Provider, BitWidth); | |||
3201 | for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx) | |||
3202 | Result->Provenance[BitIdx] = Res->Provenance[BitIdx]; | |||
3203 | return Result; | |||
3204 | } | |||
3205 | ||||
3206 | // BITREVERSE - most likely due to us previous matching a partial | |||
3207 | // bitreverse. | |||
3208 | if (match(V, m_BitReverse(m_Value(X)))) { | |||
3209 | const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS, | |||
3210 | Depth + 1, FoundRoot); | |||
3211 | if (!Res) | |||
3212 | return Result; | |||
3213 | ||||
3214 | Result = BitPart(Res->Provider, BitWidth); | |||
3215 | for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx) | |||
3216 | Result->Provenance[(BitWidth - 1) - BitIdx] = Res->Provenance[BitIdx]; | |||
3217 | return Result; | |||
3218 | } | |||
3219 | ||||
3220 | // BSWAP - most likely due to us previous matching a partial bswap. | |||
3221 | if (match(V, m_BSwap(m_Value(X)))) { | |||
3222 | const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS, | |||
3223 | Depth + 1, FoundRoot); | |||
3224 | if (!Res) | |||
3225 | return Result; | |||
3226 | ||||
3227 | unsigned ByteWidth = BitWidth / 8; | |||
3228 | Result = BitPart(Res->Provider, BitWidth); | |||
3229 | for (unsigned ByteIdx = 0; ByteIdx < ByteWidth; ++ByteIdx) { | |||
3230 | unsigned ByteBitOfs = ByteIdx * 8; | |||
3231 | for (unsigned BitIdx = 0; BitIdx < 8; ++BitIdx) | |||
3232 | Result->Provenance[(BitWidth - 8 - ByteBitOfs) + BitIdx] = | |||
3233 | Res->Provenance[ByteBitOfs + BitIdx]; | |||
3234 | } | |||
3235 | return Result; | |||
3236 | } | |||
3237 | ||||
3238 | // Funnel 'double' shifts take 3 operands, 2 inputs and the shift | |||
3239 | // amount (modulo). | |||
3240 | // fshl(X,Y,Z): (X << (Z % BW)) | (Y >> (BW - (Z % BW))) | |||
3241 | // fshr(X,Y,Z): (X << (BW - (Z % BW))) | (Y >> (Z % BW)) | |||
3242 | if (match(V, m_FShl(m_Value(X), m_Value(Y), m_APInt(C))) || | |||
3243 | match(V, m_FShr(m_Value(X), m_Value(Y), m_APInt(C)))) { | |||
3244 | // We can treat fshr as a fshl by flipping the modulo amount. | |||
3245 | unsigned ModAmt = C->urem(BitWidth); | |||
3246 | if (cast<IntrinsicInst>(I)->getIntrinsicID() == Intrinsic::fshr) | |||
3247 | ModAmt = BitWidth - ModAmt; | |||
3248 | ||||
3249 | // For bswap-only, limit shift amounts to whole bytes, for an early exit. | |||
3250 | if (!MatchBitReversals && (ModAmt % 8) != 0) | |||
3251 | return Result; | |||
3252 | ||||
3253 | // Check we have both sources and they are from the same provider. | |||
3254 | const auto &LHS = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS, | |||
3255 | Depth + 1, FoundRoot); | |||
3256 | if (!LHS || !LHS->Provider) | |||
3257 | return Result; | |||
3258 | ||||
3259 | const auto &RHS = collectBitParts(Y, MatchBSwaps, MatchBitReversals, BPS, | |||
3260 | Depth + 1, FoundRoot); | |||
3261 | if (!RHS || LHS->Provider != RHS->Provider) | |||
3262 | return Result; | |||
3263 | ||||
3264 | unsigned StartBitRHS = BitWidth - ModAmt; | |||
3265 | Result = BitPart(LHS->Provider, BitWidth); | |||
3266 | for (unsigned BitIdx = 0; BitIdx < StartBitRHS; ++BitIdx) | |||
3267 | Result->Provenance[BitIdx + ModAmt] = LHS->Provenance[BitIdx]; | |||
3268 | for (unsigned BitIdx = 0; BitIdx < ModAmt; ++BitIdx) | |||
3269 | Result->Provenance[BitIdx] = RHS->Provenance[BitIdx + StartBitRHS]; | |||
3270 | return Result; | |||
3271 | } | |||
3272 | } | |||
3273 | ||||
3274 | // If we've already found a root input value then we're never going to merge | |||
3275 | // these back together. | |||
3276 | if (FoundRoot) | |||
3277 | return Result; | |||
3278 | ||||
3279 | // Okay, we got to something that isn't a shift, 'or', 'and', etc. This must | |||
3280 | // be the root input value to the bswap/bitreverse. | |||
3281 | FoundRoot = true; | |||
3282 | Result = BitPart(V, BitWidth); | |||
3283 | for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx) | |||
3284 | Result->Provenance[BitIdx] = BitIdx; | |||
3285 | return Result; | |||
3286 | } | |||
3287 | ||||
3288 | static bool bitTransformIsCorrectForBSwap(unsigned From, unsigned To, | |||
3289 | unsigned BitWidth) { | |||
3290 | if (From % 8 != To % 8) | |||
3291 | return false; | |||
3292 | // Convert from bit indices to byte indices and check for a byte reversal. | |||
3293 | From >>= 3; | |||
3294 | To >>= 3; | |||
3295 | BitWidth >>= 3; | |||
3296 | return From == BitWidth - To - 1; | |||
3297 | } | |||
3298 | ||||
3299 | static bool bitTransformIsCorrectForBitReverse(unsigned From, unsigned To, | |||
3300 | unsigned BitWidth) { | |||
3301 | return From == BitWidth - To - 1; | |||
3302 | } | |||
3303 | ||||
3304 | bool llvm::recognizeBSwapOrBitReverseIdiom( | |||
3305 | Instruction *I, bool MatchBSwaps, bool MatchBitReversals, | |||
3306 | SmallVectorImpl<Instruction *> &InsertedInsts) { | |||
3307 | if (!match(I, m_Or(m_Value(), m_Value())) && | |||
3308 | !match(I, m_FShl(m_Value(), m_Value(), m_Value())) && | |||
3309 | !match(I, m_FShr(m_Value(), m_Value(), m_Value()))) | |||
3310 | return false; | |||
3311 | if (!MatchBSwaps && !MatchBitReversals) | |||
3312 | return false; | |||
3313 | Type *ITy = I->getType(); | |||
3314 | if (!ITy->isIntOrIntVectorTy() || ITy->getScalarSizeInBits() > 128) | |||
3315 | return false; // Can't do integer/elements > 128 bits. | |||
3316 | ||||
3317 | // Try to find all the pieces corresponding to the bswap. | |||
3318 | bool FoundRoot = false; | |||
3319 | std::map<Value *, std::optional<BitPart>> BPS; | |||
3320 | const auto &Res = | |||
3321 | collectBitParts(I, MatchBSwaps, MatchBitReversals, BPS, 0, FoundRoot); | |||
3322 | if (!Res) | |||
3323 | return false; | |||
3324 | ArrayRef<int8_t> BitProvenance = Res->Provenance; | |||
3325 | assert(all_of(BitProvenance,(static_cast <bool> (all_of(BitProvenance, [](int8_t I) { return I == BitPart::Unset || 0 <= I; }) && "Illegal bit provenance index" ) ? void (0) : __assert_fail ("all_of(BitProvenance, [](int8_t I) { return I == BitPart::Unset || 0 <= I; }) && \"Illegal bit provenance index\"" , "llvm/lib/Transforms/Utils/Local.cpp", 3327, __extension__ __PRETTY_FUNCTION__ )) | |||
3326 | [](int8_t I) { return I == BitPart::Unset || 0 <= I; }) &&(static_cast <bool> (all_of(BitProvenance, [](int8_t I) { return I == BitPart::Unset || 0 <= I; }) && "Illegal bit provenance index" ) ? void (0) : __assert_fail ("all_of(BitProvenance, [](int8_t I) { return I == BitPart::Unset || 0 <= I; }) && \"Illegal bit provenance index\"" , "llvm/lib/Transforms/Utils/Local.cpp", 3327, __extension__ __PRETTY_FUNCTION__ )) | |||
3327 | "Illegal bit provenance index")(static_cast <bool> (all_of(BitProvenance, [](int8_t I) { return I == BitPart::Unset || 0 <= I; }) && "Illegal bit provenance index" ) ? void (0) : __assert_fail ("all_of(BitProvenance, [](int8_t I) { return I == BitPart::Unset || 0 <= I; }) && \"Illegal bit provenance index\"" , "llvm/lib/Transforms/Utils/Local.cpp", 3327, __extension__ __PRETTY_FUNCTION__ )); | |||
3328 | ||||
3329 | // If the upper bits are zero, then attempt to perform as a truncated op. | |||
3330 | Type *DemandedTy = ITy; | |||
3331 | if (BitProvenance.back() == BitPart::Unset) { | |||
3332 | while (!BitProvenance.empty() && BitProvenance.back() == BitPart::Unset) | |||
3333 | BitProvenance = BitProvenance.drop_back(); | |||
3334 | if (BitProvenance.empty()) | |||
3335 | return false; // TODO - handle null value? | |||
3336 | DemandedTy = Type::getIntNTy(I->getContext(), BitProvenance.size()); | |||
3337 | if (auto *IVecTy = dyn_cast<VectorType>(ITy)) | |||
3338 | DemandedTy = VectorType::get(DemandedTy, IVecTy); | |||
3339 | } | |||
3340 | ||||
3341 | // Check BitProvenance hasn't found a source larger than the result type. | |||
3342 | unsigned DemandedBW = DemandedTy->getScalarSizeInBits(); | |||
3343 | if (DemandedBW > ITy->getScalarSizeInBits()) | |||
3344 | return false; | |||
3345 | ||||
3346 | // Now, is the bit permutation correct for a bswap or a bitreverse? We can | |||
3347 | // only byteswap values with an even number of bytes. | |||
3348 | APInt DemandedMask = APInt::getAllOnes(DemandedBW); | |||
3349 | bool OKForBSwap = MatchBSwaps && (DemandedBW % 16) == 0; | |||
3350 | bool OKForBitReverse = MatchBitReversals; | |||
3351 | for (unsigned BitIdx = 0; | |||
3352 | (BitIdx < DemandedBW) && (OKForBSwap || OKForBitReverse); ++BitIdx) { | |||
3353 | if (BitProvenance[BitIdx] == BitPart::Unset) { | |||
3354 | DemandedMask.clearBit(BitIdx); | |||
3355 | continue; | |||
3356 | } | |||
3357 | OKForBSwap &= bitTransformIsCorrectForBSwap(BitProvenance[BitIdx], BitIdx, | |||
3358 | DemandedBW); | |||
3359 | OKForBitReverse &= bitTransformIsCorrectForBitReverse(BitProvenance[BitIdx], | |||
3360 | BitIdx, DemandedBW); | |||
3361 | } | |||
3362 | ||||
3363 | Intrinsic::ID Intrin; | |||
3364 | if (OKForBSwap) | |||
3365 | Intrin = Intrinsic::bswap; | |||
3366 | else if (OKForBitReverse) | |||
3367 | Intrin = Intrinsic::bitreverse; | |||
3368 | else | |||
3369 | return false; | |||
3370 | ||||
3371 | Function *F = Intrinsic::getDeclaration(I->getModule(), Intrin, DemandedTy); | |||
3372 | Value *Provider = Res->Provider; | |||
3373 | ||||
3374 | // We may need to truncate the provider. | |||
3375 | if (DemandedTy != Provider->getType()) { | |||
3376 | auto *Trunc = | |||
3377 | CastInst::CreateIntegerCast(Provider, DemandedTy, false, "trunc", I); | |||
3378 | InsertedInsts.push_back(Trunc); | |||
3379 | Provider = Trunc; | |||
3380 | } | |||
3381 | ||||
3382 | Instruction *Result = CallInst::Create(F, Provider, "rev", I); | |||
3383 | InsertedInsts.push_back(Result); | |||
3384 | ||||
3385 | if (!DemandedMask.isAllOnes()) { | |||
3386 | auto *Mask = ConstantInt::get(DemandedTy, DemandedMask); | |||
3387 | Result = BinaryOperator::Create(Instruction::And, Result, Mask, "mask", I); | |||
3388 | InsertedInsts.push_back(Result); | |||
3389 | } | |||
3390 | ||||
3391 | // We may need to zeroextend back to the result type. | |||
3392 | if (ITy != Result->getType()) { | |||
3393 | auto *ExtInst = CastInst::CreateIntegerCast(Result, ITy, false, "zext", I); | |||
3394 | InsertedInsts.push_back(ExtInst); | |||
3395 | } | |||
3396 | ||||
3397 | return true; | |||
3398 | } | |||
3399 | ||||
3400 | // CodeGen has special handling for some string functions that may replace | |||
3401 | // them with target-specific intrinsics. Since that'd skip our interceptors | |||
3402 | // in ASan/MSan/TSan/DFSan, and thus make us miss some memory accesses, | |||
3403 | // we mark affected calls as NoBuiltin, which will disable optimization | |||
3404 | // in CodeGen. | |||
3405 | void llvm::maybeMarkSanitizerLibraryCallNoBuiltin( | |||
3406 | CallInst *CI, const TargetLibraryInfo *TLI) { | |||
3407 | Function *F = CI->getCalledFunction(); | |||
3408 | LibFunc Func; | |||
3409 | if (F && !F->hasLocalLinkage() && F->hasName() && | |||
3410 | TLI->getLibFunc(F->getName(), Func) && TLI->hasOptimizedCodeGen(Func) && | |||
3411 | !F->doesNotAccessMemory()) | |||
3412 | CI->addFnAttr(Attribute::NoBuiltin); | |||
3413 | } | |||
3414 | ||||
3415 | bool llvm::canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx) { | |||
3416 | // We can't have a PHI with a metadata type. | |||
3417 | if (I->getOperand(OpIdx)->getType()->isMetadataTy()) | |||
3418 | return false; | |||
3419 | ||||
3420 | // Early exit. | |||
3421 | if (!isa<Constant>(I->getOperand(OpIdx))) | |||
3422 | return true; | |||
3423 | ||||
3424 | switch (I->getOpcode()) { | |||
3425 | default: | |||
3426 | return true; | |||
3427 | case Instruction::Call: | |||
3428 | case Instruction::Invoke: { | |||
3429 | const auto &CB = cast<CallBase>(*I); | |||
3430 | ||||
3431 | // Can't handle inline asm. Skip it. | |||
3432 | if (CB.isInlineAsm()) | |||
3433 | return false; | |||
3434 | ||||
3435 | // Constant bundle operands may need to retain their constant-ness for | |||
3436 | // correctness. | |||
3437 | if (CB.isBundleOperand(OpIdx)) | |||
3438 | return false; | |||
3439 | ||||
3440 | if (OpIdx < CB.arg_size()) { | |||
3441 | // Some variadic intrinsics require constants in the variadic arguments, | |||
3442 | // which currently aren't markable as immarg. | |||
3443 | if (isa<IntrinsicInst>(CB) && | |||
3444 | OpIdx >= CB.getFunctionType()->getNumParams()) { | |||
3445 | // This is known to be OK for stackmap. | |||
3446 | return CB.getIntrinsicID() == Intrinsic::experimental_stackmap; | |||
3447 | } | |||
3448 | ||||
3449 | // gcroot is a special case, since it requires a constant argument which | |||
3450 | // isn't also required to be a simple ConstantInt. | |||
3451 | if (CB.getIntrinsicID() == Intrinsic::gcroot) | |||
3452 | return false; | |||
3453 | ||||
3454 | // Some intrinsic operands are required to be immediates. | |||
3455 | return !CB.paramHasAttr(OpIdx, Attribute::ImmArg); | |||
3456 | } | |||
3457 | ||||
3458 | // It is never allowed to replace the call argument to an intrinsic, but it | |||
3459 | // may be possible for a call. | |||
3460 | return !isa<IntrinsicInst>(CB); | |||
3461 | } | |||
3462 | case Instruction::ShuffleVector: | |||
3463 | // Shufflevector masks are constant. | |||
3464 | return OpIdx != 2; | |||
3465 | case Instruction::Switch: | |||
3466 | case Instruction::ExtractValue: | |||
3467 | // All operands apart from the first are constant. | |||
3468 | return OpIdx == 0; | |||
3469 | case Instruction::InsertValue: | |||
3470 | // All operands apart from the first and the second are constant. | |||
3471 | return OpIdx < 2; | |||
3472 | case Instruction::Alloca: | |||
3473 | // Static allocas (constant size in the entry block) are handled by | |||
3474 | // prologue/epilogue insertion so they're free anyway. We definitely don't | |||
3475 | // want to make them non-constant. | |||
3476 | return !cast<AllocaInst>(I)->isStaticAlloca(); | |||
3477 | case Instruction::GetElementPtr: | |||
3478 | if (OpIdx == 0) | |||
3479 | return true; | |||
3480 | gep_type_iterator It = gep_type_begin(I); | |||
3481 | for (auto E = std::next(It, OpIdx); It != E; ++It) | |||
3482 | if (It.isStruct()) | |||
3483 | return false; | |||
3484 | return true; | |||
3485 | } | |||
3486 | } | |||
3487 | ||||
3488 | Value *llvm::invertCondition(Value *Condition) { | |||
3489 | // First: Check if it's a constant | |||
3490 | if (Constant *C = dyn_cast<Constant>(Condition)) | |||
3491 | return ConstantExpr::getNot(C); | |||
3492 | ||||
3493 | // Second: If the condition is already inverted, return the original value | |||
3494 | Value *NotCondition; | |||
3495 | if (match(Condition, m_Not(m_Value(NotCondition)))) | |||
3496 | return NotCondition; | |||
3497 | ||||
3498 | BasicBlock *Parent = nullptr; | |||
3499 | Instruction *Inst = dyn_cast<Instruction>(Condition); | |||
3500 | if (Inst) | |||
3501 | Parent = Inst->getParent(); | |||
3502 | else if (Argument *Arg = dyn_cast<Argument>(Condition)) | |||
3503 | Parent = &Arg->getParent()->getEntryBlock(); | |||
3504 | assert(Parent && "Unsupported condition to invert")(static_cast <bool> (Parent && "Unsupported condition to invert" ) ? void (0) : __assert_fail ("Parent && \"Unsupported condition to invert\"" , "llvm/lib/Transforms/Utils/Local.cpp", 3504, __extension__ __PRETTY_FUNCTION__ )); | |||
3505 | ||||
3506 | // Third: Check all the users for an invert | |||
3507 | for (User *U : Condition->users()) | |||
3508 | if (Instruction *I = dyn_cast<Instruction>(U)) | |||
3509 | if (I->getParent() == Parent && match(I, m_Not(m_Specific(Condition)))) | |||
3510 | return I; | |||
3511 | ||||
3512 | // Last option: Create a new instruction | |||
3513 | auto *Inverted = | |||
3514 | BinaryOperator::CreateNot(Condition, Condition->getName() + ".inv"); | |||
3515 | if (Inst && !isa<PHINode>(Inst)) | |||
3516 | Inverted->insertAfter(Inst); | |||
3517 | else | |||
3518 | Inverted->insertBefore(&*Parent->getFirstInsertionPt()); | |||
3519 | return Inverted; | |||
3520 | } | |||
3521 | ||||
3522 | bool llvm::inferAttributesFromOthers(Function &F) { | |||
3523 | // Note: We explicitly check for attributes rather than using cover functions | |||
3524 | // because some of the cover functions include the logic being implemented. | |||
3525 | ||||
3526 | bool Changed = false; | |||
3527 | // readnone + not convergent implies nosync | |||
3528 | if (!F.hasFnAttribute(Attribute::NoSync) && | |||
3529 | F.doesNotAccessMemory() && !F.isConvergent()) { | |||
3530 | F.setNoSync(); | |||
3531 | Changed = true; | |||
3532 | } | |||
3533 | ||||
3534 | // readonly implies nofree | |||
3535 | if (!F.hasFnAttribute(Attribute::NoFree) && F.onlyReadsMemory()) { | |||
3536 | F.setDoesNotFreeMemory(); | |||
3537 | Changed = true; | |||
3538 | } | |||
3539 | ||||
3540 | // willreturn implies mustprogress | |||
3541 | if (!F.hasFnAttribute(Attribute::MustProgress) && F.willReturn()) { | |||
3542 | F.setMustProgress(); | |||
3543 | Changed = true; | |||
3544 | } | |||
3545 | ||||
3546 | // TODO: There are a bunch of cases of restrictive memory effects we | |||
3547 | // can infer by inspecting arguments of argmemonly-ish functions. | |||
3548 | ||||
3549 | return Changed; | |||
3550 | } |