Bug Summary

File:llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp
Warning:line 285, column 18
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name HexagonEarlyIfConv.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 -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mthread-model posix -mframe-pointer=none -fmath-errno -fno-rounding-math -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-10/lib/clang/10.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/build-llvm/lib/Target/Hexagon -I /build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/Hexagon -I /build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/build-llvm/include -I /build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-10/lib/clang/10.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/build-llvm/lib/Target/Hexagon -fdebug-prefix-map=/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809=. -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -o /tmp/scan-build-2019-12-11-181444-25759-1 -x c++ /build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp

/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp

1//===- HexagonEarlyIfConv.cpp ---------------------------------------------===//
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 implements a Hexagon-specific if-conversion pass that runs on the
10// SSA form.
11// In SSA it is not straightforward to represent instructions that condi-
12// tionally define registers, since a conditionally-defined register may
13// only be used under the same condition on which the definition was based.
14// To avoid complications of this nature, this patch will only generate
15// predicated stores, and speculate other instructions from the "if-conver-
16// ted" block.
17// The code will recognize CFG patterns where a block with a conditional
18// branch "splits" into a "true block" and a "false block". Either of these
19// could be omitted (in case of a triangle, for example).
20// If after conversion of the side block(s) the CFG allows it, the resul-
21// ting blocks may be merged. If the "join" block contained PHI nodes, they
22// will be replaced with MUX (or MUX-like) instructions to maintain the
23// semantics of the PHI.
24//
25// Example:
26//
27// %40 = L2_loadrub_io killed %39, 1
28// %41 = S2_tstbit_i killed %40, 0
29// J2_jumpt killed %41, <%bb.5>, implicit dead %pc
30// J2_jump <%bb.4>, implicit dead %pc
31// Successors according to CFG: %bb.4(62) %bb.5(62)
32//
33// %bb.4: derived from LLVM BB %if.then
34// Predecessors according to CFG: %bb.3
35// %11 = A2_addp %6, %10
36// S2_storerd_io %32, 16, %11
37// Successors according to CFG: %bb.5
38//
39// %bb.5: derived from LLVM BB %if.end
40// Predecessors according to CFG: %bb.3 %bb.4
41// %12 = PHI %6, <%bb.3>, %11, <%bb.4>
42// %13 = A2_addp %7, %12
43// %42 = C2_cmpeqi %9, 10
44// J2_jumpf killed %42, <%bb.3>, implicit dead %pc
45// J2_jump <%bb.6>, implicit dead %pc
46// Successors according to CFG: %bb.6(4) %bb.3(124)
47//
48// would become:
49//
50// %40 = L2_loadrub_io killed %39, 1
51// %41 = S2_tstbit_i killed %40, 0
52// spec-> %11 = A2_addp %6, %10
53// pred-> S2_pstorerdf_io %41, %32, 16, %11
54// %46 = PS_pselect %41, %6, %11
55// %13 = A2_addp %7, %46
56// %42 = C2_cmpeqi %9, 10
57// J2_jumpf killed %42, <%bb.3>, implicit dead %pc
58// J2_jump <%bb.6>, implicit dead %pc
59// Successors according to CFG: %bb.6 %bb.3
60
61#include "Hexagon.h"
62#include "HexagonInstrInfo.h"
63#include "HexagonSubtarget.h"
64#include "llvm/ADT/DenseSet.h"
65#include "llvm/ADT/SmallVector.h"
66#include "llvm/ADT/StringRef.h"
67#include "llvm/ADT/iterator_range.h"
68#include "llvm/CodeGen/MachineBasicBlock.h"
69#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
70#include "llvm/CodeGen/MachineDominators.h"
71#include "llvm/CodeGen/MachineFunction.h"
72#include "llvm/CodeGen/MachineFunctionPass.h"
73#include "llvm/CodeGen/MachineInstr.h"
74#include "llvm/CodeGen/MachineInstrBuilder.h"
75#include "llvm/CodeGen/MachineLoopInfo.h"
76#include "llvm/CodeGen/MachineOperand.h"
77#include "llvm/CodeGen/MachineRegisterInfo.h"
78#include "llvm/CodeGen/TargetRegisterInfo.h"
79#include "llvm/IR/DebugLoc.h"
80#include "llvm/Pass.h"
81#include "llvm/Support/BranchProbability.h"
82#include "llvm/Support/CommandLine.h"
83#include "llvm/Support/Compiler.h"
84#include "llvm/Support/Debug.h"
85#include "llvm/Support/ErrorHandling.h"
86#include "llvm/Support/raw_ostream.h"
87#include <cassert>
88#include <iterator>
89
90#define DEBUG_TYPE"hexagon-eif" "hexagon-eif"
91
92using namespace llvm;
93
94namespace llvm {
95
96 FunctionPass *createHexagonEarlyIfConversion();
97 void initializeHexagonEarlyIfConversionPass(PassRegistry& Registry);
98
99} // end namespace llvm
100
101static cl::opt<bool> EnableHexagonBP("enable-hexagon-br-prob", cl::Hidden,
102 cl::init(true), cl::desc("Enable branch probability info"));
103static cl::opt<unsigned> SizeLimit("eif-limit", cl::init(6), cl::Hidden,
104 cl::desc("Size limit in Hexagon early if-conversion"));
105static cl::opt<bool> SkipExitBranches("eif-no-loop-exit", cl::init(false),
106 cl::Hidden, cl::desc("Do not convert branches that may exit the loop"));
107
108namespace {
109
110 struct PrintMB {
111 PrintMB(const MachineBasicBlock *B) : MB(B) {}
112
113 const MachineBasicBlock *MB;
114 };
115 raw_ostream &operator<< (raw_ostream &OS, const PrintMB &P) {
116 if (!P.MB)
117 return OS << "<none>";
118 return OS << '#' << P.MB->getNumber();
119 }
120
121 struct FlowPattern {
122 FlowPattern() = default;
123 FlowPattern(MachineBasicBlock *B, unsigned PR, MachineBasicBlock *TB,
124 MachineBasicBlock *FB, MachineBasicBlock *JB)
125 : SplitB(B), TrueB(TB), FalseB(FB), JoinB(JB), PredR(PR) {}
126
127 MachineBasicBlock *SplitB = nullptr;
128 MachineBasicBlock *TrueB = nullptr;
129 MachineBasicBlock *FalseB = nullptr;
130 MachineBasicBlock *JoinB = nullptr;
131 unsigned PredR = 0;
132 };
133
134 struct PrintFP {
135 PrintFP(const FlowPattern &P, const TargetRegisterInfo &T)
136 : FP(P), TRI(T) {}
137
138 const FlowPattern &FP;
139 const TargetRegisterInfo &TRI;
140 friend raw_ostream &operator<< (raw_ostream &OS, const PrintFP &P);
141 };
142 raw_ostream &operator<<(raw_ostream &OS,
143 const PrintFP &P) LLVM_ATTRIBUTE_UNUSED__attribute__((__unused__));
144 raw_ostream &operator<<(raw_ostream &OS, const PrintFP &P) {
145 OS << "{ SplitB:" << PrintMB(P.FP.SplitB)
146 << ", PredR:" << printReg(P.FP.PredR, &P.TRI)
147 << ", TrueB:" << PrintMB(P.FP.TrueB)
148 << ", FalseB:" << PrintMB(P.FP.FalseB)
149 << ", JoinB:" << PrintMB(P.FP.JoinB) << " }";
150 return OS;
151 }
152
153 class HexagonEarlyIfConversion : public MachineFunctionPass {
154 public:
155 static char ID;
156
157 HexagonEarlyIfConversion() : MachineFunctionPass(ID) {}
158
159 StringRef getPassName() const override {
160 return "Hexagon early if conversion";
161 }
162
163 void getAnalysisUsage(AnalysisUsage &AU) const override {
164 AU.addRequired<MachineBranchProbabilityInfo>();
165 AU.addRequired<MachineDominatorTree>();
166 AU.addPreserved<MachineDominatorTree>();
167 AU.addRequired<MachineLoopInfo>();
168 MachineFunctionPass::getAnalysisUsage(AU);
169 }
170
171 bool runOnMachineFunction(MachineFunction &MF) override;
172
173 private:
174 using BlockSetType = DenseSet<MachineBasicBlock *>;
175
176 bool isPreheader(const MachineBasicBlock *B) const;
177 bool matchFlowPattern(MachineBasicBlock *B, MachineLoop *L,
178 FlowPattern &FP);
179 bool visitBlock(MachineBasicBlock *B, MachineLoop *L);
180 bool visitLoop(MachineLoop *L);
181
182 bool hasEHLabel(const MachineBasicBlock *B) const;
183 bool hasUncondBranch(const MachineBasicBlock *B) const;
184 bool isValidCandidate(const MachineBasicBlock *B) const;
185 bool usesUndefVReg(const MachineInstr *MI) const;
186 bool isValid(const FlowPattern &FP) const;
187 unsigned countPredicateDefs(const MachineBasicBlock *B) const;
188 unsigned computePhiCost(const MachineBasicBlock *B,
189 const FlowPattern &FP) const;
190 bool isProfitable(const FlowPattern &FP) const;
191 bool isPredicableStore(const MachineInstr *MI) const;
192 bool isSafeToSpeculate(const MachineInstr *MI) const;
193 bool isPredicate(unsigned R) const;
194
195 unsigned getCondStoreOpcode(unsigned Opc, bool IfTrue) const;
196 void predicateInstr(MachineBasicBlock *ToB, MachineBasicBlock::iterator At,
197 MachineInstr *MI, unsigned PredR, bool IfTrue);
198 void predicateBlockNB(MachineBasicBlock *ToB,
199 MachineBasicBlock::iterator At, MachineBasicBlock *FromB,
200 unsigned PredR, bool IfTrue);
201
202 unsigned buildMux(MachineBasicBlock *B, MachineBasicBlock::iterator At,
203 const TargetRegisterClass *DRC, unsigned PredR, unsigned TR,
204 unsigned TSR, unsigned FR, unsigned FSR);
205 void updatePhiNodes(MachineBasicBlock *WhereB, const FlowPattern &FP);
206 void convert(const FlowPattern &FP);
207
208 void removeBlock(MachineBasicBlock *B);
209 void eliminatePhis(MachineBasicBlock *B);
210 void mergeBlocks(MachineBasicBlock *PredB, MachineBasicBlock *SuccB);
211 void simplifyFlowGraph(const FlowPattern &FP);
212
213 const HexagonInstrInfo *HII = nullptr;
214 const TargetRegisterInfo *TRI = nullptr;
215 MachineFunction *MFN = nullptr;
216 MachineRegisterInfo *MRI = nullptr;
217 MachineDominatorTree *MDT = nullptr;
218 MachineLoopInfo *MLI = nullptr;
219 BlockSetType Deleted;
220 const MachineBranchProbabilityInfo *MBPI;
221 };
222
223} // end anonymous namespace
224
225char HexagonEarlyIfConversion::ID = 0;
226
227INITIALIZE_PASS(HexagonEarlyIfConversion, "hexagon-early-if",static void *initializeHexagonEarlyIfConversionPassOnce(PassRegistry
&Registry) { PassInfo *PI = new PassInfo( "Hexagon early if conversion"
, "hexagon-early-if", &HexagonEarlyIfConversion::ID, PassInfo
::NormalCtor_t(callDefaultCtor<HexagonEarlyIfConversion>
), false, false); Registry.registerPass(*PI, true); return PI
; } static llvm::once_flag InitializeHexagonEarlyIfConversionPassFlag
; void llvm::initializeHexagonEarlyIfConversionPass(PassRegistry
&Registry) { llvm::call_once(InitializeHexagonEarlyIfConversionPassFlag
, initializeHexagonEarlyIfConversionPassOnce, std::ref(Registry
)); }
228 "Hexagon early if conversion", false, false)static void *initializeHexagonEarlyIfConversionPassOnce(PassRegistry
&Registry) { PassInfo *PI = new PassInfo( "Hexagon early if conversion"
, "hexagon-early-if", &HexagonEarlyIfConversion::ID, PassInfo
::NormalCtor_t(callDefaultCtor<HexagonEarlyIfConversion>
), false, false); Registry.registerPass(*PI, true); return PI
; } static llvm::once_flag InitializeHexagonEarlyIfConversionPassFlag
; void llvm::initializeHexagonEarlyIfConversionPass(PassRegistry
&Registry) { llvm::call_once(InitializeHexagonEarlyIfConversionPassFlag
, initializeHexagonEarlyIfConversionPassOnce, std::ref(Registry
)); }
229
230bool HexagonEarlyIfConversion::isPreheader(const MachineBasicBlock *B) const {
231 if (B->succ_size() != 1)
232 return false;
233 MachineBasicBlock *SB = *B->succ_begin();
234 MachineLoop *L = MLI->getLoopFor(SB);
235 return L && SB == L->getHeader() && MDT->dominates(B, SB);
236}
237
238bool HexagonEarlyIfConversion::matchFlowPattern(MachineBasicBlock *B,
239 MachineLoop *L, FlowPattern &FP) {
240 LLVM_DEBUG(dbgs() << "Checking flow pattern at " << printMBBReference(*B)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-eif")) { dbgs() << "Checking flow pattern at "
<< printMBBReference(*B) << "\n"; } } while (false
)
23
Assuming 'DebugFlag' is false
24
Loop condition is false. Exiting loop
241 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-eif")) { dbgs() << "Checking flow pattern at "
<< printMBBReference(*B) << "\n"; } } while (false
)
;
242
243 // Interested only in conditional branches, no .new, no new-value, etc.
244 // Check the terminators directly, it's easier than handling all responses
245 // from analyzeBranch.
246 MachineBasicBlock *TB = nullptr, *FB = nullptr;
247 MachineBasicBlock::const_iterator T1I = B->getFirstTerminator();
248 if (T1I == B->end())
25
Calling 'operator=='
31
Returning from 'operator=='
32
Taking false branch
249 return false;
250 unsigned Opc = T1I->getOpcode();
251 if (Opc != Hexagon::J2_jumpt && Opc != Hexagon::J2_jumpf)
33
Assuming 'Opc' is not equal to J2_jumpt
34
Assuming 'Opc' is equal to J2_jumpf
35
Taking false branch
252 return false;
253 Register PredR = T1I->getOperand(0).getReg();
254
255 // Get the layout successor, or 0 if B does not have one.
256 MachineFunction::iterator NextBI = std::next(MachineFunction::iterator(B));
257 MachineBasicBlock *NextB = (NextBI != MFN->end()) ? &*NextBI : nullptr;
36
'?' condition is false
37
'NextB' initialized to a null pointer value
258
259 MachineBasicBlock *T1B = T1I->getOperand(1).getMBB();
260 MachineBasicBlock::const_iterator T2I = std::next(T1I);
261 // The second terminator should be an unconditional branch.
262 assert(T2I == B->end() || T2I->getOpcode() == Hexagon::J2_jump)((T2I == B->end() || T2I->getOpcode() == Hexagon::J2_jump
) ? static_cast<void> (0) : __assert_fail ("T2I == B->end() || T2I->getOpcode() == Hexagon::J2_jump"
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp"
, 262, __PRETTY_FUNCTION__))
;
263 MachineBasicBlock *T2B = (T2I == B->end()) ? NextB
38
'?' condition is true
39
'T2B' initialized to a null pointer value
264 : T2I->getOperand(0).getMBB();
265 if (T1B == T2B) {
40
Assuming 'T1B' is not equal to 'T2B'
41
Taking false branch
266 // XXX merge if T1B == NextB, or convert branch to unconditional.
267 // mark as diamond with both sides equal?
268 return false;
269 }
270
271 // Record the true/false blocks in such a way that "true" means "if (PredR)",
272 // and "false" means "if (!PredR)".
273 if (Opc
41.1
'Opc' is not equal to J2_jumpt
41.1
'Opc' is not equal to J2_jumpt
41.1
'Opc' is not equal to J2_jumpt
== Hexagon::J2_jumpt)
42
Taking false branch
274 TB = T1B, FB = T2B;
275 else
276 TB = T2B, FB = T1B;
43
Null pointer value stored to 'TB'
277
278 if (!MDT->properlyDominates(B, TB) || !MDT->properlyDominates(B, FB))
44
Assuming the condition is false
45
Assuming the condition is false
46
Taking false branch
279 return false;
280
281 // Detect triangle first. In case of a triangle, one of the blocks TB/FB
282 // can fall through into the other, in other words, it will be executed
283 // in both cases. We only want to predicate the block that is executed
284 // conditionally.
285 unsigned TNP = TB->pred_size(), FNP = FB->pred_size();
47
Called C++ object pointer is null
286 unsigned TNS = TB->succ_size(), FNS = FB->succ_size();
287
288 // A block is predicable if it has one predecessor (it must be B), and
289 // it has a single successor. In fact, the block has to end either with
290 // an unconditional branch (which can be predicated), or with a fall-
291 // through.
292 // Also, skip blocks that do not belong to the same loop.
293 bool TOk = (TNP == 1 && TNS == 1 && MLI->getLoopFor(TB) == L);
294 bool FOk = (FNP == 1 && FNS == 1 && MLI->getLoopFor(FB) == L);
295
296 // If requested (via an option), do not consider branches where the
297 // true and false targets do not belong to the same loop.
298 if (SkipExitBranches && MLI->getLoopFor(TB) != MLI->getLoopFor(FB))
299 return false;
300
301 // If neither is predicable, there is nothing interesting.
302 if (!TOk && !FOk)
303 return false;
304
305 MachineBasicBlock *TSB = (TNS > 0) ? *TB->succ_begin() : nullptr;
306 MachineBasicBlock *FSB = (FNS > 0) ? *FB->succ_begin() : nullptr;
307 MachineBasicBlock *JB = nullptr;
308
309 if (TOk) {
310 if (FOk) {
311 if (TSB == FSB)
312 JB = TSB;
313 // Diamond: "if (P) then TB; else FB;".
314 } else {
315 // TOk && !FOk
316 if (TSB == FB)
317 JB = FB;
318 FB = nullptr;
319 }
320 } else {
321 // !TOk && FOk (at least one must be true by now).
322 if (FSB == TB)
323 JB = TB;
324 TB = nullptr;
325 }
326 // Don't try to predicate loop preheaders.
327 if ((TB && isPreheader(TB)) || (FB && isPreheader(FB))) {
328 LLVM_DEBUG(dbgs() << "One of blocks " << PrintMB(TB) << ", " << PrintMB(FB)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-eif")) { dbgs() << "One of blocks " << PrintMB
(TB) << ", " << PrintMB(FB) << " is a loop preheader. Skipping.\n"
; } } while (false)
329 << " is a loop preheader. Skipping.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-eif")) { dbgs() << "One of blocks " << PrintMB
(TB) << ", " << PrintMB(FB) << " is a loop preheader. Skipping.\n"
; } } while (false)
;
330 return false;
331 }
332
333 FP = FlowPattern(B, PredR, TB, FB, JB);
334 LLVM_DEBUG(dbgs() << "Detected " << PrintFP(FP, *TRI) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-eif")) { dbgs() << "Detected " << PrintFP
(FP, *TRI) << "\n"; } } while (false)
;
335 return true;
336}
337
338// KLUDGE: HexagonInstrInfo::analyzeBranch won't work on a block that
339// contains EH_LABEL.
340bool HexagonEarlyIfConversion::hasEHLabel(const MachineBasicBlock *B) const {
341 for (auto &I : *B)
342 if (I.isEHLabel())
343 return true;
344 return false;
345}
346
347// KLUDGE: HexagonInstrInfo::analyzeBranch may be unable to recognize
348// that a block can never fall-through.
349bool HexagonEarlyIfConversion::hasUncondBranch(const MachineBasicBlock *B)
350 const {
351 MachineBasicBlock::const_iterator I = B->getFirstTerminator(), E = B->end();
352 while (I != E) {
353 if (I->isBarrier())
354 return true;
355 ++I;
356 }
357 return false;
358}
359
360bool HexagonEarlyIfConversion::isValidCandidate(const MachineBasicBlock *B)
361 const {
362 if (!B)
363 return true;
364 if (B->isEHPad() || B->hasAddressTaken())
365 return false;
366 if (B->succ_size() == 0)
367 return false;
368
369 for (auto &MI : *B) {
370 if (MI.isDebugInstr())
371 continue;
372 if (MI.isConditionalBranch())
373 return false;
374 unsigned Opc = MI.getOpcode();
375 bool IsJMP = (Opc == Hexagon::J2_jump);
376 if (!isPredicableStore(&MI) && !IsJMP && !isSafeToSpeculate(&MI))
377 return false;
378 // Look for predicate registers defined by this instruction. It's ok
379 // to speculate such an instruction, but the predicate register cannot
380 // be used outside of this block (or else it won't be possible to
381 // update the use of it after predication). PHI uses will be updated
382 // to use a result of a MUX, and a MUX cannot be created for predicate
383 // registers.
384 for (const MachineOperand &MO : MI.operands()) {
385 if (!MO.isReg() || !MO.isDef())
386 continue;
387 Register R = MO.getReg();
388 if (!Register::isVirtualRegister(R))
389 continue;
390 if (!isPredicate(R))
391 continue;
392 for (auto U = MRI->use_begin(R); U != MRI->use_end(); ++U)
393 if (U->getParent()->isPHI())
394 return false;
395 }
396 }
397 return true;
398}
399
400bool HexagonEarlyIfConversion::usesUndefVReg(const MachineInstr *MI) const {
401 for (const MachineOperand &MO : MI->operands()) {
402 if (!MO.isReg() || !MO.isUse())
403 continue;
404 Register R = MO.getReg();
405 if (!Register::isVirtualRegister(R))
406 continue;
407 const MachineInstr *DefI = MRI->getVRegDef(R);
408 // "Undefined" virtual registers are actually defined via IMPLICIT_DEF.
409 assert(DefI && "Expecting a reaching def in MRI")((DefI && "Expecting a reaching def in MRI") ? static_cast
<void> (0) : __assert_fail ("DefI && \"Expecting a reaching def in MRI\""
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp"
, 409, __PRETTY_FUNCTION__))
;
410 if (DefI->isImplicitDef())
411 return true;
412 }
413 return false;
414}
415
416bool HexagonEarlyIfConversion::isValid(const FlowPattern &FP) const {
417 if (hasEHLabel(FP.SplitB)) // KLUDGE: see function definition
418 return false;
419 if (FP.TrueB && !isValidCandidate(FP.TrueB))
420 return false;
421 if (FP.FalseB && !isValidCandidate(FP.FalseB))
422 return false;
423 // Check the PHIs in the join block. If any of them use a register
424 // that is defined as IMPLICIT_DEF, do not convert this. This can
425 // legitimately happen if one side of the split never executes, but
426 // the compiler is unable to prove it. That side may then seem to
427 // provide an "undef" value to the join block, however it will never
428 // execute at run-time. If we convert this case, the "undef" will
429 // be used in a MUX instruction, and that may seem like actually
430 // using an undefined value to other optimizations. This could lead
431 // to trouble further down the optimization stream, cause assertions
432 // to fail, etc.
433 if (FP.JoinB) {
434 const MachineBasicBlock &B = *FP.JoinB;
435 for (auto &MI : B) {
436 if (!MI.isPHI())
437 break;
438 if (usesUndefVReg(&MI))
439 return false;
440 Register DefR = MI.getOperand(0).getReg();
441 if (isPredicate(DefR))
442 return false;
443 }
444 }
445 return true;
446}
447
448unsigned HexagonEarlyIfConversion::computePhiCost(const MachineBasicBlock *B,
449 const FlowPattern &FP) const {
450 if (B->pred_size() < 2)
451 return 0;
452
453 unsigned Cost = 0;
454 for (const MachineInstr &MI : *B) {
455 if (!MI.isPHI())
456 break;
457 // If both incoming blocks are one of the TrueB/FalseB/SplitB, then
458 // a MUX may be needed. Otherwise the PHI will need to be updated at
459 // no extra cost.
460 // Find the interesting PHI operands for further checks.
461 SmallVector<unsigned,2> Inc;
462 for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) {
463 const MachineBasicBlock *BB = MI.getOperand(i+1).getMBB();
464 if (BB == FP.SplitB || BB == FP.TrueB || BB == FP.FalseB)
465 Inc.push_back(i);
466 }
467 assert(Inc.size() <= 2)((Inc.size() <= 2) ? static_cast<void> (0) : __assert_fail
("Inc.size() <= 2", "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp"
, 467, __PRETTY_FUNCTION__))
;
468 if (Inc.size() < 2)
469 continue;
470
471 const MachineOperand &RA = MI.getOperand(1);
472 const MachineOperand &RB = MI.getOperand(3);
473 assert(RA.isReg() && RB.isReg())((RA.isReg() && RB.isReg()) ? static_cast<void>
(0) : __assert_fail ("RA.isReg() && RB.isReg()", "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp"
, 473, __PRETTY_FUNCTION__))
;
474 // Must have a MUX if the phi uses a subregister.
475 if (RA.getSubReg() != 0 || RB.getSubReg() != 0) {
476 Cost++;
477 continue;
478 }
479 const MachineInstr *Def1 = MRI->getVRegDef(RA.getReg());
480 const MachineInstr *Def3 = MRI->getVRegDef(RB.getReg());
481 if (!HII->isPredicable(*Def1) || !HII->isPredicable(*Def3))
482 Cost++;
483 }
484 return Cost;
485}
486
487unsigned HexagonEarlyIfConversion::countPredicateDefs(
488 const MachineBasicBlock *B) const {
489 unsigned PredDefs = 0;
490 for (auto &MI : *B) {
491 for (const MachineOperand &MO : MI.operands()) {
492 if (!MO.isReg() || !MO.isDef())
493 continue;
494 Register R = MO.getReg();
495 if (!Register::isVirtualRegister(R))
496 continue;
497 if (isPredicate(R))
498 PredDefs++;
499 }
500 }
501 return PredDefs;
502}
503
504bool HexagonEarlyIfConversion::isProfitable(const FlowPattern &FP) const {
505 BranchProbability JumpProb(1, 10);
506 BranchProbability Prob(9, 10);
507 if (MBPI && FP.TrueB && !FP.FalseB &&
508 (MBPI->getEdgeProbability(FP.SplitB, FP.TrueB) < JumpProb ||
509 MBPI->getEdgeProbability(FP.SplitB, FP.TrueB) > Prob))
510 return false;
511
512 if (MBPI && !FP.TrueB && FP.FalseB &&
513 (MBPI->getEdgeProbability(FP.SplitB, FP.FalseB) < JumpProb ||
514 MBPI->getEdgeProbability(FP.SplitB, FP.FalseB) > Prob))
515 return false;
516
517 if (FP.TrueB && FP.FalseB) {
518 // Do not IfCovert if the branch is one sided.
519 if (MBPI) {
520 if (MBPI->getEdgeProbability(FP.SplitB, FP.TrueB) > Prob)
521 return false;
522 if (MBPI->getEdgeProbability(FP.SplitB, FP.FalseB) > Prob)
523 return false;
524 }
525
526 // If both sides are predicable, convert them if they join, and the
527 // join block has no other predecessors.
528 MachineBasicBlock *TSB = *FP.TrueB->succ_begin();
529 MachineBasicBlock *FSB = *FP.FalseB->succ_begin();
530 if (TSB != FSB)
531 return false;
532 if (TSB->pred_size() != 2)
533 return false;
534 }
535
536 // Calculate the total size of the predicated blocks.
537 // Assume instruction counts without branches to be the approximation of
538 // the code size. If the predicated blocks are smaller than a packet size,
539 // approximate the spare room in the packet that could be filled with the
540 // predicated/speculated instructions.
541 auto TotalCount = [] (const MachineBasicBlock *B, unsigned &Spare) {
542 if (!B)
543 return 0u;
544 unsigned T = std::count_if(B->begin(), B->getFirstTerminator(),
545 [](const MachineInstr &MI) {
546 return !MI.isMetaInstruction();
547 });
548 if (T < HEXAGON_PACKET_SIZE4)
549 Spare += HEXAGON_PACKET_SIZE4-T;
550 return T;
551 };
552 unsigned Spare = 0;
553 unsigned TotalIn = TotalCount(FP.TrueB, Spare) + TotalCount(FP.FalseB, Spare);
554 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-eif")) { dbgs() << "Total number of instructions to be predicated/speculated: "
<< TotalIn << ", spare room: " << Spare <<
"\n"; } } while (false)
555 dbgs() << "Total number of instructions to be predicated/speculated: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-eif")) { dbgs() << "Total number of instructions to be predicated/speculated: "
<< TotalIn << ", spare room: " << Spare <<
"\n"; } } while (false)
556 << TotalIn << ", spare room: " << Spare << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-eif")) { dbgs() << "Total number of instructions to be predicated/speculated: "
<< TotalIn << ", spare room: " << Spare <<
"\n"; } } while (false)
;
557 if (TotalIn >= SizeLimit+Spare)
558 return false;
559
560 // Count the number of PHI nodes that will need to be updated (converted
561 // to MUX). Those can be later converted to predicated instructions, so
562 // they aren't always adding extra cost.
563 // KLUDGE: Also, count the number of predicate register definitions in
564 // each block. The scheduler may increase the pressure of these and cause
565 // expensive spills (e.g. bitmnp01).
566 unsigned TotalPh = 0;
567 unsigned PredDefs = countPredicateDefs(FP.SplitB);
568 if (FP.JoinB) {
569 TotalPh = computePhiCost(FP.JoinB, FP);
570 PredDefs += countPredicateDefs(FP.JoinB);
571 } else {
572 if (FP.TrueB && FP.TrueB->succ_size() > 0) {
573 MachineBasicBlock *SB = *FP.TrueB->succ_begin();
574 TotalPh += computePhiCost(SB, FP);
575 PredDefs += countPredicateDefs(SB);
576 }
577 if (FP.FalseB && FP.FalseB->succ_size() > 0) {
578 MachineBasicBlock *SB = *FP.FalseB->succ_begin();
579 TotalPh += computePhiCost(SB, FP);
580 PredDefs += countPredicateDefs(SB);
581 }
582 }
583 LLVM_DEBUG(dbgs() << "Total number of extra muxes from converted phis: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-eif")) { dbgs() << "Total number of extra muxes from converted phis: "
<< TotalPh << "\n"; } } while (false)
584 << TotalPh << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-eif")) { dbgs() << "Total number of extra muxes from converted phis: "
<< TotalPh << "\n"; } } while (false)
;
585 if (TotalIn+TotalPh >= SizeLimit+Spare)
586 return false;
587
588 LLVM_DEBUG(dbgs() << "Total number of predicate registers: " << PredDefsdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-eif")) { dbgs() << "Total number of predicate registers: "
<< PredDefs << "\n"; } } while (false)
589 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-eif")) { dbgs() << "Total number of predicate registers: "
<< PredDefs << "\n"; } } while (false)
;
590 if (PredDefs > 4)
591 return false;
592
593 return true;
594}
595
596bool HexagonEarlyIfConversion::visitBlock(MachineBasicBlock *B,
597 MachineLoop *L) {
598 bool Changed = false;
599
600 // Visit all dominated blocks from the same loop first, then process B.
601 MachineDomTreeNode *N = MDT->getNode(B);
602
603 using GTN = GraphTraits<MachineDomTreeNode *>;
604
605 // We will change CFG/DT during this traversal, so take precautions to
606 // avoid problems related to invalidated iterators. In fact, processing
607 // a child C of B cannot cause another child to be removed, but it can
608 // cause a new child to be added (which was a child of C before C itself
609 // was removed. This new child C, however, would have been processed
610 // prior to processing B, so there is no need to process it again.
611 // Simply keep a list of children of B, and traverse that list.
612 using DTNodeVectType = SmallVector<MachineDomTreeNode *, 4>;
613 DTNodeVectType Cn(GTN::child_begin(N), GTN::child_end(N));
614 for (DTNodeVectType::iterator I = Cn.begin(), E = Cn.end(); I != E; ++I) {
13
Assuming 'I' is not equal to 'E'
14
Loop condition is true. Entering loop body
18
Assuming 'I' is equal to 'E'
19
Loop condition is false. Execution continues on line 622
615 MachineBasicBlock *SB = (*I)->getBlock();
616 if (!Deleted.count(SB))
15
Assuming the condition is true
16
Taking true branch
617 Changed |= visitBlock(SB, L);
17
Calling 'HexagonEarlyIfConversion::visitBlock'
618 }
619 // When walking down the dominator tree, we want to traverse through
620 // blocks from nested (other) loops, because they can dominate blocks
621 // that are in L. Skip the non-L blocks only after the tree traversal.
622 if (MLI->getLoopFor(B) != L)
20
Assuming the condition is false
21
Taking false branch
623 return Changed;
624
625 FlowPattern FP;
626 if (!matchFlowPattern(B, L, FP))
22
Calling 'HexagonEarlyIfConversion::matchFlowPattern'
627 return Changed;
628
629 if (!isValid(FP)) {
630 LLVM_DEBUG(dbgs() << "Conversion is not valid\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-eif")) { dbgs() << "Conversion is not valid\n"
; } } while (false)
;
631 return Changed;
632 }
633 if (!isProfitable(FP)) {
634 LLVM_DEBUG(dbgs() << "Conversion is not profitable\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-eif")) { dbgs() << "Conversion is not profitable\n"
; } } while (false)
;
635 return Changed;
636 }
637
638 convert(FP);
639 simplifyFlowGraph(FP);
640 return true;
641}
642
643bool HexagonEarlyIfConversion::visitLoop(MachineLoop *L) {
644 MachineBasicBlock *HB = L
6.1
'L' is null
6.1
'L' is null
6.1
'L' is null
? L->getHeader() : nullptr;
7
'?' condition is false
645 LLVM_DEBUG((L ? dbgs() << "Visiting loop H:" << PrintMB(HB)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-eif")) { (L ? dbgs() << "Visiting loop H:" <<
PrintMB(HB) : dbgs() << "Visiting function") << "\n"
; } } while (false)
8
Assuming 'DebugFlag' is false
9
Loop condition is false. Exiting loop
646 : dbgs() << "Visiting function")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-eif")) { (L ? dbgs() << "Visiting loop H:" <<
PrintMB(HB) : dbgs() << "Visiting function") << "\n"
; } } while (false)
647 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-eif")) { (L ? dbgs() << "Visiting loop H:" <<
PrintMB(HB) : dbgs() << "Visiting function") << "\n"
; } } while (false)
;
648 bool Changed = false;
649 if (L
9.1
'L' is null
9.1
'L' is null
9.1
'L' is null
) {
10
Taking false branch
650 for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I)
651 Changed |= visitLoop(*I);
652 }
653
654 MachineBasicBlock *EntryB = GraphTraits<MachineFunction*>::getEntryNode(MFN);
655 Changed |= visitBlock(L
10.1
'L' is null
10.1
'L' is null
10.1
'L' is null
? HB : EntryB, L)
;
11
'?' condition is false
12
Calling 'HexagonEarlyIfConversion::visitBlock'
656 return Changed;
657}
658
659bool HexagonEarlyIfConversion::isPredicableStore(const MachineInstr *MI)
660 const {
661 // HexagonInstrInfo::isPredicable will consider these stores are non-
662 // -predicable if the offset would become constant-extended after
663 // predication.
664 unsigned Opc = MI->getOpcode();
665 switch (Opc) {
666 case Hexagon::S2_storerb_io:
667 case Hexagon::S2_storerbnew_io:
668 case Hexagon::S2_storerh_io:
669 case Hexagon::S2_storerhnew_io:
670 case Hexagon::S2_storeri_io:
671 case Hexagon::S2_storerinew_io:
672 case Hexagon::S2_storerd_io:
673 case Hexagon::S4_storeirb_io:
674 case Hexagon::S4_storeirh_io:
675 case Hexagon::S4_storeiri_io:
676 return true;
677 }
678
679 // TargetInstrInfo::isPredicable takes a non-const pointer.
680 return MI->mayStore() && HII->isPredicable(const_cast<MachineInstr&>(*MI));
681}
682
683bool HexagonEarlyIfConversion::isSafeToSpeculate(const MachineInstr *MI)
684 const {
685 if (MI->mayLoad() || MI->mayStore())
686 return false;
687 if (MI->isCall() || MI->isBarrier() || MI->isBranch())
688 return false;
689 if (MI->hasUnmodeledSideEffects())
690 return false;
691 if (MI->getOpcode() == TargetOpcode::LIFETIME_END)
692 return false;
693
694 return true;
695}
696
697bool HexagonEarlyIfConversion::isPredicate(unsigned R) const {
698 const TargetRegisterClass *RC = MRI->getRegClass(R);
699 return RC == &Hexagon::PredRegsRegClass ||
700 RC == &Hexagon::HvxQRRegClass;
701}
702
703unsigned HexagonEarlyIfConversion::getCondStoreOpcode(unsigned Opc,
704 bool IfTrue) const {
705 return HII->getCondOpcode(Opc, !IfTrue);
706}
707
708void HexagonEarlyIfConversion::predicateInstr(MachineBasicBlock *ToB,
709 MachineBasicBlock::iterator At, MachineInstr *MI,
710 unsigned PredR, bool IfTrue) {
711 DebugLoc DL;
712 if (At != ToB->end())
713 DL = At->getDebugLoc();
714 else if (!ToB->empty())
715 DL = ToB->back().getDebugLoc();
716
717 unsigned Opc = MI->getOpcode();
718
719 if (isPredicableStore(MI)) {
720 unsigned COpc = getCondStoreOpcode(Opc, IfTrue);
721 assert(COpc)((COpc) ? static_cast<void> (0) : __assert_fail ("COpc"
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp"
, 721, __PRETTY_FUNCTION__))
;
722 MachineInstrBuilder MIB = BuildMI(*ToB, At, DL, HII->get(COpc));
723 MachineInstr::mop_iterator MOI = MI->operands_begin();
724 if (HII->isPostIncrement(*MI)) {
725 MIB.add(*MOI);
726 ++MOI;
727 }
728 MIB.addReg(PredR);
729 for (const MachineOperand &MO : make_range(MOI, MI->operands_end()))
730 MIB.add(MO);
731
732 // Set memory references.
733 MIB.cloneMemRefs(*MI);
734
735 MI->eraseFromParent();
736 return;
737 }
738
739 if (Opc == Hexagon::J2_jump) {
740 MachineBasicBlock *TB = MI->getOperand(0).getMBB();
741 const MCInstrDesc &D = HII->get(IfTrue ? Hexagon::J2_jumpt
742 : Hexagon::J2_jumpf);
743 BuildMI(*ToB, At, DL, D)
744 .addReg(PredR)
745 .addMBB(TB);
746 MI->eraseFromParent();
747 return;
748 }
749
750 // Print the offending instruction unconditionally as we are about to
751 // abort.
752 dbgs() << *MI;
753 llvm_unreachable("Unexpected instruction")::llvm::llvm_unreachable_internal("Unexpected instruction", "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp"
, 753)
;
754}
755
756// Predicate/speculate non-branch instructions from FromB into block ToB.
757// Leave the branches alone, they will be handled later. Btw, at this point
758// FromB should have at most one branch, and it should be unconditional.
759void HexagonEarlyIfConversion::predicateBlockNB(MachineBasicBlock *ToB,
760 MachineBasicBlock::iterator At, MachineBasicBlock *FromB,
761 unsigned PredR, bool IfTrue) {
762 LLVM_DEBUG(dbgs() << "Predicating block " << PrintMB(FromB) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-eif")) { dbgs() << "Predicating block " <<
PrintMB(FromB) << "\n"; } } while (false)
;
763 MachineBasicBlock::iterator End = FromB->getFirstTerminator();
764 MachineBasicBlock::iterator I, NextI;
765
766 for (I = FromB->begin(); I != End; I = NextI) {
767 assert(!I->isPHI())((!I->isPHI()) ? static_cast<void> (0) : __assert_fail
("!I->isPHI()", "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp"
, 767, __PRETTY_FUNCTION__))
;
768 NextI = std::next(I);
769 if (isSafeToSpeculate(&*I))
770 ToB->splice(At, FromB, I);
771 else
772 predicateInstr(ToB, At, &*I, PredR, IfTrue);
773 }
774}
775
776unsigned HexagonEarlyIfConversion::buildMux(MachineBasicBlock *B,
777 MachineBasicBlock::iterator At, const TargetRegisterClass *DRC,
778 unsigned PredR, unsigned TR, unsigned TSR, unsigned FR, unsigned FSR) {
779 unsigned Opc = 0;
780 switch (DRC->getID()) {
781 case Hexagon::IntRegsRegClassID:
782 case Hexagon::IntRegsLow8RegClassID:
783 Opc = Hexagon::C2_mux;
784 break;
785 case Hexagon::DoubleRegsRegClassID:
786 case Hexagon::GeneralDoubleLow8RegsRegClassID:
787 Opc = Hexagon::PS_pselect;
788 break;
789 case Hexagon::HvxVRRegClassID:
790 Opc = Hexagon::PS_vselect;
791 break;
792 case Hexagon::HvxWRRegClassID:
793 Opc = Hexagon::PS_wselect;
794 break;
795 default:
796 llvm_unreachable("unexpected register type")::llvm::llvm_unreachable_internal("unexpected register type",
"/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp"
, 796)
;
797 }
798 const MCInstrDesc &D = HII->get(Opc);
799
800 DebugLoc DL = B->findBranchDebugLoc();
801 Register MuxR = MRI->createVirtualRegister(DRC);
802 BuildMI(*B, At, DL, D, MuxR)
803 .addReg(PredR)
804 .addReg(TR, 0, TSR)
805 .addReg(FR, 0, FSR);
806 return MuxR;
807}
808
809void HexagonEarlyIfConversion::updatePhiNodes(MachineBasicBlock *WhereB,
810 const FlowPattern &FP) {
811 // Visit all PHI nodes in the WhereB block and generate MUX instructions
812 // in the split block. Update the PHI nodes with the values of the MUX.
813 auto NonPHI = WhereB->getFirstNonPHI();
814 for (auto I = WhereB->begin(); I != NonPHI; ++I) {
815 MachineInstr *PN = &*I;
816 // Registers and subregisters corresponding to TrueB, FalseB and SplitB.
817 unsigned TR = 0, TSR = 0, FR = 0, FSR = 0, SR = 0, SSR = 0;
818 for (int i = PN->getNumOperands()-2; i > 0; i -= 2) {
819 const MachineOperand &RO = PN->getOperand(i), &BO = PN->getOperand(i+1);
820 if (BO.getMBB() == FP.SplitB)
821 SR = RO.getReg(), SSR = RO.getSubReg();
822 else if (BO.getMBB() == FP.TrueB)
823 TR = RO.getReg(), TSR = RO.getSubReg();
824 else if (BO.getMBB() == FP.FalseB)
825 FR = RO.getReg(), FSR = RO.getSubReg();
826 else
827 continue;
828 PN->RemoveOperand(i+1);
829 PN->RemoveOperand(i);
830 }
831 if (TR == 0)
832 TR = SR, TSR = SSR;
833 else if (FR == 0)
834 FR = SR, FSR = SSR;
835
836 assert(TR || FR)((TR || FR) ? static_cast<void> (0) : __assert_fail ("TR || FR"
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp"
, 836, __PRETTY_FUNCTION__))
;
837 unsigned MuxR = 0, MuxSR = 0;
838
839 if (TR && FR) {
840 Register DR = PN->getOperand(0).getReg();
841 const TargetRegisterClass *RC = MRI->getRegClass(DR);
842 MuxR = buildMux(FP.SplitB, FP.SplitB->getFirstTerminator(), RC,
843 FP.PredR, TR, TSR, FR, FSR);
844 } else if (TR) {
845 MuxR = TR;
846 MuxSR = TSR;
847 } else {
848 MuxR = FR;
849 MuxSR = FSR;
850 }
851
852 PN->addOperand(MachineOperand::CreateReg(MuxR, false, false, false, false,
853 false, false, MuxSR));
854 PN->addOperand(MachineOperand::CreateMBB(FP.SplitB));
855 }
856}
857
858void HexagonEarlyIfConversion::convert(const FlowPattern &FP) {
859 MachineBasicBlock *TSB = nullptr, *FSB = nullptr;
860 MachineBasicBlock::iterator OldTI = FP.SplitB->getFirstTerminator();
861 assert(OldTI != FP.SplitB->end())((OldTI != FP.SplitB->end()) ? static_cast<void> (0)
: __assert_fail ("OldTI != FP.SplitB->end()", "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp"
, 861, __PRETTY_FUNCTION__))
;
862 DebugLoc DL = OldTI->getDebugLoc();
863
864 if (FP.TrueB) {
865 TSB = *FP.TrueB->succ_begin();
866 predicateBlockNB(FP.SplitB, OldTI, FP.TrueB, FP.PredR, true);
867 }
868 if (FP.FalseB) {
869 FSB = *FP.FalseB->succ_begin();
870 MachineBasicBlock::iterator At = FP.SplitB->getFirstTerminator();
871 predicateBlockNB(FP.SplitB, At, FP.FalseB, FP.PredR, false);
872 }
873
874 // Regenerate new terminators in the split block and update the successors.
875 // First, remember any information that may be needed later and remove the
876 // existing terminators/successors from the split block.
877 MachineBasicBlock *SSB = nullptr;
878 FP.SplitB->erase(OldTI, FP.SplitB->end());
879 while (FP.SplitB->succ_size() > 0) {
880 MachineBasicBlock *T = *FP.SplitB->succ_begin();
881 // It's possible that the split block had a successor that is not a pre-
882 // dicated block. This could only happen if there was only one block to
883 // be predicated. Example:
884 // split_b:
885 // if (p) jump true_b
886 // jump unrelated2_b
887 // unrelated1_b:
888 // ...
889 // unrelated2_b: ; can have other predecessors, so it's not "false_b"
890 // jump other_b
891 // true_b: ; only reachable from split_b, can be predicated
892 // ...
893 //
894 // Find this successor (SSB) if it exists.
895 if (T != FP.TrueB && T != FP.FalseB) {
896 assert(!SSB)((!SSB) ? static_cast<void> (0) : __assert_fail ("!SSB"
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp"
, 896, __PRETTY_FUNCTION__))
;
897 SSB = T;
898 }
899 FP.SplitB->removeSuccessor(FP.SplitB->succ_begin());
900 }
901
902 // Insert new branches and update the successors of the split block. This
903 // may create unconditional branches to the layout successor, etc., but
904 // that will be cleaned up later. For now, make sure that correct code is
905 // generated.
906 if (FP.JoinB) {
907 assert(!SSB || SSB == FP.JoinB)((!SSB || SSB == FP.JoinB) ? static_cast<void> (0) : __assert_fail
("!SSB || SSB == FP.JoinB", "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp"
, 907, __PRETTY_FUNCTION__))
;
908 BuildMI(*FP.SplitB, FP.SplitB->end(), DL, HII->get(Hexagon::J2_jump))
909 .addMBB(FP.JoinB);
910 FP.SplitB->addSuccessor(FP.JoinB);
911 } else {
912 bool HasBranch = false;
913 if (TSB) {
914 BuildMI(*FP.SplitB, FP.SplitB->end(), DL, HII->get(Hexagon::J2_jumpt))
915 .addReg(FP.PredR)
916 .addMBB(TSB);
917 FP.SplitB->addSuccessor(TSB);
918 HasBranch = true;
919 }
920 if (FSB) {
921 const MCInstrDesc &D = HasBranch ? HII->get(Hexagon::J2_jump)
922 : HII->get(Hexagon::J2_jumpf);
923 MachineInstrBuilder MIB = BuildMI(*FP.SplitB, FP.SplitB->end(), DL, D);
924 if (!HasBranch)
925 MIB.addReg(FP.PredR);
926 MIB.addMBB(FSB);
927 FP.SplitB->addSuccessor(FSB);
928 }
929 if (SSB) {
930 // This cannot happen if both TSB and FSB are set. [TF]SB are the
931 // successor blocks of the TrueB and FalseB (or null of the TrueB
932 // or FalseB block is null). SSB is the potential successor block
933 // of the SplitB that is neither TrueB nor FalseB.
934 BuildMI(*FP.SplitB, FP.SplitB->end(), DL, HII->get(Hexagon::J2_jump))
935 .addMBB(SSB);
936 FP.SplitB->addSuccessor(SSB);
937 }
938 }
939
940 // What is left to do is to update the PHI nodes that could have entries
941 // referring to predicated blocks.
942 if (FP.JoinB) {
943 updatePhiNodes(FP.JoinB, FP);
944 } else {
945 if (TSB)
946 updatePhiNodes(TSB, FP);
947 if (FSB)
948 updatePhiNodes(FSB, FP);
949 // Nothing to update in SSB, since SSB's predecessors haven't changed.
950 }
951}
952
953void HexagonEarlyIfConversion::removeBlock(MachineBasicBlock *B) {
954 LLVM_DEBUG(dbgs() << "Removing block " << PrintMB(B) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-eif")) { dbgs() << "Removing block " <<
PrintMB(B) << "\n"; } } while (false)
;
955
956 // Transfer the immediate dominator information from B to its descendants.
957 MachineDomTreeNode *N = MDT->getNode(B);
958 MachineDomTreeNode *IDN = N->getIDom();
959 if (IDN) {
960 MachineBasicBlock *IDB = IDN->getBlock();
961
962 using GTN = GraphTraits<MachineDomTreeNode *>;
963 using DTNodeVectType = SmallVector<MachineDomTreeNode *, 4>;
964
965 DTNodeVectType Cn(GTN::child_begin(N), GTN::child_end(N));
966 for (DTNodeVectType::iterator I = Cn.begin(), E = Cn.end(); I != E; ++I) {
967 MachineBasicBlock *SB = (*I)->getBlock();
968 MDT->changeImmediateDominator(SB, IDB);
969 }
970 }
971
972 while (B->succ_size() > 0)
973 B->removeSuccessor(B->succ_begin());
974
975 for (auto I = B->pred_begin(), E = B->pred_end(); I != E; ++I)
976 (*I)->removeSuccessor(B, true);
977
978 Deleted.insert(B);
979 MDT->eraseNode(B);
980 MFN->erase(B->getIterator());
981}
982
983void HexagonEarlyIfConversion::eliminatePhis(MachineBasicBlock *B) {
984 LLVM_DEBUG(dbgs() << "Removing phi nodes from block " << PrintMB(B) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-eif")) { dbgs() << "Removing phi nodes from block "
<< PrintMB(B) << "\n"; } } while (false)
;
985 MachineBasicBlock::iterator I, NextI, NonPHI = B->getFirstNonPHI();
986 for (I = B->begin(); I != NonPHI; I = NextI) {
987 NextI = std::next(I);
988 MachineInstr *PN = &*I;
989 assert(PN->getNumOperands() == 3 && "Invalid phi node")((PN->getNumOperands() == 3 && "Invalid phi node")
? static_cast<void> (0) : __assert_fail ("PN->getNumOperands() == 3 && \"Invalid phi node\""
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp"
, 989, __PRETTY_FUNCTION__))
;
990 MachineOperand &UO = PN->getOperand(1);
991 Register UseR = UO.getReg(), UseSR = UO.getSubReg();
992 Register DefR = PN->getOperand(0).getReg();
993 unsigned NewR = UseR;
994 if (UseSR) {
995 // MRI.replaceVregUsesWith does not allow to update the subregister,
996 // so instead of doing the use-iteration here, create a copy into a
997 // "non-subregistered" register.
998 const DebugLoc &DL = PN->getDebugLoc();
999 const TargetRegisterClass *RC = MRI->getRegClass(DefR);
1000 NewR = MRI->createVirtualRegister(RC);
1001 NonPHI = BuildMI(*B, NonPHI, DL, HII->get(TargetOpcode::COPY), NewR)
1002 .addReg(UseR, 0, UseSR);
1003 }
1004 MRI->replaceRegWith(DefR, NewR);
1005 B->erase(I);
1006 }
1007}
1008
1009void HexagonEarlyIfConversion::mergeBlocks(MachineBasicBlock *PredB,
1010 MachineBasicBlock *SuccB) {
1011 LLVM_DEBUG(dbgs() << "Merging blocks " << PrintMB(PredB) << " and "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-eif")) { dbgs() << "Merging blocks " <<
PrintMB(PredB) << " and " << PrintMB(SuccB) <<
"\n"; } } while (false)
1012 << PrintMB(SuccB) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-eif")) { dbgs() << "Merging blocks " <<
PrintMB(PredB) << " and " << PrintMB(SuccB) <<
"\n"; } } while (false)
;
1013 bool TermOk = hasUncondBranch(SuccB);
1014 eliminatePhis(SuccB);
1015 HII->removeBranch(*PredB);
1016 PredB->removeSuccessor(SuccB);
1017 PredB->splice(PredB->end(), SuccB, SuccB->begin(), SuccB->end());
1018 PredB->transferSuccessorsAndUpdatePHIs(SuccB);
1019 removeBlock(SuccB);
1020 if (!TermOk)
1021 PredB->updateTerminator();
1022}
1023
1024void HexagonEarlyIfConversion::simplifyFlowGraph(const FlowPattern &FP) {
1025 if (FP.TrueB)
1026 removeBlock(FP.TrueB);
1027 if (FP.FalseB)
1028 removeBlock(FP.FalseB);
1029
1030 FP.SplitB->updateTerminator();
1031 if (FP.SplitB->succ_size() != 1)
1032 return;
1033
1034 MachineBasicBlock *SB = *FP.SplitB->succ_begin();
1035 if (SB->pred_size() != 1)
1036 return;
1037
1038 // By now, the split block has only one successor (SB), and SB has only
1039 // one predecessor. We can try to merge them. We will need to update ter-
1040 // minators in FP.Split+SB, and that requires working analyzeBranch, which
1041 // fails on Hexagon for blocks that have EH_LABELs. However, if SB ends
1042 // with an unconditional branch, we won't need to touch the terminators.
1043 if (!hasEHLabel(SB) || hasUncondBranch(SB))
1044 mergeBlocks(FP.SplitB, SB);
1045}
1046
1047bool HexagonEarlyIfConversion::runOnMachineFunction(MachineFunction &MF) {
1048 if (skipFunction(MF.getFunction()))
1
Assuming the condition is false
2
Taking false branch
1049 return false;
1050
1051 auto &ST = MF.getSubtarget<HexagonSubtarget>();
1052 HII = ST.getInstrInfo();
1053 TRI = ST.getRegisterInfo();
1054 MFN = &MF;
1055 MRI = &MF.getRegInfo();
1056 MDT = &getAnalysis<MachineDominatorTree>();
1057 MLI = &getAnalysis<MachineLoopInfo>();
1058 MBPI = EnableHexagonBP ? &getAnalysis<MachineBranchProbabilityInfo>() :
3
Assuming the condition is false
4
'?' condition is false
1059 nullptr;
1060
1061 Deleted.clear();
1062 bool Changed = false;
1063
1064 for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end(); I != E; ++I)
5
Loop condition is false. Execution continues on line 1066
1065 Changed |= visitLoop(*I);
1066 Changed |= visitLoop(nullptr);
6
Calling 'HexagonEarlyIfConversion::visitLoop'
1067
1068 return Changed;
1069}
1070
1071//===----------------------------------------------------------------------===//
1072// Public Constructor Functions
1073//===----------------------------------------------------------------------===//
1074FunctionPass *llvm::createHexagonEarlyIfConversion() {
1075 return new HexagonEarlyIfConversion();
1076}

