HexagonCommonGEP.cpp Source File (original) (raw)

42#include

43#include

44#include

45#include

46#include

47#include

48#include

49#include

51#define DEBUG_TYPE "commgep"

53using namespace llvm;

63namespace {

65 struct GepNode;

66 using NodeSet = std::set<GepNode *>;

67 using NodeToValueMap = std::map<GepNode *, Value *>;

68 using NodeVect = std::vector<GepNode *>;

69 using NodeChildrenMap = std::map<GepNode *, NodeVect>;

71 using NodeToUsesMap = std::map<GepNode *, UseSet>;

75 struct NodeOrdering {

76 NodeOrdering() = default;

78 void insert(const GepNode *N) { Map.insert(std::make_pair(N, ++LastNum)); }

79 void clear() { Map.clear(); }

81 bool operator()(const GepNode *N1, const GepNode *N2) const {

82 auto F1 = Map.find(N1), F2 = Map.find(N2);

83 assert(F1 != Map.end() && F2 != Map.end());

84 return F1->second < F2->second;

85 }

87 private:

88 std::map<const GepNode *, unsigned> Map;

89 unsigned LastNum = 0;

90 };

92 class HexagonCommonGEP : public FunctionPass {

93 public:

94 static char ID;

96 HexagonCommonGEP() : FunctionPass(ID) {}

99 StringRef getPassName() const override { return "Hexagon Common GEP"; }

100

101 void getAnalysisUsage(AnalysisUsage &AU) const override {

102 AU.addRequired();

104 AU.addRequired();

105 AU.addPreserved();

108 FunctionPass::getAnalysisUsage(AU);

109 }

110

111 private:

112 using ValueToNodeMap = std::map<Value *, GepNode *>;

113 using ValueVect = std::vector<Value *>;

114 using NodeToValuesMap = std::map<GepNode *, ValueVect>;

115

116 void getBlockTraversalOrder(BasicBlock *Root, ValueVect &Order);

117 bool isHandledGepForm(GetElementPtrInst *GepI);

118 void processGepInst(GetElementPtrInst *GepI, ValueToNodeMap &NM);

119 void collect();

120 void common();

121

122 BasicBlock *recalculatePlacement(GepNode *Node, NodeChildrenMap &NCM,

123 NodeToValueMap &Loc);

124 BasicBlock *recalculatePlacementRec(GepNode *Node, NodeChildrenMap &NCM,

125 NodeToValueMap &Loc);

126 bool isInvariantIn(Value *Val, Loop *L);

127 bool isInvariantIn(GepNode *Node, Loop *L);

128 bool isInMainPath(BasicBlock *B, Loop *L);

129 BasicBlock *adjustForInvariance(GepNode *Node, NodeChildrenMap &NCM,

130 NodeToValueMap &Loc);

131 void separateChainForNode(GepNode *Node, Use *U, NodeToValueMap &Loc);

132 void separateConstantChains(GepNode *Node, NodeChildrenMap &NCM,

133 NodeToValueMap &Loc);

134 void computeNodePlacement(NodeToValueMap &Loc);

135

137 BasicBlock *LocB);

138 void getAllUsersForNode(GepNode *Node, ValueVect &Values,

139 NodeChildrenMap &NCM);

140 void materialize(NodeToValueMap &Loc);

141

142 void removeDeadCode();

143

144 NodeVect Nodes;

145 NodeToUsesMap Uses;

146 NodeOrdering NodeOrder;

147 SpecificBumpPtrAllocator *Mem;

148 LLVMContext *Ctx;

149 LoopInfo *LI;

150 DominatorTree *DT;

151 PostDominatorTree *PDT;

153 };

154

155}

156

157char HexagonCommonGEP::ID = 0;

158

160 false, false)

166

167namespace {

168

170 enum {

177 };

178

179

180

181

182

183

184

185

186

187

188

189

191 union {

194 };

196 Type *PTy = nullptr;

197

198

199

207

209 };

210

212 OS << "{ {";

213 bool Comma = false;

215 OS << "root";

216 Comma = true;

217 }

219 if (Comma)

220 OS << ',';

221 OS << "internal";

222 Comma = true;

223 }

225 if (Comma)

226 OS << ',';

227 OS << "used";

228 }

230 if (Comma)

231 OS << ',';

232 OS << "inbounds";

233 }

235 if (Comma)

236 OS << ',';

237 OS << "pointer";

238 }

239 OS << "} ";

242 else

243 OS << "Parent:" << GN.Parent;

244

245 OS << " Idx:";

247 OS << CI->getValue().getSExtValue();

250 else

251 OS << " =" << *GN.Idx;

252

253 OS << " PTy:";

258 else

