SampleProfileInference.h Source File (original) (raw)

14#ifndef LLVM_TRANSFORMS_UTILS_SAMPLEPROFILEINFERENCE_H

15#define LLVM_TRANSFORMS_UTILS_SAMPLEPROFILEINFERENCE_H

21namespace llvm {

55 std::vector Blocks;

57 std::vector Jumps;

60};

101

102

104

105

107

108

110

111

113};

114

117

118

120public:

124 using Edge = std::pair<const BasicBlockT *, const BasicBlockT *>;

129

132 : F(F), Successors(Successors), SampleBlockWeights(SampleBlockWeights) {}

136 : F(F), Successors(Successors), SampleBlockWeights(SampleBlockWeights),

137 SampleEdgeWeights(SampleEdgeWeights) {}

138

139

141

142private:

143

145 createFlowFunction(const std::vector<const BasicBlockT *> &BasicBlocks,

147

148

149

150

151 void findUnlikelyJumps(const std::vector<const BasicBlockT *> &BasicBlocks,

153

154

156

157

159

160

162

163

165

166

168};

169

170template

173

174

177 (void)BB ;

178

179

180

182 for (const auto &BB : F) {

183

184 if (isExit(&BB)) {

186 (void)RBB;

187 }

188 }

189

190

192 std::vector<const BasicBlockT *> BasicBlocks;

193 BlockIndex.reserve(Reachable.size());

194 BasicBlocks.reserve(Reachable.size());

195 for (const auto &BB : F) {

196 if (Reachable.count(&BB) && InverseReachable.count(&BB)) {

197 BlockIndex[&BB] = BasicBlocks.size();

198 BasicBlocks.push_back(&BB);

199 }

200 }

201

202 BlockWeights.clear();

203 EdgeWeights.clear();

204 bool HasSamples = false;

205 for (const auto *BB : BasicBlocks) {

206 auto It = SampleBlockWeights.find(BB);

207 if (It != SampleBlockWeights.end() && It->second > 0) {

208 HasSamples = true;

209 BlockWeights[BB] = It->second;

210 }

211 }

212

213 if (BasicBlocks.size() <= 1 || !HasSamples) {

214 return;

215 }

216

217

218 FlowFunction Func = createFlowFunction(BasicBlocks, BlockIndex);

219

220

222

223

224

225

226 for (const auto *BB : BasicBlocks) {

227 BlockWeights[BB] = Func.Blocks[BlockIndex[BB]].Flow;

228 }

229 for (auto &Jump : Func.Jumps) {

230 Edge E = std::make_pair(BasicBlocks[Jump.Source], BasicBlocks[Jump.Target]);

231 EdgeWeights[E] = Jump.Flow;

232 }

233

234#ifndef NDEBUG

235

236 for (auto &I : BlockWeights) {

237 assert(Reachable.contains(I.first));

239 }

240 for (auto &I : EdgeWeights) {

241 assert(Reachable.contains(I.first.first) &&

242 Reachable.contains(I.first.second));

244 InverseReachable.contains(I.first.second));

245 }

246#endif

247}

248

249template