/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h

1//===- llvm/CodeGen/MachineInstrBundleIterator.h ----------------*- 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// Defines an iterator class that bundles MachineInstr.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_CODEGEN_MACHINEINSTRBUNDLEITERATOR_H
14#define LLVM_CODEGEN_MACHINEINSTRBUNDLEITERATOR_H
15
16#include "llvm/ADT/ilist.h"
17#include "llvm/ADT/simple_ilist.h"
18#include <cassert>
19#include <iterator>
20#include <type_traits>
21
22namespace llvm {
23
24template <class T, bool IsReverse> struct MachineInstrBundleIteratorTraits;
25template <class T> struct MachineInstrBundleIteratorTraits<T, false> {
26 using list_type = simple_ilist<T, ilist_sentinel_tracking<true>>;
27 using instr_iterator = typename list_type::iterator;
28 using nonconst_instr_iterator = typename list_type::iterator;
29 using const_instr_iterator = typename list_type::const_iterator;
30};
31template <class T> struct MachineInstrBundleIteratorTraits<T, true> {
32 using list_type = simple_ilist<T, ilist_sentinel_tracking<true>>;
33 using instr_iterator = typename list_type::reverse_iterator;
34 using nonconst_instr_iterator = typename list_type::reverse_iterator;
35 using const_instr_iterator = typename list_type::const_reverse_iterator;
36};
37template <class T> struct MachineInstrBundleIteratorTraits<const T, false> {
38 using list_type = simple_ilist<T, ilist_sentinel_tracking<true>>;
39 using instr_iterator = typename list_type::const_iterator;
40 using nonconst_instr_iterator = typename list_type::iterator;
41 using const_instr_iterator = typename list_type::const_iterator;
42};
43template <class T> struct MachineInstrBundleIteratorTraits<const T, true> {
44 using list_type = simple_ilist<T, ilist_sentinel_tracking<true>>;
45 using instr_iterator = typename list_type::const_reverse_iterator;
46 using nonconst_instr_iterator = typename list_type::reverse_iterator;
47 using const_instr_iterator = typename list_type::const_reverse_iterator;
48};
49
50template <bool IsReverse> struct MachineInstrBundleIteratorHelper;
51template <> struct MachineInstrBundleIteratorHelper<false> {
52 /// Get the beginning of the current bundle.
53 template <class Iterator> static Iterator getBundleBegin(Iterator I) {
54 if (!I.isEnd())
55 while (I->isBundledWithPred())
56 --I;
57 return I;
58 }
59
60 /// Get the final node of the current bundle.
61 template <class Iterator> static Iterator getBundleFinal(Iterator I) {
62 if (!I.isEnd())
63 while (I->isBundledWithSucc())
64 ++I;
65 return I;
66 }
67
68 /// Increment forward ilist iterator.
69 template <class Iterator> static void increment(Iterator &I) {
70 I = std::next(getBundleFinal(I));
71 }
72
73 /// Decrement forward ilist iterator.
74 template <class Iterator> static void decrement(Iterator &I) {
75 I = getBundleBegin(std::prev(I));
76 }
77};
78
79template <> struct MachineInstrBundleIteratorHelper<true> {
80 /// Get the beginning of the current bundle.
81 template <class Iterator> static Iterator getBundleBegin(Iterator I) {
82 return MachineInstrBundleIteratorHelper<false>::getBundleBegin(
83 I.getReverse())
84 .getReverse();
85 }
86
87 /// Get the final node of the current bundle.
88 template <class Iterator> static Iterator getBundleFinal(Iterator I) {
89 return MachineInstrBundleIteratorHelper<false>::getBundleFinal(
90 I.getReverse())
91 .getReverse();
92 }
93
94 /// Increment reverse ilist iterator.
95 template <class Iterator> static void increment(Iterator &I) {
96 I = getBundleBegin(std::next(I));
97 }
98
99 /// Decrement reverse ilist iterator.
100 template <class Iterator> static void decrement(Iterator &I) {
101 I = std::prev(getBundleFinal(I));
102 }
103};
104
105/// MachineBasicBlock iterator that automatically skips over MIs that are
106/// inside bundles (i.e. walk top level MIs only).
107template <typename Ty, bool IsReverse = false>
108class MachineInstrBundleIterator : MachineInstrBundleIteratorHelper<IsReverse> {
109 using Traits = MachineInstrBundleIteratorTraits<Ty, IsReverse>;
110 using instr_iterator = typename Traits::instr_iterator;
111
112 instr_iterator MII;
113
114public:
115 using value_type = typename instr_iterator::value_type;
116 using difference_type = typename instr_iterator::difference_type;
117 using pointer = typename instr_iterator::pointer;
118 using reference = typename instr_iterator::reference;
119 using const_pointer = typename instr_iterator::const_pointer;
120 using const_reference = typename instr_iterator::const_reference;
121 using iterator_category = std::bidirectional_iterator_tag;
122
123private:
124 using nonconst_instr_iterator = typename Traits::nonconst_instr_iterator;
125 using const_instr_iterator = typename Traits::const_instr_iterator;
126 using nonconst_iterator =
127 MachineInstrBundleIterator<typename nonconst_instr_iterator::value_type,
128 IsReverse>;
129 using reverse_iterator = MachineInstrBundleIterator<Ty, !IsReverse>;
130
131public:
132 MachineInstrBundleIterator(instr_iterator MI) : MII(MI) {
133 assert((!MI.getNodePtr() || MI.isEnd() || !MI->isBundledWithPred()) &&(((!MI.getNodePtr() || MI.isEnd() || !MI->isBundledWithPred
()) && "It's not legal to initialize MachineInstrBundleIterator with a "
"bundled MI") ? static_cast<void> (0) : __assert_fail (
"(!MI.getNodePtr() || MI.isEnd() || !MI->isBundledWithPred()) && \"It's not legal to initialize MachineInstrBundleIterator with a \" \"bundled MI\""
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h"
, 135, __PRETTY_FUNCTION__))
134 "It's not legal to initialize MachineInstrBundleIterator with a "(((!MI.getNodePtr() || MI.isEnd() || !MI->isBundledWithPred
()) && "It's not legal to initialize MachineInstrBundleIterator with a "
"bundled MI") ? static_cast<void> (0) : __assert_fail (
"(!MI.getNodePtr() || MI.isEnd() || !MI->isBundledWithPred()) && \"It's not legal to initialize MachineInstrBundleIterator with a \" \"bundled MI\""
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h"
, 135, __PRETTY_FUNCTION__))
135 "bundled MI")(((!MI.getNodePtr() || MI.isEnd() || !MI->isBundledWithPred
()) && "It's not legal to initialize MachineInstrBundleIterator with a "
"bundled MI") ? static_cast<void> (0) : __assert_fail (
"(!MI.getNodePtr() || MI.isEnd() || !MI->isBundledWithPred()) && \"It's not legal to initialize MachineInstrBundleIterator with a \" \"bundled MI\""
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h"
, 135, __PRETTY_FUNCTION__))
;
136 }
137
138 MachineInstrBundleIterator(reference MI) : MII(MI) {
139 assert(!MI.isBundledWithPred() && "It's not legal to initialize "((!MI.isBundledWithPred() && "It's not legal to initialize "
"MachineInstrBundleIterator with a " "bundled MI") ? static_cast
<void> (0) : __assert_fail ("!MI.isBundledWithPred() && \"It's not legal to initialize \" \"MachineInstrBundleIterator with a \" \"bundled MI\""
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h"
, 141, __PRETTY_FUNCTION__))
140 "MachineInstrBundleIterator with a "((!MI.isBundledWithPred() && "It's not legal to initialize "
"MachineInstrBundleIterator with a " "bundled MI") ? static_cast
<void> (0) : __assert_fail ("!MI.isBundledWithPred() && \"It's not legal to initialize \" \"MachineInstrBundleIterator with a \" \"bundled MI\""
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h"
, 141, __PRETTY_FUNCTION__))
141 "bundled MI")((!MI.isBundledWithPred() && "It's not legal to initialize "
"MachineInstrBundleIterator with a " "bundled MI") ? static_cast
<void> (0) : __assert_fail ("!MI.isBundledWithPred() && \"It's not legal to initialize \" \"MachineInstrBundleIterator with a \" \"bundled MI\""
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h"
, 141, __PRETTY_FUNCTION__))
;
142 }
143
144 MachineInstrBundleIterator(pointer MI) : MII(MI) {
145 // FIXME: This conversion should be explicit.
146 assert((!MI || !MI->isBundledWithPred()) && "It's not legal to initialize "(((!MI || !MI->isBundledWithPred()) && "It's not legal to initialize "
"MachineInstrBundleIterator " "with a bundled MI") ? static_cast
<void> (0) : __assert_fail ("(!MI || !MI->isBundledWithPred()) && \"It's not legal to initialize \" \"MachineInstrBundleIterator \" \"with a bundled MI\""
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h"
, 148, __PRETTY_FUNCTION__))
147 "MachineInstrBundleIterator "(((!MI || !MI->isBundledWithPred()) && "It's not legal to initialize "
"MachineInstrBundleIterator " "with a bundled MI") ? static_cast
<void> (0) : __assert_fail ("(!MI || !MI->isBundledWithPred()) && \"It's not legal to initialize \" \"MachineInstrBundleIterator \" \"with a bundled MI\""
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h"
, 148, __PRETTY_FUNCTION__))
148 "with a bundled MI")(((!MI || !MI->isBundledWithPred()) && "It's not legal to initialize "
"MachineInstrBundleIterator " "with a bundled MI") ? static_cast
<void> (0) : __assert_fail ("(!MI || !MI->isBundledWithPred()) && \"It's not legal to initialize \" \"MachineInstrBundleIterator \" \"with a bundled MI\""
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h"
, 148, __PRETTY_FUNCTION__))
;
149 }
150
151 // Template allows conversion from const to nonconst.
152 template <class OtherTy>
153 MachineInstrBundleIterator(
154 const MachineInstrBundleIterator<OtherTy, IsReverse> &I,
155 typename std::enable_if<std::is_convertible<OtherTy *, Ty *>::value,
156 void *>::type = nullptr)
157 : MII(I.getInstrIterator()) {}
158
159 MachineInstrBundleIterator() : MII(nullptr) {}
160
161 /// Explicit conversion between forward/reverse iterators.
162 ///
163 /// Translate between forward and reverse iterators without changing range
164 /// boundaries. The resulting iterator will dereference (and have a handle)
165 /// to the previous node, which is somewhat unexpected; but converting the
166 /// two endpoints in a range will give the same range in reverse.
167 ///
168 /// This matches std::reverse_iterator conversions.
169 explicit MachineInstrBundleIterator(
170 const MachineInstrBundleIterator<Ty, !IsReverse> &I)
171 : MachineInstrBundleIterator(++I.getReverse()) {}
172
173 /// Get the bundle iterator for the given instruction's bundle.
174 static MachineInstrBundleIterator getAtBundleBegin(instr_iterator MI) {
175 return MachineInstrBundleIteratorHelper<IsReverse>::getBundleBegin(MI);
176 }
177
178 reference operator*() const { return *MII; }
179 pointer operator->() const { return &operator*(); }
180
181 /// Check for null.
182 bool isValid() const { return MII.getNodePtr(); }
183
184 friend bool operator==(const MachineInstrBundleIterator &L,
185 const MachineInstrBundleIterator &R) {
186 return L.MII == R.MII;
26
Calling 'operator=='
29
Returning from 'operator=='
30
Returning zero, which participates in a condition later
187 }
188 friend bool operator==(const MachineInstrBundleIterator &L,
189 const const_instr_iterator &R) {
190 return L.MII == R; // Avoid assertion about validity of R.
191 }
192 friend bool operator==(const const_instr_iterator &L,
193 const MachineInstrBundleIterator &R) {
194 return L == R.MII; // Avoid assertion about validity of L.
195 }
196 friend bool operator==(const MachineInstrBundleIterator &L,
197 const nonconst_instr_iterator &R) {
198 return L.MII == R; // Avoid assertion about validity of R.
199 }
200 friend bool operator==(const nonconst_instr_iterator &L,
201 const MachineInstrBundleIterator &R) {
202 return L == R.MII; // Avoid assertion about validity of L.
203 }
204 friend bool operator==(const MachineInstrBundleIterator &L, const_pointer R) {
205 return L == const_instr_iterator(R); // Avoid assertion about validity of R.
206 }
207 friend bool operator==(const_pointer L, const MachineInstrBundleIterator &R) {
208 return const_instr_iterator(L) == R; // Avoid assertion about validity of L.
209 }
210 friend bool operator==(const MachineInstrBundleIterator &L,
211 const_reference R) {
212 return L == &R; // Avoid assertion about validity of R.
213 }
214 friend bool operator==(const_reference L,
215 const MachineInstrBundleIterator &R) {
216 return &L == R; // Avoid assertion about validity of L.
217 }
218
219 friend bool operator!=(const MachineInstrBundleIterator &L,
220 const MachineInstrBundleIterator &R) {
221 return !(L == R);
222 }
223 friend bool operator!=(const MachineInstrBundleIterator &L,
224 const const_instr_iterator &R) {
225 return !(L == R);
226 }
227 friend bool operator!=(const const_instr_iterator &L,
228 const MachineInstrBundleIterator &R) {
229 return !(L == R);
230 }
231 friend bool operator!=(const MachineInstrBundleIterator &L,
232 const nonconst_instr_iterator &R) {
233 return !(L == R);
234 }
235 friend bool operator!=(const nonconst_instr_iterator &L,
236 const MachineInstrBundleIterator &R) {
237 return !(L == R);
238 }
239 friend bool operator!=(const MachineInstrBundleIterator &L, const_pointer R) {
240 return !(L == R);
241 }
242 friend bool operator!=(const_pointer L, const MachineInstrBundleIterator &R) {
243 return !(L == R);
244 }
245 friend bool operator!=(const MachineInstrBundleIterator &L,
246 const_reference R) {
247 return !(L == R);
248 }
249 friend bool operator!=(const_reference L,
250 const MachineInstrBundleIterator &R) {
251 return !(L == R);
252 }
253
254 // Increment and decrement operators...
255 MachineInstrBundleIterator &operator--() {
256 this->decrement(MII);
257 return *this;
258 }
259 MachineInstrBundleIterator &operator++() {
260 this->increment(MII);
261 return *this;
262 }
263 MachineInstrBundleIterator operator--(int) {
264 MachineInstrBundleIterator Temp = *this;
265 --*this;
266 return Temp;
267 }
268 MachineInstrBundleIterator operator++(int) {
269 MachineInstrBundleIterator Temp = *this;
270 ++*this;
271 return Temp;
272 }
273
274 instr_iterator getInstrIterator() const { return MII; }
275
276 nonconst_iterator getNonConstIterator() const { return MII.getNonConst(); }
277
278 /// Get a reverse iterator to the same node.
279 ///
280 /// Gives a reverse iterator that will dereference (and have a handle) to the
281 /// same node. Converting the endpoint iterators in a range will give a
282 /// different range; for range operations, use the explicit conversions.
283 reverse_iterator getReverse() const { return MII.getReverse(); }
284};
285
286} // end namespace llvm
287
288#endif // LLVM_CODEGEN_MACHINEINSTRBUNDLEITERATOR_H

