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