TailRecursionElimination.cpp Source File (original) (raw)

84#include

85using namespace llvm;

87#define DEBUG_TYPE "tailcallelim"

89 STATISTIC(NumEliminated, "Number of tail calls removed");

90 STATISTIC(NumRetDuped, "Number of return duplicated");

91 STATISTIC(NumAccumAdded, "Number of accumulators introduced");

95 cl::desc("Force disabling recomputing of function entry count, on "

96 "successful tail recursion elimination."));

101

102

103

104

107 return !AI || AI->isStaticAlloca();

108 });

109}

110

111namespace {

112struct AllocaDerivedValueTracker {

113

114

115

116 void walk(Value *Root) {

118 SmallPtrSet<Use *, 32> Visited;

119

120 auto AddUsesToWorklist = [&](Value *V) {

121 for (auto &U : V->uses()) {

122 if (!Visited.insert(&U).second)

123 continue;

125 }

126 };

127

128 AddUsesToWorklist(Root);

129

130 while (!Worklist.empty()) {

133

134 switch (I->getOpcode()) {

135 case Instruction::Call:

136 case Instruction::Invoke: {

138

139

140

141

142 if (CB.isArgOperand(U) && CB.isByValArgument(CB.getArgOperandNo(U)))

143 continue;

144 bool IsNocapture =

145 CB.isDataOperand(U) && CB.doesNotCapture(CB.getDataOperandNo(U));

146 callUsesLocalStack(CB, IsNocapture);

147 if (IsNocapture) {

148

149

150 continue;

151 }

152 break;

153 }

154 case Instruction::Load: {

155

156

157 continue;

158 }

159 case Instruction::Store: {

160 if (U->getOperandNo() == 0)

161 EscapePoints.insert(I);

162 continue;

163 }

164 case Instruction::BitCast:

165 case Instruction::GetElementPtr:

166 case Instruction::PHI:

167 case Instruction::Select:

168 case Instruction::AddrSpaceCast:

169 break;

170 default:

171 EscapePoints.insert(I);

172 break;

173 }

174

175 AddUsesToWorklist(I);

176 }

177 }

178

179 void callUsesLocalStack(CallBase &CB, bool IsNocapture) {

180

181 AllocaUsers.insert(&CB);

182

183

184 if (IsNocapture)

185 return;

186

187

189 EscapePoints.insert(&CB);

190 }

191

192 SmallPtrSet<Instruction *, 32> AllocaUsers;

193 SmallPtrSet<Instruction *, 32> EscapePoints;

194};

195}

196

198 if (F.callsFunctionThatReturnsTwice())

199 return false;

200

201

202 AllocaDerivedValueTracker Tracker;

204 if (Arg.hasByValAttr())

205 Tracker.walk(&Arg);

206 }

207 for (auto &BB : F) {

208 for (auto &I : BB)

210 Tracker.walk(AI);

211 }

212

214

215

216

217

218 enum VisitType {

219 UNVISITED,

220 UNESCAPED,

221 ESCAPED

222 };

224

225

226

227

229

230

231

232

233

234

235

236

238

240 VisitType Escaped = UNESCAPED;

241 do {

242 for (auto &I : *BB) {

243 if (Tracker.EscapePoints.count(&I))

244 Escaped = ESCAPED;

245

247

248

249

251 continue;

252

253

254

256 if (II->getIntrinsicID() == Intrinsic::stackrestore)

257 continue;

258

259

260

265

267

268

269

270

271

272

273

274 bool SafeToTail = true;

275 for (auto &Arg : CI->args()) {

277 continue;

279 if (->hasByValAttr())

280 continue;

281 SafeToTail = false;

282 break;

283 }

284 if (SafeToTail) {

285 using namespace ore;

286 ORE->emit([&]() {

288 << "marked as tail call candidate (readnone)";

289 });

292 continue;

293 }

294 }

295

296 if (!IsNoTail && Escaped == UNESCAPED && !Tracker.AllocaUsers.count(CI))

298 }

299

300 for (auto *SuccBB : successors(BB)) {

301 auto &State = Visited[SuccBB];

302 if (State < Escaped) {

303 State = Escaped;

304 if (State == ESCAPED)

305 WorklistEscaped.push_back(SuccBB);

306 else

307 WorklistUnescaped.push_back(SuccBB);

308 }

309 }

310