250FlowFunction SampleProfileInference::createFlowFunction(

251 const std::vector<const BasicBlockT *> &BasicBlocks,

254 Func.Blocks.reserve(BasicBlocks.size());

255

256 for (const auto *BB : BasicBlocks) {

258 auto It = SampleBlockWeights.find(BB);

259 if (It != SampleBlockWeights.end()) {

260 Block.HasUnknownWeight = false;

261 Block.Weight = It->second;

262 } else {

263 Block.HasUnknownWeight = true;

264 Block.Weight = 0;

265 }

266 Block.Index = Func.Blocks.size();

268 }

269

270 for (const auto *BB : BasicBlocks) {

271 for (auto *Succ : Successors[BB]) {

272 if (!BlockIndex.count(Succ))

273 continue;

275 Jump.Source = BlockIndex[BB];

276 Jump.Target = BlockIndex[Succ];

277 auto It = SampleEdgeWeights.find(std::make_pair(BB, Succ));

278 if (It != SampleEdgeWeights.end()) {

279 Jump.HasUnknownWeight = false;

280 Jump.Weight = It->second;

281 } else {

282 Jump.HasUnknownWeight = true;

283 Jump.Weight = 0;

284 }

285 Func.Jumps.push_back(Jump);

286 }

287 }

288 for (auto &Jump : Func.Jumps) {

289 uint64_t Src = Jump.Source;

290 uint64_t Dst = Jump.Target;

291 Func.Blocks[Src].SuccJumps.push_back(&Jump);

292 Func.Blocks[Dst].PredJumps.push_back(&Jump);

293 }

294

295

296 findUnlikelyJumps(BasicBlocks, Successors, Func);

297

298

299 for (size_t I = 0; I < Func.Blocks.size(); I++) {

300 if (Func.Blocks[I].isEntry()) {

302 break;

303 }

304 }

305 assert(Func.Entry == 0 && "incorrect index of the entry block");

306

307

308 auto &EntryBlock = Func.Blocks[Func.Entry];

309 if (EntryBlock.Weight == 0 && !EntryBlock.HasUnknownWeight) {

310 EntryBlock.Weight = 1;

311 EntryBlock.HasUnknownWeight = false;

312 }

313

315}

316

317template

318inline void SampleProfileInference::findUnlikelyJumps(

319 const std::vector<const BasicBlockT *> &BasicBlocks,

320 BlockEdgeMap &Successors, FlowFunction &Func) {}

321

322template

323inline bool SampleProfileInference::isExit(const BasicBlockT *BB) {

324 return BB->succ_empty();

325}

326

327}

328#endif

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

static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")

This file defines the DenseMap class.

This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.

This file defines the SmallVector class.

iterator find(const_arg_type_t< KeyT > Val)

size_type count(const_arg_type_t< KeyT > Val) const

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

void reserve(size_type NumEntries)

Grow the densemap so that it can contain at least NumEntries items before resizing again.

std::remove_pointer_t< NodeRef > BasicBlockT

Definition SampleProfileInference.h:122

DenseMap< const BasicBlockT *, uint64_t > BlockWeightMap

Definition SampleProfileInference.h:125

DenseMap< const BasicBlockT *, SmallVector< const BasicBlockT *, 8 > > BlockEdgeMap

Definition SampleProfileInference.h:127

typename GraphTraits< FT * >::NodeRef NodeRef

Definition SampleProfileInference.h:121

SampleProfileInference(FunctionT &F, BlockEdgeMap &Successors, BlockWeightMap &SampleBlockWeights, EdgeWeightMap &SampleEdgeWeights)

Definition SampleProfileInference.h:133

FT FunctionT

Definition SampleProfileInference.h:123

DenseMap< Edge, uint64_t > EdgeWeightMap

Definition SampleProfileInference.h:126

std::pair< const BasicBlockT *, const BasicBlockT * > Edge

Definition SampleProfileInference.h:124

void apply(BlockWeightMap &BlockWeights, EdgeWeightMap &EdgeWeights)

Apply the profile inference algorithm for a given function.

Definition SampleProfileInference.h:171

SampleProfileInference(FunctionT &F, BlockEdgeMap &Successors, BlockWeightMap &SampleBlockWeights)

Definition SampleProfileInference.h:130

size_type count(ConstPtrType Ptr) const

count - Return 1 if the specified pointer is in the set, 0 otherwise.

bool contains(ConstPtrType Ptr) const

NodeAddr< FuncNode * > Func

This is an optimization pass for GlobalISel generic memory operations.

iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)

iterator_range< idf_ext_iterator< T, SetTy > > inverse_depth_first_ext(const T &G, SetTy &S)

