LowerSwitch.cpp Source File (original) (raw)

41#include

42#include

43#include

45using namespace llvm;

47#define DEBUG_TYPE "lower-switch"

49namespace {

51struct IntRange {

53};

55}

57namespace {

59bool IsInRanges(const IntRange &R, const std::vector &Ranges) {

66 Ranges, R, [](IntRange A, IntRange B) { return A.High.slt(B.High); });

67 return I != Ranges.end() && I->Low.sle(R.Low);

68}

70struct CaseRange {

71 ConstantInt *Low;

72 ConstantInt *High;

75 CaseRange(ConstantInt *low, ConstantInt *high, BasicBlock *bb)

76 : Low(low), High(high), BB(bb) {}

77};

79using CaseVector = std::vector;

80using CaseItr = std::vector::iterator;

84struct CaseCmp {

85 bool operator()(const CaseRange &C1, const CaseRange &C2) {

89 }

90};

95 O << "[";

97 for (CaseVector::const_iterator B = C.begin(), E = C.end(); B != E;) {

98 O << "[" << B->Low->getValue() << ", " << B->High->getValue() << "]";

99 if (++B != E)

100 O << ", ";

101 }

102

103 return O << "]";

104}

105

106

107

108

109

110

111

112

113

114

115

117 const APInt &NumMergedCases) {

118 for (auto &I : SuccBB->phis()) {

120

121

123 APInt LocalNumMergedCases = NumMergedCases;

124 for (; Idx != E && NewBB; ++Idx) {

127 break;

128 }

129 }

130

131

132 if (NewBB)

133 ++Idx;

134

135

136

138 for (; LocalNumMergedCases.ugt(0) && Idx < E; ++Idx)

141 LocalNumMergedCases -= 1;

142 }

143

144

147 }

148}

149

150

151

152

153

159 F->insert(++OrigBlock->getIterator(), NewLeaf);

160

161

163 if (Leaf.Low == Leaf.High) {

164

165 Comp =

167 } else {

168

169 if (Leaf.Low == LowerBound) {

170

172 "SwitchLeaf");

173 } else if (Leaf.High == UpperBound) {

174

176 "SwitchLeaf");

177 } else if (Leaf.Low->isZero()) {

178

180 "SwitchLeaf");

181 } else {

182

185 Val, NegLo, Val->getName() + ".off", NewLeaf);

188 "SwitchLeaf");

189 }

190 }

191

192

195

196

197 for (auto &I : Default->phis()) {

201 }

202

203

204

207

209 for (APInt j(Range.getBitWidth(), 0, false); j.ult(Range); ++j) {

211 }

212

214 assert(BlockIdx != -1 && "Switch didn't go to this successor??");

216 }

217

218 return NewLeaf;

219}

220

221

222

223

224

225

230 const std::vector &UnreachableRanges) {

231 assert(LowerBound && UpperBound && "Bounds must be initialized");

232 unsigned Size = End - Begin;

233

234 if (Size == 1) {

235

236

237

238

239 if (Begin->Low == LowerBound && Begin->High == UpperBound) {

241 FixPhis(Begin->BB, OrigBlock, Predecessor, NumMergedCases);

242 return Begin->BB;

243 }

244 return NewLeafBlock(*Begin, Val, LowerBound, UpperBound, OrigBlock,

246 }

247

248 unsigned Mid = Size / 2;

249 std::vector LHS(Begin, Begin + Mid);

251 std::vector RHS(Begin + Mid, End);

253

254 CaseRange &Pivot = *(Begin + Mid);

256 << Pivot.High->getValue() << "]\n");

257

258

259

260

261

263

264

265

267 NewLowerBound->getValue() - 1);

268

269 if (!UnreachableRanges.empty()) {

270

271 APInt GapLow = LHS.back().High->getValue() + 1;

273 IntRange Gap = {GapLow, GapHigh};

274 if (GapHigh.sge(GapLow) && IsInRanges(Gap, UnreachableRanges))

275 NewUpperBound = LHS.back().High;

276 }

277

279 << NewUpperBound->getValue() << "]\n"

280 << "RHS Bounds ==> [" << NewLowerBound->getValue() << ", "

281 << UpperBound->getValue() << "]\n");

282

283

284

287

289