259 OS << ":" << *STy;

260 }

261 else

262 OS << *GN.PTy;

263 OS << " }";

264 return OS;

265 }

266

267 template

269 using const_iterator = typename NodeContainer::const_iterator;

270

272 OS << *I << ' ' << **I << '\n';

273 }

274

280

282 const NodeToUsesMap &M);

284 for (const auto &I : M) {

285 const UseSet &Us = I.second;

286 OS << I.first << " -> #" << Us.size() << '{';

287 for (const Use *U : Us) {

288 User *R = U->getUser();

289 if (R->hasName())

290 OS << ' ' << R->getName();

291 else

292 OS << " <?>(" << *R << ')';

293 }

294 OS << " }\n";

295 }

296 return OS;

297 }

298

301

303 return NS.find(N) != NS.end();

304 }

305

306 private:

308 };

309

310}

311

313 return A.Allocate();

314}

315

316void HexagonCommonGEP::getBlockTraversalOrder(BasicBlock *Root,

317 ValueVect &Order) {

318

319

320

321

322 Order.push_back(Root);

324 getBlockTraversalOrder(DTN->getBlock(), Order);

325}

326

327bool HexagonCommonGEP::isHandledGepForm(GetElementPtrInst *GepI) {

328

330 return false;

331

333 return false;

334 return true;

335}

336

337void HexagonCommonGEP::processGepInst(GetElementPtrInst *GepI,

338 ValueToNodeMap &NM) {

339 LLVM_DEBUG(dbgs() << "Visiting GEP: " << *GepI << '\n');

340 GepNode *N = new (*Mem) GepNode;

342 uint32_t InBounds = GepI->isInBounds() ? GepNode::InBounds : 0;

343 ValueToNodeMap::iterator F = NM.find(PtrOp);

344 if (F == NM.end()) {

345 N->BaseVal = PtrOp;

346 N->Flags |= GepNode::Root | InBounds;

347 } else {

348

349

350

351 N->Parent = F->second;

352 }

354 N->Flags |= GepNode::Pointer;

356

357

358

359 UseSet Us;

360 for (Value::user_iterator UI = GepI->user_begin(), UE = GepI->user_end();

361 UI != UE; ++UI) {

362

363

366 if (isHandledGepForm(UserG))

367 continue;

368 }

369 Us.insert(&UI.getUse());

370 }

371 Nodes.push_back(N);

373

374

375

376 GepNode *PN = N;

380 GepNode *Nx = new (*Mem) GepNode;

381 Nx->Parent = PN;

382 Nx->Flags |= GepNode::Internal | InBounds;

383 Nx->PTy = PtrTy;

384 Nx->Idx = Op;

385 Nodes.push_back(Nx);

387 PN = Nx;

388

390 }

391

392

393 if (!Us.empty()) {

394 PN->Flags |= GepNode::Used;

395 Uses[PN].insert_range(Us);

396 }

397

398

399

400 NM.insert(std::make_pair(GepI, PN));

401}

402

403void HexagonCommonGEP::collect() {

404

405 ValueVect BO;

406 getBlockTraversalOrder(&Fn->front(), BO);

407

408

409

410

411 ValueToNodeMap NM;

412 for (Value *I : BO) {

414 for (Instruction &J : *B)

416 if (isHandledGepForm(GepI))

417 processGepInst(GepI, NM);

418 }

419

420 LLVM_DEBUG(dbgs() << "Gep nodes after initial collection:\n" << Nodes);

421}

422

424 NodeVect &Roots) {

425 for (GepNode *N : Nodes) {

426 if (N->Flags & GepNode::Root) {

427 Roots.push_back(N);

428 continue;

429 }

430 GepNode *PN = N->Parent;

431 NCM[PN].push_back(N);

432 }

433}

434

437 NodeVect Work;

438 Work.push_back(Root);

440

441 while (!Work.empty()) {

442 NodeVect::iterator First = Work.begin();

444 Work.erase(First);

445 NodeChildrenMap::iterator CF = NCM.find(N);

446 if (CF != NCM.end()) {

448 Nodes.insert(CF->second.begin(), CF->second.end());

449 }

450 }

451}

452

453namespace {

454

455 using NodeSymRel = std::set;

456 using NodePair = std::pair<GepNode *, GepNode *>;

457 using NodePairSet = std::set;

458

459}

460

462 for (const NodeSet &S : Rel)

463 if (S.count(N))

464 return &S;

465 return nullptr;

466}

467

468

469

470

471static NodePair node_pair(GepNode *N1, GepNode *N2) {

472 uintptr_t P1 = reinterpret_cast<uintptr_t>(N1);

473 uintptr_t P2 = reinterpret_cast<uintptr_t>(N2);

474 if (P1 <= P2)

475 return std::make_pair(N1, N2);

476 return std::make_pair(N2, N1);

477}

