JumpTableToSwitch.cpp Source File (original) (raw)

25#include

27using namespace llvm;

31 cl::desc("Only split jump tables with size less or "

32 "equal than JumpTableSizeThreshold."),

39 "jump-table-to-switch-function-size-threshold", cl::Hidden,

40 cl::desc("Only split jump tables containing functions whose sizes are less "

41 "or equal than this threshold."),

44namespace llvm {

46}

48#define DEBUG_TYPE "jump-table-to-switch"

50namespace {

51struct JumpTableTy {

54};

55}

60 if (!Ptr)

61 return std::nullopt;

65 return std::nullopt;

70 DL.getIndexSizeInBits(GEP->getPointerAddressSpace());

73 if ( GEP ->collectOffset(DL, BitWidth, VariableOffsets, ConstantOffset))

74 return std::nullopt;

75 if (VariableOffsets.size() != 1)

76 return std::nullopt;

78 if (!ConstantOffset.isZero())

79 return std::nullopt;

80 APInt StrideBytes = VariableOffsets.front().second;

82 if (JumpTableSizeBytes % StrideBytes.getZExtValue() != 0)

83 return std::nullopt;

86 return std::nullopt;

91 for (uint64_t Index = 0; Index < N; ++Index) {

97 if (!Func || Func->isDeclaration() ||

99 return std::nullopt;

101 }

103}

104

109 GetGuidForFunction) {

111

118

121 F.getContext(), "default.switch.case.unreachable", &F, Tail);

122 IRBuilder<> BuilderUnreachable(BBUnreachable);

124

126 SwitchInst *Switch = Builder.CreateSwitch(JT.Index, BBUnreachable);

128

131 IsVoid ? nullptr : BuilderTail.CreatePHI(CB->getType(), JT.Funcs.size());

132 const auto *ProfMD = CB->getMetadata(LLVMContext::MD_prof);

133

137 if (HadProfile) {

138

139

141 JT.Funcs, [](const Function *F) { return F && !F->isDeclaration(); }));

142 BranchWeights.reserve(JT.Funcs.size() + 1);

143

144

148 *CB, InstrProfValueKind::IPVK_IndirectCallTarget,

149 std::numeric_limits<uint32_t>::max(), TotalCount);

150

151 for (const auto &[G, C] : Targets) {

152 [[maybe_unused]] auto It = GuidToCounter.insert({G, C});

154 }

155 }

161

163

164

165

166 Call->setMetadata(LLVMContext::MD_prof, nullptr);

167 Call->setCalledFunction(Func);

168 Call->insertInto(B, B->end());

169 Switch->addCase(

172

173

174 BranchWeights.push_back(FctID == 0U ? 0U

175 : GuidToCounter.lookup_or(FctID, 0U));

179 }

181 ORE.emit([&]() {

183 << "expanded indirect call into switch";

184 });

186

189 false);

190 } else

196}

197

204 DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy);

206 auto FuncToGuid = [&](const Function &Fct) {

209

211 };

212

215 while (CurrentBB) {

216 BasicBlock *SplittedOutTail = nullptr;

219 if ( Call || Call->getCalledFunction() || Call->isMustTailCall())

220 continue;

222

223 if (!L || !L->isSimple())

224 continue;

226 if ( GEP )

227 continue;

229 assert(PtrTy && "call operand must be a pointer");

232 continue;

233 SplittedOutTail =

236 break;

237 }

238 CurrentBB = SplittedOutTail ? SplittedOutTail : nullptr;

239 }

240 }

241

244

246 if (DT)

248 if (PDT)

250 return PA;

251}

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

This file defines the DenseSet and SmallDenseSet classes.

static cl::opt< unsigned > FunctionSizeThreshold("jump-table-to-switch-function-size-threshold", cl::Hidden, cl::desc("Only split jump tables containing functions whose sizes are less " "or equal than this threshold."), cl::init(50))

static BasicBlock * expandToSwitch(CallBase *CB, const JumpTableTy &JT, DomTreeUpdater &DTU, OptimizationRemarkEmitter &ORE, llvm::function_ref< GlobalValue::GUID(const Function &)> GetGuidForFunction)

Definition JumpTableToSwitch.cpp:106

static cl::opt< unsigned > JumpTableSizeThreshold("jump-table-to-switch-size-threshold", cl::Hidden, cl::desc("Only split jump tables with size less or " "equal than JumpTableSizeThreshold."), cl::init(10))

static std::optional< JumpTableTy > parseJumpTable(GetElementPtrInst *GEP, PointerType *PtrTy)

Definition JumpTableToSwitch.cpp:57

This file contains the declarations for profiling metadata utility functions.

This file defines the SmallVector class.

Class for arbitrary precision integers.

uint64_t getZExtValue() const

Get zero extended value.

bool isZero() const

Determine if this value is zero, i.e. all bits are clear.

PassT::Result * getCachedResult(IRUnitT &IR) const

Get the cached result of an analysis pass for a given IR unit.

PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)

Get the result of an analysis pass for a given IR unit.

static LLVM_ABI uint64_t getGUID(const Function &F)

static LLVM_ABI const char * GUIDMetadataName

LLVM Basic Block Representation.

const Function * getParent() const

Return the enclosing method, or null if none.

static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)

Creates a new BasicBlock.

const Instruction * getTerminator() const LLVM_READONLY

Returns the terminator instruction if the block is well formed or null if the block is not well forme...

static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)

Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...

This is an important base class in LLVM.

A parsed version of the target data layout string in and methods for querying it.

ValueT lookup_or(const_arg_type_t< KeyT > Val, U &&Default) const

std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)

Analysis pass which computes a DominatorTree.

static constexpr UpdateKind Delete

static constexpr UpdateKind Insert

Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.

void applyUpdates(ArrayRef< UpdateT > Updates)

Submit updates to all available trees.

an instruction for type-safe pointer arithmetic to access elements of arrays and structs

static LLVM_ABI GUID getGUIDAssumingExternalLinkage(StringRef GlobalName)

Return a 64-bit global unique ID constructed from the name of a global symbol.

uint64_t GUID

Declare a type to represent a global unique identifier for a global value.

Type * getValueType() const

const Constant * getInitializer() const

getInitializer - Return the initializer for this global variable.

bool isConstant() const

If the value is a global constant, its value is immutable throughout the runtime execution of the pro...

bool hasDefinitiveInitializer() const

hasDefinitiveInitializer - Whether the global variable has an initializer, and any other instances of...

UnreachableInst * CreateUnreachable()

PHINode * CreatePHI(Type *Ty, unsigned NumReservedValues, const Twine &Name="")

This provides a uniform API for creating instructions and inserting them into a basic block: either a...

LLVM_ABI Instruction * clone() const

Create a copy of 'this' instruction that is identical in all ways except the following:

LLVM_ABI InstListType::iterator eraseFromParent()

This method unlinks 'this' from the containing basic block and deletes it.

MDNode * getMetadata(unsigned KindID) const

Get the metadata of given kind attached to this Instruction.

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Run the pass over the function.

Definition JumpTableToSwitch.cpp:198

std::pair< KeyT, ValueT > & front()

Analysis pass which computes a PostDominatorTree.

PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...

A set of analyses that are preserved following a run of a transformation pass.

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

PreservedAnalyses & preserve()

Mark an analysis as preserved.

void reserve(size_type N)

void push_back(const T &Elt)

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...

static LLVM_ABI Type * getVoidTy(LLVMContext &C)

LLVM Value Representation.

Type * getType() const

All values are typed, get the type of this value.

LLVM_ABI void replaceAllUsesWith(Value *V)

Change all uses of this to point to a new Value.

LLVM_ABI LLVMContext & getContext() const

All values hold a context through their type.

LLVM_ABI StringRef getName() const

Return a constant reference to the value's name.

An efficient, type-erasing, non-owning reference to a callable.

const ParentTy * getParent() const

@ Tail

Attemps to make calls as fast as possible while guaranteeing that tail call optimization can always b...

@ C

The default llvm calling convention, compatible with C.

initializer< Ty > init(const Ty &Val)

This is an optimization pass for GlobalISel generic memory operations.

bool all_of(R &&range, UnaryPredicate P)

Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.

LLVM_ABI std::string getIRPGOFuncName(const Function &F, bool InLTO=false)

auto enumerate(FirstRange &&First, RestRanges &&...Rest)

Given two or more input ranges, returns a new range whose values are tuples (A, B,...

decltype(auto) dyn_cast(const From &Val)

dyn_cast - Return the argument parameter cast to the specified type.

iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)

Make a range that does early increment to allow mutation of the underlying range without disrupting i...

LLVM_ABI void setExplicitlyUnknownBranchWeights(Instruction &I, StringRef PassName)

Specify that the branch weights for this terminator cannot be known at compile time.

LLVM_ABI void setBranchWeights(Instruction &I, ArrayRef< uint32_t > Weights, bool IsExpected, bool ElideAllZero=false)

Create a new branch_weights metadata node and add or overwrite a prof metadata reference to instructi...

auto dyn_cast_or_null(const Y &Val)

bool any_of(R &&range, UnaryPredicate P)

Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.

LLVM_ABI Constant * ConstantFoldLoadFromConst(Constant *C, Type *Ty, const APInt &Offset, const DataLayout &DL)

Extract value of C at the given Offset reinterpreted as Ty.

LLVM_ABI SmallVector< InstrProfValueData, 4 > getValueProfDataFromInst(const Instruction &Inst, InstrProfValueKind ValueKind, uint32_t MaxNumValueData, uint64_t &TotalC, bool GetNoICPValue=false)

Extract the value profile data from Inst and returns them if Inst is annotated with value profile dat...

LLVM_ABI bool isValueProfileMD(const MDNode *ProfileData)

Checks if an MDNode contains value profiling Metadata.

constexpr unsigned BitWidth

decltype(auto) cast(const From &Val)

cast - Return the argument parameter cast to the specified type.

LLVM_ABI BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)

Split the specified block at the specified instruction.

cl::opt< bool > ProfcheckDisableMetadataFixes("profcheck-disable-metadata-fixes", cl::Hidden, cl::init(false), cl::desc("Disable metadata propagation fixes discovered through Issue #147390"))

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

LLVM_ABI SmallVector< uint32_t > downscaleWeights(ArrayRef< uint64_t > Weights, std::optional< uint64_t > KnownMaxCount=std::nullopt)

downscale the given weights preserving the ratio.

A MapVector that performs no allocations if smaller than a certain size.