PredicateInfo.cpp Source File (original) (raw)

28#define DEBUG_TYPE "predicateinfo"

29using namespace llvm;

34 cl::desc("Verify PredicateInfo in legacy printer pass."));

36 "Controls which variables are renamed with predicateinfo");

42namespace {

47 "Only branches and switches should have PHIOnly defs that "

48 "require branch blocks.");

50}

56 "Not a predicate info type we know how to get a terminator from.");

58}

62std::pair<BasicBlock *, BasicBlock *> getBlockEdge(const PredicateBase *PB) {

64 "Not a predicate info type we know how to get an edge from.");

66 return std::make_pair(PEdge->From, PEdge->To);

67}

68}

70namespace llvm {

99 if (&A == &B)

100 return false;

101

102

103 if (A.DFSIn != B.DFSIn)

104 return A.DFSIn < B.DFSIn;

105 assert(A.DFSOut == B.DFSOut &&

106 "Equal DFS-in numbers imply equal out numbers");

107

108

109 if (A.LocalNum != B.LocalNum)

110 return A.LocalNum < B.LocalNum;

111

112

113

114

115

118

119

122

123

124

126 assert(A.PInfo && B.PInfo && "Must be predicate info def");

127 return false;

128 }

129

130

132 if (VD.U) {

134 return std::make_pair(PHI->getIncomingBlock(*VD.U), PHI->getParent());

135 }

136

137 return ::getBlockEdge(VD.PInfo);

138 }

139

140

142 BasicBlock *ASrc, *ADest, *BSrc, *BDest;

145

146#ifndef NDEBUG

147

151 "DFS numbers for A should match the ones of the source block");

153 "DFS numbers for B should match the ones of the source block");

154 assert(A.DFSIn == B.DFSIn && "Values must be in the same block");

155#endif

156 (void)ASrc;

157 (void)BSrc;

158

159

160

165 bool isAUse = A.U;

166 bool isBUse = B.U;

167 assert((.PInfo || .U) && (.PInfo || .U) &&

168 "Def and U cannot be set at the same time");

169

170 return std::tie(AIn, isAUse) < std::tie(BIn, isBUse);

171 }

172

174 if (VD.U)

176

177

178

179 assert(VD.PInfo && "No use, and no predicateinfo should not occur");

181 "Middle of block should only occur for assumes");

183 }

184

185

186

192};

193

195

196 struct ValueInfo {

198 };

199

204

205

206

207

209

210

211

212

214

216

217 ValueInfo &getOrCreateValueInfo(Value *);

218 const ValueInfo &getValueInfo(Value *) const;

219

229

230 struct StackEntry {

232 Value *Def = nullptr;

233

234 StackEntry(const ValueDFS *V) : V(V) {}

235 };

236

239 Value *materializeStack(unsigned int &, ValueDFSStack &, Value *);

240 bool stackIsInScope(const ValueDFSStack &, const ValueDFS &) const;

241 void popStackUntilDFSScope(ValueDFSStack &, const ValueDFS &);

242

243public:

246 : PI(PI), F(F), DT(DT), AC(AC), Allocator(Allocator) {

247

248 ValueInfos.resize(1);

249 }

250

252};

253

254bool PredicateInfoBuilder::stackIsInScope(const ValueDFSStack &Stack,

255 const ValueDFS &VDUse) const {

256 assert(!Stack.empty() && "Should not be called with empty stack");

257

258

259

260

261

262 const ValueDFS &Top = *Stack.back().V;

263 assert(Top.PInfo && "RenameStack should only contain predicate infos (defs)");

265 if (!VDUse.U) {

266 assert(VDUse.PInfo && "A non-use VDUse should have a predicate info");

267

269

270

271 getBlockEdge(Top.PInfo) == getBlockEdge(VDUse.PInfo);

272 }

274 if ( PHI )

275 return false;

276

277 BasicBlock *EdgePred = PHI->getIncomingBlock(*VDUse.U);

278 if (EdgePred != getBranchBlock(Top.PInfo))

279 return false;

280

281

282 return DT.dominates(getBlockEdge(Top.PInfo), *VDUse.U);

283 }

284

286}

287

288void PredicateInfoBuilder::popStackUntilDFSScope(ValueDFSStack &Stack,

290 while ( Stack .empty() && !stackIsInScope(Stack, VD))

291 Stack.pop_back();

292}

293

294

295

