Bug Summary

File:lib/Target/Hexagon/HexagonEarlyIfConv.cpp
Warning:line 286, 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-eagerly-assume -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 -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-7/lib/clang/7.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/lib/Target/Hexagon -I /build/llvm-toolchain-snapshot-7~svn329677/lib/Target/Hexagon -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/include -I /build/llvm-toolchain-snapshot-7~svn329677/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0/backward -internal-isystem /usr/include/clang/7.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-7/lib/clang/7.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++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/lib/Target/Hexagon -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-checker optin.performance.Padding -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-04-11-031539-24776-1 -x c++ /build/llvm-toolchain-snapshot-7~svn329677/lib/Target/Hexagon/HexagonEarlyIfConv.cpp
1//===- HexagonEarlyIfConv.cpp ---------------------------------------------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This implements a Hexagon-specific if-conversion pass that runs on the
11// SSA form.
12// In SSA it is not straightforward to represent instructions that condi-
13// tionally define registers, since a conditionally-defined register may
14// only be used under the same condition on which the definition was based.
15// To avoid complications of this nature, this patch will only generate
16// predicated stores, and speculate other instructions from the "if-conver-
17// ted" block.
18// The code will recognize CFG patterns where a block with a conditional
19// branch "splits" into a "true block" and a "false block". Either of these
20// could be omitted (in case of a triangle, for example).
21// If after conversion of the side block(s) the CFG allows it, the resul-
22// ting blocks may be merged. If the "join" block contained PHI nodes, they
23// will be replaced with MUX (or MUX-like) instructions to maintain the
24// semantics of the PHI.
25//
26// Example:
27//
28// %40 = L2_loadrub_io killed %39, 1
29// %41 = S2_tstbit_i killed %40, 0
30// J2_jumpt killed %41, <%bb.5>, implicit dead %pc
31// J2_jump <%bb.4>, implicit dead %pc
32// Successors according to CFG: %bb.4(62) %bb.5(62)
33//
34// %bb.4: derived from LLVM BB %if.then
35// Predecessors according to CFG: %bb.3
36// %11 = A2_addp %6, %10
37// S2_storerd_io %32, 16, %11
38// Successors according to CFG: %bb.5
39//
40// %bb.5: derived from LLVM BB %if.end
41// Predecessors according to CFG: %bb.3 %bb.4
42// %12 = PHI %6, <%bb.3>, %11, <%bb.4>
43// %13 = A2_addp %7, %12
44// %42 = C2_cmpeqi %9, 10
45// J2_jumpf killed %42, <%bb.3>, implicit dead %pc
46// J2_jump <%bb.6>, implicit dead %pc
47// Successors according to CFG: %bb.6(4) %bb.3(124)
48//
49// would become:
50//
51// %40 = L2_loadrub_io killed %39, 1
52// %41 = S2_tstbit_i killed %40, 0
53// spec-> %11 = A2_addp %6, %10
54// pred-> S2_pstorerdf_io %41, %32, 16, %11
55// %46 = PS_pselect %41, %6, %11
56// %13 = A2_addp %7, %46
57// %42 = C2_cmpeqi %9, 10
58// J2_jumpf killed %42, <%bb.3>, implicit dead %pc
59// J2_jump <%bb.6>, implicit dead %pc
60// Successors according to CFG: %bb.6 %bb.3
61
62#include "Hexagon.h"
63#include "HexagonInstrInfo.h"
64#include "HexagonSubtarget.h"
65#include "llvm/ADT/DenseSet.h"
66#include "llvm/ADT/SmallVector.h"
67#include "llvm/ADT/StringRef.h"
68#include "llvm/ADT/iterator_range.h"
69#include "llvm/CodeGen/MachineBasicBlock.h"
70#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
71#include "llvm/CodeGen/MachineDominators.h"
72#include "llvm/CodeGen/MachineFunction.h"
73#include "llvm/CodeGen/MachineFunctionPass.h"
74#include "llvm/CodeGen/MachineInstr.h"
75#include "llvm/CodeGen/MachineInstrBuilder.h"
76#include "llvm/CodeGen/MachineLoopInfo.h"
77#include "llvm/CodeGen/MachineOperand.h"
78#include "llvm/CodeGen/MachineRegisterInfo.h"
79#include "llvm/CodeGen/TargetRegisterInfo.h"
80#include "llvm/IR/DebugLoc.h"
81#include "llvm/Pass.h"
82#include "llvm/Support/BranchProbability.h"
83#include "llvm/Support/CommandLine.h"
84#include "llvm/Support/Compiler.h"
85#include "llvm/Support/Debug.h"
86#include "llvm/Support/ErrorHandling.h"
87#include "llvm/Support/raw_ostream.h"
88#include <cassert>
89#include <iterator>
90
91#define DEBUG_TYPE"hexagon-eif" "hexagon-eif"
92
93using namespace llvm;
94
95namespace llvm {
96
97 FunctionPass *createHexagonEarlyIfConversion();
98 void initializeHexagonEarlyIfConversionPass(PassRegistry& Registry);
99
100} // end namespace llvm
101
102static cl::opt<bool> EnableHexagonBP("enable-hexagon-br-prob", cl::Hidden,
103 cl::init(true), cl::desc("Enable branch probability info"));
104static cl::opt<unsigned> SizeLimit("eif-limit", cl::init(6), cl::Hidden,
105 cl::desc("Size limit in Hexagon early if-conversion"));
106static cl::opt<bool> SkipExitBranches("eif-no-loop-exit", cl::init(false),
107 cl::Hidden, cl::desc("Do not convert branches that may exit the loop"));
108
109namespace {
110
111 struct PrintMB {
112 PrintMB(const MachineBasicBlock *B) : MB(B) {}
113
114 const MachineBasicBlock *MB;
115 };
116 raw_ostream &operator<< (raw_ostream &OS, const PrintMB &P) {
117 if (!P.MB)
118 return OS << "<none>";
119 return OS << '#' << P.MB->getNumber();
120 }
121
122 struct FlowPattern {
123 FlowPattern() = default;
124 FlowPattern(MachineBasicBlock *B, unsigned PR, MachineBasicBlock *TB,
125 MachineBasicBlock *FB, MachineBasicBlock *JB)
126 : SplitB(B), TrueB(TB), FalseB(FB), JoinB(JB), PredR(PR) {}
127
128 MachineBasicBlock *SplitB = nullptr;
129 MachineBasicBlock *TrueB = nullptr;
130 MachineBasicBlock *FalseB = nullptr;
131 MachineBasicBlock *JoinB = nullptr;
132 unsigned PredR = 0;
133 };
134
135 struct PrintFP {
136 PrintFP(const FlowPattern &P, const TargetRegisterInfo &T)
137 : FP(P), TRI(T) {}
138
139 const FlowPattern &FP;
140 const TargetRegisterInfo &TRI;
141 friend raw_ostream &operator<< (raw_ostream &OS, const PrintFP &P);
142 };
143 raw_ostream &operator<<(raw_ostream &OS,
144 const PrintFP &P) LLVM_ATTRIBUTE_UNUSED__attribute__((__unused__));
145 raw_ostream &operator<<(raw_ostream &OS, const PrintFP &P) {
146 OS << "{ SplitB:" << PrintMB(P.FP.SplitB)
147 << ", PredR:" << printReg(P.FP.PredR, &P.TRI)
148 << ", TrueB:" << PrintMB(P.FP.TrueB)
149 << ", FalseB:" << PrintMB(P.FP.FalseB)
150 << ", JoinB:" << PrintMB(P.FP.JoinB) << " }";
151 return OS;
152 }
153
154 class HexagonEarlyIfConversion : public MachineFunctionPass {
155 public:
156 static char ID;
157
158 HexagonEarlyIfConversion() : MachineFunctionPass(ID) {}
159
160 StringRef getPassName() const override {
161 return "Hexagon early if conversion";
162 }
163
164 void getAnalysisUsage(AnalysisUsage &AU) const override {
165 AU.addRequired<MachineBranchProbabilityInfo>();
166 AU.addRequired<MachineDominatorTree>();
167 AU.addPreserved<MachineDominatorTree>();
168 AU.addRequired<MachineLoopInfo>();
169 MachineFunctionPass::getAnalysisUsage(AU);
170 }
171
172 bool runOnMachineFunction(MachineFunction &MF) override;
173
174 private:
175 using BlockSetType = DenseSet<MachineBasicBlock *>;
176
177 bool isPreheader(const MachineBasicBlock *B) const;
178 bool matchFlowPattern(MachineBasicBlock *B, MachineLoop *L,
179 FlowPattern &FP);
180 bool visitBlock(MachineBasicBlock *B, MachineLoop *L);
181 bool visitLoop(MachineLoop *L);
182
183 bool hasEHLabel(const MachineBasicBlock *B) const;
184 bool hasUncondBranch(const MachineBasicBlock *B) const;
185 bool isValidCandidate(const MachineBasicBlock *B) const;
186 bool usesUndefVReg(const MachineInstr *MI) const;
187 bool isValid(const FlowPattern &FP) const;
188 unsigned countPredicateDefs(const MachineBasicBlock *B) const;
189 unsigned computePhiCost(const MachineBasicBlock *B,
190 const FlowPattern &FP) const;
191 bool isProfitable(const FlowPattern &FP) const;
192 bool isPredicableStore(const MachineInstr *MI) const;
193 bool isSafeToSpeculate(const MachineInstr *MI) const;
194 bool isPredicate(unsigned R) const;
195
196 unsigned getCondStoreOpcode(unsigned Opc, bool IfTrue) const;
197 void predicateInstr(MachineBasicBlock *ToB, MachineBasicBlock::iterator At,
198 MachineInstr *MI, unsigned PredR, bool IfTrue);
199 void predicateBlockNB(MachineBasicBlock *ToB,
200 MachineBasicBlock::iterator At, MachineBasicBlock *FromB,
201 unsigned PredR, bool IfTrue);
202
203 unsigned buildMux(MachineBasicBlock *B, MachineBasicBlock::iterator At,
204 const TargetRegisterClass *DRC, unsigned PredR, unsigned TR,
205 unsigned TSR, unsigned FR, unsigned FSR);
206 void updatePhiNodes(MachineBasicBlock *WhereB, const FlowPattern &FP);
207 void convert(const FlowPattern &FP);
208
209 void removeBlock(MachineBasicBlock *B);
210 void eliminatePhis(MachineBasicBlock *B);
211 void replacePhiEdges(MachineBasicBlock *OldB, MachineBasicBlock *NewB);
212 void mergeBlocks(MachineBasicBlock *PredB, MachineBasicBlock *SuccB);
213 void simplifyFlowGraph(const FlowPattern &FP);
214
215 const HexagonInstrInfo *HII = nullptr;
216 const TargetRegisterInfo *TRI = nullptr;
217 MachineFunction *MFN = nullptr;
218 MachineRegisterInfo *MRI = nullptr;
219 MachineDominatorTree *MDT = nullptr;
220 MachineLoopInfo *MLI = nullptr;
221 BlockSetType Deleted;
222 const MachineBranchProbabilityInfo *MBPI;
223 };
224
225} // end anonymous namespace
226
227char HexagonEarlyIfConversion::ID = 0;
228
229INITIALIZE_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
)); }
230 "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
)); }
231
232bool HexagonEarlyIfConversion::isPreheader(const MachineBasicBlock *B) const {
233 if (B->succ_size() != 1)
234 return false;
235 MachineBasicBlock *SB = *B->succ_begin();
236 MachineLoop *L = MLI->getLoopFor(SB);
237 return L && SB == L->getHeader() && MDT->dominates(B, SB);
238}
239
240bool HexagonEarlyIfConversion::matchFlowPattern(MachineBasicBlock *B,
241 MachineLoop *L, FlowPattern &FP) {
242 DEBUG(dbgs() << "Checking flow pattern at " << printMBBReference(*B) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-eif")) { dbgs() << "Checking flow pattern at "
<< printMBBReference(*B) << "\n"; } } while (false
);
243
244 // Interested only in conditional branches, no .new, no new-value, etc.
245 // Check the terminators directly, it's easier than handling all responses
246 // from analyzeBranch.
247 MachineBasicBlock *TB = nullptr, *FB = nullptr;
248 MachineBasicBlock::const_iterator T1I = B->getFirstTerminator();
249 if (T1I == B->end())
22
←
Taking false branch
→
250 return false;
251 unsigned Opc = T1I->getOpcode();
252 if (Opc != Hexagon::J2_jumpt && Opc != Hexagon::J2_jumpf)
23
←
Assuming 'Opc' is equal to J2_jumpt
→
253 return false;
254 unsigned PredR = T1I->getOperand(0).getReg();
255
256 // Get the layout successor, or 0 if B does not have one.
257 MachineFunction::iterator NextBI = std::next(MachineFunction::iterator(B));
258 MachineBasicBlock *NextB = (NextBI != MFN->end()) ? &*NextBI : nullptr;
24
←
'?' condition is false
→
25
←
'NextB' initialized to a null pointer value
→
259
260 MachineBasicBlock *T1B = T1I->getOperand(1).getMBB();
261 MachineBasicBlock::const_iterator T2I = std::next(T1I);
262 // The second terminator should be an unconditional branch.
263 assert(T2I == B->end() || T2I->getOpcode() == Hexagon::J2_jump)(static_cast <bool> (T2I == B->end() || T2I->getOpcode
() == Hexagon::J2_jump) ? void (0) : __assert_fail ("T2I == B->end() || T2I->getOpcode() == Hexagon::J2_jump"
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Target/Hexagon/HexagonEarlyIfConv.cpp"
, 263, __extension__ __PRETTY_FUNCTION__));
264 MachineBasicBlock *T2B = (T2I == B->end()) ? NextB
26
←
'?' condition is true
→
27
←
'T2B' initialized to a null pointer value
→
265 : T2I->getOperand(0).getMBB();
266 if (T1B == T2B) {
28
←
Assuming 'T1B' is not equal to 'T2B'
→
29
←
Taking false branch
→
267 // XXX merge if T1B == NextB, or convert branch to unconditional.
268 // mark as diamond with both sides equal?
269 return false;
270 }
271
272 // Record the true/false blocks in such a way that "true" means "if (PredR)",
273 // and "false" means "if (!PredR)".
274 if (Opc == Hexagon::J2_jumpt)
30
←
Taking true branch
→
275 TB = T1B, FB = T2B;
31
←
Null pointer value stored to 'FB'
→
276 else
277 TB = T2B, FB = T1B;
278
279 if (!MDT->properlyDominates(B, TB) || !MDT->properlyDominates(B, FB))
32
←
Assuming the condition is false
→
33
←
Assuming the condition is false
→
34
←
Taking false branch
→
280 return false;
281
282 // Detect triangle first. In case of a triangle, one of the blocks TB/FB
283 // can fall through into the other, in other words, it will be executed
284 // in both cases. We only want to predicate the block that is executed
285 // conditionally.
286 unsigned TNP = TB->pred_size(), FNP = FB->pred_size();
35
←
Called C++ object pointer is null
287 unsigned TNS = TB->succ_size(), FNS = FB->succ_size();
288
289 // A block is predicable if it has one predecessor (it must be B), and
290 // it has a single successor. In fact, the block has to end either with
291 // an unconditional branch (which can be predicated), or with a fall-
292 // through.
293 // Also, skip blocks that do not belong to the same loop.
294 bool TOk = (TNP == 1 && TNS == 1 && MLI->getLoopFor(TB) == L);
295 bool FOk = (FNP == 1 && FNS == 1 && MLI->getLoopFor(FB) == L);
296
297 // If requested (via an option), do not consider branches where the
298 // true and false targets do not belong to the same loop.
299 if (SkipExitBranches && MLI->getLoopFor(TB) != MLI->getLoopFor(FB))
300 return false;
301
302 // If neither is predicable, there is nothing interesting.
303 if (!TOk && !FOk)
304 return false;
305
306 MachineBasicBlock *TSB = (TNS > 0) ? *TB->succ_begin() : nullptr;
307 MachineBasicBlock *FSB = (FNS > 0) ? *FB->succ_begin() : nullptr;
308 MachineBasicBlock *JB = nullptr;
309
310 if (TOk) {
311 if (FOk) {
312 if (TSB == FSB)
313 JB = TSB;
314 // Diamond: "if (P) then TB; else FB;".
315 } else {
316 // TOk && !FOk
317 if (TSB == FB)
318 JB = FB;
319 FB = nullptr;
320 }
321 } else {
322 // !TOk && FOk (at least one must be true by now).
323 if (FSB == TB)
324 JB = TB;
325 TB = nullptr;
326 }
327 // Don't try to predicate loop preheaders.
328 if ((TB && isPreheader(TB)) || (FB && isPreheader(FB))) {
329 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)
330 << " 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);
331 return false;
332 }
333
334 FP = FlowPattern(B, PredR, TB, FB, JB);
335 DEBUG(dbgs() << "Detected " << PrintFP(FP, *TRI) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-eif")) { dbgs() << "Detected " << PrintFP
(FP, *TRI) << "\n"; } } while (false);
336 return true;
337}
338
339// KLUDGE: HexagonInstrInfo::analyzeBranch won't work on a block that
340// contains EH_LABEL.
341bool HexagonEarlyIfConversion::hasEHLabel(const MachineBasicBlock *B) const {
342 for (auto &I : *B)
343 if (I.isEHLabel())
344 return true;
345 return false;
346}
347
348// KLUDGE: HexagonInstrInfo::analyzeBranch may be unable to recognize
349// that a block can never fall-through.
350bool HexagonEarlyIfConversion::hasUncondBranch(const MachineBasicBlock *B)
351 const {
352 MachineBasicBlock::const_iterator I = B->getFirstTerminator(), E = B->end();
353 while (I != E) {
354 if (I->isBarrier())
355 return true;
356 ++I;
357 }
358 return false;
359}
360
361bool HexagonEarlyIfConversion::isValidCandidate(const MachineBasicBlock *B)
362 const {
363 if (!B)
364 return true;
365 if (B->isEHPad() || B->hasAddressTaken())
366 return false;
367 if (B->succ_size() == 0)
368 return false;
369
370 for (auto &MI : *B) {
371 if (MI.isDebugValue())
372 continue;
373 if (MI.isConditionalBranch())
374 return false;
375 unsigned Opc = MI.getOpcode();
376 bool IsJMP = (Opc == Hexagon::J2_jump);
377 if (!isPredicableStore(&MI) && !IsJMP && !isSafeToSpeculate(&MI))
378 return false;
379 // Look for predicate registers defined by this instruction. It's ok
380 // to speculate such an instruction, but the predicate register cannot
381 // be used outside of this block (or else it won't be possible to
382 // update the use of it after predication). PHI uses will be updated
383 // to use a result of a MUX, and a MUX cannot be created for predicate
384 // registers.
385 for (const MachineOperand &MO : MI.operands()) {
386 if (!MO.isReg() || !MO.isDef())
387 continue;
388 unsigned R = MO.getReg();
389 if (!TargetRegisterInfo::isVirtualRegister(R))
390 continue;
391 if (!isPredicate(R))
392 continue;
393 for (auto U = MRI->use_begin(R); U != MRI->use_end(); ++U)
394 if (U->getParent()->isPHI())
395 return false;
396 }
397 }
398 return true;
399}
400
401bool HexagonEarlyIfConversion::usesUndefVReg(const MachineInstr *MI) const {
402 for (const MachineOperand &MO : MI->operands()) {
403 if (!MO.isReg() || !MO.isUse())
404 continue;
405 unsigned R = MO.getReg();
406 if (!TargetRegisterInfo::isVirtualRegister(R))
407 continue;
408 const MachineInstr *DefI = MRI->getVRegDef(R);
409 // "Undefined" virtual registers are actually defined via IMPLICIT_DEF.
410 assert(DefI && "Expecting a reaching def in MRI")(static_cast <bool> (DefI && "Expecting a reaching def in MRI"
) ? void (0) : __assert_fail ("DefI && \"Expecting a reaching def in MRI\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Target/Hexagon/HexagonEarlyIfConv.cpp"
, 410, __extension__ __PRETTY_FUNCTION__));
411 if (DefI->isImplicitDef())
412 return true;
413 }
414 return false;
415}
416
417bool HexagonEarlyIfConversion::isValid(const FlowPattern &FP) const {
418 if (hasEHLabel(FP.SplitB)) // KLUDGE: see function definition
419 return false;
420 if (FP.TrueB && !isValidCandidate(FP.TrueB))
421 return false;
422 if (FP.FalseB && !isValidCandidate(FP.FalseB))
423 return false;
424 // Check the PHIs in the join block. If any of them use a register
425 // that is defined as IMPLICIT_DEF, do not convert this. This can
426 // legitimately happen if one side of the split never executes, but
427 // the compiler is unable to prove it. That side may then seem to
428 // provide an "undef" value to the join block, however it will never
429 // execute at run-time. If we convert this case, the "undef" will
430 // be used in a MUX instruction, and that may seem like actually
431 // using an undefined value to other optimizations. This could lead
432 // to trouble further down the optimization stream, cause assertions
433 // to fail, etc.
434 if (FP.JoinB) {
435 const MachineBasicBlock &B = *FP.JoinB;
436 for (auto &MI : B) {
437 if (!MI.isPHI())
438 break;
439 if (usesUndefVReg(&MI))
440 return false;
441 unsigned DefR = MI.getOperand(0).getReg();
442 if (isPredicate(DefR))
443 return false;
444 }
445 }
446 return true;
447}
448
449unsigned HexagonEarlyIfConversion::computePhiCost(const MachineBasicBlock *B,
450 const FlowPattern &FP) const {
451 if (B->pred_size() < 2)
452 return 0;
453
454 unsigned Cost = 0;
455 for (const MachineInstr &MI : *B) {
456 if (!MI.isPHI())
457 break;
458 // If both incoming blocks are one of the TrueB/FalseB/SplitB, then
459 // a MUX may be needed. Otherwise the PHI will need to be updated at
460 // no extra cost.
461 // Find the interesting PHI operands for further checks.
462 SmallVector<unsigned,2> Inc;
463 for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) {
464 const MachineBasicBlock *BB = MI.getOperand(i+1).getMBB();
465 if (BB == FP.SplitB || BB == FP.TrueB || BB == FP.FalseB)
466 Inc.push_back(i);
467 }
468 assert(Inc.size() <= 2)(static_cast <bool> (Inc.size() <= 2) ? void (0) : __assert_fail
("Inc.size() <= 2", "/build/llvm-toolchain-snapshot-7~svn329677/lib/Target/Hexagon/HexagonEarlyIfConv.cpp"
, 468, __extension__ __PRETTY_FUNCTION__));
469 if (Inc.size() < 2)
470 continue;
471
472 const MachineOperand &RA = MI.getOperand(1);
473 const MachineOperand &RB = MI.getOperand(3);
474 assert(RA.isReg() && RB.isReg())(static_cast <bool> (RA.isReg() && RB.isReg()) ?
void (0) : __assert_fail ("RA.isReg() && RB.isReg()"
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Target/Hexagon/HexagonEarlyIfConv.cpp"
, 474, __extension__ __PRETTY_FUNCTION__));
475 // Must have a MUX if the phi uses a subregister.
476 if (RA.getSubReg() != 0 || RB.getSubReg() != 0) {
477 Cost++;
478 continue;
479 }
480 const MachineInstr *Def1 = MRI->getVRegDef(RA.getReg());
481 const MachineInstr *Def3 = MRI->getVRegDef(RB.getReg());
482 if (!HII->isPredicable(*Def1) || !HII->isPredicable(*Def3))
483 Cost++;
484 }
485 return Cost;
486}
487
488unsigned HexagonEarlyIfConversion::countPredicateDefs(
489 const MachineBasicBlock *B) const {
490 unsigned PredDefs = 0;
491 for (auto &MI : *B) {
492 for (const MachineOperand &MO : MI.operands()) {
493 if (!MO.isReg() || !MO.isDef())
494 continue;
495 unsigned R = MO.getReg();
496 if (!TargetRegisterInfo::isVirtualRegister(R))
497 continue;
498 if (isPredicate(R))
499 PredDefs++;
500 }
501 }
502 return PredDefs;
503}
504
505bool HexagonEarlyIfConversion::isProfitable(const FlowPattern &FP) const {
506 BranchProbability JumpProb(1, 10);
507 BranchProbability Prob(9, 10);
508 if (MBPI && FP.TrueB && !FP.FalseB &&
509 (MBPI->getEdgeProbability(FP.SplitB, FP.TrueB) < JumpProb ||
510 MBPI->getEdgeProbability(FP.SplitB, FP.TrueB) > Prob))
511 return false;
512
513 if (MBPI && !FP.TrueB && FP.FalseB &&
514 (MBPI->getEdgeProbability(FP.SplitB, FP.FalseB) < JumpProb ||
515 MBPI->getEdgeProbability(FP.SplitB, FP.FalseB) > Prob))
516 return false;
517
518 if (FP.TrueB && FP.FalseB) {
519 // Do not IfCovert if the branch is one sided.
520 if (MBPI) {
521 if (MBPI->getEdgeProbability(FP.SplitB, FP.TrueB) > Prob)
522 return false;
523 if (MBPI->getEdgeProbability(FP.SplitB, FP.FalseB) > Prob)
524 return false;
525 }
526
527 // If both sides are predicable, convert them if they join, and the
528 // join block has no other predecessors.
529 MachineBasicBlock *TSB = *FP.TrueB->succ_begin();
530 MachineBasicBlock *FSB = *FP.FalseB->succ_begin();
531 if (TSB != FSB)
532 return false;
533 if (TSB->pred_size() != 2)
534 return false;
535 }
536
537 // Calculate the total size of the predicated blocks.
538 // Assume instruction counts without branches to be the approximation of
539 // the code size. If the predicated blocks are smaller than a packet size,
540 // approximate the spare room in the packet that could be filled with the
541 // predicated/speculated instructions.
542 auto TotalCount = [] (const MachineBasicBlock *B, unsigned &Spare) {
543 if (!B)
544 return 0u;
545 unsigned T = std::count_if(B->begin(), B->getFirstTerminator(),
546 [](const MachineInstr &MI) {
547 return !MI.isMetaInstruction();
548 });
549 if (T < HEXAGON_PACKET_SIZE4)
550 Spare += HEXAGON_PACKET_SIZE4-T;
551 return T;
552 };
553 unsigned Spare = 0;
554 unsigned TotalIn = TotalCount(FP.TrueB, Spare) + TotalCount(FP.FalseB, Spare);
555 DEBUG(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 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 DEBUG(dbgs() << "Total number of predicate registers: " << PredDefs << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-eif")) { dbgs() << "Total number of predicate registers: "
<< PredDefs << "\n"; } } while (false);
589 if (PredDefs > 4)
590 return false;
591
592 return true;
593}
594
595bool HexagonEarlyIfConversion::visitBlock(MachineBasicBlock *B,
596 MachineLoop *L) {
597 bool Changed = false;
598
599 // Visit all dominated blocks from the same loop first, then process B.
600 MachineDomTreeNode *N = MDT->getNode(B);
601
602 using GTN = GraphTraits<MachineDomTreeNode *>;
603
604 // We will change CFG/DT during this traversal, so take precautions to
605 // avoid problems related to invalidated iterators. In fact, processing
606 // a child C of B cannot cause another child to be removed, but it can
607 // cause a new child to be added (which was a child of C before C itself
608 // was removed. This new child C, however, would have been processed
609 // prior to processing B, so there is no need to process it again.
610 // Simply keep a list of children of B, and traverse that list.
611 using DTNodeVectType = SmallVector<MachineDomTreeNode *, 4>;
612 DTNodeVectType Cn(GTN::child_begin(N), GTN::child_end(N));
613 for (DTNodeVectType::iterator I = Cn.begin(), E = Cn.end(); I != E; ++I) {
17
←
Assuming 'I' is equal to 'E'
→
18
←
Loop condition is false. Execution continues on line 621
→
614 MachineBasicBlock *SB = (*I)->getBlock();
615 if (!Deleted.count(SB))
616 Changed |= visitBlock(SB, L);
617 }
618 // When walking down the dominator tree, we want to traverse through
619 // blocks from nested (other) loops, because they can dominate blocks
620 // that are in L. Skip the non-L blocks only after the tree traversal.
621 if (MLI->getLoopFor(B) != L)
19
←
Assuming the condition is false
→
20
←
Taking false branch
→
622 return Changed;
623
624 FlowPattern FP;
625 if (!matchFlowPattern(B, L, FP))
21
←
Calling 'HexagonEarlyIfConversion::matchFlowPattern'
→
626 return Changed;
627
628 if (!isValid(FP)) {
629 DEBUG(dbgs() << "Conversion is not valid\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-eif")) { dbgs() << "Conversion is not valid\n"
; } } while (false);
630 return Changed;
631 }
632 if (!isProfitable(FP)) {
633 DEBUG(dbgs() << "Conversion is not profitable\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-eif")) { dbgs() << "Conversion is not profitable\n"
; } } while (false);
634 return Changed;
635 }
636
637 convert(FP);
638 simplifyFlowGraph(FP);
639 return true;
640}
641
642bool HexagonEarlyIfConversion::visitLoop(MachineLoop *L) {
643 MachineBasicBlock *HB = L ? L->getHeader() : nullptr;
7
←
Assuming 'L' is non-null
→
8
←
'?' condition is true
→
12
←
Assuming 'L' is null
→
13
←
'?' condition is false
→
644 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)
645 : dbgs() << "Visiting function") << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-eif")) { (L ? dbgs() << "Visiting loop H:" <<
PrintMB(HB) : dbgs() << "Visiting function") << "\n"
; } } while (false);
646 bool Changed = false;
647 if (L) {
9
←
Taking true branch
→
14
←
Taking false branch
→
648 for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I)
10
←
Loop condition is true. Entering loop body
→
649 Changed |= visitLoop(*I);
11
←
Calling 'HexagonEarlyIfConversion::visitLoop'
→
650 }
651
652 MachineBasicBlock *EntryB = GraphTraits<MachineFunction*>::getEntryNode(MFN);
653 Changed |= visitBlock(L ? HB : EntryB, L);
15
←
'?' condition is false
→
16
←
Calling 'HexagonEarlyIfConversion::visitBlock'
→
654 return Changed;
655}
656
657bool HexagonEarlyIfConversion::isPredicableStore(const MachineInstr *MI)
658 const {
659 // HexagonInstrInfo::isPredicable will consider these stores are non-
660 // -predicable if the offset would become constant-extended after
661 // predication.
662 unsigned Opc = MI->getOpcode();
663 switch (Opc) {
664 case Hexagon::S2_storerb_io:
665 case Hexagon::S2_storerbnew_io:
666 case Hexagon::S2_storerh_io:
667 case Hexagon::S2_storerhnew_io:
668 case Hexagon::S2_storeri_io:
669 case Hexagon::S2_storerinew_io:
670 case Hexagon::S2_storerd_io:
671 case Hexagon::S4_storeirb_io:
672 case Hexagon::S4_storeirh_io:
673 case Hexagon::S4_storeiri_io:
674 return true;
675 }
676
677 // TargetInstrInfo::isPredicable takes a non-const pointer.
678 return MI->mayStore() && HII->isPredicable(const_cast<MachineInstr&>(*MI));
679}
680
681bool HexagonEarlyIfConversion::isSafeToSpeculate(const MachineInstr *MI)
682 const {
683 if (MI->mayLoad() || MI->mayStore())
684 return false;
685 if (MI->isCall() || MI->isBarrier() || MI->isBranch())
686 return false;
687 if (MI->hasUnmodeledSideEffects())
688 return false;
689 if (MI->getOpcode() == TargetOpcode::LIFETIME_END)
690 return false;
691
692 return true;
693}
694
695bool HexagonEarlyIfConversion::isPredicate(unsigned R) const {
696 const TargetRegisterClass *RC = MRI->getRegClass(R);
697 return RC == &Hexagon::PredRegsRegClass ||
698 RC == &Hexagon::HvxQRRegClass;
699}
700
701unsigned HexagonEarlyIfConversion::getCondStoreOpcode(unsigned Opc,
702 bool IfTrue) const {
703 return HII->getCondOpcode(Opc, !IfTrue);
704}
705
706void HexagonEarlyIfConversion::predicateInstr(MachineBasicBlock *ToB,
707 MachineBasicBlock::iterator At, MachineInstr *MI,
708 unsigned PredR, bool IfTrue) {
709 DebugLoc DL;
710 if (At != ToB->end())
711 DL = At->getDebugLoc();
712 else if (!ToB->empty())
713 DL = ToB->back().getDebugLoc();
714
715 unsigned Opc = MI->getOpcode();
716
717 if (isPredicableStore(MI)) {
718 unsigned COpc = getCondStoreOpcode(Opc, IfTrue);
719 assert(COpc)(static_cast <bool> (COpc) ? void (0) : __assert_fail (
"COpc", "/build/llvm-toolchain-snapshot-7~svn329677/lib/Target/Hexagon/HexagonEarlyIfConv.cpp"
, 719, __extension__ __PRETTY_FUNCTION__));
720 MachineInstrBuilder MIB = BuildMI(*ToB, At, DL, HII->get(COpc));
721 MachineInstr::mop_iterator MOI = MI->operands_begin();
722 if (HII->isPostIncrement(*MI)) {
723 MIB.add(*MOI);
724 ++MOI;
725 }
726 MIB.addReg(PredR);
727 for (const MachineOperand &MO : make_range(MOI, MI->operands_end()))
728 MIB.add(MO);
729
730 // Set memory references.
731 MachineInstr::mmo_iterator MMOBegin = MI->memoperands_begin();
732 MachineInstr::mmo_iterator MMOEnd = MI->memoperands_end();
733 MIB.setMemRefs(MMOBegin, MMOEnd);
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-7~svn329677/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 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())(static_cast <bool> (!I->isPHI()) ? void (0) : __assert_fail
("!I->isPHI()", "/build/llvm-toolchain-snapshot-7~svn329677/lib/Target/Hexagon/HexagonEarlyIfConv.cpp"
, 767, __extension__ __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-7~svn329677/lib/Target/Hexagon/HexagonEarlyIfConv.cpp"
, 796);
797 }
798 const MCInstrDesc &D = HII->get(Opc);
799
800 DebugLoc DL = B->findBranchDebugLoc();
801 unsigned 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)(static_cast <bool> (TR || FR) ? void (0) : __assert_fail
("TR || FR", "/build/llvm-toolchain-snapshot-7~svn329677/lib/Target/Hexagon/HexagonEarlyIfConv.cpp"
, 836, __extension__ __PRETTY_FUNCTION__));
837 unsigned MuxR = 0, MuxSR = 0;
838
839 if (TR && FR) {
840 unsigned 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())(static_cast <bool> (OldTI != FP.SplitB->end()) ? void
(0) : __assert_fail ("OldTI != FP.SplitB->end()", "/build/llvm-toolchain-snapshot-7~svn329677/lib/Target/Hexagon/HexagonEarlyIfConv.cpp"
, 861, __extension__ __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)(static_cast <bool> (!SSB) ? void (0) : __assert_fail (
"!SSB", "/build/llvm-toolchain-snapshot-7~svn329677/lib/Target/Hexagon/HexagonEarlyIfConv.cpp"
, 896, __extension__ __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)(static_cast <bool> (!SSB || SSB == FP.JoinB) ? void (0
) : __assert_fail ("!SSB || SSB == FP.JoinB", "/build/llvm-toolchain-snapshot-7~svn329677/lib/Target/Hexagon/HexagonEarlyIfConv.cpp"
, 907, __extension__ __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 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 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")(static_cast <bool> (PN->getNumOperands() == 3 &&
"Invalid phi node") ? void (0) : __assert_fail ("PN->getNumOperands() == 3 && \"Invalid phi node\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Target/Hexagon/HexagonEarlyIfConv.cpp"
, 989, __extension__ __PRETTY_FUNCTION__));
990 MachineOperand &UO = PN->getOperand(1);
991 unsigned UseR = UO.getReg(), UseSR = UO.getSubReg();
992 unsigned 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::replacePhiEdges(MachineBasicBlock *OldB,
1010 MachineBasicBlock *NewB) {
1011 for (auto I = OldB->succ_begin(), E = OldB->succ_end(); I != E; ++I) {
1012 MachineBasicBlock *SB = *I;
1013 MachineBasicBlock::iterator P, N = SB->getFirstNonPHI();
1014 for (P = SB->begin(); P != N; ++P) {
1015 MachineInstr &PN = *P;
1016 for (MachineOperand &MO : PN.operands())
1017 if (MO.isMBB() && MO.getMBB() == OldB)
1018 MO.setMBB(NewB);
1019 }
1020 }
1021}
1022
1023void HexagonEarlyIfConversion::mergeBlocks(MachineBasicBlock *PredB,
1024 MachineBasicBlock *SuccB) {
1025 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)
1026 << PrintMB(SuccB) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-eif")) { dbgs() << "Merging blocks " <<
PrintMB(PredB) << " and " << PrintMB(SuccB) <<
"\n"; } } while (false);
1027 bool TermOk = hasUncondBranch(SuccB);
1028 eliminatePhis(SuccB);
1029 HII->removeBranch(*PredB);
1030 PredB->removeSuccessor(SuccB);
1031 PredB->splice(PredB->end(), SuccB, SuccB->begin(), SuccB->end());
1032 PredB->transferSuccessorsAndUpdatePHIs(SuccB);
1033 removeBlock(SuccB);
1034 if (!TermOk)
1035 PredB->updateTerminator();
1036}
1037
1038void HexagonEarlyIfConversion::simplifyFlowGraph(const FlowPattern &FP) {
1039 if (FP.TrueB)
1040 removeBlock(FP.TrueB);
1041 if (FP.FalseB)
1042 removeBlock(FP.FalseB);
1043
1044 FP.SplitB->updateTerminator();
1045 if (FP.SplitB->succ_size() != 1)
1046 return;
1047
1048 MachineBasicBlock *SB = *FP.SplitB->succ_begin();
1049 if (SB->pred_size() != 1)
1050 return;
1051
1052 // By now, the split block has only one successor (SB), and SB has only
1053 // one predecessor. We can try to merge them. We will need to update ter-
1054 // minators in FP.Split+SB, and that requires working analyzeBranch, which
1055 // fails on Hexagon for blocks that have EH_LABELs. However, if SB ends
1056 // with an unconditional branch, we won't need to touch the terminators.
1057 if (!hasEHLabel(SB) || hasUncondBranch(SB))
1058 mergeBlocks(FP.SplitB, SB);
1059}
1060
1061bool HexagonEarlyIfConversion::runOnMachineFunction(MachineFunction &MF) {
1062 if (skipFunction(MF.getFunction()))
1
Assuming the condition is false
→
2
←
Taking false branch
→
1063 return false;
1064
1065 auto &ST = MF.getSubtarget<HexagonSubtarget>();
1066 HII = ST.getInstrInfo();
1067 TRI = ST.getRegisterInfo();
1068 MFN = &MF;
1069 MRI = &MF.getRegInfo();
1070 MDT = &getAnalysis<MachineDominatorTree>();
1071 MLI = &getAnalysis<MachineLoopInfo>();
1072 MBPI = EnableHexagonBP ? &getAnalysis<MachineBranchProbabilityInfo>() :
3
←
Assuming the condition is false
→
4
←
'?' condition is false
→
1073 nullptr;
1074
1075 Deleted.clear();
1076 bool Changed = false;
1077
1078 for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end(); I != E; ++I)
5
←
Loop condition is true. Entering loop body
→
1079 Changed |= visitLoop(*I);
6
←
Calling 'HexagonEarlyIfConversion::visitLoop'
→
1080 Changed |= visitLoop(nullptr);
1081
1082 return Changed;
1083}
1084
1085//===----------------------------------------------------------------------===//
1086// Public Constructor Functions
1087//===----------------------------------------------------------------------===//
1088FunctionPass *llvm::createHexagonEarlyIfConversion() {
1089 return new HexagonEarlyIfConversion();
1090}