HexagonCommonGEP.cpp Source File (original) (raw)

40#include

41#include

42#include

43#include

44#include

45#include

46#include

47#include

49#define DEBUG_TYPE "commgep"

51using namespace llvm;

61namespace llvm {

65}

67namespace {

69 struct GepNode;

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

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

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

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

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

79 struct NodeOrdering {

80 NodeOrdering() = default;

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

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

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

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

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

89 }

91 private:

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

93 unsigned LastNum = 0;

94 };

96 class HexagonCommonGEP : public FunctionPass {

97 public:

98 static char ID;

102 }

103

106

115 }

116

117 private:

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

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

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

121

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

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

125 void collect();

126 void common();

127

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

129 NodeToValueMap &Loc);

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

131 NodeToValueMap &Loc);

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

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

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

136 NodeToValueMap &Loc);

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

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

139 NodeToValueMap &Loc);

140 void computeNodePlacement(NodeToValueMap &Loc);

141

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

145 NodeChildrenMap &NCM);

146 void materialize(NodeToValueMap &Loc);

147

148 void removeDeadCode();

149

150 NodeVect Nodes;

151 NodeToUsesMap Uses;

152 NodeOrdering NodeOrder;

159 };

160

161}

162

163char HexagonCommonGEP::ID = 0;

164

166 false, false)

172

173namespace {

174

176 enum {

178 Root = 0x01,

179 Internal = 0x02,

180 Used = 0x04,

181 InBounds = 0x08,

182 Pointer = 0x10,

183 };

184

185

186

187

188

189

190

191

192

193

194

195

197 union {

200 };

202 Type *PTy = nullptr;

203

204

205

208 if (Flags & Root)

209 BaseVal = N->BaseVal;

210 else

211 Parent = N->Parent;

212 }

213

215 };

216

218 OS << "{ {";

219 bool Comma = false;

220 if (GN.Flags & GepNode::Root) {

221 OS << "root";

222 Comma = true;

223 }

224 if (GN.Flags & GepNode::Internal) {

225 if (Comma)

226 OS << ',';

227 OS << "internal";

228 Comma = true;

229 }

230 if (GN.Flags & GepNode::Used) {

231 if (Comma)

232 OS << ',';

233 OS << "used";

234 }

235 if (GN.Flags & GepNode::InBounds) {

236 if (Comma)

237 OS << ',';

238 OS << "inbounds";

239 }

240 if (GN.Flags & GepNode::Pointer) {

241 if (Comma)

242 OS << ',';

243 OS << "pointer";

244 }

245 OS << "} ";

246 if (GN.Flags & GepNode::Root)

248 else

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

250

251 OS << " Idx:";

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

256 else

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

258

259 OS << " PTy:";

264 else

265 OS << ":" << *STy;

266 }

267 else

269 OS << " }";

270 return OS;

271 }

272

273 template

275 using const_iterator = typename NodeContainer::const_iterator;

276

277 for (const_iterator I = S.begin(), E = S.end(); I != E; ++I)

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

279 }

280

285 return OS;

286 }

287

291 for (const auto &I : M) {

292 const UseSet &Us = I.second;

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

294 for (const Use *U : Us) {

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

296 if (R->hasName())

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

298 else

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

300 }

301 OS << " }\n";

302 }

303 return OS;

304 }

305

308

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

311 }

312

313 private:

315 };

316

317}

318

320 return A.Allocate();

321}

322

323void HexagonCommonGEP::getBlockTraversalOrder(BasicBlock *Root,

324 ValueVect &Order) {

325

326

327

328

329 Order.push_back(Root);

330 for (auto *DTN : children<DomTreeNode*>(DT->getNode(Root)))

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

332}

333

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

335

337 return false;

338

340 return false;

341 return true;

342}

343

345 ValueToNodeMap &NM) {

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

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

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

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

352 N->BaseVal = PtrOp;

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

354 } else {

355

356

357

358 N->Parent = F->second;

359 }

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

363

364

365

366 UseSet Us;

368 UI != UE; ++UI) {

369

370

371 if (isa(*UI)) {

373 if (isHandledGepForm(UserG))

374 continue;

375 }

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

377 }

