SpeculativeExecution.cpp Source File (original) (raw)

76using namespace llvm;

78#define DEBUG_TYPE "speculative-execution"

84 cl::desc("Speculative execution is not applied to basic blocks where "

85 "the cost of the instructions to speculatively execute "

86 "exceeds this limit."));

94 cl::desc("Speculative execution is not applied to basic blocks where the "

95 "number of instructions that would not be speculatively executed "

96 "exceeds this limit."));

100 cl::desc("Speculative execution is applied only to targets with divergent "

101 "branches, even if the pass was configured to apply only to all "

102 "targets."));

103

104namespace {

105

106class SpeculativeExecutionLegacyPass : public FunctionPass {

107public:

108 static char ID;

109 explicit SpeculativeExecutionLegacyPass(bool OnlyIfDivergentTarget = false)

110 : FunctionPass(ID), OnlyIfDivergentTarget(OnlyIfDivergentTarget ||

112 Impl(OnlyIfDivergentTarget) {}

113

116

118 if (OnlyIfDivergentTarget)

119 return "Speculatively execute instructions if target has divergent "

120 "branches";

121 return "Speculatively execute instructions";

122 }

123

124private:

125

126 const bool OnlyIfDivergentTarget;

127

129};

130}

131

132char SpeculativeExecutionLegacyPass::ID = 0;

134 "Speculatively execute instructions", false, false)

138

139void SpeculativeExecutionLegacyPass::getAnalysisUsage(AnalysisUsage &AU) const {

142 AU.setPreservesCFG();

143}

144

145bool SpeculativeExecutionLegacyPass::runOnFunction(Function &F) {

146 if (skipFunction(F))

147 return false;

148

149 auto *TTI = &getAnalysis().getTTI(F);

150 return Impl.runImpl(F, TTI);

151}

152

153namespace llvm {

154

157 LLVM_DEBUG(dbgs() << "Not running SpeculativeExecution because "

158 "TTI->hasBranchDivergence() is false.\n");

159 return false;

160 }

161

162 this->TTI = TTI;

163 bool Changed = false;

164 for (auto& B : F) {

165 Changed |= runOnBasicBlock(B);

166 }

167 return Changed;

168}

169

170bool SpeculativeExecutionPass::runOnBasicBlock(BasicBlock &B) {

171 BranchInst *BI = dyn_cast(B.getTerminator());

172 if (BI == nullptr)

173 return false;

174

176 return false;

179

180 if (&B == &Succ0 || &B == &Succ1 || &Succ0 == &Succ1) {

181 return false;

182 }

183

184

187 return considerHoistingFromTo(Succ0, B);

188 }

189

190

193 return considerHoistingFromTo(Succ1, B);

194 }

195

196

197

203

204

205 if (Succ1.size() == 1)

206 return considerHoistingFromTo(Succ0, B);

207 if (Succ0.size() == 1)

208 return considerHoistingFromTo(Succ1, B);

209 }

210

211 return false;

212}

213

217 case Instruction::GetElementPtr:

218 case Instruction::Add:

219 case Instruction::Mul:

220 case Instruction::And:

221 case Instruction::Or:

222 case Instruction::Select:

223 case Instruction::Shl:

224 case Instruction::Sub:

225 case Instruction::LShr:

226 case Instruction::AShr:

227 case Instruction::Xor:

228 case Instruction::ZExt:

229 case Instruction::SExt:

230 case Instruction::Call:

231 case Instruction::BitCast:

232 case Instruction::PtrToInt:

233 case Instruction::IntToPtr:

234 case Instruction::AddrSpaceCast:

235 case Instruction::FPToUI:

236 case Instruction::FPToSI:

237 case Instruction::UIToFP:

238 case Instruction::SIToFP:

239 case Instruction::FPExt:

240 case Instruction::FPTrunc:

241 case Instruction::FAdd:

242 case Instruction::FSub:

243 case Instruction::FMul:

244 case Instruction::FDiv:

245 case Instruction::FRem:

246 case Instruction::FNeg:

247 case Instruction::ICmp:

248 case Instruction::FCmp:

249 case Instruction::Trunc:

250 case Instruction::Freeze:

251 case Instruction::ExtractElement:

252 case Instruction::InsertElement:

253 case Instruction::ShuffleVector:

254 case Instruction::ExtractValue:

255 case Instruction::InsertValue:

257

258 default:

260

261 }

