DivRemPairs.cpp Source File (original) (raw)

26#include

28using namespace llvm;

31#define DEBUG_TYPE "div-rem-pairs"

32 STATISTIC(NumPairs, "Number of div/rem pairs");

33 STATISTIC(NumRecomposed, "Number of instructions recomposed");

34 STATISTIC(NumHoisted, "Number of instructions hoisted");

35 STATISTIC(NumDecomposed, "Number of instructions decomposed");

37 "Controls transformations in div-rem-pairs pass");

39namespace {

40struct ExpandedMatch {

43};

44}

51 Value *Dividend, *XroundedDownToMultipleOfY;

53 return std::nullopt;

59 XroundedDownToMultipleOfY,

63 return std::nullopt;

65 ExpandedMatch M;

66 M.Key.SignedOp = Div->getOpcode() == Instruction::SDiv;

67 M.Key.Dividend = Dividend;

68 M.Key.Divisor = Divisor;

70 return M;

71}

73namespace {

76struct DivRemPairWorklistEntry {

78 AssertingVH DivInst;

82 AssertingVH RemInst;

84 DivRemPairWorklistEntry(Instruction *DivInst_, Instruction *RemInst_)

85 : DivInst(DivInst_), RemInst(RemInst_) {

86 assert((DivInst->getOpcode() == Instruction::UDiv ||

87 DivInst->getOpcode() == Instruction::SDiv) &&

88 "Not a division.");

89 assert(DivInst->getType() == RemInst->getType() && "Types should match.");

92 }

95 Type *getType() const { return DivInst->getType(); }

98 bool isSigned() const { return DivInst->getOpcode() == Instruction::SDiv; }

100

101 Value *getDividend() const { return DivInst->getOperand(0); }

102 Value *getDivisor() const { return DivInst->getOperand(1); }

103

104 bool isRemExpanded() const {

105 switch (RemInst->getOpcode()) {

106 case Instruction::SRem:

107 case Instruction::URem:

108 return false;

109 default:

110 return true;

111 }

112 }

113};

114}

116

117

118

119

120

121

123

124

126

127

129 for (auto &BB : F) {

130 for (auto &I : BB) {

131 if (I.getOpcode() == Instruction::SDiv)

132 DivMap[DivRemMapKey(true, I.getOperand(0), I.getOperand(1))] = &I;

133 else if (I.getOpcode() == Instruction::UDiv)

134 DivMap[DivRemMapKey(false, I.getOperand(0), I.getOperand(1))] = &I;

135 else if (I.getOpcode() == Instruction::SRem)

136 RemMap[DivRemMapKey(true, I.getOperand(0), I.getOperand(1))] = &I;

137 else if (I.getOpcode() == Instruction::URem)

138 RemMap[DivRemMapKey(false, I.getOperand(0), I.getOperand(1))] = &I;

140 RemMap[Match->Key] = Match->Value;

141 }

142 }

143

144

146

147

148

149

150 for (auto &RemPair : RemMap) {

151

152 auto It = DivMap.find(RemPair.first);

153 if (It == DivMap.end())

154 continue;

155

156

157 NumPairs++;

159

160

162 }

163

164 return Worklist;

165}

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

184

185

186

188

189