378 Nodes.push_back(N);

380

381

382

383 GepNode *PN = N;

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

388 Nx->Parent = PN;

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

390 Nx->PTy = PtrTy;

391 Nx->Idx = Op;

392 Nodes.push_back(Nx);

394 PN = Nx;

395

397 }

398

399

400 if (!Us.empty()) {

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

402 Uses[PN].insert(Us.begin(), Us.end());

403 }

404

405

406

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

408}

409

410void HexagonCommonGEP::collect() {

411

412 ValueVect BO;

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

414

415

416

417

418 ValueToNodeMap NM;

419 for (Value *I : BO) {

422 if (auto *GepI = dyn_cast(&J))

423 if (isHandledGepForm(GepI))

424 processGepInst(GepI, NM);

425 }

426

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

428}

429

431 NodeVect &Roots) {

432 for (GepNode *N : Nodes) {

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

434 Roots.push_back(N);

435 continue;

436 }

437 GepNode *PN = N->Parent;

438 NCM[PN].push_back(N);

439 }

440}

441

444 NodeVect Work;

445 Work.push_back(Root);

447

448 while (!Work.empty()) {

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

451 Work.erase(First);

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

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

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

456 }

457 }

458}

459

460namespace {

461

462 using NodeSymRel = std::set;

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

464 using NodePairSet = std::set;

465

466}

467

469 for (const NodeSet &S : Rel)

470 if (S.count(N))

471 return &S;

472 return nullptr;

473}

474

475

476

477

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

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

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

481 if (P1 <= P2)

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

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

484}

485

487

489 ID.AddPointer(N->Idx);

490 ID.AddPointer(N->PTy);

491 return ID.ComputeHash();

492}

493

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

495 NodePairSet &Ne) {

496

497

499 return false;

500

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

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

504 return true;

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

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

507 return false;

508

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

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

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

513

514

515

516

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

518 Ne.insert(P);

519 return false;

520 }

521

522

523

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

525 Eq.insert(P);

526 return true;

527 }

528 return false;

529}

530

531void HexagonCommonGEP::common() {

532

533

534

535

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

537 NodeSetMap MaybeEq;

538

539 for (GepNode *N : Nodes) {

541 MaybeEq[H].insert(N);

542 }

543

544

545

546 NodeSymRel EqRel;

547 NodePairSet Eq, Ne;

548 for (auto &I : MaybeEq) {

551 GepNode *N = *NI;

552

553

554

556 continue;

557

558

562 C.insert(*NJ);

563

564

565 if (.empty()) {

566 C.insert(N);

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

568 (void)Ins;

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

570 }

571 }

572 }

573

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

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

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

578

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

580 for (const NodeSet &S : EqRel) {

581 dbgs() << '{';

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

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

584 dbgs() << ',';

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

586 }

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

588 }

589 });

590

591

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

593 ProjMap PM;

594 for (const NodeSet &S : EqRel) {

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

597 (void)Ins;

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

599

600

602 UseSet &MinUs = Uses[Min];

603 for (GepNode *N : S) {

605

606

607 if (NF & GepNode::Used)

610 }

611 if (MinUs.empty())

612 Uses.erase(Min);

613

614

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

616 Min->Flags = Flags;

617 }

618

619

620

621

622

623 for (GepNode *N : Nodes) {

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

625 continue;

627 if (!PC)

628 continue;

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

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

631 continue;

632

633 GepNode *Rep = F->second;

634 N->Parent = Rep;

635 }

636

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

638

639

641 for (GepNode *N : Nodes) {

643 if (!PC)

644 continue;

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

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

647 continue;

648 if (N == F->second)

649 continue;

650

652 }

653 erase_if(Nodes, in_set(Erase));

654

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

656}

657

658template

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

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

663 ++I) {

664 if (!*I)

665 continue;

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

668 }

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

670 });

671

672

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

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

675 return nullptr;

677 while (++I != E) {

678 BasicBlock *B = cast_or_null(*I);

680 if (!Dom)

681 return nullptr;

682 }

684 return Dom;

685}

686

687template

689

690

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

692

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

694 ++I;