296void PredicateInfoBuilder::convertUsesToDFSOrdered(

298 for (auto &U : Op->uses()) {

300

301

302 if (I->isLifetimeStartOrEnd())

303 continue;

304

305 ValueDFS VD;

306

309 IBlock = PN->getIncomingBlock(U);

310

311

313 } else {

314

315

318 }

319 DomTreeNode *DomNode = DT.getNode(IBlock);

320

321 if (!DomNode)

322 continue;

325 VD.U = &U;

327 }

328 }

329}

330

337

338

339

341 auto *Op0 = Comparison->getOperand(0);

342 auto *Op1 = Comparison->getOperand(1);

343 if (Op0 == Op1)

344 return;

345

348}

349

350

353 auto &OperandInfo = getOrCreateValueInfo(Op);

354 if (OperandInfo.Infos.empty())

356 OperandInfo.Infos.push_back(PB);

357}

358

359

360

361void PredicateInfoBuilder::processAssume(

365 SmallPtrSet<Value *, 4> Visited;

367 while (!Worklist.empty()) {

370 continue;

372 break;

373

374 Value *Op0, *Op1;

378 }

379

386

387 for (Value *V : Values) {

389 auto *PA = new (Allocator) PredicateAssume(V, II, Cond);

390 addInfoFor(OpsToRename, V, PA);

391 }

392 }

393 }

394}

395

396

397

398void PredicateInfoBuilder::processBranch(

403

404 for (BasicBlock *Succ : {FirstBB, SecondBB}) {

405 bool TakenEdge = Succ == FirstBB;

406

407

408 if (Succ == BranchBB)

409 continue;

410

412 SmallPtrSet<Value *, 4> Visited;

414 while (!Worklist.empty()) {

417 continue;

419 break;

420

421 Value *Op0, *Op1;

426 }

427

434

435 for (Value *V : Values) {

437 PredicateBase *PB = new (Allocator)

438 PredicateBranch(V, BranchBB, Succ, Cond, TakenEdge);

439 addInfoFor(OpsToRename, V, PB);

440 }

441 }

442 }

443 }

444}

445

446

447void PredicateInfoBuilder::processSwitch(

452 return;

453

454

455 SmallDenseMap<BasicBlock *, unsigned, 16> SwitchEdges;

456 for (BasicBlock *TargetBlock : successors(BranchBB))

457 ++SwitchEdges[TargetBlock];

458

459

460 for (auto C : SI->cases()) {

461 BasicBlock *TargetBlock = C.getCaseSuccessor();

462 if (SwitchEdges.lookup(TargetBlock) == 1) {

463 PredicateSwitch *PS = new (Allocator) PredicateSwitch(

464 Op, SI->getParent(), TargetBlock, C.getCaseValue(), SI);

465 addInfoFor(OpsToRename, Op, PS);

466 }

467 }

468}

469

470

472 DT.updateDFSNumbers();

473

474

477 if (!DT.isReachableFromEntry(&BB))

478 continue;

479

482 continue;

483

485 continue;

486 processBranch(BI, &BB, OpsToRename);

488 processSwitch(SI, &BB, OpsToRename);

489 }

490 }

491 for (auto &Assume : AC.assumptions()) {

493 if (DT.isReachableFromEntry(II->getParent()))

494 processAssume(II, II->getParent(), OpsToRename);

495 }

496

497 renameUses(OpsToRename);

498}

499

500

501

502Value *PredicateInfoBuilder::materializeStack(unsigned int &Counter,

503 ValueDFSStack &RenameStack,

505

506 auto RevIter = RenameStack.rbegin();

507 for (; RevIter != RenameStack.rend(); ++RevIter)

508 if (RevIter->Def)

509 break;

510

511 size_t Start = RevIter - RenameStack.rbegin();

512

513

514

515 for (auto RenameIter = RenameStack.end() - Start;

516 RenameIter != RenameStack.end(); ++RenameIter) {

517 auto *Op =

518 RenameIter == RenameStack.begin() ? OrigOp : (RenameIter - 1)->Def;

519 StackEntry &Result = *RenameIter;

520 auto *ValInfo = Result.V->PInfo;

521 ValInfo->RenamedOp = (RenameStack.end() - Start) == RenameStack.begin()

522 ? OrigOp

523 : (RenameStack.end() - Start - 1)->Def;

525 const Twine &Name = "") {

526

528 };

529

530

531

532

533

535 BitCastInst *PIC = CreateSSACopy(getBranchTerminator(ValInfo), Op,

536 Op->getName() + "." + Twine(Counter++));

537 PI.PredicateMap.insert({PIC, ValInfo});

539 } else {

542 "Should not have gotten here without it being an assume");

