ControlHeightReduction.cpp | Explore in Territory

//===-- ControlHeightReduction.cpp - Control Height Reduction -------------===//
//
// 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
//
//===----------------------------------------------------------------------===//
//
// This pass merges conditional blocks of code and reduces the number of
// conditional branches in the hot paths based on profiles.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Instrumentation/ControlHeightReduction.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringSet.h"
#include "llvm/Analysis/BlockFrequencyInfo.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ProfileSummaryInfo.h"
#include "llvm/Analysis/RegionInfo.h"
#include "llvm/Analysis/RegionIterator.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/MDBuilder.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/ProfDataUtils.h"
#include "llvm/Support/BranchProbability.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/MemoryBuffer.h"
#include "llvm/Transforms/Utils.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/ValueMapper.h"

#include <optional>
#include <set>
#include <sstream>

usingnamespacellvm;

#define DEBUG_TYPE …

#define CHR_DEBUG(X) …

static cl::opt<bool> DisableCHR("disable-chr", cl::init(false), cl::Hidden,
                                cl::desc("Disable CHR for all functions"));

static cl::opt<bool> ForceCHR("force-chr", cl::init(false), cl::Hidden,
                              cl::desc("Apply CHR for all functions"));

static cl::opt<double> CHRBiasThreshold(
    "chr-bias-threshold", cl::init(0.99), cl::Hidden,
    cl::desc("CHR considers a branch bias greater than this ratio as biased"));

static cl::opt<unsigned> CHRMergeThreshold(
    "chr-merge-threshold", cl::init(2), cl::Hidden,
    cl::desc("CHR merges a group of N branches/selects where N >= this value"));

static cl::opt<std::string> CHRModuleList(
    "chr-module-list", cl::init(""), cl::Hidden,
    cl::desc("Specify file to retrieve the list of modules to apply CHR to"));

static cl::opt<std::string> CHRFunctionList(
    "chr-function-list", cl::init(""), cl::Hidden,
    cl::desc("Specify file to retrieve the list of functions to apply CHR to"));

static cl::opt<unsigned> CHRDupThreshsold(
    "chr-dup-threshold", cl::init(3), cl::Hidden,
    cl::desc("Max number of duplications by CHR for a region"));

static StringSet<> CHRModules;
static StringSet<> CHRFunctions;

static void parseCHRFilterFiles() { … }

namespace {

struct CHRStats { … };

// RegInfo - some properties of a Region.
struct RegInfo { … };

HoistStopMapTy;

// CHRScope - a sequence of regions to CHR together. It corresponds to a
// sequence of conditional blocks. It can have subscopes which correspond to
// nested conditional blocks. Nested CHRScopes form a tree.
class CHRScope { … };

class CHR { … };

} // end anonymous namespace

static inline
raw_ostream LLVM_ATTRIBUTE_UNUSED &operator<<(raw_ostream &OS,
                                              const CHRStats &Stats) { … }

static inline
raw_ostream &operator<<(raw_ostream &OS, const CHRScope &Scope) { … }

static bool shouldApply(Function &F, ProfileSummaryInfo &PSI) { … }

static void LLVM_ATTRIBUTE_UNUSED dumpIR(Function &F, const char *Label,
                                         CHRStats *Stats) { … }

void CHRScope::print(raw_ostream &OS) const { … }

// Return true if the given instruction type can be hoisted by CHR.
static bool isHoistableInstructionType(Instruction *I) { … }

// Return true if the given instruction can be hoisted by CHR.
static bool isHoistable(Instruction *I, DominatorTree &DT) { … }

// Recursively traverse the use-def chains of the given value and return a set
// of the unhoistable base values defined within the scope (excluding the
// first-region entry block) or the (hoistable or unhoistable) base values that
// are defined outside (including the first-region entry block) of the
// scope. The returned set doesn't include constants.
static const std::set<Value *> &
getBaseValues(Value *V, DominatorTree &DT,
              DenseMap<Value *, std::set<Value *>> &Visited) { … }

// Return true if V is already hoisted or can be hoisted (along with its
// operands) above the insert point. When it returns true and HoistStops is
// non-null, the instructions to stop hoisting at through the use-def chains are
// inserted into HoistStops.
static bool
checkHoistValue(Value *V, Instruction *InsertPoint, DominatorTree &DT,
                DenseSet<Instruction *> &Unhoistables,
                DenseSet<Instruction *> *HoistStops,
                DenseMap<Instruction *, bool> &Visited) { … }

// Constructs the true and false branch probabilities if the the instruction has
// valid branch weights. Returns true when this was successful, false otherwise.
static bool extractBranchProbabilities(Instruction *I,
                                       BranchProbability &TrueProb,
                                       BranchProbability &FalseProb) { … }

static BranchProbability getCHRBiasThreshold() { … }