void applyFlowInference(const ProfiParams &Params, FlowFunction &Func)

Apply the profile inference algorithm for a given function and provided profi options.

A wrapper of a binary basic block.

Definition SampleProfileInference.h:26

uint64_t Index

Definition SampleProfileInference.h:27

bool isEntry() const

Check if it is the entry block in the function.

Definition SampleProfileInference.h:36

bool isExit() const

Check if it is an exit block in the function.

Definition SampleProfileInference.h:39

uint64_t Flow

Definition SampleProfileInference.h:31

std::vector< FlowJump * > PredJumps

Definition SampleProfileInference.h:33

bool HasUnknownWeight

Definition SampleProfileInference.h:29

bool IsUnlikely

Definition SampleProfileInference.h:30

std::vector< FlowJump * > SuccJumps

Definition SampleProfileInference.h:32

uint64_t Weight

Definition SampleProfileInference.h:28

A wrapper of binary function with basic blocks and jumps.

Definition SampleProfileInference.h:53

std::vector< FlowJump > Jumps

Jumps between the basic blocks.

Definition SampleProfileInference.h:57

std::vector< FlowBlock > Blocks

Basic blocks in the function.

Definition SampleProfileInference.h:55

uint64_t Entry

The index of the entry block.

Definition SampleProfileInference.h:59

A wrapper of a jump between two basic blocks.

Definition SampleProfileInference.h:43

bool IsUnlikely

Definition SampleProfileInference.h:48

bool HasUnknownWeight

Definition SampleProfileInference.h:47

uint64_t Target

Definition SampleProfileInference.h:45

uint64_t Flow

Definition SampleProfileInference.h:49

uint64_t Weight

Definition SampleProfileInference.h:46

uint64_t Source

Definition SampleProfileInference.h:44

typename GraphType::UnknownGraphTypeError NodeRef

Various thresholds and options controlling the behavior of the profile inference algorithm.

Definition SampleProfileInference.h:65

unsigned CostJumpUnknownFTInc

The cost of increasing an unknown fall-through jump's count by one.

Definition SampleProfileInference.h:109

unsigned CostBlockInc

The cost of increasing a block's count by one.

Definition SampleProfileInference.h:76

unsigned CostJumpFTInc

The cost of increasing a fall-through jump's count by one.

Definition SampleProfileInference.h:97

bool RebalanceUnknown

Evenly re-distribute flow among unknown subgraphs.

Definition SampleProfileInference.h:70

const int64_t CostUnlikely

The cost of taking an unlikely block/jump.

Definition SampleProfileInference.h:112

unsigned CostJumpDec

The cost of decreasing a jump's count by one.

Definition SampleProfileInference.h:100

bool JoinIslands

Join isolated components having positive flow.

Definition SampleProfileInference.h:73

unsigned CostBlockZeroInc

The cost of increasing a count of zero-weight block by one.

Definition SampleProfileInference.h:82

unsigned CostBlockEntryDec

The cost of decreasing the entry block's count by one.

Definition SampleProfileInference.h:88

unsigned CostJumpInc

The cost of increasing a jump's count by one.

Definition SampleProfileInference.h:94

unsigned CostJumpUnknownInc

The cost of increasing an unknown jump's count by one.

Definition SampleProfileInference.h:106

unsigned CostBlockUnknownInc

The cost of increasing an unknown block's count by one.

Definition SampleProfileInference.h:91

unsigned CostJumpFTDec

The cost of decreasing a fall-through jump's count by one.

Definition SampleProfileInference.h:103

unsigned CostBlockDec

The cost of decreasing a block's count by one.

Definition SampleProfileInference.h:79

unsigned CostBlockEntryInc

The cost of increasing the entry block's count by one.

Definition SampleProfileInference.h:85

bool EvenFlowDistribution

Evenly distribute flow when there are multiple equally likely options.

Definition SampleProfileInference.h:67