543

544

545 BitCastInst *PIC = CreateSSACopy(PAssume->AssumeInst->getNextNode(), Op);

546 PI.PredicateMap.insert({PIC, ValInfo});

548 }

549 }

550 return RenameStack.back().Def;

551}

552

553

554

555

556

557

558

559

560

561

562

563

564

565

566

567

568

569

570

571

573 ValueDFS_Compare Compare(DT);

574

575 for (auto *Op : OpsToRename) {

577 unsigned Counter = 0;

579 const auto &ValueInfo = getValueInfo(Op);

580

581

582

583 for (const auto &PossibleCopy : ValueInfo.Infos) {

584 ValueDFS VD;

585

586

587

588

589

592 DomTreeNode *DomNode = DT.getNode(PAssume->AssumeInst->getParent());

593 if (!DomNode)

594 continue;

597 VD.PInfo = PossibleCopy;

600

601

602

603 auto BlockEdge = getBlockEdge(PossibleCopy);

604 if (!BlockEdge.second->getSinglePredecessor()) {

606 auto *DomNode = DT.getNode(BlockEdge.first);

607 if (DomNode) {

610 VD.PInfo = PossibleCopy;

612 }

613 } else {

614

615

616

618 auto *DomNode = DT.getNode(BlockEdge.second);

619 if (DomNode) {

622 VD.PInfo = PossibleCopy;

624 }

625 }

626 }

627 }

628

629 convertUsesToDFSOrdered(Op, OrderedUses);

630

631

632

633

634

637

638

639 for (const ValueDFS &VD : OrderedUses) {

640

641

642 if (RenameStack.empty()) {

644 } else {

645 LLVM_DEBUG(dbgs() << "Rename Stack Top DFS numbers are ("

646 << RenameStack.back().V->DFSIn << ","

647 << RenameStack.back().V->DFSOut << ")\n");

648 }

649

651 << VD.DFSOut << ")\n");

652

653

654 popStackUntilDFSScope(RenameStack, VD);

655

658 continue;

659 }

660

661

662

663 if (RenameStack.empty())

664 continue;

666 LLVM_DEBUG(dbgs() << "Skipping execution due to debug counter\n");

667 continue;

668 }

669 StackEntry &Result = RenameStack.back();

670

671

672

673

675 Result.Def = materializeStack(Counter, RenameStack, Op);

676

678 << *VD.U->get() << " in " << *(VD.U->getUser())

679 << "\n");

681 "Predicateinfo def should have dominated this use");

683 }

684 }

685}

686

687PredicateInfoBuilder::ValueInfo &

688PredicateInfoBuilder::getOrCreateValueInfo(Value *Operand) {

689 auto Res = ValueInfoNums.try_emplace(Operand, ValueInfos.size());

690 if (Res.second) {

691

692 ValueInfos.resize(ValueInfos.size() + 1);

693 }

694 return ValueInfos[Res.first->second];

695}

696

697const PredicateInfoBuilder::ValueInfo &

698PredicateInfoBuilder::getValueInfo(Value *Operand) const {

699 auto OINI = ValueInfoNums.lookup(Operand);

700 assert(OINI != 0 && "Operand was not really in the Value Info Numbers");

701 assert(OINI < ValueInfos.size() &&

702 "Value Info Number greater than size of Value Info Table");

703 return ValueInfos[OINI];

704}

705

708 : F(F) {

710 Builder.buildPredicateInfo();

711}

712

714 switch (Type) {

717 bool TrueEdge = true;

719 TrueEdge = PBranch->TrueEdge;

720

725 }

726

730 }

731

733 if (!Cmp) {

734

735 return std::nullopt;

736 }

737

740 if (Cmp->getOperand(0) == RenamedOp) {

741 Pred = Cmp->getPredicate();

742 OtherOp = Cmp->getOperand(1);

743 } else if (Cmp->getOperand(1) == RenamedOp) {

744 Pred = Cmp->getSwappedPredicate();

745 OtherOp = Cmp->getOperand(0);

746 } else {

747

748 return std::nullopt;

749 }

750

751

752 if (!TrueEdge)

754

755 return {{Pred, OtherOp}};

756 }

759

760 return std::nullopt;

761 }

762