311 if (!WorklistEscaped.empty()) {

313 Escaped = ESCAPED;

314 } else {

315 BB = nullptr;

316 while (!WorklistUnescaped.empty()) {

317 auto *NextBB = WorklistUnescaped.pop_back_val();

318 if (Visited[NextBB] == UNESCAPED) {

319 BB = NextBB;

320 Escaped = UNESCAPED;

321 break;

322 }

323 }

324 }

325 } while (BB);

326

327 for (CallInst *CI : DeferredTails) {

328 if (Visited[CI->getParent()] != ESCAPED) {

329

330

331 LLVM_DEBUG(dbgs() << "Marked as tail call candidate: " << *CI << "\n");

332 CI->setTailCall();

334 }

335 }

336

338}

339

340

341

342

343

346 if (II->getIntrinsicID() == Intrinsic::lifetime_end)

347 return true;

348

349

350

351 if (I->mayHaveSideEffects())

352 return false;

353

355

357

358

359

360

364 L->getAlign(), DL, L))

365 return false;

366 }

367 }

368

369

370

371

372

373

375}

376

378 if (->isAssociative() || ->isCommutative())

379 return false;

380

381 assert(I->getNumOperands() >= 2 &&

382 "Associative/commutative operations should have at least 2 args!");

383

385

387 return false;

388 }

389

390

391 if ((I->getOperand(0) == CI && I->getOperand(1) == CI) ||

392 (I->getOperand(0) != CI && I->getOperand(1) != CI))

393 return false;

394

395

397 return false;

398

399 return true;

400}

401

402namespace {

403class TailRecursionEliminator {

405 const TargetTransformInfo *TTI;

407 OptimizationRemarkEmitter *ORE;

408 DomTreeUpdater &DTU;

409 BlockFrequencyInfo *const BFI;

410 const uint64_t OrigEntryBBFreq;

411 const uint64_t OrigEntryCount;

412

413

414

415

418

419

420 PHINode *RetPN = nullptr;

421

422

423 PHINode *RetKnownPN = nullptr;

424

425

426

428

429

430

431

432

433

434 PHINode *AccPN = nullptr;

435

436

437 Instruction *AccumulatorRecursionInstr = nullptr;

438

439 TailRecursionEliminator(Function &F, const TargetTransformInfo *TTI,

440 AliasAnalysis *AA, OptimizationRemarkEmitter *ORE,

441 DomTreeUpdater &DTU, BlockFrequencyInfo *BFI)

442 : F(F), TTI(TTI), AA(AA), ORE(ORE), DTU(DTU), BFI(BFI),

443 OrigEntryBBFreq(

444 BFI ? BFI->getBlockFreq(&F.getEntryBlock()).getFrequency() : 0U),

445 OrigEntryCount(F.getEntryCount() ? F.getEntryCount()->getCount() : 0) {

446 if (BFI) {

447

448 assert((OrigEntryCount != 0 && OrigEntryBBFreq != 0) &&

449 "If a BFI was provided, the function should have both an entry "

450 "count that is non-zero and an entry basic block with a non-zero "

451 "frequency.");

452 }

453 }

454

455 CallInst *findTRECandidate(BasicBlock *BB);

456

457 void createTailRecurseLoopHeader(CallInst *CI);

458

459 void insertAccumulator(Instruction *AccRecInstr);

460

461 bool eliminateCall(CallInst *CI);

462

463 void cleanupAndFinalize();

464

465 bool processBlock(BasicBlock &BB);

466

467 void copyByValueOperandIntoLocalTemp(CallInst *CI, int OpndIdx);

468

469 void copyLocalTempOfByValueOperandIntoArguments(CallInst *CI, int OpndIdx);

470

471public:

472 static bool eliminate(Function &F, const TargetTransformInfo *TTI,

473 AliasAnalysis *AA, OptimizationRemarkEmitter *ORE,

474 DomTreeUpdater &DTU, BlockFrequencyInfo *BFI);

475};

476}

477

480

481 if (&BB->front() == TI)

482 return nullptr;

483

484

485

486 CallInst *CI = nullptr;

488 while (true) {

491 break;

492

493 if (BBI == BB->begin())

494 return nullptr;

495 --BBI;

496 }

497

499 "Incompatible call site attributes(Tail,NoTail)");

501 return nullptr;

502

503

504

505

506

