[ARM] MVE integer min and max
[llvm-complete.git] / lib / Target / Hexagon / HexagonCommonGEP.cpp
blobcf1b0a0f7daa9bf29c16c51144d9d7b75e10c734
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 //===----------------------------------------------------------------------===//
9 #define DEBUG_TYPE "commgep"
11 #include "llvm/ADT/ArrayRef.h"
12 #include "llvm/ADT/FoldingSet.h"
13 #include "llvm/ADT/GraphTraits.h"
14 #include "llvm/ADT/SetVector.h"
15 #include "llvm/ADT/STLExtras.h"
16 #include "llvm/ADT/StringRef.h"
17 #include "llvm/Analysis/LoopInfo.h"
18 #include "llvm/Analysis/PostDominators.h"
19 #include "llvm/Transforms/Utils/Local.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/Pass.h"
34 #include "llvm/Support/Allocator.h"
35 #include "llvm/Support/Casting.h"
36 #include "llvm/Support/CommandLine.h"
37 #include "llvm/Support/Compiler.h"
38 #include "llvm/Support/Debug.h"
39 #include "llvm/Support/raw_ostream.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>
50 using namespace llvm;
52 static cl::opt<bool> OptSpeculate("commgep-speculate", cl::init(true),
53 cl::Hidden, cl::ZeroOrMore);
55 static cl::opt<bool> OptEnableInv("commgep-inv", cl::init(true), cl::Hidden,
56 cl::ZeroOrMore);
58 static cl::opt<bool> OptEnableConst("commgep-const", cl::init(true),
59 cl::Hidden, cl::ZeroOrMore);
61 namespace llvm {
63 void initializeHexagonCommonGEPPass(PassRegistry&);
65 } // end namespace llvm
67 namespace {
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>;
74 using UseSet = SetVector<Use *>;
75 using NodeToUsesMap = std::map<GepNode *, UseSet>;
77 // Numbering map for gep nodes. Used to keep track of ordering for
78 // gep nodes.
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);
87 assert(F1 != Map.end() && F2 != Map.end());
88 return F1->second < F2->second;
91 private:
92 std::map<const GepNode *, unsigned> Map;
93 unsigned LastNum = 0;
96 class HexagonCommonGEP : public FunctionPass {
97 public:
98 static char ID;
100 HexagonCommonGEP() : FunctionPass(ID) {
101 initializeHexagonCommonGEPPass(*PassRegistry::getPassRegistry());
104 bool runOnFunction(Function &F) override;
105 StringRef getPassName() const override { return "Hexagon Common GEP"; }
107 void getAnalysisUsage(AnalysisUsage &AU) const override {
108 AU.addRequired<DominatorTreeWrapperPass>();
109 AU.addPreserved<DominatorTreeWrapperPass>();
110 AU.addRequired<PostDominatorTreeWrapperPass>();
111 AU.addPreserved<PostDominatorTreeWrapperPass>();
112 AU.addRequired<LoopInfoWrapperPass>();
113 AU.addPreserved<LoopInfoWrapperPass>();
114 FunctionPass::getAnalysisUsage(AU);
117 private:
118 using ValueToNodeMap = std::map<Value *, GepNode *>;
119 using ValueVect = std::vector<Value *>;
120 using NodeToValuesMap = std::map<GepNode *, ValueVect>;
122 void getBlockTraversalOrder(BasicBlock *Root, ValueVect &Order);
123 bool isHandledGepForm(GetElementPtrInst *GepI);
124 void processGepInst(GetElementPtrInst *GepI, ValueToNodeMap &NM);
125 void collect();
126 void common();
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);
134 bool isInMainPath(BasicBlock *B, 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);
142 Value *fabricateGEP(NodeVect &NA, BasicBlock::iterator At,
143 BasicBlock *LocB);
144 void getAllUsersForNode(GepNode *Node, ValueVect &Values,
145 NodeChildrenMap &NCM);
146 void materialize(NodeToValueMap &Loc);
148 void removeDeadCode();
150 NodeVect Nodes;
151 NodeToUsesMap Uses;
152 NodeOrdering NodeOrder; // Node ordering, for deterministic behavior.
153 SpecificBumpPtrAllocator<GepNode> *Mem;
154 LLVMContext *Ctx;
155 LoopInfo *LI;
156 DominatorTree *DT;
157 PostDominatorTree *PDT;
158 Function *Fn;
161 } // end anonymous namespace
163 char HexagonCommonGEP::ID = 0;
165 INITIALIZE_PASS_BEGIN(HexagonCommonGEP, "hcommgep", "Hexagon Common GEP",
166 false, false)
167 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
168 INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
169 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
170 INITIALIZE_PASS_END(HexagonCommonGEP, "hcommgep", "Hexagon Common GEP",
171 false, false)
173 namespace {
175 struct GepNode {
176 enum {
177 None = 0,
178 Root = 0x01,
179 Internal = 0x02,
180 Used = 0x04,
181 InBounds = 0x08
184 uint32_t Flags = 0;
185 union {
186 GepNode *Parent;
187 Value *BaseVal;
189 Value *Idx = nullptr;
190 Type *PTy = nullptr; // Type of the pointer operand.
192 GepNode() : Parent(nullptr) {}
193 GepNode(const GepNode *N) : Flags(N->Flags), Idx(N->Idx), PTy(N->PTy) {
194 if (Flags & Root)
195 BaseVal = N->BaseVal;
196 else
197 Parent = N->Parent;
200 friend raw_ostream &operator<< (raw_ostream &OS, const GepNode &GN);
203 Type *next_type(Type *Ty, Value *Idx) {
204 if (auto *PTy = dyn_cast<PointerType>(Ty))
205 return PTy->getElementType();
206 // Advance the type.
207 if (!Ty->isStructTy()) {
208 Type *NexTy = cast<SequentialType>(Ty)->getElementType();
209 return NexTy;
211 // Otherwise it is a struct type.
212 ConstantInt *CI = dyn_cast<ConstantInt>(Idx);
213 assert(CI && "Struct type with non-constant index");
214 int64_t i = CI->getValue().getSExtValue();
215 Type *NextTy = cast<StructType>(Ty)->getElementType(i);
216 return NextTy;
219 raw_ostream &operator<< (raw_ostream &OS, const GepNode &GN) {
220 OS << "{ {";
221 bool Comma = false;
222 if (GN.Flags & GepNode::Root) {
223 OS << "root";
224 Comma = true;
226 if (GN.Flags & GepNode::Internal) {
227 if (Comma)
228 OS << ',';
229 OS << "internal";
230 Comma = true;
232 if (GN.Flags & GepNode::Used) {
233 if (Comma)
234 OS << ',';
235 OS << "used";
237 if (GN.Flags & GepNode::InBounds) {
238 if (Comma)
239 OS << ',';
240 OS << "inbounds";
242 OS << "} ";
243 if (GN.Flags & GepNode::Root)
244 OS << "BaseVal:" << GN.BaseVal->getName() << '(' << GN.BaseVal << ')';
245 else
246 OS << "Parent:" << GN.Parent;
248 OS << " Idx:";
249 if (ConstantInt *CI = dyn_cast<ConstantInt>(GN.Idx))
250 OS << CI->getValue().getSExtValue();
251 else if (GN.Idx->hasName())
252 OS << GN.Idx->getName();
253 else
254 OS << "<anon> =" << *GN.Idx;
256 OS << " PTy:";
257 if (GN.PTy->isStructTy()) {
258 StructType *STy = cast<StructType>(GN.PTy);
259 if (!STy->isLiteral())
260 OS << GN.PTy->getStructName();
261 else
262 OS << "<anon-struct>:" << *STy;
264 else
265 OS << *GN.PTy;
266 OS << " }";
267 return OS;
270 template <typename NodeContainer>
271 void dump_node_container(raw_ostream &OS, const NodeContainer &S) {
272 using const_iterator = typename NodeContainer::const_iterator;
274 for (const_iterator I = S.begin(), E = S.end(); I != E; ++I)
275 OS << *I << ' ' << **I << '\n';
278 raw_ostream &operator<< (raw_ostream &OS,
279 const NodeVect &S) LLVM_ATTRIBUTE_UNUSED;
280 raw_ostream &operator<< (raw_ostream &OS, const NodeVect &S) {
281 dump_node_container(OS, S);
282 return OS;
285 raw_ostream &operator<< (raw_ostream &OS,
286 const NodeToUsesMap &M) LLVM_ATTRIBUTE_UNUSED;
287 raw_ostream &operator<< (raw_ostream &OS, const NodeToUsesMap &M){
288 using const_iterator = NodeToUsesMap::const_iterator;
290 for (const_iterator I = M.begin(), E = M.end(); I != E; ++I) {
291 const UseSet &Us = I->second;
292 OS << I->first << " -> #" << Us.size() << '{';
293 for (UseSet::const_iterator J = Us.begin(), F = Us.end(); J != F; ++J) {
294 User *R = (*J)->getUser();
295 if (R->hasName())
296 OS << ' ' << R->getName();
297 else
298 OS << " <?>(" << *R << ')';
300 OS << " }\n";
302 return OS;
305 struct in_set {
306 in_set(const NodeSet &S) : NS(S) {}
308 bool operator() (GepNode *N) const {
309 return NS.find(N) != NS.end();
312 private:
313 const NodeSet &NS;
316 } // end anonymous namespace
318 inline void *operator new(size_t, SpecificBumpPtrAllocator<GepNode> &A) {
319 return A.Allocate();
322 void HexagonCommonGEP::getBlockTraversalOrder(BasicBlock *Root,
323 ValueVect &Order) {
324 // Compute block ordering for a typical DT-based traversal of the flow
325 // graph: "before visiting a block, all of its dominators must have been
326 // visited".
328 Order.push_back(Root);
329 for (auto *DTN : children<DomTreeNode*>(DT->getNode(Root)))
330 getBlockTraversalOrder(DTN->getBlock(), Order);
333 bool HexagonCommonGEP::isHandledGepForm(GetElementPtrInst *GepI) {
334 // No vector GEPs.
335 if (!GepI->getType()->isPointerTy())
336 return false;
337 // No GEPs without any indices. (Is this possible?)
338 if (GepI->idx_begin() == GepI->idx_end())
339 return false;
340 return true;
343 void HexagonCommonGEP::processGepInst(GetElementPtrInst *GepI,
344 ValueToNodeMap &NM) {
345 LLVM_DEBUG(dbgs() << "Visiting GEP: " << *GepI << '\n');
346 GepNode *N = new (*Mem) GepNode;
347 Value *PtrOp = GepI->getPointerOperand();
348 uint32_t InBounds = GepI->isInBounds() ? GepNode::InBounds : 0;
349 ValueToNodeMap::iterator F = NM.find(PtrOp);
350 if (F == NM.end()) {
351 N->BaseVal = PtrOp;
352 N->Flags |= GepNode::Root | InBounds;
353 } else {
354 // If PtrOp was a GEP instruction, it must have already been processed.
355 // The ValueToNodeMap entry for it is the last gep node in the generated
356 // chain. Link to it here.
357 N->Parent = F->second;
359 N->PTy = PtrOp->getType();
360 N->Idx = *GepI->idx_begin();
362 // Collect the list of users of this GEP instruction. Will add it to the
363 // last node created for it.
364 UseSet Us;
365 for (Value::user_iterator UI = GepI->user_begin(), UE = GepI->user_end();
366 UI != UE; ++UI) {
367 // Check if this gep is used by anything other than other geps that
368 // we will process.
369 if (isa<GetElementPtrInst>(*UI)) {
370 GetElementPtrInst *UserG = cast<GetElementPtrInst>(*UI);
371 if (isHandledGepForm(UserG))
372 continue;
374 Us.insert(&UI.getUse());
376 Nodes.push_back(N);
377 NodeOrder.insert(N);
379 // Skip the first index operand, since we only handle 0. This dereferences
380 // the pointer operand.
381 GepNode *PN = N;
382 Type *PtrTy = cast<PointerType>(PtrOp->getType())->getElementType();
383 for (User::op_iterator OI = GepI->idx_begin()+1, OE = GepI->idx_end();
384 OI != OE; ++OI) {
385 Value *Op = *OI;
386 GepNode *Nx = new (*Mem) GepNode;
387 Nx->Parent = PN; // Link Nx to the previous node.
388 Nx->Flags |= GepNode::Internal | InBounds;
389 Nx->PTy = PtrTy;
390 Nx->Idx = Op;
391 Nodes.push_back(Nx);
392 NodeOrder.insert(Nx);
393 PN = Nx;
395 PtrTy = next_type(PtrTy, Op);
398 // After last node has been created, update the use information.
399 if (!Us.empty()) {
400 PN->Flags |= GepNode::Used;
401 Uses[PN].insert(Us.begin(), Us.end());
404 // Link the last node with the originating GEP instruction. This is to
405 // help with linking chained GEP instructions.
406 NM.insert(std::make_pair(GepI, PN));
409 void HexagonCommonGEP::collect() {
410 // Establish depth-first traversal order of the dominator tree.
411 ValueVect BO;
412 getBlockTraversalOrder(&Fn->front(), BO);
414 // The creation of gep nodes requires DT-traversal. When processing a GEP
415 // instruction that uses another GEP instruction as the base pointer, the
416 // gep node for the base pointer should already exist.
417 ValueToNodeMap NM;
418 for (ValueVect::iterator I = BO.begin(), E = BO.end(); I != E; ++I) {
419 BasicBlock *B = cast<BasicBlock>(*I);
420 for (BasicBlock::iterator J = B->begin(), F = B->end(); J != F; ++J) {
421 if (!isa<GetElementPtrInst>(J))
422 continue;
423 GetElementPtrInst *GepI = cast<GetElementPtrInst>(J);
424 if (isHandledGepForm(GepI))
425 processGepInst(GepI, NM);
429 LLVM_DEBUG(dbgs() << "Gep nodes after initial collection:\n" << Nodes);
432 static void invert_find_roots(const NodeVect &Nodes, NodeChildrenMap &NCM,
433 NodeVect &Roots) {
434 using const_iterator = NodeVect::const_iterator;
436 for (const_iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) {
437 GepNode *N = *I;
438 if (N->Flags & GepNode::Root) {
439 Roots.push_back(N);
440 continue;
442 GepNode *PN = N->Parent;
443 NCM[PN].push_back(N);
447 static void nodes_for_root(GepNode *Root, NodeChildrenMap &NCM,
448 NodeSet &Nodes) {
449 NodeVect Work;
450 Work.push_back(Root);
451 Nodes.insert(Root);
453 while (!Work.empty()) {
454 NodeVect::iterator First = Work.begin();
455 GepNode *N = *First;
456 Work.erase(First);
457 NodeChildrenMap::iterator CF = NCM.find(N);
458 if (CF != NCM.end()) {
459 Work.insert(Work.end(), CF->second.begin(), CF->second.end());
460 Nodes.insert(CF->second.begin(), CF->second.end());
465 namespace {
467 using NodeSymRel = std::set<NodeSet>;
468 using NodePair = std::pair<GepNode *, GepNode *>;
469 using NodePairSet = std::set<NodePair>;
471 } // end anonymous namespace
473 static const NodeSet *node_class(GepNode *N, NodeSymRel &Rel) {
474 for (NodeSymRel::iterator I = Rel.begin(), E = Rel.end(); I != E; ++I)
475 if (I->count(N))
476 return &*I;
477 return nullptr;
480 // Create an ordered pair of GepNode pointers. The pair will be used in
481 // determining equality. The only purpose of the ordering is to eliminate
482 // duplication due to the commutativity of equality/non-equality.
483 static NodePair node_pair(GepNode *N1, GepNode *N2) {
484 uintptr_t P1 = uintptr_t(N1), P2 = uintptr_t(N2);
485 if (P1 <= P2)
486 return std::make_pair(N1, N2);
487 return std::make_pair(N2, N1);
490 static unsigned node_hash(GepNode *N) {
491 // Include everything except flags and parent.
492 FoldingSetNodeID ID;
493 ID.AddPointer(N->Idx);
494 ID.AddPointer(N->PTy);
495 return ID.ComputeHash();
498 static bool node_eq(GepNode *N1, GepNode *N2, NodePairSet &Eq,
499 NodePairSet &Ne) {
500 // Don't cache the result for nodes with different hashes. The hash
501 // comparison is fast enough.
502 if (node_hash(N1) != node_hash(N2))
503 return false;
505 NodePair NP = node_pair(N1, N2);
506 NodePairSet::iterator FEq = Eq.find(NP);
507 if (FEq != Eq.end())
508 return true;
509 NodePairSet::iterator FNe = Ne.find(NP);
510 if (FNe != Ne.end())
511 return false;
512 // Not previously compared.
513 bool Root1 = N1->Flags & GepNode::Root;
514 bool Root2 = N2->Flags & GepNode::Root;
515 NodePair P = node_pair(N1, N2);
516 // If the Root flag has different values, the nodes are different.
517 // If both nodes are root nodes, but their base pointers differ,
518 // they are different.
519 if (Root1 != Root2 || (Root1 && N1->BaseVal != N2->BaseVal)) {
520 Ne.insert(P);
521 return false;
523 // Here the root flags are identical, and for root nodes the
524 // base pointers are equal, so the root nodes are equal.
525 // For non-root nodes, compare their parent nodes.
526 if (Root1 || node_eq(N1->Parent, N2->Parent, Eq, Ne)) {
527 Eq.insert(P);
528 return true;
530 return false;
533 void HexagonCommonGEP::common() {
534 // The essence of this commoning is finding gep nodes that are equal.
535 // To do this we need to compare all pairs of nodes. To save time,
536 // first, partition the set of all nodes into sets of potentially equal
537 // nodes, and then compare pairs from within each partition.
538 using NodeSetMap = std::map<unsigned, NodeSet>;
539 NodeSetMap MaybeEq;
541 for (NodeVect::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) {
542 GepNode *N = *I;
543 unsigned H = node_hash(N);
544 MaybeEq[H].insert(N);
547 // Compute the equivalence relation for the gep nodes. Use two caches,
548 // one for equality and the other for non-equality.
549 NodeSymRel EqRel; // Equality relation (as set of equivalence classes).
550 NodePairSet Eq, Ne; // Caches.
551 for (NodeSetMap::iterator I = MaybeEq.begin(), E = MaybeEq.end();
552 I != E; ++I) {
553 NodeSet &S = I->second;
554 for (NodeSet::iterator NI = S.begin(), NE = S.end(); NI != NE; ++NI) {
555 GepNode *N = *NI;
556 // If node already has a class, then the class must have been created
557 // in a prior iteration of this loop. Since equality is transitive,
558 // nothing more will be added to that class, so skip it.
559 if (node_class(N, EqRel))
560 continue;
562 // Create a new class candidate now.
563 NodeSet C;
564 for (NodeSet::iterator NJ = std::next(NI); NJ != NE; ++NJ)
565 if (node_eq(N, *NJ, Eq, Ne))
566 C.insert(*NJ);
567 // If Tmp is empty, N would be the only element in it. Don't bother
568 // creating a class for it then.
569 if (!C.empty()) {
570 C.insert(N); // Finalize the set before adding it to the relation.
571 std::pair<NodeSymRel::iterator, bool> Ins = EqRel.insert(C);
572 (void)Ins;
573 assert(Ins.second && "Cannot add a class");
578 LLVM_DEBUG({
579 dbgs() << "Gep node equality:\n";
580 for (NodePairSet::iterator I = Eq.begin(), E = Eq.end(); I != E; ++I)
581 dbgs() << "{ " << I->first << ", " << I->second << " }\n";
583 dbgs() << "Gep equivalence classes:\n";
584 for (NodeSymRel::iterator I = EqRel.begin(), E = EqRel.end(); I != E; ++I) {
585 dbgs() << '{';
586 const NodeSet &S = *I;
587 for (NodeSet::const_iterator J = S.begin(), F = S.end(); J != F; ++J) {
588 if (J != S.begin())
589 dbgs() << ',';
590 dbgs() << ' ' << *J;
592 dbgs() << " }\n";
596 // Create a projection from a NodeSet to the minimal element in it.
597 using ProjMap = std::map<const NodeSet *, GepNode *>;
598 ProjMap PM;
599 for (NodeSymRel::iterator I = EqRel.begin(), E = EqRel.end(); I != E; ++I) {
600 const NodeSet &S = *I;
601 GepNode *Min = *std::min_element(S.begin(), S.end(), NodeOrder);
602 std::pair<ProjMap::iterator,bool> Ins = PM.insert(std::make_pair(&S, Min));
603 (void)Ins;
604 assert(Ins.second && "Cannot add minimal element");
606 // Update the min element's flags, and user list.
607 uint32_t Flags = 0;
608 UseSet &MinUs = Uses[Min];
609 for (NodeSet::iterator J = S.begin(), F = S.end(); J != F; ++J) {
610 GepNode *N = *J;
611 uint32_t NF = N->Flags;
612 // If N is used, append all original values of N to the list of
613 // original values of Min.
614 if (NF & GepNode::Used)
615 MinUs.insert(Uses[N].begin(), Uses[N].end());
616 Flags |= NF;
618 if (MinUs.empty())
619 Uses.erase(Min);
621 // The collected flags should include all the flags from the min element.
622 assert((Min->Flags & Flags) == Min->Flags);
623 Min->Flags = Flags;
626 // Commoning: for each non-root gep node, replace "Parent" with the
627 // selected (minimum) node from the corresponding equivalence class.
628 // If a given parent does not have an equivalence class, leave it
629 // unchanged (it means that it's the only element in its class).
630 for (NodeVect::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) {
631 GepNode *N = *I;
632 if (N->Flags & GepNode::Root)
633 continue;
634 const NodeSet *PC = node_class(N->Parent, EqRel);
635 if (!PC)
636 continue;
637 ProjMap::iterator F = PM.find(PC);
638 if (F == PM.end())
639 continue;
640 // Found a replacement, use it.
641 GepNode *Rep = F->second;
642 N->Parent = Rep;
645 LLVM_DEBUG(dbgs() << "Gep nodes after commoning:\n" << Nodes);
647 // Finally, erase the nodes that are no longer used.
648 NodeSet Erase;
649 for (NodeVect::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) {
650 GepNode *N = *I;
651 const NodeSet *PC = node_class(N, EqRel);
652 if (!PC)
653 continue;
654 ProjMap::iterator F = PM.find(PC);
655 if (F == PM.end())
656 continue;
657 if (N == F->second)
658 continue;
659 // Node for removal.
660 Erase.insert(*I);
662 NodeVect::iterator NewE = remove_if(Nodes, in_set(Erase));
663 Nodes.resize(std::distance(Nodes.begin(), NewE));
665 LLVM_DEBUG(dbgs() << "Gep nodes after post-commoning cleanup:\n" << Nodes);
668 template <typename T>
669 static BasicBlock *nearest_common_dominator(DominatorTree *DT, T &Blocks) {
670 LLVM_DEBUG({
671 dbgs() << "NCD of {";
672 for (typename T::iterator I = Blocks.begin(), E = Blocks.end(); I != E;
673 ++I) {
674 if (!*I)
675 continue;
676 BasicBlock *B = cast<BasicBlock>(*I);
677 dbgs() << ' ' << B->getName();
679 dbgs() << " }\n";
682 // Allow null basic blocks in Blocks. In such cases, return nullptr.
683 typename T::iterator I = Blocks.begin(), E = Blocks.end();
684 if (I == E || !*I)
685 return nullptr;
686 BasicBlock *Dom = cast<BasicBlock>(*I);
687 while (++I != E) {
688 BasicBlock *B = cast_or_null<BasicBlock>(*I);
689 Dom = B ? DT->findNearestCommonDominator(Dom, B) : nullptr;
690 if (!Dom)
691 return nullptr;
693 LLVM_DEBUG(dbgs() << "computed:" << Dom->getName() << '\n');
694 return Dom;
697 template <typename T>
698 static BasicBlock *nearest_common_dominatee(DominatorTree *DT, T &Blocks) {
699 // If two blocks, A and B, dominate a block C, then A dominates B,
700 // or B dominates A.
701 typename T::iterator I = Blocks.begin(), E = Blocks.end();
702 // Find the first non-null block.
703 while (I != E && !*I)
704 ++I;
705 if (I == E)
706 return DT->getRoot();
707 BasicBlock *DomB = cast<BasicBlock>(*I);
708 while (++I != E) {
709 if (!*I)
710 continue;
711 BasicBlock *B = cast<BasicBlock>(*I);
712 if (DT->dominates(B, DomB))
713 continue;
714 if (!DT->dominates(DomB, B))
715 return nullptr;
716 DomB = B;
718 return DomB;
721 // Find the first use in B of any value from Values. If no such use,
722 // return B->end().
723 template <typename T>
724 static BasicBlock::iterator first_use_of_in_block(T &Values, BasicBlock *B) {
725 BasicBlock::iterator FirstUse = B->end(), BEnd = B->end();
727 using iterator = typename T::iterator;
729 for (iterator I = Values.begin(), E = Values.end(); I != E; ++I) {
730 Value *V = *I;
731 // If V is used in a PHI node, the use belongs to the incoming block,
732 // not the block with the PHI node. In the incoming block, the use
733 // would be considered as being at the end of it, so it cannot
734 // influence the position of the first use (which is assumed to be
735 // at the end to start with).
736 if (isa<PHINode>(V))
737 continue;
738 if (!isa<Instruction>(V))
739 continue;
740 Instruction *In = cast<Instruction>(V);
741 if (In->getParent() != B)
742 continue;
743 BasicBlock::iterator It = In->getIterator();
744 if (std::distance(FirstUse, BEnd) < std::distance(It, BEnd))
745 FirstUse = It;
747 return FirstUse;
750 static bool is_empty(const BasicBlock *B) {
751 return B->empty() || (&*B->begin() == B->getTerminator());
754 BasicBlock *HexagonCommonGEP::recalculatePlacement(GepNode *Node,
755 NodeChildrenMap &NCM, NodeToValueMap &Loc) {
756 LLVM_DEBUG(dbgs() << "Loc for node:" << Node << '\n');
757 // Recalculate the placement for Node, assuming that the locations of
758 // its children in Loc are valid.
759 // Return nullptr if there is no valid placement for Node (for example, it
760 // uses an index value that is not available at the location required
761 // to dominate all children, etc.).
763 // Find the nearest common dominator for:
764 // - all users, if the node is used, and
765 // - all children.
766 ValueVect Bs;
767 if (Node->Flags & GepNode::Used) {
768 // Append all blocks with uses of the original values to the
769 // block vector Bs.
770 NodeToUsesMap::iterator UF = Uses.find(Node);
771 assert(UF != Uses.end() && "Used node with no use information");
772 UseSet &Us = UF->second;
773 for (UseSet::iterator I = Us.begin(), E = Us.end(); I != E; ++I) {
774 Use *U = *I;
775 User *R = U->getUser();
776 if (!isa<Instruction>(R))
777 continue;
778 BasicBlock *PB = isa<PHINode>(R)
779 ? cast<PHINode>(R)->getIncomingBlock(*U)
780 : cast<Instruction>(R)->getParent();
781 Bs.push_back(PB);
784 // Append the location of each child.
785 NodeChildrenMap::iterator CF = NCM.find(Node);
786 if (CF != NCM.end()) {
787 NodeVect &Cs = CF->second;
788 for (NodeVect::iterator I = Cs.begin(), E = Cs.end(); I != E; ++I) {
789 GepNode *CN = *I;
790 NodeToValueMap::iterator LF = Loc.find(CN);
791 // If the child is only used in GEP instructions (i.e. is not used in
792 // non-GEP instructions), the nearest dominator computed for it may
793 // have been null. In such case it won't have a location available.
794 if (LF == Loc.end())
795 continue;
796 Bs.push_back(LF->second);
800 BasicBlock *DomB = nearest_common_dominator(DT, Bs);
801 if (!DomB)
802 return nullptr;
803 // Check if the index used by Node dominates the computed dominator.
804 Instruction *IdxI = dyn_cast<Instruction>(Node->Idx);
805 if (IdxI && !DT->dominates(IdxI->getParent(), DomB))
806 return nullptr;
808 // Avoid putting nodes into empty blocks.
809 while (is_empty(DomB)) {
810 DomTreeNode *N = (*DT)[DomB]->getIDom();
811 if (!N)
812 break;
813 DomB = N->getBlock();
816 // Otherwise, DomB is fine. Update the location map.
817 Loc[Node] = DomB;
818 return DomB;
821 BasicBlock *HexagonCommonGEP::recalculatePlacementRec(GepNode *Node,
822 NodeChildrenMap &NCM, NodeToValueMap &Loc) {
823 LLVM_DEBUG(dbgs() << "LocRec begin for node:" << Node << '\n');
824 // Recalculate the placement of Node, after recursively recalculating the
825 // placements of all its children.
826 NodeChildrenMap::iterator CF = NCM.find(Node);
827 if (CF != NCM.end()) {
828 NodeVect &Cs = CF->second;
829 for (NodeVect::iterator I = Cs.begin(), E = Cs.end(); I != E; ++I)
830 recalculatePlacementRec(*I, NCM, Loc);
832 BasicBlock *LB = recalculatePlacement(Node, NCM, Loc);
833 LLVM_DEBUG(dbgs() << "LocRec end for node:" << Node << '\n');
834 return LB;
837 bool HexagonCommonGEP::isInvariantIn(Value *Val, Loop *L) {
838 if (isa<Constant>(Val) || isa<Argument>(Val))
839 return true;
840 Instruction *In = dyn_cast<Instruction>(Val);
841 if (!In)
842 return false;
843 BasicBlock *HdrB = L->getHeader(), *DefB = In->getParent();
844 return DT->properlyDominates(DefB, HdrB);
847 bool HexagonCommonGEP::isInvariantIn(GepNode *Node, Loop *L) {
848 if (Node->Flags & GepNode::Root)
849 if (!isInvariantIn(Node->BaseVal, L))
850 return false;
851 return isInvariantIn(Node->Idx, L);
854 bool HexagonCommonGEP::isInMainPath(BasicBlock *B, Loop *L) {
855 BasicBlock *HB = L->getHeader();
856 BasicBlock *LB = L->getLoopLatch();
857 // B must post-dominate the loop header or dominate the loop latch.
858 if (PDT->dominates(B, HB))
859 return true;
860 if (LB && DT->dominates(B, LB))
861 return true;
862 return false;
865 static BasicBlock *preheader(DominatorTree *DT, Loop *L) {
866 if (BasicBlock *PH = L->getLoopPreheader())
867 return PH;
868 if (!OptSpeculate)
869 return nullptr;
870 DomTreeNode *DN = DT->getNode(L->getHeader());
871 if (!DN)
872 return nullptr;
873 return DN->getIDom()->getBlock();
876 BasicBlock *HexagonCommonGEP::adjustForInvariance(GepNode *Node,
877 NodeChildrenMap &NCM, NodeToValueMap &Loc) {
878 // Find the "topmost" location for Node: it must be dominated by both,
879 // its parent (or the BaseVal, if it's a root node), and by the index
880 // value.
881 ValueVect Bs;
882 if (Node->Flags & GepNode::Root) {
883 if (Instruction *PIn = dyn_cast<Instruction>(Node->BaseVal))
884 Bs.push_back(PIn->getParent());
885 } else {
886 Bs.push_back(Loc[Node->Parent]);
888 if (Instruction *IIn = dyn_cast<Instruction>(Node->Idx))
889 Bs.push_back(IIn->getParent());
890 BasicBlock *TopB = nearest_common_dominatee(DT, Bs);
892 // Traverse the loop nest upwards until we find a loop in which Node
893 // is no longer invariant, or until we get to the upper limit of Node's
894 // placement. The traversal will also stop when a suitable "preheader"
895 // cannot be found for a given loop. The "preheader" may actually be
896 // a regular block outside of the loop (i.e. not guarded), in which case
897 // the Node will be speculated.
898 // For nodes that are not in the main path of the containing loop (i.e.
899 // are not executed in each iteration), do not move them out of the loop.
900 BasicBlock *LocB = cast_or_null<BasicBlock>(Loc[Node]);
901 if (LocB) {
902 Loop *Lp = LI->getLoopFor(LocB);
903 while (Lp) {
904 if (!isInvariantIn(Node, Lp) || !isInMainPath(LocB, Lp))
905 break;
906 BasicBlock *NewLoc = preheader(DT, Lp);
907 if (!NewLoc || !DT->dominates(TopB, NewLoc))
908 break;
909 Lp = Lp->getParentLoop();
910 LocB = NewLoc;
913 Loc[Node] = LocB;
915 // Recursively compute the locations of all children nodes.
916 NodeChildrenMap::iterator CF = NCM.find(Node);
917 if (CF != NCM.end()) {
918 NodeVect &Cs = CF->second;
919 for (NodeVect::iterator I = Cs.begin(), E = Cs.end(); I != E; ++I)
920 adjustForInvariance(*I, NCM, Loc);
922 return LocB;
925 namespace {
927 struct LocationAsBlock {
928 LocationAsBlock(const NodeToValueMap &L) : Map(L) {}
930 const NodeToValueMap &Map;
933 raw_ostream &operator<< (raw_ostream &OS,
934 const LocationAsBlock &Loc) LLVM_ATTRIBUTE_UNUSED ;
935 raw_ostream &operator<< (raw_ostream &OS, const LocationAsBlock &Loc) {
936 for (NodeToValueMap::const_iterator I = Loc.Map.begin(), E = Loc.Map.end();
937 I != E; ++I) {
938 OS << I->first << " -> ";
939 BasicBlock *B = cast<BasicBlock>(I->second);
940 OS << B->getName() << '(' << B << ')';
941 OS << '\n';
943 return OS;
946 inline bool is_constant(GepNode *N) {
947 return isa<ConstantInt>(N->Idx);
950 } // end anonymous namespace
952 void HexagonCommonGEP::separateChainForNode(GepNode *Node, Use *U,
953 NodeToValueMap &Loc) {
954 User *R = U->getUser();
955 LLVM_DEBUG(dbgs() << "Separating chain for node (" << Node << ") user: " << *R
956 << '\n');
957 BasicBlock *PB = cast<Instruction>(R)->getParent();
959 GepNode *N = Node;
960 GepNode *C = nullptr, *NewNode = nullptr;
961 while (is_constant(N) && !(N->Flags & GepNode::Root)) {
962 // XXX if (single-use) dont-replicate;
963 GepNode *NewN = new (*Mem) GepNode(N);
964 Nodes.push_back(NewN);
965 Loc[NewN] = PB;
967 if (N == Node)
968 NewNode = NewN;
969 NewN->Flags &= ~GepNode::Used;
970 if (C)
971 C->Parent = NewN;
972 C = NewN;
973 N = N->Parent;
975 if (!NewNode)
976 return;
978 // Move over all uses that share the same user as U from Node to NewNode.
979 NodeToUsesMap::iterator UF = Uses.find(Node);
980 assert(UF != Uses.end());
981 UseSet &Us = UF->second;
982 UseSet NewUs;
983 for (Use *U : Us) {
984 if (U->getUser() == R)
985 NewUs.insert(U);
987 for (Use *U : NewUs)
988 Us.remove(U); // erase takes an iterator.
990 if (Us.empty()) {
991 Node->Flags &= ~GepNode::Used;
992 Uses.erase(UF);
995 // Should at least have U in NewUs.
996 NewNode->Flags |= GepNode::Used;
997 LLVM_DEBUG(dbgs() << "new node: " << NewNode << " " << *NewNode << '\n');
998 assert(!NewUs.empty());
999 Uses[NewNode] = NewUs;
1002 void HexagonCommonGEP::separateConstantChains(GepNode *Node,
1003 NodeChildrenMap &NCM, NodeToValueMap &Loc) {
1004 // First approximation: extract all chains.
1005 NodeSet Ns;
1006 nodes_for_root(Node, NCM, Ns);
1008 LLVM_DEBUG(dbgs() << "Separating constant chains for node: " << Node << '\n');
1009 // Collect all used nodes together with the uses from loads and stores,
1010 // where the GEP node could be folded into the load/store instruction.
1011 NodeToUsesMap FNs; // Foldable nodes.
1012 for (NodeSet::iterator I = Ns.begin(), E = Ns.end(); I != E; ++I) {
1013 GepNode *N = *I;
1014 if (!(N->Flags & GepNode::Used))
1015 continue;
1016 NodeToUsesMap::iterator UF = Uses.find(N);
1017 assert(UF != Uses.end());
1018 UseSet &Us = UF->second;
1019 // Loads/stores that use the node N.
1020 UseSet LSs;
1021 for (UseSet::iterator J = Us.begin(), F = Us.end(); J != F; ++J) {
1022 Use *U = *J;
1023 User *R = U->getUser();
1024 // We're interested in uses that provide the address. It can happen
1025 // that the value may also be provided via GEP, but we won't handle
1026 // those cases here for now.
1027 if (LoadInst *Ld = dyn_cast<LoadInst>(R)) {
1028 unsigned PtrX = LoadInst::getPointerOperandIndex();
1029 if (&Ld->getOperandUse(PtrX) == U)
1030 LSs.insert(U);
1031 } else if (StoreInst *St = dyn_cast<StoreInst>(R)) {
1032 unsigned PtrX = StoreInst::getPointerOperandIndex();
1033 if (&St->getOperandUse(PtrX) == U)
1034 LSs.insert(U);
1037 // Even if the total use count is 1, separating the chain may still be
1038 // beneficial, since the constant chain may be longer than the GEP alone
1039 // would be (e.g. if the parent node has a constant index and also has
1040 // other children).
1041 if (!LSs.empty())
1042 FNs.insert(std::make_pair(N, LSs));
1045 LLVM_DEBUG(dbgs() << "Nodes with foldable users:\n" << FNs);
1047 for (NodeToUsesMap::iterator I = FNs.begin(), E = FNs.end(); I != E; ++I) {
1048 GepNode *N = I->first;
1049 UseSet &Us = I->second;
1050 for (UseSet::iterator J = Us.begin(), F = Us.end(); J != F; ++J)
1051 separateChainForNode(N, *J, Loc);
1055 void HexagonCommonGEP::computeNodePlacement(NodeToValueMap &Loc) {
1056 // Compute the inverse of the Node.Parent links. Also, collect the set
1057 // of root nodes.
1058 NodeChildrenMap NCM;
1059 NodeVect Roots;
1060 invert_find_roots(Nodes, NCM, Roots);
1062 // Compute the initial placement determined by the users' locations, and
1063 // the locations of the child nodes.
1064 for (NodeVect::iterator I = Roots.begin(), E = Roots.end(); I != E; ++I)
1065 recalculatePlacementRec(*I, NCM, Loc);
1067 LLVM_DEBUG(dbgs() << "Initial node placement:\n" << LocationAsBlock(Loc));
1069 if (OptEnableInv) {
1070 for (NodeVect::iterator I = Roots.begin(), E = Roots.end(); I != E; ++I)
1071 adjustForInvariance(*I, NCM, Loc);
1073 LLVM_DEBUG(dbgs() << "Node placement after adjustment for invariance:\n"
1074 << LocationAsBlock(Loc));
1076 if (OptEnableConst) {
1077 for (NodeVect::iterator I = Roots.begin(), E = Roots.end(); I != E; ++I)
1078 separateConstantChains(*I, NCM, Loc);
1080 LLVM_DEBUG(dbgs() << "Node use information:\n" << Uses);
1082 // At the moment, there is no further refinement of the initial placement.
1083 // Such a refinement could include splitting the nodes if they are placed
1084 // too far from some of its users.
1086 LLVM_DEBUG(dbgs() << "Final node placement:\n" << LocationAsBlock(Loc));
1089 Value *HexagonCommonGEP::fabricateGEP(NodeVect &NA, BasicBlock::iterator At,
1090 BasicBlock *LocB) {
1091 LLVM_DEBUG(dbgs() << "Fabricating GEP in " << LocB->getName()
1092 << " for nodes:\n"
1093 << NA);
1094 unsigned Num = NA.size();
1095 GepNode *RN = NA[0];
1096 assert((RN->Flags & GepNode::Root) && "Creating GEP for non-root");
1098 GetElementPtrInst *NewInst = nullptr;
1099 Value *Input = RN->BaseVal;
1100 Value **IdxList = new Value*[Num+1];
1101 unsigned nax = 0;
1102 do {
1103 unsigned IdxC = 0;
1104 // If the type of the input of the first node is not a pointer,
1105 // we need to add an artificial i32 0 to the indices (because the
1106 // actual input in the IR will be a pointer).
1107 if (!NA[nax]->PTy->isPointerTy()) {
1108 Type *Int32Ty = Type::getInt32Ty(*Ctx);
1109 IdxList[IdxC++] = ConstantInt::get(Int32Ty, 0);
1112 // Keep adding indices from NA until we have to stop and generate
1113 // an "intermediate" GEP.
1114 while (++nax <= Num) {
1115 GepNode *N = NA[nax-1];
1116 IdxList[IdxC++] = N->Idx;
1117 if (nax < Num) {
1118 // We have to stop, if the expected type of the output of this node
1119 // is not the same as the input type of the next node.
1120 Type *NextTy = next_type(N->PTy, N->Idx);
1121 if (NextTy != NA[nax]->PTy)
1122 break;
1125 ArrayRef<Value*> A(IdxList, IdxC);
1126 Type *InpTy = Input->getType();
1127 Type *ElTy = cast<PointerType>(InpTy->getScalarType())->getElementType();
1128 NewInst = GetElementPtrInst::Create(ElTy, Input, A, "cgep", &*At);
1129 NewInst->setIsInBounds(RN->Flags & GepNode::InBounds);
1130 LLVM_DEBUG(dbgs() << "new GEP: " << *NewInst << '\n');
1131 Input = NewInst;
1132 } while (nax <= Num);
1134 delete[] IdxList;
1135 return NewInst;
1138 void HexagonCommonGEP::getAllUsersForNode(GepNode *Node, ValueVect &Values,
1139 NodeChildrenMap &NCM) {
1140 NodeVect Work;
1141 Work.push_back(Node);
1143 while (!Work.empty()) {
1144 NodeVect::iterator First = Work.begin();
1145 GepNode *N = *First;
1146 Work.erase(First);
1147 if (N->Flags & GepNode::Used) {
1148 NodeToUsesMap::iterator UF = Uses.find(N);
1149 assert(UF != Uses.end() && "No use information for used node");
1150 UseSet &Us = UF->second;
1151 for (UseSet::iterator I = Us.begin(), E = Us.end(); I != E; ++I)
1152 Values.push_back((*I)->getUser());
1154 NodeChildrenMap::iterator CF = NCM.find(N);
1155 if (CF != NCM.end()) {
1156 NodeVect &Cs = CF->second;
1157 Work.insert(Work.end(), Cs.begin(), Cs.end());
1162 void HexagonCommonGEP::materialize(NodeToValueMap &Loc) {
1163 LLVM_DEBUG(dbgs() << "Nodes before materialization:\n" << Nodes << '\n');
1164 NodeChildrenMap NCM;
1165 NodeVect Roots;
1166 // Compute the inversion again, since computing placement could alter
1167 // "parent" relation between nodes.
1168 invert_find_roots(Nodes, NCM, Roots);
1170 while (!Roots.empty()) {
1171 NodeVect::iterator First = Roots.begin();
1172 GepNode *Root = *First, *Last = *First;
1173 Roots.erase(First);
1175 NodeVect NA; // Nodes to assemble.
1176 // Append to NA all child nodes up to (and including) the first child
1177 // that:
1178 // (1) has more than 1 child, or
1179 // (2) is used, or
1180 // (3) has a child located in a different block.
1181 bool LastUsed = false;
1182 unsigned LastCN = 0;
1183 // The location may be null if the computation failed (it can legitimately
1184 // happen for nodes created from dead GEPs).
1185 Value *LocV = Loc[Last];
1186 if (!LocV)
1187 continue;
1188 BasicBlock *LastB = cast<BasicBlock>(LocV);
1189 do {
1190 NA.push_back(Last);
1191 LastUsed = (Last->Flags & GepNode::Used);
1192 if (LastUsed)
1193 break;
1194 NodeChildrenMap::iterator CF = NCM.find(Last);
1195 LastCN = (CF != NCM.end()) ? CF->second.size() : 0;
1196 if (LastCN != 1)
1197 break;
1198 GepNode *Child = CF->second.front();
1199 BasicBlock *ChildB = cast_or_null<BasicBlock>(Loc[Child]);
1200 if (ChildB != nullptr && LastB != ChildB)
1201 break;
1202 Last = Child;
1203 } while (true);
1205 BasicBlock::iterator InsertAt = LastB->getTerminator()->getIterator();
1206 if (LastUsed || LastCN > 0) {
1207 ValueVect Urs;
1208 getAllUsersForNode(Root, Urs, NCM);
1209 BasicBlock::iterator FirstUse = first_use_of_in_block(Urs, LastB);
1210 if (FirstUse != LastB->end())
1211 InsertAt = FirstUse;
1214 // Generate a new instruction for NA.
1215 Value *NewInst = fabricateGEP(NA, InsertAt, LastB);
1217 // Convert all the children of Last node into roots, and append them
1218 // to the Roots list.
1219 if (LastCN > 0) {
1220 NodeVect &Cs = NCM[Last];
1221 for (NodeVect::iterator I = Cs.begin(), E = Cs.end(); I != E; ++I) {
1222 GepNode *CN = *I;
1223 CN->Flags &= ~GepNode::Internal;
1224 CN->Flags |= GepNode::Root;
1225 CN->BaseVal = NewInst;
1226 Roots.push_back(CN);
1230 // Lastly, if the Last node was used, replace all uses with the new GEP.
1231 // The uses reference the original GEP values.
1232 if (LastUsed) {
1233 NodeToUsesMap::iterator UF = Uses.find(Last);
1234 assert(UF != Uses.end() && "No use information found");
1235 UseSet &Us = UF->second;
1236 for (UseSet::iterator I = Us.begin(), E = Us.end(); I != E; ++I) {
1237 Use *U = *I;
1238 U->set(NewInst);
1244 void HexagonCommonGEP::removeDeadCode() {
1245 ValueVect BO;
1246 BO.push_back(&Fn->front());
1248 for (unsigned i = 0; i < BO.size(); ++i) {
1249 BasicBlock *B = cast<BasicBlock>(BO[i]);
1250 for (auto DTN : children<DomTreeNode*>(DT->getNode(B)))
1251 BO.push_back(DTN->getBlock());
1254 for (unsigned i = BO.size(); i > 0; --i) {
1255 BasicBlock *B = cast<BasicBlock>(BO[i-1]);
1256 BasicBlock::InstListType &IL = B->getInstList();
1258 using reverse_iterator = BasicBlock::InstListType::reverse_iterator;
1260 ValueVect Ins;
1261 for (reverse_iterator I = IL.rbegin(), E = IL.rend(); I != E; ++I)
1262 Ins.push_back(&*I);
1263 for (ValueVect::iterator I = Ins.begin(), E = Ins.end(); I != E; ++I) {
1264 Instruction *In = cast<Instruction>(*I);
1265 if (isInstructionTriviallyDead(In))
1266 In->eraseFromParent();
1271 bool HexagonCommonGEP::runOnFunction(Function &F) {
1272 if (skipFunction(F))
1273 return false;
1275 // For now bail out on C++ exception handling.
1276 for (Function::iterator A = F.begin(), Z = F.end(); A != Z; ++A)
1277 for (BasicBlock::iterator I = A->begin(), E = A->end(); I != E; ++I)
1278 if (isa<InvokeInst>(I) || isa<LandingPadInst>(I))
1279 return false;
1281 Fn = &F;
1282 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1283 PDT = &getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
1284 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1285 Ctx = &F.getContext();
1287 Nodes.clear();
1288 Uses.clear();
1289 NodeOrder.clear();
1291 SpecificBumpPtrAllocator<GepNode> Allocator;
1292 Mem = &Allocator;
1294 collect();
1295 common();
1297 NodeToValueMap Loc;
1298 computeNodePlacement(Loc);
1299 materialize(Loc);
1300 removeDeadCode();
1302 #ifdef EXPENSIVE_CHECKS
1303 // Run this only when expensive checks are enabled.
1304 verifyFunction(F);
1305 #endif
1306 return true;
1309 namespace llvm {
1311 FunctionPass *createHexagonCommonGEP() {
1312 return new HexagonCommonGEP();
1315 } // end namespace llvm