262}

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286bool SpeculativeExecutionPass::considerHoistingFromTo(

289 auto HasNoUnhoistedInstr = [&NotHoisted](auto Values) {

290 for (const Value *V : Values) {

291 if (const auto *I = dyn_cast_or_null(V))

293 return false;

294 }

295 return true;

296 };

297 auto AllPrecedingUsesFromBlockHoisted =

298 [&HasNoUnhoistedInstr](const User *U) {

299

300 if (isa(U))

301 return false;

302

303 return HasNoUnhoistedInstr(U->operand_values());

304 };

305

307 unsigned NotHoistedInstCount = 0;

308 for (const auto &I : FromBlock) {

311 AllPrecedingUsesFromBlockHoisted(&I)) {

312 TotalSpeculationCost += Cost;

314 return false;

315 } else {

316

317 if (!isa(I))

318 NotHoistedInstCount++;

320 return false;

322 }

323 }

324

325 for (auto I = FromBlock.begin(); I != FromBlock.end();) {

326

327

328 auto Current = I;

329 ++I;

330 if (!NotHoisted.count(&*Current)) {

332 Current->dropLocation();

333 }

334 }

335 return true;

336}

337

339 return new SpeculativeExecutionLegacyPass();

340}

341

343 return new SpeculativeExecutionLegacyPass( true);

344}

345

347 : OnlyIfDivergentTarget(OnlyIfDivergentTarget ||

349

353

355

356 if (!Changed)

360 return PA;

361}

362

366 OS, MapClassName2PassName);

367 OS << '<';

368 if (OnlyIfDivergentTarget)

369 OS << "only-if-divergent-target";

370 OS << '>';

371}

372}

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

This is the interface for a simple mod/ref and alias analysis over globals.

#define INITIALIZE_PASS_DEPENDENCY(depName)

#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)

#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)

This file defines the SmallPtrSet class.

static cl::opt< unsigned > SpecExecMaxNotHoisted("spec-exec-max-not-hoisted", cl::init(5), cl::Hidden, cl::desc("Speculative execution is not applied to basic blocks where the " "number of instructions that would not be speculatively executed " "exceeds this limit."))

speculative Speculatively execute instructions

static cl::opt< unsigned > SpecExecMaxSpeculationCost("spec-exec-max-speculation-cost", cl::init(7), cl::Hidden, cl::desc("Speculative execution is not applied to basic blocks where " "the cost of the instructions to speculatively execute " "exceeds this limit."))

static cl::opt< bool > SpecExecOnlyIfDivergentTarget("spec-exec-only-if-divergent-target", cl::init(false), cl::Hidden, cl::desc("Speculative execution is applied only to targets with divergent " "branches, even if the pass was configured to apply only to all " "targets."))

This pass exposes codegen information to IR-level passes.

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

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

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

Represent the analysis usage information of a pass.

LLVM Basic Block Representation.

const BasicBlock * getSinglePredecessor() const

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

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

Conditional or Unconditional Branch instruction.

unsigned getNumSuccessors() const

BasicBlock * getSuccessor(unsigned i) const

Represents analyses that only rely on functions' control flow.

FunctionPass class - This class is used to implement most global optimizations.

virtual bool runOnFunction(Function &F)=0

runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.

Legacy wrapper pass to provide the GlobalsAAResult object.

static InstructionCost getInvalid(CostType Val=0)

unsigned getOpcode() const

Return the opcode for this Instruction or ConstantExpr.

virtual void getAnalysisUsage(AnalysisUsage &) const

getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...

virtual StringRef getPassName() const

getPassName - Return a nice clean name for a pass.

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.

void preserveSet()

Mark an analysis set as preserved.

size_type count(ConstPtrType Ptr) const

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

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

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

bool contains(ConstPtrType Ptr) const

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

SpeculativeExecutionPass(bool OnlyIfDivergentTarget=false)

bool runImpl(Function &F, TargetTransformInfo *TTI)

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)

StringRef - Represent a constant reference to a string, i.e.

Analysis pass providing the TargetTransformInfo.

Wrapper pass for TargetTransformInfo.

This pass provides access to the codegen interfaces that are needed for IR-level transformations.

bool hasBranchDivergence(const Function *F=nullptr) const

Return true if branch divergence exists.

@ TCK_SizeAndLatency

The weighted sum of size and latency.

InstructionCost getInstructionCost(const User *U, ArrayRef< const Value * > Operands, TargetCostKind CostKind) const

Estimate the cost of a given IR user when lowered.

LLVM Value Representation.

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

This class implements an extremely fast bulk output stream that can only output to a stream.

unsigned ID

LLVM IR allows to use arbitrary numbers as calling convention identifiers.

initializer< Ty > init(const Ty &Val)

This is an optimization pass for GlobalISel generic memory operations.

FunctionPass * createSpeculativeExecutionIfHasBranchDivergencePass()

raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

FunctionPass * createSpeculativeExecutionPass()

bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr, bool UseVariableInfo=true)

Return true if the instruction does not have any effects besides calculating the result and does not ...

static InstructionCost ComputeSpeculationCost(const Instruction *I, const TargetTransformInfo &TTI)

A CRTP mix-in to automatically provide informational APIs needed for passes.