]>
Commit | Line | Data |
---|---|---|
223e47cc LB |
1 | //===-- IfConversion.cpp - Machine code if conversion pass. ---------------===// |
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 file implements the machine instruction level if-conversion pass. | |
11 | // | |
12 | //===----------------------------------------------------------------------===// | |
13 | ||
223e47cc | 14 | #include "llvm/CodeGen/Passes.h" |
970d7e83 LB |
15 | #include "BranchFolding.h" |
16 | #include "llvm/ADT/STLExtras.h" | |
17 | #include "llvm/ADT/SmallSet.h" | |
18 | #include "llvm/ADT/Statistic.h" | |
1a4d82fc JJ |
19 | #include "llvm/CodeGen/LivePhysRegs.h" |
20 | #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" | |
223e47cc LB |
21 | #include "llvm/CodeGen/MachineBranchProbabilityInfo.h" |
22 | #include "llvm/CodeGen/MachineFunctionPass.h" | |
970d7e83 LB |
23 | #include "llvm/CodeGen/MachineInstrBuilder.h" |
24 | #include "llvm/CodeGen/MachineModuleInfo.h" | |
223e47cc | 25 | #include "llvm/CodeGen/MachineRegisterInfo.h" |
1a4d82fc | 26 | #include "llvm/CodeGen/TargetSchedule.h" |
223e47cc | 27 | #include "llvm/MC/MCInstrItineraries.h" |
223e47cc LB |
28 | #include "llvm/Support/CommandLine.h" |
29 | #include "llvm/Support/Debug.h" | |
30 | #include "llvm/Support/ErrorHandling.h" | |
31 | #include "llvm/Support/raw_ostream.h" | |
970d7e83 LB |
32 | #include "llvm/Target/TargetInstrInfo.h" |
33 | #include "llvm/Target/TargetLowering.h" | |
970d7e83 | 34 | #include "llvm/Target/TargetRegisterInfo.h" |
1a4d82fc JJ |
35 | #include "llvm/Target/TargetSubtargetInfo.h" |
36 | ||
223e47cc LB |
37 | using namespace llvm; |
38 | ||
1a4d82fc JJ |
39 | #define DEBUG_TYPE "ifcvt" |
40 | ||
223e47cc LB |
41 | // Hidden options for help debugging. |
42 | static cl::opt<int> IfCvtFnStart("ifcvt-fn-start", cl::init(-1), cl::Hidden); | |
43 | static cl::opt<int> IfCvtFnStop("ifcvt-fn-stop", cl::init(-1), cl::Hidden); | |
44 | static cl::opt<int> IfCvtLimit("ifcvt-limit", cl::init(-1), cl::Hidden); | |
45 | static cl::opt<bool> DisableSimple("disable-ifcvt-simple", | |
46 | cl::init(false), cl::Hidden); | |
47 | static cl::opt<bool> DisableSimpleF("disable-ifcvt-simple-false", | |
48 | cl::init(false), cl::Hidden); | |
49 | static cl::opt<bool> DisableTriangle("disable-ifcvt-triangle", | |
50 | cl::init(false), cl::Hidden); | |
51 | static cl::opt<bool> DisableTriangleR("disable-ifcvt-triangle-rev", | |
52 | cl::init(false), cl::Hidden); | |
53 | static cl::opt<bool> DisableTriangleF("disable-ifcvt-triangle-false", | |
54 | cl::init(false), cl::Hidden); | |
55 | static cl::opt<bool> DisableTriangleFR("disable-ifcvt-triangle-false-rev", | |
56 | cl::init(false), cl::Hidden); | |
57 | static cl::opt<bool> DisableDiamond("disable-ifcvt-diamond", | |
58 | cl::init(false), cl::Hidden); | |
59 | static cl::opt<bool> IfCvtBranchFold("ifcvt-branch-fold", | |
60 | cl::init(true), cl::Hidden); | |
61 | ||
62 | STATISTIC(NumSimple, "Number of simple if-conversions performed"); | |
63 | STATISTIC(NumSimpleFalse, "Number of simple (F) if-conversions performed"); | |
64 | STATISTIC(NumTriangle, "Number of triangle if-conversions performed"); | |
65 | STATISTIC(NumTriangleRev, "Number of triangle (R) if-conversions performed"); | |
66 | STATISTIC(NumTriangleFalse,"Number of triangle (F) if-conversions performed"); | |
67 | STATISTIC(NumTriangleFRev, "Number of triangle (F/R) if-conversions performed"); | |
68 | STATISTIC(NumDiamonds, "Number of diamond if-conversions performed"); | |
69 | STATISTIC(NumIfConvBBs, "Number of if-converted blocks"); | |
70 | STATISTIC(NumDupBBs, "Number of duplicated blocks"); | |
71 | STATISTIC(NumUnpred, "Number of true blocks of diamonds unpredicated"); | |
72 | ||
73 | namespace { | |
74 | class IfConverter : public MachineFunctionPass { | |
75 | enum IfcvtKind { | |
76 | ICNotClassfied, // BB data valid, but not classified. | |
77 | ICSimpleFalse, // Same as ICSimple, but on the false path. | |
78 | ICSimple, // BB is entry of an one split, no rejoin sub-CFG. | |
79 | ICTriangleFRev, // Same as ICTriangleFalse, but false path rev condition. | |
80 | ICTriangleRev, // Same as ICTriangle, but true path rev condition. | |
81 | ICTriangleFalse, // Same as ICTriangle, but on the false path. | |
82 | ICTriangle, // BB is entry of a triangle sub-CFG. | |
83 | ICDiamond // BB is entry of a diamond sub-CFG. | |
84 | }; | |
85 | ||
86 | /// BBInfo - One per MachineBasicBlock, this is used to cache the result | |
87 | /// if-conversion feasibility analysis. This includes results from | |
88 | /// TargetInstrInfo::AnalyzeBranch() (i.e. TBB, FBB, and Cond), and its | |
89 | /// classification, and common tail block of its successors (if it's a | |
90 | /// diamond shape), its size, whether it's predicable, and whether any | |
91 | /// instruction can clobber the 'would-be' predicate. | |
92 | /// | |
93 | /// IsDone - True if BB is not to be considered for ifcvt. | |
94 | /// IsBeingAnalyzed - True if BB is currently being analyzed. | |
95 | /// IsAnalyzed - True if BB has been analyzed (info is still valid). | |
96 | /// IsEnqueued - True if BB has been enqueued to be ifcvt'ed. | |
97 | /// IsBrAnalyzable - True if AnalyzeBranch() returns false. | |
98 | /// HasFallThrough - True if BB may fallthrough to the following BB. | |
99 | /// IsUnpredicable - True if BB is known to be unpredicable. | |
100 | /// ClobbersPred - True if BB could modify predicates (e.g. has | |
101 | /// cmp, call, etc.) | |
102 | /// NonPredSize - Number of non-predicated instructions. | |
103 | /// ExtraCost - Extra cost for multi-cycle instructions. | |
104 | /// ExtraCost2 - Some instructions are slower when predicated | |
105 | /// BB - Corresponding MachineBasicBlock. | |
106 | /// TrueBB / FalseBB- See AnalyzeBranch(). | |
107 | /// BrCond - Conditions for end of block conditional branches. | |
108 | /// Predicate - Predicate used in the BB. | |
109 | struct BBInfo { | |
110 | bool IsDone : 1; | |
111 | bool IsBeingAnalyzed : 1; | |
112 | bool IsAnalyzed : 1; | |
113 | bool IsEnqueued : 1; | |
114 | bool IsBrAnalyzable : 1; | |
115 | bool HasFallThrough : 1; | |
116 | bool IsUnpredicable : 1; | |
117 | bool CannotBeCopied : 1; | |
118 | bool ClobbersPred : 1; | |
119 | unsigned NonPredSize; | |
120 | unsigned ExtraCost; | |
121 | unsigned ExtraCost2; | |
122 | MachineBasicBlock *BB; | |
123 | MachineBasicBlock *TrueBB; | |
124 | MachineBasicBlock *FalseBB; | |
125 | SmallVector<MachineOperand, 4> BrCond; | |
126 | SmallVector<MachineOperand, 4> Predicate; | |
127 | BBInfo() : IsDone(false), IsBeingAnalyzed(false), | |
128 | IsAnalyzed(false), IsEnqueued(false), IsBrAnalyzable(false), | |
129 | HasFallThrough(false), IsUnpredicable(false), | |
130 | CannotBeCopied(false), ClobbersPred(false), NonPredSize(0), | |
1a4d82fc JJ |
131 | ExtraCost(0), ExtraCost2(0), BB(nullptr), TrueBB(nullptr), |
132 | FalseBB(nullptr) {} | |
223e47cc LB |
133 | }; |
134 | ||
135 | /// IfcvtToken - Record information about pending if-conversions to attempt: | |
136 | /// BBI - Corresponding BBInfo. | |
137 | /// Kind - Type of block. See IfcvtKind. | |
138 | /// NeedSubsumption - True if the to-be-predicated BB has already been | |
139 | /// predicated. | |
140 | /// NumDups - Number of instructions that would be duplicated due | |
141 | /// to this if-conversion. (For diamonds, the number of | |
142 | /// identical instructions at the beginnings of both | |
143 | /// paths). | |
144 | /// NumDups2 - For diamonds, the number of identical instructions | |
145 | /// at the ends of both paths. | |
146 | struct IfcvtToken { | |
147 | BBInfo &BBI; | |
148 | IfcvtKind Kind; | |
149 | bool NeedSubsumption; | |
150 | unsigned NumDups; | |
151 | unsigned NumDups2; | |
152 | IfcvtToken(BBInfo &b, IfcvtKind k, bool s, unsigned d, unsigned d2 = 0) | |
153 | : BBI(b), Kind(k), NeedSubsumption(s), NumDups(d), NumDups2(d2) {} | |
154 | }; | |
155 | ||
156 | /// BBAnalysis - Results of if-conversion feasibility analysis indexed by | |
157 | /// basic block number. | |
158 | std::vector<BBInfo> BBAnalysis; | |
1a4d82fc | 159 | TargetSchedModel SchedModel; |
223e47cc | 160 | |
970d7e83 | 161 | const TargetLoweringBase *TLI; |
223e47cc LB |
162 | const TargetInstrInfo *TII; |
163 | const TargetRegisterInfo *TRI; | |
1a4d82fc | 164 | const MachineBlockFrequencyInfo *MBFI; |
223e47cc LB |
165 | const MachineBranchProbabilityInfo *MBPI; |
166 | MachineRegisterInfo *MRI; | |
167 | ||
1a4d82fc JJ |
168 | LivePhysRegs Redefs; |
169 | LivePhysRegs DontKill; | |
170 | ||
223e47cc LB |
171 | bool PreRegAlloc; |
172 | bool MadeChange; | |
173 | int FnNum; | |
174 | public: | |
175 | static char ID; | |
176 | IfConverter() : MachineFunctionPass(ID), FnNum(-1) { | |
177 | initializeIfConverterPass(*PassRegistry::getPassRegistry()); | |
178 | } | |
179 | ||
1a4d82fc JJ |
180 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
181 | AU.addRequired<MachineBlockFrequencyInfo>(); | |
223e47cc LB |
182 | AU.addRequired<MachineBranchProbabilityInfo>(); |
183 | MachineFunctionPass::getAnalysisUsage(AU); | |
184 | } | |
185 | ||
1a4d82fc | 186 | bool runOnMachineFunction(MachineFunction &MF) override; |
223e47cc LB |
187 | |
188 | private: | |
189 | bool ReverseBranchCondition(BBInfo &BBI); | |
190 | bool ValidSimple(BBInfo &TrueBBI, unsigned &Dups, | |
191 | const BranchProbability &Prediction) const; | |
192 | bool ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI, | |
193 | bool FalseBranch, unsigned &Dups, | |
194 | const BranchProbability &Prediction) const; | |
195 | bool ValidDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI, | |
196 | unsigned &Dups1, unsigned &Dups2) const; | |
197 | void ScanInstructions(BBInfo &BBI); | |
198 | BBInfo &AnalyzeBlock(MachineBasicBlock *BB, | |
199 | std::vector<IfcvtToken*> &Tokens); | |
200 | bool FeasibilityAnalysis(BBInfo &BBI, SmallVectorImpl<MachineOperand> &Cond, | |
201 | bool isTriangle = false, bool RevBranch = false); | |
202 | void AnalyzeBlocks(MachineFunction &MF, std::vector<IfcvtToken*> &Tokens); | |
203 | void InvalidatePreds(MachineBasicBlock *BB); | |
204 | void RemoveExtraEdges(BBInfo &BBI); | |
205 | bool IfConvertSimple(BBInfo &BBI, IfcvtKind Kind); | |
206 | bool IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind); | |
207 | bool IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind, | |
208 | unsigned NumDups1, unsigned NumDups2); | |
209 | void PredicateBlock(BBInfo &BBI, | |
210 | MachineBasicBlock::iterator E, | |
211 | SmallVectorImpl<MachineOperand> &Cond, | |
1a4d82fc | 212 | SmallSet<unsigned, 4> *LaterRedefs = nullptr); |
223e47cc LB |
213 | void CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI, |
214 | SmallVectorImpl<MachineOperand> &Cond, | |
223e47cc LB |
215 | bool IgnoreBr = false); |
216 | void MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges = true); | |
217 | ||
218 | bool MeetIfcvtSizeLimit(MachineBasicBlock &BB, | |
219 | unsigned Cycle, unsigned Extra, | |
220 | const BranchProbability &Prediction) const { | |
221 | return Cycle > 0 && TII->isProfitableToIfCvt(BB, Cycle, Extra, | |
222 | Prediction); | |
223 | } | |
224 | ||
225 | bool MeetIfcvtSizeLimit(MachineBasicBlock &TBB, | |
226 | unsigned TCycle, unsigned TExtra, | |
227 | MachineBasicBlock &FBB, | |
228 | unsigned FCycle, unsigned FExtra, | |
229 | const BranchProbability &Prediction) const { | |
230 | return TCycle > 0 && FCycle > 0 && | |
231 | TII->isProfitableToIfCvt(TBB, TCycle, TExtra, FBB, FCycle, FExtra, | |
232 | Prediction); | |
233 | } | |
234 | ||
235 | // blockAlwaysFallThrough - Block ends without a terminator. | |
236 | bool blockAlwaysFallThrough(BBInfo &BBI) const { | |
1a4d82fc | 237 | return BBI.IsBrAnalyzable && BBI.TrueBB == nullptr; |
223e47cc LB |
238 | } |
239 | ||
240 | // IfcvtTokenCmp - Used to sort if-conversion candidates. | |
241 | static bool IfcvtTokenCmp(IfcvtToken *C1, IfcvtToken *C2) { | |
242 | int Incr1 = (C1->Kind == ICDiamond) | |
243 | ? -(int)(C1->NumDups + C1->NumDups2) : (int)C1->NumDups; | |
244 | int Incr2 = (C2->Kind == ICDiamond) | |
245 | ? -(int)(C2->NumDups + C2->NumDups2) : (int)C2->NumDups; | |
246 | if (Incr1 > Incr2) | |
247 | return true; | |
248 | else if (Incr1 == Incr2) { | |
249 | // Favors subsumption. | |
250 | if (C1->NeedSubsumption == false && C2->NeedSubsumption == true) | |
251 | return true; | |
252 | else if (C1->NeedSubsumption == C2->NeedSubsumption) { | |
253 | // Favors diamond over triangle, etc. | |
254 | if ((unsigned)C1->Kind < (unsigned)C2->Kind) | |
255 | return true; | |
256 | else if (C1->Kind == C2->Kind) | |
257 | return C1->BBI.BB->getNumber() < C2->BBI.BB->getNumber(); | |
258 | } | |
259 | } | |
260 | return false; | |
261 | } | |
262 | }; | |
263 | ||
264 | char IfConverter::ID = 0; | |
265 | } | |
266 | ||
267 | char &llvm::IfConverterID = IfConverter::ID; | |
268 | ||
269 | INITIALIZE_PASS_BEGIN(IfConverter, "if-converter", "If Converter", false, false) | |
270 | INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) | |
271 | INITIALIZE_PASS_END(IfConverter, "if-converter", "If Converter", false, false) | |
272 | ||
273 | bool IfConverter::runOnMachineFunction(MachineFunction &MF) { | |
1a4d82fc JJ |
274 | TLI = MF.getSubtarget().getTargetLowering(); |
275 | TII = MF.getSubtarget().getInstrInfo(); | |
276 | TRI = MF.getSubtarget().getRegisterInfo(); | |
277 | MBFI = &getAnalysis<MachineBlockFrequencyInfo>(); | |
223e47cc LB |
278 | MBPI = &getAnalysis<MachineBranchProbabilityInfo>(); |
279 | MRI = &MF.getRegInfo(); | |
1a4d82fc JJ |
280 | |
281 | const TargetSubtargetInfo &ST = | |
282 | MF.getTarget().getSubtarget<TargetSubtargetInfo>(); | |
283 | SchedModel.init(ST.getSchedModel(), &ST, TII); | |
284 | ||
223e47cc LB |
285 | if (!TII) return false; |
286 | ||
287 | PreRegAlloc = MRI->isSSA(); | |
288 | ||
289 | bool BFChange = false; | |
290 | if (!PreRegAlloc) { | |
291 | // Tail merge tend to expose more if-conversion opportunities. | |
1a4d82fc JJ |
292 | BranchFolder BF(true, false, *MBFI, *MBPI); |
293 | BFChange = BF.OptimizeFunction(MF, TII, MF.getSubtarget().getRegisterInfo(), | |
223e47cc LB |
294 | getAnalysisIfAvailable<MachineModuleInfo>()); |
295 | } | |
296 | ||
297 | DEBUG(dbgs() << "\nIfcvt: function (" << ++FnNum << ") \'" | |
298 | << MF.getName() << "\'"); | |
299 | ||
300 | if (FnNum < IfCvtFnStart || (IfCvtFnStop != -1 && FnNum > IfCvtFnStop)) { | |
301 | DEBUG(dbgs() << " skipped\n"); | |
302 | return false; | |
303 | } | |
304 | DEBUG(dbgs() << "\n"); | |
305 | ||
306 | MF.RenumberBlocks(); | |
307 | BBAnalysis.resize(MF.getNumBlockIDs()); | |
308 | ||
309 | std::vector<IfcvtToken*> Tokens; | |
310 | MadeChange = false; | |
311 | unsigned NumIfCvts = NumSimple + NumSimpleFalse + NumTriangle + | |
312 | NumTriangleRev + NumTriangleFalse + NumTriangleFRev + NumDiamonds; | |
313 | while (IfCvtLimit == -1 || (int)NumIfCvts < IfCvtLimit) { | |
314 | // Do an initial analysis for each basic block and find all the potential | |
315 | // candidates to perform if-conversion. | |
316 | bool Change = false; | |
317 | AnalyzeBlocks(MF, Tokens); | |
318 | while (!Tokens.empty()) { | |
319 | IfcvtToken *Token = Tokens.back(); | |
320 | Tokens.pop_back(); | |
321 | BBInfo &BBI = Token->BBI; | |
322 | IfcvtKind Kind = Token->Kind; | |
323 | unsigned NumDups = Token->NumDups; | |
324 | unsigned NumDups2 = Token->NumDups2; | |
325 | ||
326 | delete Token; | |
327 | ||
328 | // If the block has been evicted out of the queue or it has already been | |
329 | // marked dead (due to it being predicated), then skip it. | |
330 | if (BBI.IsDone) | |
331 | BBI.IsEnqueued = false; | |
332 | if (!BBI.IsEnqueued) | |
333 | continue; | |
334 | ||
335 | BBI.IsEnqueued = false; | |
336 | ||
337 | bool RetVal = false; | |
338 | switch (Kind) { | |
339 | default: llvm_unreachable("Unexpected!"); | |
340 | case ICSimple: | |
341 | case ICSimpleFalse: { | |
342 | bool isFalse = Kind == ICSimpleFalse; | |
343 | if ((isFalse && DisableSimpleF) || (!isFalse && DisableSimple)) break; | |
344 | DEBUG(dbgs() << "Ifcvt (Simple" << (Kind == ICSimpleFalse ? | |
345 | " false" : "") | |
346 | << "): BB#" << BBI.BB->getNumber() << " (" | |
347 | << ((Kind == ICSimpleFalse) | |
348 | ? BBI.FalseBB->getNumber() | |
349 | : BBI.TrueBB->getNumber()) << ") "); | |
350 | RetVal = IfConvertSimple(BBI, Kind); | |
351 | DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n"); | |
352 | if (RetVal) { | |
353 | if (isFalse) ++NumSimpleFalse; | |
354 | else ++NumSimple; | |
355 | } | |
356 | break; | |
357 | } | |
358 | case ICTriangle: | |
359 | case ICTriangleRev: | |
360 | case ICTriangleFalse: | |
361 | case ICTriangleFRev: { | |
362 | bool isFalse = Kind == ICTriangleFalse; | |
363 | bool isRev = (Kind == ICTriangleRev || Kind == ICTriangleFRev); | |
364 | if (DisableTriangle && !isFalse && !isRev) break; | |
365 | if (DisableTriangleR && !isFalse && isRev) break; | |
366 | if (DisableTriangleF && isFalse && !isRev) break; | |
367 | if (DisableTriangleFR && isFalse && isRev) break; | |
368 | DEBUG(dbgs() << "Ifcvt (Triangle"); | |
369 | if (isFalse) | |
370 | DEBUG(dbgs() << " false"); | |
371 | if (isRev) | |
372 | DEBUG(dbgs() << " rev"); | |
373 | DEBUG(dbgs() << "): BB#" << BBI.BB->getNumber() << " (T:" | |
374 | << BBI.TrueBB->getNumber() << ",F:" | |
375 | << BBI.FalseBB->getNumber() << ") "); | |
376 | RetVal = IfConvertTriangle(BBI, Kind); | |
377 | DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n"); | |
378 | if (RetVal) { | |
379 | if (isFalse) { | |
380 | if (isRev) ++NumTriangleFRev; | |
381 | else ++NumTriangleFalse; | |
382 | } else { | |
383 | if (isRev) ++NumTriangleRev; | |
384 | else ++NumTriangle; | |
385 | } | |
386 | } | |
387 | break; | |
388 | } | |
389 | case ICDiamond: { | |
390 | if (DisableDiamond) break; | |
391 | DEBUG(dbgs() << "Ifcvt (Diamond): BB#" << BBI.BB->getNumber() << " (T:" | |
392 | << BBI.TrueBB->getNumber() << ",F:" | |
393 | << BBI.FalseBB->getNumber() << ") "); | |
394 | RetVal = IfConvertDiamond(BBI, Kind, NumDups, NumDups2); | |
395 | DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n"); | |
396 | if (RetVal) ++NumDiamonds; | |
397 | break; | |
398 | } | |
399 | } | |
400 | ||
401 | Change |= RetVal; | |
402 | ||
403 | NumIfCvts = NumSimple + NumSimpleFalse + NumTriangle + NumTriangleRev + | |
404 | NumTriangleFalse + NumTriangleFRev + NumDiamonds; | |
405 | if (IfCvtLimit != -1 && (int)NumIfCvts >= IfCvtLimit) | |
406 | break; | |
407 | } | |
408 | ||
409 | if (!Change) | |
410 | break; | |
411 | MadeChange |= Change; | |
412 | } | |
413 | ||
414 | // Delete tokens in case of early exit. | |
415 | while (!Tokens.empty()) { | |
416 | IfcvtToken *Token = Tokens.back(); | |
417 | Tokens.pop_back(); | |
418 | delete Token; | |
419 | } | |
420 | ||
421 | Tokens.clear(); | |
422 | BBAnalysis.clear(); | |
423 | ||
424 | if (MadeChange && IfCvtBranchFold) { | |
1a4d82fc JJ |
425 | BranchFolder BF(false, false, *MBFI, *MBPI); |
426 | BF.OptimizeFunction(MF, TII, MF.getSubtarget().getRegisterInfo(), | |
223e47cc LB |
427 | getAnalysisIfAvailable<MachineModuleInfo>()); |
428 | } | |
429 | ||
430 | MadeChange |= BFChange; | |
431 | return MadeChange; | |
432 | } | |
433 | ||
434 | /// findFalseBlock - BB has a fallthrough. Find its 'false' successor given | |
435 | /// its 'true' successor. | |
436 | static MachineBasicBlock *findFalseBlock(MachineBasicBlock *BB, | |
437 | MachineBasicBlock *TrueBB) { | |
438 | for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), | |
439 | E = BB->succ_end(); SI != E; ++SI) { | |
440 | MachineBasicBlock *SuccBB = *SI; | |
441 | if (SuccBB != TrueBB) | |
442 | return SuccBB; | |
443 | } | |
1a4d82fc | 444 | return nullptr; |
223e47cc LB |
445 | } |
446 | ||
447 | /// ReverseBranchCondition - Reverse the condition of the end of the block | |
448 | /// branch. Swap block's 'true' and 'false' successors. | |
449 | bool IfConverter::ReverseBranchCondition(BBInfo &BBI) { | |
450 | DebugLoc dl; // FIXME: this is nowhere | |
451 | if (!TII->ReverseBranchCondition(BBI.BrCond)) { | |
452 | TII->RemoveBranch(*BBI.BB); | |
453 | TII->InsertBranch(*BBI.BB, BBI.FalseBB, BBI.TrueBB, BBI.BrCond, dl); | |
454 | std::swap(BBI.TrueBB, BBI.FalseBB); | |
455 | return true; | |
456 | } | |
457 | return false; | |
458 | } | |
459 | ||
460 | /// getNextBlock - Returns the next block in the function blocks ordering. If | |
461 | /// it is the end, returns NULL. | |
462 | static inline MachineBasicBlock *getNextBlock(MachineBasicBlock *BB) { | |
463 | MachineFunction::iterator I = BB; | |
464 | MachineFunction::iterator E = BB->getParent()->end(); | |
465 | if (++I == E) | |
1a4d82fc | 466 | return nullptr; |
223e47cc LB |
467 | return I; |
468 | } | |
469 | ||
470 | /// ValidSimple - Returns true if the 'true' block (along with its | |
471 | /// predecessor) forms a valid simple shape for ifcvt. It also returns the | |
472 | /// number of instructions that the ifcvt would need to duplicate if performed | |
473 | /// in Dups. | |
474 | bool IfConverter::ValidSimple(BBInfo &TrueBBI, unsigned &Dups, | |
475 | const BranchProbability &Prediction) const { | |
476 | Dups = 0; | |
477 | if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone) | |
478 | return false; | |
479 | ||
480 | if (TrueBBI.IsBrAnalyzable) | |
481 | return false; | |
482 | ||
483 | if (TrueBBI.BB->pred_size() > 1) { | |
484 | if (TrueBBI.CannotBeCopied || | |
485 | !TII->isProfitableToDupForIfCvt(*TrueBBI.BB, TrueBBI.NonPredSize, | |
486 | Prediction)) | |
487 | return false; | |
488 | Dups = TrueBBI.NonPredSize; | |
489 | } | |
490 | ||
491 | return true; | |
492 | } | |
493 | ||
494 | /// ValidTriangle - Returns true if the 'true' and 'false' blocks (along | |
495 | /// with their common predecessor) forms a valid triangle shape for ifcvt. | |
496 | /// If 'FalseBranch' is true, it checks if 'true' block's false branch | |
497 | /// branches to the 'false' block rather than the other way around. It also | |
498 | /// returns the number of instructions that the ifcvt would need to duplicate | |
499 | /// if performed in 'Dups'. | |
500 | bool IfConverter::ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI, | |
501 | bool FalseBranch, unsigned &Dups, | |
502 | const BranchProbability &Prediction) const { | |
503 | Dups = 0; | |
504 | if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone) | |
505 | return false; | |
506 | ||
507 | if (TrueBBI.BB->pred_size() > 1) { | |
508 | if (TrueBBI.CannotBeCopied) | |
509 | return false; | |
510 | ||
511 | unsigned Size = TrueBBI.NonPredSize; | |
512 | if (TrueBBI.IsBrAnalyzable) { | |
513 | if (TrueBBI.TrueBB && TrueBBI.BrCond.empty()) | |
514 | // Ends with an unconditional branch. It will be removed. | |
515 | --Size; | |
516 | else { | |
517 | MachineBasicBlock *FExit = FalseBranch | |
518 | ? TrueBBI.TrueBB : TrueBBI.FalseBB; | |
519 | if (FExit) | |
520 | // Require a conditional branch | |
521 | ++Size; | |
522 | } | |
523 | } | |
524 | if (!TII->isProfitableToDupForIfCvt(*TrueBBI.BB, Size, Prediction)) | |
525 | return false; | |
526 | Dups = Size; | |
527 | } | |
528 | ||
529 | MachineBasicBlock *TExit = FalseBranch ? TrueBBI.FalseBB : TrueBBI.TrueBB; | |
530 | if (!TExit && blockAlwaysFallThrough(TrueBBI)) { | |
531 | MachineFunction::iterator I = TrueBBI.BB; | |
532 | if (++I == TrueBBI.BB->getParent()->end()) | |
533 | return false; | |
534 | TExit = I; | |
535 | } | |
536 | return TExit && TExit == FalseBBI.BB; | |
537 | } | |
538 | ||
539 | /// ValidDiamond - Returns true if the 'true' and 'false' blocks (along | |
540 | /// with their common predecessor) forms a valid diamond shape for ifcvt. | |
541 | bool IfConverter::ValidDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI, | |
542 | unsigned &Dups1, unsigned &Dups2) const { | |
543 | Dups1 = Dups2 = 0; | |
544 | if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone || | |
545 | FalseBBI.IsBeingAnalyzed || FalseBBI.IsDone) | |
546 | return false; | |
547 | ||
548 | MachineBasicBlock *TT = TrueBBI.TrueBB; | |
549 | MachineBasicBlock *FT = FalseBBI.TrueBB; | |
550 | ||
551 | if (!TT && blockAlwaysFallThrough(TrueBBI)) | |
552 | TT = getNextBlock(TrueBBI.BB); | |
553 | if (!FT && blockAlwaysFallThrough(FalseBBI)) | |
554 | FT = getNextBlock(FalseBBI.BB); | |
555 | if (TT != FT) | |
556 | return false; | |
1a4d82fc | 557 | if (!TT && (TrueBBI.IsBrAnalyzable || FalseBBI.IsBrAnalyzable)) |
223e47cc LB |
558 | return false; |
559 | if (TrueBBI.BB->pred_size() > 1 || FalseBBI.BB->pred_size() > 1) | |
560 | return false; | |
561 | ||
562 | // FIXME: Allow true block to have an early exit? | |
563 | if (TrueBBI.FalseBB || FalseBBI.FalseBB || | |
564 | (TrueBBI.ClobbersPred && FalseBBI.ClobbersPred)) | |
565 | return false; | |
566 | ||
567 | // Count duplicate instructions at the beginning of the true and false blocks. | |
568 | MachineBasicBlock::iterator TIB = TrueBBI.BB->begin(); | |
569 | MachineBasicBlock::iterator FIB = FalseBBI.BB->begin(); | |
570 | MachineBasicBlock::iterator TIE = TrueBBI.BB->end(); | |
571 | MachineBasicBlock::iterator FIE = FalseBBI.BB->end(); | |
572 | while (TIB != TIE && FIB != FIE) { | |
573 | // Skip dbg_value instructions. These do not count. | |
574 | if (TIB->isDebugValue()) { | |
575 | while (TIB != TIE && TIB->isDebugValue()) | |
576 | ++TIB; | |
577 | if (TIB == TIE) | |
578 | break; | |
579 | } | |
580 | if (FIB->isDebugValue()) { | |
581 | while (FIB != FIE && FIB->isDebugValue()) | |
582 | ++FIB; | |
583 | if (FIB == FIE) | |
584 | break; | |
585 | } | |
586 | if (!TIB->isIdenticalTo(FIB)) | |
587 | break; | |
588 | ++Dups1; | |
589 | ++TIB; | |
590 | ++FIB; | |
591 | } | |
592 | ||
593 | // Now, in preparation for counting duplicate instructions at the ends of the | |
594 | // blocks, move the end iterators up past any branch instructions. | |
595 | while (TIE != TIB) { | |
596 | --TIE; | |
597 | if (!TIE->isBranch()) | |
598 | break; | |
599 | } | |
600 | while (FIE != FIB) { | |
601 | --FIE; | |
602 | if (!FIE->isBranch()) | |
603 | break; | |
604 | } | |
605 | ||
606 | // If Dups1 includes all of a block, then don't count duplicate | |
607 | // instructions at the end of the blocks. | |
608 | if (TIB == TIE || FIB == FIE) | |
609 | return true; | |
610 | ||
611 | // Count duplicate instructions at the ends of the blocks. | |
612 | while (TIE != TIB && FIE != FIB) { | |
613 | // Skip dbg_value instructions. These do not count. | |
614 | if (TIE->isDebugValue()) { | |
615 | while (TIE != TIB && TIE->isDebugValue()) | |
616 | --TIE; | |
617 | if (TIE == TIB) | |
618 | break; | |
619 | } | |
620 | if (FIE->isDebugValue()) { | |
621 | while (FIE != FIB && FIE->isDebugValue()) | |
622 | --FIE; | |
623 | if (FIE == FIB) | |
624 | break; | |
625 | } | |
626 | if (!TIE->isIdenticalTo(FIE)) | |
627 | break; | |
628 | ++Dups2; | |
629 | --TIE; | |
630 | --FIE; | |
631 | } | |
632 | ||
633 | return true; | |
634 | } | |
635 | ||
636 | /// ScanInstructions - Scan all the instructions in the block to determine if | |
637 | /// the block is predicable. In most cases, that means all the instructions | |
638 | /// in the block are isPredicable(). Also checks if the block contains any | |
639 | /// instruction which can clobber a predicate (e.g. condition code register). | |
640 | /// If so, the block is not predicable unless it's the last instruction. | |
641 | void IfConverter::ScanInstructions(BBInfo &BBI) { | |
642 | if (BBI.IsDone) | |
643 | return; | |
644 | ||
645 | bool AlreadyPredicated = !BBI.Predicate.empty(); | |
646 | // First analyze the end of BB branches. | |
1a4d82fc | 647 | BBI.TrueBB = BBI.FalseBB = nullptr; |
223e47cc LB |
648 | BBI.BrCond.clear(); |
649 | BBI.IsBrAnalyzable = | |
650 | !TII->AnalyzeBranch(*BBI.BB, BBI.TrueBB, BBI.FalseBB, BBI.BrCond); | |
1a4d82fc | 651 | BBI.HasFallThrough = BBI.IsBrAnalyzable && BBI.FalseBB == nullptr; |
223e47cc LB |
652 | |
653 | if (BBI.BrCond.size()) { | |
654 | // No false branch. This BB must end with a conditional branch and a | |
655 | // fallthrough. | |
656 | if (!BBI.FalseBB) | |
657 | BBI.FalseBB = findFalseBlock(BBI.BB, BBI.TrueBB); | |
658 | if (!BBI.FalseBB) { | |
659 | // Malformed bcc? True and false blocks are the same? | |
660 | BBI.IsUnpredicable = true; | |
661 | return; | |
662 | } | |
663 | } | |
664 | ||
665 | // Then scan all the instructions. | |
666 | BBI.NonPredSize = 0; | |
667 | BBI.ExtraCost = 0; | |
668 | BBI.ExtraCost2 = 0; | |
669 | BBI.ClobbersPred = false; | |
670 | for (MachineBasicBlock::iterator I = BBI.BB->begin(), E = BBI.BB->end(); | |
671 | I != E; ++I) { | |
672 | if (I->isDebugValue()) | |
673 | continue; | |
674 | ||
675 | if (I->isNotDuplicable()) | |
676 | BBI.CannotBeCopied = true; | |
677 | ||
678 | bool isPredicated = TII->isPredicated(I); | |
679 | bool isCondBr = BBI.IsBrAnalyzable && I->isConditionalBranch(); | |
680 | ||
1a4d82fc JJ |
681 | // A conditional branch is not predicable, but it may be eliminated. |
682 | if (isCondBr) | |
683 | continue; | |
684 | ||
685 | if (!isPredicated) { | |
686 | BBI.NonPredSize++; | |
687 | unsigned ExtraPredCost = TII->getPredicationCost(&*I); | |
688 | unsigned NumCycles = SchedModel.computeInstrLatency(&*I, false); | |
689 | if (NumCycles > 1) | |
690 | BBI.ExtraCost += NumCycles-1; | |
691 | BBI.ExtraCost2 += ExtraPredCost; | |
692 | } else if (!AlreadyPredicated) { | |
693 | // FIXME: This instruction is already predicated before the | |
694 | // if-conversion pass. It's probably something like a conditional move. | |
695 | // Mark this block unpredicable for now. | |
696 | BBI.IsUnpredicable = true; | |
697 | return; | |
223e47cc LB |
698 | } |
699 | ||
700 | if (BBI.ClobbersPred && !isPredicated) { | |
701 | // Predicate modification instruction should end the block (except for | |
702 | // already predicated instructions and end of block branches). | |
223e47cc LB |
703 | // Predicate may have been modified, the subsequent (currently) |
704 | // unpredicated instructions cannot be correctly predicated. | |
705 | BBI.IsUnpredicable = true; | |
706 | return; | |
707 | } | |
708 | ||
709 | // FIXME: Make use of PredDefs? e.g. ADDC, SUBC sets predicates but are | |
710 | // still potentially predicable. | |
711 | std::vector<MachineOperand> PredDefs; | |
712 | if (TII->DefinesPredicate(I, PredDefs)) | |
713 | BBI.ClobbersPred = true; | |
714 | ||
715 | if (!TII->isPredicable(I)) { | |
716 | BBI.IsUnpredicable = true; | |
717 | return; | |
718 | } | |
719 | } | |
720 | } | |
721 | ||
722 | /// FeasibilityAnalysis - Determine if the block is a suitable candidate to be | |
723 | /// predicated by the specified predicate. | |
724 | bool IfConverter::FeasibilityAnalysis(BBInfo &BBI, | |
725 | SmallVectorImpl<MachineOperand> &Pred, | |
726 | bool isTriangle, bool RevBranch) { | |
727 | // If the block is dead or unpredicable, then it cannot be predicated. | |
728 | if (BBI.IsDone || BBI.IsUnpredicable) | |
729 | return false; | |
730 | ||
1a4d82fc JJ |
731 | // If it is already predicated, check if the new predicate subsumes |
732 | // its predicate. | |
733 | if (BBI.Predicate.size() && !TII->SubsumesPredicate(Pred, BBI.Predicate)) | |
223e47cc LB |
734 | return false; |
735 | ||
736 | if (BBI.BrCond.size()) { | |
737 | if (!isTriangle) | |
738 | return false; | |
739 | ||
740 | // Test predicate subsumption. | |
741 | SmallVector<MachineOperand, 4> RevPred(Pred.begin(), Pred.end()); | |
742 | SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end()); | |
743 | if (RevBranch) { | |
744 | if (TII->ReverseBranchCondition(Cond)) | |
745 | return false; | |
746 | } | |
747 | if (TII->ReverseBranchCondition(RevPred) || | |
748 | !TII->SubsumesPredicate(Cond, RevPred)) | |
749 | return false; | |
750 | } | |
751 | ||
752 | return true; | |
753 | } | |
754 | ||
755 | /// AnalyzeBlock - Analyze the structure of the sub-CFG starting from | |
756 | /// the specified block. Record its successors and whether it looks like an | |
757 | /// if-conversion candidate. | |
758 | IfConverter::BBInfo &IfConverter::AnalyzeBlock(MachineBasicBlock *BB, | |
759 | std::vector<IfcvtToken*> &Tokens) { | |
760 | BBInfo &BBI = BBAnalysis[BB->getNumber()]; | |
761 | ||
762 | if (BBI.IsAnalyzed || BBI.IsBeingAnalyzed) | |
763 | return BBI; | |
764 | ||
765 | BBI.BB = BB; | |
766 | BBI.IsBeingAnalyzed = true; | |
767 | ||
768 | ScanInstructions(BBI); | |
769 | ||
770 | // Unanalyzable or ends with fallthrough or unconditional branch, or if is not | |
771 | // considered for ifcvt anymore. | |
772 | if (!BBI.IsBrAnalyzable || BBI.BrCond.empty() || BBI.IsDone) { | |
773 | BBI.IsBeingAnalyzed = false; | |
774 | BBI.IsAnalyzed = true; | |
775 | return BBI; | |
776 | } | |
777 | ||
778 | // Do not ifcvt if either path is a back edge to the entry block. | |
779 | if (BBI.TrueBB == BB || BBI.FalseBB == BB) { | |
780 | BBI.IsBeingAnalyzed = false; | |
781 | BBI.IsAnalyzed = true; | |
782 | return BBI; | |
783 | } | |
784 | ||
785 | // Do not ifcvt if true and false fallthrough blocks are the same. | |
786 | if (!BBI.FalseBB) { | |
787 | BBI.IsBeingAnalyzed = false; | |
788 | BBI.IsAnalyzed = true; | |
789 | return BBI; | |
790 | } | |
791 | ||
792 | BBInfo &TrueBBI = AnalyzeBlock(BBI.TrueBB, Tokens); | |
793 | BBInfo &FalseBBI = AnalyzeBlock(BBI.FalseBB, Tokens); | |
794 | ||
795 | if (TrueBBI.IsDone && FalseBBI.IsDone) { | |
796 | BBI.IsBeingAnalyzed = false; | |
797 | BBI.IsAnalyzed = true; | |
798 | return BBI; | |
799 | } | |
800 | ||
801 | SmallVector<MachineOperand, 4> RevCond(BBI.BrCond.begin(), BBI.BrCond.end()); | |
802 | bool CanRevCond = !TII->ReverseBranchCondition(RevCond); | |
803 | ||
804 | unsigned Dups = 0; | |
805 | unsigned Dups2 = 0; | |
806 | bool TNeedSub = !TrueBBI.Predicate.empty(); | |
807 | bool FNeedSub = !FalseBBI.Predicate.empty(); | |
808 | bool Enqueued = false; | |
809 | ||
810 | BranchProbability Prediction = MBPI->getEdgeProbability(BB, TrueBBI.BB); | |
811 | ||
812 | if (CanRevCond && ValidDiamond(TrueBBI, FalseBBI, Dups, Dups2) && | |
813 | MeetIfcvtSizeLimit(*TrueBBI.BB, (TrueBBI.NonPredSize - (Dups + Dups2) + | |
814 | TrueBBI.ExtraCost), TrueBBI.ExtraCost2, | |
815 | *FalseBBI.BB, (FalseBBI.NonPredSize - (Dups + Dups2) + | |
816 | FalseBBI.ExtraCost),FalseBBI.ExtraCost2, | |
817 | Prediction) && | |
818 | FeasibilityAnalysis(TrueBBI, BBI.BrCond) && | |
819 | FeasibilityAnalysis(FalseBBI, RevCond)) { | |
820 | // Diamond: | |
821 | // EBB | |
822 | // / \_ | |
823 | // | | | |
824 | // TBB FBB | |
825 | // \ / | |
826 | // TailBB | |
827 | // Note TailBB can be empty. | |
828 | Tokens.push_back(new IfcvtToken(BBI, ICDiamond, TNeedSub|FNeedSub, Dups, | |
829 | Dups2)); | |
830 | Enqueued = true; | |
831 | } | |
832 | ||
833 | if (ValidTriangle(TrueBBI, FalseBBI, false, Dups, Prediction) && | |
834 | MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost, | |
835 | TrueBBI.ExtraCost2, Prediction) && | |
836 | FeasibilityAnalysis(TrueBBI, BBI.BrCond, true)) { | |
837 | // Triangle: | |
838 | // EBB | |
839 | // | \_ | |
840 | // | | | |
841 | // | TBB | |
842 | // | / | |
843 | // FBB | |
844 | Tokens.push_back(new IfcvtToken(BBI, ICTriangle, TNeedSub, Dups)); | |
845 | Enqueued = true; | |
846 | } | |
847 | ||
848 | if (ValidTriangle(TrueBBI, FalseBBI, true, Dups, Prediction) && | |
849 | MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost, | |
850 | TrueBBI.ExtraCost2, Prediction) && | |
851 | FeasibilityAnalysis(TrueBBI, BBI.BrCond, true, true)) { | |
852 | Tokens.push_back(new IfcvtToken(BBI, ICTriangleRev, TNeedSub, Dups)); | |
853 | Enqueued = true; | |
854 | } | |
855 | ||
856 | if (ValidSimple(TrueBBI, Dups, Prediction) && | |
857 | MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost, | |
858 | TrueBBI.ExtraCost2, Prediction) && | |
859 | FeasibilityAnalysis(TrueBBI, BBI.BrCond)) { | |
860 | // Simple (split, no rejoin): | |
861 | // EBB | |
862 | // | \_ | |
863 | // | | | |
864 | // | TBB---> exit | |
865 | // | | |
866 | // FBB | |
867 | Tokens.push_back(new IfcvtToken(BBI, ICSimple, TNeedSub, Dups)); | |
868 | Enqueued = true; | |
869 | } | |
870 | ||
871 | if (CanRevCond) { | |
872 | // Try the other path... | |
873 | if (ValidTriangle(FalseBBI, TrueBBI, false, Dups, | |
874 | Prediction.getCompl()) && | |
875 | MeetIfcvtSizeLimit(*FalseBBI.BB, | |
876 | FalseBBI.NonPredSize + FalseBBI.ExtraCost, | |
877 | FalseBBI.ExtraCost2, Prediction.getCompl()) && | |
878 | FeasibilityAnalysis(FalseBBI, RevCond, true)) { | |
879 | Tokens.push_back(new IfcvtToken(BBI, ICTriangleFalse, FNeedSub, Dups)); | |
880 | Enqueued = true; | |
881 | } | |
882 | ||
883 | if (ValidTriangle(FalseBBI, TrueBBI, true, Dups, | |
884 | Prediction.getCompl()) && | |
885 | MeetIfcvtSizeLimit(*FalseBBI.BB, | |
886 | FalseBBI.NonPredSize + FalseBBI.ExtraCost, | |
887 | FalseBBI.ExtraCost2, Prediction.getCompl()) && | |
888 | FeasibilityAnalysis(FalseBBI, RevCond, true, true)) { | |
889 | Tokens.push_back(new IfcvtToken(BBI, ICTriangleFRev, FNeedSub, Dups)); | |
890 | Enqueued = true; | |
891 | } | |
892 | ||
893 | if (ValidSimple(FalseBBI, Dups, Prediction.getCompl()) && | |
894 | MeetIfcvtSizeLimit(*FalseBBI.BB, | |
895 | FalseBBI.NonPredSize + FalseBBI.ExtraCost, | |
896 | FalseBBI.ExtraCost2, Prediction.getCompl()) && | |
897 | FeasibilityAnalysis(FalseBBI, RevCond)) { | |
898 | Tokens.push_back(new IfcvtToken(BBI, ICSimpleFalse, FNeedSub, Dups)); | |
899 | Enqueued = true; | |
900 | } | |
901 | } | |
902 | ||
903 | BBI.IsEnqueued = Enqueued; | |
904 | BBI.IsBeingAnalyzed = false; | |
905 | BBI.IsAnalyzed = true; | |
906 | return BBI; | |
907 | } | |
908 | ||
909 | /// AnalyzeBlocks - Analyze all blocks and find entries for all if-conversion | |
910 | /// candidates. | |
911 | void IfConverter::AnalyzeBlocks(MachineFunction &MF, | |
912 | std::vector<IfcvtToken*> &Tokens) { | |
913 | for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) { | |
914 | MachineBasicBlock *BB = I; | |
915 | AnalyzeBlock(BB, Tokens); | |
916 | } | |
917 | ||
918 | // Sort to favor more complex ifcvt scheme. | |
919 | std::stable_sort(Tokens.begin(), Tokens.end(), IfcvtTokenCmp); | |
920 | } | |
921 | ||
922 | /// canFallThroughTo - Returns true either if ToBB is the next block after BB or | |
923 | /// that all the intervening blocks are empty (given BB can fall through to its | |
924 | /// next block). | |
925 | static bool canFallThroughTo(MachineBasicBlock *BB, MachineBasicBlock *ToBB) { | |
926 | MachineFunction::iterator PI = BB; | |
1a4d82fc | 927 | MachineFunction::iterator I = std::next(PI); |
223e47cc LB |
928 | MachineFunction::iterator TI = ToBB; |
929 | MachineFunction::iterator E = BB->getParent()->end(); | |
930 | while (I != TI) { | |
931 | // Check isSuccessor to avoid case where the next block is empty, but | |
932 | // it's not a successor. | |
933 | if (I == E || !I->empty() || !PI->isSuccessor(I)) | |
934 | return false; | |
935 | PI = I++; | |
936 | } | |
937 | return true; | |
938 | } | |
939 | ||
940 | /// InvalidatePreds - Invalidate predecessor BB info so it would be re-analyzed | |
941 | /// to determine if it can be if-converted. If predecessor is already enqueued, | |
942 | /// dequeue it! | |
943 | void IfConverter::InvalidatePreds(MachineBasicBlock *BB) { | |
1a4d82fc JJ |
944 | for (const auto &Predecessor : BB->predecessors()) { |
945 | BBInfo &PBBI = BBAnalysis[Predecessor->getNumber()]; | |
223e47cc LB |
946 | if (PBBI.IsDone || PBBI.BB == BB) |
947 | continue; | |
948 | PBBI.IsAnalyzed = false; | |
949 | PBBI.IsEnqueued = false; | |
950 | } | |
951 | } | |
952 | ||
953 | /// InsertUncondBranch - Inserts an unconditional branch from BB to ToBB. | |
954 | /// | |
955 | static void InsertUncondBranch(MachineBasicBlock *BB, MachineBasicBlock *ToBB, | |
956 | const TargetInstrInfo *TII) { | |
957 | DebugLoc dl; // FIXME: this is nowhere | |
958 | SmallVector<MachineOperand, 0> NoCond; | |
1a4d82fc | 959 | TII->InsertBranch(*BB, ToBB, nullptr, NoCond, dl); |
223e47cc LB |
960 | } |
961 | ||
962 | /// RemoveExtraEdges - Remove true / false edges if either / both are no longer | |
963 | /// successors. | |
964 | void IfConverter::RemoveExtraEdges(BBInfo &BBI) { | |
1a4d82fc | 965 | MachineBasicBlock *TBB = nullptr, *FBB = nullptr; |
223e47cc LB |
966 | SmallVector<MachineOperand, 4> Cond; |
967 | if (!TII->AnalyzeBranch(*BBI.BB, TBB, FBB, Cond)) | |
968 | BBI.BB->CorrectExtraCFGEdges(TBB, FBB, !Cond.empty()); | |
969 | } | |
970 | ||
1a4d82fc JJ |
971 | /// Behaves like LiveRegUnits::StepForward() but also adds implicit uses to all |
972 | /// values defined in MI which are not live/used by MI. | |
973 | static void UpdatePredRedefs(MachineInstr *MI, LivePhysRegs &Redefs) { | |
974 | for (ConstMIBundleOperands Ops(MI); Ops.isValid(); ++Ops) { | |
975 | if (!Ops->isReg() || !Ops->isKill()) | |
223e47cc | 976 | continue; |
1a4d82fc JJ |
977 | unsigned Reg = Ops->getReg(); |
978 | if (Reg == 0) | |
223e47cc | 979 | continue; |
1a4d82fc | 980 | Redefs.removeReg(Reg); |
223e47cc | 981 | } |
1a4d82fc JJ |
982 | for (MIBundleOperands Ops(MI); Ops.isValid(); ++Ops) { |
983 | if (!Ops->isReg() || !Ops->isDef()) | |
984 | continue; | |
985 | unsigned Reg = Ops->getReg(); | |
986 | if (Reg == 0 || Redefs.contains(Reg)) | |
987 | continue; | |
988 | Redefs.addReg(Reg); | |
989 | ||
990 | MachineOperand &Op = *Ops; | |
991 | MachineInstr *MI = Op.getParent(); | |
992 | MachineInstrBuilder MIB(*MI->getParent()->getParent(), MI); | |
993 | MIB.addReg(Reg, RegState::Implicit | RegState::Undef); | |
223e47cc LB |
994 | } |
995 | } | |
996 | ||
1a4d82fc JJ |
997 | /** |
998 | * Remove kill flags from operands with a registers in the @p DontKill set. | |
999 | */ | |
1000 | static void RemoveKills(MachineInstr &MI, const LivePhysRegs &DontKill) { | |
1001 | for (MIBundleOperands O(&MI); O.isValid(); ++O) { | |
1002 | if (!O->isReg() || !O->isKill()) | |
1003 | continue; | |
1004 | if (DontKill.contains(O->getReg())) | |
1005 | O->setIsKill(false); | |
223e47cc LB |
1006 | } |
1007 | } | |
1008 | ||
1a4d82fc JJ |
1009 | /** |
1010 | * Walks a range of machine instructions and removes kill flags for registers | |
1011 | * in the @p DontKill set. | |
1012 | */ | |
1013 | static void RemoveKills(MachineBasicBlock::iterator I, | |
1014 | MachineBasicBlock::iterator E, | |
1015 | const LivePhysRegs &DontKill, | |
1016 | const MCRegisterInfo &MCRI) { | |
1017 | for ( ; I != E; ++I) | |
1018 | RemoveKills(*I, DontKill); | |
1019 | } | |
1020 | ||
223e47cc LB |
1021 | /// IfConvertSimple - If convert a simple (split, no rejoin) sub-CFG. |
1022 | /// | |
1023 | bool IfConverter::IfConvertSimple(BBInfo &BBI, IfcvtKind Kind) { | |
1024 | BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()]; | |
1025 | BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()]; | |
1026 | BBInfo *CvtBBI = &TrueBBI; | |
1027 | BBInfo *NextBBI = &FalseBBI; | |
1028 | ||
1029 | SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end()); | |
1030 | if (Kind == ICSimpleFalse) | |
1031 | std::swap(CvtBBI, NextBBI); | |
1032 | ||
1033 | if (CvtBBI->IsDone || | |
1034 | (CvtBBI->CannotBeCopied && CvtBBI->BB->pred_size() > 1)) { | |
1035 | // Something has changed. It's no longer safe to predicate this block. | |
1036 | BBI.IsAnalyzed = false; | |
1037 | CvtBBI->IsAnalyzed = false; | |
1038 | return false; | |
1039 | } | |
1040 | ||
1a4d82fc JJ |
1041 | if (CvtBBI->BB->hasAddressTaken()) |
1042 | // Conservatively abort if-conversion if BB's address is taken. | |
1043 | return false; | |
1044 | ||
223e47cc LB |
1045 | if (Kind == ICSimpleFalse) |
1046 | if (TII->ReverseBranchCondition(Cond)) | |
1047 | llvm_unreachable("Unable to reverse branch condition!"); | |
1048 | ||
1049 | // Initialize liveins to the first BB. These are potentiall redefined by | |
1050 | // predicated instructions. | |
1a4d82fc JJ |
1051 | Redefs.init(TRI); |
1052 | Redefs.addLiveIns(CvtBBI->BB); | |
1053 | Redefs.addLiveIns(NextBBI->BB); | |
1054 | ||
1055 | // Compute a set of registers which must not be killed by instructions in | |
1056 | // BB1: This is everything live-in to BB2. | |
1057 | DontKill.init(TRI); | |
1058 | DontKill.addLiveIns(NextBBI->BB); | |
223e47cc LB |
1059 | |
1060 | if (CvtBBI->BB->pred_size() > 1) { | |
1061 | BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB); | |
1062 | // Copy instructions in the true block, predicate them, and add them to | |
1063 | // the entry block. | |
1a4d82fc JJ |
1064 | CopyAndPredicateBlock(BBI, *CvtBBI, Cond); |
1065 | ||
1066 | // RemoveExtraEdges won't work if the block has an unanalyzable branch, so | |
1067 | // explicitly remove CvtBBI as a successor. | |
1068 | BBI.BB->removeSuccessor(CvtBBI->BB); | |
223e47cc | 1069 | } else { |
1a4d82fc JJ |
1070 | RemoveKills(CvtBBI->BB->begin(), CvtBBI->BB->end(), DontKill, *TRI); |
1071 | PredicateBlock(*CvtBBI, CvtBBI->BB->end(), Cond); | |
223e47cc LB |
1072 | |
1073 | // Merge converted block into entry block. | |
1074 | BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB); | |
1075 | MergeBlocks(BBI, *CvtBBI); | |
1076 | } | |
1077 | ||
1078 | bool IterIfcvt = true; | |
1079 | if (!canFallThroughTo(BBI.BB, NextBBI->BB)) { | |
1080 | InsertUncondBranch(BBI.BB, NextBBI->BB, TII); | |
1081 | BBI.HasFallThrough = false; | |
1082 | // Now ifcvt'd block will look like this: | |
1083 | // BB: | |
1084 | // ... | |
1085 | // t, f = cmp | |
1086 | // if t op | |
1087 | // b BBf | |
1088 | // | |
1089 | // We cannot further ifcvt this block because the unconditional branch | |
1090 | // will have to be predicated on the new condition, that will not be | |
1091 | // available if cmp executes. | |
1092 | IterIfcvt = false; | |
1093 | } | |
1094 | ||
1095 | RemoveExtraEdges(BBI); | |
1096 | ||
1097 | // Update block info. BB can be iteratively if-converted. | |
1098 | if (!IterIfcvt) | |
1099 | BBI.IsDone = true; | |
1100 | InvalidatePreds(BBI.BB); | |
1101 | CvtBBI->IsDone = true; | |
1102 | ||
1103 | // FIXME: Must maintain LiveIns. | |
1104 | return true; | |
1105 | } | |
1106 | ||
1a4d82fc JJ |
1107 | /// Scale down weights to fit into uint32_t. NewTrue is the new weight |
1108 | /// for successor TrueBB, and NewFalse is the new weight for successor | |
1109 | /// FalseBB. | |
1110 | static void ScaleWeights(uint64_t NewTrue, uint64_t NewFalse, | |
1111 | MachineBasicBlock *MBB, | |
1112 | const MachineBasicBlock *TrueBB, | |
1113 | const MachineBasicBlock *FalseBB, | |
1114 | const MachineBranchProbabilityInfo *MBPI) { | |
1115 | uint64_t NewMax = (NewTrue > NewFalse) ? NewTrue : NewFalse; | |
1116 | uint32_t Scale = (NewMax / UINT32_MAX) + 1; | |
1117 | for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), | |
1118 | SE = MBB->succ_end(); | |
1119 | SI != SE; ++SI) { | |
1120 | if (*SI == TrueBB) | |
1121 | MBB->setSuccWeight(SI, (uint32_t)(NewTrue / Scale)); | |
1122 | else if (*SI == FalseBB) | |
1123 | MBB->setSuccWeight(SI, (uint32_t)(NewFalse / Scale)); | |
1124 | else | |
1125 | MBB->setSuccWeight(SI, MBPI->getEdgeWeight(MBB, SI) / Scale); | |
1126 | } | |
1127 | } | |
1128 | ||
223e47cc LB |
1129 | /// IfConvertTriangle - If convert a triangle sub-CFG. |
1130 | /// | |
1131 | bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) { | |
1132 | BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()]; | |
1133 | BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()]; | |
1134 | BBInfo *CvtBBI = &TrueBBI; | |
1135 | BBInfo *NextBBI = &FalseBBI; | |
1136 | DebugLoc dl; // FIXME: this is nowhere | |
1137 | ||
1138 | SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end()); | |
1139 | if (Kind == ICTriangleFalse || Kind == ICTriangleFRev) | |
1140 | std::swap(CvtBBI, NextBBI); | |
1141 | ||
1142 | if (CvtBBI->IsDone || | |
1143 | (CvtBBI->CannotBeCopied && CvtBBI->BB->pred_size() > 1)) { | |
1144 | // Something has changed. It's no longer safe to predicate this block. | |
1145 | BBI.IsAnalyzed = false; | |
1146 | CvtBBI->IsAnalyzed = false; | |
1147 | return false; | |
1148 | } | |
1149 | ||
1a4d82fc JJ |
1150 | if (CvtBBI->BB->hasAddressTaken()) |
1151 | // Conservatively abort if-conversion if BB's address is taken. | |
1152 | return false; | |
1153 | ||
223e47cc LB |
1154 | if (Kind == ICTriangleFalse || Kind == ICTriangleFRev) |
1155 | if (TII->ReverseBranchCondition(Cond)) | |
1156 | llvm_unreachable("Unable to reverse branch condition!"); | |
1157 | ||
1158 | if (Kind == ICTriangleRev || Kind == ICTriangleFRev) { | |
1159 | if (ReverseBranchCondition(*CvtBBI)) { | |
1160 | // BB has been changed, modify its predecessors (except for this | |
1161 | // one) so they don't get ifcvt'ed based on bad intel. | |
1162 | for (MachineBasicBlock::pred_iterator PI = CvtBBI->BB->pred_begin(), | |
1163 | E = CvtBBI->BB->pred_end(); PI != E; ++PI) { | |
1164 | MachineBasicBlock *PBB = *PI; | |
1165 | if (PBB == BBI.BB) | |
1166 | continue; | |
1167 | BBInfo &PBBI = BBAnalysis[PBB->getNumber()]; | |
1168 | if (PBBI.IsEnqueued) { | |
1169 | PBBI.IsAnalyzed = false; | |
1170 | PBBI.IsEnqueued = false; | |
1171 | } | |
1172 | } | |
1173 | } | |
1174 | } | |
1175 | ||
1176 | // Initialize liveins to the first BB. These are potentially redefined by | |
1177 | // predicated instructions. | |
1a4d82fc JJ |
1178 | Redefs.init(TRI); |
1179 | Redefs.addLiveIns(CvtBBI->BB); | |
1180 | Redefs.addLiveIns(NextBBI->BB); | |
1181 | ||
1182 | DontKill.clear(); | |
1183 | ||
1184 | bool HasEarlyExit = CvtBBI->FalseBB != nullptr; | |
1185 | uint64_t CvtNext = 0, CvtFalse = 0, BBNext = 0, BBCvt = 0, SumWeight = 0; | |
1186 | uint32_t WeightScale = 0; | |
1187 | ||
1188 | if (HasEarlyExit) { | |
1189 | // Get weights before modifying CvtBBI->BB and BBI.BB. | |
1190 | CvtNext = MBPI->getEdgeWeight(CvtBBI->BB, NextBBI->BB); | |
1191 | CvtFalse = MBPI->getEdgeWeight(CvtBBI->BB, CvtBBI->FalseBB); | |
1192 | BBNext = MBPI->getEdgeWeight(BBI.BB, NextBBI->BB); | |
1193 | BBCvt = MBPI->getEdgeWeight(BBI.BB, CvtBBI->BB); | |
1194 | SumWeight = MBPI->getSumForBlock(CvtBBI->BB, WeightScale); | |
1195 | } | |
223e47cc | 1196 | |
223e47cc LB |
1197 | if (CvtBBI->BB->pred_size() > 1) { |
1198 | BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB); | |
1199 | // Copy instructions in the true block, predicate them, and add them to | |
1200 | // the entry block. | |
1a4d82fc JJ |
1201 | CopyAndPredicateBlock(BBI, *CvtBBI, Cond, true); |
1202 | ||
1203 | // RemoveExtraEdges won't work if the block has an unanalyzable branch, so | |
1204 | // explicitly remove CvtBBI as a successor. | |
1205 | BBI.BB->removeSuccessor(CvtBBI->BB); | |
223e47cc LB |
1206 | } else { |
1207 | // Predicate the 'true' block after removing its branch. | |
1208 | CvtBBI->NonPredSize -= TII->RemoveBranch(*CvtBBI->BB); | |
1a4d82fc | 1209 | PredicateBlock(*CvtBBI, CvtBBI->BB->end(), Cond); |
223e47cc LB |
1210 | |
1211 | // Now merge the entry of the triangle with the true block. | |
1212 | BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB); | |
1213 | MergeBlocks(BBI, *CvtBBI, false); | |
1214 | } | |
1215 | ||
1216 | // If 'true' block has a 'false' successor, add an exit branch to it. | |
1217 | if (HasEarlyExit) { | |
1218 | SmallVector<MachineOperand, 4> RevCond(CvtBBI->BrCond.begin(), | |
1219 | CvtBBI->BrCond.end()); | |
1220 | if (TII->ReverseBranchCondition(RevCond)) | |
1221 | llvm_unreachable("Unable to reverse branch condition!"); | |
1a4d82fc | 1222 | TII->InsertBranch(*BBI.BB, CvtBBI->FalseBB, nullptr, RevCond, dl); |
223e47cc | 1223 | BBI.BB->addSuccessor(CvtBBI->FalseBB); |
1a4d82fc JJ |
1224 | // Update the edge weight for both CvtBBI->FalseBB and NextBBI. |
1225 | // New_Weight(BBI.BB, NextBBI->BB) = | |
1226 | // Weight(BBI.BB, NextBBI->BB) * getSumForBlock(CvtBBI->BB) + | |
1227 | // Weight(BBI.BB, CvtBBI->BB) * Weight(CvtBBI->BB, NextBBI->BB) | |
1228 | // New_Weight(BBI.BB, CvtBBI->FalseBB) = | |
1229 | // Weight(BBI.BB, CvtBBI->BB) * Weight(CvtBBI->BB, CvtBBI->FalseBB) | |
1230 | ||
1231 | uint64_t NewNext = BBNext * SumWeight + (BBCvt * CvtNext) / WeightScale; | |
1232 | uint64_t NewFalse = (BBCvt * CvtFalse) / WeightScale; | |
1233 | // We need to scale down all weights of BBI.BB to fit uint32_t. | |
1234 | // Here BBI.BB is connected to CvtBBI->FalseBB and will fall through to | |
1235 | // the next block. | |
1236 | ScaleWeights(NewNext, NewFalse, BBI.BB, getNextBlock(BBI.BB), | |
1237 | CvtBBI->FalseBB, MBPI); | |
223e47cc LB |
1238 | } |
1239 | ||
1240 | // Merge in the 'false' block if the 'false' block has no other | |
1241 | // predecessors. Otherwise, add an unconditional branch to 'false'. | |
1242 | bool FalseBBDead = false; | |
1243 | bool IterIfcvt = true; | |
1244 | bool isFallThrough = canFallThroughTo(BBI.BB, NextBBI->BB); | |
1245 | if (!isFallThrough) { | |
1246 | // Only merge them if the true block does not fallthrough to the false | |
1247 | // block. By not merging them, we make it possible to iteratively | |
1248 | // ifcvt the blocks. | |
1249 | if (!HasEarlyExit && | |
1a4d82fc JJ |
1250 | NextBBI->BB->pred_size() == 1 && !NextBBI->HasFallThrough && |
1251 | !NextBBI->BB->hasAddressTaken()) { | |
223e47cc LB |
1252 | MergeBlocks(BBI, *NextBBI); |
1253 | FalseBBDead = true; | |
1254 | } else { | |
1255 | InsertUncondBranch(BBI.BB, NextBBI->BB, TII); | |
1256 | BBI.HasFallThrough = false; | |
1257 | } | |
1258 | // Mixed predicated and unpredicated code. This cannot be iteratively | |
1259 | // predicated. | |
1260 | IterIfcvt = false; | |
1261 | } | |
1262 | ||
1263 | RemoveExtraEdges(BBI); | |
1264 | ||
1265 | // Update block info. BB can be iteratively if-converted. | |
1266 | if (!IterIfcvt) | |
1267 | BBI.IsDone = true; | |
1268 | InvalidatePreds(BBI.BB); | |
1269 | CvtBBI->IsDone = true; | |
1270 | if (FalseBBDead) | |
1271 | NextBBI->IsDone = true; | |
1272 | ||
1273 | // FIXME: Must maintain LiveIns. | |
1274 | return true; | |
1275 | } | |
1276 | ||
1277 | /// IfConvertDiamond - If convert a diamond sub-CFG. | |
1278 | /// | |
1279 | bool IfConverter::IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind, | |
1280 | unsigned NumDups1, unsigned NumDups2) { | |
1281 | BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()]; | |
1282 | BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()]; | |
1283 | MachineBasicBlock *TailBB = TrueBBI.TrueBB; | |
1284 | // True block must fall through or end with an unanalyzable terminator. | |
1285 | if (!TailBB) { | |
1286 | if (blockAlwaysFallThrough(TrueBBI)) | |
1287 | TailBB = FalseBBI.TrueBB; | |
1288 | assert((TailBB || !TrueBBI.IsBrAnalyzable) && "Unexpected!"); | |
1289 | } | |
1290 | ||
1291 | if (TrueBBI.IsDone || FalseBBI.IsDone || | |
1292 | TrueBBI.BB->pred_size() > 1 || | |
1293 | FalseBBI.BB->pred_size() > 1) { | |
1294 | // Something has changed. It's no longer safe to predicate these blocks. | |
1295 | BBI.IsAnalyzed = false; | |
1296 | TrueBBI.IsAnalyzed = false; | |
1297 | FalseBBI.IsAnalyzed = false; | |
1298 | return false; | |
1299 | } | |
1300 | ||
1a4d82fc JJ |
1301 | if (TrueBBI.BB->hasAddressTaken() || FalseBBI.BB->hasAddressTaken()) |
1302 | // Conservatively abort if-conversion if either BB has its address taken. | |
1303 | return false; | |
1304 | ||
223e47cc LB |
1305 | // Put the predicated instructions from the 'true' block before the |
1306 | // instructions from the 'false' block, unless the true block would clobber | |
1307 | // the predicate, in which case, do the opposite. | |
1308 | BBInfo *BBI1 = &TrueBBI; | |
1309 | BBInfo *BBI2 = &FalseBBI; | |
1310 | SmallVector<MachineOperand, 4> RevCond(BBI.BrCond.begin(), BBI.BrCond.end()); | |
1311 | if (TII->ReverseBranchCondition(RevCond)) | |
1312 | llvm_unreachable("Unable to reverse branch condition!"); | |
1313 | SmallVector<MachineOperand, 4> *Cond1 = &BBI.BrCond; | |
1314 | SmallVector<MachineOperand, 4> *Cond2 = &RevCond; | |
1315 | ||
1316 | // Figure out the more profitable ordering. | |
1317 | bool DoSwap = false; | |
1318 | if (TrueBBI.ClobbersPred && !FalseBBI.ClobbersPred) | |
1319 | DoSwap = true; | |
1320 | else if (TrueBBI.ClobbersPred == FalseBBI.ClobbersPred) { | |
1321 | if (TrueBBI.NonPredSize > FalseBBI.NonPredSize) | |
1322 | DoSwap = true; | |
1323 | } | |
1324 | if (DoSwap) { | |
1325 | std::swap(BBI1, BBI2); | |
1326 | std::swap(Cond1, Cond2); | |
1327 | } | |
1328 | ||
1329 | // Remove the conditional branch from entry to the blocks. | |
1330 | BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB); | |
1331 | ||
1332 | // Initialize liveins to the first BB. These are potentially redefined by | |
1333 | // predicated instructions. | |
1a4d82fc JJ |
1334 | Redefs.init(TRI); |
1335 | Redefs.addLiveIns(BBI1->BB); | |
223e47cc LB |
1336 | |
1337 | // Remove the duplicated instructions at the beginnings of both paths. | |
1338 | MachineBasicBlock::iterator DI1 = BBI1->BB->begin(); | |
1339 | MachineBasicBlock::iterator DI2 = BBI2->BB->begin(); | |
1340 | MachineBasicBlock::iterator DIE1 = BBI1->BB->end(); | |
1341 | MachineBasicBlock::iterator DIE2 = BBI2->BB->end(); | |
1342 | // Skip dbg_value instructions | |
1343 | while (DI1 != DIE1 && DI1->isDebugValue()) | |
1344 | ++DI1; | |
1345 | while (DI2 != DIE2 && DI2->isDebugValue()) | |
1346 | ++DI2; | |
1347 | BBI1->NonPredSize -= NumDups1; | |
1348 | BBI2->NonPredSize -= NumDups1; | |
1349 | ||
1350 | // Skip past the dups on each side separately since there may be | |
1351 | // differing dbg_value entries. | |
1352 | for (unsigned i = 0; i < NumDups1; ++DI1) { | |
1353 | if (!DI1->isDebugValue()) | |
1354 | ++i; | |
1355 | } | |
1356 | while (NumDups1 != 0) { | |
1357 | ++DI2; | |
1358 | if (!DI2->isDebugValue()) | |
1359 | --NumDups1; | |
1360 | } | |
1361 | ||
1a4d82fc JJ |
1362 | // Compute a set of registers which must not be killed by instructions in BB1: |
1363 | // This is everything used+live in BB2 after the duplicated instructions. We | |
1364 | // can compute this set by simulating liveness backwards from the end of BB2. | |
1365 | DontKill.init(TRI); | |
1366 | for (MachineBasicBlock::reverse_iterator I = BBI2->BB->rbegin(), | |
1367 | E = MachineBasicBlock::reverse_iterator(DI2); I != E; ++I) { | |
1368 | DontKill.stepBackward(*I); | |
1369 | } | |
1370 | ||
1371 | for (MachineBasicBlock::const_iterator I = BBI1->BB->begin(), E = DI1; I != E; | |
1372 | ++I) { | |
1373 | Redefs.stepForward(*I); | |
1374 | } | |
223e47cc LB |
1375 | BBI.BB->splice(BBI.BB->end(), BBI1->BB, BBI1->BB->begin(), DI1); |
1376 | BBI2->BB->erase(BBI2->BB->begin(), DI2); | |
1377 | ||
1378 | // Remove branch from 'true' block and remove duplicated instructions. | |
1379 | BBI1->NonPredSize -= TII->RemoveBranch(*BBI1->BB); | |
1380 | DI1 = BBI1->BB->end(); | |
1381 | for (unsigned i = 0; i != NumDups2; ) { | |
1382 | // NumDups2 only counted non-dbg_value instructions, so this won't | |
1383 | // run off the head of the list. | |
1384 | assert (DI1 != BBI1->BB->begin()); | |
1385 | --DI1; | |
1386 | // skip dbg_value instructions | |
1387 | if (!DI1->isDebugValue()) | |
1388 | ++i; | |
1389 | } | |
1390 | BBI1->BB->erase(DI1, BBI1->BB->end()); | |
1391 | ||
1a4d82fc JJ |
1392 | // Kill flags in the true block for registers living into the false block |
1393 | // must be removed. | |
1394 | RemoveKills(BBI1->BB->begin(), BBI1->BB->end(), DontKill, *TRI); | |
1395 | ||
223e47cc LB |
1396 | // Remove 'false' block branch and find the last instruction to predicate. |
1397 | BBI2->NonPredSize -= TII->RemoveBranch(*BBI2->BB); | |
1398 | DI2 = BBI2->BB->end(); | |
1399 | while (NumDups2 != 0) { | |
1400 | // NumDups2 only counted non-dbg_value instructions, so this won't | |
1401 | // run off the head of the list. | |
1402 | assert (DI2 != BBI2->BB->begin()); | |
1403 | --DI2; | |
1404 | // skip dbg_value instructions | |
1405 | if (!DI2->isDebugValue()) | |
1406 | --NumDups2; | |
1407 | } | |
1408 | ||
1409 | // Remember which registers would later be defined by the false block. | |
1410 | // This allows us not to predicate instructions in the true block that would | |
1411 | // later be re-defined. That is, rather than | |
1412 | // subeq r0, r1, #1 | |
1413 | // addne r0, r1, #1 | |
1414 | // generate: | |
1415 | // sub r0, r1, #1 | |
1416 | // addne r0, r1, #1 | |
1417 | SmallSet<unsigned, 4> RedefsByFalse; | |
1418 | SmallSet<unsigned, 4> ExtUses; | |
1419 | if (TII->isProfitableToUnpredicate(*BBI1->BB, *BBI2->BB)) { | |
1420 | for (MachineBasicBlock::iterator FI = BBI2->BB->begin(); FI != DI2; ++FI) { | |
1421 | if (FI->isDebugValue()) | |
1422 | continue; | |
1423 | SmallVector<unsigned, 4> Defs; | |
1424 | for (unsigned i = 0, e = FI->getNumOperands(); i != e; ++i) { | |
1425 | const MachineOperand &MO = FI->getOperand(i); | |
1426 | if (!MO.isReg()) | |
1427 | continue; | |
1428 | unsigned Reg = MO.getReg(); | |
1429 | if (!Reg) | |
1430 | continue; | |
1431 | if (MO.isDef()) { | |
1432 | Defs.push_back(Reg); | |
1433 | } else if (!RedefsByFalse.count(Reg)) { | |
1434 | // These are defined before ctrl flow reach the 'false' instructions. | |
1435 | // They cannot be modified by the 'true' instructions. | |
1a4d82fc JJ |
1436 | for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true); |
1437 | SubRegs.isValid(); ++SubRegs) | |
223e47cc LB |
1438 | ExtUses.insert(*SubRegs); |
1439 | } | |
1440 | } | |
1441 | ||
1442 | for (unsigned i = 0, e = Defs.size(); i != e; ++i) { | |
1443 | unsigned Reg = Defs[i]; | |
1444 | if (!ExtUses.count(Reg)) { | |
1a4d82fc JJ |
1445 | for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true); |
1446 | SubRegs.isValid(); ++SubRegs) | |
223e47cc LB |
1447 | RedefsByFalse.insert(*SubRegs); |
1448 | } | |
1449 | } | |
1450 | } | |
1451 | } | |
1452 | ||
1453 | // Predicate the 'true' block. | |
1a4d82fc | 1454 | PredicateBlock(*BBI1, BBI1->BB->end(), *Cond1, &RedefsByFalse); |
223e47cc LB |
1455 | |
1456 | // Predicate the 'false' block. | |
1a4d82fc | 1457 | PredicateBlock(*BBI2, DI2, *Cond2); |
223e47cc LB |
1458 | |
1459 | // Merge the true block into the entry of the diamond. | |
1a4d82fc JJ |
1460 | MergeBlocks(BBI, *BBI1, TailBB == nullptr); |
1461 | MergeBlocks(BBI, *BBI2, TailBB == nullptr); | |
223e47cc LB |
1462 | |
1463 | // If the if-converted block falls through or unconditionally branches into | |
1464 | // the tail block, and the tail block does not have other predecessors, then | |
1465 | // fold the tail block in as well. Otherwise, unless it falls through to the | |
1466 | // tail, add a unconditional branch to it. | |
1467 | if (TailBB) { | |
1468 | BBInfo &TailBBI = BBAnalysis[TailBB->getNumber()]; | |
1a4d82fc JJ |
1469 | bool CanMergeTail = !TailBBI.HasFallThrough && |
1470 | !TailBBI.BB->hasAddressTaken(); | |
223e47cc LB |
1471 | // There may still be a fall-through edge from BBI1 or BBI2 to TailBB; |
1472 | // check if there are any other predecessors besides those. | |
1473 | unsigned NumPreds = TailBB->pred_size(); | |
1474 | if (NumPreds > 1) | |
1475 | CanMergeTail = false; | |
1476 | else if (NumPreds == 1 && CanMergeTail) { | |
1477 | MachineBasicBlock::pred_iterator PI = TailBB->pred_begin(); | |
1478 | if (*PI != BBI1->BB && *PI != BBI2->BB) | |
1479 | CanMergeTail = false; | |
1480 | } | |
1481 | if (CanMergeTail) { | |
1482 | MergeBlocks(BBI, TailBBI); | |
1483 | TailBBI.IsDone = true; | |
1484 | } else { | |
1485 | BBI.BB->addSuccessor(TailBB); | |
1486 | InsertUncondBranch(BBI.BB, TailBB, TII); | |
1487 | BBI.HasFallThrough = false; | |
1488 | } | |
1489 | } | |
1490 | ||
1491 | // RemoveExtraEdges won't work if the block has an unanalyzable branch, | |
1492 | // which can happen here if TailBB is unanalyzable and is merged, so | |
1493 | // explicitly remove BBI1 and BBI2 as successors. | |
1494 | BBI.BB->removeSuccessor(BBI1->BB); | |
1495 | BBI.BB->removeSuccessor(BBI2->BB); | |
1496 | RemoveExtraEdges(BBI); | |
1497 | ||
1498 | // Update block info. | |
1499 | BBI.IsDone = TrueBBI.IsDone = FalseBBI.IsDone = true; | |
1500 | InvalidatePreds(BBI.BB); | |
1501 | ||
1502 | // FIXME: Must maintain LiveIns. | |
1503 | return true; | |
1504 | } | |
1505 | ||
1506 | static bool MaySpeculate(const MachineInstr *MI, | |
1507 | SmallSet<unsigned, 4> &LaterRedefs, | |
1508 | const TargetInstrInfo *TII) { | |
1509 | bool SawStore = true; | |
1a4d82fc | 1510 | if (!MI->isSafeToMove(TII, nullptr, SawStore)) |
223e47cc LB |
1511 | return false; |
1512 | ||
1513 | for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { | |
1514 | const MachineOperand &MO = MI->getOperand(i); | |
1515 | if (!MO.isReg()) | |
1516 | continue; | |
1517 | unsigned Reg = MO.getReg(); | |
1518 | if (!Reg) | |
1519 | continue; | |
1520 | if (MO.isDef() && !LaterRedefs.count(Reg)) | |
1521 | return false; | |
1522 | } | |
1523 | ||
1524 | return true; | |
1525 | } | |
1526 | ||
1527 | /// PredicateBlock - Predicate instructions from the start of the block to the | |
1528 | /// specified end with the specified condition. | |
1529 | void IfConverter::PredicateBlock(BBInfo &BBI, | |
1530 | MachineBasicBlock::iterator E, | |
1531 | SmallVectorImpl<MachineOperand> &Cond, | |
223e47cc LB |
1532 | SmallSet<unsigned, 4> *LaterRedefs) { |
1533 | bool AnyUnpred = false; | |
1a4d82fc | 1534 | bool MaySpec = LaterRedefs != nullptr; |
223e47cc LB |
1535 | for (MachineBasicBlock::iterator I = BBI.BB->begin(); I != E; ++I) { |
1536 | if (I->isDebugValue() || TII->isPredicated(I)) | |
1537 | continue; | |
1538 | // It may be possible not to predicate an instruction if it's the 'true' | |
1539 | // side of a diamond and the 'false' side may re-define the instruction's | |
1540 | // defs. | |
1541 | if (MaySpec && MaySpeculate(I, *LaterRedefs, TII)) { | |
1542 | AnyUnpred = true; | |
1543 | continue; | |
1544 | } | |
1545 | // If any instruction is predicated, then every instruction after it must | |
1546 | // be predicated. | |
1547 | MaySpec = false; | |
1548 | if (!TII->PredicateInstruction(I, Cond)) { | |
1549 | #ifndef NDEBUG | |
1550 | dbgs() << "Unable to predicate " << *I << "!\n"; | |
1551 | #endif | |
1a4d82fc | 1552 | llvm_unreachable(nullptr); |
223e47cc LB |
1553 | } |
1554 | ||
1555 | // If the predicated instruction now redefines a register as the result of | |
1556 | // if-conversion, add an implicit kill. | |
1a4d82fc | 1557 | UpdatePredRedefs(I, Redefs); |
223e47cc LB |
1558 | } |
1559 | ||
1560 | std::copy(Cond.begin(), Cond.end(), std::back_inserter(BBI.Predicate)); | |
1561 | ||
1562 | BBI.IsAnalyzed = false; | |
1563 | BBI.NonPredSize = 0; | |
1564 | ||
1565 | ++NumIfConvBBs; | |
1566 | if (AnyUnpred) | |
1567 | ++NumUnpred; | |
1568 | } | |
1569 | ||
1570 | /// CopyAndPredicateBlock - Copy and predicate instructions from source BB to | |
1571 | /// the destination block. Skip end of block branches if IgnoreBr is true. | |
1572 | void IfConverter::CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI, | |
1573 | SmallVectorImpl<MachineOperand> &Cond, | |
223e47cc LB |
1574 | bool IgnoreBr) { |
1575 | MachineFunction &MF = *ToBBI.BB->getParent(); | |
1576 | ||
1577 | for (MachineBasicBlock::iterator I = FromBBI.BB->begin(), | |
1578 | E = FromBBI.BB->end(); I != E; ++I) { | |
1579 | // Do not copy the end of the block branches. | |
1580 | if (IgnoreBr && I->isBranch()) | |
1581 | break; | |
1582 | ||
1583 | MachineInstr *MI = MF.CloneMachineInstr(I); | |
1584 | ToBBI.BB->insert(ToBBI.BB->end(), MI); | |
1585 | ToBBI.NonPredSize++; | |
1a4d82fc JJ |
1586 | unsigned ExtraPredCost = TII->getPredicationCost(&*I); |
1587 | unsigned NumCycles = SchedModel.computeInstrLatency(&*I, false); | |
223e47cc LB |
1588 | if (NumCycles > 1) |
1589 | ToBBI.ExtraCost += NumCycles-1; | |
1590 | ToBBI.ExtraCost2 += ExtraPredCost; | |
1591 | ||
1592 | if (!TII->isPredicated(I) && !MI->isDebugValue()) { | |
1593 | if (!TII->PredicateInstruction(MI, Cond)) { | |
1594 | #ifndef NDEBUG | |
1595 | dbgs() << "Unable to predicate " << *I << "!\n"; | |
1596 | #endif | |
1a4d82fc | 1597 | llvm_unreachable(nullptr); |
223e47cc LB |
1598 | } |
1599 | } | |
1600 | ||
1601 | // If the predicated instruction now redefines a register as the result of | |
1602 | // if-conversion, add an implicit kill. | |
1a4d82fc JJ |
1603 | UpdatePredRedefs(MI, Redefs); |
1604 | ||
1605 | // Some kill flags may not be correct anymore. | |
1606 | if (!DontKill.empty()) | |
1607 | RemoveKills(*MI, DontKill); | |
223e47cc LB |
1608 | } |
1609 | ||
1610 | if (!IgnoreBr) { | |
1611 | std::vector<MachineBasicBlock *> Succs(FromBBI.BB->succ_begin(), | |
1612 | FromBBI.BB->succ_end()); | |
1613 | MachineBasicBlock *NBB = getNextBlock(FromBBI.BB); | |
1a4d82fc | 1614 | MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : nullptr; |
223e47cc LB |
1615 | |
1616 | for (unsigned i = 0, e = Succs.size(); i != e; ++i) { | |
1617 | MachineBasicBlock *Succ = Succs[i]; | |
1618 | // Fallthrough edge can't be transferred. | |
1619 | if (Succ == FallThrough) | |
1620 | continue; | |
1621 | ToBBI.BB->addSuccessor(Succ); | |
1622 | } | |
1623 | } | |
1624 | ||
1625 | std::copy(FromBBI.Predicate.begin(), FromBBI.Predicate.end(), | |
1626 | std::back_inserter(ToBBI.Predicate)); | |
1627 | std::copy(Cond.begin(), Cond.end(), std::back_inserter(ToBBI.Predicate)); | |
1628 | ||
1629 | ToBBI.ClobbersPred |= FromBBI.ClobbersPred; | |
1630 | ToBBI.IsAnalyzed = false; | |
1631 | ||
1632 | ++NumDupBBs; | |
1633 | } | |
1634 | ||
1635 | /// MergeBlocks - Move all instructions from FromBB to the end of ToBB. | |
1636 | /// This will leave FromBB as an empty block, so remove all of its | |
1637 | /// successor edges except for the fall-through edge. If AddEdges is true, | |
1638 | /// i.e., when FromBBI's branch is being moved, add those successor edges to | |
1639 | /// ToBBI. | |
1640 | void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges) { | |
1a4d82fc JJ |
1641 | assert(!FromBBI.BB->hasAddressTaken() && |
1642 | "Removing a BB whose address is taken!"); | |
1643 | ||
223e47cc LB |
1644 | ToBBI.BB->splice(ToBBI.BB->end(), |
1645 | FromBBI.BB, FromBBI.BB->begin(), FromBBI.BB->end()); | |
1646 | ||
1647 | std::vector<MachineBasicBlock *> Succs(FromBBI.BB->succ_begin(), | |
1648 | FromBBI.BB->succ_end()); | |
1649 | MachineBasicBlock *NBB = getNextBlock(FromBBI.BB); | |
1a4d82fc | 1650 | MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : nullptr; |
223e47cc LB |
1651 | |
1652 | for (unsigned i = 0, e = Succs.size(); i != e; ++i) { | |
1653 | MachineBasicBlock *Succ = Succs[i]; | |
1654 | // Fallthrough edge can't be transferred. | |
1655 | if (Succ == FallThrough) | |
1656 | continue; | |
1657 | FromBBI.BB->removeSuccessor(Succ); | |
970d7e83 | 1658 | if (AddEdges && !ToBBI.BB->isSuccessor(Succ)) |
223e47cc LB |
1659 | ToBBI.BB->addSuccessor(Succ); |
1660 | } | |
1661 | ||
1662 | // Now FromBBI always falls through to the next block! | |
1663 | if (NBB && !FromBBI.BB->isSuccessor(NBB)) | |
1664 | FromBBI.BB->addSuccessor(NBB); | |
1665 | ||
1666 | std::copy(FromBBI.Predicate.begin(), FromBBI.Predicate.end(), | |
1667 | std::back_inserter(ToBBI.Predicate)); | |
1668 | FromBBI.Predicate.clear(); | |
1669 | ||
1670 | ToBBI.NonPredSize += FromBBI.NonPredSize; | |
1671 | ToBBI.ExtraCost += FromBBI.ExtraCost; | |
1672 | ToBBI.ExtraCost2 += FromBBI.ExtraCost2; | |
1673 | FromBBI.NonPredSize = 0; | |
1674 | FromBBI.ExtraCost = 0; | |
1675 | FromBBI.ExtraCost2 = 0; | |
1676 | ||
1677 | ToBBI.ClobbersPred |= FromBBI.ClobbersPred; | |
1678 | ToBBI.HasFallThrough = FromBBI.HasFallThrough; | |
1679 | ToBBI.IsAnalyzed = false; | |
1680 | FromBBI.IsAnalyzed = false; | |
1681 | } |