190 for (DivRemPairWorklistEntry &E : Worklist) {

192 continue;

193

194 bool HasDivRemOp = TTI.hasDivRemOp(E.getType(), E.isSigned());

195

196 auto &DivInst = E.DivInst;

197 auto &RemInst = E.RemInst;

198

199 const bool RemOriginallyWasInExpandedForm = E.isRemExpanded();

200 (void)RemOriginallyWasInExpandedForm;

201

202 if (HasDivRemOp && E.isRemExpanded()) {

203

204

205 Value *X = E.getDividend();

206 Value *Y = E.getDivisor();

207 Instruction *RealRem = E.isSigned() ? BinaryOperator::CreateSRem(X, Y)

208 : BinaryOperator::CreateURem(X, Y);

209

210

211 RealRem->setName(RemInst->getName() + ".recomposed");

212 RealRem->insertAfter(RemInst->getIterator());

214

215 RemInst = RealRem;

216

220 NumRecomposed++;

221

222

224 }

225

226 assert((.isRemExpanded() || !HasDivRemOp) &&

227 "*If* the target supports div-rem, then by now the RemInst *is* "

228 "Instruction::[US]Rem.");

229

230

231

232

233 if (HasDivRemOp && RemInst->getParent() == DivInst->getParent())

234 continue;

235

236 bool DivDominates = DT.dominates(DivInst, RemInst);

237 if (!DivDominates && !DT.dominates(RemInst, DivInst)) {

238

239

240

242 BasicBlock *DivBB = DivInst->getParent();

243 BasicBlock *RemBB = RemInst->getParent();

244

245

246

248 for (auto I = ParentBB->begin(), E = DivOrRem->getIterator(); I != E;

249 ++I)

251 return false;

252

253 return true;

254 };

255

256

257

258

259

260

261

262

263

264

265

266

267

270

271

272

273

274

275

276

277

278

279

280

281

282

283

285

287 PredBB = RemPredBB;

288 }

289

290

293 IsSafeToHoist(RemInst, RemBB) && IsSafeToHoist(DivInst, DivBB) &&

295 [&](BasicBlock *BB) { return BB == DivBB || BB == RemBB; }) &&

297 [&](BasicBlock *BB) { return BB == RemBB || BB == PredBB; })) {

298 DivDominates = true;

301 if (HasDivRemOp) {

303 continue;

304 }

305 } else

306 continue;

307 }

308

309

310

311 if (!HasDivRemOp && E.isRemExpanded())

312 continue;

313

314 if (HasDivRemOp) {

315

316

317 if (DivDominates)

318 RemInst->moveAfter(DivInst);

319 else

320 DivInst->moveAfter(RemInst);

321 NumHoisted++;

322 } else {

323

324

325

326

327

328 assert(!RemOriginallyWasInExpandedForm &&

329 "We should not be expanding if the rem was in expanded form to "

330 "begin with.");

331

332 Value *X = E.getDividend();

333 Value *Y = E.getDivisor();

334 Instruction *Mul = BinaryOperator::CreateMul(DivInst, Y);

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367 if (!DivDominates)

368 DivInst->moveBefore(RemInst->getIterator());

369 Mul->insertAfter(RemInst->getIterator());

370 Mul->setDebugLoc(RemInst->getDebugLoc());

371 Sub->insertAfter(Mul->getIterator());

372 Sub->setDebugLoc(RemInst->getDebugLoc());

373

374

375

376 DivInst->dropPoisonGeneratingFlags();

377

378

379

380

381

382

383

384

385

386

388 auto *FrX =

389 new FreezeInst(X, X->getName() + ".frozen", DivInst->getIterator());

390 FrX->setDebugLoc(DivInst->getDebugLoc());

391 DivInst->setOperand(0, FrX);

392 Sub->setOperand(0, FrX);

393 }

394

395

397 auto *FrY =

398 new FreezeInst(Y, Y->getName() + ".frozen", DivInst->getIterator());

399 FrY->setDebugLoc(DivInst->getDebugLoc());

400 DivInst->setOperand(1, FrY);

401 Mul->setOperand(1, FrY);

402 }

403

404

405

406 Sub->setName(RemInst->getName() + ".decomposed");

408

409 RemInst = Sub;

410

413 NumDecomposed++;

414 }

416 }

417

419}

420

421

422

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

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

This file provides an implementation of debug counters.

#define DEBUG_COUNTER(VARNAME, COUNTERNAME, DESC)

This file defines the DenseMap class.

static DivRemWorklistTy getWorklist(Function &F)