478

480

482 ID.AddPointer(N->Idx);

483 ID.AddPointer(N->PTy);

484 return ID.ComputeHash();

485}

486

487static bool node_eq(GepNode *N1, GepNode *N2, NodePairSet &Eq,

488 NodePairSet &Ne) {

489

490

492 return false;

493

495 NodePairSet::iterator FEq = Eq.find(NP);

496 if (FEq != Eq.end())

497 return true;

498 NodePairSet::iterator FNe = Ne.find(NP);

499 if (FNe != Ne.end())

500 return false;

501

502 bool Root1 = N1->Flags & GepNode::Root;

503 uint32_t CmpFlags = GepNode::Root | GepNode::Pointer;

504 bool Different = (N1->Flags & CmpFlags) != (N2->Flags & CmpFlags);

506

507

508

509

510 if (Different || (Root1 && N1->BaseVal != N2->BaseVal)) {

511 Ne.insert(P);

512 return false;

513 }

514

515

516

517 if (Root1 || node_eq(N1->Parent, N2->Parent, Eq, Ne)) {

518 Eq.insert(P);

519 return true;

520 }

521 return false;

522}

523

524void HexagonCommonGEP::common() {

525

526

527

528

529 using NodeSetMap = std::map<unsigned, NodeSet>;

530 NodeSetMap MaybeEq;

531

532 for (GepNode *N : Nodes) {

534 MaybeEq[H].insert(N);

535 }

536

537

538

539 NodeSymRel EqRel;

540 NodePairSet Eq, Ne;

541 for (auto &I : MaybeEq) {

544 GepNode *N = *NI;

545

546

547

549 continue;

550

551

555 C.insert(*NJ);

556

557

558 if (.empty()) {

559 C.insert(N);

560 std::pair<NodeSymRel::iterator, bool> Ins = EqRel.insert(C);

561 (void)Ins;

562 assert(Ins.second && "Cannot add a class");

563 }

564 }

565 }

566

568 dbgs() << "Gep node equality:\n";

569 for (NodePairSet::iterator I = Eq.begin(), E = Eq.end(); I != E; ++I)

570 dbgs() << "{ " << I->first << ", " << I->second << " }\n";

571

572 dbgs() << "Gep equivalence classes:\n";

573 for (const NodeSet &S : EqRel) {

574 dbgs() << '{';

575 for (NodeSet::const_iterator J = S.begin(), F = S.end(); J != F; ++J) {

576 if (J != S.begin())

577 dbgs() << ',';

578 dbgs() << ' ' << *J;

579 }

580 dbgs() << " }\n";

581 }

582 });

583

584

585 using ProjMap = std::map<const NodeSet *, GepNode *>;

586 ProjMap PM;

587 for (const NodeSet &S : EqRel) {

589 std::pairProjMap::iterator,bool Ins = PM.insert(std::make_pair(&S, Min));

590 (void)Ins;

591 assert(Ins.second && "Cannot add minimal element");

592

593

594 uint32_t Flags = 0;

595 UseSet &MinUs = Uses[Min];

596 for (GepNode *N : S) {

597 uint32_t NF = N->Flags;

598

599

600 if (NF & GepNode::Used) {

602 MinUs.insert_range(U);

603 }

605 }

606 if (MinUs.empty())

607 Uses.erase(Min);

608

609

610 assert((Min->Flags & Flags) == Min->Flags);

611 Min->Flags = Flags;

612 }

613

614

615

616

617

618 for (GepNode *N : Nodes) {

619 if (N->Flags & GepNode::Root)

620 continue;

622 if (!PC)

623 continue;

624 ProjMap::iterator F = PM.find(PC);

625 if (F == PM.end())

626 continue;

627

628 GepNode *Rep = F->second;

629 N->Parent = Rep;

630 }

631

632 LLVM_DEBUG(dbgs() << "Gep nodes after commoning:\n" << Nodes);

633

634

636 for (GepNode *N : Nodes) {

638 if (!PC)

639 continue;

640 ProjMap::iterator F = PM.find(PC);

641 if (F == PM.end())

642 continue;

643 if (N == F->second)

644 continue;

645

647 }

648 erase_if(Nodes, in_set(Erase));

649

650 LLVM_DEBUG(dbgs() << "Gep nodes after post-commoning cleanup:\n" << Nodes);

651}

652

653template

656 dbgs() << "NCD of {";

657 for (typename T::iterator I = Blocks.begin(), E = Blocks.end(); I != E;

658 ++I) {

659 if (!*I)

660 continue;

662 dbgs() << ' ' << B->getName();

663 }

