Bug Summary

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

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple amd64-unknown-openbsd7.0 -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name Local.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 1 -fhalf-no-semantic-interposition -mframe-pointer=all -relaxed-aliasing -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/usr/src/gnu/usr.bin/clang/libLLVM/obj -resource-dir /usr/local/lib/clang/13.0.0 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Analysis -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ASMParser -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/BinaryFormat -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Bitcode -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Bitcode -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Bitstream -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /include/llvm/CodeGen -I /include/llvm/CodeGen/PBQP -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/IR -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/IR -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Coroutines -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ProfileData/Coverage -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/CodeView -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/DWARF -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/MSF -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/PDB -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Demangle -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ExecutionEngine -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ExecutionEngine/JITLink -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ExecutionEngine/Orc -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend/OpenACC -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend/OpenMP -I /include/llvm/CodeGen/GlobalISel -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/IRReader -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/InstCombine -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/Transforms/InstCombine -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/LTO -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Linker -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/MC -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/MC/MCParser -I /include/llvm/CodeGen/MIRParser -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Object -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Option -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Passes -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ProfileData -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Scalar -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ADT -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Support -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/Symbolize -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Target -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Utils -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Vectorize -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/IPO -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include -I /usr/src/gnu/usr.bin/clang/libLLVM/../include -I /usr/src/gnu/usr.bin/clang/libLLVM/obj -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include -D NDEBUG -D __STDC_LIMIT_MACROS -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D LLVM_PREFIX="/usr" -D PIC -internal-isystem /usr/include/c++/v1 -internal-isystem /usr/local/lib/clang/13.0.0/include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/usr/src/gnu/usr.bin/clang/libLLVM/obj -ferror-limit 19 -fvisibility-inlines-hidden -fwrapv -D_RET_PROTECTOR -ret-protector -fno-rtti -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -fno-builtin-malloc -fno-builtin-calloc -fno-builtin-realloc -fno-builtin-valloc -fno-builtin-free -fno-builtin-strdup -fno-builtin-strndup -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /home/ben/Projects/vmm/scan-build/2022-01-12-194120-40624-1 -x c++ /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Transforms/Utils/Local.cpp

/usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Transforms/Utils/Local.cpp

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

/usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/IR/PatternMatch.h