764 }

766}

767

769

770

773 const auto *PI = PredInfo.getPredicateInfoFor(&Inst);

774 if (!PI)

775 continue;

776

778 Inst.getType() == Inst.getOperand(0)->getType());

779 Inst.replaceAllUsesWith(Inst.getOperand(0));

780 Inst.eraseFromParent();

781 }

782}

783

788 OS << "PredicateInfo for function: " << F.getName() << "\n";

790 auto PredInfo = std::make_unique(F, DT, AC, Allocator);

791 PredInfo->print(OS);

792

795}

796

797

798

802

803public:

805

808

811 if (const auto *PI = PredInfo->getPredicateInfoFor(I)) {

813 OS << "; branch predicate info { TrueEdge: " << PB->TrueEdge

814 << " Comparison:" << *PB->Condition << " Edge: [";

815 PB->From->printAsOperand(OS);

816 OS << ",";

817 PB->To->printAsOperand(OS);

818 OS << "]";

820 OS << "; switch predicate info { CaseValue: " << *PS->CaseValue

821 << " Edge: [";

822 PS->From->printAsOperand(OS);

823 OS << ",";

824 PS->To->printAsOperand(OS);

825 OS << "]";

827 OS << "; assume predicate info {"

828 << " Comparison:" << *PA->Condition;

829 }

830 OS << ", RenamedOp: ";

831 PI->RenamedOp->printAsOperand(OS, false);

832 OS << " }\n";

833 }

834 }

835};

836

839 F.print(OS, &Writer);

840}

841

844 F.print(dbgs(), &Writer);

845}

846

852 std::make_unique(F, DT, AC, Allocator)->verifyPredicateInfo();

853

855}

856}

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

Expand Atomic instructions

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

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

This file provides an implementation of debug counters.

#define DEBUG_COUNTER(VARNAME, COUNTERNAME, DESC)

This file defines the DenseMap class.

uint64_t IntrinsicInst * II

PassInstrumentationCallbacks PIC

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

static cl::opt< bool > VerifyPredicateInfo("verify-predicateinfo", cl::init(false), cl::Hidden, cl::desc("Verify PredicateInfo in legacy printer pass."))

static const unsigned MaxCondsPerBranch

Definition PredicateInfo.cpp:40

This file implements the PredicateInfo analysis, which creates an Extended SSA form for operations us...

const SmallVectorImpl< MachineOperand > & Cond

This file defines the SmallPtrSet class.

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

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

A function analysis which provides an AssumptionCache.

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

LLVM Basic Block Representation.

const Function * getParent() const

Return the enclosing method, or null if none.

This class represents a no-op cast from one type to another.

Conditional or Unconditional Branch instruction.

bool isConditional() const

BasicBlock * getSuccessor(unsigned i) const

Value * getCondition() const

This class is the base class for the comparison instructions.

Predicate

This enumeration lists the possible predicates for CmpInst subclasses.

Predicate getInversePredicate() const

For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...

static LLVM_ABI ConstantInt * getTrue(LLVMContext &Context)

static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)

static LLVM_ABI Constant * getNullValue(Type *Ty)

Constructor to create a '0' constant of arbitrary type.

static bool shouldExecute(CounterInfo &Counter)

ValueT lookup(const_arg_type_t< KeyT > Val) const

lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...

unsigned getDFSNumIn() const

getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes in the dominator tree.

unsigned getDFSNumOut() const

Analysis pass which computes a DominatorTree.

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

LLVM_ABI bool comesBefore(const Instruction *Other) const

Given an instruction Other in the same basic block as this instruction, return true if this instructi...

A wrapper class for inspecting calls to intrinsic functions.

LLVM_ABI std::optional< PredicateConstraint > getConstraint() const

Fetch condition in the form of PredicateConstraint, if possible.

Definition PredicateInfo.cpp:713

PredicateInfoAnnotatedWriter(const PredicateInfo *M)

Definition PredicateInfo.cpp:804

void emitInstructionAnnot(const Instruction *I, formatted_raw_ostream &OS) override

emitInstructionAnnot - This may be implemented to emit a string right before an instruction is emitte...

Definition PredicateInfo.cpp:809

friend class PredicateInfo

Definition PredicateInfo.cpp:800

void emitBasicBlockStartAnnot(const BasicBlock *BB, formatted_raw_ostream &OS) override

emitBasicBlockStartAnnot - This may be implemented to emit a string right after the basic block label...

