LowerExpectIntrinsic.cpp Source File (original) (raw)

27#include

29using namespace llvm;

31#define DEBUG_TYPE "lower-expect-intrinsic"

34 "Number of 'expect' intrinsic instructions handled");

50 cl::desc("Weight of the branch likely to be taken (default = 2000)"));

53 cl::desc("Weight of the branch unlikely to be taken (default = 1)"));

55static std::tuple<uint32_t, uint32_t>

57 if (IntrinsicID == Intrinsic::expect) {

61 } else {

64 "expect with probability must have 3 arguments");

65 auto *Confidence = cast(CI->getArgOperand(2));

66 double TrueProb = Confidence->getValueAPF().convertToDouble();

67 assert((TrueProb >= 0.0 && TrueProb <= 1.0) &&

68 "probability value must be in the range [0.0, 1.0]");

69 double FalseProb = (1.0 - TrueProb) / (BranchCount - 1);

70 uint32_t LikelyBW = ceil((TrueProb * (double)(INT32_MAX - 1)) + 1.0);

71 uint32_t UnlikelyBW = ceil((FalseProb * (double)(INT32_MAX - 1)) + 1.0);

72 return std::make_tuple(LikelyBW, UnlikelyBW);

73 }

74}

77 CallInst *CI = dyn_cast(SI.getCondition());

78 if (!CI)

79 return false;

82 if (!Fn || (Fn->getIntrinsicID() != Intrinsic::expect &&

83 Fn->getIntrinsicID() != Intrinsic::expect_with_probability))

84 return false;

88 if (!ExpectedValue)

89 return false;

92 unsigned n = SI.getNumCases();

93 uint32_t LikelyBranchWeightVal, UnlikelyBranchWeightVal;

94 std::tie(LikelyBranchWeightVal, UnlikelyBranchWeightVal) =

100 Weights[Index] = LikelyBranchWeightVal;

101

103

104 SI.setCondition(ArgValue);

106 return true;

107}

108

109

110

111

112

113

114

115

119 if (!ExpectedValue)

120 return;

121 const APInt &ExpectedPhiValue = ExpectedValue->getValue();

122 bool ExpectedValueIsLikely = true;

124

125

126

127

128 if (Fn->getIntrinsicID() == Intrinsic::expect_with_probability) {

129 auto *Confidence = cast(Expect->getArgOperand(2));

130 double TrueProb = Confidence->getValueAPF().convertToDouble();

131 ExpectedValueIsLikely = (TrueProb > 0.5);

132 }

133

134

135

136

137

138

139

140

141

142

143

146 while (!isa(V)) {

147 if (ZExtInst *ZExt = dyn_cast(V)) {

148 V = ZExt->getOperand(0);

150 continue;

151 }

152

153 if (SExtInst *SExt = dyn_cast(V)) {

154 V = SExt->getOperand(0);

156 continue;

157 }

158

160 if (!BinOp || BinOp->getOpcode() != Instruction::Xor)

161 return;

162

164 if (!CInt)

165 return;

166

169 }

170

171

172 auto ApplyOperations = [&](const APInt &Value) {

175 switch (Op->getOpcode()) {

176 case Instruction::Xor:

177 Result ^= cast(Op->getOperand(1))->getValue();

178 break;

179 case Instruction::ZExt:

180 Result = Result.zext(Op->getType()->getIntegerBitWidth());

181 break;

182 case Instruction::SExt:

183 Result = Result.sext(Op->getType()->getIntegerBitWidth());

184 break;

185 default:

187 }

188 }

189 return Result;

190 };

191

192 auto *PhiDef = cast(V);

193

194

195

196 auto GetDomConditional = [&](unsigned i) -> BranchInst * {

197 BasicBlock *BB = PhiDef->getIncomingBlock(i);

200 return BI;

202 if (!BB)

203 return nullptr;

206 return nullptr;

207 return BI;

208 };

209

210

211

212