664 dbgs() << " }\n";

665 });

666

667

668 typename T::iterator I = Blocks.begin(), E = Blocks.end();

669 if (I == E || !*I)

670 return nullptr;

672 while (++I != E) {

675 if (!Dom)

676 return nullptr;

677 }

679 return Dom;

680}

681

682template

684

685

686 typename T::iterator I = Blocks.begin(), E = Blocks.end();

687

688 while (I != E && !*I)

689 ++I;

690 if (I == E)

693 while (++I != E) {

694 if (!*I)

695 continue;

698 continue;

700 return nullptr;

701 DomB = B;

702 }

703 return DomB;

704}

705

706

707

708template

711

712 using iterator = typename T::iterator;

713

714 for (iterator I = Values.begin(), E = Values.end(); I != E; ++I) {

716

717

718

719

720

722 continue;

724 continue;

726 if (In->getParent() != B)

727 continue;

729 if (std::distance(FirstUse, BEnd) < std::distance(It, BEnd))

730 FirstUse = It;

731 }

732 return FirstUse;

733}

734

736 return B->empty() || (&*B->begin() == B->getTerminator());

737}

738

739BasicBlock *HexagonCommonGEP::recalculatePlacement(GepNode *Node,

740 NodeChildrenMap &NCM, NodeToValueMap &Loc) {

741 LLVM_DEBUG(dbgs() << "Loc for node:" << Node << '\n');

742

743

744

745

746

747

748

749

750

751 ValueVect Bs;

752 if (Node->Flags & GepNode::Used) {

753

754

755 NodeToUsesMap::iterator UF = Uses.find(Node);

756 assert(UF != Uses.end() && "Used node with no use information");

757 UseSet &Us = UF->second;

758 for (Use *U : Us) {

759 User *R = U->getUser();

761 continue;

765 Bs.push_back(PB);

766 }

767 }

768

769 NodeChildrenMap::iterator CF = NCM.find(Node);

770 if (CF != NCM.end()) {

771 NodeVect &Cs = CF->second;

772 for (GepNode *CN : Cs) {

773 NodeToValueMap::iterator LF = Loc.find(CN);

774

775

776

777 if (LF == Loc.end())

778 continue;

779 Bs.push_back(LF->second);

780 }

781 }

782

784 if (!DomB)

785 return nullptr;

786

789 return nullptr;

790

791

794 if ()

795 break;

796 DomB = N->getBlock();

797 }

798

799

800 Loc[Node] = DomB;

801 return DomB;

802}

803

804BasicBlock *HexagonCommonGEP::recalculatePlacementRec(GepNode *Node,

805 NodeChildrenMap &NCM, NodeToValueMap &Loc) {

806 LLVM_DEBUG(dbgs() << "LocRec begin for node:" << Node << '\n');

807

808

809 NodeChildrenMap::iterator CF = NCM.find(Node);

810 if (CF != NCM.end()) {

811 NodeVect &Cs = CF->second;

812 for (GepNode *C : Cs)

813 recalculatePlacementRec(C, NCM, Loc);

814 }

815 BasicBlock *LB = recalculatePlacement(Node, NCM, Loc);

816 LLVM_DEBUG(dbgs() << "LocRec end for node:" << Node << '\n');

817 return LB;

818}

819

820bool HexagonCommonGEP::isInvariantIn(Value *Val, Loop *L) {

822 return true;

824 if (!In)

825 return false;

826 BasicBlock *HdrB = L->getHeader(), *DefB = In->getParent();

828}

829

830bool HexagonCommonGEP::isInvariantIn(GepNode *Node, Loop *L) {

831 if (Node->Flags & GepNode::Root)

832 if (!isInvariantIn(Node->BaseVal, L))

833 return false;

834 return isInvariantIn(Node->Idx, L);

835}

836

837bool HexagonCommonGEP::isInMainPath(BasicBlock *B, Loop *L) {

840

842 return true;

844 return true;

845 return false;

846}

847

849 if (BasicBlock *PH = L->getLoopPreheader())

850 return PH;

852 return nullptr;

854 if (!DN)

855 return nullptr;

857}

858