291 SwitchConvert(LHS.begin(), LHS.end(), LowerBound, NewUpperBound, Val,

292 NewNode, OrigBlock, Default, UnreachableRanges);

294 SwitchConvert(RHS.begin(), RHS.end(), NewLowerBound, UpperBound, Val,

295 NewNode, OrigBlock, Default, UnreachableRanges);

296

297 F->insert(++OrigBlock->getIterator(), NewNode);

299

301 return NewNode;

302}

303

304

305

306

307unsigned Clusterify(CaseVector &Cases, SwitchInst *SI) {

308 unsigned NumSimpleCases = 0;

309

310

311 for (auto Case : SI->cases()) {

312 if (Case.getCaseSuccessor() == SI->getDefaultDest())

313 continue;

314 Cases.push_back(CaseRange(Case.getCaseValue(), Case.getCaseValue(),

315 Case.getCaseSuccessor()));

316 ++NumSimpleCases;

317 }

318

320

321

322 if (Cases.size() >= 2) {

323 CaseItr I = Cases.begin();

324 for (CaseItr J = std::next(I), E = Cases.end(); J != E; ++J) {

325 const APInt &nextValue = J->Low->getValue();

326 const APInt &currentValue = I->High->getValue();

329

330

331

332 assert(nextValue.sgt(currentValue) &&

333 "Cases should be strictly ascending");

334 if ((nextValue == currentValue + 1) && (currentBB == nextBB)) {

335 I->High = J->High;

336

337 } else if (++I != J) {

338 *I = *J;

339 }

340 }

341 Cases.erase(std::next(I), Cases.end());

342 }

343

344 return NumSimpleCases;

345}

346

347

348

354 Value *Val = SI->getCondition();

356

357

358

359 if ((OrigBlock != &F->getEntryBlock() && pred_empty(OrigBlock)) ||

361 DeleteList.insert(OrigBlock);

362 return;

363 }

364

365

366 CaseVector Cases;

367 const unsigned NumSimpleCases = Clusterify(Cases, SI);

369 const unsigned BitWidth = IT->getBitWidth();

370

371

374 LLVM_DEBUG(dbgs() << "Clusterify finished. Total clusters: " << Cases.size()

375 << ". Total non-default cases: " << NumSimpleCases

376 << "\nCase clusters: " << Cases << "\n");

377

378

379 if (Cases.empty()) {

381

382 FixPhis(Default, OrigBlock, OrigBlock, UnsignedMax);

383 SI->eraseFromParent();

384 return;

385 }

386

389 bool DefaultIsUnreachableFromSwitch = false;

390

391 if (SI->defaultDestUnreachable()) {

392

393

394

395 LowerBound = Cases.front().Low;

396 UpperBound = Cases.back().High;

397 DefaultIsUnreachableFromSwitch = true;

398 } else {

399

400

401

402

403

404

405

406

407

410

416

417

418

419

420 const APInt &Low = Cases.front().Low->getValue();

421 const APInt &High = Cases.back().High->getValue();

424

425 LowerBound = ConstantInt::get(SI->getContext(), Min);

426 UpperBound = ConstantInt::get(SI->getContext(), Max);

427 DefaultIsUnreachableFromSwitch = (Min + (NumSimpleCases - 1) == Max);

428 }

429

430 std::vector UnreachableRanges;

431

432 if (DefaultIsUnreachableFromSwitch) {

434 APInt MaxPop(UnsignedZero);

436

439 IntRange R = {SignedMin, SignedMax};

440 UnreachableRanges.push_back(R);

441 for (const auto &I : Cases) {

442 const APInt &Low = I.Low->getValue();

443 const APInt &High = I.High->getValue();

444

445 IntRange &LastRange = UnreachableRanges.back();

446 if (LastRange.Low.eq(Low)) {

447

448 UnreachableRanges.pop_back();

449 } else {

450

452 LastRange.High = Low - 1;

453 }

454 if (High.ne(SignedMax)) {

455 IntRange R = {High + 1, SignedMax};

456 UnreachableRanges.push_back(R);

457 }

458

459

460 assert(High.sge(Low) && "Popularity shouldn't be negative.");

462

463 APInt &Pop = Popularity.insert({I.BB, APInt(UnsignedZero)}).first->second;

464 if ((Pop += N).ugt(MaxPop)) {

465 MaxPop = Pop;

466 PopSucc = I.BB;

467 }

468 }

469#ifndef NDEBUG

470

471 for (auto I = UnreachableRanges.begin(), E = UnreachableRanges.end();

472 I != E; ++I) {

474 auto Next = I + 1;

477 }

478 }

