1//====- X86CmovConversion.cpp - Convert Cmov to Branch --------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9/// \file
10/// This file implements a pass that converts X86 cmov instructions into
11/// branches when profitable. This pass is conservative. It transforms if and
12/// only if it can guarantee a gain with high confidence.
13///
14/// Thus, the optimization applies under the following conditions:
15/// 1. Consider as candidates only CMOVs in innermost loops (assume that
16/// most hotspots are represented by these loops).
17/// 2. Given a group of CMOV instructions that are using the same EFLAGS def
18/// instruction:
19/// a. Consider them as candidates only if all have the same code condition
20/// or the opposite one to prevent generating more than one conditional
21/// jump per EFLAGS def instruction.
22/// b. Consider them as candidates only if all are profitable to be
23/// converted (assume that one bad conversion may cause a degradation).
24/// 3. Apply conversion only for loops that are found profitable and only for
25/// CMOV candidates that were found profitable.
26/// a. A loop is considered profitable only if conversion will reduce its
27/// depth cost by some threshold.
28/// b. CMOV is considered profitable if the cost of its condition is higher
29/// than the average cost of its true-value and false-value by 25% of
30/// branch-misprediction-penalty. This assures no degradation even with
31/// 25% branch misprediction.
32///
33/// Note: This pass is assumed to run on SSA machine code.
34//
35//===----------------------------------------------------------------------===//
36//
37// External interfaces:
38// FunctionPass *llvm::createX86CmovConverterPass();
39// bool X86CmovConverterPass::runOnMachineFunction(MachineFunction &MF);
40//
41//===----------------------------------------------------------------------===//
42
43#include "X86.h"
44#include "X86InstrInfo.h"
45#include "llvm/ADT/ArrayRef.h"
46#include "llvm/ADT/DenseMap.h"
47#include "llvm/ADT/STLExtras.h"
48#include "llvm/ADT/SmallPtrSet.h"
49#include "llvm/ADT/SmallVector.h"
50#include "llvm/ADT/Statistic.h"
51#include "llvm/CodeGen/MachineBasicBlock.h"
52#include "llvm/CodeGen/MachineFunction.h"
53#include "llvm/CodeGen/MachineFunctionPass.h"
54#include "llvm/CodeGen/MachineInstr.h"
55#include "llvm/CodeGen/MachineInstrBuilder.h"
56#include "llvm/CodeGen/MachineLoopInfo.h"
57#include "llvm/CodeGen/MachineOperand.h"
58#include "llvm/CodeGen/MachineRegisterInfo.h"
59#include "llvm/CodeGen/TargetInstrInfo.h"
60#include "llvm/CodeGen/TargetRegisterInfo.h"
61#include "llvm/CodeGen/TargetSchedule.h"
62#include "llvm/CodeGen/TargetSubtargetInfo.h"
63#include "llvm/IR/DebugLoc.h"
64#include "llvm/InitializePasses.h"
65#include "llvm/MC/MCSchedule.h"
66#include "llvm/Pass.h"
67#include "llvm/Support/CommandLine.h"
68#include "llvm/Support/Debug.h"
69#include "llvm/Support/raw_ostream.h"
70#include "llvm/Target/CGPassBuilderOption.h"
71#include <algorithm>
72#include <cassert>
73#include <iterator>
74#include <utility>
75
76using namespace llvm;
77
78#define DEBUG_TYPE "x86-cmov-conversion"
79
80STATISTIC(NumOfSkippedCmovGroups, "Number of unsupported CMOV-groups");
81STATISTIC(NumOfCmovGroupCandidate, "Number of CMOV-group candidates");
82STATISTIC(NumOfLoopCandidate, "Number of CMOV-conversion profitable loops");
83STATISTIC(NumOfOptimizedCmovGroups, "Number of optimized CMOV-groups");
84
85// This internal switch can be used to turn off the cmov/branch optimization.
86static cl::opt<bool>
87 EnableCmovConverter("x86-cmov-converter",
88 cl::desc("Enable the X86 cmov-to-branch optimization."),
89 cl::init(Val: true), cl::Hidden);
90
91static cl::opt<unsigned>
92 GainCycleThreshold("x86-cmov-converter-threshold",
93 cl::desc("Minimum gain per loop (in cycles) threshold."),
94 cl::init(Val: 4), cl::Hidden);
95
96static cl::opt<bool> ForceMemOperand(
97 "x86-cmov-converter-force-mem-operand",
98 cl::desc("Convert cmovs to branches whenever they have memory operands."),
99 cl::init(Val: true), cl::Hidden);
100
101static cl::opt<bool> ForceAll(
102 "x86-cmov-converter-force-all",
103 cl::desc("Convert all cmovs to branches."),
104 cl::init(Val: false), cl::Hidden);
105
106namespace {
107
108/// Converts X86 cmov instructions into branches when profitable.
109class X86CmovConversionImpl {
110public:
111 X86CmovConversionImpl(MachineLoopInfo *MLI) : MLI(MLI) {}
112
113 bool runOnMachineFunction(MachineFunction &MF);
114
115private:
116 MachineRegisterInfo *MRI = nullptr;
117 const TargetInstrInfo *TII = nullptr;
118 const TargetRegisterInfo *TRI = nullptr;
119 const TargetSubtargetInfo *STI = nullptr;
120 MachineLoopInfo *MLI = nullptr;
121 TargetSchedModel TSchedModel;
122
123 /// List of consecutive CMOV instructions.
124 using CmovGroup = SmallVector<MachineInstr *, 2>;
125 using CmovGroups = SmallVector<CmovGroup, 2>;
126
127 /// Collect all CMOV-group-candidates in \p CurrLoop and update \p
128 /// CmovInstGroups accordingly.
129 ///
130 /// \param Blocks List of blocks to process.
131 /// \param CmovInstGroups List of consecutive CMOV instructions in CurrLoop.
132 /// \returns true iff it found any CMOV-group-candidate.
133 bool collectCmovCandidates(ArrayRef<MachineBasicBlock *> Blocks,
134 CmovGroups &CmovInstGroups,
135 bool IncludeLoads = false);
136
137 /// Check if it is profitable to transform each CMOV-group-candidates into
138 /// branch. Remove all groups that are not profitable from \p CmovInstGroups.
139 ///
140 /// \param Blocks List of blocks to process.
141 /// \param CmovInstGroups List of consecutive CMOV instructions in CurrLoop.
142 /// \returns true iff any CMOV-group-candidate remain.
143 bool checkForProfitableCmovCandidates(ArrayRef<MachineBasicBlock *> Blocks,
144 CmovGroups &CmovInstGroups);
145
146 /// Convert the given list of consecutive CMOV instructions into a branch.
147 ///
148 /// \param Group Consecutive CMOV instructions to be converted into branch.
149 void convertCmovInstsToBranches(SmallVectorImpl<MachineInstr *> &Group) const;
150};
151
152class X86CmovConversionLegacy : public MachineFunctionPass {
153public:
154 X86CmovConversionLegacy() : MachineFunctionPass(ID) {}
155
156 StringRef getPassName() const override { return "X86 cmov Conversion"; }
157 bool runOnMachineFunction(MachineFunction &MF) override;
158 void getAnalysisUsage(AnalysisUsage &AU) const override;
159
160 /// Pass identification, replacement for typeid.
161 static char ID;
162};
163
164} // end anonymous namespace
165
166char X86CmovConversionLegacy::ID = 0;
167
168void X86CmovConversionLegacy::getAnalysisUsage(AnalysisUsage &AU) const {
169 MachineFunctionPass::getAnalysisUsage(AU);
170 AU.addRequired<MachineLoopInfoWrapperPass>();
171}
172
173bool X86CmovConversionImpl::runOnMachineFunction(MachineFunction &MF) {
174 if (!EnableCmovConverter)
175 return false;
176
177 // If the SelectOptimize pass is enabled, cmovs have already been optimized.
178 if (!getCGPassBuilderOption().DisableSelectOptimize)
179 return false;
180
181 LLVM_DEBUG(dbgs() << "********** " << DEBUG_TYPE << " : " << MF.getName()
182 << "**********\n");
183
184 bool Changed = false;
185 STI = &MF.getSubtarget();
186 MRI = &MF.getRegInfo();
187 TII = STI->getInstrInfo();
188 TRI = STI->getRegisterInfo();
189 TSchedModel.init(TSInfo: STI);
190
191 // Before we handle the more subtle cases of register-register CMOVs inside
192 // of potentially hot loops, we want to quickly remove all CMOVs (ForceAll) or
193 // the ones with a memory operand (ForceMemOperand option). The latter CMOV
194 // will risk a stall waiting for the load to complete that speculative
195 // execution behind a branch is better suited to handle on modern x86 chips.
196 if (ForceMemOperand || ForceAll) {
197 CmovGroups AllCmovGroups;
198 SmallVector<MachineBasicBlock *, 4> Blocks(llvm::make_pointer_range(Range&: MF));
199 if (collectCmovCandidates(Blocks, CmovInstGroups&: AllCmovGroups, /*IncludeLoads*/ true)) {
200 for (auto &Group : AllCmovGroups) {
201 // Skip any group that doesn't do at least one memory operand cmov.
202 if (ForceMemOperand && !ForceAll &&
203 llvm::none_of(Range&: Group, P: [&](MachineInstr *I) { return I->mayLoad(); }))
204 continue;
205
206 // For CMOV groups which we can rewrite and which contain a memory load,
207 // always rewrite them. On x86, a CMOV will dramatically amplify any
208 // memory latency by blocking speculative execution.
209 Changed = true;
210 convertCmovInstsToBranches(Group);
211 }
212 }
213 // Early return as ForceAll converts all CmovGroups.
214 if (ForceAll)
215 return Changed;
216 }
217
218 //===--------------------------------------------------------------------===//
219 // Register-operand Conversion Algorithm
220 // ---------
221 // For each innermost loop
222 // collectCmovCandidates() {
223 // Find all CMOV-group-candidates.
224 // }
225 //
226 // checkForProfitableCmovCandidates() {
227 // * Calculate both loop-depth and optimized-loop-depth.
228 // * Use these depth to check for loop transformation profitability.
229 // * Check for CMOV-group-candidate transformation profitability.
230 // }
231 //
232 // For each profitable CMOV-group-candidate
233 // convertCmovInstsToBranches() {
234 // * Create FalseBB, SinkBB, Conditional branch to SinkBB.
235 // * Replace each CMOV instruction with a PHI instruction in SinkBB.
236 // }
237 //
238 // Note: For more details, see each function description.
239 //===--------------------------------------------------------------------===//
240
241 // Build up the loops in pre-order.
242 SmallVector<MachineLoop *, 4> Loops(MLI->begin(), MLI->end());
243 // Note that we need to check size on each iteration as we accumulate child
244 // loops.
245 for (int i = 0; i < (int)Loops.size(); ++i)
246 llvm::append_range(C&: Loops, R: Loops[i]->getSubLoops());
247
248 for (MachineLoop *CurrLoop : Loops) {
249 // Optimize only innermost loops.
250 if (!CurrLoop->getSubLoops().empty())
251 continue;
252
253 // List of consecutive CMOV instructions to be processed.
254 CmovGroups CmovInstGroups;
255
256 if (!collectCmovCandidates(Blocks: CurrLoop->getBlocks(), CmovInstGroups))
257 continue;
258
259 if (!checkForProfitableCmovCandidates(Blocks: CurrLoop->getBlocks(),
260 CmovInstGroups))
261 continue;
262
263 Changed = true;
264 for (auto &Group : CmovInstGroups)
265 convertCmovInstsToBranches(Group);
266 }
267
268 return Changed;
269}
270
271bool X86CmovConversionImpl::collectCmovCandidates(
272 ArrayRef<MachineBasicBlock *> Blocks, CmovGroups &CmovInstGroups,
273 bool IncludeLoads) {
274 //===--------------------------------------------------------------------===//
275 // Collect all CMOV-group-candidates and add them into CmovInstGroups.
276 //
277 // CMOV-group:
278 // CMOV instructions, in same MBB, that uses same EFLAGS def instruction.
279 //
280 // CMOV-group-candidate:
281 // CMOV-group where all the CMOV instructions are
282 // 1. consecutive.
283 // 2. have same condition code or opposite one.
284 // 3. have only operand registers (X86::CMOVrr).
285 //===--------------------------------------------------------------------===//
286 // List of possible improvement (TODO's):
287 // --------------------------------------
288 // TODO: Add support for X86::CMOVrm instructions.
289 // TODO: Add support for X86::SETcc instructions.
290 // TODO: Add support for CMOV-groups with non consecutive CMOV instructions.
291 //===--------------------------------------------------------------------===//
292
293 // Current processed CMOV-Group.
294 CmovGroup Group;
295 for (auto *MBB : Blocks) {
296 Group.clear();
297 // Condition code of first CMOV instruction current processed range and its
298 // opposite condition code.
299 X86::CondCode FirstCC = X86::COND_INVALID, FirstOppCC = X86::COND_INVALID,
300 MemOpCC = X86::COND_INVALID;
301 // Indicator of a non CMOVrr instruction in the current processed range.
302 bool FoundNonCMOVInst = false;
303 // Indicator for current processed CMOV-group if it should be skipped.
304 bool SkipGroup = false;
305
306 for (auto &I : *MBB) {
307 // Skip debug instructions.
308 if (I.isDebugInstr())
309 continue;
310
311 X86::CondCode CC = X86::getCondFromCMov(MI: I);
312 // Check if we found a X86::CMOVrr instruction. If it is marked as
313 // unpredictable, skip it and do not convert it to branch.
314 if (CC != X86::COND_INVALID &&
315 !I.getFlag(Flag: MachineInstr::MIFlag::Unpredictable) &&
316 (IncludeLoads || !I.mayLoad())) {
317 if (Group.empty()) {
318 // We found first CMOV in the range, reset flags.
319 FirstCC = CC;
320 FirstOppCC = X86::GetOppositeBranchCondition(CC);
321 // Clear out the prior group's memory operand CC.
322 MemOpCC = X86::COND_INVALID;
323 FoundNonCMOVInst = false;
324 SkipGroup = false;
325 }
326 Group.push_back(Elt: &I);
327 // Check if it is a non-consecutive CMOV instruction or it has different
328 // condition code than FirstCC or FirstOppCC.
329 if (FoundNonCMOVInst || (CC != FirstCC && CC != FirstOppCC))
330 // Mark the SKipGroup indicator to skip current processed CMOV-Group.
331 SkipGroup = true;
332 if (I.mayLoad()) {
333 if (MemOpCC == X86::COND_INVALID)
334 // The first memory operand CMOV.
335 MemOpCC = CC;
336 else if (CC != MemOpCC)
337 // Can't handle mixed conditions with memory operands.
338 SkipGroup = true;
339 }
340 // Check if we were relying on zero-extending behavior of the CMOV.
341 if (!SkipGroup &&
342 llvm::any_of(
343 Range: MRI->use_nodbg_instructions(Reg: I.defs().begin()->getReg()),
344 P: [&](MachineInstr &UseI) {
345 return UseI.getOpcode() == X86::SUBREG_TO_REG;
346 }))
347 // FIXME: We should model the cost of using an explicit MOV to handle
348 // the zero-extension rather than just refusing to handle this.
349 SkipGroup = true;
350 continue;
351 }
352 // If Group is empty, keep looking for first CMOV in the range.
353 if (Group.empty())
354 continue;
355
356 // We found a non X86::CMOVrr instruction.
357 FoundNonCMOVInst = true;
358 // Check if this instruction define EFLAGS, to determine end of processed
359 // range, as there would be no more instructions using current EFLAGS def.
360 if (I.definesRegister(Reg: X86::EFLAGS, /*TRI=*/nullptr)) {
361 // Check if current processed CMOV-group should not be skipped and add
362 // it as a CMOV-group-candidate.
363 if (!SkipGroup)
364 CmovInstGroups.push_back(Elt: Group);
365 else
366 ++NumOfSkippedCmovGroups;
367 Group.clear();
368 }
369 }
370 // End of basic block is considered end of range, check if current processed
371 // CMOV-group should not be skipped and add it as a CMOV-group-candidate.
372 if (Group.empty())
373 continue;
374 if (!SkipGroup)
375 CmovInstGroups.push_back(Elt: Group);
376 else
377 ++NumOfSkippedCmovGroups;
378 }
379
380 NumOfCmovGroupCandidate += CmovInstGroups.size();
381 return !CmovInstGroups.empty();
382}
383
384/// \returns Depth of CMOV instruction as if it was converted into branch.
385/// \param TrueOpDepth depth cost of CMOV true value operand.
386/// \param FalseOpDepth depth cost of CMOV false value operand.
387static unsigned getDepthOfOptCmov(unsigned TrueOpDepth, unsigned FalseOpDepth) {
388 // The depth of the result after branch conversion is
389 // TrueOpDepth * TrueOpProbability + FalseOpDepth * FalseOpProbability.
390 // As we have no info about branch weight, we assume 75% for one and 25% for
391 // the other, and pick the result with the largest resulting depth.
392 return std::max(
393 a: divideCeil(Numerator: TrueOpDepth * 3 + FalseOpDepth, Denominator: 4),
394 b: divideCeil(Numerator: FalseOpDepth * 3 + TrueOpDepth, Denominator: 4));
395}
396
397bool X86CmovConversionImpl::checkForProfitableCmovCandidates(
398 ArrayRef<MachineBasicBlock *> Blocks, CmovGroups &CmovInstGroups) {
399 struct DepthInfo {
400 /// Depth of original loop.
401 unsigned Depth;
402 /// Depth of optimized loop.
403 unsigned OptDepth;
404 };
405 /// Number of loop iterations to calculate depth for ?!
406 static const unsigned LoopIterations = 2;
407 DenseMap<MachineInstr *, DepthInfo> DepthMap;
408 DepthInfo LoopDepth[LoopIterations] = {{.Depth: 0, .OptDepth: 0}, {.Depth: 0, .OptDepth: 0}};
409 enum { PhyRegType = 0, VirRegType = 1, RegTypeNum = 2 };
410 /// For each register type maps the register to its last def instruction.
411 DenseMap<Register, MachineInstr *> RegDefMaps[RegTypeNum];
412 /// Maps register operand to its def instruction, which can be nullptr if it
413 /// is unknown (e.g., operand is defined outside the loop).
414 DenseMap<MachineOperand *, MachineInstr *> OperandToDefMap;
415
416 // Set depth of unknown instruction (i.e., nullptr) to zero.
417 DepthMap[nullptr] = {.Depth: 0, .OptDepth: 0};
418
419 SmallPtrSet<MachineInstr *, 4> CmovInstructions;
420 for (auto &Group : CmovInstGroups)
421 CmovInstructions.insert_range(R&: Group);
422
423 //===--------------------------------------------------------------------===//
424 // Step 1: Calculate instruction depth and loop depth.
425 // Optimized-Loop:
426 // loop with CMOV-group-candidates converted into branches.
427 //
428 // Instruction-Depth:
429 // instruction latency + max operand depth.
430 // * For CMOV instruction in optimized loop the depth is calculated as:
431 // CMOV latency + getDepthOfOptCmov(True-Op-Depth, False-Op-depth)
432 // TODO: Find a better way to estimate the latency of the branch instruction
433 // rather than using the CMOV latency.
434 //
435 // Loop-Depth:
436 // max instruction depth of all instructions in the loop.
437 // Note: instruction with max depth represents the critical-path in the loop.
438 //
439 // Loop-Depth[i]:
440 // Loop-Depth calculated for first `i` iterations.
441 // Note: it is enough to calculate depth for up to two iterations.
442 //
443 // Depth-Diff[i]:
444 // Number of cycles saved in first 'i` iterations by optimizing the loop.
445 //===--------------------------------------------------------------------===//
446 for (DepthInfo &MaxDepth : LoopDepth) {
447 for (auto *MBB : Blocks) {
448 // Clear physical registers Def map.
449 RegDefMaps[PhyRegType].clear();
450 for (MachineInstr &MI : *MBB) {
451 // Skip debug instructions.
452 if (MI.isDebugInstr())
453 continue;
454 unsigned MIDepth = 0;
455 unsigned MIDepthOpt = 0;
456 bool IsCMOV = CmovInstructions.count(Ptr: &MI);
457 for (auto &MO : MI.uses()) {
458 // Checks for "isUse()" as "uses()" returns also implicit definitions.
459 if (!MO.isReg() || !MO.isUse())
460 continue;
461 Register Reg = MO.getReg();
462 auto &RDM = RegDefMaps[Reg.isVirtual()];
463 if (MachineInstr *DefMI = RDM.lookup(Val: Reg)) {
464 OperandToDefMap[&MO] = DefMI;
465 DepthInfo Info = DepthMap.lookup(Val: DefMI);
466 MIDepth = std::max(a: MIDepth, b: Info.Depth);
467 if (!IsCMOV)
468 MIDepthOpt = std::max(a: MIDepthOpt, b: Info.OptDepth);
469 }
470 }
471
472 if (IsCMOV)
473 MIDepthOpt = getDepthOfOptCmov(
474 TrueOpDepth: DepthMap[OperandToDefMap.lookup(Val: &MI.getOperand(i: 1))].OptDepth,
475 FalseOpDepth: DepthMap[OperandToDefMap.lookup(Val: &MI.getOperand(i: 2))].OptDepth);
476
477 // Iterates over all operands to handle implicit definitions as well.
478 for (auto &MO : MI.operands()) {
479 if (!MO.isReg() || !MO.isDef())
480 continue;
481 Register Reg = MO.getReg();
482 RegDefMaps[Reg.isVirtual()][Reg] = &MI;
483 }
484
485 unsigned Latency = TSchedModel.computeInstrLatency(MI: &MI);
486 DepthMap[&MI] = {.Depth: MIDepth += Latency, .OptDepth: MIDepthOpt += Latency};
487 MaxDepth.Depth = std::max(a: MaxDepth.Depth, b: MIDepth);
488 MaxDepth.OptDepth = std::max(a: MaxDepth.OptDepth, b: MIDepthOpt);
489 }
490 }
491 }
492
493 unsigned Diff[LoopIterations] = {LoopDepth[0].Depth - LoopDepth[0].OptDepth,
494 LoopDepth[1].Depth - LoopDepth[1].OptDepth};
495
496 //===--------------------------------------------------------------------===//
497 // Step 2: Check if Loop worth to be optimized.
498 // Worth-Optimize-Loop:
499 // case 1: Diff[1] == Diff[0]
500 // Critical-path is iteration independent - there is no dependency
501 // of critical-path instructions on critical-path instructions of
502 // previous iteration.
503 // Thus, it is enough to check gain percent of 1st iteration -
504 // To be conservative, the optimized loop need to have a depth of
505 // 12.5% cycles less than original loop, per iteration.
506 //
507 // case 2: Diff[1] > Diff[0]
508 // Critical-path is iteration dependent - there is dependency of
509 // critical-path instructions on critical-path instructions of
510 // previous iteration.
511 // Thus, check the gain percent of the 2nd iteration (similar to the
512 // previous case), but it is also required to check the gradient of
513 // the gain - the change in Depth-Diff compared to the change in
514 // Loop-Depth between 1st and 2nd iterations.
515 // To be conservative, the gradient need to be at least 50%.
516 //
517 // In addition, In order not to optimize loops with very small gain, the
518 // gain (in cycles) after 2nd iteration should not be less than a given
519 // threshold. Thus, the check (Diff[1] >= GainCycleThreshold) must apply.
520 //
521 // If loop is not worth optimizing, remove all CMOV-group-candidates.
522 //===--------------------------------------------------------------------===//
523 if (Diff[1] < GainCycleThreshold)
524 return false;
525
526 bool WorthOptLoop = false;
527 if (Diff[1] == Diff[0])
528 WorthOptLoop = Diff[0] * 8 >= LoopDepth[0].Depth;
529 else if (Diff[1] > Diff[0])
530 WorthOptLoop =
531 (Diff[1] - Diff[0]) * 2 >= (LoopDepth[1].Depth - LoopDepth[0].Depth) &&
532 (Diff[1] * 8 >= LoopDepth[1].Depth);
533
534 if (!WorthOptLoop)
535 return false;
536
537 ++NumOfLoopCandidate;
538
539 //===--------------------------------------------------------------------===//
540 // Step 3: Check for each CMOV-group-candidate if it worth to be optimized.
541 // Worth-Optimize-Group:
542 // Iff it is worth to optimize all CMOV instructions in the group.
543 //
544 // Worth-Optimize-CMOV:
545 // Predicted branch is faster than CMOV by the difference between depth of
546 // condition operand and depth of taken (predicted) value operand.
547 // To be conservative, the gain of such CMOV transformation should cover at
548 // at least 25% of branch-misprediction-penalty.
549 //===--------------------------------------------------------------------===//
550 unsigned MispredictPenalty = STI->getMispredictionPenalty();
551 CmovGroups TempGroups;
552 std::swap(LHS&: TempGroups, RHS&: CmovInstGroups);
553 for (auto &Group : TempGroups) {
554 bool WorthOpGroup = true;
555 for (auto *MI : Group) {
556 // Avoid CMOV instruction which value is used as a pointer to load from.
557 // This is another conservative check to avoid converting CMOV instruction
558 // used with tree-search like algorithm, where the branch is unpredicted.
559 auto UIs = MRI->use_instructions(Reg: MI->defs().begin()->getReg());
560 if (hasSingleElement(C&: UIs)) {
561 unsigned Op = UIs.begin()->getOpcode();
562 if (Op == X86::MOV64rm || Op == X86::MOV32rm) {
563 WorthOpGroup = false;
564 break;
565 }
566 }
567
568 unsigned CondCost =
569 DepthMap[OperandToDefMap.lookup(Val: &MI->getOperand(i: 4))].Depth;
570 unsigned ValCost = getDepthOfOptCmov(
571 TrueOpDepth: DepthMap[OperandToDefMap.lookup(Val: &MI->getOperand(i: 1))].Depth,
572 FalseOpDepth: DepthMap[OperandToDefMap.lookup(Val: &MI->getOperand(i: 2))].Depth);
573 if (ValCost > CondCost || (CondCost - ValCost) * 4 < MispredictPenalty) {
574 WorthOpGroup = false;
575 break;
576 }
577 }
578
579 if (WorthOpGroup)
580 CmovInstGroups.push_back(Elt: Group);
581 }
582
583 return !CmovInstGroups.empty();
584}
585
586static bool checkEFLAGSLive(MachineInstr *MI) {
587 if (MI->killsRegister(Reg: X86::EFLAGS, /*TRI=*/nullptr))
588 return false;
589
590 // The EFLAGS operand of MI might be missing a kill marker.
591 // Figure out whether EFLAGS operand should LIVE after MI instruction.
592 MachineBasicBlock *BB = MI->getParent();
593 MachineBasicBlock::iterator ItrMI = MI;
594
595 // Scan forward through BB for a use/def of EFLAGS.
596 for (auto I = std::next(x: ItrMI), E = BB->end(); I != E; ++I) {
597 if (I->readsRegister(Reg: X86::EFLAGS, /*TRI=*/nullptr))
598 return true;
599 if (I->definesRegister(Reg: X86::EFLAGS, /*TRI=*/nullptr))
600 return false;
601 }
602
603 // We hit the end of the block, check whether EFLAGS is live into a successor.
604 for (MachineBasicBlock *Succ : BB->successors())
605 if (Succ->isLiveIn(Reg: X86::EFLAGS))
606 return true;
607
608 return false;
609}
610
611/// Given /p First CMOV instruction and /p Last CMOV instruction representing a
612/// group of CMOV instructions, which may contain debug instructions in between,
613/// move all debug instructions to after the last CMOV instruction, making the
614/// CMOV group consecutive.
615static void packCmovGroup(MachineInstr *First, MachineInstr *Last) {
616 assert(X86::getCondFromCMov(*Last) != X86::COND_INVALID &&
617 "Last instruction in a CMOV group must be a CMOV instruction");
618
619 SmallVector<MachineInstr *, 2> DBGInstructions;
620 for (auto I = First->getIterator(), E = Last->getIterator(); I != E; I++) {
621 if (I->isDebugInstr())
622 DBGInstructions.push_back(Elt: &*I);
623 }
624
625 // Splice the debug instruction after the cmov group.
626 MachineBasicBlock *MBB = First->getParent();
627 for (auto *MI : DBGInstructions)
628 MBB->insertAfter(I: Last, MI: MI->removeFromParent());
629}
630
631void X86CmovConversionImpl::convertCmovInstsToBranches(
632 SmallVectorImpl<MachineInstr *> &Group) const {
633 assert(!Group.empty() && "No CMOV instructions to convert");
634 ++NumOfOptimizedCmovGroups;
635
636 // If the CMOV group is not packed, e.g., there are debug instructions between
637 // first CMOV and last CMOV, then pack the group and make the CMOV instruction
638 // consecutive by moving the debug instructions to after the last CMOV.
639 packCmovGroup(First: Group.front(), Last: Group.back());
640
641 // To convert a CMOVcc instruction, we actually have to insert the diamond
642 // control-flow pattern. The incoming instruction knows the destination vreg
643 // to set, the condition code register to branch on, the true/false values to
644 // select between, and a branch opcode to use.
645
646 // Before
647 // -----
648 // MBB:
649 // cond = cmp ...
650 // v1 = CMOVge t1, f1, cond
651 // v2 = CMOVlt t2, f2, cond
652 // v3 = CMOVge v1, f3, cond
653 //
654 // After
655 // -----
656 // MBB:
657 // cond = cmp ...
658 // jge %SinkMBB
659 //
660 // FalseMBB:
661 // jmp %SinkMBB
662 //
663 // SinkMBB:
664 // %v1 = phi[%f1, %FalseMBB], [%t1, %MBB]
665 // %v2 = phi[%t2, %FalseMBB], [%f2, %MBB] ; For CMOV with OppCC switch
666 // ; true-value with false-value
667 // %v3 = phi[%f3, %FalseMBB], [%t1, %MBB] ; Phi instruction cannot use
668 // ; previous Phi instruction result
669
670 MachineInstr &MI = *Group.front();
671 MachineInstr *LastCMOV = Group.back();
672 DebugLoc DL = MI.getDebugLoc();
673
674 X86::CondCode CC = X86::CondCode(X86::getCondFromCMov(MI));
675 X86::CondCode OppCC = X86::GetOppositeBranchCondition(CC);
676 // Potentially swap the condition codes so that any memory operand to a CMOV
677 // is in the *false* position instead of the *true* position. We can invert
678 // any non-memory operand CMOV instructions to cope with this and we ensure
679 // memory operand CMOVs are only included with a single condition code.
680 if (llvm::any_of(Range&: Group, P: [&](MachineInstr *I) {
681 return I->mayLoad() && X86::getCondFromCMov(MI: *I) == CC;
682 }))
683 std::swap(a&: CC, b&: OppCC);
684
685 MachineBasicBlock *MBB = MI.getParent();
686 MachineFunction::iterator It = ++MBB->getIterator();
687 MachineFunction *F = MBB->getParent();
688 const BasicBlock *BB = MBB->getBasicBlock();
689
690 MachineBasicBlock *FalseMBB = F->CreateMachineBasicBlock(BB);
691 MachineBasicBlock *SinkMBB = F->CreateMachineBasicBlock(BB);
692 F->insert(MBBI: It, MBB: FalseMBB);
693 F->insert(MBBI: It, MBB: SinkMBB);
694
695 // If the EFLAGS register isn't dead in the terminator, then claim that it's
696 // live into the sink and copy blocks.
697 if (checkEFLAGSLive(MI: LastCMOV)) {
698 FalseMBB->addLiveIn(PhysReg: X86::EFLAGS);
699 SinkMBB->addLiveIn(PhysReg: X86::EFLAGS);
700 }
701
702 // Transfer the remainder of BB and its successor edges to SinkMBB.
703 SinkMBB->splice(Where: SinkMBB->begin(), Other: MBB,
704 From: std::next(x: MachineBasicBlock::iterator(LastCMOV)), To: MBB->end());
705 SinkMBB->transferSuccessorsAndUpdatePHIs(FromMBB: MBB);
706
707 // Add the false and sink blocks as its successors.
708 MBB->addSuccessor(Succ: FalseMBB);
709 MBB->addSuccessor(Succ: SinkMBB);
710
711 // Create the conditional branch instruction.
712 BuildMI(BB: MBB, MIMD: DL, MCID: TII->get(Opcode: X86::JCC_1)).addMBB(MBB: SinkMBB).addImm(Val: CC);
713
714 // Add the sink block to the false block successors.
715 FalseMBB->addSuccessor(Succ: SinkMBB);
716
717 MachineInstrBuilder MIB;
718 MachineBasicBlock::iterator MIItBegin = MachineBasicBlock::iterator(MI);
719 MachineBasicBlock::iterator MIItEnd =
720 std::next(x: MachineBasicBlock::iterator(LastCMOV));
721 MachineBasicBlock::iterator FalseInsertionPoint = FalseMBB->begin();
722 MachineBasicBlock::iterator SinkInsertionPoint = SinkMBB->begin();
723
724 // First we need to insert an explicit load on the false path for any memory
725 // operand. We also need to potentially do register rewriting here, but it is
726 // simpler as the memory operands are always on the false path so we can
727 // simply take that input, whatever it is.
728 DenseMap<Register, Register> FalseBBRegRewriteTable;
729 for (MachineBasicBlock::iterator MIIt = MIItBegin; MIIt != MIItEnd;) {
730 auto &MI = *MIIt++;
731 // Skip any CMOVs in this group which don't load from memory.
732 if (!MI.mayLoad()) {
733 // Remember the false-side register input.
734 Register FalseReg =
735 MI.getOperand(i: X86::getCondFromCMov(MI) == CC ? 1 : 2).getReg();
736 // Walk back through any intermediate cmovs referenced.
737 while (true) {
738 auto FRIt = FalseBBRegRewriteTable.find(Val: FalseReg);
739 if (FRIt == FalseBBRegRewriteTable.end())
740 break;
741 FalseReg = FRIt->second;
742 }
743 FalseBBRegRewriteTable[MI.getOperand(i: 0).getReg()] = FalseReg;
744 continue;
745 }
746
747 // The condition must be the *opposite* of the one we've decided to branch
748 // on as the branch will go *around* the load and the load should happen
749 // when the CMOV condition is false.
750 assert(X86::getCondFromCMov(MI) == OppCC &&
751 "Can only handle memory-operand cmov instructions with a condition "
752 "opposite to the selected branch direction.");
753
754 // The goal is to rewrite the cmov from:
755 //
756 // MBB:
757 // %A = CMOVcc %B (tied), (mem)
758 //
759 // to
760 //
761 // MBB:
762 // %A = CMOVcc %B (tied), %C
763 // FalseMBB:
764 // %C = MOV (mem)
765 //
766 // Which will allow the next loop to rewrite the CMOV in terms of a PHI:
767 //
768 // MBB:
769 // JMP!cc SinkMBB
770 // FalseMBB:
771 // %C = MOV (mem)
772 // SinkMBB:
773 // %A = PHI [ %C, FalseMBB ], [ %B, MBB]
774
775 // Get a fresh register to use as the destination of the MOV.
776 const TargetRegisterClass *RC = MRI->getRegClass(Reg: MI.getOperand(i: 0).getReg());
777 Register TmpReg = MRI->createVirtualRegister(RegClass: RC);
778
779 // Retain debug instr number when unfolded.
780 unsigned OldDebugInstrNum = MI.peekDebugInstrNum();
781 SmallVector<MachineInstr *, 4> NewMIs;
782 bool Unfolded = TII->unfoldMemoryOperand(MF&: *MBB->getParent(), MI, Reg: TmpReg,
783 /*UnfoldLoad*/ true,
784 /*UnfoldStore*/ false, NewMIs);
785 (void)Unfolded;
786 assert(Unfolded && "Should never fail to unfold a loading cmov!");
787
788 // Move the new CMOV to just before the old one and reset any impacted
789 // iterator.
790 auto *NewCMOV = NewMIs.pop_back_val();
791 assert(X86::getCondFromCMov(*NewCMOV) == OppCC &&
792 "Last new instruction isn't the expected CMOV!");
793 LLVM_DEBUG(dbgs() << "\tRewritten cmov: "; NewCMOV->dump());
794 MBB->insert(I: MachineBasicBlock::iterator(MI), MI: NewCMOV);
795 if (&*MIItBegin == &MI)
796 MIItBegin = MachineBasicBlock::iterator(NewCMOV);
797
798 if (OldDebugInstrNum)
799 NewCMOV->setDebugInstrNum(OldDebugInstrNum);
800
801 // Sink whatever instructions were needed to produce the unfolded operand
802 // into the false block.
803 for (auto *NewMI : NewMIs) {
804 LLVM_DEBUG(dbgs() << "\tRewritten load instr: "; NewMI->dump());
805 FalseMBB->insert(I: FalseInsertionPoint, MI: NewMI);
806 // Re-map any operands that are from other cmovs to the inputs for this block.
807 for (auto &MOp : NewMI->uses()) {
808 if (!MOp.isReg())
809 continue;
810 auto It = FalseBBRegRewriteTable.find(Val: MOp.getReg());
811 if (It == FalseBBRegRewriteTable.end())
812 continue;
813
814 MOp.setReg(It->second);
815 // This might have been a kill when it referenced the cmov result, but
816 // it won't necessarily be once rewritten.
817 // FIXME: We could potentially improve this by tracking whether the
818 // operand to the cmov was also a kill, and then skipping the PHI node
819 // construction below.
820 MOp.setIsKill(false);
821 }
822 }
823 MBB->erase(I: &MI);
824
825 // Add this PHI to the rewrite table.
826 FalseBBRegRewriteTable[NewCMOV->getOperand(i: 0).getReg()] = TmpReg;
827 }
828
829 // As we are creating the PHIs, we have to be careful if there is more than
830 // one. Later CMOVs may reference the results of earlier CMOVs, but later
831 // PHIs have to reference the individual true/false inputs from earlier PHIs.
832 // That also means that PHI construction must work forward from earlier to
833 // later, and that the code must maintain a mapping from earlier PHI's
834 // destination registers, and the registers that went into the PHI.
835 DenseMap<Register, std::pair<Register, Register>> RegRewriteTable;
836
837 for (MachineBasicBlock::iterator MIIt = MIItBegin; MIIt != MIItEnd; ++MIIt) {
838 Register DestReg = MIIt->getOperand(i: 0).getReg();
839 Register Op1Reg = MIIt->getOperand(i: 1).getReg();
840 Register Op2Reg = MIIt->getOperand(i: 2).getReg();
841
842 // If this CMOV we are processing is the opposite condition from the jump we
843 // generated, then we have to swap the operands for the PHI that is going to
844 // be generated.
845 if (X86::getCondFromCMov(MI: *MIIt) == OppCC)
846 std::swap(a&: Op1Reg, b&: Op2Reg);
847
848 auto Op1Itr = RegRewriteTable.find(Val: Op1Reg);
849 if (Op1Itr != RegRewriteTable.end())
850 Op1Reg = Op1Itr->second.first;
851
852 auto Op2Itr = RegRewriteTable.find(Val: Op2Reg);
853 if (Op2Itr != RegRewriteTable.end())
854 Op2Reg = Op2Itr->second.second;
855
856 // SinkMBB:
857 // %Result = phi [ %FalseValue, FalseMBB ], [ %TrueValue, MBB ]
858 // ...
859 MIB = BuildMI(BB&: *SinkMBB, I: SinkInsertionPoint, MIMD: DL, MCID: TII->get(Opcode: X86::PHI), DestReg)
860 .addReg(RegNo: Op1Reg)
861 .addMBB(MBB: FalseMBB)
862 .addReg(RegNo: Op2Reg)
863 .addMBB(MBB);
864 (void)MIB;
865 LLVM_DEBUG(dbgs() << "\tFrom: "; MIIt->dump());
866 LLVM_DEBUG(dbgs() << "\tTo: "; MIB->dump());
867
868 // debug-info: we can just copy the instr-ref number from one instruction
869 // to the other, seeing how it's a one-for-one substitution.
870 if (unsigned InstrNum = MIIt->peekDebugInstrNum())
871 MIB->setDebugInstrNum(InstrNum);
872
873 // Add this PHI to the rewrite table.
874 RegRewriteTable[DestReg] = std::make_pair(x&: Op1Reg, y&: Op2Reg);
875 }
876
877 // Reset the NoPHIs property if a PHI was inserted to prevent a conflict with
878 // the MachineVerifier during testing.
879 if (MIItBegin != MIItEnd)
880 F->getProperties().resetNoPHIs();
881
882 // Now remove the CMOV(s).
883 MBB->erase(I: MIItBegin, E: MIItEnd);
884
885 // Add new basic blocks to MachineLoopInfo.
886 if (MachineLoop *L = MLI->getLoopFor(BB: MBB)) {
887 L->addBasicBlockToLoop(NewBB: FalseMBB, LI&: *MLI);
888 L->addBasicBlockToLoop(NewBB: SinkMBB, LI&: *MLI);
889 }
890}
891
892INITIALIZE_PASS_BEGIN(X86CmovConversionLegacy, DEBUG_TYPE,
893 "X86 cmov Conversion", false, false)
894INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)
895INITIALIZE_PASS_END(X86CmovConversionLegacy, DEBUG_TYPE, "X86 cmov Conversion",
896 false, false)
897
898FunctionPass *llvm::createX86CmovConversionLegacyPass() {
899 return new X86CmovConversionLegacy();
900}
901
902bool X86CmovConversionLegacy::runOnMachineFunction(MachineFunction &MF) {
903 if (skipFunction(F: MF.getFunction()))
904 return false;
905 MachineLoopInfo *MLI = &getAnalysis<MachineLoopInfoWrapperPass>().getLI();
906 X86CmovConversionImpl Impl(MLI);
907 return Impl.runOnMachineFunction(MF);
908}
909
910PreservedAnalyses
911X86CmovConversionPass::run(MachineFunction &MF,
912 MachineFunctionAnalysisManager &MFAM) {
913 MachineLoopInfo *MLI = &MFAM.getResult<MachineLoopAnalysis>(IR&: MF);
914 X86CmovConversionImpl Impl(MLI);
915 bool Changed = Impl.runOnMachineFunction(MF);
916 return Changed ? getMachineFunctionPassPreservedAnalyses()
917 : PreservedAnalyses::all();
918}
919