X86CmovConversion.cpp | Explore in Territory

//====- X86CmovConversion.cpp - Convert Cmov to Branch --------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
/// \file
/// This file implements a pass that converts X86 cmov instructions into
/// branches when profitable. This pass is conservative. It transforms if and
/// only if it can guarantee a gain with high confidence.
///
/// Thus, the optimization applies under the following conditions:
///   1. Consider as candidates only CMOVs in innermost loops (assume that
///      most hotspots are represented by these loops).
///   2. Given a group of CMOV instructions that are using the same EFLAGS def
///      instruction:
///      a. Consider them as candidates only if all have the same code condition
///         or the opposite one to prevent generating more than one conditional
///         jump per EFLAGS def instruction.
///      b. Consider them as candidates only if all are profitable to be
///         converted (assume that one bad conversion may cause a degradation).
///   3. Apply conversion only for loops that are found profitable and only for
///      CMOV candidates that were found profitable.
///      a. A loop is considered profitable only if conversion will reduce its
///         depth cost by some threshold.
///      b. CMOV is considered profitable if the cost of its condition is higher
///         than the average cost of its true-value and false-value by 25% of
///         branch-misprediction-penalty. This assures no degradation even with
///         25% branch misprediction.
///
/// Note: This pass is assumed to run on SSA machine code.
//
//===----------------------------------------------------------------------===//
//
//  External interfaces:
//      FunctionPass *llvm::createX86CmovConverterPass();
//      bool X86CmovConverterPass::runOnMachineFunction(MachineFunction &MF);
//
//===----------------------------------------------------------------------===//

#include "X86.h"
#include "X86InstrInfo.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSchedule.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/InitializePasses.h"
#include "llvm/MC/MCSchedule.h"
#include "llvm/Pass.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/CGPassBuilderOption.h"
#include <algorithm>
#include <cassert>
#include <iterator>
#include <utility>

usingnamespacellvm;

#define DEBUG_TYPE …

STATISTIC(NumOfSkippedCmovGroups, "Number of unsupported CMOV-groups");
STATISTIC(NumOfCmovGroupCandidate, "Number of CMOV-group candidates");
STATISTIC(NumOfLoopCandidate, "Number of CMOV-conversion profitable loops");
STATISTIC(NumOfOptimizedCmovGroups, "Number of optimized CMOV-groups");

// This internal switch can be used to turn off the cmov/branch optimization.
static cl::opt<bool>
    EnableCmovConverter("x86-cmov-converter",
                        cl::desc("Enable the X86 cmov-to-branch optimization."),
                        cl::init(true), cl::Hidden);

static cl::opt<unsigned>
    GainCycleThreshold("x86-cmov-converter-threshold",
                       cl::desc("Minimum gain per loop (in cycles) threshold."),
                       cl::init(4), cl::Hidden);

static cl::opt<bool> ForceMemOperand(
    "x86-cmov-converter-force-mem-operand",
    cl::desc("Convert cmovs to branches whenever they have memory operands."),
    cl::init(true), cl::Hidden);

static cl::opt<bool> ForceAll(
    "x86-cmov-converter-force-all",
    cl::desc("Convert all cmovs to branches."),
    cl::init(false), cl::Hidden);

namespace {

/// Converts X86 cmov instructions into branches when profitable.
class X86CmovConverterPass : public MachineFunctionPass { … };

} // end anonymous namespace

char X86CmovConverterPass::ID = …;

void X86CmovConverterPass::getAnalysisUsage(AnalysisUsage &AU) const { … }

bool X86CmovConverterPass::runOnMachineFunction(MachineFunction &MF) { … }

bool X86CmovConverterPass::collectCmovCandidates(
    ArrayRef<MachineBasicBlock *> Blocks, CmovGroups &CmovInstGroups,
    bool IncludeLoads) { … }

/// \returns Depth of CMOV instruction as if it was converted into branch.
/// \param TrueOpDepth depth cost of CMOV true value operand.
/// \param FalseOpDepth depth cost of CMOV false value operand.
static unsigned getDepthOfOptCmov(unsigned TrueOpDepth, unsigned FalseOpDepth) { … }

bool X86CmovConverterPass::checkForProfitableCmovCandidates(
    ArrayRef<MachineBasicBlock *> Blocks, CmovGroups &CmovInstGroups) { … }

static bool checkEFLAGSLive(MachineInstr *MI) { … }

/// Given /p First CMOV instruction and /p Last CMOV instruction representing a
/// group of CMOV instructions, which may contain debug instructions in between,
/// move all debug instructions to after the last CMOV instruction, making the
/// CMOV group consecutive.
static void packCmovGroup(MachineInstr *First, MachineInstr *Last) { … }

void X86CmovConverterPass::convertCmovInstsToBranches(
    SmallVectorImpl<MachineInstr *> &Group) const { … }

INITIALIZE_PASS_BEGIN(X86CmovConverterPass, DEBUG_TYPE, "X86 cmov Conversion",
                      false, false)
INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)
INITIALIZE_PASS_END(X86CmovConverterPass, DEBUG_TYPE, "X86 cmov Conversion",
                    false, false)

FunctionPass *llvm::createX86CmovConverterPass() { … }
llvm/llvm/lib/Target/X86/X86CmovConversion.cpp