507 if (BB == &F.getEntryBlock() && &BB->front() == CI &&

510

511

514 for (; I != E && FI != FE; ++I, ++FI)

515 if (*I != &*FI) break;

516 if (I == E && FI == FE)

517 return nullptr;

518 }

519

520 return CI;

521}

522

523void TailRecursionEliminator::createTailRecurseLoopHeader(CallInst *CI) {

524 HeaderBB = &F.getEntryBlock();

526 NewEntry->takeName(HeaderBB);

527 HeaderBB->setName("tailrecurse");

530

531

532

533

534

536 NEBI = NewEntry->begin();

537 OEBI != E;)

540 AI->moveBefore(NEBI);

541

542

543

544

545

548 PHINode *PN = PHINode::Create(I->getType(), 2, I->getName() + ".tr");

550 I->replaceAllUsesWith(PN);

553 }

554

555

556

557

558

559 Type *RetType = F.getReturnType();

561 Type *BoolType = Type::getInt1Ty(F.getContext());

564 RetKnownPN = PHINode::Create(BoolType, 2, "ret.known.tr");

566

569 }

570

571

572

573

575}

576

577void TailRecursionEliminator::insertAccumulator(Instruction *AccRecInstr) {

578 assert(!AccPN && "Trying to insert multiple accumulators");

579

580 AccumulatorRecursionInstr = AccRecInstr;

581

582

584 AccPN = PHINode::Create(F.getReturnType(), std::distance(PB, PE) + 1,

585 "accumulator.tr");

587

588

589

590

591

592

593

596 if (P == &F.getEntryBlock()) {

600 } else {

602 }

603 }

604

605 ++NumAccumAdded;

606}

607

608

609

610void TailRecursionEliminator::copyByValueOperandIntoLocalTemp(CallInst *CI,

611 int OpndIdx) {

614 const DataLayout &DL = F.getDataLayout();

615

616

618

619

620

621 Value *NewAlloca = new AllocaInst(

622 AggTy, DL.getAllocaAddrSpace(), nullptr, Alignment,

624

626 Value *Size = Builder.getInt64(DL.getTypeAllocSize(AggTy));

627

628

629 Builder.CreateMemCpy(NewAlloca, Alignment,

631 Alignment, Size);

633}

634

635

636

637void TailRecursionEliminator::copyLocalTempOfByValueOperandIntoArguments(

638 CallInst *CI, int OpndIdx) {

641 const DataLayout &DL = F.getDataLayout();

642

643

645

647 Value *Size = Builder.getInt64(DL.getTypeAllocSize(AggTy));

648

649

650

651 Builder.CreateMemCpy(F.getArg(OpndIdx), Alignment,

653 Alignment, Size);

654}

655

656bool TailRecursionEliminator::eliminateCall(CallInst *CI) {

658

659

660

661

662

665 for (++BBI; &*BBI != Ret; ++BBI) {

667 continue;

668

669

670

671

672

674 return false;

675

676

677

678 AccRecInstr = &*BBI;

679 }

680

682

683 using namespace ore;

684 ORE->emit([&]() {

685 return OptimizationRemark(DEBUG_TYPE, "tailcall-recursion", CI)

686 << "transforming tail recursion into loop";

687 });

688

689

690

691 if (!HeaderBB)

692 createTailRecurseLoopHeader(CI);

693

694

695 for (unsigned I = 0, E = CI->arg_size(); I != E; ++I) {

697 copyByValueOperandIntoLocalTemp(CI, I);

698 }

699

700

701

702

703 for (unsigned I = 0, E = CI->arg_size(); I != E; ++I) {

705 copyLocalTempOfByValueOperandIntoArguments(CI, I);

706

707

708

709

710

711 F.removeParamAttr(I, Attribute::ReadOnly);

712 ArgumentPHIs[I]->addIncoming(F.getArg(I), BB);

713 } else

715 }

716

717 if (AccRecInstr) {

718 insertAccumulator(AccRecInstr);

719

720

721

722

724 }

725

726

727 if (RetPN) {

729

732 } else {

733

734

735

736 SelectInst *SI =

741

744 }

745

746 if (AccPN)

747 AccPN->addIncoming(AccRecInstr ? AccRecInstr : AccPN, BB);

748 }

749

750

751

754

757 DTU.applyUpdates({{DominatorTree::Insert, BB, HeaderBB}});

758 ++NumEliminated;