213 for (unsigned i = 0, e = PhiDef->getNumIncomingValues(); i != e; ++i) {

214

215 Value *PhiOpnd = PhiDef->getIncomingValue(i);

216 ConstantInt *CI = dyn_cast(PhiOpnd);

217 if (!CI)

218 continue;

219

220

221

222

223

224

225 const APInt &CurrentPhiValue = ApplyOperations(CI->getValue());

226 if (ExpectedValueIsLikely == (ExpectedPhiValue == CurrentPhiValue))

227 continue;

228

229 BranchInst *BI = GetDomConditional(i);

230 if (!BI)

231 continue;

232

233 MDBuilder MDB(PhiDef->getContext());

234

235

236

237

238

239

240

241

242

243 auto *OpndIncomingBB = PhiDef->getIncomingBlock(i);

244 auto IsOpndComingFromSuccessor = [&](BasicBlock *Succ) {

245 if (OpndIncomingBB == Succ)

246

247

248 return true;

249 if (OpndIncomingBB == BI->getParent() && Succ == PhiDef->getParent())

250

251

252

253 return true;

254 return false;

255 };

256 uint32_t LikelyBranchWeightVal, UnlikelyBranchWeightVal;

257 std::tie(LikelyBranchWeightVal, UnlikelyBranchWeightVal) = getBranchWeight(

259 if (!ExpectedValueIsLikely)

260 std::swap(LikelyBranchWeightVal, UnlikelyBranchWeightVal);

261

262 if (IsOpndComingFromSuccessor(BI->getSuccessor(1)))

265 UnlikelyBranchWeightVal,

266 true));

267 else if (IsOpndComingFromSuccessor(BI->getSuccessor(0)))

270 LikelyBranchWeightVal,

271 true));

272 }

273}

274

275

277

278

279

280

281

282

283

284

285

286

288

289 ICmpInst *CmpI = dyn_cast(BSI.getCondition());

292 if (!CmpI) {

293 CI = dyn_cast(BSI.getCondition());

295 } else {

298 return false;

299

300 CmpConstOperand = dyn_cast(CmpI->getOperand(1));

301 if (!CmpConstOperand)

302 return false;

303 CI = dyn_cast(CmpI->getOperand(0));

304 }

305

306 if (!CI)

307 return false;

308

309 uint64_t ValueComparedTo = 0;

310 if (CmpConstOperand) {

312 return false;

313 ValueComparedTo = CmpConstOperand->getZExtValue();

314 }

315

317 if (!Fn || (Fn->getIntrinsicID() != Intrinsic::expect &&

318 Fn->getIntrinsicID() != Intrinsic::expect_with_probability))

319 return false;

320

323 if (!ExpectedValue)

324 return false;

325

328

329 uint32_t LikelyBranchWeightVal, UnlikelyBranchWeightVal;

330 std::tie(LikelyBranchWeightVal, UnlikelyBranchWeightVal) =

332

334 if ((ExpectedValue->getZExtValue() == ValueComparedTo) ==

337 LikelyBranchWeightVal, UnlikelyBranchWeightVal, true);

338 ExpectedWeights = {LikelyBranchWeightVal, UnlikelyBranchWeightVal};

339 } else {

341 LikelyBranchWeightVal, true);

342 ExpectedWeights = {UnlikelyBranchWeightVal, LikelyBranchWeightVal};

343 }

344

345 if (CmpI)

347 else

348 BSI.setCondition(ArgValue);

349

351

352 BSI.setMetadata(LLVMContext::MD_prof, Node);

353

354 return true;

355}

356

359 return false;

360

361 return handleBrSelExpect(BI);

362}

363

365 bool Changed = false;

366

368

369 if (BranchInst *BI = dyn_cast(BB.getTerminator())) {

371 ExpectIntrinsicsHandled++;

372 } else if (SwitchInst *SI = dyn_cast(BB.getTerminator())) {

374 ExpectIntrinsicsHandled++;

375 }

376

377

378

379

381 CallInst *CI = dyn_cast(&Inst);

382 if (!CI) {

383 if (SelectInst *SI = dyn_cast(&Inst)) {

385 ExpectIntrinsicsHandled++;

386 }

387 continue;

388 }

389

391 if (Fn && (Fn->getIntrinsicID() == Intrinsic::expect ||

392 Fn->getIntrinsicID() == Intrinsic::expect_with_probability)) {

393

394

395

400 Changed = true;

401 }