859BasicBlock *HexagonCommonGEP::adjustForInvariance(GepNode *Node,

860 NodeChildrenMap &NCM, NodeToValueMap &Loc) {

861

862

863

864 ValueVect Bs;

865 if (Node->Flags & GepNode::Root) {

867 Bs.push_back(PIn->getParent());

868 } else {

869 Bs.push_back(Loc[Node->Parent]);

870 }

872 Bs.push_back(IIn->getParent());

874

875

876

877

878

879

880

881

882

884 if (LocB) {

886 while (Lp) {

887 if (!isInvariantIn(Node, Lp) || !isInMainPath(LocB, Lp))

888 break;

890 if (!NewLoc || !DT->dominates(TopB, NewLoc))

891 break;

893 LocB = NewLoc;

894 }

895 }

896 Loc[Node] = LocB;

897

898

899 NodeChildrenMap::iterator CF = NCM.find(Node);

900 if (CF != NCM.end()) {

901 NodeVect &Cs = CF->second;

902 for (GepNode *C : Cs)

903 adjustForInvariance(C, NCM, Loc);

904 }

905 return LocB;

906}

907

908namespace {

909

910 struct LocationAsBlock {

911 LocationAsBlock(const NodeToValueMap &L) : Map(L) {}

912

913 const NodeToValueMap ⤅

914 };

915

916 [[maybe_unused]] raw_ostream &operator<<(raw_ostream &OS,

917 const LocationAsBlock &Loc) {

918 for (const auto &I : Loc.Map) {

919 OS << I.first << " -> ";

921 OS << B->getName() << '(' << B << ')';

922 else

923 OS << "";

924 OS << '\n';

925 }

926 return OS;

927 }

928

929 inline bool is_constant(GepNode *N) {

931 }

932

933}

934

935void HexagonCommonGEP::separateChainForNode(GepNode *Node, Use *U,

936 NodeToValueMap &Loc) {

937 User *R = U->getUser();

938 LLVM_DEBUG(dbgs() << "Separating chain for node (" << Node << ") user: " << *R

939 << '\n');

941

942 GepNode *N = Node;

943 GepNode *C = nullptr, *NewNode = nullptr;

944 while (is_constant(N) && !(N->Flags & GepNode::Root)) {

945

946 GepNode *NewN = new (*Mem) GepNode(N);

947 Nodes.push_back(NewN);

948 Loc[NewN] = PB;

949

950 if (N == Node)

951 NewNode = NewN;

952 NewN->Flags &= ~GepNode::Used;

953 if (C)

954 C->Parent = NewN;

955 C = NewN;

956 N = N->Parent;

957 }

958 if (!NewNode)

959 return;

960

961

962 NodeToUsesMap::iterator UF = Uses.find(Node);

964 UseSet &Us = UF->second;

965 UseSet NewUs;

966 for (Use *U : Us) {

967 if (U->getUser() == R)

968 NewUs.insert(U);

969 }

970 for (Use *U : NewUs)

971 Us.remove(U);

972

973 if (Us.empty()) {

974 Node->Flags &= ~GepNode::Used;

975 Uses.erase(UF);

976 }

977

978

979 NewNode->Flags |= GepNode::Used;

980 LLVM_DEBUG(dbgs() << "new node: " << NewNode << " " << *NewNode << '\n');

981 assert(!NewUs.empty());

982 Uses[NewNode] = NewUs;

983}

984

985void HexagonCommonGEP::separateConstantChains(GepNode *Node,

986 NodeChildrenMap &NCM, NodeToValueMap &Loc) {

987

990

991 LLVM_DEBUG(dbgs() << "Separating constant chains for node: " << Node << '\n');

992

993

994 NodeToUsesMap FNs;

995 for (GepNode *N : Ns) {

996 if (!(N->Flags & GepNode::Used))

997 continue;

998 NodeToUsesMap::iterator UF = Uses.find(N);

1000 UseSet &Us = UF->second;

1001

1002 UseSet LSs;

1003 for (Use *U : Us) {

1004 User *R = U->getUser();

1005

1006

1007

1010 if (&Ld->getOperandUse(PtrX) == U)

1011 LSs.insert(U);

1014 if (&St->getOperandUse(PtrX) == U)

1015 LSs.insert(U);

1016 }

1017 }

1018

1019

1020

1021

1022 if (!LSs.empty())

1023 FNs.insert(std::make_pair(N, LSs));

1024 }

1025

1026 LLVM_DEBUG(dbgs() << "Nodes with foldable users:\n" << FNs);

1027

1028 for (auto &FN : FNs) {

1029 GepNode *N = FN.first;

1030 UseSet &Us = FN.second;

1031 for (Use *U : Us)

1032 separateChainForNode(N, U, Loc);

1033 }

1034}

1035

1036void HexagonCommonGEP::computeNodePlacement(NodeToValueMap &Loc) {

1037

1038

1039 NodeChildrenMap NCM;

1040 NodeVect Roots;

1042

1043

1044

1045 for (GepNode *Root : Roots)

1046 recalculatePlacementRec(Root, NCM, Loc);

1047

1048 LLVM_DEBUG(dbgs() << "Initial node placement:\n" << LocationAsBlock(Loc));

1049

1051 for (GepNode *Root : Roots)

1052 adjustForInvariance(Root, NCM, Loc);

1053

1054 LLVM_DEBUG(dbgs() << "Node placement after adjustment for invariance:\n"

1055 << LocationAsBlock(Loc));

1056 }