759 if (OrigEntryBBFreq) {

760 assert(F.getEntryCount().has_value());

761

762

763

764 assert(&F.getEntryBlock() != BB);

765 auto RelativeBBFreq =

766 static_cast<double>(BFI->getBlockFreq(BB).getFrequency()) /

767 static_cast<double>(OrigEntryBBFreq);

768 auto ToSubtract =

769 static_cast<uint64_t>(std::round(RelativeBBFreq * OrigEntryCount));

770 auto OldEntryCount = F.getEntryCount()->getCount();

771 if (OldEntryCount <= ToSubtract) {

773 errs() << "[TRE] The entrycount attributable to the recursive call, "

774 << ToSubtract

775 << ", should be strictly lower than the function entry count, "

776 << OldEntryCount << "\n");

777 } else {

778 F.setEntryCount(OldEntryCount - ToSubtract, F.getEntryCount()->getType());

779 }

780 }

781 return true;

782}

783

784void TailRecursionEliminator::cleanupAndFinalize() {

785

786

787

788

789

790 for (PHINode *PN : ArgumentPHIs) {

791

795 }

796 }

797

798 if (RetPN) {

799 if (RetSelects.empty()) {

800

801

804

807

808 if (AccPN) {

809

810

811 Instruction *AccRecInstr = AccumulatorRecursionInstr;

812 for (BasicBlock &BB : F) {

814 if (!RI)

815 continue;

816

818 AccRecInstrNew->setName("accumulator.ret.tr");

824 }

825 }

826 } else {

827

828

829 for (BasicBlock &BB : F) {

831 if (!RI)

832 continue;

833

834 SelectInst *SI =

840 }

841

842 if (AccPN) {

843

844

845 Instruction *AccRecInstr = AccumulatorRecursionInstr;

846 for (SelectInst *SI : RetSelects) {

848 AccRecInstrNew->setName("accumulator.ret.tr");

850 SI->getFalseValue());

853 SI->setFalseValue(AccRecInstrNew);

854 }

855 }

856 }

857 }

858}

859

860bool TailRecursionEliminator::processBlock(BasicBlock &BB) {

862

864 if (BI->isConditional())

865 return false;

866

867 BasicBlock *Succ = BI->getSuccessor(0);

869

870 if (!Ret)

871 return false;

872

873 CallInst *CI = findTRECandidate(&BB);

874

875 if (!CI)

876 return false;

877

879 << "INTO UNCOND BRANCH PRED: " << BB);

881 ++NumRetDuped;

882

883

884

885

886

887

890

891 eliminateCall(CI);

892 return true;

894 CallInst *CI = findTRECandidate(&BB);

895

896 if (CI)

897 return eliminateCall(CI);

898 }

899

900 return false;

901}

902

903bool TailRecursionEliminator::eliminate(Function &F,

904 const TargetTransformInfo *TTI,

906 OptimizationRemarkEmitter *ORE,

907 DomTreeUpdater &DTU,

908 BlockFrequencyInfo *BFI) {

909 if (F.getFnAttribute("disable-tail-calls").getValueAsBool())

910 return false;

911

912 bool MadeChange = false;

914

915

916

917 if (F.getFunctionType()->isVarArg())

918 return MadeChange;

919

921 return MadeChange;

922

923

924 TailRecursionEliminator TRE(F, TTI, AA, ORE, DTU, BFI);

925

926 for (BasicBlock &BB : F)

927 MadeChange |= TRE.processBlock(BB);

928

929 TRE.cleanupAndFinalize();

930

931 return MadeChange;

932}

933

934namespace {

935struct TailCallElim : public FunctionPass {

936 static char ID;

937 TailCallElim() : FunctionPass(ID) {

939 }

940

941 void getAnalysisUsage(AnalysisUsage &AU) const override {

942 AU.addRequired();

944 AU.addRequired();

947 AU.addPreserved();

948 }

949

951 if (skipFunction(F))

952 return false;

953

954 auto *DTWP = getAnalysisIfAvailable();

955 auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;

956 auto *PDTWP = getAnalysisIfAvailable();

957 auto *PDT = PDTWP ? &PDTWP->getPostDomTree() : nullptr;

958

959

960

961 DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Eager);

962

963 return TailRecursionEliminator::eliminate(

964 F, &getAnalysis().getTTI(F),

965 &getAnalysis().getAAResults(),

966 &getAnalysis().getORE(), DTU,

967 nullptr);

968 }