402 }

403 }

404

405 return Changed;

406}

407

412

414}

This file contains the declarations for the subclasses of Constant, which represent the different fla...

static cl::opt< uint32_t > UnlikelyBranchWeight("unlikely-branch-weight", cl::Hidden, cl::init(1), cl::desc("Weight of the branch unlikely to be taken (default = 1)"))

static bool handleBranchExpect(BranchInst &BI)

static std::tuple< uint32_t, uint32_t > getBranchWeight(Intrinsic::ID IntrinsicID, CallInst *CI, int BranchCount)

static bool handleBrSelExpect(BrSelInst &BSI)

static cl::opt< uint32_t > LikelyBranchWeight("likely-branch-weight", cl::Hidden, cl::init(2000), cl::desc("Weight of the branch likely to be taken (default = 2000)"))

static bool handleSwitchExpect(SwitchInst &SI)

static bool lowerExpectIntrinsic(Function &F)

static void handlePhiDef(CallInst *Expect)

Handler for PHINodes that define the value argument to an @llvm.expect call.

The header file for the LowerExpectIntrinsic pass as used by the new pass manager.

This file contains the declarations for profiling metadata utility functions.

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

This file defines the SmallVector class.

This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...

#define STATISTIC(VARNAME, DESC)

Class for arbitrary precision integers.

A container for analyses that lazily runs them and caches their results.

LLVM Basic Block Representation.

const BasicBlock * getSinglePredecessor() const

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

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

BinaryOps getOpcode() const

Conditional or Unconditional Branch instruction.

bool isConditional() const

BasicBlock * getSuccessor(unsigned i) const

bool isUnconditional() const

Function * getCalledFunction() const

Returns the function called, or null if this is an indirect function invocation or the function signa...

Value * getArgOperand(unsigned i) const

This class represents a function call, abstracting a target machine's calling convention.

Predicate

This enumeration lists the possible predicates for CmpInst subclasses.

Predicate getPredicate() const

Return the predicate for this instruction.

This is the shared class of boolean and integer constants.

unsigned getBitWidth() const

getBitWidth - Return the scalar bitwidth of this constant.

uint64_t getZExtValue() const

Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...

const APInt & getValue() const

Return the constant as an APInt value reference.

This class represents an Operation in the Expression.

Intrinsic::ID getIntrinsicID() const LLVM_READONLY

getIntrinsicID - This method returns the ID number of the specified function, or Intrinsic::not_intri...

This instruction compares its operands according to the predicate given to the constructor.

InstListType::iterator eraseFromParent()

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

void setMetadata(unsigned KindID, MDNode *Node)

Set the metadata of the specified kind to the specified node.

MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight, bool IsExpected=false)

Return metadata containing two branch weights.

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

static PreservedAnalyses none()

Convenience factory function for the empty preserved set.

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

This class represents a sign extension of integer types.

This class represents the LLVM 'select' instruction.

void push_back(const T &Elt)

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

unsigned getCaseIndex() const

Returns number of current case.

void setOperand(unsigned i, Value *Val)

Value * getOperand(unsigned i) const

unsigned getNumOperands() const

LLVM Value Representation.

void replaceAllUsesWith(Value *V)

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

LLVMContext & getContext() const

All values hold a context through their type.

This class represents zero extension of integer types.

const ParentTy * getParent() const

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

initializer< Ty > init(const Ty &Val)

void checkFrontendInstrumentation(Instruction &I, const ArrayRef< uint32_t > ExpectedWeights)

checkFrontendInstrumentation - compares PGO counters to the thresholds used for llvm....

void checkExpectAnnotations(Instruction &I, const ArrayRef< uint32_t > ExistingWeights, bool IsFrontend)

checkExpectAnnotations - compares PGO counters to the thresholds used for llvm.expect and warns if th...

This is an optimization pass for GlobalISel generic memory operations.

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

auto reverse(ContainerTy &&C)

void setBranchWeights(Instruction &I, ArrayRef< uint32_t > Weights, bool IsExpected)

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

void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)

Implement std::swap in terms of BitVector swap.

PreservedAnalyses run(Function &F, FunctionAnalysisManager &)

Run the pass over the function.