479#endif

480

481

482

483 const unsigned NumDefaultEdges = SI->getNumCases() + 1 - NumSimpleCases;

484 for (unsigned I = 0; I < NumDefaultEdges; ++I)

485 Default->removePredecessor(OrigBlock);

486

487

488

491 [PopSucc](const CaseRange &R) { return R.BB == PopSucc; });

492

493

494 if (Cases.empty()) {

496 SI->eraseFromParent();

497

498

499 if (!MaxPop.isZero())

500 for (APInt I(UnsignedZero); I.ult(MaxPop - 1); ++I)

502 return;

503 }

504

505

506

507

508 Val = SI->getCondition();

509 }

510

512 SwitchConvert(Cases.begin(), Cases.end(), LowerBound, UpperBound, Val,

513 OrigBlock, OrigBlock, Default, UnreachableRanges);

514

515

516

517

518

519

520 if (SwitchBlock != Default)

521 FixPhis(Default, OrigBlock, nullptr, UnsignedMax);

522

523

525

526

527 BasicBlock *OldDefault = SI->getDefaultDest();

528 SI->eraseFromParent();

529

530

532 DeleteList.insert(OldDefault);

533}

534

538

539

541

542

543 if (DeleteList.count(&Cur))

544 continue;

545

548 ProcessSwitchInst(SI, DeleteList, AC, LVI);

549 }

550 }

551

555 }

556

558}

559

560

561class LowerSwitchLegacyPass : public FunctionPass {

562public:

563

564 static char ID;

565

566 LowerSwitchLegacyPass() : FunctionPass(ID) {

568 }

569

571

572 void getAnalysisUsage(AnalysisUsage &AU) const override {

573 AU.addRequired();

574 }

575};

576

577}

578

579char LowerSwitchLegacyPass::ID = 0;

580

581

583

585 "Lower SwitchInst's to branches", false, false)

590

591

593 return new LowerSwitchLegacyPass();

594}

595

596bool LowerSwitchLegacyPass::runOnFunction(Function &F) {

597 LazyValueInfo *LVI = &getAnalysis().getLVI();

598 auto *ACT = getAnalysisIfAvailable();

599 AssumptionCache *AC = ACT ? &ACT->getAssumptionCache(F) : nullptr;

600 return LowerSwitch(F, LVI, AC);

601}

602

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

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::values(clEnumValN(DefaultIT, "arm-default-it", "Generate any type of IT block"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow complex IT blocks")))

static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")

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

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

#define LLVM_ATTRIBUTE_USED

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

This file defines the DenseMap class.

static bool runOnFunction(Function &F, bool PostInlining)

This file provides various utilities for inspecting and working with the control flow graph in LLVM I...

This header defines various interfaces for pass management in LLVM.

ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))

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

This file defines the SmallVector class.

Class for arbitrary precision integers.

static APInt getMaxValue(unsigned numBits)

Gets maximum unsigned value of APInt for specific bit width.

bool sgt(const APInt &RHS) const

Signed greater than comparison.

bool ugt(const APInt &RHS) const

Unsigned greater than comparison.

static APInt getSignedMaxValue(unsigned numBits)

Gets maximum signed value of APInt for a specific bit width.

bool eq(const APInt &RHS) const

Equality comparison.

static APInt getSignedMinValue(unsigned numBits)

Gets minimum signed value of APInt for a specific bit width.

bool slt(const APInt &RHS) const

Signed less than comparison.

bool sge(const APInt &RHS) const

Signed greater or equal comparison.

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.

AnalysisUsage & addRequired()

A function analysis which provides an AssumptionCache.

An immutable pass that tracks lazily created AssumptionCache objects.

A cache of @llvm.assume calls within a function.

LLVM Basic Block Representation.

iterator begin()

Instruction iterator methods.

iterator_range< const_phi_iterator > phis() const

Returns a range that iterates over the phis in the basic block.

const Function * getParent() const

Return the enclosing method, or null if none.

static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)

Creates a new BasicBlock.

LLVM_ABI const BasicBlock * getSinglePredecessor() const

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