1//===- PatternMatch.h - Match on the LLVM IR --------------------*- C++ -*-===//
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 file provides a simple and efficient mechanism for performing general
10// tree-based pattern matches on the LLVM IR. The power of these routines is
11// that it allows you to write concise patterns that are expressive and easy to
12// understand. The other major advantage of this is that it allows you to
13// trivially capture/bind elements in the pattern to variables. For example,
14// you can do something like this:
15//
16// Value *Exp = ...
17// Value *X, *Y; ConstantInt *C1, *C2; // (X & C1) | (Y & C2)
18// if (match(Exp, m_Or(m_And(m_Value(X), m_ConstantInt(C1)),
19// m_And(m_Value(Y), m_ConstantInt(C2))))) {
20// ... Pattern is matched and variables are bound ...
21// }
22//
23// This is primarily useful to things like the instruction combiner, but can
24// also be useful for static analysis tools or code generators.
25//
26//===----------------------------------------------------------------------===//
27
28#ifndef LLVM_IR_PATTERNMATCH_H
29#define LLVM_IR_PATTERNMATCH_H
30
31#include "llvm/ADT/APFloat.h"
32#include "llvm/ADT/APInt.h"
33#include "llvm/IR/Constant.h"
34#include "llvm/IR/Constants.h"
35#include "llvm/IR/DataLayout.h"
36#include "llvm/IR/InstrTypes.h"
37#include "llvm/IR/Instruction.h"
38#include "llvm/IR/Instructions.h"
39#include "llvm/IR/IntrinsicInst.h"
40#include "llvm/IR/Intrinsics.h"
41#include "llvm/IR/Operator.h"
42#include "llvm/IR/Value.h"
43#include "llvm/Support/Casting.h"
44#include <cstdint>
45
46namespace llvm {
47namespace PatternMatch {
48
49template <typename Val, typename Pattern> bool match(Val *V, const Pattern &P) {
50 return const_cast<Pattern &>(P).match(V);
4
Calling 'BinaryOp_match::match'
10
Returning from 'BinaryOp_match::match'
11
Returning zero, which participates in a condition later
51}
52
53template <typename Pattern> bool match(ArrayRef<int> Mask, const Pattern &P) {
54 return const_cast<Pattern &>(P).match(Mask);
55}
56
57template <typename SubPattern_t> struct OneUse_match {
58 SubPattern_t SubPattern;
59
60 OneUse_match(const SubPattern_t &SP) : SubPattern(SP) {}
61
62 template <typename OpTy> bool match(OpTy *V) {
63 return V->hasOneUse() && SubPattern.match(V);
64 }
65};
66
67template <typename T> inline OneUse_match<T> m_OneUse(const T &SubPattern) {
68 return SubPattern;
69}
70
71template <typename Class> struct class_match {
72 template <typename ITy> bool match(ITy *V) { return isa<Class>(V); }
73};
74
75/// Match an arbitrary value and ignore it.
76inline class_match<Value> m_Value() { return class_match<Value>(); }
77
78/// Match an arbitrary unary operation and ignore it.
79inline class_match<UnaryOperator> m_UnOp() {
80 return class_match<UnaryOperator>();
81}
82
83/// Match an arbitrary binary operation and ignore it.
84inline class_match<BinaryOperator> m_BinOp() {
85 return class_match<BinaryOperator>();
86}
87
88/// Matches any compare instruction and ignore it.
89inline class_match<CmpInst> m_Cmp() { return class_match<CmpInst>(); }
90
91struct undef_match {
92 static bool check(const Value *V) {
93 if (isa<UndefValue>(V))
94 return true;
95
96 const auto *CA = dyn_cast<ConstantAggregate>(V);
97 if (!CA)
98 return false;
99
100 SmallPtrSet<const ConstantAggregate *, 8> Seen;
101 SmallVector<const ConstantAggregate *, 8> Worklist;
102
103 // Either UndefValue, PoisonValue, or an aggregate that only contains
104 // these is accepted by matcher.
105 // CheckValue returns false if CA cannot satisfy this constraint.
106 auto CheckValue = [&](const ConstantAggregate *CA) {
107 for (const Value *Op : CA->operand_values()) {
108 if (isa<UndefValue>(Op))
109 continue;
110
111 const auto *CA = dyn_cast<ConstantAggregate>(Op);
112 if (!CA)
113 return false;
114 if (Seen.insert(CA).second)
115 Worklist.emplace_back(CA);
116 }
117
118 return true;
119 };
120
121 if (!CheckValue(CA))
122 return false;
123
124 while (!Worklist.empty()) {
125 if (!CheckValue(Worklist.pop_back_val()))
126 return false;
127 }
128 return true;
129 }
130 template <typename ITy> bool match(ITy *V) { return check(V); }
131};
132
133/// Match an arbitrary undef constant. This matches poison as well.
134/// If this is an aggregate and contains a non-aggregate element that is
135/// neither undef nor poison, the aggregate is not matched.
136inline auto m_Undef() { return undef_match(); }
137
138/// Match an arbitrary poison constant.
139inline class_match<PoisonValue> m_Poison() { return class_match<PoisonValue>(); }
140
141/// Match an arbitrary Constant and ignore it.
142inline class_match<Constant> m_Constant() { return class_match<Constant>(); }
143
144/// Match an arbitrary ConstantInt and ignore it.
145inline class_match<ConstantInt> m_ConstantInt() {
146 return class_match<ConstantInt>();
147}
148
149/// Match an arbitrary ConstantFP and ignore it.
150inline class_match<ConstantFP> m_ConstantFP() {
151 return class_match<ConstantFP>();
152}
153
154/// Match an arbitrary ConstantExpr and ignore it.
155inline class_match<ConstantExpr> m_ConstantExpr() {
156 return class_match<ConstantExpr>();
157}
158
159/// Match an arbitrary basic block value and ignore it.
160inline class_match<BasicBlock> m_BasicBlock() {
161 return class_match<BasicBlock>();
162}
163
164/// Inverting matcher
165template <typename Ty> struct match_unless {
166 Ty M;
167
168 match_unless(const Ty &Matcher) : M(Matcher) {}
169
170 template <typename ITy> bool match(ITy *V) { return !M.match(V); }
171};
172
173/// Match if the inner matcher does *NOT* match.
174template <typename Ty> inline match_unless<Ty> m_Unless(const Ty &M) {
175 return match_unless<Ty>(M);
176}
177
178/// Matching combinators
179template <typename LTy, typename RTy> struct match_combine_or {
180 LTy L;
181 RTy R;
182
183 match_combine_or(const LTy &Left, const RTy &Right) : L(Left), R(Right) {}
184
185 template <typename ITy> bool match(ITy *V) {
186 if (L.match(V))
187 return true;
188 if (R.match(V))
189 return true;
190 return false;
191 }
192};
193
194template <typename LTy, typename RTy> struct match_combine_and {
195 LTy L;
196 RTy R;
197
198 match_combine_and(const LTy &Left, const RTy &Right) : L(Left), R(Right) {}
199
200 template <typename ITy> bool match(ITy *V) {
201 if (L.match(V))
202 if (R.match(V))
203 return true;
204 return false;
205 }
206};
207
208/// Combine two pattern matchers matching L || R
209template <typename LTy, typename RTy>
210inline match_combine_or<LTy, RTy> m_CombineOr(const LTy &L, const RTy &R) {
211 return match_combine_or<LTy, RTy>(L, R);
212}
213
214/// Combine two pattern matchers matching L && R
215template <typename LTy, typename RTy>
216inline match_combine_and<LTy, RTy> m_CombineAnd(const LTy &L, const RTy &R) {
217 return match_combine_and<LTy, RTy>(L, R);
218}
219
220struct apint_match {
221 const APInt *&Res;
222 bool AllowUndef;
223
224 apint_match(const APInt *&Res, bool AllowUndef)
225 : Res(Res), AllowUndef(AllowUndef) {}
226
227 template <typename ITy> bool match(ITy *V) {
228 if (auto *CI = dyn_cast<ConstantInt>(V)) {
229 Res = &CI->getValue();
230 return true;
231 }
232 if (V->getType()->isVectorTy())
233 if (const auto *C = dyn_cast<Constant>(V))
234 if (auto *CI = dyn_cast_or_null<ConstantInt>(
235 C->getSplatValue(AllowUndef))) {
236 Res = &CI->getValue();
237 return true;
238 }
239 return false;
240 }
241};
242// Either constexpr if or renaming ConstantFP::getValueAPF to
243// ConstantFP::getValue is needed to do it via single template
244// function for both apint/apfloat.
245struct apfloat_match {
246 const APFloat *&Res;
247 bool AllowUndef;
248
249 apfloat_match(const APFloat *&Res, bool AllowUndef)
250 : Res(Res), AllowUndef(AllowUndef) {}
251
252 template <typename ITy> bool match(ITy *V) {
253 if (auto *CI = dyn_cast<ConstantFP>(V)) {
254 Res = &CI->getValueAPF();
255 return true;
256 }
257 if (V->getType()->isVectorTy())
258 if (const auto *C = dyn_cast<Constant>(V))
259 if (auto *CI = dyn_cast_or_null<ConstantFP>(
260 C->getSplatValue(AllowUndef))) {
261 Res = &CI->getValueAPF();
262 return true;
263 }
264 return false;
265 }
266};
267
268/// Match a ConstantInt or splatted ConstantVector, binding the
269/// specified pointer to the contained APInt.
270inline apint_match m_APInt(const APInt *&Res) {
271 // Forbid undefs by default to maintain previous behavior.
272 return apint_match(Res, /* AllowUndef */ false);
273}
274
275/// Match APInt while allowing undefs in splat vector constants.
276inline apint_match m_APIntAllowUndef(const APInt *&Res) {
277 return apint_match(Res, /* AllowUndef */ true);
278}
279
280/// Match APInt while forbidding undefs in splat vector constants.
281inline apint_match m_APIntForbidUndef(const APInt *&Res) {
282 return apint_match(Res, /* AllowUndef */ false);
283}
284
285/// Match a ConstantFP or splatted ConstantVector, binding the
286/// specified pointer to the contained APFloat.
287inline apfloat_match m_APFloat(const APFloat *&Res) {
288 // Forbid undefs by default to maintain previous behavior.
289 return apfloat_match(Res, /* AllowUndef */ false);
290}
291
292/// Match APFloat while allowing undefs in splat vector constants.
293inline apfloat_match m_APFloatAllowUndef(const APFloat *&Res) {
294 return apfloat_match(Res, /* AllowUndef */ true);
295}
296
297/// Match APFloat while forbidding undefs in splat vector constants.
298inline apfloat_match m_APFloatForbidUndef(const APFloat *&Res) {
299 return apfloat_match(Res, /* AllowUndef */ false);
300}
301
302template <int64_t Val> struct constantint_match {
303 template <typename ITy> bool match(ITy *V) {
304 if (const auto *CI = dyn_cast<ConstantInt>(V)) {
305 const APInt &CIV = CI->getValue();
306 if (Val >= 0)
307 return CIV == static_cast<uint64_t>(Val);
308 // If Val is negative, and CI is shorter than it, truncate to the right
309 // number of bits. If it is larger, then we have to sign extend. Just
310 // compare their negated values.
311 return -CIV == -Val;
312 }
313 return false;
314 }
315};
316
317/// Match a ConstantInt with a specific value.
318template <int64_t Val> inline constantint_match<Val> m_ConstantInt() {
319 return constantint_match<Val>();
320}
321
322/// This helper class is used to match constant scalars, vector splats,
323/// and fixed width vectors that satisfy a specified predicate.
324/// For fixed width vector constants, undefined elements are ignored.
325template <typename Predicate, typename ConstantVal>
326struct cstval_pred_ty : public Predicate {
327 template <typename ITy> bool match(ITy *V) {
328 if (const auto *CV = dyn_cast<ConstantVal>(V))
329 return this->isValue(CV->getValue());
330 if (const auto *VTy = dyn_cast<VectorType>(V->getType())) {
331 if (const auto *C = dyn_cast<Constant>(V)) {
332 if (const auto *CV = dyn_cast_or_null<ConstantVal>(C->getSplatValue()))
333 return this->isValue(CV->getValue());
334
335 // Number of elements of a scalable vector unknown at compile time
336 auto *FVTy = dyn_cast<FixedVectorType>(VTy);
337 if (!FVTy)
338 return false;
339
340 // Non-splat vector constant: check each element for a match.
341 unsigned NumElts = FVTy->getNumElements();
342 assert(NumElts != 0 && "Constant vector with no elements?")((void)0);
343 bool HasNonUndefElements = false;
344 for (unsigned i = 0; i != NumElts; ++i) {
345 Constant *Elt = C->getAggregateElement(i);
346 if (!Elt)
347 return false;
348 if (isa<UndefValue>(Elt))
349 continue;
350 auto *CV = dyn_cast<ConstantVal>(Elt);
351 if (!CV || !this->isValue(CV->getValue()))
352 return false;
353 HasNonUndefElements = true;
354 }
355 return HasNonUndefElements;
356 }
357 }
358 return false;
359 }
360};
361
362/// specialization of cstval_pred_ty for ConstantInt
363template <typename Predicate>
364using cst_pred_ty = cstval_pred_ty<Predicate, ConstantInt>;
365
366/// specialization of cstval_pred_ty for ConstantFP
367template <typename Predicate>
368using cstfp_pred_ty = cstval_pred_ty<Predicate, ConstantFP>;
369
370/// This helper class is used to match scalar and vector constants that
371/// satisfy a specified predicate, and bind them to an APInt.
372template <typename Predicate> struct api_pred_ty : public Predicate {
373 const APInt *&Res;
374
375 api_pred_ty(const APInt *&R) : Res(R) {}
376
377 template <typename ITy> bool match(ITy *V) {
378 if (const auto *CI = dyn_cast<ConstantInt>(V))
379 if (this->isValue(CI->getValue())) {
380 Res = &CI->getValue();
381 return true;
382 }
383 if (V->getType()->isVectorTy())
384 if (const auto *C = dyn_cast<Constant>(V))
385 if (auto *CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue()))
386 if (this->isValue(CI->getValue())) {
387 Res = &CI->getValue();
388 return true;
389 }
390
391 return false;
392 }
393};
394
395/// This helper class is used to match scalar and vector constants that
396/// satisfy a specified predicate, and bind them to an APFloat.
397/// Undefs are allowed in splat vector constants.
398template <typename Predicate> struct apf_pred_ty : public Predicate {
399 const APFloat *&Res;
400
401 apf_pred_ty(const APFloat *&R) : Res(R) {}
402
403 template <typename ITy> bool match(ITy *V) {
404 if (const auto *CI = dyn_cast<ConstantFP>(V))
405 if (this->isValue(CI->getValue())) {
406 Res = &CI->getValue();
407 return true;
408 }
409 if (V->getType()->isVectorTy())
410 if (const auto *C = dyn_cast<Constant>(V))
411 if (auto *CI = dyn_cast_or_null<ConstantFP>(
412 C->getSplatValue(/* AllowUndef */ true)))
413 if (this->isValue(CI->getValue())) {
414 Res = &CI->getValue();
415 return true;
416 }
417
418 return false;
419 }
420};
421
422///////////////////////////////////////////////////////////////////////////////
423//
424// Encapsulate constant value queries for use in templated predicate matchers.
425// This allows checking if constants match using compound predicates and works
426// with vector constants, possibly with relaxed constraints. For example, ignore
427// undef values.
428//
429///////////////////////////////////////////////////////////////////////////////
430
431struct is_any_apint {
432 bool isValue(const APInt &C) { return true; }
433};
434/// Match an integer or vector with any integral constant.
435/// For vectors, this includes constants with undefined elements.
436inline cst_pred_ty<is_any_apint> m_AnyIntegralConstant() {
437 return cst_pred_ty<is_any_apint>();
438}
439
440struct is_all_ones {
441 bool isValue(const APInt &C) { return C.isAllOnesValue(); }
442};
443/// Match an integer or vector with all bits set.
444/// For vectors, this includes constants with undefined elements.
445inline cst_pred_ty<is_all_ones> m_AllOnes() {
446 return cst_pred_ty<is_all_ones>();
447}
448
449struct is_maxsignedvalue {
450 bool isValue(const APInt &C) { return C.isMaxSignedValue(); }
451};
452/// Match an integer or vector with values having all bits except for the high
453/// bit set (0x7f...).
454/// For vectors, this includes constants with undefined elements.
455inline cst_pred_ty<is_maxsignedvalue> m_MaxSignedValue() {
456 return cst_pred_ty<is_maxsignedvalue>();
457}
458inline api_pred_ty<is_maxsignedvalue> m_MaxSignedValue(const APInt *&V) {
459 return V;
460}
461
462struct is_negative {
463 bool isValue(const APInt &C) { return C.isNegative(); }
464};
465/// Match an integer or vector of negative values.
466/// For vectors, this includes constants with undefined elements.
467inline cst_pred_ty<is_negative> m_Negative() {
468 return cst_pred_ty<is_negative>();
469}
470inline api_pred_ty<is_negative> m_Negative(const APInt *&V) {
471 return V;
472}
473
474struct is_nonnegative {
475 bool isValue(const APInt &C) { return C.isNonNegative(); }
476};
477/// Match an integer or vector of non-negative values.
478/// For vectors, this includes constants with undefined elements.
479inline cst_pred_ty<is_nonnegative> m_NonNegative() {
480 return cst_pred_ty<is_nonnegative>();
481}
482inline api_pred_ty<is_nonnegative> m_NonNegative(const APInt *&V) {
483 return V;
484}
485
486struct is_strictlypositive {
487 bool isValue(const APInt &C) { return C.isStrictlyPositive(); }
488};
489/// Match an integer or vector of strictly positive values.
490/// For vectors, this includes constants with undefined elements.
491inline cst_pred_ty<is_strictlypositive> m_StrictlyPositive() {
492 return cst_pred_ty<is_strictlypositive>();
493}
494inline api_pred_ty<is_strictlypositive> m_StrictlyPositive(const APInt *&V) {
495 return V;
496}
497
498struct is_nonpositive {
499 bool isValue(const APInt &C) { return C.isNonPositive(); }
500};
501/// Match an integer or vector of non-positive values.
502/// For vectors, this includes constants with undefined elements.
503inline cst_pred_ty<is_nonpositive> m_NonPositive() {
504 return cst_pred_ty<is_nonpositive>();
505}
506inline api_pred_ty<is_nonpositive> m_NonPositive(const APInt *&V) { return V; }
507
508struct is_one {
509 bool isValue(const APInt &C) { return C.isOneValue(); }
510};
511/// Match an integer 1 or a vector with all elements equal to 1.
512/// For vectors, this includes constants with undefined elements.
513inline cst_pred_ty<is_one> m_One() {
514 return cst_pred_ty<is_one>();
515}
516
517struct is_zero_int {
518 bool isValue(const APInt &C) { return C.isNullValue(); }
519};
520/// Match an integer 0 or a vector with all elements equal to 0.
521/// For vectors, this includes constants with undefined elements.
522inline cst_pred_ty<is_zero_int> m_ZeroInt() {
523 return cst_pred_ty<is_zero_int>();
524}
525
526struct is_zero {
527 template <typename ITy> bool match(ITy *V) {
528 auto *C = dyn_cast<Constant>(V);
529 // FIXME: this should be able to do something for scalable vectors
530 return C && (C->isNullValue() || cst_pred_ty<is_zero_int>().match(C));
531 }
532};
533/// Match any null constant or a vector with all elements equal to 0.
534/// For vectors, this includes constants with undefined elements.
535inline is_zero m_Zero() {
536 return is_zero();
537}
538
539struct is_power2 {
540 bool isValue(const APInt &C) { return C.isPowerOf2(); }
541};
542/// Match an integer or vector power-of-2.
543/// For vectors, this includes constants with undefined elements.
544inline cst_pred_ty<is_power2> m_Power2() {
545 return cst_pred_ty<is_power2>();
546}
547inline api_pred_ty<is_power2> m_Power2(const APInt *&V) {
548 return V;
549}
550
551struct is_negated_power2 {
552 bool isValue(const APInt &C) { return (-C).isPowerOf2(); }
553};
554/// Match a integer or vector negated power-of-2.
555/// For vectors, this includes constants with undefined elements.
556inline cst_pred_ty<is_negated_power2> m_NegatedPower2() {
557 return cst_pred_ty<is_negated_power2>();
558}
559inline api_pred_ty<is_negated_power2> m_NegatedPower2(const APInt *&V) {
560 return V;
561}
562
563struct is_power2_or_zero {
564 bool isValue(const APInt &C) { return !C || C.isPowerOf2(); }
565};
566/// Match an integer or vector of 0 or power-of-2 values.
567/// For vectors, this includes constants with undefined elements.
568inline cst_pred_ty<is_power2_or_zero> m_Power2OrZero() {
569 return cst_pred_ty<is_power2_or_zero>();
570}
571inline api_pred_ty<is_power2_or_zero> m_Power2OrZero(const APInt *&V) {
572 return V;
573}
574
575struct is_sign_mask {
576 bool isValue(const APInt &C) { return C.isSignMask(); }
577};
578/// Match an integer or vector with only the sign bit(s) set.
579/// For vectors, this includes constants with undefined elements.
580inline cst_pred_ty<is_sign_mask> m_SignMask() {
581 return cst_pred_ty<is_sign_mask>();
582}
583
584struct is_lowbit_mask {
585 bool isValue(const APInt &C) { return C.isMask(); }
586};
587/// Match an integer or vector with only the low bit(s) set.
588/// For vectors, this includes constants with undefined elements.
589inline cst_pred_ty<is_lowbit_mask> m_LowBitMask() {
590 return cst_pred_ty<is_lowbit_mask>();
591}
592
593struct icmp_pred_with_threshold {
594 ICmpInst::Predicate Pred;
595 const APInt *Thr;
596 bool isValue(const APInt &C) {
597 switch (Pred) {
598 case ICmpInst::Predicate::ICMP_EQ:
599 return C.eq(*Thr);
600 case ICmpInst::Predicate::ICMP_NE:
601 return C.ne(*Thr);
602 case ICmpInst::Predicate::ICMP_UGT:
603 return C.ugt(*Thr);
604 case ICmpInst::Predicate::ICMP_UGE:
605 return C.uge(*Thr);
606 case ICmpInst::Predicate::ICMP_ULT:
607 return C.ult(*Thr);
608 case ICmpInst::Predicate::ICMP_ULE:
609 return C.ule(*Thr);
610 case ICmpInst::Predicate::ICMP_SGT:
611 return C.sgt(*Thr);
612 case ICmpInst::Predicate::ICMP_SGE:
613 return C.sge(*Thr);
614 case ICmpInst::Predicate::ICMP_SLT:
615 return C.slt(*Thr);
616 case ICmpInst::Predicate::ICMP_SLE:
617 return C.sle(*Thr);
618 default:
619 llvm_unreachable("Unhandled ICmp predicate")__builtin_unreachable();
620 }
621 }
622};
623/// Match an integer or vector with every element comparing 'pred' (eg/ne/...)
624/// to Threshold. For vectors, this includes constants with undefined elements.
625inline cst_pred_ty<icmp_pred_with_threshold>
626m_SpecificInt_ICMP(ICmpInst::Predicate Predicate, const APInt &Threshold) {
627 cst_pred_ty<icmp_pred_with_threshold> P;
628 P.Pred = Predicate;
629 P.Thr = &Threshold;
630 return P;
631}
632
633struct is_nan {
634 bool isValue(const APFloat &C) { return C.isNaN(); }
635};
636/// Match an arbitrary NaN constant. This includes quiet and signalling nans.
637/// For vectors, this includes constants with undefined elements.
638inline cstfp_pred_ty<is_nan> m_NaN() {
639 return cstfp_pred_ty<is_nan>();
640}
641
642struct is_nonnan {
643 bool isValue(const APFloat &C) { return !C.isNaN(); }
644};
645/// Match a non-NaN FP constant.
646/// For vectors, this includes constants with undefined elements.
647inline cstfp_pred_ty<is_nonnan> m_NonNaN() {
648 return cstfp_pred_ty<is_nonnan>();
649}
650
651struct is_inf {
652 bool isValue(const APFloat &C) { return C.isInfinity(); }
653};
654/// Match a positive or negative infinity FP constant.
655/// For vectors, this includes constants with undefined elements.
656inline cstfp_pred_ty<is_inf> m_Inf() {
657 return cstfp_pred_ty<is_inf>();
658}
659
660struct is_noninf {
661 bool isValue(const APFloat &C) { return !C.isInfinity(); }
662};
663/// Match a non-infinity FP constant, i.e. finite or NaN.
664/// For vectors, this includes constants with undefined elements.
665inline cstfp_pred_ty<is_noninf> m_NonInf() {
666 return cstfp_pred_ty<is_noninf>();
667}
668
669struct is_finite {
670 bool isValue(const APFloat &C) { return C.isFinite(); }
671};
672/// Match a finite FP constant, i.e. not infinity or NaN.
673/// For vectors, this includes constants with undefined elements.
674inline cstfp_pred_ty<is_finite> m_Finite() {
675 return cstfp_pred_ty<is_finite>();
676}
677inline apf_pred_ty<is_finite> m_Finite(const APFloat *&V) { return V; }
678
679struct is_finitenonzero {
680 bool isValue(const APFloat &C) { return C.isFiniteNonZero(); }
681};
682/// Match a finite non-zero FP constant.
683/// For vectors, this includes constants with undefined elements.
684inline cstfp_pred_ty<is_finitenonzero> m_FiniteNonZero() {
685 return cstfp_pred_ty<is_finitenonzero>();
686}
687inline apf_pred_ty<is_finitenonzero> m_FiniteNonZero(const APFloat *&V) {
688 return V;
689}
690
691struct is_any_zero_fp {
692 bool isValue(const APFloat &C) { return C.isZero(); }
693};
694/// Match a floating-point negative zero or positive zero.
695/// For vectors, this includes constants with undefined elements.
696inline cstfp_pred_ty<is_any_zero_fp> m_AnyZeroFP() {
697 return cstfp_pred_ty<is_any_zero_fp>();
698}
699
700struct is_pos_zero_fp {
701 bool isValue(const APFloat &C) { return C.isPosZero(); }
702};
703/// Match a floating-point positive zero.
704/// For vectors, this includes constants with undefined elements.
705inline cstfp_pred_ty<is_pos_zero_fp> m_PosZeroFP() {
706 return cstfp_pred_ty<is_pos_zero_fp>();
707}
708
709struct is_neg_zero_fp {
710 bool isValue(const APFloat &C) { return C.isNegZero(); }
711};
712/// Match a floating-point negative zero.
713/// For vectors, this includes constants with undefined elements.
714inline cstfp_pred_ty<is_neg_zero_fp> m_NegZeroFP() {
715 return cstfp_pred_ty<is_neg_zero_fp>();
716}
717
718struct is_non_zero_fp {
719 bool isValue(const APFloat &C) { return C.isNonZero(); }
720};
721/// Match a floating-point non-zero.
722/// For vectors, this includes constants with undefined elements.
723inline cstfp_pred_ty<is_non_zero_fp> m_NonZeroFP() {
724 return cstfp_pred_ty<is_non_zero_fp>();
725}
726
727///////////////////////////////////////////////////////////////////////////////
728
729template <typename Class> struct bind_ty {
730 Class *&VR;
731
732 bind_ty(Class *&V) : VR(V) {}
733
734 template <typename ITy> bool match(ITy *V) {
735 if (auto *CV = dyn_cast<Class>(V)) {
736 VR = CV;
737 return true;
738 }
739 return false;
740 }
741};
742
743/// Match a value, capturing it if we match.
744inline bind_ty<Value> m_Value(Value *&V) { return V; }
745inline bind_ty<const Value> m_Value(const Value *&V) { return V; }
746
747/// Match an instruction, capturing it if we match.
748inline bind_ty<Instruction> m_Instruction(Instruction *&I) { return I; }
749/// Match a unary operator, capturing it if we match.
750inline bind_ty<UnaryOperator> m_UnOp(UnaryOperator *&I) { return I; }
751/// Match a binary operator, capturing it if we match.
752inline bind_ty<BinaryOperator> m_BinOp(BinaryOperator *&I) { return I; }
753/// Match a with overflow intrinsic, capturing it if we match.
754inline bind_ty<WithOverflowInst> m_WithOverflowInst(WithOverflowInst *&I) { return I; }
755inline bind_ty<const WithOverflowInst>
756m_WithOverflowInst(const WithOverflowInst *&I) {
757 return I;
758}
759
760/// Match a Constant, capturing the value if we match.
761inline bind_ty<Constant> m_Constant(Constant *&C) { return C; }
762
763/// Match a ConstantInt, capturing the value if we match.
764inline bind_ty<ConstantInt> m_ConstantInt(ConstantInt *&CI) { return CI; }
765
766/// Match a ConstantFP, capturing the value if we match.
767inline bind_ty<ConstantFP> m_ConstantFP(ConstantFP *&C) { return C; }
768
769/// Match a ConstantExpr, capturing the value if we match.
770inline bind_ty<ConstantExpr> m_ConstantExpr(ConstantExpr *&C) { return C; }
771
772/// Match a basic block value, capturing it if we match.
773inline bind_ty<BasicBlock> m_BasicBlock(BasicBlock *&V) { return V; }
774inline bind_ty<const BasicBlock> m_BasicBlock(const BasicBlock *&V) {
775 return V;
776}
777
778/// Match an arbitrary immediate Constant and ignore it.
779inline match_combine_and<class_match<Constant>,
780 match_unless<class_match<ConstantExpr>>>
781m_ImmConstant() {
782 return m_CombineAnd(m_Constant(), m_Unless(m_ConstantExpr()));
783}
784
785/// Match an immediate Constant, capturing the value if we match.
786inline match_combine_and<bind_ty<Constant>,
787 match_unless<class_match<ConstantExpr>>>
788m_ImmConstant(Constant *&C) {
789 return m_CombineAnd(m_Constant(C), m_Unless(m_ConstantExpr()));
790}
791
792/// Match a specified Value*.
793struct specificval_ty {
794 const Value *Val;
795
796 specificval_ty(const Value *V) : Val(V) {}
797
798 template <typename ITy> bool match(ITy *V) { return V == Val; }
799};
800
801/// Match if we have a specific specified value.
802inline specificval_ty m_Specific(const Value *V) { return V; }
803
804/// Stores a reference to the Value *, not the Value * itself,
805/// thus can be used in commutative matchers.
806template <typename Class> struct deferredval_ty {
807 Class *const &Val;
808
809 deferredval_ty(Class *const &V) : Val(V) {}
810
811 template <typename ITy> bool match(ITy *const V) { return V == Val; }
812};
813
814/// Like m_Specific(), but works if the specific value to match is determined
815/// as part of the same match() expression. For example:
816/// m_Add(m_Value(X), m_Specific(X)) is incorrect, because m_Specific() will
817/// bind X before the pattern match starts.
818/// m_Add(m_Value(X), m_Deferred(X)) is correct, and will check against
819/// whichever value m_Value(X) populated.
820inline deferredval_ty<Value> m_Deferred(Value *const &V) { return V; }
821inline deferredval_ty<const Value> m_Deferred(const Value *const &V) {
822 return V;
823}
824
825/// Match a specified floating point value or vector of all elements of
826/// that value.
827struct specific_fpval {
828 double Val;
829
830 specific_fpval(double V) : Val(V) {}
831
832 template <typename ITy> bool match(ITy *V) {
833 if (const auto *CFP = dyn_cast<ConstantFP>(V))
834 return CFP->isExactlyValue(Val);
835 if (V->getType()->isVectorTy())
836 if (const auto *C = dyn_cast<Constant>(V))
837 if (auto *CFP = dyn_cast_or_null<ConstantFP>(C->getSplatValue()))
838 return CFP->isExactlyValue(Val);
839 return false;
840 }
841};
842
843/// Match a specific floating point value or vector with all elements
844/// equal to the value.
845inline specific_fpval m_SpecificFP(double V) { return specific_fpval(V); }
846
847/// Match a float 1.0 or vector with all elements equal to 1.0.
848inline specific_fpval m_FPOne() { return m_SpecificFP(1.0); }
849
850struct bind_const_intval_ty {
851 uint64_t &VR;
852
853 bind_const_intval_ty(uint64_t &V) : VR(V) {}
854
855 template <typename ITy> bool match(ITy *V) {
856 if (const auto *CV = dyn_cast<ConstantInt>(V))
857 if (CV->getValue().ule(UINT64_MAX0xffffffffffffffffULL)) {
858 VR = CV->getZExtValue();
859 return true;
860 }
861 return false;
862 }
863};
864
865/// Match a specified integer value or vector of all elements of that
866/// value.
867template <bool AllowUndefs>
868struct specific_intval {
869 APInt Val;
870
871 specific_intval(APInt V) : Val(std::move(V)) {}
872
873 template <typename ITy> bool match(ITy *V) {
874 const auto *CI = dyn_cast<ConstantInt>(V);
875 if (!CI && V->getType()->isVectorTy())
876 if (const auto *C = dyn_cast<Constant>(V))
877 CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue(AllowUndefs));
878
879 return CI && APInt::isSameValue(CI->getValue(), Val);
880 }
881};
882
883/// Match a specific integer value or vector with all elements equal to
884/// the value.
885inline specific_intval<false> m_SpecificInt(APInt V) {
886 return specific_intval<false>(std::move(V));
887}
888
889inline specific_intval<false> m_SpecificInt(uint64_t V) {
890 return m_SpecificInt(APInt(64, V));
891}
892
893inline specific_intval<true> m_SpecificIntAllowUndef(APInt V) {
894 return specific_intval<true>(std::move(V));
895}
896
897inline specific_intval<true> m_SpecificIntAllowUndef(uint64_t V) {
898 return m_SpecificIntAllowUndef(APInt(64, V));
899}
900
901/// Match a ConstantInt and bind to its value. This does not match
902/// ConstantInts wider than 64-bits.
903inline bind_const_intval_ty m_ConstantInt(uint64_t &V) { return V; }
904
905/// Match a specified basic block value.
906struct specific_bbval {
907 BasicBlock *Val;
908
909 specific_bbval(BasicBlock *Val) : Val(Val) {}
910
911 template <typename ITy> bool match(ITy *V) {
912 const auto *BB = dyn_cast<BasicBlock>(V);
913 return BB && BB == Val;
914 }
915};
916
917/// Match a specific basic block value.
918inline specific_bbval m_SpecificBB(BasicBlock *BB) {
919 return specific_bbval(BB);
920}
921
922/// A commutative-friendly version of m_Specific().
923inline deferredval_ty<BasicBlock> m_Deferred(BasicBlock *const &BB) {
924 return BB;
925}
926inline deferredval_ty<const BasicBlock>
927m_Deferred(const BasicBlock *const &BB) {
928 return BB;
929}
930
931//===----------------------------------------------------------------------===//
932// Matcher for any binary operator.
933//
934template <typename LHS_t, typename RHS_t, bool Commutable = false>
935struct AnyBinaryOp_match {
936 LHS_t L;
937 RHS_t R;
938
939 // The evaluation order is always stable, regardless of Commutability.
940 // The LHS is always matched first.
941 AnyBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
942
943 template <typename OpTy> bool match(OpTy *V) {
944 if (auto *I = dyn_cast<BinaryOperator>(V))
945 return (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
946 (Commutable && L.match(I->getOperand(1)) &&
947 R.match(I->getOperand(0)));
948 return false;
949 }
950};
951
952template <typename LHS, typename RHS>
953inline AnyBinaryOp_match<LHS, RHS> m_BinOp(const LHS &L, const RHS &R) {
954 return AnyBinaryOp_match<LHS, RHS>(L, R);
955}
956
957//===----------------------------------------------------------------------===//
958// Matcher for any unary operator.
959// TODO fuse unary, binary matcher into n-ary matcher
960//
961template <typename OP_t> struct AnyUnaryOp_match {
962 OP_t X;
963
964 AnyUnaryOp_match(const OP_t &X) : X(X) {}
965
966 template <typename OpTy> bool match(OpTy *V) {
967 if (auto *I = dyn_cast<UnaryOperator>(V))
968 return X.match(I->getOperand(0));
969 return false;
970 }
971};
972
973template <typename OP_t> inline AnyUnaryOp_match<OP_t> m_UnOp(const OP_t &X) {
974 return AnyUnaryOp_match<OP_t>(X);
975}
976
977//===----------------------------------------------------------------------===//
978// Matchers for specific binary operators.
979//
980
981template <typename LHS_t, typename RHS_t, unsigned Opcode,
982 bool Commutable = false>
983struct BinaryOp_match {
984 LHS_t L;
985 RHS_t R;
986
987 // The evaluation order is always stable, regardless of Commutability.
988 // The LHS is always matched first.
989 BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
990
991 template <typename OpTy> bool match(OpTy *V) {
992 if (V->getValueID() == Value::InstructionVal + Opcode) {
5
Assuming the condition is false
6
Taking false branch
993 auto *I = cast<BinaryOperator>(V);
994 return (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
995 (Commutable && L.match(I->getOperand(1)) &&
996 R.match(I->getOperand(0)));
997 }
998 if (auto *CE
7.1
'CE' is null
7.1
'CE' is null
= dyn_cast<ConstantExpr>(V))
7
Assuming 'V' is not a 'ConstantExpr'
8
Taking false branch
999 return CE->getOpcode() == Opcode &&
1000 ((L.match(CE->getOperand(0)) && R.match(CE->getOperand(1))) ||
1001 (Commutable && L.match(CE->getOperand(1)) &&
1002 R.match(CE->getOperand(0))));
1003 return false;
9
Returning zero, which participates in a condition later
1004 }
1005};
1006
1007template <typename LHS, typename RHS>
1008inline BinaryOp_match<LHS, RHS, Instruction::Add> m_Add(const LHS &L,
1009 const RHS &R) {
1010 return BinaryOp_match<LHS, RHS, Instruction::Add>(L, R);
1011}
1012
1013template <typename LHS, typename RHS>
1014inline BinaryOp_match<LHS, RHS, Instruction::FAdd> m_FAdd(const LHS &L,
1015 const RHS &R) {
1016 return BinaryOp_match<LHS, RHS, Instruction::FAdd>(L, R);
1017}
1018
1019template <typename LHS, typename RHS>
1020inline BinaryOp_match<LHS, RHS, Instruction::Sub> m_Sub(const LHS &L,
1021 const RHS &R) {
1022 return BinaryOp_match<LHS, RHS, Instruction::Sub>(L, R);
1023}
1024
1025template <typename LHS, typename RHS>
1026inline BinaryOp_match<LHS, RHS, Instruction::FSub> m_FSub(const LHS &L,
1027 const RHS &R) {
1028 return BinaryOp_match<LHS, RHS, Instruction::FSub>(L, R);
1029}
1030
1031template <typename Op_t> struct FNeg_match {
1032 Op_t X;
1033
1034 FNeg_match(const Op_t &Op) : X(Op) {}
1035 template <typename OpTy> bool match(OpTy *V) {
1036 auto *FPMO = dyn_cast<FPMathOperator>(V);
1037 if (!FPMO) return false;
1038
1039 if (FPMO->getOpcode() == Instruction::FNeg)
1040 return X.match(FPMO->getOperand(0));
1041
1042 if (FPMO->getOpcode() == Instruction::FSub) {
1043 if (FPMO->hasNoSignedZeros()) {
1044 // With 'nsz', any zero goes.
1045 if (!cstfp_pred_ty<is_any_zero_fp>().match(FPMO->getOperand(0)))
1046 return false;
1047 } else {
1048 // Without 'nsz', we need fsub -0.0, X exactly.
1049 if (!cstfp_pred_ty<is_neg_zero_fp>().match(FPMO->getOperand(0)))
1050 return false;
1051 }
1052
1053 return X.match(FPMO->getOperand(1));
1054 }
1055
1056 return false;
1057 }
1058};
1059
1060/// Match 'fneg X' as 'fsub -0.0, X'.
1061template <typename OpTy>
1062inline FNeg_match<OpTy>
1063m_FNeg(const OpTy &X) {
1064 return FNeg_match<OpTy>(X);
1065}
1066
1067/// Match 'fneg X' as 'fsub +-0.0, X'.
1068template <typename RHS>
1069inline BinaryOp_match<cstfp_pred_ty<is_any_zero_fp>, RHS, Instruction::FSub>
1070m_FNegNSZ(const RHS &X) {
1071 return m_FSub(m_AnyZeroFP(), X);
1072}
1073
1074template <typename LHS, typename RHS>
1075inline BinaryOp_match<LHS, RHS, Instruction::Mul> m_Mul(const LHS &L,
1076 const RHS &R) {
1077 return BinaryOp_match<LHS, RHS, Instruction::Mul>(L, R);
1078}
1079
1080template <typename LHS, typename RHS>
1081inline BinaryOp_match<LHS, RHS, Instruction::FMul> m_FMul(const LHS &L,
1082 const RHS &R) {
1083 return BinaryOp_match<LHS, RHS, Instruction::FMul>(L, R);
1084}
1085
1086template <typename LHS, typename RHS>
1087inline BinaryOp_match<LHS, RHS, Instruction::UDiv> m_UDiv(const LHS &L,
1088 const RHS &R) {
1089 return BinaryOp_match<LHS, RHS, Instruction::UDiv>(L, R);
1090}
1091
1092template <typename LHS, typename RHS>
1093inline BinaryOp_match<LHS, RHS, Instruction::SDiv> m_SDiv(const LHS &L,
1094 const RHS &R) {
1095 return BinaryOp_match<LHS, RHS, Instruction::SDiv>(L, R);
1096}
1097
1098template <typename LHS, typename RHS>
1099inline BinaryOp_match<LHS, RHS, Instruction::FDiv> m_FDiv(const LHS &L,
1100 const RHS &R) {
1101 return BinaryOp_match<LHS, RHS, Instruction::FDiv>(L, R);
1102}
1103
1104template <typename LHS, typename RHS>
1105inline BinaryOp_match<LHS, RHS, Instruction::URem> m_URem(const LHS &L,
1106 const RHS &R) {
1107 return BinaryOp_match<LHS, RHS, Instruction::URem>(L, R);
1108}
1109
1110template <typename LHS, typename RHS>
1111inline BinaryOp_match<LHS, RHS, Instruction::SRem> m_SRem(const LHS &L,
1112 const RHS &R) {
1113 return BinaryOp_match<LHS, RHS, Instruction::SRem>(L, R);
1114}
1115
1116template <typename LHS, typename RHS>
1117inline BinaryOp_match<LHS, RHS, Instruction::FRem> m_FRem(const LHS &L,
1118 const RHS &R) {
1119 return BinaryOp_match<LHS, RHS, Instruction::FRem>(L, R);
1120}
1121
1122template <typename LHS, typename RHS>
1123inline BinaryOp_match<LHS, RHS, Instruction::And> m_And(const LHS &L,
1124 const RHS &R) {
1125 return BinaryOp_match<LHS, RHS, Instruction::And>(L, R);
1126}
1127
1128template <typename LHS, typename RHS>
1129inline BinaryOp_match<LHS, RHS, Instruction::Or> m_Or(const LHS &L,
1130 const RHS &R) {
1131 return BinaryOp_match<LHS, RHS, Instruction::Or>(L, R);
1132}
1133
1134template <typename LHS, typename RHS>
1135inline BinaryOp_match<LHS, RHS, Instruction::Xor> m_Xor(const LHS &L,
1136 const RHS &R) {
1137 return BinaryOp_match<LHS, RHS, Instruction::Xor>(L, R);
1138}
1139
1140template <typename LHS, typename RHS>
1141inline BinaryOp_match<LHS, RHS, Instruction::Shl> m_Shl(const LHS &L,
1142 const RHS &R) {
1143 return BinaryOp_match<LHS, RHS, Instruction::Shl>(L, R);
1144}
1145
1146template <typename LHS, typename RHS>
1147inline BinaryOp_match<LHS, RHS, Instruction::LShr> m_LShr(const LHS &L,
1148 const RHS &R) {
1149 return BinaryOp_match<LHS, RHS, Instruction::LShr>(L, R);
1150}
1151
1152template <typename LHS, typename RHS>
1153inline BinaryOp_match<LHS, RHS, Instruction::AShr> m_AShr(const LHS &L,
1154 const RHS &R) {
1155 return BinaryOp_match<LHS, RHS, Instruction::AShr>(L, R);
1156}
1157
1158template <typename LHS_t, typename RHS_t, unsigned Opcode,
1159 unsigned WrapFlags = 0>
1160struct OverflowingBinaryOp_match {
1161 LHS_t L;
1162 RHS_t R;
1163
1164 OverflowingBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS)
1165 : L(LHS), R(RHS) {}
1166
1167 template <typename OpTy> bool match(OpTy *V) {
1168 if (auto *Op = dyn_cast<OverflowingBinaryOperator>(V)) {
1169 if (Op->getOpcode() != Opcode)
1170 return false;
1171 if ((WrapFlags & OverflowingBinaryOperator::NoUnsignedWrap) &&
1172 !Op->hasNoUnsignedWrap())
1173 return false;
1174 if ((WrapFlags & OverflowingBinaryOperator::NoSignedWrap) &&
1175 !Op->hasNoSignedWrap())
1176 return false;
1177 return L.match(Op->getOperand(0)) && R.match(Op->getOperand(1));
1178 }
1179 return false;
1180 }
1181};
1182
1183template <typename LHS, typename RHS>
1184inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
1185 OverflowingBinaryOperator::NoSignedWrap>
1186m_NSWAdd(const LHS &L, const RHS &R) {
1187 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
1188 OverflowingBinaryOperator::NoSignedWrap>(
1189 L, R);
1190}
1191template <typename LHS, typename RHS>
1192inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
1193 OverflowingBinaryOperator::NoSignedWrap>
1194m_NSWSub(const LHS &L, const RHS &R) {
1195 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
1196 OverflowingBinaryOperator::NoSignedWrap>(
1197 L, R);
1198}
1199template <typename LHS, typename RHS>
1200inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
1201 OverflowingBinaryOperator::NoSignedWrap>
1202m_NSWMul(const LHS &L, const RHS &R) {
1203 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
1204 OverflowingBinaryOperator::NoSignedWrap>(
1205 L, R);
1206}
1207template <typename LHS, typename RHS>
1208inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
1209 OverflowingBinaryOperator::NoSignedWrap>
1210m_NSWShl(const LHS &L, const RHS &R) {
1211 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
1212 OverflowingBinaryOperator::NoSignedWrap>(
1213 L, R);
1214}
1215
1216template <typename LHS, typename RHS>
1217inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
1218 OverflowingBinaryOperator::NoUnsignedWrap>
1219m_NUWAdd(const LHS &L, const RHS &R) {
1220 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
1221 OverflowingBinaryOperator::NoUnsignedWrap>(
1222 L, R);
1223}
1224template <typename LHS, typename RHS>
1225inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
1226 OverflowingBinaryOperator::NoUnsignedWrap>
1227m_NUWSub(const LHS &L, const RHS &R) {
1228 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
1229 OverflowingBinaryOperator::NoUnsignedWrap>(
1230 L, R);
1231}
1232template <typename LHS, typename RHS>
1233inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
1234 OverflowingBinaryOperator::NoUnsignedWrap>
1235m_NUWMul(const LHS &L, const RHS &R) {
1236 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
1237 OverflowingBinaryOperator::NoUnsignedWrap>(
1238 L, R);
1239}
1240template <typename LHS, typename RHS>
1241inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
1242 OverflowingBinaryOperator::NoUnsignedWrap>
1243m_NUWShl(const LHS &L, const RHS &R) {
1244 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
1245 OverflowingBinaryOperator::NoUnsignedWrap>(
1246 L, R);
1247}
1248
1249//===----------------------------------------------------------------------===//
1250// Class that matches a group of binary opcodes.
1251//
1252template <typename LHS_t, typename RHS_t, typename Predicate>
1253struct BinOpPred_match : Predicate {
1254 LHS_t L;
1255 RHS_t R;
1256
1257 BinOpPred_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
1258
1259 template <typename OpTy> bool match(OpTy *V) {
1260 if (auto *I = dyn_cast<Instruction>(V))
1261 return this->isOpType(I->getOpcode()) && L.match(I->getOperand(0)) &&
1262 R.match(I->getOperand(1));
1263 if (auto *CE = dyn_cast<ConstantExpr>(V))
1264 return this->isOpType(CE->getOpcode()) && L.match(CE->getOperand(0)) &&
1265 R.match(CE->getOperand(1));
1266 return false;
1267 }
1268};
1269
1270struct is_shift_op {
1271 bool isOpType(unsigned Opcode) { return Instruction::isShift(Opcode); }
1272};
1273
1274struct is_right_shift_op {
1275 bool isOpType(unsigned Opcode) {
1276 return Opcode == Instruction::LShr || Opcode == Instruction::AShr;
1277 }
1278};
1279
1280struct is_logical_shift_op {
1281 bool isOpType(unsigned Opcode) {
1282 return Opcode == Instruction::LShr || Opcode == Instruction::Shl;
1283 }
1284};
1285
1286struct is_bitwiselogic_op {
1287 bool isOpType(unsigned Opcode) {
1288 return Instruction::isBitwiseLogicOp(Opcode);
1289 }
1290};
1291
1292struct is_idiv_op {
1293 bool isOpType(unsigned Opcode) {
1294 return Opcode == Instruction::SDiv || Opcode == Instruction::UDiv;
1295 }
1296};
1297
1298struct is_irem_op {
1299 bool isOpType(unsigned Opcode) {
1300 return Opcode == Instruction::SRem || Opcode == Instruction::URem;
1301 }
1302};
1303
1304/// Matches shift operations.
1305template <typename LHS, typename RHS>
1306inline BinOpPred_match<LHS, RHS, is_shift_op> m_Shift(const LHS &L,
1307 const RHS &R) {
1308 return BinOpPred_match<LHS, RHS, is_shift_op>(L, R);
1309}
1310
1311/// Matches logical shift operations.
1312template <typename LHS, typename RHS>
1313inline BinOpPred_match<LHS, RHS, is_right_shift_op> m_Shr(const LHS &L,
1314 const RHS &R) {
1315 return BinOpPred_match<LHS, RHS, is_right_shift_op>(L, R);
1316}
1317
1318/// Matches logical shift operations.
1319template <typename LHS, typename RHS>
1320inline BinOpPred_match<LHS, RHS, is_logical_shift_op>
1321m_LogicalShift(const LHS &L, const RHS &R) {
1322 return BinOpPred_match<LHS, RHS, is_logical_shift_op>(L, R);
1323}
1324
1325/// Matches bitwise logic operations.
1326template <typename LHS, typename RHS>
1327inline BinOpPred_match<LHS, RHS, is_bitwiselogic_op>
1328m_BitwiseLogic(const LHS &L, const RHS &R) {
1329 return BinOpPred_match<LHS, RHS, is_bitwiselogic_op>(L, R);
1330}
1331
1332/// Matches integer division operations.
1333template <typename LHS, typename RHS>
1334inline BinOpPred_match<LHS, RHS, is_idiv_op> m_IDiv(const LHS &L,
1335 const RHS &R) {
1336 return BinOpPred_match<LHS, RHS, is_idiv_op>(L, R);
1337}
1338
1339/// Matches integer remainder operations.
1340template <typename LHS, typename RHS>
1341inline BinOpPred_match<LHS, RHS, is_irem_op> m_IRem(const LHS &L,
1342 const RHS &R) {
1343 return BinOpPred_match<LHS, RHS, is_irem_op>(L, R);
1344}
1345
1346//===----------------------------------------------------------------------===//
1347// Class that matches exact binary ops.
1348//
1349template <typename SubPattern_t> struct Exact_match {
1350 SubPattern_t SubPattern;
1351
1352 Exact_match(const SubPattern_t &SP) : SubPattern(SP) {}
1353
1354 template <typename OpTy> bool match(OpTy *V) {
1355 if (auto *PEO = dyn_cast<PossiblyExactOperator>(V))
1356 return PEO->isExact() && SubPattern.match(V);
1357 return false;
1358 }
1359};
1360
1361template <typename T> inline Exact_match<T> m_Exact(const T &SubPattern) {
1362 return SubPattern;
1363}
1364
1365//===----------------------------------------------------------------------===//
1366// Matchers for CmpInst classes
1367//
1368
1369template <typename LHS_t, typename RHS_t, typename Class, typename PredicateTy,
1370 bool Commutable = false>
1371struct CmpClass_match {
1372 PredicateTy &Predicate;
1373 LHS_t L;
1374 RHS_t R;
1375
1376 // The evaluation order is always stable, regardless of Commutability.
1377 // The LHS is always matched first.
1378 CmpClass_match(PredicateTy &Pred, const LHS_t &LHS, const RHS_t &RHS)
1379 : Predicate(Pred), L(LHS), R(RHS) {}
1380
1381 template <typename OpTy> bool match(OpTy *V) {
1382 if (auto *I = dyn_cast<Class>(V)) {
1383 if (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) {
1384 Predicate = I->getPredicate();
1385 return true;
1386 } else if (Commutable && L.match(I->getOperand(1)) &&
1387 R.match(I->getOperand(0))) {
1388 Predicate = I->getSwappedPredicate();
1389 return true;
1390 }
1391 }
1392 return false;
1393 }
1394};
1395
1396template <typename LHS, typename RHS>
1397inline CmpClass_match<LHS, RHS, CmpInst, CmpInst::Predicate>
1398m_Cmp(CmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
1399 return CmpClass_match<LHS, RHS, CmpInst, CmpInst::Predicate>(Pred, L, R);
1400}
1401
1402template <typename LHS, typename RHS>
1403inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>
1404m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
1405 return CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>(Pred, L, R);
1406}
1407
1408template <typename LHS, typename RHS>
1409inline CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate>
1410m_FCmp(FCmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
1411 return CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate>(Pred, L, R);
1412}
1413
1414//===----------------------------------------------------------------------===//
1415// Matchers for instructions with a given opcode and number of operands.
1416//
1417
1418/// Matches instructions with Opcode and three operands.
1419template <typename T0, unsigned Opcode> struct OneOps_match {
1420 T0 Op1;
1421
1422 OneOps_match(const T0 &Op1) : Op1(Op1) {}
1423
1424 template <typename OpTy> bool match(OpTy *V) {
1425 if (V->getValueID() == Value::InstructionVal + Opcode) {
1426 auto *I = cast<Instruction>(V);
1427 return Op1.match(I->getOperand(0));
1428 }
1429 return false;
1430 }
1431};
1432
1433/// Matches instructions with Opcode and three operands.
1434template <typename T0, typename T1, unsigned Opcode> struct TwoOps_match {
1435 T0 Op1;
1436 T1 Op2;
1437
1438 TwoOps_match(const T0 &Op1, const T1 &Op2) : Op1(Op1), Op2(Op2) {}
1439
1440 template <typename OpTy> bool match(OpTy *V) {
1441 if (V->getValueID() == Value::InstructionVal + Opcode) {
1442 auto *I = cast<Instruction>(V);
1443 return Op1.match(I->getOperand(0)) && Op2.match(I->getOperand(1));
1444 }
1445 return false;
1446 }
1447};
1448
1449/// Matches instructions with Opcode and three operands.
1450template <typename T0, typename T1, typename T2, unsigned Opcode>
1451struct ThreeOps_match {
1452 T0 Op1;
1453 T1 Op2;
1454 T2 Op3;
1455
1456 ThreeOps_match(const T0 &Op1, const T1 &Op2, const T2 &Op3)
1457 : Op1(Op1), Op2(Op2), Op3(Op3) {}
1458
1459 template <typename OpTy> bool match(OpTy *V) {
1460 if (V->getValueID() == Value::InstructionVal + Opcode) {
1461 auto *I = cast<Instruction>(V);
1462 return Op1.match(I->getOperand(0)) && Op2.match(I->getOperand(1)) &&
1463 Op3.match(I->getOperand(2));
1464 }
1465 return false;
1466 }
1467};
1468
1469/// Matches SelectInst.
1470template <typename Cond, typename LHS, typename RHS>
1471inline ThreeOps_match<Cond, LHS, RHS, Instruction::Select>
1472m_Select(const Cond &C, const LHS &L, const RHS &R) {
1473 return ThreeOps_match<Cond, LHS, RHS, Instruction::Select>(C, L, R);
1474}
1475
1476/// This matches a select of two constants, e.g.:
1477/// m_SelectCst<-1, 0>(m_Value(V))
1478template <int64_t L, int64_t R, typename Cond>
1479inline ThreeOps_match<Cond, constantint_match<L>, constantint_match<R>,
1480 Instruction::Select>
1481m_SelectCst(const Cond &C) {
1482 return m_Select(C, m_ConstantInt<L>(), m_ConstantInt<R>());
1483}
1484
1485/// Matches FreezeInst.
1486template <typename OpTy>
1487inline OneOps_match<OpTy, Instruction::Freeze> m_Freeze(const OpTy &Op) {
1488 return OneOps_match<OpTy, Instruction::Freeze>(Op);
1489}
1490
1491/// Matches InsertElementInst.
1492template <typename Val_t, typename Elt_t, typename Idx_t>
1493inline ThreeOps_match<Val_t, Elt_t, Idx_t, Instruction::InsertElement>
1494m_InsertElt(const Val_t &Val, const Elt_t &Elt, const Idx_t &Idx) {
1495 return ThreeOps_match<Val_t, Elt_t, Idx_t, Instruction::InsertElement>(
1496 Val, Elt, Idx);
1497}
1498
1499/// Matches ExtractElementInst.
1500template <typename Val_t, typename Idx_t>
1501inline TwoOps_match<Val_t, Idx_t, Instruction::ExtractElement>
1502m_ExtractElt(const Val_t &Val, const Idx_t &Idx) {
1503 return TwoOps_match<Val_t, Idx_t, Instruction::ExtractElement>(Val, Idx);
1504}
1505
1506/// Matches shuffle.
1507template <typename T0, typename T1, typename T2> struct Shuffle_match {
1508 T0 Op1;
1509 T1 Op2;
1510 T2 Mask;
1511
1512 Shuffle_match(const T0 &Op1, const T1 &Op2, const T2 &Mask)
1513 : Op1(Op1), Op2(Op2), Mask(Mask) {}
1514
1515 template <typename OpTy> bool match(OpTy *V) {
1516 if (auto *I = dyn_cast<ShuffleVectorInst>(V)) {
1517 return Op1.match(I->getOperand(0)) && Op2.match(I->getOperand(1)) &&
1518 Mask.match(I->getShuffleMask());
1519 }
1520 return false;
1521 }
1522};
1523
1524struct m_Mask {
1525 ArrayRef<int> &MaskRef;
1526 m_Mask(ArrayRef<int> &MaskRef) : MaskRef(MaskRef) {}
1527 bool match(ArrayRef<int> Mask) {
1528 MaskRef = Mask;
1529 return true;
1530 }
1531};
1532
1533struct m_ZeroMask {
1534 bool match(ArrayRef<int> Mask) {
1535 return all_of(Mask, [](int Elem) { return Elem == 0 || Elem == -1; });
1536 }
1537};
1538
1539struct m_SpecificMask {
1540 ArrayRef<int> &MaskRef;
1541 m_SpecificMask(ArrayRef<int> &MaskRef) : MaskRef(MaskRef) {}
1542 bool match(ArrayRef<int> Mask) { return MaskRef == Mask; }
1543};
1544
1545struct m_SplatOrUndefMask {
1546 int &SplatIndex;
1547 m_SplatOrUndefMask(int &SplatIndex) : SplatIndex(SplatIndex) {}
1548 bool match(ArrayRef<int> Mask) {
1549 auto First = find_if(Mask, [](int Elem) { return Elem != -1; });
1550 if (First == Mask.end())
1551 return false;
1552 SplatIndex = *First;
1553 return all_of(Mask,
1554 [First](int Elem) { return Elem == *First || Elem == -1; });
1555 }
1556};
1557
1558/// Matches ShuffleVectorInst independently of mask value.
1559template <typename V1_t, typename V2_t>
1560inline TwoOps_match<V1_t, V2_t, Instruction::ShuffleVector>
1561m_Shuffle(const V1_t &v1, const V2_t &v2) {
1562 return TwoOps_match<V1_t, V2_t, Instruction::ShuffleVector>(v1, v2);
1563}
1564
1565template <typename V1_t, typename V2_t, typename Mask_t>
1566inline Shuffle_match<V1_t, V2_t, Mask_t>
1567m_Shuffle(const V1_t &v1, const V2_t &v2, const Mask_t &mask) {
1568 return Shuffle_match<V1_t, V2_t, Mask_t>(v1, v2, mask);
1569}
1570
1571/// Matches LoadInst.
1572template <typename OpTy>
1573inline OneOps_match<OpTy, Instruction::Load> m_Load(const OpTy &Op) {
1574 return OneOps_match<OpTy, Instruction::Load>(Op);
1575}
1576
1577/// Matches StoreInst.
1578template <typename ValueOpTy, typename PointerOpTy>
1579inline TwoOps_match<ValueOpTy, PointerOpTy, Instruction::Store>
1580m_Store(const ValueOpTy &ValueOp, const PointerOpTy &PointerOp) {
1581 return TwoOps_match<ValueOpTy, PointerOpTy, Instruction::Store>(ValueOp,
1582 PointerOp);
1583}
1584
1585//===----------------------------------------------------------------------===//
1586// Matchers for CastInst classes
1587//
1588
1589template <typename Op_t, unsigned Opcode> struct CastClass_match {
1590 Op_t Op;
1591
1592 CastClass_match(const Op_t &OpMatch) : Op(OpMatch) {}
1593
1594 template <typename OpTy> bool match(OpTy *V) {
1595 if (auto *O = dyn_cast<Operator>(V))
1596 return O->getOpcode() == Opcode && Op.match(O->getOperand(0));
1597 return false;
1598 }
1599};
1600
1601/// Matches BitCast.
1602template <typename OpTy>
1603inline CastClass_match<OpTy, Instruction::BitCast> m_BitCast(const OpTy &Op) {
1604 return CastClass_match<OpTy, Instruction::BitCast>(Op);
1605}
1606
1607/// Matches PtrToInt.
1608template <typename OpTy>
1609inline CastClass_match<OpTy, Instruction::PtrToInt> m_PtrToInt(const OpTy &Op) {
1610 return CastClass_match<OpTy, Instruction::PtrToInt>(Op);
1611}
1612
1613/// Matches IntToPtr.
1614template <typename OpTy>
1615inline CastClass_match<OpTy, Instruction::IntToPtr> m_IntToPtr(const OpTy &Op) {
1616 return CastClass_match<OpTy, Instruction::IntToPtr>(Op);
1617}
1618
1619/// Matches Trunc.
1620template <typename OpTy>
1621inline CastClass_match<OpTy, Instruction::Trunc> m_Trunc(const OpTy &Op) {
1622 return CastClass_match<OpTy, Instruction::Trunc>(Op);
1623}
1624
1625template <typename OpTy>
1626inline match_combine_or<CastClass_match<OpTy, Instruction::Trunc>, OpTy>
1627m_TruncOrSelf(const OpTy &Op) {
1628 return m_CombineOr(m_Trunc(Op), Op);
1629}
1630
1631/// Matches SExt.
1632template <typename OpTy>
1633inline CastClass_match<OpTy, Instruction::SExt> m_SExt(const OpTy &Op) {
1634 return CastClass_match<OpTy, Instruction::SExt>(Op);
1635}
1636
1637/// Matches ZExt.
1638template <typename OpTy>
1639inline CastClass_match<OpTy, Instruction::ZExt> m_ZExt(const OpTy &Op) {
1640 return CastClass_match<OpTy, Instruction::ZExt>(Op);
1641}
1642
1643template <typename OpTy>
1644inline match_combine_or<CastClass_match<OpTy, Instruction::ZExt>, OpTy>
1645m_ZExtOrSelf(const OpTy &Op) {
1646 return m_CombineOr(m_ZExt(Op), Op);
1647}
1648
1649template <typename OpTy>
1650inline match_combine_or<CastClass_match<OpTy, Instruction::SExt>, OpTy>
1651m_SExtOrSelf(const OpTy &Op) {
1652 return m_CombineOr(m_SExt(Op), Op);
1653}
1654
1655template <typename OpTy>
1656inline match_combine_or<CastClass_match<OpTy, Instruction::ZExt>,
1657 CastClass_match<OpTy, Instruction::SExt>>
1658m_ZExtOrSExt(const OpTy &Op) {
1659 return m_CombineOr(m_ZExt(Op), m_SExt(Op));
1660}
1661
1662template <typename OpTy>
1663inline match_combine_or<
1664 match_combine_or<CastClass_match<OpTy, Instruction::ZExt>,
1665 CastClass_match<OpTy, Instruction::SExt>>,
1666 OpTy>
1667m_ZExtOrSExtOrSelf(const OpTy &Op) {
1668 return m_CombineOr(m_ZExtOrSExt(Op), Op);
1669}
1670
1671template <typename OpTy>
1672inline CastClass_match<OpTy, Instruction::UIToFP> m_UIToFP(const OpTy &Op) {
1673 return CastClass_match<OpTy, Instruction::UIToFP>(Op);
1674}
1675
1676template <typename OpTy>
1677inline CastClass_match<OpTy, Instruction::SIToFP> m_SIToFP(const OpTy &Op) {
1678 return CastClass_match<OpTy, Instruction::SIToFP>(Op);
1679}
1680
1681template <typename OpTy>
1682inline CastClass_match<OpTy, Instruction::FPToUI> m_FPToUI(const OpTy &Op) {
1683 return CastClass_match<OpTy, Instruction::FPToUI>(Op);
1684}
1685
1686template <typename OpTy>
1687inline CastClass_match<OpTy, Instruction::FPToSI> m_FPToSI(const OpTy &Op) {
1688 return CastClass_match<OpTy, Instruction::FPToSI>(Op);
1689}
1690
1691template <typename OpTy>
1692inline CastClass_match<OpTy, Instruction::FPTrunc> m_FPTrunc(const OpTy &Op) {
1693 return CastClass_match<OpTy, Instruction::FPTrunc>(Op);
1694}
1695
1696template <typename OpTy>
1697inline CastClass_match<OpTy, Instruction::FPExt> m_FPExt(const OpTy &Op) {
1698 return CastClass_match<OpTy, Instruction::FPExt>(Op);
1699}
1700
1701//===----------------------------------------------------------------------===//
1702// Matchers for control flow.
1703//
1704
1705struct br_match {
1706 BasicBlock *&Succ;
1707
1708 br_match(BasicBlock *&Succ) : Succ(Succ) {}
1709
1710 template <typename OpTy> bool match(OpTy *V) {
1711 if (auto *BI = dyn_cast<BranchInst>(V))
1712 if (BI->isUnconditional()) {
1713 Succ = BI->getSuccessor(0);
1714 return true;
1715 }
1716 return false;
1717 }
1718};
1719
1720inline br_match m_UnconditionalBr(BasicBlock *&Succ) { return br_match(Succ); }
1721
1722template <typename Cond_t, typename TrueBlock_t, typename FalseBlock_t>
1723struct brc_match {
1724 Cond_t Cond;
1725 TrueBlock_t T;
1726 FalseBlock_t F;
1727
1728 brc_match(const Cond_t &C, const TrueBlock_t &t, const FalseBlock_t &f)
1729 : Cond(C), T(t), F(f) {}
1730
1731 template <typename OpTy> bool match(OpTy *V) {
1732 if (auto *BI = dyn_cast<BranchInst>(V))
1733 if (BI->isConditional() && Cond.match(BI->getCondition()))
1734 return T.match(BI->getSuccessor(0)) && F.match(BI->getSuccessor(1));
1735 return false;
1736 }
1737};
1738
1739template <typename Cond_t>
1740inline brc_match<Cond_t, bind_ty<BasicBlock>, bind_ty<BasicBlock>>
1741m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F) {
1742 return brc_match<Cond_t, bind_ty<BasicBlock>, bind_ty<BasicBlock>>(
1743 C, m_BasicBlock(T), m_BasicBlock(F));
1744}
1745
1746template <typename Cond_t, typename TrueBlock_t, typename FalseBlock_t>
1747inline brc_match<Cond_t, TrueBlock_t, FalseBlock_t>
1748m_Br(const Cond_t &C, const TrueBlock_t &T, const FalseBlock_t &F) {
1749 return brc_match<Cond_t, TrueBlock_t, FalseBlock_t>(C, T, F);
1750}
1751
1752//===----------------------------------------------------------------------===//
1753// Matchers for max/min idioms, eg: "select (sgt x, y), x, y" -> smax(x,y).
1754//
1755
1756template <typename CmpInst_t, typename LHS_t, typename RHS_t, typename Pred_t,
1757 bool Commutable = false>
1758struct MaxMin_match {
1759 using PredType = Pred_t;
1760 LHS_t L;
1761 RHS_t R;
1762
1763 // The evaluation order is always stable, regardless of Commutability.
1764 // The LHS is always matched first.
1765 MaxMin_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
1766
1767 template <typename OpTy> bool match(OpTy *V) {
1768 if (auto *II = dyn_cast<IntrinsicInst>(V)) {
1769 Intrinsic::ID IID = II->getIntrinsicID();
1770 if ((IID == Intrinsic::smax && Pred_t::match(ICmpInst::ICMP_SGT)) ||
1771 (IID == Intrinsic::smin && Pred_t::match(ICmpInst::ICMP_SLT)) ||
1772 (IID == Intrinsic::umax && Pred_t::match(ICmpInst::ICMP_UGT)) ||
1773 (IID == Intrinsic::umin && Pred_t::match(ICmpInst::ICMP_ULT))) {
1774 Value *LHS = II->getOperand(0), *RHS = II->getOperand(1);
1775 return (L.match(LHS) && R.match(RHS)) ||
1776 (Commutable && L.match(RHS) && R.match(LHS));
1777 }
1778 }
1779 // Look for "(x pred y) ? x : y" or "(x pred y) ? y : x".
1780 auto *SI = dyn_cast<SelectInst>(V);
1781 if (!SI)
1782 return false;
1783 auto *Cmp = dyn_cast<CmpInst_t>(SI->getCondition());
1784 if (!Cmp)
1785 return false;
1786 // At this point we have a select conditioned on a comparison. Check that
1787 // it is the values returned by the select that are being compared.
1788 auto *TrueVal = SI->getTrueValue();
1789 auto *FalseVal = SI->getFalseValue();
1790 auto *LHS = Cmp->getOperand(0);
1791 auto *RHS = Cmp->getOperand(1);
1792 if ((TrueVal != LHS || FalseVal != RHS) &&
1793 (TrueVal != RHS || FalseVal != LHS))
1794 return false;
1795 typename CmpInst_t::Predicate Pred =
1796 LHS == TrueVal ? Cmp->getPredicate() : Cmp->getInversePredicate();
1797 // Does "(x pred y) ? x : y" represent the desired max/min operation?
1798 if (!Pred_t::match(Pred))
1799 return false;
1800 // It does! Bind the operands.
1801 return (L.match(LHS) && R.match(RHS)) ||
1802 (Commutable && L.match(RHS) && R.match(LHS));
1803 }
1804};
1805
1806/// Helper class for identifying signed max predicates.
1807struct smax_pred_ty {
1808 static bool match(ICmpInst::Predicate Pred) {
1809 return Pred == CmpInst::ICMP_SGT || Pred == CmpInst::ICMP_SGE;
1810 }
1811};
1812
1813/// Helper class for identifying signed min predicates.
1814struct smin_pred_ty {
1815 static bool match(ICmpInst::Predicate Pred) {
1816 return Pred == CmpInst::ICMP_SLT || Pred == CmpInst::ICMP_SLE;
1817 }
1818};
1819
1820/// Helper class for identifying unsigned max predicates.
1821struct umax_pred_ty {
1822 static bool match(ICmpInst::Predicate Pred) {
1823 return Pred == CmpInst::ICMP_UGT || Pred == CmpInst::ICMP_UGE;
1824 }
1825};
1826
1827/// Helper class for identifying unsigned min predicates.
1828struct umin_pred_ty {
1829 static bool match(ICmpInst::Predicate Pred) {
1830 return Pred == CmpInst::ICMP_ULT || Pred == CmpInst::ICMP_ULE;
1831 }
1832};
1833
1834/// Helper class for identifying ordered max predicates.
1835struct ofmax_pred_ty {
1836 static bool match(FCmpInst::Predicate Pred) {
1837 return Pred == CmpInst::FCMP_OGT || Pred == CmpInst::FCMP_OGE;
1838 }
1839};
1840
1841/// Helper class for identifying ordered min predicates.
1842struct ofmin_pred_ty {
1843 static bool match(FCmpInst::Predicate Pred) {
1844 return Pred == CmpInst::FCMP_OLT || Pred == CmpInst::FCMP_OLE;
1845 }
1846};
1847
1848/// Helper class for identifying unordered max predicates.
1849struct ufmax_pred_ty {
1850 static bool match(FCmpInst::Predicate Pred) {
1851 return Pred == CmpInst::FCMP_UGT || Pred == CmpInst::FCMP_UGE;
1852 }
1853};
1854
1855/// Helper class for identifying unordered min predicates.
1856struct ufmin_pred_ty {
1857 static bool match(FCmpInst::Predicate Pred) {
1858 return Pred == CmpInst::FCMP_ULT || Pred == CmpInst::FCMP_ULE;
1859 }
1860};
1861
1862template <typename LHS, typename RHS>
1863inline MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty> m_SMax(const LHS &L,
1864 const RHS &R) {
1865 return MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty>(L, R);
1866}
1867
1868template <typename LHS, typename RHS>
1869inline MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty> m_SMin(const LHS &L,
1870 const RHS &R) {
1871 return MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty>(L, R);
1872}
1873
1874template <typename LHS, typename RHS>
1875inline MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty> m_UMax(const LHS &L,
1876 const RHS &R) {
1877 return MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty>(L, R);
1878}
1879
1880template <typename LHS, typename RHS>
1881inline MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty> m_UMin(const LHS &L,
1882 const RHS &R) {
1883 return MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty>(L, R);
1884}
1885
1886template <typename LHS, typename RHS>
1887inline match_combine_or<
1888 match_combine_or<MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty>,
1889 MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty>>,
1890 match_combine_or<MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty>,
1891 MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty>>>
1892m_MaxOrMin(const LHS &L, const RHS &R) {
1893 return m_CombineOr(m_CombineOr(m_SMax(L, R), m_SMin(L, R)),
1894 m_CombineOr(m_UMax(L, R), m_UMin(L, R)));
1895}
1896
1897/// Match an 'ordered' floating point maximum function.
1898/// Floating point has one special value 'NaN'. Therefore, there is no total
1899/// order. However, if we can ignore the 'NaN' value (for example, because of a
1900/// 'no-nans-float-math' flag) a combination of a fcmp and select has 'maximum'
1901/// semantics. In the presence of 'NaN' we have to preserve the original
1902/// select(fcmp(ogt/ge, L, R), L, R) semantics matched by this predicate.
1903///
1904/// max(L, R) iff L and R are not NaN
1905/// m_OrdFMax(L, R) = R iff L or R are NaN
1906template <typename LHS, typename RHS>
1907inline MaxMin_match<FCmpInst, LHS, RHS, ofmax_pred_ty> m_OrdFMax(const LHS &L,
1908 const RHS &R) {
1909 return MaxMin_match<FCmpInst, LHS, RHS, ofmax_pred_ty>(L, R);
1910}
1911
1912/// Match an 'ordered' floating point minimum function.
1913/// Floating point has one special value 'NaN'. Therefore, there is no total
1914/// order. However, if we can ignore the 'NaN' value (for example, because of a
1915/// 'no-nans-float-math' flag) a combination of a fcmp and select has 'minimum'
1916/// semantics. In the presence of 'NaN' we have to preserve the original
1917/// select(fcmp(olt/le, L, R), L, R) semantics matched by this predicate.
1918///
1919/// min(L, R) iff L and R are not NaN
1920/// m_OrdFMin(L, R) = R iff L or R are NaN
1921template <typename LHS, typename RHS>
1922inline MaxMin_match<FCmpInst, LHS, RHS, ofmin_pred_ty> m_OrdFMin(const LHS &L,
1923 const RHS &R) {
1924 return MaxMin_match<FCmpInst, LHS, RHS, ofmin_pred_ty>(L, R);
1925}
1926
1927/// Match an 'unordered' floating point maximum function.
1928/// Floating point has one special value 'NaN'. Therefore, there is no total
1929/// order. However, if we can ignore the 'NaN' value (for example, because of a
1930/// 'no-nans-float-math' flag) a combination of a fcmp and select has 'maximum'
1931/// semantics. In the presence of 'NaN' we have to preserve the original
1932/// select(fcmp(ugt/ge, L, R), L, R) semantics matched by this predicate.
1933///
1934/// max(L, R) iff L and R are not NaN
1935/// m_UnordFMax(L, R) = L iff L or R are NaN
1936template <typename LHS, typename RHS>
1937inline MaxMin_match<FCmpInst, LHS, RHS, ufmax_pred_ty>
1938m_UnordFMax(const LHS &L, const RHS &R) {
1939 return MaxMin_match<FCmpInst, LHS, RHS, ufmax_pred_ty>(L, R);
1940}
1941
1942/// Match an 'unordered' floating point minimum function.
1943/// Floating point has one special value 'NaN'. Therefore, there is no total
1944/// order. However, if we can ignore the 'NaN' value (for example, because of a
1945/// 'no-nans-float-math' flag) a combination of a fcmp and select has 'minimum'
1946/// semantics. In the presence of 'NaN' we have to preserve the original
1947/// select(fcmp(ult/le, L, R), L, R) semantics matched by this predicate.
1948///
1949/// min(L, R) iff L and R are not NaN
1950/// m_UnordFMin(L, R) = L iff L or R are NaN
1951template <typename LHS, typename RHS>
1952inline MaxMin_match<FCmpInst, LHS, RHS, ufmin_pred_ty>
1953m_UnordFMin(const LHS &L, const RHS &R) {
1954 return MaxMin_match<FCmpInst, LHS, RHS, ufmin_pred_ty>(L, R);
1955}
1956
1957//===----------------------------------------------------------------------===//
1958// Matchers for overflow check patterns: e.g. (a + b) u< a, (a ^ -1) <u b
1959// Note that S might be matched to other instructions than AddInst.
1960//
1961
1962template <typename LHS_t, typename RHS_t, typename Sum_t>
1963struct UAddWithOverflow_match {
1964 LHS_t L;
1965 RHS_t R;
1966 Sum_t S;
1967
1968 UAddWithOverflow_match(const LHS_t &L, const RHS_t &R, const Sum_t &S)
1969 : L(L), R(R), S(S) {}
1970
1971 template <typename OpTy> bool match(OpTy *V) {
1972 Value *ICmpLHS, *ICmpRHS;
1973 ICmpInst::Predicate Pred;
1974 if (!m_ICmp(Pred, m_Value(ICmpLHS), m_Value(ICmpRHS)).match(V))
1975 return false;
1976
1977 Value *AddLHS, *AddRHS;
1978 auto AddExpr = m_Add(m_Value(AddLHS), m_Value(AddRHS));
1979
1980 // (a + b) u< a, (a + b) u< b
1981 if (Pred == ICmpInst::ICMP_ULT)
1982 if (AddExpr.match(ICmpLHS) && (ICmpRHS == AddLHS || ICmpRHS == AddRHS))
1983 return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpLHS);
1984
1985 // a >u (a + b), b >u (a + b)
1986 if (Pred == ICmpInst::ICMP_UGT)
1987 if (AddExpr.match(ICmpRHS) && (ICmpLHS == AddLHS || ICmpLHS == AddRHS))
1988 return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpRHS);
1989
1990 Value *Op1;
1991 auto XorExpr = m_OneUse(m_Xor(m_Value(Op1), m_AllOnes()));
1992 // (a ^ -1) <u b
1993 if (Pred == ICmpInst::ICMP_ULT) {
1994 if (XorExpr.match(ICmpLHS))
1995 return L.match(Op1) && R.match(ICmpRHS) && S.match(ICmpLHS);
1996 }
1997 // b > u (a ^ -1)
1998 if (Pred == ICmpInst::ICMP_UGT) {
1999 if (XorExpr.match(ICmpRHS))
2000 return L.match(Op1) && R.match(ICmpLHS) && S.match(ICmpRHS);
2001 }
2002
2003 // Match special-case for increment-by-1.
2004 if (Pred == ICmpInst::ICMP_EQ) {
2005 // (a + 1) == 0
2006 // (1 + a) == 0
2007 if (AddExpr.match(ICmpLHS) && m_ZeroInt().match(ICmpRHS) &&
2008 (m_One().match(AddLHS) || m_One().match(AddRHS)))
2009 return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpLHS);
2010 // 0 == (a + 1)
2011 // 0 == (1 + a)
2012 if (m_ZeroInt().match(ICmpLHS) && AddExpr.match(ICmpRHS) &&
2013 (m_One().match(AddLHS) || m_One().match(AddRHS)))
2014 return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpRHS);
2015 }
2016
2017 return false;
2018 }
2019};
2020
2021/// Match an icmp instruction checking for unsigned overflow on addition.
2022///
2023/// S is matched to the addition whose result is being checked for overflow, and
2024/// L and R are matched to the LHS and RHS of S.
2025template <typename LHS_t, typename RHS_t, typename Sum_t>
2026UAddWithOverflow_match<LHS_t, RHS_t, Sum_t>
2027m_UAddWithOverflow(const LHS_t &L, const RHS_t &R, const Sum_t &S) {
2028 return UAddWithOverflow_match<LHS_t, RHS_t, Sum_t>(L, R, S);
2029}
2030
2031template <typename Opnd_t> struct Argument_match {
2032 unsigned OpI;
2033 Opnd_t Val;
2034
2035 Argument_match(unsigned OpIdx, const Opnd_t &V) : OpI(OpIdx), Val(V) {}
2036
2037 template <typename OpTy> bool match(OpTy *V) {
2038 // FIXME: Should likely be switched to use `CallBase`.
2039 if (const auto *CI = dyn_cast<CallInst>(V))
2040 return Val.match(CI->getArgOperand(OpI));
2041 return false;
2042 }
2043};
2044
2045/// Match an argument.
2046template <unsigned OpI, typename Opnd_t>
2047inline Argument_match<Opnd_t> m_Argument(const Opnd_t &Op) {
2048 return Argument_match<Opnd_t>(OpI, Op);
2049}
2050
2051/// Intrinsic matchers.
2052struct IntrinsicID_match {
2053 unsigned ID;
2054
2055 IntrinsicID_match(Intrinsic::ID IntrID) : ID(IntrID) {}
2056
2057 template <typename OpTy> bool match(OpTy *V) {
2058 if (const auto *CI = dyn_cast<CallInst>(V))
2059 if (const auto *F = CI->getCalledFunction())
2060 return F->getIntrinsicID() == ID;
2061 return false;
2062 }
2063};
2064
2065/// Intrinsic matches are combinations of ID matchers, and argument
2066/// matchers. Higher arity matcher are defined recursively in terms of and-ing
2067/// them with lower arity matchers. Here's some convenient typedefs for up to
2068/// several arguments, and more can be added as needed
2069template <typename T0 = void, typename T1 = void, typename T2 = void,
2070 typename T3 = void, typename T4 = void, typename T5 = void,
2071 typename T6 = void, typename T7 = void, typename T8 = void,
2072 typename T9 = void, typename T10 = void>
2073struct m_Intrinsic_Ty;
2074template <typename T0> struct m_Intrinsic_Ty<T0> {
2075 using Ty = match_combine_and<IntrinsicID_match, Argument_match<T0>>;
2076};
2077template <typename T0, typename T1> struct m_Intrinsic_Ty<T0, T1> {
2078 using Ty =
2079 match_combine_and<typename m_Intrinsic_Ty<T0>::Ty, Argument_match<T1>>;
2080};
2081template <typename T0, typename T1, typename T2>
2082struct m_Intrinsic_Ty<T0, T1, T2> {
2083 using Ty =
2084 match_combine_and<typename m_Intrinsic_Ty<T0, T1>::Ty,
2085 Argument_match<T2>>;
2086};
2087template <typename T0, typename T1, typename T2, typename T3>
2088struct m_Intrinsic_Ty<T0, T1, T2, T3> {
2089 using Ty =
2090 match_combine_and<typename m_Intrinsic_Ty<T0, T1, T2>::Ty,
2091 Argument_match<T3>>;
2092};
2093
2094template <typename T0, typename T1, typename T2, typename T3, typename T4>
2095struct m_Intrinsic_Ty<T0, T1, T2, T3, T4> {
2096 using Ty = match_combine_and<typename m_Intrinsic_Ty<T0, T1, T2, T3>::Ty,
2097 Argument_match<T4>>;
2098};
2099
2100template <typename T0, typename T1, typename T2, typename T3, typename T4, typename T5>
2101struct m_Intrinsic_Ty<T0, T1, T2, T3, T4, T5> {
2102 using Ty = match_combine_and<typename m_Intrinsic_Ty<T0, T1, T2, T3, T4>::Ty,
2103 Argument_match<T5>>;
2104};
2105
2106/// Match intrinsic calls like this:
2107/// m_Intrinsic<Intrinsic::fabs>(m_Value(X))
2108template <Intrinsic::ID IntrID> inline IntrinsicID_match m_Intrinsic() {
2109 return IntrinsicID_match(IntrID);
2110}
2111
2112/// Matches MaskedLoad Intrinsic.
2113template <typename Opnd0, typename Opnd1, typename Opnd2, typename Opnd3>
2114inline typename m_Intrinsic_Ty<Opnd0, Opnd1, Opnd2, Opnd3>::Ty
2115m_MaskedLoad(const Opnd0 &Op0, const Opnd1 &Op1, const Opnd2 &Op2,
2116 const Opnd3 &Op3) {
2117 return m_Intrinsic<Intrinsic::masked_load>(Op0, Op1, Op2, Op3);
2118}
2119
2120template <Intrinsic::ID IntrID, typename T0>
2121inline typename m_Intrinsic_Ty<T0>::Ty m_Intrinsic(const T0 &Op0) {
2122 return m_CombineAnd(m_Intrinsic<IntrID>(), m_Argument<0>(Op0));
2123}
2124
2125template <Intrinsic::ID IntrID, typename T0, typename T1>
2126inline typename m_Intrinsic_Ty<T0, T1>::Ty m_Intrinsic(const T0 &Op0,
2127 const T1 &Op1) {
2128 return m_CombineAnd(m_Intrinsic<IntrID>(Op0), m_Argument<1>(Op1));
2129}
2130
2131template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2>
2132inline typename m_Intrinsic_Ty<T0, T1, T2>::Ty
2133m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2) {
2134 return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1), m_Argument<2>(Op2));
2135}
2136
2137template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2,
2138 typename T3>
2139inline typename m_Intrinsic_Ty<T0, T1, T2, T3>::Ty
2140m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2, const T3 &Op3) {
2141 return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1, Op2), m_Argument<3>(Op3));
2142}
2143
2144template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2,
2145 typename T3, typename T4>
2146inline typename m_Intrinsic_Ty<T0, T1, T2, T3, T4>::Ty
2147m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2, const T3 &Op3,
2148 const T4 &Op4) {
2149 return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1, Op2, Op3),
2150 m_Argument<4>(Op4));
2151}
2152
2153template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2,
2154 typename T3, typename T4, typename T5>
2155inline typename m_Intrinsic_Ty<T0, T1, T2, T3, T4, T5>::Ty
2156m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2, const T3 &Op3,
2157 const T4 &Op4, const T5 &Op5) {
2158 return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1, Op2, Op3, Op4),
2159 m_Argument<5>(Op5));
2160}
2161
2162// Helper intrinsic matching specializations.
2163template <typename Opnd0>
2164inline typename m_Intrinsic_Ty<Opnd0>::Ty m_BitReverse(const Opnd0 &Op0) {
2165 return m_Intrinsic<Intrinsic::bitreverse>(Op0);
2166}
2167
2168template <typename Opnd0>
2169inline typename m_Intrinsic_Ty<Opnd0>::Ty m_BSwap(const Opnd0 &Op0) {
2170 return m_Intrinsic<Intrinsic::bswap>(Op0);
2171}
2172
2173template <typename Opnd0>
2174inline typename m_Intrinsic_Ty<Opnd0>::Ty m_FAbs(const Opnd0 &Op0) {
2175 return m_Intrinsic<Intrinsic::fabs>(Op0);
2176}
2177
2178template <typename Opnd0>
2179inline typename m_Intrinsic_Ty<Opnd0>::Ty m_FCanonicalize(const Opnd0 &Op0) {
2180 return m_Intrinsic<Intrinsic::canonicalize>(Op0);
2181}
2182
2183template <typename Opnd0, typename Opnd1>
2184inline typename m_Intrinsic_Ty<Opnd0, Opnd1>::Ty m_FMin(const Opnd0 &Op0,
2185 const Opnd1 &Op1) {
2186 return m_Intrinsic<Intrinsic::minnum>(Op0, Op1);
2187}
2188
2189template <typename Opnd0, typename Opnd1>
2190inline typename m_Intrinsic_Ty<Opnd0, Opnd1>::Ty m_FMax(const Opnd0 &Op0,
2191 const Opnd1 &Op1) {
2192 return m_Intrinsic<Intrinsic::maxnum>(Op0, Op1);
2193}
2194
2195template <typename Opnd0, typename Opnd1, typename Opnd2>
2196inline typename m_Intrinsic_Ty<Opnd0, Opnd1, Opnd2>::Ty
2197m_FShl(const Opnd0 &Op0, const Opnd1 &Op1, const Opnd2 &Op2) {
2198 return m_Intrinsic<Intrinsic::fshl>(Op0, Op1, Op2);
2199}
2200
2201template <typename Opnd0, typename Opnd1, typename Opnd2>
2202inline typename m_Intrinsic_Ty<Opnd0, Opnd1, Opnd2>::Ty
2203m_FShr(const Opnd0 &Op0, const Opnd1 &Op1, const Opnd2 &Op2) {
2204 return m_Intrinsic<Intrinsic::fshr>(Op0, Op1, Op2);
2205}
2206
2207//===----------------------------------------------------------------------===//
2208// Matchers for two-operands operators with the operators in either order
2209//
2210
2211/// Matches a BinaryOperator with LHS and RHS in either order.
2212template <typename LHS, typename RHS>
2213inline AnyBinaryOp_match<LHS, RHS, true> m_c_BinOp(const LHS &L, const RHS &R) {
2214 return AnyBinaryOp_match<LHS, RHS, true>(L, R);
2215}
2216
2217/// Matches an ICmp with a predicate over LHS and RHS in either order.
2218/// Swaps the predicate if operands are commuted.
2219template <typename LHS, typename RHS>
2220inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate, true>
2221m_c_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
2222 return CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate, true>(Pred, L,
2223 R);
2224}
2225
2226/// Matches a Add with LHS and RHS in either order.
2227template <typename LHS, typename RHS>
2228inline BinaryOp_match<LHS, RHS, Instruction::Add, true> m_c_Add(const LHS &L,
2229 const RHS &R) {
2230 return BinaryOp_match<LHS, RHS, Instruction::Add, true>(L, R);
2231}
2232
2233/// Matches a Mul with LHS and RHS in either order.
2234template <typename LHS, typename RHS>
2235inline BinaryOp_match<LHS, RHS, Instruction::Mul, true> m_c_Mul(const LHS &L,
2236 const RHS &R) {
2237 return BinaryOp_match<LHS, RHS, Instruction::Mul, true>(L, R);
2238}
2239
2240/// Matches an And with LHS and RHS in either order.
2241template <typename LHS, typename RHS>
2242inline BinaryOp_match<LHS, RHS, Instruction::And, true> m_c_And(const LHS &L,
2243 const RHS &R) {
2244 return BinaryOp_match<LHS, RHS, Instruction::And, true>(L, R);
2245}
2246
2247/// Matches an Or with LHS and RHS in either order.
2248template <typename LHS, typename RHS>
2249inline BinaryOp_match<LHS, RHS, Instruction::Or, true> m_c_Or(const LHS &L,
2250 const RHS &R) {
2251 return BinaryOp_match<LHS, RHS, Instruction::Or, true>(L, R);
2252}
2253
2254/// Matches an Xor with LHS and RHS in either order.
2255template <typename LHS, typename RHS>
2256inline BinaryOp_match<LHS, RHS, Instruction::Xor, true> m_c_Xor(const LHS &L,
2257 const RHS &R) {
2258 return BinaryOp_match<LHS, RHS, Instruction::Xor, true>(L, R);
2259}
2260
2261/// Matches a 'Neg' as 'sub 0, V'.
2262template <typename ValTy>
2263inline BinaryOp_match<cst_pred_ty<is_zero_int>, ValTy, Instruction::Sub>
2264m_Neg(const ValTy &V) {
2265 return m_Sub(m_ZeroInt(), V);
2266}
2267
2268/// Matches a 'Neg' as 'sub nsw 0, V'.
2269template <typename ValTy>
2270inline OverflowingBinaryOp_match<cst_pred_ty<is_zero_int>, ValTy,
2271 Instruction::Sub,
2272 OverflowingBinaryOperator::NoSignedWrap>
2273m_NSWNeg(const ValTy &V) {
2274 return m_NSWSub(m_ZeroInt(), V);
2275}
2276
2277/// Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
2278template <typename ValTy>
2279inline BinaryOp_match<ValTy, cst_pred_ty<is_all_ones>, Instruction::Xor, true>
2280m_Not(const ValTy &V) {
2281 return m_c_Xor(V, m_AllOnes());
2282}
2283
2284/// Matches an SMin with LHS and RHS in either order.
2285template <typename LHS, typename RHS>
2286inline MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty, true>
2287m_c_SMin(const LHS &L, const RHS &R) {
2288 return MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty, true>(L, R);
2289}
2290/// Matches an SMax with LHS and RHS in either order.
2291template <typename LHS, typename RHS>
2292inline MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty, true>
2293m_c_SMax(const LHS &L, const RHS &R) {
2294 return MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty, true>(L, R);
2295}
2296/// Matches a UMin with LHS and RHS in either order.
2297template <typename LHS, typename RHS>
2298inline MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty, true>
2299m_c_UMin(const LHS &L, const RHS &R) {
2300 return MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty, true>(L, R);
2301}
2302/// Matches a UMax with LHS and RHS in either order.
2303template <typename LHS, typename RHS>
2304inline MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty, true>
2305m_c_UMax(const LHS &L, const RHS &R) {
2306 return MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty, true>(L, R);
2307}
2308
2309template <typename LHS, typename RHS>
2310inline match_combine_or<
2311 match_combine_or<MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty, true>,
2312 MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty, true>>,
2313 match_combine_or<MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty, true>,
2314 MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty, true>>>
2315m_c_MaxOrMin(const LHS &L, const RHS &R) {
2316 return m_CombineOr(m_CombineOr(m_c_SMax(L, R), m_c_SMin(L, R)),
2317 m_CombineOr(m_c_UMax(L, R), m_c_UMin(L, R)));
2318}
2319
2320/// Matches FAdd with LHS and RHS in either order.
2321template <typename LHS, typename RHS>
2322inline BinaryOp_match<LHS, RHS, Instruction::FAdd, true>
2323m_c_FAdd(const LHS &L, const RHS &R) {
2324 return BinaryOp_match<LHS, RHS, Instruction::FAdd, true>(L, R);
2325}
2326
2327/// Matches FMul with LHS and RHS in either order.
2328template <typename LHS, typename RHS>
2329inline BinaryOp_match<LHS, RHS, Instruction::FMul, true>
2330m_c_FMul(const LHS &L, const RHS &R) {
2331 return BinaryOp_match<LHS, RHS, Instruction::FMul, true>(L, R);
2332}
2333
2334template <typename Opnd_t> struct Signum_match {
2335 Opnd_t Val;
2336 Signum_match(const Opnd_t &V) : Val(V) {}
2337
2338 template <typename OpTy> bool match(OpTy *V) {
2339 unsigned TypeSize = V->getType()->getScalarSizeInBits();
2340 if (TypeSize == 0)
2341 return false;
2342
2343 unsigned ShiftWidth = TypeSize - 1;
2344 Value *OpL = nullptr, *OpR = nullptr;
2345
2346 // This is the representation of signum we match:
2347 //
2348 // signum(x) == (x >> 63) | (-x >>u 63)
2349 //
2350 // An i1 value is its own signum, so it's correct to match
2351 //
2352 // signum(x) == (x >> 0) | (-x >>u 0)
2353 //
2354 // for i1 values.
2355
2356 auto LHS = m_AShr(m_Value(OpL), m_SpecificInt(ShiftWidth));
2357 auto RHS = m_LShr(m_Neg(m_Value(OpR)), m_SpecificInt(ShiftWidth));
2358 auto Signum = m_Or(LHS, RHS);
2359
2360 return Signum.match(V) && OpL == OpR && Val.match(OpL);
2361 }
2362};
2363
2364/// Matches a signum pattern.
2365///
2366/// signum(x) =
2367/// x > 0 -> 1
2368/// x == 0 -> 0
2369/// x < 0 -> -1
2370template <typename Val_t> inline Signum_match<Val_t> m_Signum(const Val_t &V) {
2371 return Signum_match<Val_t>(V);
2372}
2373
2374template <int Ind, typename Opnd_t> struct ExtractValue_match {
2375 Opnd_t Val;
2376 ExtractValue_match(const Opnd_t &V) : Val(V) {}
2377
2378 template <typename OpTy> bool match(OpTy *V) {
2379 if (auto *I = dyn_cast<ExtractValueInst>(V)) {
2380 // If Ind is -1, don't inspect indices
2381 if (Ind != -1 &&
2382 !(I->getNumIndices() == 1 && I->getIndices()[0] == (unsigned)Ind))
2383 return false;
2384 return Val.match(I->getAggregateOperand());
2385 }
2386 return false;
2387 }
2388};
2389
2390/// Match a single index ExtractValue instruction.
2391/// For example m_ExtractValue<1>(...)
2392template <int Ind, typename Val_t>
2393inline ExtractValue_match<Ind, Val_t> m_ExtractValue(const Val_t &V) {
2394 return ExtractValue_match<Ind, Val_t>(V);
2395}
2396
2397/// Match an ExtractValue instruction with any index.
2398/// For example m_ExtractValue(...)
2399template <typename Val_t>
2400inline ExtractValue_match<-1, Val_t> m_ExtractValue(const Val_t &V) {
2401 return ExtractValue_match<-1, Val_t>(V);
2402}
2403
2404/// Matcher for a single index InsertValue instruction.
2405template <int Ind, typename T0, typename T1> struct InsertValue_match {
2406 T0 Op0;
2407 T1 Op1;
2408
2409 InsertValue_match(const T0 &Op0, const T1 &Op1) : Op0(Op0), Op1(Op1) {}
2410
2411 template <typename OpTy> bool match(OpTy *V) {
2412 if (auto *I = dyn_cast<InsertValueInst>(V)) {
2413 return Op0.match(I->getOperand(0)) && Op1.match(I->getOperand(1)) &&
2414 I->getNumIndices() == 1 && Ind == I->getIndices()[0];
2415 }
2416 return false;
2417 }
2418};
2419
2420/// Matches a single index InsertValue instruction.
2421template <int Ind, typename Val_t, typename Elt_t>
2422inline InsertValue_match<Ind, Val_t, Elt_t> m_InsertValue(const Val_t &Val,
2423 const Elt_t &Elt) {
2424 return InsertValue_match<Ind, Val_t, Elt_t>(Val, Elt);
2425}
2426
2427/// Matches patterns for `vscale`. This can either be a call to `llvm.vscale` or
2428/// the constant expression
2429/// `ptrtoint(gep <vscale x 1 x i8>, <vscale x 1 x i8>* null, i32 1>`
2430/// under the right conditions determined by DataLayout.
2431struct VScaleVal_match {
2432 const DataLayout &DL;
2433 VScaleVal_match(const DataLayout &DL) : DL(DL) {}
2434
2435 template <typename ITy> bool match(ITy *V) {
2436 if (m_Intrinsic<Intrinsic::vscale>().match(V))
2437 return true;
2438
2439 Value *Ptr;
2440 if (m_PtrToInt(m_Value(Ptr)).match(V)) {
2441 if (auto *GEP = dyn_cast<GEPOperator>(Ptr)) {
2442 auto *DerefTy = GEP->getSourceElementType();
2443 if (GEP->getNumIndices() == 1 && isa<ScalableVectorType>(DerefTy) &&
2444 m_Zero().match(GEP->getPointerOperand()) &&
2445 m_SpecificInt(1).match(GEP->idx_begin()->get()) &&
2446 DL.getTypeAllocSizeInBits(DerefTy).getKnownMinSize() == 8)
2447 return true;
2448 }
2449 }
2450
2451 return false;
2452 }
2453};
2454
2455inline VScaleVal_match m_VScale(const DataLayout &DL) {
2456 return VScaleVal_match(DL);
2457}
2458
2459template <typename LHS, typename RHS, unsigned Opcode>
2460struct LogicalOp_match {
2461 LHS L;
2462 RHS R;
2463
2464 LogicalOp_match(const LHS &L, const RHS &R) : L(L), R(R) {}
2465
2466 template <typename T> bool match(T *V) {
2467 if (auto *I = dyn_cast<Instruction>(V)) {
2468 if (!I->getType()->isIntOrIntVectorTy(1))
2469 return false;
2470
2471 if (I->getOpcode() == Opcode && L.match(I->getOperand(0)) &&
2472 R.match(I->getOperand(1)))
2473 return true;
2474
2475 if (auto *SI = dyn_cast<SelectInst>(I)) {
2476 if (Opcode == Instruction::And) {
2477 if (const auto *C = dyn_cast<Constant>(SI->getFalseValue()))
2478 if (C->isNullValue() && L.match(SI->getCondition()) &&
2479 R.match(SI->getTrueValue()))
2480 return true;
2481 } else {
2482 assert(Opcode == Instruction::Or)((void)0);
2483 if (const auto *C = dyn_cast<Constant>(SI->getTrueValue()))
2484 if (C->isOneValue() && L.match(SI->getCondition()) &&
2485 R.match(SI->getFalseValue()))
2486 return true;
2487 }
2488 }
2489 }
2490
2491 return false;
2492 }
2493};
2494
2495/// Matches L && R either in the form of L & R or L ? R : false.
2496/// Note that the latter form is poison-blocking.
2497template <typename LHS, typename RHS>
2498inline LogicalOp_match<LHS, RHS, Instruction::And>
2499m_LogicalAnd(const LHS &L, const RHS &R) {
2500 return LogicalOp_match<LHS, RHS, Instruction::And>(L, R);
2501}
2502
2503/// Matches L && R where L and R are arbitrary values.
2504inline auto m_LogicalAnd() { return m_LogicalAnd(m_Value(), m_Value()); }
2505
2506/// Matches L || R either in the form of L | R or L ? true : R.
2507/// Note that the latter form is poison-blocking.
2508template <typename LHS, typename RHS>
2509inline LogicalOp_match<LHS, RHS, Instruction::Or>
2510m_LogicalOr(const LHS &L, const RHS &R) {
2511 return LogicalOp_match<LHS, RHS, Instruction::Or>(L, R);
2512}
2513
2514/// Matches L || R where L and R are arbitrary values.
2515inline auto m_LogicalOr() {
2516 return m_LogicalOr(m_Value(), m_Value());
2517}
2518
2519} // end namespace PatternMatch
2520} // end namespace llvm
2521
2522#endif // LLVM_IR_PATTERNMATCH_H