Definition PredicateInfo.cpp:806

PredicateInfoBuilder(PredicateInfo &PI, Function &F, DominatorTree &DT, AssumptionCache &AC, BumpPtrAllocator &Allocator)

Definition PredicateInfo.cpp:244

void buildPredicateInfo()

Definition PredicateInfo.cpp:471

LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Definition PredicateInfo.cpp:784

Encapsulates PredicateInfo, including all data associated with memory accesses.

friend class PredicateInfoAnnotatedWriter

LLVM_ABI void verifyPredicateInfo() const

Definition PredicateInfo.cpp:768

friend class PredicateInfoBuilder

LLVM_ABI void print(raw_ostream &) const

Definition PredicateInfo.cpp:837

LLVM_ABI PredicateInfo(Function &, DominatorTree &, AssumptionCache &, BumpPtrAllocator &)

Definition PredicateInfo.cpp:706

LLVM_ABI void dump() const

Definition PredicateInfo.cpp:842

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.

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

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

This class consists of common code factored out of the SmallVector class to reduce code duplication b...

void push_back(const T &Elt)

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

Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...

A Use represents the edge between a Value definition and its users.

LLVM Value Representation.

formatted_raw_ostream - A raw_ostream that wraps another one and keeps track of line and column posit...

self_iterator getIterator()

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

#define llvm_unreachable(msg)

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

@ C

The default llvm calling convention, compatible with C.

@ BasicBlock

Various leaf nodes.

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

specificval_ty m_Specific(const Value *V)

Match if we have a specific specified value.

auto m_LogicalOr()

Matches L || R where L and R are arbitrary values.

NoWrapTrunc_match< OpTy, TruncInst::NoUnsignedWrap > m_NUWTrunc(const OpTy &Op)

Matches trunc nuw.

class_match< Value > m_Value()

Match an arbitrary value and ignore it.

auto m_LogicalAnd()

Matches L && R where L and R are arbitrary values.

initializer< Ty > init(const Ty &Val)

This is an optimization pass for GlobalISel generic memory operations.

FunctionAddr VTableAddr Value

void stable_sort(R &&Range)

void collectCmpOps(CmpInst *Comparison, SmallVectorImpl< Value * > &CmpOperands)

Definition PredicateInfo.cpp:340

decltype(auto) dyn_cast(const From &Val)

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

auto successors(const MachineBasicBlock *BB)

static void replaceCreatedSSACopys(PredicateInfo &PredInfo, Function &F)

Definition PredicateInfo.cpp:771

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

bool shouldRename(Value *V)

Definition PredicateInfo.cpp:331

DomTreeNodeBase< BasicBlock > DomTreeNode

auto dyn_cast_or_null(const Y &Val)

LLVM_ABI raw_ostream & dbgs()

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

LocalNum

Definition PredicateInfo.cpp:71

@ LN_First

Definition PredicateInfo.cpp:73

@ LN_Last

Definition PredicateInfo.cpp:78

@ LN_Middle

Definition PredicateInfo.cpp:76

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

DWARFExpression::Operation Op

decltype(auto) cast(const From &Val)

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

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

BumpPtrAllocatorImpl<> BumpPtrAllocator

The standard BumpPtrAllocator which just uses the default template parameters.

LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Definition PredicateInfo.cpp:847

std::pair< BasicBlock *, BasicBlock * > getBlockEdge(const ValueDFS &VD) const

Definition PredicateInfo.cpp:131

bool operator()(const ValueDFS &A, const ValueDFS &B) const

Definition PredicateInfo.cpp:98

const Instruction * getDefOrUser(const ValueDFS &VD) const

Definition PredicateInfo.cpp:173

bool comparePHIRelated(const ValueDFS &A, const ValueDFS &B) const

Definition PredicateInfo.cpp:141

ValueDFS_Compare(DominatorTree &DT)

Definition PredicateInfo.cpp:96

bool localComesBefore(const ValueDFS &A, const ValueDFS &B) const

Definition PredicateInfo.cpp:187

DominatorTree & DT

Definition PredicateInfo.cpp:95

Definition PredicateInfo.cpp:83

int DFSOut

Definition PredicateInfo.cpp:85

Use * U

Definition PredicateInfo.cpp:88

PredicateBase * PInfo

Definition PredicateInfo.cpp:89

unsigned int LocalNum

Definition PredicateInfo.cpp:86

int DFSIn

Definition PredicateInfo.cpp:84