695 if (I == E)

698 while (++I != E) {

699 if (!*I)

700 continue;

703 continue;

705 return nullptr;

706 DomB = B;

707 }

708 return DomB;

709}

710

711

712

713template

716

717 using iterator = typename T::iterator;

718

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

721

722

723

724

725

726 if (isa(V))

727 continue;

728 if (!isa(V))

729 continue;

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

732 continue;

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

735 FirstUse = It;

736 }

737 return FirstUse;

738}

739

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

742}

743

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

745 NodeChildrenMap &NCM, NodeToValueMap &Loc) {

747

748

749

750

751

752

753

754

755

756 ValueVect Bs;

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

758

759

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

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

762 UseSet &Us = UF->second;

763 for (Use *U : Us) {

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

765 if (!isa(R))

766 continue;

768 ? cast(R)->getIncomingBlock(*U)

769 : cast(R)->getParent();

770 Bs.push_back(PB);

771 }

772 }

773

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

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

776 NodeVect &Cs = CF->second;

777 for (GepNode *CN : Cs) {

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

779

780

781

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

783 continue;

784 Bs.push_back(LF->second);

785 }

786 }

787

789 if (!DomB)

790 return nullptr;

791

794 return nullptr;

795

796

799 if ()

800 break;

801 DomB = N->getBlock();

802 }

803

804

805 Loc[Node] = DomB;

806 return DomB;

807}

808

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

810 NodeChildrenMap &NCM, NodeToValueMap &Loc) {

812

813

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

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

816 NodeVect &Cs = CF->second;

817 for (GepNode *C : Cs)

818 recalculatePlacementRec(C, NCM, Loc);

819 }

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

822 return LB;

823}

824

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

826 if (isa(Val) || isa(Val))

827 return true;

829 if (!In)

830 return false;

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

833}

834

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

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

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

838 return false;

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

840}

841

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

845

846 if (PDT->dominates(B, HB))

847 return true;

849 return true;

850 return false;

851}

852

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

855 return PH;

857 return nullptr;

859 if (!DN)

860 return nullptr;

862}

863

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

865 NodeChildrenMap &NCM, NodeToValueMap &Loc) {

866

867

868

869 ValueVect Bs;

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

871 if (Instruction *PIn = dyn_cast(Node->BaseVal))

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

873 } else {

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

875 }

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

879

880

881

882

883

884

885

886

887

888 BasicBlock *LocB = cast_or_null(Loc[Node]);

889 if (LocB) {

890 Loop *Lp = LI->getLoopFor(LocB);

891 while (Lp) {

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

893 break;

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

896 break;

898 LocB = NewLoc;

899 }

900 }

901 Loc[Node] = LocB;

902

903

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

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

906 NodeVect &Cs = CF->second;

907 for (GepNode *C : Cs)

908 adjustForInvariance(C, NCM, Loc);

909 }

910 return LocB;

911}

912

913namespace {

914

915 struct LocationAsBlock {

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

917

918 const NodeToValueMap &Map;

919 };

920

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

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

926 if (BasicBlock *B = cast_or_null(I.second))

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

928 else

929 OS << "";

930 OS << '\n';

931 }

932 return OS;

933 }

934

935 inline bool is_constant(GepNode *N) {

936 return isa(N->Idx);

937 }

938

939}

940

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

942 NodeToValueMap &Loc) {

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

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

945 << '\n');

946 BasicBlock *PB = cast(R)->getParent();

947

948 GepNode *N = Node;

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

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

951

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

953 Nodes.push_back(NewN);

954 Loc[NewN] = PB;

955

957 NewNode = NewN;

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

959 if (C)

960 C->Parent = NewN;

961 C = NewN;

962 N = N->Parent;

963 }

964 if (!NewNode)

965 return;

966

967

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

970 UseSet &Us = UF->second;

971 UseSet NewUs;

972 for (Use *U : Us) {

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

974 NewUs.insert(U);

975 }

976 for (Use *U : NewUs)

977 Us.remove(U);

978

979 if (Us.empty()) {

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

981 Uses.erase(UF);

982 }

983

984

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

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

987 assert(!NewUs.empty());