1058 for (GepNode *Root : Roots)

1059 separateConstantChains(Root, NCM, Loc);

1060 }

1062

1063

1064

1065

1066

1067 LLVM_DEBUG(dbgs() << "Final node placement:\n" << LocationAsBlock(Loc));

1068}

1069

1071 BasicBlock *LocB) {

1073 << " for nodes:\n"

1074 << NA);

1075 unsigned Num = NA.size();

1076 GepNode *RN = NA[0];

1077 assert((RN->Flags & GepNode::Root) && "Creating GEP for non-root");

1078

1079 GetElementPtrInst *NewInst = nullptr;

1080 Value *Input = RN->BaseVal;

1081 Type *InpTy = RN->PTy;

1082

1083 unsigned Idx = 0;

1084 do {

1086

1087

1088

1089 if (!(NA[Idx]->Flags & GepNode::Pointer)) {

1092 }

1093

1094

1095

1096 while (++Idx <= Num) {

1097 GepNode *N = NA[Idx-1];

1099 if (Idx < Num) {

1100

1101 if (NA[Idx]->Flags & GepNode::Pointer)

1102 break;

1103 }

1104 }

1107 LLVM_DEBUG(dbgs() << "new GEP: " << *NewInst << '\n');

1108 if (Idx < Num) {

1109 Input = NewInst;

1110 InpTy = NA[Idx]->PTy;

1111 }

1112 } while (Idx <= Num);

1113

1114 return NewInst;

1115}

1116

1117void HexagonCommonGEP::getAllUsersForNode(GepNode *Node, ValueVect &Values,

1118 NodeChildrenMap &NCM) {

1119 NodeVect Work;

1120 Work.push_back(Node);

1121

1122 while (!Work.empty()) {

1123 NodeVect::iterator First = Work.begin();

1124 GepNode *N = *First;

1125 Work.erase(First);

1126 if (N->Flags & GepNode::Used) {

1127 NodeToUsesMap::iterator UF = Uses.find(N);

1128 assert(UF != Uses.end() && "No use information for used node");

1129 UseSet &Us = UF->second;

1130 for (const auto &U : Us)

1131 Values.push_back(U->getUser());

1132 }

1133 NodeChildrenMap::iterator CF = NCM.find(N);

1134 if (CF != NCM.end()) {

1135 NodeVect &Cs = CF->second;

1137 }

1138 }

1139}

1140

1141void HexagonCommonGEP::materialize(NodeToValueMap &Loc) {

1142 LLVM_DEBUG(dbgs() << "Nodes before materialization:\n" << Nodes << '\n');

1143 NodeChildrenMap NCM;

1144 NodeVect Roots;

1145

1146

1148

1149 while (!Roots.empty()) {

1150 NodeVect::iterator First = Roots.begin();

1153

1154 NodeVect NA;

1155

1156

1157

1158

1159

1160 bool LastUsed = false;

1161 unsigned LastCN = 0;

1162

1163

1165 if (!LocV)

1166 continue;

1168 do {

1169 NA.push_back(Last);

1170 LastUsed = (Last->Flags & GepNode::Used);

1171 if (LastUsed)

1172 break;

1173 NodeChildrenMap::iterator CF = NCM.find(Last);

1174 LastCN = (CF != NCM.end()) ? CF->second.size() : 0;

1175 if (LastCN != 1)

1176 break;

1177 GepNode *Child = CF->second.front();

1179 if (ChildB != nullptr && LastB != ChildB)

1180 break;

1181 Last = Child;

1182 } while (true);

1183

1185 if (LastUsed || LastCN > 0) {

1186 ValueVect Urs;

1187 getAllUsersForNode(Root, Urs, NCM);

1189 if (FirstUse != LastB->end())

1190 InsertAt = FirstUse;

1191 }

1192

1193

1194 Value *NewInst = fabricateGEP(NA, InsertAt, LastB);

1195

1196

1197

1198 if (LastCN > 0) {

1199 NodeVect &Cs = NCM[Last];

1200 for (GepNode *CN : Cs) {

1201 CN->Flags &= ~GepNode::Internal;

1202 CN->Flags |= GepNode::Root;

1203 CN->BaseVal = NewInst;

1204 Roots.push_back(CN);

1205 }

1206 }

1207

1208

1209

1210 if (LastUsed) {

1211 NodeToUsesMap::iterator UF = Uses.find(Last);

1212 assert(UF != Uses.end() && "No use information found");

1213 UseSet &Us = UF->second;

1214 for (Use *U : Us)

1215 U->set(NewInst);

1216 }

1217 }

1218}

