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