988 Uses[NewNode] = NewUs;

989}

990

991void HexagonCommonGEP::separateConstantChains(GepNode *Node,

992 NodeChildrenMap &NCM, NodeToValueMap &Loc) {

993

996

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

998

999

1000 NodeToUsesMap FNs;

1001 for (GepNode *N : Ns) {

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

1003 continue;

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

1006 UseSet &Us = UF->second;

1007

1008 UseSet LSs;

1009 for (Use *U : Us) {

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

1011

1012

1013

1014 if (LoadInst *Ld = dyn_cast(R)) {

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

1017 LSs.insert(U);

1018 } else if (StoreInst *St = dyn_cast(R)) {

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

1021 LSs.insert(U);

1022 }

1023 }

1024

1025

1026

1027

1028 if (!LSs.empty())

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

1030 }

1031

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

1033

1034 for (auto &FN : FNs) {

1035 GepNode *N = FN.first;

1036 UseSet &Us = FN.second;

1037 for (Use *U : Us)

1038 separateChainForNode(N, U, Loc);

1039 }

1040}

1041

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

1043

1044

1045 NodeChildrenMap NCM;

1046 NodeVect Roots;

1048

1049

1050

1051 for (GepNode *Root : Roots)

1052 recalculatePlacementRec(Root, NCM, Loc);

1053

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

1055

1057 for (GepNode *Root : Roots)

1058 adjustForInvariance(Root, NCM, Loc);

1059

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

1061 << LocationAsBlock(Loc));

1062 }

1064 for (GepNode *Root : Roots)

1065 separateConstantChains(Root, NCM, Loc);

1066 }

1068

1069

1070

1071

1072

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

1074}

1075

1079 << " for nodes:\n"

1080 << NA);

1081 unsigned Num = NA.size();

1082 GepNode *RN = NA[0];

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

1084

1086 Value *Input = RN->BaseVal;

1087 Type *InpTy = RN->PTy;

1088

1089 unsigned Idx = 0;

1090 do {

1092

1093

1094

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

1097 IdxList.push_back(ConstantInt::get(Int32Ty, 0));

1098 }

1099

1100

1101

1102 while (++Idx <= Num) {

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

1105 if (Idx < Num) {

1106

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

1108 break;

1109 }

1110 }

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

1114 if (Idx < Num) {

1115 Input = NewInst;

1116 InpTy = NA[Idx]->PTy;

1117 }

1118 } while (Idx <= Num);

1119

1120 return NewInst;

1121}

1122

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

1124 NodeChildrenMap &NCM) {

1125 NodeVect Work;

1126 Work.push_back(Node);

1127

1128 while (!Work.empty()) {

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

1130 GepNode *N = *First;

1131 Work.erase(First);

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

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

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

1135 UseSet &Us = UF->second;

1136 for (const auto &U : Us)

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

1138 }

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

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

1141 NodeVect &Cs = CF->second;

1143 }

1144 }

1145}

1146

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

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

1149 NodeChildrenMap NCM;

1150 NodeVect Roots;

1151

1152

1154

1155 while (!Roots.empty()) {

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

1158 Roots.erase(First);

1159

1160 NodeVect NA;

1161

1162

1163

1164

1165

1166 bool LastUsed = false;

1167 unsigned LastCN = 0;

1168

1169

1171 if (!LocV)

1172 continue;

1173 BasicBlock *LastB = cast(LocV);

1174 do {

1175 NA.push_back(Last);

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

1177 if (LastUsed)

1178 break;

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

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

1181 if (LastCN != 1)

1182 break;

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

1184 BasicBlock *ChildB = cast_or_null(Loc[Child]);

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

1186 break;

1187 Last = Child;

1188 } while (true);

1189

1191 if (LastUsed || LastCN > 0) {

1192 ValueVect Urs;

1193 getAllUsersForNode(Root, Urs, NCM);

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

1196 InsertAt = FirstUse;

1197 }

1198

1199

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

1201

1202

1203

1204 if (LastCN > 0) {

1205 NodeVect &Cs = NCM[Last];

1206 for (GepNode *CN : Cs) {

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

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

1209 CN->BaseVal = NewInst;

1210 Roots.push_back(CN);

1211 }

1212 }

1213

1214

1215

1216 if (LastUsed) {

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

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

1219 UseSet &Us = UF->second;

1220 for (Use *U : Us)

1221 U->set(NewInst);

1222 }

1223 }