InstListType::iterator iterator

Instruction iterators...

LLVM_ABI void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)

Update PHI nodes in this BasicBlock before removal of predecessor Pred.

static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)

@ ICMP_SLT

signed less than

@ ICMP_SLE

signed less or equal

@ ICMP_SGE

signed greater or equal

@ ICMP_ULE

unsigned less or equal

static LLVM_ABI Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)

static LLVM_ABI Constant * getNeg(Constant *C, bool HasNSW=false)

This is the shared class of boolean and integer constants.

bool isZero() const

This is just a convenience method to make client code smaller for a common code.

const APInt & getValue() const

Return the constant as an APInt value reference.

This class represents a range of values.

static LLVM_ABI ConstantRange fromKnownBits(const KnownBits &Known, bool IsSigned)

Initialize a range based on a known bits constraint.

LLVM_ABI APInt getSignedMin() const

Return the smallest signed value contained in the ConstantRange.

LLVM_ABI ConstantRange intersectWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const

Return the range that results from the intersection of this range with another range.

LLVM_ABI APInt getSignedMax() const

Return the largest signed value contained in the ConstantRange.

This is an important base class in LLVM.

A parsed version of the target data layout string in and methods for querying it.

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

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

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

LLVM_ABI InstListType::iterator insertInto(BasicBlock *ParentBB, InstListType::iterator It)

Inserts an unlinked instruction into ParentBB at position It and returns the iterator of the inserted...

Class to represent integer types.

Analysis to compute lazy value information.

Wrapper around LazyValueInfo.

This pass computes, caches, and vends lazy value constraint information.

void eraseBlock(BasicBlock *BB)

Inform the analysis cache that we have erased a block.

ConstantRange getConstantRange(Value *V, Instruction *CxtI, bool UndefAllowed)

Return the ConstantRange constraint that is known to hold for the specified value at the specified in...

void addIncoming(Value *V, BasicBlock *BB)

Add an incoming value to the end of the PHI list.

void setIncomingBlock(unsigned i, BasicBlock *BB)

LLVM_ABI Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)

Remove an incoming value.

Value * getIncomingValueForBlock(const BasicBlock *BB) const

BasicBlock * getIncomingBlock(unsigned i) const

Return incoming basic block number i.

int getBasicBlockIndex(const BasicBlock *BB) const

Return the first index of the specified basic block in the value list for this PHI.

unsigned getNumIncomingValues() const

Return the number of incoming edges.

static LLVM_ABI PassRegistry * getPassRegistry()

getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...

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.

A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...

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.

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

void push_back(const T &Elt)

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

LLVM Value Representation.

LLVM_ABI LLVMContext & getContext() const

All values hold a context through their type.

LLVM_ABI StringRef getName() const

Return a constant reference to the value's name.

self_iterator getIterator()

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

const APInt & smin(const APInt &A, const APInt &B)

Determine the smaller of two APInts considered to be signed.

const APInt & smax(const APInt &A, const APInt &B)

Determine the larger of two APInts considered to be signed.

@ C

The default llvm calling convention, compatible with C.

@ BasicBlock

Various leaf nodes.

This is an optimization pass for GlobalISel generic memory operations.

@ Low

Lower the current thread's priority such that it does not affect foreground tasks significantly.

decltype(auto) dyn_cast(const From &Val)

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

LLVM_ABI void initializeLowerSwitchLegacyPassPass(PassRegistry &)

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

LLVM_ABI void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)

Delete the specified block, which must have no predecessors.

auto reverse(ContainerTy &&C)

LLVM_ABI char & LowerSwitchID

Definition LowerSwitch.cpp:582

void sort(IteratorTy Start, IteratorTy End)

LLVM_ABI void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)

Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...

LLVM_ABI raw_ostream & dbgs()

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

bool isa(const From &Val)

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

auto lower_bound(R &&Range, T &&Value)

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

FunctionAddr VTableAddr Next

raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)

constexpr unsigned BitWidth

decltype(auto) cast(const From &Val)

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

void erase_if(Container &C, UnaryPredicate P)

Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...

LLVM_ABI FunctionPass * createLowerSwitchPass()

Definition LowerSwitch.cpp:592

bool pred_empty(const BasicBlock *BB)

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Definition LowerSwitch.cpp:603