1219

1220void HexagonCommonGEP::removeDeadCode() {

1221 ValueVect BO;

1222 BO.push_back(&Fn->front());

1223

1224 for (unsigned i = 0; i < BO.size(); ++i) {

1227 BO.push_back(DTN->getBlock());

1228 }

1229

1232 ValueVect Ins;

1234 Ins.push_back(&I);

1235 for (Value *I : Ins) {

1238 In->eraseFromParent();

1239 }

1240 }

1241}

1242

1243bool HexagonCommonGEP::runOnFunction(Function &F) {

1244 if (skipFunction(F))

1245 return false;

1246

1247

1248 for (const BasicBlock &BB : F)

1249 for (const Instruction &I : BB)

1251 return false;

1252

1253 Fn = &F;

1254 DT = &getAnalysis().getDomTree();

1255 PDT = &getAnalysis().getPostDomTree();

1256 LI = &getAnalysis().getLoopInfo();

1257 Ctx = &F.getContext();

1258

1259 Nodes.clear();

1260 Uses.clear();

1262

1263 SpecificBumpPtrAllocator Allocator;

1265

1266 collect();

1267 common();

1268

1269 NodeToValueMap Loc;

1270 computeNodePlacement(Loc);

1271 materialize(Loc);

1272 removeDeadCode();

1273

1274#ifdef EXPENSIVE_CHECKS

1275

1278#endif

1279 return true;

1280}

1281

1282namespace llvm {

1283

1285 return new HexagonCommonGEP();

1286 }

1287

1288}

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

This file defines the BumpPtrAllocator interface.

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

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

static bool runOnFunction(Function &F, bool PostInlining)

This file defines a hash set that can be used to remove duplication of nodes in a graph.

This file defines the little GraphTraits template class that should be specialized by classes that...

static unsigned node_hash(GepNode *N)

Definition HexagonCommonGEP.cpp:479

static cl::opt< bool > OptEnableInv("commgep-inv", cl::init(true), cl::Hidden)

static NodePair node_pair(GepNode *N1, GepNode *N2)

Definition HexagonCommonGEP.cpp:471

static bool node_eq(GepNode *N1, GepNode *N2, NodePairSet &Eq, NodePairSet &Ne)

Definition HexagonCommonGEP.cpp:487

static const NodeSet * node_class(GepNode *N, NodeSymRel &Rel)

Definition HexagonCommonGEP.cpp:461

static cl::opt< bool > OptEnableConst("commgep-const", cl::init(true), cl::Hidden)

static BasicBlock * nearest_common_dominatee(DominatorTree *DT, T &Blocks)

Definition HexagonCommonGEP.cpp:683

static cl::opt< bool > OptSpeculate("commgep-speculate", cl::init(true), cl::Hidden)

static void invert_find_roots(const NodeVect &Nodes, NodeChildrenMap &NCM, NodeVect &Roots)

Definition HexagonCommonGEP.cpp:423

static BasicBlock * nearest_common_dominator(DominatorTree *DT, T &Blocks)

Definition HexagonCommonGEP.cpp:654

static bool is_empty(const BasicBlock *B)

Definition HexagonCommonGEP.cpp:735

static void nodes_for_root(GepNode *Root, NodeChildrenMap &NCM, NodeSet &Nodes)

Definition HexagonCommonGEP.cpp:435

static BasicBlock * preheader(DominatorTree *DT, Loop *L)

Definition HexagonCommonGEP.cpp:848

static BasicBlock::iterator first_use_of_in_block(T &Values, BasicBlock *B)

Definition HexagonCommonGEP.cpp:709

This defines the Use class.

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)

Remove Loads Into Fake Uses

This file implements a set that has insertion order iteration characteristics.

This file defines the SmallVector class.

AnalysisUsage & addRequired()

AnalysisUsage & addPreserved()

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

LLVM Basic Block Representation.

LLVM_ABI BasicBlock::iterator erase(BasicBlock::iterator FromIt, BasicBlock::iterator ToIt)

Erases a range of instructions from FromIt to (not including) ToIt.

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

This is the shared class of boolean and integer constants.

DomTreeNodeBase * getIDom() const

DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const

getNode - return the (Post)DominatorTree node for the specified basic block.

bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const

properlyDominates - Returns true iff A dominates B and A != B.

Legacy analysis pass which computes a DominatorTree.

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

LLVM_ABI Instruction * findNearestCommonDominator(Instruction *I1, Instruction *I2) const