1224}

1225

1226void HexagonCommonGEP::removeDeadCode() {

1227 ValueVect BO;

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

1229

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

1231 BasicBlock *B = cast(BO[i]);

1232 for (auto *DTN : children<DomTreeNode *>(DT->getNode(B)))

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

1234 }

1235

1238 ValueVect Ins;

1240 Ins.push_back(&I);

1241 for (Value *I : Ins) {

1244 In->eraseFromParent();

1245 }

1246 }

1247}

1248

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

1250 if (skipFunction(F))

1251 return false;

1252

1253

1256 if (isa(I) || isa(I))

1257 return false;

1258

1259 Fn = &F;

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

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

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

1263 Ctx = &F.getContext();

1264

1265 Nodes.clear();

1266 Uses.clear();

1268

1271

1272 collect();

1273 common();

1274

1275 NodeToValueMap Loc;

1276 computeNodePlacement(Loc);

1277 materialize(Loc);

1278 removeDeadCode();

1279

1280#ifdef EXPENSIVE_CHECKS

1281

1284#endif

1285 return true;

1286}

1287

1288namespace llvm {

1289

1291 return new HexagonCommonGEP();

1292 }

1293

1294}

This file defines the BumpPtrAllocator interface.

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

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

#define LLVM_ATTRIBUTE_UNUSED

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

Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx

DenseMap< Block *, BlockRelaxAux > Blocks

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)

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

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

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

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

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

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

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

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

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

static bool is_empty(const BasicBlock *B)

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

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

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

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

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

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

This file defines the SmallVector class.

Represent the analysis usage information of a pass.

AnalysisUsage & addRequired()

AnalysisUsage & addPreserved()

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

LLVM Basic Block Representation.

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.

This class represents an Operation in the Expression.

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.

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

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.

virtual bool runOnFunction(Function &F)=0

runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.

an instruction for type-safe pointer arithmetic to access elements of arrays and structs

bool isInBounds() const

Determine whether the GEP has the inbounds flag.

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

void setIsInBounds(bool b=true)

Set or clear the inbounds flag on this GEP instruction.

Type * getSourceElementType() const

This is an important class for using LLVM in a threaded context.

An instruction for reading from memory.

static unsigned getPointerOperandIndex()

LoopT * getParentLoop() const

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

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

PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...

static PassRegistry * getPassRegistry()

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

virtual void getAnalysisUsage(AnalysisUsage &) const

getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...

virtual StringRef getPassName() const

getPassName - Return a nice clean name for a pass.

PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...

A vector that has set insertion semantics.

void push_back(const T &Elt)

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

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

An instruction for storing to memory.

static unsigned getPointerOperandIndex()

StringRef - Represent a constant reference to a string, i.e.

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.

StringRef getStructName() const

bool isStructTy() const

True if this is an instance of StructType.

static IntegerType * getInt32Ty(LLVMContext &C)

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

user_iterator_impl< User > user_iterator

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)

@ C

The default llvm calling convention, compatible with C.

unsigned ID

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

initializer< Ty > init(const Ty &Val)

const_iterator begin(StringRef path LLVM_LIFETIME_BOUND, Style style=Style::native)

Get begin iterator over path.

const_iterator end(StringRef path LLVM_LIFETIME_BOUND)

Get end iterator over path.

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.

auto min_element(R &&Range)

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

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

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

void initializeHexagonCommonGEPPass(PassRegistry &)

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

Wrapper function to append range R to container C.

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)

raw_ostream & dbgs()

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

void report_fatal_error(Error Err, bool gen_crash_diag=true)

Report a serious error, calling any installed error handler.

@ First

Helpers to iterate all locations in the MemoryEffectsBase class.

FunctionPass * createHexagonCommonGEP()

DWARFExpression::Operation Op

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

void erase_if(Container &C, UnaryPredicate P)

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

GepNode(const GepNode *N)