Bug Summary

File:llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp
Warning:line 285, column 41
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 -target-cpu x86-64 -dwarf-column-info -fno-split-dwarf-inlining -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~++20200110111110+a1cc19b5814/build-llvm/lib/Target/Hexagon -I /build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/lib/Target/Hexagon -I /build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/build-llvm/include -I /build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/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~++20200110111110+a1cc19b5814/build-llvm/lib/Target/Hexagon -fdebug-prefix-map=/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814=. -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-2020-01-11-115256-23437-1 -x c++ /build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp

/build/llvm-toolchain-snapshot-10~++20200110111110+a1cc19b5814/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 = nullptr;
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
)
18
Assuming 'DebugFlag' is false
19
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())
20
Calling 'operator=='
26
Returning from 'operator=='
27
Taking false branch
249 return false;
250 unsigned Opc = T1I->getOpcode();
251 if (Opc != Hexagon::J2_jumpt && Opc != Hexagon::J2_jumpf)
28
Assuming 'Opc' is equal to J2_jumpt
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;
29
'?' condition is false
30
'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~++20200110111110+a1cc19b5814/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp"
, 262, __PRETTY_FUNCTION__))
;
263 MachineBasicBlock *T2B = (T2I == B->end()) ? NextB
31
'?' condition is true
32
'T2B' initialized to a null pointer value
264 : T2I->getOperand(0).getMBB();
265 if (T1B == T2B) {
33
Assuming 'T1B' is not equal to 'T2B'
34
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
34.1
'Opc' is equal to J2_jumpt
34.1
'Opc' is equal to J2_jumpt
34.1
'Opc' is equal to J2_jumpt
== Hexagon::J2_jumpt)
35
Taking true branch
274 TB = T1B, FB = T2B;
36
Null pointer value stored to 'FB'
275 else
276 TB = T2B, FB = T1B;
277
278 if (!MDT->properlyDominates(B, TB) || !MDT->properlyDominates(B, FB))
37
Assuming the condition is false
38
Assuming the condition is false
39
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();
40
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~++20200110111110+a1cc19b5814/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~++20200110111110+a1cc19b5814/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~++20200110111110+a1cc19b5814/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 equal to 'E'
14
Loop condition is false. Execution continues on line 622
615 MachineBasicBlock *SB = (*I)->getBlock();
616 if (!Deleted.count(SB))
617 Changed |= visitBlock(SB, L);
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)
15
Assuming the condition is false
16
Taking false branch
623 return Changed;
624
625 FlowPattern FP;
626 if (!matchFlowPattern(B, L, FP))
17
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->mayLoadOrStore())
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~++20200110111110+a1cc19b5814/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~++20200110111110+a1cc19b5814/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~++20200110111110+a1cc19b5814/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~++20200110111110+a1cc19b5814/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~++20200110111110+a1cc19b5814/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~++20200110111110+a1cc19b5814/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~++20200110111110+a1cc19b5814/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~++20200110111110+a1cc19b5814/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~++20200110111110+a1cc19b5814/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~++20200110111110+a1cc19b5814/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~++20200110111110+a1cc19b5814/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~++20200110111110+a1cc19b5814/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~++20200110111110+a1cc19b5814/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~++20200110111110+a1cc19b5814/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~++20200110111110+a1cc19b5814/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~++20200110111110+a1cc19b5814/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~++20200110111110+a1cc19b5814/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~++20200110111110+a1cc19b5814/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~++20200110111110+a1cc19b5814/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;
21
Calling 'operator=='
24
Returning from 'operator=='
25
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~++20200110111110+a1cc19b5814/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~++20200110111110+a1cc19b5814/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;
22
Assuming 'LHS.NodePtr' is not equal to 'RHS.NodePtr'
23
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