Find the nearest instruction I that dominates both I1 and I2, in the sense that a result produced bef...

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.

FoldingSetNodeID - This class is used to gather all the unique data bits of a node.

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

const BasicBlock & front() const

LLVM_ABI bool isInBounds() const

Determine whether the GEP has the inbounds flag.

static LLVM_ABI Type * getTypeAtIndex(Type *Ty, Value *Idx)

Return the type of the element at the given index of an indexable type.

Value * getPointerOperand()

iterator_range< op_iterator > indices()

static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)

LLVM_ABI void setIsInBounds(bool b=true)

Set or clear the inbounds flag on this GEP instruction.

Type * getSourceElementType() const

static unsigned getPointerOperandIndex()

LoopT * getParentLoop() const

Return the parent loop if it exists or nullptr for top level loops.

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

The legacy pass manager's analysis pass to compute loop information.

Represents a single loop in the control flow graph.

A NodeSet contains a set of SUnit DAG nodes with additional information that assigns a priority to th...

SetVector< SUnit * >::const_iterator iterator

LLVM_ABI bool dominates(const Instruction *I1, const Instruction *I2) const

Return true if I1 dominates I2.

A vector that has set insertion semantics.

void push_back(const T &Elt)

A BumpPtrAllocator that allows only elements of a specific type to be allocated.

static unsigned getPointerOperandIndex()

Class to represent struct types.

bool isLiteral() const

Return true if this type is uniqued by structural equivalence, false if it is a struct definition.

The instances of the Type class are immutable: once they are created, they are never changed.

bool isPointerTy() const

True if this is an instance of PointerType.

LLVM_ABI StringRef getStructName() const

bool isStructTy() const

True if this is an instance of StructType.

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

LLVM Value Representation.

Type * getType() const

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

user_iterator user_begin()

LLVM_ABI StringRef getName() const

Return a constant reference to the value's name.

const ParentTy * getParent() const

self_iterator getIterator()

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

void dump_node_container(raw_ostream &OS, const NodeContainer &S)

Definition HexagonCommonGEP.cpp:268

unsigned ID

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

@ C

The default llvm calling convention, compatible with C.

@ BasicBlock

Various leaf nodes.

initializer< Ty > init(const Ty &Val)

@ User

could "use" a pointer

NodeAddr< NodeBase * > Node

std::set< NodeId > NodeSet

friend class Instruction

Iterator for Instructions in a `BasicBlock.

This is an optimization pass for GlobalISel generic memory operations.

auto drop_begin(T &&RangeOrContainer, size_t N=1)

Return a range covering RangeOrContainer with the first N elements excluded.

FunctionAddr VTableAddr Value

auto min_element(R &&Range)

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

decltype(auto) dyn_cast(const From &Val)

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

FunctionAddr VTableAddr uintptr_t uintptr_t Int32Ty

LLVM_ABI bool verifyFunction(const Function &F, raw_ostream *OS=nullptr)

Check a function for errors, useful for use when debugging a pass.

void append_range(Container &C, Range &&R)

Wrapper function to append range R to container C.

auto cast_or_null(const Y &Val)

DomTreeNodeBase< BasicBlock > DomTreeNode

LLVM_ABI bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)

Return true if the result produced by the instruction is not used, and the instruction will return.

auto reverse(ContainerTy &&C)

LLVM_ABI raw_ostream & dbgs()

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

LLVM_ABI void report_fatal_error(Error Err, bool gen_crash_diag=true)

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

@ First

Helpers to iterate all locations in the MemoryEffectsBase class.

FunctionPass * createHexagonCommonGEP()

Definition HexagonCommonGEP.cpp:1284

DWARFExpression::Operation Op

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

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

iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)

GepNode * Parent

Definition HexagonCommonGEP.cpp:192

Type * PTy

Definition HexagonCommonGEP.cpp:196

Value * BaseVal

Definition HexagonCommonGEP.cpp:193

GepNode(const GepNode *N)

Definition HexagonCommonGEP.cpp:201

@ InBounds

Definition HexagonCommonGEP.cpp:175

@ Pointer

Definition HexagonCommonGEP.cpp:176

@ Used

Definition HexagonCommonGEP.cpp:174

@ Root

Definition HexagonCommonGEP.cpp:172

@ None

Definition HexagonCommonGEP.cpp:171

@ Internal

Definition HexagonCommonGEP.cpp:173

uint32_t Flags

Definition HexagonCommonGEP.cpp:190

GepNode()

Definition HexagonCommonGEP.cpp:200

Value * Idx

Definition HexagonCommonGEP.cpp:195

in_set(const NodeSet &S)

Definition HexagonCommonGEP.cpp:300