1//===- HexagonCommonGEP.cpp -----------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "llvm/ADT/ArrayRef.h"
10#include "llvm/ADT/FoldingSet.h"
11#include "llvm/ADT/GraphTraits.h"
12#include "llvm/ADT/STLExtras.h"
13#include "llvm/ADT/SetVector.h"
14#include "llvm/ADT/SmallVector.h"
15#include "llvm/ADT/StringRef.h"
16#include "llvm/Analysis/LoopInfo.h"
17#include "llvm/Analysis/PostDominators.h"
18#include "llvm/IR/BasicBlock.h"
19#include "llvm/IR/Constant.h"
20#include "llvm/IR/Constants.h"
21#include "llvm/IR/DerivedTypes.h"
22#include "llvm/IR/Dominators.h"
23#include "llvm/IR/Function.h"
24#include "llvm/IR/Instruction.h"
25#include "llvm/IR/Instructions.h"
26#include "llvm/IR/Type.h"
27#include "llvm/IR/Use.h"
28#include "llvm/IR/User.h"
29#include "llvm/IR/Value.h"
30#include "llvm/IR/Verifier.h"
31#include "llvm/InitializePasses.h"
32#include "llvm/Pass.h"
33#include "llvm/Support/Allocator.h"
34#include "llvm/Support/Casting.h"
35#include "llvm/Support/CommandLine.h"
36#include "llvm/Support/Compiler.h"
37#include "llvm/Support/Debug.h"
38#include "llvm/Support/raw_ostream.h"
39#include "llvm/Transforms/Utils/Local.h"
40#include <algorithm>
41#include <cassert>
42#include <cstddef>
43#include <cstdint>
44#include <iterator>
45#include <map>
46#include <set>
47#include <utility>
48#include <vector>
49
50#define DEBUG_TYPE "commgep"
51
52using namespace llvm;
53
54static cl::opt<bool> OptSpeculate("commgep-speculate", cl::init(Val: true),
55 cl::Hidden);
56
57static cl::opt<bool> OptEnableInv("commgep-inv", cl::init(Val: true), cl::Hidden);
58
59static cl::opt<bool> OptEnableConst("commgep-const", cl::init(Val: true),
60 cl::Hidden);
61
62namespace llvm {
63
64 void initializeHexagonCommonGEPPass(PassRegistry&);
65
66} // end namespace llvm
67
68namespace {
69
70 struct GepNode;
71 using NodeSet = std::set<GepNode *>;
72 using NodeToValueMap = std::map<GepNode *, Value *>;
73 using NodeVect = std::vector<GepNode *>;
74 using NodeChildrenMap = std::map<GepNode *, NodeVect>;
75 using UseSet = SetVector<Use *>;
76 using NodeToUsesMap = std::map<GepNode *, UseSet>;
77
78 // Numbering map for gep nodes. Used to keep track of ordering for
79 // gep nodes.
80 struct NodeOrdering {
81 NodeOrdering() = default;
82
83 void insert(const GepNode *N) { Map.insert(x: std::make_pair(x&: N, y&: ++LastNum)); }
84 void clear() { Map.clear(); }
85
86 bool operator()(const GepNode *N1, const GepNode *N2) const {
87 auto F1 = Map.find(x: N1), F2 = Map.find(x: N2);
88 assert(F1 != Map.end() && F2 != Map.end());
89 return F1->second < F2->second;
90 }
91
92 private:
93 std::map<const GepNode *, unsigned> Map;
94 unsigned LastNum = 0;
95 };
96
97 class HexagonCommonGEP : public FunctionPass {
98 public:
99 static char ID;
100
101 HexagonCommonGEP() : FunctionPass(ID) {
102 initializeHexagonCommonGEPPass(*PassRegistry::getPassRegistry());
103 }
104
105 bool runOnFunction(Function &F) override;
106 StringRef getPassName() const override { return "Hexagon Common GEP"; }
107
108 void getAnalysisUsage(AnalysisUsage &AU) const override {
109 AU.addRequired<DominatorTreeWrapperPass>();
110 AU.addPreserved<DominatorTreeWrapperPass>();
111 AU.addRequired<PostDominatorTreeWrapperPass>();
112 AU.addPreserved<PostDominatorTreeWrapperPass>();
113 AU.addRequired<LoopInfoWrapperPass>();
114 AU.addPreserved<LoopInfoWrapperPass>();
115 FunctionPass::getAnalysisUsage(AU);
116 }
117
118 private:
119 using ValueToNodeMap = std::map<Value *, GepNode *>;
120 using ValueVect = std::vector<Value *>;
121 using NodeToValuesMap = std::map<GepNode *, ValueVect>;
122
123 void getBlockTraversalOrder(BasicBlock *Root, ValueVect &Order);
124 bool isHandledGepForm(GetElementPtrInst *GepI);
125 void processGepInst(GetElementPtrInst *GepI, ValueToNodeMap &NM);
126 void collect();
127 void common();
128
129 BasicBlock *recalculatePlacement(GepNode *Node, NodeChildrenMap &NCM,
130 NodeToValueMap &Loc);
131 BasicBlock *recalculatePlacementRec(GepNode *Node, NodeChildrenMap &NCM,
132 NodeToValueMap &Loc);
133 bool isInvariantIn(Value *Val, Loop *L);
134 bool isInvariantIn(GepNode *Node, Loop *L);
135 bool isInMainPath(BasicBlock *B, Loop *L);
136 BasicBlock *adjustForInvariance(GepNode *Node, NodeChildrenMap &NCM,
137 NodeToValueMap &Loc);
138 void separateChainForNode(GepNode *Node, Use *U, NodeToValueMap &Loc);
139 void separateConstantChains(GepNode *Node, NodeChildrenMap &NCM,
140 NodeToValueMap &Loc);
141 void computeNodePlacement(NodeToValueMap &Loc);
142
143 Value *fabricateGEP(NodeVect &NA, BasicBlock::iterator At,
144 BasicBlock *LocB);
145 void getAllUsersForNode(GepNode *Node, ValueVect &Values,
146 NodeChildrenMap &NCM);
147 void materialize(NodeToValueMap &Loc);
148
149 void removeDeadCode();
150
151 NodeVect Nodes;
152 NodeToUsesMap Uses;
153 NodeOrdering NodeOrder; // Node ordering, for deterministic behavior.
154 SpecificBumpPtrAllocator<GepNode> *Mem;
155 LLVMContext *Ctx;
156 LoopInfo *LI;
157 DominatorTree *DT;
158 PostDominatorTree *PDT;
159 Function *Fn;
160 };
161
162} // end anonymous namespace
163
164char HexagonCommonGEP::ID = 0;
165
166INITIALIZE_PASS_BEGIN(HexagonCommonGEP, "hcommgep", "Hexagon Common GEP",
167 false, false)
168INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
169INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
170INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
171INITIALIZE_PASS_END(HexagonCommonGEP, "hcommgep", "Hexagon Common GEP",
172 false, false)
173
174namespace {
175
176 struct GepNode {
177 enum {
178 None = 0,
179 Root = 0x01,
180 Internal = 0x02,
181 Used = 0x04,
182 InBounds = 0x08,
183 Pointer = 0x10, // See note below.
184 };
185 // Note: GEP indices generally traverse nested types, and so a GepNode
186 // (representing a single index) can be associated with some composite
187 // type. The exception is the GEP input, which is a pointer, and not
188 // a composite type (at least not in the sense of having sub-types).
189 // Also, the corresponding index plays a different role as well: it is
190 // simply added to the input pointer. Since pointer types are becoming
191 // opaque (i.e. are no longer going to include the pointee type), the
192 // two pieces of information (1) the fact that it's a pointer, and
193 // (2) the pointee type, need to be stored separately. The pointee type
194 // will be stored in the PTy member, while the fact that the node
195 // operates on a pointer will be reflected by the flag "Pointer".
196
197 uint32_t Flags = 0;
198 union {
199 GepNode *Parent;
200 Value *BaseVal;
201 };
202 Value *Idx = nullptr;
203 Type *PTy = nullptr; // Type indexed by this node. For pointer nodes
204 // this is the "pointee" type, and indexing a
205 // pointer does not change the type.
206
207 GepNode() : Parent(nullptr) {}
208 GepNode(const GepNode *N) : Flags(N->Flags), Idx(N->Idx), PTy(N->PTy) {
209 if (Flags & Root)
210 BaseVal = N->BaseVal;
211 else
212 Parent = N->Parent;
213 }
214
215 friend raw_ostream &operator<< (raw_ostream &OS, const GepNode &GN);
216 };
217
218 raw_ostream &operator<< (raw_ostream &OS, const GepNode &GN) {
219 OS << "{ {";
220 bool Comma = false;
221 if (GN.Flags & GepNode::Root) {
222 OS << "root";
223 Comma = true;
224 }
225 if (GN.Flags & GepNode::Internal) {
226 if (Comma)
227 OS << ',';
228 OS << "internal";
229 Comma = true;
230 }
231 if (GN.Flags & GepNode::Used) {
232 if (Comma)
233 OS << ',';
234 OS << "used";
235 }
236 if (GN.Flags & GepNode::InBounds) {
237 if (Comma)
238 OS << ',';
239 OS << "inbounds";
240 }
241 if (GN.Flags & GepNode::Pointer) {
242 if (Comma)
243 OS << ',';
244 OS << "pointer";
245 }
246 OS << "} ";
247 if (GN.Flags & GepNode::Root)
248 OS << "BaseVal:" << GN.BaseVal->getName() << '(' << GN.BaseVal << ')';
249 else
250 OS << "Parent:" << GN.Parent;
251
252 OS << " Idx:";
253 if (ConstantInt *CI = dyn_cast<ConstantInt>(Val: GN.Idx))
254 OS << CI->getValue().getSExtValue();
255 else if (GN.Idx->hasName())
256 OS << GN.Idx->getName();
257 else
258 OS << "<anon> =" << *GN.Idx;
259
260 OS << " PTy:";
261 if (GN.PTy->isStructTy()) {
262 StructType *STy = cast<StructType>(Val: GN.PTy);
263 if (!STy->isLiteral())
264 OS << GN.PTy->getStructName();
265 else
266 OS << "<anon-struct>:" << *STy;
267 }
268 else
269 OS << *GN.PTy;
270 OS << " }";
271 return OS;
272 }
273
274 template <typename NodeContainer>
275 void dump_node_container(raw_ostream &OS, const NodeContainer &S) {
276 using const_iterator = typename NodeContainer::const_iterator;
277
278 for (const_iterator I = S.begin(), E = S.end(); I != E; ++I)
279 OS << *I << ' ' << **I << '\n';
280 }
281
282 raw_ostream &operator<< (raw_ostream &OS,
283 const NodeVect &S) LLVM_ATTRIBUTE_UNUSED;
284 raw_ostream &operator<< (raw_ostream &OS, const NodeVect &S) {
285 dump_node_container(OS, S);
286 return OS;
287 }
288
289 raw_ostream &operator<< (raw_ostream &OS,
290 const NodeToUsesMap &M) LLVM_ATTRIBUTE_UNUSED;
291 raw_ostream &operator<< (raw_ostream &OS, const NodeToUsesMap &M){
292 for (const auto &I : M) {
293 const UseSet &Us = I.second;
294 OS << I.first << " -> #" << Us.size() << '{';
295 for (const Use *U : Us) {
296 User *R = U->getUser();
297 if (R->hasName())
298 OS << ' ' << R->getName();
299 else
300 OS << " <?>(" << *R << ')';
301 }
302 OS << " }\n";
303 }
304 return OS;
305 }
306
307 struct in_set {
308 in_set(const NodeSet &S) : NS(S) {}
309
310 bool operator() (GepNode *N) const {
311 return NS.find(x: N) != NS.end();
312 }
313
314 private:
315 const NodeSet &NS;
316 };
317
318} // end anonymous namespace
319
320inline void *operator new(size_t, SpecificBumpPtrAllocator<GepNode> &A) {
321 return A.Allocate();
322}
323
324void HexagonCommonGEP::getBlockTraversalOrder(BasicBlock *Root,
325 ValueVect &Order) {
326 // Compute block ordering for a typical DT-based traversal of the flow
327 // graph: "before visiting a block, all of its dominators must have been
328 // visited".
329
330 Order.push_back(x: Root);
331 for (auto *DTN : children<DomTreeNode*>(G: DT->getNode(BB: Root)))
332 getBlockTraversalOrder(Root: DTN->getBlock(), Order);
333}
334
335bool HexagonCommonGEP::isHandledGepForm(GetElementPtrInst *GepI) {
336 // No vector GEPs.
337 if (!GepI->getType()->isPointerTy())
338 return false;
339 // No GEPs without any indices. (Is this possible?)
340 if (GepI->idx_begin() == GepI->idx_end())
341 return false;
342 return true;
343}
344
345void HexagonCommonGEP::processGepInst(GetElementPtrInst *GepI,
346 ValueToNodeMap &NM) {
347 LLVM_DEBUG(dbgs() << "Visiting GEP: " << *GepI << '\n');
348 GepNode *N = new (*Mem) GepNode;
349 Value *PtrOp = GepI->getPointerOperand();
350 uint32_t InBounds = GepI->isInBounds() ? GepNode::InBounds : 0;
351 ValueToNodeMap::iterator F = NM.find(x: PtrOp);
352 if (F == NM.end()) {
353 N->BaseVal = PtrOp;
354 N->Flags |= GepNode::Root | InBounds;
355 } else {
356 // If PtrOp was a GEP instruction, it must have already been processed.
357 // The ValueToNodeMap entry for it is the last gep node in the generated
358 // chain. Link to it here.
359 N->Parent = F->second;
360 }
361 N->PTy = GepI->getSourceElementType();
362 N->Flags |= GepNode::Pointer;
363 N->Idx = *GepI->idx_begin();
364
365 // Collect the list of users of this GEP instruction. Will add it to the
366 // last node created for it.
367 UseSet Us;
368 for (Value::user_iterator UI = GepI->user_begin(), UE = GepI->user_end();
369 UI != UE; ++UI) {
370 // Check if this gep is used by anything other than other geps that
371 // we will process.
372 if (isa<GetElementPtrInst>(Val: *UI)) {
373 GetElementPtrInst *UserG = cast<GetElementPtrInst>(Val: *UI);
374 if (isHandledGepForm(GepI: UserG))
375 continue;
376 }
377 Us.insert(X: &UI.getUse());
378 }
379 Nodes.push_back(x: N);
380 NodeOrder.insert(N);
381
382 // Skip the first index operand, since it was already handled above. This
383 // dereferences the pointer operand.
384 GepNode *PN = N;
385 Type *PtrTy = GepI->getSourceElementType();
386 for (Use &U : llvm::drop_begin(RangeOrContainer: GepI->indices())) {
387 Value *Op = U;
388 GepNode *Nx = new (*Mem) GepNode;
389 Nx->Parent = PN; // Link Nx to the previous node.
390 Nx->Flags |= GepNode::Internal | InBounds;
391 Nx->PTy = PtrTy;
392 Nx->Idx = Op;
393 Nodes.push_back(x: Nx);
394 NodeOrder.insert(N: Nx);
395 PN = Nx;
396
397 PtrTy = GetElementPtrInst::getTypeAtIndex(Ty: PtrTy, Idx: Op);
398 }
399
400 // After last node has been created, update the use information.
401 if (!Us.empty()) {
402 PN->Flags |= GepNode::Used;
403 Uses[PN].insert(Start: Us.begin(), End: Us.end());
404 }
405
406 // Link the last node with the originating GEP instruction. This is to
407 // help with linking chained GEP instructions.
408 NM.insert(x: std::make_pair(x&: GepI, y&: PN));
409}
410
411void HexagonCommonGEP::collect() {
412 // Establish depth-first traversal order of the dominator tree.
413 ValueVect BO;
414 getBlockTraversalOrder(Root: &Fn->front(), Order&: BO);
415
416 // The creation of gep nodes requires DT-traversal. When processing a GEP
417 // instruction that uses another GEP instruction as the base pointer, the
418 // gep node for the base pointer should already exist.
419 ValueToNodeMap NM;
420 for (Value *I : BO) {
421 BasicBlock *B = cast<BasicBlock>(Val: I);
422 for (Instruction &J : *B)
423 if (auto *GepI = dyn_cast<GetElementPtrInst>(Val: &J))
424 if (isHandledGepForm(GepI))
425 processGepInst(GepI, NM);
426 }
427
428 LLVM_DEBUG(dbgs() << "Gep nodes after initial collection:\n" << Nodes);
429}
430
431static void invert_find_roots(const NodeVect &Nodes, NodeChildrenMap &NCM,
432 NodeVect &Roots) {
433 for (GepNode *N : Nodes) {
434 if (N->Flags & GepNode::Root) {
435 Roots.push_back(x: N);
436 continue;
437 }
438 GepNode *PN = N->Parent;
439 NCM[PN].push_back(x: N);
440 }
441}
442
443static void nodes_for_root(GepNode *Root, NodeChildrenMap &NCM,
444 NodeSet &Nodes) {
445 NodeVect Work;
446 Work.push_back(x: Root);
447 Nodes.insert(x: Root);
448
449 while (!Work.empty()) {
450 NodeVect::iterator First = Work.begin();
451 GepNode *N = *First;
452 Work.erase(position: First);
453 NodeChildrenMap::iterator CF = NCM.find(x: N);
454 if (CF != NCM.end()) {
455 llvm::append_range(C&: Work, R&: CF->second);
456 Nodes.insert(first: CF->second.begin(), last: CF->second.end());
457 }
458 }
459}
460
461namespace {
462
463 using NodeSymRel = std::set<NodeSet>;
464 using NodePair = std::pair<GepNode *, GepNode *>;
465 using NodePairSet = std::set<NodePair>;
466
467} // end anonymous namespace
468
469static const NodeSet *node_class(GepNode *N, NodeSymRel &Rel) {
470 for (const NodeSet &S : Rel)
471 if (S.count(x: N))
472 return &S;
473 return nullptr;
474}
475
476 // Create an ordered pair of GepNode pointers. The pair will be used in
477 // determining equality. The only purpose of the ordering is to eliminate
478 // duplication due to the commutativity of equality/non-equality.
479static NodePair node_pair(GepNode *N1, GepNode *N2) {
480 uintptr_t P1 = reinterpret_cast<uintptr_t>(N1);
481 uintptr_t P2 = reinterpret_cast<uintptr_t>(N2);
482 if (P1 <= P2)
483 return std::make_pair(x&: N1, y&: N2);
484 return std::make_pair(x&: N2, y&: N1);
485}
486
487static unsigned node_hash(GepNode *N) {
488 // Include everything except flags and parent.
489 FoldingSetNodeID ID;
490 ID.AddPointer(Ptr: N->Idx);
491 ID.AddPointer(Ptr: N->PTy);
492 return ID.ComputeHash();
493}
494
495static bool node_eq(GepNode *N1, GepNode *N2, NodePairSet &Eq,
496 NodePairSet &Ne) {
497 // Don't cache the result for nodes with different hashes. The hash
498 // comparison is fast enough.
499 if (node_hash(N: N1) != node_hash(N: N2))
500 return false;
501
502 NodePair NP = node_pair(N1, N2);
503 NodePairSet::iterator FEq = Eq.find(x: NP);
504 if (FEq != Eq.end())
505 return true;
506 NodePairSet::iterator FNe = Ne.find(x: NP);
507 if (FNe != Ne.end())
508 return false;
509 // Not previously compared.
510 bool Root1 = N1->Flags & GepNode::Root;
511 uint32_t CmpFlags = GepNode::Root | GepNode::Pointer;
512 bool Different = (N1->Flags & CmpFlags) != (N2->Flags & CmpFlags);
513 NodePair P = node_pair(N1, N2);
514 // If the root/pointer flags have different values, the nodes are
515 // different.
516 // If both nodes are root nodes, but their base pointers differ,
517 // they are different.
518 if (Different || (Root1 && N1->BaseVal != N2->BaseVal)) {
519 Ne.insert(x: P);
520 return false;
521 }
522 // Here the root/pointer flags are identical, and for root nodes the
523 // base pointers are equal, so the root nodes are equal.
524 // For non-root nodes, compare their parent nodes.
525 if (Root1 || node_eq(N1: N1->Parent, N2: N2->Parent, Eq, Ne)) {
526 Eq.insert(x: P);
527 return true;
528 }
529 return false;
530}
531
532void HexagonCommonGEP::common() {
533 // The essence of this commoning is finding gep nodes that are equal.
534 // To do this we need to compare all pairs of nodes. To save time,
535 // first, partition the set of all nodes into sets of potentially equal
536 // nodes, and then compare pairs from within each partition.
537 using NodeSetMap = std::map<unsigned, NodeSet>;
538 NodeSetMap MaybeEq;
539
540 for (GepNode *N : Nodes) {
541 unsigned H = node_hash(N);
542 MaybeEq[H].insert(x: N);
543 }
544
545 // Compute the equivalence relation for the gep nodes. Use two caches,
546 // one for equality and the other for non-equality.
547 NodeSymRel EqRel; // Equality relation (as set of equivalence classes).
548 NodePairSet Eq, Ne; // Caches.
549 for (auto &I : MaybeEq) {
550 NodeSet &S = I.second;
551 for (NodeSet::iterator NI = S.begin(), NE = S.end(); NI != NE; ++NI) {
552 GepNode *N = *NI;
553 // If node already has a class, then the class must have been created
554 // in a prior iteration of this loop. Since equality is transitive,
555 // nothing more will be added to that class, so skip it.
556 if (node_class(N, Rel&: EqRel))
557 continue;
558
559 // Create a new class candidate now.
560 NodeSet C;
561 for (NodeSet::iterator NJ = std::next(x: NI); NJ != NE; ++NJ)
562 if (node_eq(N1: N, N2: *NJ, Eq, Ne))
563 C.insert(x: *NJ);
564 // If Tmp is empty, N would be the only element in it. Don't bother
565 // creating a class for it then.
566 if (!C.empty()) {
567 C.insert(x: N); // Finalize the set before adding it to the relation.
568 std::pair<NodeSymRel::iterator, bool> Ins = EqRel.insert(x: C);
569 (void)Ins;
570 assert(Ins.second && "Cannot add a class");
571 }
572 }
573 }
574
575 LLVM_DEBUG({
576 dbgs() << "Gep node equality:\n";
577 for (NodePairSet::iterator I = Eq.begin(), E = Eq.end(); I != E; ++I)
578 dbgs() << "{ " << I->first << ", " << I->second << " }\n";
579
580 dbgs() << "Gep equivalence classes:\n";
581 for (const NodeSet &S : EqRel) {
582 dbgs() << '{';
583 for (NodeSet::const_iterator J = S.begin(), F = S.end(); J != F; ++J) {
584 if (J != S.begin())
585 dbgs() << ',';
586 dbgs() << ' ' << *J;
587 }
588 dbgs() << " }\n";
589 }
590 });
591
592 // Create a projection from a NodeSet to the minimal element in it.
593 using ProjMap = std::map<const NodeSet *, GepNode *>;
594 ProjMap PM;
595 for (const NodeSet &S : EqRel) {
596 GepNode *Min = *llvm::min_element(Range: S, C: NodeOrder);
597 std::pair<ProjMap::iterator,bool> Ins = PM.insert(x: std::make_pair(x: &S, y&: Min));
598 (void)Ins;
599 assert(Ins.second && "Cannot add minimal element");
600
601 // Update the min element's flags, and user list.
602 uint32_t Flags = 0;
603 UseSet &MinUs = Uses[Min];
604 for (GepNode *N : S) {
605 uint32_t NF = N->Flags;
606 // If N is used, append all original values of N to the list of
607 // original values of Min.
608 if (NF & GepNode::Used)
609 MinUs.insert(Start: Uses[N].begin(), End: Uses[N].end());
610 Flags |= NF;
611 }
612 if (MinUs.empty())
613 Uses.erase(x: Min);
614
615 // The collected flags should include all the flags from the min element.
616 assert((Min->Flags & Flags) == Min->Flags);
617 Min->Flags = Flags;
618 }
619
620 // Commoning: for each non-root gep node, replace "Parent" with the
621 // selected (minimum) node from the corresponding equivalence class.
622 // If a given parent does not have an equivalence class, leave it
623 // unchanged (it means that it's the only element in its class).
624 for (GepNode *N : Nodes) {
625 if (N->Flags & GepNode::Root)
626 continue;
627 const NodeSet *PC = node_class(N: N->Parent, Rel&: EqRel);
628 if (!PC)
629 continue;
630 ProjMap::iterator F = PM.find(x: PC);
631 if (F == PM.end())
632 continue;
633 // Found a replacement, use it.
634 GepNode *Rep = F->second;
635 N->Parent = Rep;
636 }
637
638 LLVM_DEBUG(dbgs() << "Gep nodes after commoning:\n" << Nodes);
639
640 // Finally, erase the nodes that are no longer used.
641 NodeSet Erase;
642 for (GepNode *N : Nodes) {
643 const NodeSet *PC = node_class(N, Rel&: EqRel);
644 if (!PC)
645 continue;
646 ProjMap::iterator F = PM.find(x: PC);
647 if (F == PM.end())
648 continue;
649 if (N == F->second)
650 continue;
651 // Node for removal.
652 Erase.insert(x: N);
653 }
654 erase_if(C&: Nodes, P: in_set(Erase));
655
656 LLVM_DEBUG(dbgs() << "Gep nodes after post-commoning cleanup:\n" << Nodes);
657}
658
659template <typename T>
660static BasicBlock *nearest_common_dominator(DominatorTree *DT, T &Blocks) {
661 LLVM_DEBUG({
662 dbgs() << "NCD of {";
663 for (typename T::iterator I = Blocks.begin(), E = Blocks.end(); I != E;
664 ++I) {
665 if (!*I)
666 continue;
667 BasicBlock *B = cast<BasicBlock>(*I);
668 dbgs() << ' ' << B->getName();
669 }
670 dbgs() << " }\n";
671 });
672
673 // Allow null basic blocks in Blocks. In such cases, return nullptr.
674 typename T::iterator I = Blocks.begin(), E = Blocks.end();
675 if (I == E || !*I)
676 return nullptr;
677 BasicBlock *Dom = cast<BasicBlock>(*I);
678 while (++I != E) {
679 BasicBlock *B = cast_or_null<BasicBlock>(*I);
680 Dom = B ? DT->findNearestCommonDominator(A: Dom, B) : nullptr;
681 if (!Dom)
682 return nullptr;
683 }
684 LLVM_DEBUG(dbgs() << "computed:" << Dom->getName() << '\n');
685 return Dom;
686}
687
688template <typename T>
689static BasicBlock *nearest_common_dominatee(DominatorTree *DT, T &Blocks) {
690 // If two blocks, A and B, dominate a block C, then A dominates B,
691 // or B dominates A.
692 typename T::iterator I = Blocks.begin(), E = Blocks.end();
693 // Find the first non-null block.
694 while (I != E && !*I)
695 ++I;
696 if (I == E)
697 return DT->getRoot();
698 BasicBlock *DomB = cast<BasicBlock>(*I);
699 while (++I != E) {
700 if (!*I)
701 continue;
702 BasicBlock *B = cast<BasicBlock>(*I);
703 if (DT->dominates(A: B, B: DomB))
704 continue;
705 if (!DT->dominates(A: DomB, B))
706 return nullptr;
707 DomB = B;
708 }
709 return DomB;
710}
711
712// Find the first use in B of any value from Values. If no such use,
713// return B->end().
714template <typename T>
715static BasicBlock::iterator first_use_of_in_block(T &Values, BasicBlock *B) {
716 BasicBlock::iterator FirstUse = B->end(), BEnd = B->end();
717
718 using iterator = typename T::iterator;
719
720 for (iterator I = Values.begin(), E = Values.end(); I != E; ++I) {
721 Value *V = *I;
722 // If V is used in a PHI node, the use belongs to the incoming block,
723 // not the block with the PHI node. In the incoming block, the use
724 // would be considered as being at the end of it, so it cannot
725 // influence the position of the first use (which is assumed to be
726 // at the end to start with).
727 if (isa<PHINode>(Val: V))
728 continue;
729 if (!isa<Instruction>(Val: V))
730 continue;
731 Instruction *In = cast<Instruction>(Val: V);
732 if (In->getParent() != B)
733 continue;
734 BasicBlock::iterator It = In->getIterator();
735 if (std::distance(first: FirstUse, last: BEnd) < std::distance(first: It, last: BEnd))
736 FirstUse = It;
737 }
738 return FirstUse;
739}
740
741static bool is_empty(const BasicBlock *B) {
742 return B->empty() || (&*B->begin() == B->getTerminator());
743}
744
745BasicBlock *HexagonCommonGEP::recalculatePlacement(GepNode *Node,
746 NodeChildrenMap &NCM, NodeToValueMap &Loc) {
747 LLVM_DEBUG(dbgs() << "Loc for node:" << Node << '\n');
748 // Recalculate the placement for Node, assuming that the locations of
749 // its children in Loc are valid.
750 // Return nullptr if there is no valid placement for Node (for example, it
751 // uses an index value that is not available at the location required
752 // to dominate all children, etc.).
753
754 // Find the nearest common dominator for:
755 // - all users, if the node is used, and
756 // - all children.
757 ValueVect Bs;
758 if (Node->Flags & GepNode::Used) {
759 // Append all blocks with uses of the original values to the
760 // block vector Bs.
761 NodeToUsesMap::iterator UF = Uses.find(x: Node);
762 assert(UF != Uses.end() && "Used node with no use information");
763 UseSet &Us = UF->second;
764 for (Use *U : Us) {
765 User *R = U->getUser();
766 if (!isa<Instruction>(Val: R))
767 continue;
768 BasicBlock *PB = isa<PHINode>(Val: R)
769 ? cast<PHINode>(Val: R)->getIncomingBlock(U: *U)
770 : cast<Instruction>(Val: R)->getParent();
771 Bs.push_back(x: PB);
772 }
773 }
774 // Append the location of each child.
775 NodeChildrenMap::iterator CF = NCM.find(x: Node);
776 if (CF != NCM.end()) {
777 NodeVect &Cs = CF->second;
778 for (GepNode *CN : Cs) {
779 NodeToValueMap::iterator LF = Loc.find(x: CN);
780 // If the child is only used in GEP instructions (i.e. is not used in
781 // non-GEP instructions), the nearest dominator computed for it may
782 // have been null. In such case it won't have a location available.
783 if (LF == Loc.end())
784 continue;
785 Bs.push_back(x: LF->second);
786 }
787 }
788
789 BasicBlock *DomB = nearest_common_dominator(DT, Blocks&: Bs);
790 if (!DomB)
791 return nullptr;
792 // Check if the index used by Node dominates the computed dominator.
793 Instruction *IdxI = dyn_cast<Instruction>(Val: Node->Idx);
794 if (IdxI && !DT->dominates(A: IdxI->getParent(), B: DomB))
795 return nullptr;
796
797 // Avoid putting nodes into empty blocks.
798 while (is_empty(B: DomB)) {
799 DomTreeNode *N = (*DT)[DomB]->getIDom();
800 if (!N)
801 break;
802 DomB = N->getBlock();
803 }
804
805 // Otherwise, DomB is fine. Update the location map.
806 Loc[Node] = DomB;
807 return DomB;
808}
809
810BasicBlock *HexagonCommonGEP::recalculatePlacementRec(GepNode *Node,
811 NodeChildrenMap &NCM, NodeToValueMap &Loc) {
812 LLVM_DEBUG(dbgs() << "LocRec begin for node:" << Node << '\n');
813 // Recalculate the placement of Node, after recursively recalculating the
814 // placements of all its children.
815 NodeChildrenMap::iterator CF = NCM.find(x: Node);
816 if (CF != NCM.end()) {
817 NodeVect &Cs = CF->second;
818 for (GepNode *C : Cs)
819 recalculatePlacementRec(Node: C, NCM, Loc);
820 }
821 BasicBlock *LB = recalculatePlacement(Node, NCM, Loc);
822 LLVM_DEBUG(dbgs() << "LocRec end for node:" << Node << '\n');
823 return LB;
824}
825
826bool HexagonCommonGEP::isInvariantIn(Value *Val, Loop *L) {
827 if (isa<Constant>(Val) || isa<Argument>(Val))
828 return true;
829 Instruction *In = dyn_cast<Instruction>(Val);
830 if (!In)
831 return false;
832 BasicBlock *HdrB = L->getHeader(), *DefB = In->getParent();
833 return DT->properlyDominates(A: DefB, B: HdrB);
834}
835
836bool HexagonCommonGEP::isInvariantIn(GepNode *Node, Loop *L) {
837 if (Node->Flags & GepNode::Root)
838 if (!isInvariantIn(Val: Node->BaseVal, L))
839 return false;
840 return isInvariantIn(Val: Node->Idx, L);
841}
842
843bool HexagonCommonGEP::isInMainPath(BasicBlock *B, Loop *L) {
844 BasicBlock *HB = L->getHeader();
845 BasicBlock *LB = L->getLoopLatch();
846 // B must post-dominate the loop header or dominate the loop latch.
847 if (PDT->dominates(A: B, B: HB))
848 return true;
849 if (LB && DT->dominates(A: B, B: LB))
850 return true;
851 return false;
852}
853
854static BasicBlock *preheader(DominatorTree *DT, Loop *L) {
855 if (BasicBlock *PH = L->getLoopPreheader())
856 return PH;
857 if (!OptSpeculate)
858 return nullptr;
859 DomTreeNode *DN = DT->getNode(BB: L->getHeader());
860 if (!DN)
861 return nullptr;
862 return DN->getIDom()->getBlock();
863}
864
865BasicBlock *HexagonCommonGEP::adjustForInvariance(GepNode *Node,
866 NodeChildrenMap &NCM, NodeToValueMap &Loc) {
867 // Find the "topmost" location for Node: it must be dominated by both,
868 // its parent (or the BaseVal, if it's a root node), and by the index
869 // value.
870 ValueVect Bs;
871 if (Node->Flags & GepNode::Root) {
872 if (Instruction *PIn = dyn_cast<Instruction>(Val: Node->BaseVal))
873 Bs.push_back(x: PIn->getParent());
874 } else {
875 Bs.push_back(x: Loc[Node->Parent]);
876 }
877 if (Instruction *IIn = dyn_cast<Instruction>(Val: Node->Idx))
878 Bs.push_back(x: IIn->getParent());
879 BasicBlock *TopB = nearest_common_dominatee(DT, Blocks&: Bs);
880
881 // Traverse the loop nest upwards until we find a loop in which Node
882 // is no longer invariant, or until we get to the upper limit of Node's
883 // placement. The traversal will also stop when a suitable "preheader"
884 // cannot be found for a given loop. The "preheader" may actually be
885 // a regular block outside of the loop (i.e. not guarded), in which case
886 // the Node will be speculated.
887 // For nodes that are not in the main path of the containing loop (i.e.
888 // are not executed in each iteration), do not move them out of the loop.
889 BasicBlock *LocB = cast_or_null<BasicBlock>(Val: Loc[Node]);
890 if (LocB) {
891 Loop *Lp = LI->getLoopFor(BB: LocB);
892 while (Lp) {
893 if (!isInvariantIn(Node, L: Lp) || !isInMainPath(B: LocB, L: Lp))
894 break;
895 BasicBlock *NewLoc = preheader(DT, L: Lp);
896 if (!NewLoc || !DT->dominates(A: TopB, B: NewLoc))
897 break;
898 Lp = Lp->getParentLoop();
899 LocB = NewLoc;
900 }
901 }
902 Loc[Node] = LocB;
903
904 // Recursively compute the locations of all children nodes.
905 NodeChildrenMap::iterator CF = NCM.find(x: Node);
906 if (CF != NCM.end()) {
907 NodeVect &Cs = CF->second;
908 for (GepNode *C : Cs)
909 adjustForInvariance(Node: C, NCM, Loc);
910 }
911 return LocB;
912}
913
914namespace {
915
916 struct LocationAsBlock {
917 LocationAsBlock(const NodeToValueMap &L) : Map(L) {}
918
919 const NodeToValueMap &Map;
920 };
921
922 raw_ostream &operator<< (raw_ostream &OS,
923 const LocationAsBlock &Loc) LLVM_ATTRIBUTE_UNUSED ;
924 raw_ostream &operator<< (raw_ostream &OS, const LocationAsBlock &Loc) {
925 for (const auto &I : Loc.Map) {
926 OS << I.first << " -> ";
927 if (BasicBlock *B = cast_or_null<BasicBlock>(Val: I.second))
928 OS << B->getName() << '(' << B << ')';
929 else
930 OS << "<null-block>";
931 OS << '\n';
932 }
933 return OS;
934 }
935
936 inline bool is_constant(GepNode *N) {
937 return isa<ConstantInt>(Val: N->Idx);
938 }
939
940} // end anonymous namespace
941
942void HexagonCommonGEP::separateChainForNode(GepNode *Node, Use *U,
943 NodeToValueMap &Loc) {
944 User *R = U->getUser();
945 LLVM_DEBUG(dbgs() << "Separating chain for node (" << Node << ") user: " << *R
946 << '\n');
947 BasicBlock *PB = cast<Instruction>(Val: R)->getParent();
948
949 GepNode *N = Node;
950 GepNode *C = nullptr, *NewNode = nullptr;
951 while (is_constant(N) && !(N->Flags & GepNode::Root)) {
952 // XXX if (single-use) dont-replicate;
953 GepNode *NewN = new (*Mem) GepNode(N);
954 Nodes.push_back(x: NewN);
955 Loc[NewN] = PB;
956
957 if (N == Node)
958 NewNode = NewN;
959 NewN->Flags &= ~GepNode::Used;
960 if (C)
961 C->Parent = NewN;
962 C = NewN;
963 N = N->Parent;
964 }
965 if (!NewNode)
966 return;
967
968 // Move over all uses that share the same user as U from Node to NewNode.
969 NodeToUsesMap::iterator UF = Uses.find(x: Node);
970 assert(UF != Uses.end());
971 UseSet &Us = UF->second;
972 UseSet NewUs;
973 for (Use *U : Us) {
974 if (U->getUser() == R)
975 NewUs.insert(X: U);
976 }
977 for (Use *U : NewUs)
978 Us.remove(X: U); // erase takes an iterator.
979
980 if (Us.empty()) {
981 Node->Flags &= ~GepNode::Used;
982 Uses.erase(position: UF);
983 }
984
985 // Should at least have U in NewUs.
986 NewNode->Flags |= GepNode::Used;
987 LLVM_DEBUG(dbgs() << "new node: " << NewNode << " " << *NewNode << '\n');
988 assert(!NewUs.empty());
989 Uses[NewNode] = NewUs;
990}
991
992void HexagonCommonGEP::separateConstantChains(GepNode *Node,
993 NodeChildrenMap &NCM, NodeToValueMap &Loc) {
994 // First approximation: extract all chains.
995 NodeSet Ns;
996 nodes_for_root(Root: Node, NCM, Nodes&: Ns);
997
998 LLVM_DEBUG(dbgs() << "Separating constant chains for node: " << Node << '\n');
999 // Collect all used nodes together with the uses from loads and stores,
1000 // where the GEP node could be folded into the load/store instruction.
1001 NodeToUsesMap FNs; // Foldable nodes.
1002 for (GepNode *N : Ns) {
1003 if (!(N->Flags & GepNode::Used))
1004 continue;
1005 NodeToUsesMap::iterator UF = Uses.find(x: N);
1006 assert(UF != Uses.end());
1007 UseSet &Us = UF->second;
1008 // Loads/stores that use the node N.
1009 UseSet LSs;
1010 for (Use *U : Us) {
1011 User *R = U->getUser();
1012 // We're interested in uses that provide the address. It can happen
1013 // that the value may also be provided via GEP, but we won't handle
1014 // those cases here for now.
1015 if (LoadInst *Ld = dyn_cast<LoadInst>(Val: R)) {
1016 unsigned PtrX = LoadInst::getPointerOperandIndex();
1017 if (&Ld->getOperandUse(i: PtrX) == U)
1018 LSs.insert(X: U);
1019 } else if (StoreInst *St = dyn_cast<StoreInst>(Val: R)) {
1020 unsigned PtrX = StoreInst::getPointerOperandIndex();
1021 if (&St->getOperandUse(i: PtrX) == U)
1022 LSs.insert(X: U);
1023 }
1024 }
1025 // Even if the total use count is 1, separating the chain may still be
1026 // beneficial, since the constant chain may be longer than the GEP alone
1027 // would be (e.g. if the parent node has a constant index and also has
1028 // other children).
1029 if (!LSs.empty())
1030 FNs.insert(x: std::make_pair(x&: N, y&: LSs));
1031 }
1032
1033 LLVM_DEBUG(dbgs() << "Nodes with foldable users:\n" << FNs);
1034
1035 for (auto &FN : FNs) {
1036 GepNode *N = FN.first;
1037 UseSet &Us = FN.second;
1038 for (Use *U : Us)
1039 separateChainForNode(Node: N, U, Loc);
1040 }
1041}
1042
1043void HexagonCommonGEP::computeNodePlacement(NodeToValueMap &Loc) {
1044 // Compute the inverse of the Node.Parent links. Also, collect the set
1045 // of root nodes.
1046 NodeChildrenMap NCM;
1047 NodeVect Roots;
1048 invert_find_roots(Nodes, NCM, Roots);
1049
1050 // Compute the initial placement determined by the users' locations, and
1051 // the locations of the child nodes.
1052 for (GepNode *Root : Roots)
1053 recalculatePlacementRec(Node: Root, NCM, Loc);
1054
1055 LLVM_DEBUG(dbgs() << "Initial node placement:\n" << LocationAsBlock(Loc));
1056
1057 if (OptEnableInv) {
1058 for (GepNode *Root : Roots)
1059 adjustForInvariance(Node: Root, NCM, Loc);
1060
1061 LLVM_DEBUG(dbgs() << "Node placement after adjustment for invariance:\n"
1062 << LocationAsBlock(Loc));
1063 }
1064 if (OptEnableConst) {
1065 for (GepNode *Root : Roots)
1066 separateConstantChains(Node: Root, NCM, Loc);
1067 }
1068 LLVM_DEBUG(dbgs() << "Node use information:\n" << Uses);
1069
1070 // At the moment, there is no further refinement of the initial placement.
1071 // Such a refinement could include splitting the nodes if they are placed
1072 // too far from some of its users.
1073
1074 LLVM_DEBUG(dbgs() << "Final node placement:\n" << LocationAsBlock(Loc));
1075}
1076
1077Value *HexagonCommonGEP::fabricateGEP(NodeVect &NA, BasicBlock::iterator At,
1078 BasicBlock *LocB) {
1079 LLVM_DEBUG(dbgs() << "Fabricating GEP in " << LocB->getName()
1080 << " for nodes:\n"
1081 << NA);
1082 unsigned Num = NA.size();
1083 GepNode *RN = NA[0];
1084 assert((RN->Flags & GepNode::Root) && "Creating GEP for non-root");
1085
1086 GetElementPtrInst *NewInst = nullptr;
1087 Value *Input = RN->BaseVal;
1088 Type *InpTy = RN->PTy;
1089
1090 unsigned Idx = 0;
1091 do {
1092 SmallVector<Value*, 4> IdxList;
1093 // If the type of the input of the first node is not a pointer,
1094 // we need to add an artificial i32 0 to the indices (because the
1095 // actual input in the IR will be a pointer).
1096 if (!(NA[Idx]->Flags & GepNode::Pointer)) {
1097 Type *Int32Ty = Type::getInt32Ty(C&: *Ctx);
1098 IdxList.push_back(Elt: ConstantInt::get(Ty: Int32Ty, V: 0));
1099 }
1100
1101 // Keep adding indices from NA until we have to stop and generate
1102 // an "intermediate" GEP.
1103 while (++Idx <= Num) {
1104 GepNode *N = NA[Idx-1];
1105 IdxList.push_back(Elt: N->Idx);
1106 if (Idx < Num) {
1107 // We have to stop if we reach a pointer.
1108 if (NA[Idx]->Flags & GepNode::Pointer)
1109 break;
1110 }
1111 }
1112 NewInst = GetElementPtrInst::Create(PointeeType: InpTy, Ptr: Input, IdxList, NameStr: "cgep", InsertBefore: At);
1113 NewInst->setIsInBounds(RN->Flags & GepNode::InBounds);
1114 LLVM_DEBUG(dbgs() << "new GEP: " << *NewInst << '\n');
1115 if (Idx < Num) {
1116 Input = NewInst;
1117 InpTy = NA[Idx]->PTy;
1118 }
1119 } while (Idx <= Num);
1120
1121 return NewInst;
1122}
1123
1124void HexagonCommonGEP::getAllUsersForNode(GepNode *Node, ValueVect &Values,
1125 NodeChildrenMap &NCM) {
1126 NodeVect Work;
1127 Work.push_back(x: Node);
1128
1129 while (!Work.empty()) {
1130 NodeVect::iterator First = Work.begin();
1131 GepNode *N = *First;
1132 Work.erase(position: First);
1133 if (N->Flags & GepNode::Used) {
1134 NodeToUsesMap::iterator UF = Uses.find(x: N);
1135 assert(UF != Uses.end() && "No use information for used node");
1136 UseSet &Us = UF->second;
1137 for (const auto &U : Us)
1138 Values.push_back(x: U->getUser());
1139 }
1140 NodeChildrenMap::iterator CF = NCM.find(x: N);
1141 if (CF != NCM.end()) {
1142 NodeVect &Cs = CF->second;
1143 llvm::append_range(C&: Work, R&: Cs);
1144 }
1145 }
1146}
1147
1148void HexagonCommonGEP::materialize(NodeToValueMap &Loc) {
1149 LLVM_DEBUG(dbgs() << "Nodes before materialization:\n" << Nodes << '\n');
1150 NodeChildrenMap NCM;
1151 NodeVect Roots;
1152 // Compute the inversion again, since computing placement could alter
1153 // "parent" relation between nodes.
1154 invert_find_roots(Nodes, NCM, Roots);
1155
1156 while (!Roots.empty()) {
1157 NodeVect::iterator First = Roots.begin();
1158 GepNode *Root = *First, *Last = *First;
1159 Roots.erase(position: First);
1160
1161 NodeVect NA; // Nodes to assemble.
1162 // Append to NA all child nodes up to (and including) the first child
1163 // that:
1164 // (1) has more than 1 child, or
1165 // (2) is used, or
1166 // (3) has a child located in a different block.
1167 bool LastUsed = false;
1168 unsigned LastCN = 0;
1169 // The location may be null if the computation failed (it can legitimately
1170 // happen for nodes created from dead GEPs).
1171 Value *LocV = Loc[Last];
1172 if (!LocV)
1173 continue;
1174 BasicBlock *LastB = cast<BasicBlock>(Val: LocV);
1175 do {
1176 NA.push_back(x: Last);
1177 LastUsed = (Last->Flags & GepNode::Used);
1178 if (LastUsed)
1179 break;
1180 NodeChildrenMap::iterator CF = NCM.find(x: Last);
1181 LastCN = (CF != NCM.end()) ? CF->second.size() : 0;
1182 if (LastCN != 1)
1183 break;
1184 GepNode *Child = CF->second.front();
1185 BasicBlock *ChildB = cast_or_null<BasicBlock>(Val: Loc[Child]);
1186 if (ChildB != nullptr && LastB != ChildB)
1187 break;
1188 Last = Child;
1189 } while (true);
1190
1191 BasicBlock::iterator InsertAt = LastB->getTerminator()->getIterator();
1192 if (LastUsed || LastCN > 0) {
1193 ValueVect Urs;
1194 getAllUsersForNode(Node: Root, Values&: Urs, NCM);
1195 BasicBlock::iterator FirstUse = first_use_of_in_block(Values&: Urs, B: LastB);
1196 if (FirstUse != LastB->end())
1197 InsertAt = FirstUse;
1198 }
1199
1200 // Generate a new instruction for NA.
1201 Value *NewInst = fabricateGEP(NA, At: InsertAt, LocB: LastB);
1202
1203 // Convert all the children of Last node into roots, and append them
1204 // to the Roots list.
1205 if (LastCN > 0) {
1206 NodeVect &Cs = NCM[Last];
1207 for (GepNode *CN : Cs) {
1208 CN->Flags &= ~GepNode::Internal;
1209 CN->Flags |= GepNode::Root;
1210 CN->BaseVal = NewInst;
1211 Roots.push_back(x: CN);
1212 }
1213 }
1214
1215 // Lastly, if the Last node was used, replace all uses with the new GEP.
1216 // The uses reference the original GEP values.
1217 if (LastUsed) {
1218 NodeToUsesMap::iterator UF = Uses.find(x: Last);
1219 assert(UF != Uses.end() && "No use information found");
1220 UseSet &Us = UF->second;
1221 for (Use *U : Us)
1222 U->set(NewInst);
1223 }
1224 }
1225}
1226
1227void HexagonCommonGEP::removeDeadCode() {
1228 ValueVect BO;
1229 BO.push_back(x: &Fn->front());
1230
1231 for (unsigned i = 0; i < BO.size(); ++i) {
1232 BasicBlock *B = cast<BasicBlock>(Val: BO[i]);
1233 for (auto *DTN : children<DomTreeNode *>(G: DT->getNode(BB: B)))
1234 BO.push_back(x: DTN->getBlock());
1235 }
1236
1237 for (Value *V : llvm::reverse(C&: BO)) {
1238 BasicBlock *B = cast<BasicBlock>(Val: V);
1239 ValueVect Ins;
1240 for (Instruction &I : llvm::reverse(C&: *B))
1241 Ins.push_back(x: &I);
1242 for (Value *I : Ins) {
1243 Instruction *In = cast<Instruction>(Val: I);
1244 if (isInstructionTriviallyDead(I: In))
1245 In->eraseFromParent();
1246 }
1247 }
1248}
1249
1250bool HexagonCommonGEP::runOnFunction(Function &F) {
1251 if (skipFunction(F))
1252 return false;
1253
1254 // For now bail out on C++ exception handling.
1255 for (const BasicBlock &BB : F)
1256 for (const Instruction &I : BB)
1257 if (isa<InvokeInst>(Val: I) || isa<LandingPadInst>(Val: I))
1258 return false;
1259
1260 Fn = &F;
1261 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1262 PDT = &getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
1263 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1264 Ctx = &F.getContext();
1265
1266 Nodes.clear();
1267 Uses.clear();
1268 NodeOrder.clear();
1269
1270 SpecificBumpPtrAllocator<GepNode> Allocator;
1271 Mem = &Allocator;
1272
1273 collect();
1274 common();
1275
1276 NodeToValueMap Loc;
1277 computeNodePlacement(Loc);
1278 materialize(Loc);
1279 removeDeadCode();
1280
1281#ifdef EXPENSIVE_CHECKS
1282 // Run this only when expensive checks are enabled.
1283 if (verifyFunction(F, &dbgs()))
1284 report_fatal_error("Broken function");
1285#endif
1286 return true;
1287}
1288
1289namespace llvm {
1290
1291 FunctionPass *createHexagonCommonGEP() {
1292 return new HexagonCommonGEP();
1293 }
1294
1295} // end namespace llvm
1296