// A helper for CheckBiasedBranch and CheckBiasedSelect. If TrueProb >=
// CHRBiasThreshold, put Key into TrueSet and return true. If FalseProb >=
// CHRBiasThreshold, put Key into FalseSet and return true. Otherwise, return
// false.
template <typename K, typename S, typename M>
static bool checkBias(K *Key, BranchProbability TrueProb,
                      BranchProbability FalseProb, S &TrueSet, S &FalseSet,
                      M &BiasMap) { … }

// Returns true and insert a region into the right biased set and the map if the
// branch of the region is biased.
static bool checkBiasedBranch(BranchInst *BI, Region *R,
                              DenseSet<Region *> &TrueBiasedRegionsGlobal,
                              DenseSet<Region *> &FalseBiasedRegionsGlobal,
                              DenseMap<Region *, BranchProbability> &BranchBiasMap) { … }

// Returns true and insert a select into the right biased set and the map if the
// select is biased.
static bool checkBiasedSelect(
    SelectInst *SI, Region *R,
    DenseSet<SelectInst *> &TrueBiasedSelectsGlobal,
    DenseSet<SelectInst *> &FalseBiasedSelectsGlobal,
    DenseMap<SelectInst *, BranchProbability> &SelectBiasMap) { … }

// Returns the instruction at which to hoist the dependent condition values and
// insert the CHR branch for a region. This is the terminator branch in the
// entry block or the first select in the entry block, if any.
static Instruction* getBranchInsertPoint(RegInfo &RI) { … }

// Find a CHR scope in the given region.
CHRScope * CHR::findScope(Region *R) { … }

// Check that any of the branch and the selects in the region could be
// hoisted above the the CHR branch insert point (the most dominating of
// them, either the branch (at the end of the first block) or the first
// select in the first block). If the branch can't be hoisted, drop the
// selects in the first blocks.
//
// For example, for the following scope/region with selects, we want to insert
// the merged branch right before the first select in the first/entry block by
// hoisting c1, c2, c3, and c4.
//
// // Branch insert point here.
// a = c1 ? b : c; // Select 1
// d = c2 ? e : f; // Select 2
// if (c3) { // Branch
//   ...
//   c4 = foo() // A call.
//   g = c4 ? h : i; // Select 3
// }
//
// But suppose we can't hoist c4 because it's dependent on the preceding
// call. Then, we drop Select 3. Furthermore, if we can't hoist c2, we also drop
// Select 2. If we can't hoist c3, we drop Selects 1 & 2.
void CHR::checkScopeHoistable(CHRScope *Scope) { … }

// Traverse the region tree, find all nested scopes and merge them if possible.
CHRScope * CHR::findScopes(Region *R, Region *NextRegion, Region *ParentRegion,
                           SmallVectorImpl<CHRScope *> &Scopes) { … }

static DenseSet<Value *> getCHRConditionValuesForRegion(RegInfo &RI) { … }


// Determine whether to split a scope depending on the sets of the branch
// condition values of the previous region and the current region. We split
// (return true) it if 1) the condition values of the inner/lower scope can't be
// hoisted up to the outer/upper scope, or 2) the two sets of the condition
// values have an empty intersection (because the combined branch conditions
// won't probably lead to a simpler combined condition).
static bool shouldSplit(Instruction *InsertPoint,
                        DenseSet<Value *> &PrevConditionValues,
                        DenseSet<Value *> &ConditionValues,
                        DominatorTree &DT,
                        DenseSet<Instruction *> &Unhoistables) { … }

static void getSelectsInScope(CHRScope *Scope,
                              DenseSet<Instruction *> &Output) { … }

void CHR::splitScopes(SmallVectorImpl<CHRScope *> &Input,
                      SmallVectorImpl<CHRScope *> &Output) { … }

SmallVector<CHRScope *, 8> CHR::splitScope(
    CHRScope *Scope,
    CHRScope *Outer,
    DenseSet<Value *> *OuterConditionValues,
    Instruction *OuterInsertPoint,
    SmallVectorImpl<CHRScope *> &Output,
    DenseSet<Instruction *> &Unhoistables) { … }

void CHR::classifyBiasedScopes(SmallVectorImpl<CHRScope *> &Scopes) { … }

void CHR::classifyBiasedScopes(CHRScope *Scope, CHRScope *OutermostScope) { … }

static bool hasAtLeastTwoBiasedBranches(CHRScope *Scope) { … }

void CHR::filterScopes(SmallVectorImpl<CHRScope *> &Input,
                       SmallVectorImpl<CHRScope *> &Output) { … }

void CHR::setCHRRegions(SmallVectorImpl<CHRScope *> &Input,
                        SmallVectorImpl<CHRScope *> &Output) { … }

void CHR::setCHRRegions(CHRScope *Scope, CHRScope *OutermostScope) { … }