969};

970}

971

972char TailCallElim::ID = 0;

974 false, false)

979

980

982 return new TailCallElim();

983}

984

987

990

991

992

993 auto *BFI = ( ForceDisableBFI && UpdateFunctionEntryCount &&

994 F.getEntryCount().has_value() && F.getEntryCount()->getCount())

996 : nullptr;

1000

1001

1002

1003 DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Eager);

1005 TailRecursionEliminator::eliminate(F, &TTI, &AA, &ORE, DTU, BFI);

1006

1012 return PA;

1013}

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

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

Expand Atomic instructions

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

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

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

static bool runOnFunction(Function &F, bool PostInlining)

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

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

Module.h This file contains the declarations for the Module class.

uint64_t IntrinsicInst * II

PassBuilder PB(Machine, PassOpts->PTO, std::nullopt, &PIC)

#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 'Statistic' class, which is designed to be an easy way to expose various metric...

#define STATISTIC(VARNAME, DESC)

static cl::opt< bool > ForceDisableBFI("tre-disable-entrycount-recompute", cl::init(false), cl::Hidden, cl::desc("Force disabling recomputing of function entry count, on " "successful tail recursion elimination."))

static bool canTRE(Function &F)

Scan the specified function for alloca instructions.

Definition TailRecursionElimination.cpp:100

static bool canMoveAboveCall(Instruction *I, CallInst *CI, AliasAnalysis *AA)

Return true if it is safe to move the specified instruction from after the call to before the call,...

Definition TailRecursionElimination.cpp:344

static bool canTransformAccumulatorRecursion(Instruction *I, CallInst *CI)

Definition TailRecursionElimination.cpp:377

static bool markTails(Function &F, OptimizationRemarkEmitter *ORE)

Definition TailRecursionElimination.cpp:197

This pass exposes codegen information to IR-level passes.

A manager for alias analyses.

an instruction to allocate memory on the stack

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

AnalysisUsage & addPreserved()

Add the specified Pass class to the set of analyses preserved by this pass.

This class represents an incoming formal argument to a Function.

LLVM Basic Block Representation.

iterator begin()

Instruction iterator methods.

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 InstListType::const_iterator getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const

Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...

const Instruction & front() const

InstListType::iterator iterator

Instruction iterators...

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

Analysis pass which computes BlockFrequencyInfo.

LLVM_ABI BlockFrequency getBlockFreq(const BasicBlock *BB) const

getblockFreq - Return block frequency.

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

Function * getCalledFunction() const

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

bool doesNotAccessMemory(unsigned OpNo) const

User::op_iterator arg_begin()

Return the iterator pointing to the beginning of the argument list.

bool isByValArgument(unsigned ArgNo) const

Determine whether this argument is passed by value.

MaybeAlign getParamAlign(unsigned ArgNo) const

Extract the alignment for a call or parameter (0=unknown).

bool onlyReadsMemory(unsigned OpNo) const

Type * getParamByValType(unsigned ArgNo) const

Extract the byval type for a call or parameter.

bool hasOperandBundlesOtherThan(ArrayRef< uint32_t > IDs) const

Return true if this operand bundle user contains operand bundles with tags other than those specified...

Value * getArgOperand(unsigned i) const

void setArgOperand(unsigned i, Value *v)

User::op_iterator arg_end()

Return the iterator pointing to the end of the argument list.

iterator_range< User::op_iterator > args()

Iteration adapter for range-for loops.

unsigned arg_size() const

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

bool isNoTailCall() const

void setTailCall(bool IsTc=true)

static LLVM_ABI Constant * getIdentity(Instruction *I, Type *Ty, bool AllowRHSConstant=false, bool NSZ=false)

Return the identity constant for a binary or intrinsic Instruction.

static LLVM_ABI Constant * getIntrinsicIdentity(Intrinsic::ID, Type *Ty)

static LLVM_ABI ConstantInt * getTrue(LLVMContext &Context)

static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)

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

static DebugLoc getCompilerGenerated()

LLVM_ABI void deleteBB(BasicBlock *DelBB)

Delete DelBB.

Analysis pass which computes a DominatorTree.

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

void applyUpdates(ArrayRef< UpdateT > Updates)

Submit updates to all available trees.

void recalculate(FuncT &F)

Notify DTU that the entry block was replaced.

LLVM_ABI Instruction * clone() const

Create a copy of 'this' instruction that is identical in all ways except the following:

LLVM_ABI void dropLocation()

Drop the instruction's debug location.

const DebugLoc & getDebugLoc() const

Return the debug location for this node as a DebugLoc.

LLVM_ABI void insertBefore(InstListType::iterator InsertPos)

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

LLVM_ABI InstListType::iterator eraseFromParent()

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

LLVM_ABI bool mayHaveSideEffects() const LLVM_READONLY

Return true if the instruction may have side effects.

void setDebugLoc(DebugLoc Loc)

Set the debug location information for this instruction.

A wrapper class for inspecting calls to intrinsic functions.

@ OB_clang_arc_attachedcall

An instruction for reading from memory.

static LLVM_ABI MemoryLocation get(const LoadInst *LI)

Return a location with information about the memory reference by the given instruction.

void addIncoming(Value *V, BasicBlock *BB)

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

static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)

Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...

static LLVM_ABI PassRegistry * getPassRegistry()

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

static LLVM_ABI PoisonValue * get(Type *T)

Static factory methods - Return an 'poison' object of the specified type.

Analysis pass which computes a PostDominatorTree.

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

Mark an analysis as preserved.

Value * getReturnValue() const

Convenience accessor. Returns null if there is no return value.

static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", InsertPosition InsertBefore=nullptr, const Instruction *MDFrom=nullptr)

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

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

void push_back(const T &Elt)

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

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Definition TailRecursionElimination.cpp:985

Analysis pass providing the TargetTransformInfo.

Wrapper pass for TargetTransformInfo.

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

LLVM_ABI bool isLoweredToCall(const Function *F) const

Test whether calls to a function lower to actual program function calls.

bool isVoidTy() const

Return true if this is 'void'.

void dropAllReferences()

Drop all references to operands.

void setOperand(unsigned i, Value *Val)

Value * getOperand(unsigned i) const

Type * getType() const

All values are typed, get the type of this value.

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.

LLVM_ABI StringRef getName() const

Return a constant reference to the value's name.

LLVM_ABI void takeName(Value *V)

Transfer the name from V to this value.

const ParentTy * getParent() const

self_iterator getIterator()

Abstract Attribute helper functions.

constexpr char Align[]

Key for Kernel::Arg::Metadata::mAlign.

unsigned ID

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

@ BasicBlock

Various leaf nodes.

initializer< Ty > init(const Ty &Val)

Add a small namespace to avoid name clashes with the classes used in the streaming interface.

NodeAddr< UseNode * > Use

friend class Instruction

Iterator for Instructions in a `BasicBlock.

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.

LLVM_ABI FunctionPass * createTailCallEliminationPass()

Definition TailRecursionElimination.cpp:981

auto pred_end(const MachineBasicBlock *BB)

decltype(auto) dyn_cast(const From &Val)

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

auto successors(const MachineBasicBlock *BB)

LLVM_ABI ReturnInst * FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB, BasicBlock *Pred, DomTreeUpdater *DTU=nullptr)

This method duplicates the specified return instruction into a predecessor which ends in an unconditi...

LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)

See if we can compute a simplified version of this instruction.

bool isModSet(const ModRefInfo MRI)

LLVM_ABI bool isSafeToLoadUnconditionally(Value *V, Align Alignment, const APInt &Size, const DataLayout &DL, Instruction *ScanFrom, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)

Return true if we know that executing a load from this value cannot trap.

LLVM_ABI raw_ostream & dbgs()

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

class LLVM_GSL_OWNER SmallVector

Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...

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_ABI raw_fd_ostream & errs()

This returns a reference to a raw_ostream for standard error.

IRBuilder(LLVMContext &, FolderTy, InserterTy, MDNode *, ArrayRef< OperandBundleDef >) -> IRBuilder< FolderTy, InserterTy >

PredIterator< BasicBlock, Value::user_iterator > pred_iterator

auto pred_begin(const MachineBasicBlock *BB)

decltype(auto) cast(const From &Val)

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

bool is_contained(R &&Range, const E &Element)

Returns true if Element is found in Range.

bool pred_empty(const BasicBlock *BB)

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

LLVM_ABI void initializeTailCallElimPass(PassRegistry &)

AAResults AliasAnalysis

Temporary typedef for legacy code that uses a generic AliasAnalysis pointer or reference.

Align valueOrOne() const

For convenience, returns a valid alignment or 1 if undefined.