/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/ilist_iterator.h

1//===- llvm/ADT/ilist_iterator.h - Intrusive List Iterator ------*- 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#ifndef LLVM_ADT_ILIST_ITERATOR_H
10#define LLVM_ADT_ILIST_ITERATOR_H
11
12#include "llvm/ADT/ilist_node.h"
13#include <cassert>
14#include <cstddef>
15#include <iterator>
16#include <type_traits>
17
18namespace llvm {
19
20namespace ilist_detail {
21
22/// Find const-correct node types.
23template <class OptionsT, bool IsConst> struct IteratorTraits;
24template <class OptionsT> struct IteratorTraits<OptionsT, false> {
25 using value_type = typename OptionsT::value_type;
26 using pointer = typename OptionsT::pointer;
27 using reference = typename OptionsT::reference;
28 using node_pointer = ilist_node_impl<OptionsT> *;
29 using node_reference = ilist_node_impl<OptionsT> &;
30};
31template <class OptionsT> struct IteratorTraits<OptionsT, true> {
32 using value_type = const typename OptionsT::value_type;
33 using pointer = typename OptionsT::const_pointer;
34 using reference = typename OptionsT::const_reference;
35 using node_pointer = const ilist_node_impl<OptionsT> *;
36 using node_reference = const ilist_node_impl<OptionsT> &;
37};
38
39template <bool IsReverse> struct IteratorHelper;
40template <> struct IteratorHelper<false> : ilist_detail::NodeAccess {
41 using Access = ilist_detail::NodeAccess;
42
43 template <class T> static void increment(T *&I) { I = Access::getNext(*I); }
44 template <class T> static void decrement(T *&I) { I = Access::getPrev(*I); }
45};
46template <> struct IteratorHelper<true> : ilist_detail::NodeAccess {
47 using Access = ilist_detail::NodeAccess;
48
49 template <class T> static void increment(T *&I) { I = Access::getPrev(*I); }
50 template <class T> static void decrement(T *&I) { I = Access::getNext(*I); }
51};
52
53} // end namespace ilist_detail
54
55/// Iterator for intrusive lists based on ilist_node.
56template <class OptionsT, bool IsReverse, bool IsConst>
57class ilist_iterator : ilist_detail::SpecificNodeAccess<OptionsT> {
58 friend ilist_iterator<OptionsT, IsReverse, !IsConst>;
59 friend ilist_iterator<OptionsT, !IsReverse, IsConst>;
60 friend ilist_iterator<OptionsT, !IsReverse, !IsConst>;
61
62 using Traits = ilist_detail::IteratorTraits<OptionsT, IsConst>;
63 using Access = ilist_detail::SpecificNodeAccess<OptionsT>;
64
65public:
66 using value_type = typename Traits::value_type;
67 using pointer = typename Traits::pointer;
68 using reference = typename Traits::reference;
69 using difference_type = ptrdiff_t;
70 using iterator_category = std::bidirectional_iterator_tag;
71 using const_pointer = typename OptionsT::const_pointer;
72 using const_reference = typename OptionsT::const_reference;
73
74private:
75 using node_pointer = typename Traits::node_pointer;
76 using node_reference = typename Traits::node_reference;
77
78 node_pointer NodePtr = nullptr;
79
80public:
81 /// Create from an ilist_node.
82 explicit ilist_iterator(node_reference N) : NodePtr(&N) {}
83
84 explicit ilist_iterator(pointer NP) : NodePtr(Access::getNodePtr(NP)) {}
85 explicit ilist_iterator(reference NR) : NodePtr(Access::getNodePtr(&NR)) {}
86 ilist_iterator() = default;
87
88 // This is templated so that we can allow constructing a const iterator from
89 // a nonconst iterator...
90 template <bool RHSIsConst>
91 ilist_iterator(
92 const ilist_iterator<OptionsT, IsReverse, RHSIsConst> &RHS,
93 typename std::enable_if<IsConst || !RHSIsConst, void *>::type = nullptr)
94 : NodePtr(RHS.NodePtr) {}
95
96 // This is templated so that we can allow assigning to a const iterator from
97 // a nonconst iterator...
98 template <bool RHSIsConst>
99 typename std::enable_if<IsConst || !RHSIsConst, ilist_iterator &>::type
100 operator=(const ilist_iterator<OptionsT, IsReverse, RHSIsConst> &RHS) {
101 NodePtr = RHS.NodePtr;
102 return *this;
103 }
104
105 /// Explicit conversion between forward/reverse iterators.
106 ///
107 /// Translate between forward and reverse iterators without changing range
108 /// boundaries. The resulting iterator will dereference (and have a handle)
109 /// to the previous node, which is somewhat unexpected; but converting the
110 /// two endpoints in a range will give the same range in reverse.
111 ///
112 /// This matches std::reverse_iterator conversions.
113 explicit ilist_iterator(
114 const ilist_iterator<OptionsT, !IsReverse, IsConst> &RHS)
115 : ilist_iterator(++RHS.getReverse()) {}
116
117 /// Get a reverse iterator to the same node.
118 ///
119 /// Gives a reverse iterator that will dereference (and have a handle) to the
120 /// same node. Converting the endpoint iterators in a range will give a
121 /// different range; for range operations, use the explicit conversions.
122 ilist_iterator<OptionsT, !IsReverse, IsConst> getReverse() const {
123 if (NodePtr)
124 return ilist_iterator<OptionsT, !IsReverse, IsConst>(*NodePtr);
125 return ilist_iterator<OptionsT, !IsReverse, IsConst>();
126 }
127
128 /// Const-cast.
129 ilist_iterator<OptionsT, IsReverse, false> getNonConst() const {
130 if (NodePtr)
131 return ilist_iterator<OptionsT, IsReverse, false>(
132 const_cast<typename ilist_iterator<OptionsT, IsReverse,
133 false>::node_reference>(*NodePtr));
134 return ilist_iterator<OptionsT, IsReverse, false>();
135 }
136
137 // Accessors...
138 reference operator*() const {
139 assert(!NodePtr->isKnownSentinel())((!NodePtr->isKnownSentinel()) ? static_cast<void> (
0) : __assert_fail ("!NodePtr->isKnownSentinel()", "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/ilist_iterator.h"
, 139, __PRETTY_FUNCTION__))
;
140 return *Access::getValuePtr(NodePtr);
141 }
142 pointer operator->() const { return &operator*(); }
143
144 // Comparison operators
145 friend bool operator==(const ilist_iterator &LHS, const ilist_iterator &RHS) {
146 return LHS.NodePtr == RHS.NodePtr;
27
Assuming 'LHS.NodePtr' is not equal to 'RHS.NodePtr'
28
Returning zero, which participates in a condition later
147 }
148 friend bool operator!=(const ilist_iterator &LHS, const ilist_iterator &RHS) {
149 return LHS.NodePtr != RHS.NodePtr;
150 }
151
152 // Increment and decrement operators...
153 ilist_iterator &operator--() {
154 NodePtr = IsReverse ? NodePtr->getNext() : NodePtr->getPrev();
155 return *this;
156 }
157 ilist_iterator &operator++() {
158 NodePtr = IsReverse ? NodePtr->getPrev() : NodePtr->getNext();
159 return *this;
160 }
161 ilist_iterator operator--(int) {
162 ilist_iterator tmp = *this;
163 --*this;
164 return tmp;
165 }
166 ilist_iterator operator++(int) {
167 ilist_iterator tmp = *this;
168 ++*this;
169 return tmp;
170 }
171
172 /// Get the underlying ilist_node.
173 node_pointer getNodePtr() const { return static_cast<node_pointer>(NodePtr); }
174
175 /// Check for end. Only valid if ilist_sentinel_tracking<true>.
176 bool isEnd() const { return NodePtr ? NodePtr->isSentinel() : false; }
177};
178
179template <typename From> struct simplify_type;
180
181/// Allow ilist_iterators to convert into pointers to a node automatically when
182/// used by the dyn_cast, cast, isa mechanisms...
183///
184/// FIXME: remove this, since there is no implicit conversion to NodeTy.
185template <class OptionsT, bool IsConst>
186struct simplify_type<ilist_iterator<OptionsT, false, IsConst>> {
187 using iterator = ilist_iterator<OptionsT, false, IsConst>;
188 using SimpleType = typename iterator::pointer;
189
190 static SimpleType getSimplifiedValue(const iterator &Node) { return &*Node; }
191};
192template <class OptionsT, bool IsConst>
193struct simplify_type<const ilist_iterator<OptionsT, false, IsConst>>
194 : simplify_type<ilist_iterator<OptionsT, false, IsConst>> {};
195
196} // end namespace llvm
197
198#endif // LLVM_ADT_ILIST_ITERATOR_H