Find matching pairs of integer div/rem ops (they have the same numerator, denominator,...

Definition DivRemPairs.cpp:122

SmallVector< DivRemPairWorklistEntry, 4 > DivRemWorklistTy

Definition DivRemPairs.cpp:115

static bool optimizeDivRem(Function &F, const TargetTransformInfo &TTI, const DominatorTree &DT)

Find matching pairs of integer div/rem ops (they have the same numerator, denominator,...

Definition DivRemPairs.cpp:181

static std::optional< ExpandedMatch > matchExpandedRem(Instruction &I)

See if we can match: (which is the form we expand into) X - ((X ?

Definition DivRemPairs.cpp:50

static bool isSigned(unsigned int Opcode)

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

This file implements a map that provides insertion order iteration.

FunctionAnalysisManager FAM

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

#define STATISTIC(VARNAME, DESC)

static TableGen::Emitter::Opt Y("gen-skeleton-entry", EmitSkeleton, "Generate example skeleton entry")

static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")

static SymbolRef::Type getType(const Symbol *Sym)

This pass exposes codegen information to IR-level passes.

LLVM Basic Block Representation.

LLVM_ABI const BasicBlock * getUniquePredecessor() const

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

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

Represents analyses that only rely on functions' control flow.

static bool shouldExecute(CounterInfo &Counter)

iterator find(const_arg_type_t< KeyT > Val)

Analysis pass which computes a DominatorTree.

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

LLVM_ABI bool dominates(const BasicBlock *BB, const Use &U) const

Return true if the (end of the) basic block BB dominates the use U.

This class represents a freeze function that returns random concrete value if an operand is either a ...

const DebugLoc & getDebugLoc() const

Return the debug location for this node as a DebugLoc.

LLVM_ABI InstListType::iterator eraseFromParent()

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

unsigned getOpcode() const

Returns a member of one of the enums like Instruction::Add.

void setDebugLoc(DebugLoc Loc)

Set the debug location information for this instruction.

LLVM_ABI void insertAfter(Instruction *InsertPos)

Insert an unlinked instruction into a basic block immediately after the specified instruction.

This class implements a map that also provides access to all stored values in a deterministic order.

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 & preserveSet()

Mark an analysis set as preserved.

reference emplace_back(ArgTypes &&... Args)

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

Analysis pass providing the TargetTransformInfo.

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

LLVM Value Representation.

LLVM_ABI Value(Type *Ty, unsigned scid)

LLVM_ABI void setName(const Twine &Name)

Change the name of the value.

LLVM_ABI void replaceAllUsesWith(Value *V)

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

self_iterator getIterator()

bool match(Val *V, const Pattern &P)

BinOpPred_match< LHS, RHS, is_idiv_op > m_IDiv(const LHS &L, const RHS &R)

Matches integer division operations.

bind_ty< Instruction > m_Instruction(Instruction *&I)

Match an instruction, capturing it if we match.

specificval_ty m_Specific(const Value *V)

Match if we have a specific specified value.

match_combine_and< LTy, RTy > m_CombineAnd(const LTy &L, const RTy &R)

Combine two pattern matchers matching L && R.

deferredval_ty< Value > m_Deferred(Value *const &V)

Like m_Specific(), but works if the specific value to match is determined as part of the same match()...

class_match< Value > m_Value()

Match an arbitrary value and ignore it.

BinaryOp_match< LHS, RHS, Instruction::Mul, true > m_c_Mul(const LHS &L, const RHS &R)

Matches a Mul with LHS and RHS in either order.

BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)

This is an optimization pass for GlobalISel generic memory operations.

FunctionAddr VTableAddr Value

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 successors(const MachineBasicBlock *BB)

LLVM_ABI bool isGuaranteedNotToBeUndef(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)

Returns true if V cannot be undef, but may be poison.

bool isa(const From &Val)

isa - Return true if the parameter to the template is an instance of one of the template type argu...

LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key

@ Sub

Subtraction of integers.

LLVM_ABI bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)

Return true if this function can prove that the instruction I will always transfer execution to one o...

auto predecessors(const MachineBasicBlock *BB)

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

PreservedAnalyses run(Function &F, FunctionAnalysisManager &)

Definition DivRemPairs.cpp:423