static bool CHRScopeSorter(CHRScope *Scope1, CHRScope *Scope2) { … }

void CHR::sortScopes(SmallVectorImpl<CHRScope *> &Input,
                     SmallVectorImpl<CHRScope *> &Output) { … }

// Return true if V is already hoisted or was hoisted (along with its operands)
// to the insert point.
static void hoistValue(Value *V, Instruction *HoistPoint, Region *R,
                       HoistStopMapTy &HoistStopMap,
                       DenseSet<Instruction *> &HoistedSet,
                       DenseSet<PHINode *> &TrivialPHIs,
                       DominatorTree &DT) { … }

// Hoist the dependent condition values of the branches and the selects in the
// scope to the insert point.
static void hoistScopeConditions(CHRScope *Scope, Instruction *HoistPoint,
                                 DenseSet<PHINode *> &TrivialPHIs,
                                 DominatorTree &DT) { … }

// Negate the predicate if an ICmp if it's used only by branches or selects by
// swapping the operands of the branches or the selects. Returns true if success.
static bool negateICmpIfUsedByBranchOrSelectOnly(ICmpInst *ICmp,
                                                 Instruction *ExcludedUser,
                                                 CHRScope *Scope) { … }

// A helper for transformScopes. Insert a trivial phi at the scope exit block
// for a value that's defined in the scope but used outside it (meaning it's
// alive at the exit block).
static void insertTrivialPHIs(CHRScope *Scope,
                              BasicBlock *EntryBlock, BasicBlock *ExitBlock,
                              DenseSet<PHINode *> &TrivialPHIs) { … }

// Assert that all the CHR regions of the scope have a biased branch or select.
static void LLVM_ATTRIBUTE_UNUSED
assertCHRRegionsHaveBiasedBranchOrSelect(CHRScope *Scope) { … }

// Assert that all the condition values of the biased branches and selects have
// been hoisted to the pre-entry block or outside of the scope.
static void LLVM_ATTRIBUTE_UNUSED assertBranchOrSelectConditionHoisted(
    CHRScope *Scope, BasicBlock *PreEntryBlock) { … }

void CHR::transformScopes(CHRScope *Scope, DenseSet<PHINode *> &TrivialPHIs) { … }

// A helper for transformScopes. Clone the blocks in the scope (excluding the
// PreEntryBlock) to split into a hot path and a cold path and update the PHIs
// at the exit block.
void CHR::cloneScopeBlocks(CHRScope *Scope,
                           BasicBlock *PreEntryBlock,
                           BasicBlock *ExitBlock,
                           Region *LastRegion,
                           ValueToValueMapTy &VMap) { … }

// A helper for transformScope. Replace the old (placeholder) branch with the
// new (merged) conditional branch.
BranchInst *CHR::createMergedBranch(BasicBlock *PreEntryBlock,
                                    BasicBlock *EntryBlock,
                                    BasicBlock *NewEntryBlock,
                                    ValueToValueMapTy &VMap) { … }

// A helper for transformScopes. Create the combined branch condition and
// constant-fold the branches/selects in the hot path.
void CHR::fixupBranchesAndSelects(CHRScope *Scope,
                                  BasicBlock *PreEntryBlock,
                                  BranchInst *MergedBR,
                                  uint64_t ProfileCount) { … }

// A helper for fixupBranchesAndSelects. Add to the combined branch condition
// and constant-fold a branch in the hot path.
void CHR::fixupBranch(Region *R, CHRScope *Scope,
                      IRBuilder<> &IRB,
                      Value *&MergedCondition,
                      BranchProbability &CHRBranchBias) { … }

// A helper for fixupBranchesAndSelects. Add to the combined branch condition
// and constant-fold a select in the hot path.
void CHR::fixupSelect(SelectInst *SI, CHRScope *Scope,
                      IRBuilder<> &IRB,
                      Value *&MergedCondition,
                      BranchProbability &CHRBranchBias) { … }

// A helper for fixupBranch/fixupSelect. Add a branch condition to the merged
// condition.
void CHR::addToMergedCondition(bool IsTrueBiased, Value *Cond,
                               Instruction *BranchOrSelect, CHRScope *Scope,
                               IRBuilder<> &IRB, Value *&MergedCondition) { … }

void CHR::transformScopes(SmallVectorImpl<CHRScope *> &CHRScopes) { … }

static void LLVM_ATTRIBUTE_UNUSED
dumpScopes(SmallVectorImpl<CHRScope *> &Scopes, const char *Label) { … }

bool CHR::run() { … }

namespace llvm {

ControlHeightReductionPass::ControlHeightReductionPass() { … }

PreservedAnalyses ControlHeightReductionPass::run(
    Function &F,
    FunctionAnalysisManager &FAM) { … }

} // namespace llvm
llvm/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp
