SpeculateAnalyses.cpp Source File (original) (raw)

21namespace {

22using namespace llvm;

30 else

31 return false;

32 };

33 for (auto &BB : F)

34 if (findCallInst(*BB.getTerminator()) ||

35 llvm::any_of(BB.instructionsWithoutDebug(), findCallInst))

38 return BBs;

39}

40}

45namespace llvm {

46namespace orc {

51 assert(BB != nullptr && "Traversing Null BB to find calls?");

54 auto CalledValue = Call->getCalledOperand()->stripPointerCasts();

57 };

64}

74size_t BlockFreqQuery::numBBToGet(size_t numBB) {

76 if (numBB < 4)

77 return numBB;

79 else if (numBB < 20)

80 return (numBB / 2);

81 else

82 return (numBB / 2) + (numBB / 4);

83}

92 PB.registerFunctionAnalyses(FAM);

94 auto IBBs = findBBwithCalls(F);

96 if (IBBs.empty())

97 return std::nullopt;

100

101 for (const auto I : IBBs)

102 BBFreqs.push_back({I, BFI.getBlockFreq(I).getFrequency()});

103

104 assert(IBBs.size() == BBFreqs.size() && "BB Count Mismatch");

105

106 llvm::sort(BBFreqs, [](decltype(BBFreqs)::const_reference BBF,

107 decltype(BBFreqs)::const_reference BBS) {

108 return BBF.second > BBS.second ? true : false;

109 });

110

111

112 auto Topk = numBBToGet(BBFreqs.size());

113

114 for (size_t i = 0; i < Topk; i++)

115 findCalles(BBFreqs[i].first, Calles);

116

117 assert(!Calles.empty() && "Running Analysis on Function with no calls?");

118

119 CallerAndCalles.insert({F.getName(), std::move(Calles)});

120

121 return CallerAndCalles;

122}

123

124

125std::size_t SequenceBBQuery::getHottestBlocks(std::size_t TotalBlocks) {

126 if (TotalBlocks == 1)

127 return TotalBlocks;

128 return TotalBlocks / 2;

129}

130

131

133SequenceBBQuery::rearrangeBB(const Function &F, const BlockListTy &BBList) {

135

136 for (auto &Block : F)

139

140 assert(RearrangedBBSet.size() == BBList.size() &&

141 "BasicBlock missing while rearranging?");

142 return RearrangedBBSet;

143}

144

145void SequenceBBQuery::traverseToEntryBlock(const BasicBlock *AtBB,

146 const BlockListTy &CallerBlocks,

147 const BackEdgesInfoTy &BackEdgesInfo,

151 if (Itr != VisitedBlocks.end()) {

152 if (!Itr->second.Upward)

153 return;

154 Itr->second.Upward = false;

155 } else {

156

157 WalkDirection BlockHint;

158 BlockHint.Upward = false;

159

161 BlockHint.CallerBlock = true;

163 }

164

166

167

168

169 if (PIt == EIt)

170 return;

171

172 DenseSet<const BasicBlock *> PredSkipNodes;

173

174

175

176 for (auto &I : BackEdgesInfo)

177 if (I.second == AtBB)

178 PredSkipNodes.insert(I.first);

179

180

181 for (; PIt != EIt; ++PIt)

182

183 if (BPI->isEdgeHot(*PIt, AtBB) && !PredSkipNodes.count(*PIt))

184 traverseToEntryBlock(*PIt, CallerBlocks, BackEdgesInfo, BPI,

186}

187

188void SequenceBBQuery::traverseToExitBlock(const BasicBlock *AtBB,

189 const BlockListTy &CallerBlocks,

190 const BackEdgesInfoTy &BackEdgesInfo,

191 const BranchProbabilityInfo *BPI,

195 if (!Itr->second.Downward)

196 return;

197 Itr->second.Downward = false;

198 } else {

199

200 WalkDirection BlockHint;

201 BlockHint.Downward = false;

202

204 BlockHint.CallerBlock = true;

206 }

207

209 if (PIt == EIt)

210 return;

211

212

213 DenseSet<const BasicBlock *> SuccSkipNodes;

214

215

216

217 for (auto &I : BackEdgesInfo)

218 if (I.first == AtBB)

219 SuccSkipNodes.insert(I.second);

220

221 for (; PIt != EIt; ++PIt)

222 if (BPI->isEdgeHot(AtBB, *PIt) && !SuccSkipNodes.count(*PIt))

223 traverseToExitBlock(*PIt, CallerBlocks, BackEdgesInfo, BPI,

225}

226

227

228

229

231SequenceBBQuery::queryCFG(Function &F, const BlockListTy &CallerBlocks) {

232

236

237 PassBuilder PB;

240

241 auto &BFI = FAM.getResult(F);

242

244

245 for (const auto I : CallerBlocks)

246 BBFreqs.push_back({I, BFI.getBlockFreq(I).getFrequency()});

247

248 llvm::sort(BBFreqs, [](decltype(BBFreqs)::const_reference Bbf,

249 decltype(BBFreqs)::const_reference Bbs) {

250 return Bbf.second > Bbs.second;

251 });

252

254 HotBlocksRef =

255 HotBlocksRef.drop_back(BBFreqs.size() - getHottestBlocks(BBFreqs.size()));

256

257 BranchProbabilityInfo *BPI =

259

260

261

262

263

264 for (auto I : HotBlocksRef) {

265 traverseToEntryBlock(I.first, CallerBlocks, BackEdgesInfo, BPI,

267 traverseToExitBlock(I.first, CallerBlocks, BackEdgesInfo, BPI,

269 }

270

273 if (I.second.CallerBlock)

274 MinCallerBlocks.push_back(std::move(I.first));

275

276 return rearrangeBB(F, MinCallerBlocks);

277}

278

280

285

286 CallerBlocks = findBBwithCalls(F);

287 if (CallerBlocks.empty())

288 return std::nullopt;

289

291 SequencedBlocks = rearrangeBB(F, CallerBlocks);

292 else

293 SequencedBlocks = queryCFG(F, CallerBlocks);

294

295 for (const auto *BB : SequencedBlocks)

297

298 CallerAndCalles.insert({F.getName(), std::move(Calles)});

299 return CallerAndCalles;

300}

301

302}

303}

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

SmallPtrSet< const BasicBlock *, 8 > VisitedBlocks

This file defines the DenseMap class.

This header defines various interfaces for pass management in LLVM.

static const Function * getCalledFunction(const Value *V)

uint64_t IntrinsicInst * II

FunctionAnalysisManager FAM

PassBuilder PB(Machine, PassOpts->PTO, std::nullopt, &PIC)

This file defines the SmallVector class.

Contains the Analyses and Result Interpretation to select likely functions to Speculatively compile b...

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.

LLVM Basic Block Representation.

LLVM_ABI iterator_range< filter_iterator< BasicBlock::const_iterator, std::function< bool(const Instruction &)> > > instructionsWithoutDebug(bool SkipPseudoOp=true) const

Return a const iterator range over the instructions in the block, skipping any debug instructions.

LLVM_ABI const BasicBlock * getSingleSuccessor() const

Return the successor of this block if it has a single successor.

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...

Analysis pass which computes BlockFrequencyInfo.

Analysis providing branch probability information.

LLVM_ABI bool isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const

Test if an edge is hot relative to other out-edges of the Src.

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

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

Implements a dense probed hash-table based set.

This class provides access to building LLVM's passes.

LLVM_ABI void registerFunctionAnalyses(FunctionAnalysisManager &FAM)

Registers all available function analysis passes.

iterator find(ConstPtrType Ptr) const

std::pair< iterator, bool > insert(PtrType Ptr)

Inserts Ptr if and only if there is no element in the container equal to Ptr.

reference emplace_back(ArgTypes &&... Args)

void push_back(const T &Elt)

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

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

size_type count(const_arg_type_t< ValueT > V) const

Return 1 if the specified key is in the set, 0 otherwise.

LLVM_ABI ResultTy operator()(Function &F)

Definition SpeculateAnalyses.cpp:85

LLVM_ABI ResultTy operator()(Function &F)

Definition SpeculateAnalyses.cpp:279

SmallVector< std::pair< const BasicBlock *, uint64_t >, 8 > BlockFreqInfoTy

DenseMap< const BasicBlock *, WalkDirection > VisitedBlocksInfoTy

SmallVector< const BasicBlock *, 8 > BlockListTy

SmallVector< std::pair< const BasicBlock *, const BasicBlock * >, 8 > BackEdgesInfoTy

std::optional< DenseMap< StringRef, DenseSet< StringRef > > > ResultTy

LLVM_ABI bool isStraightLine(const Function &F)

Definition SpeculateAnalyses.cpp:66

LLVM_ABI void findCalles(const BasicBlock *, DenseSet< StringRef > &)

Definition SpeculateAnalyses.cpp:49

Interfaces for registering analysis passes, producing common pass manager configurations,...

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.

auto pred_end(const MachineBasicBlock *BB)

decltype(auto) dyn_cast(const From &Val)

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

PredIterator< const BasicBlock, Value::const_user_iterator > const_pred_iterator

bool any_of(R &&range, UnaryPredicate P)

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

void sort(IteratorTy Start, IteratorTy End)

RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)

RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)

ArrayRef(const T &OneElt) -> ArrayRef< T >

auto pred_begin(const MachineBasicBlock *BB)

bool is_contained(R &&Range, const E &Element)

Returns true if Element is found in Range.

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

SuccIterator< const Instruction, const BasicBlock > const_succ_iterator

LLVM_ABI void FindFunctionBackedges(const Function &F, SmallVectorImpl< std::pair< const BasicBlock *, const BasicBlock * > > &Result)

Analyze the specified function to find all of the loop backedges in the function and return them.