1 //===--- HexagonCommonGEP.cpp ---------------------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #define DEBUG_TYPE "commgep"
12 #include "llvm/Pass.h"
13 #include "llvm/ADT/FoldingSet.h"
14 #include "llvm/ADT/STLExtras.h"
15 #include "llvm/Analysis/LoopInfo.h"
16 #include "llvm/Analysis/PostDominators.h"
17 #include "llvm/CodeGen/MachineFunctionAnalysis.h"
18 #include "llvm/IR/Constants.h"
19 #include "llvm/IR/Dominators.h"
20 #include "llvm/IR/Function.h"
21 #include "llvm/IR/Instructions.h"
22 #include "llvm/IR/Verifier.h"
23 #include "llvm/Support/Allocator.h"
24 #include "llvm/Support/CommandLine.h"
25 #include "llvm/Support/Debug.h"
26 #include "llvm/Support/raw_ostream.h"
27 #include "llvm/Transforms/Scalar.h"
28 #include "llvm/Transforms/Utils/Local.h"
34 #include "HexagonTargetMachine.h"
38 static cl::opt<bool> OptSpeculate("commgep-speculate", cl::init(true),
39 cl::Hidden, cl::ZeroOrMore);
41 static cl::opt<bool> OptEnableInv("commgep-inv", cl::init(true), cl::Hidden,
44 static cl::opt<bool> OptEnableConst("commgep-const", cl::init(true),
45 cl::Hidden, cl::ZeroOrMore);
48 void initializeHexagonCommonGEPPass(PassRegistry&);
53 typedef std::set<GepNode*> NodeSet;
54 typedef std::map<GepNode*,Value*> NodeToValueMap;
55 typedef std::vector<GepNode*> NodeVect;
56 typedef std::map<GepNode*,NodeVect> NodeChildrenMap;
57 typedef std::set<Use*> UseSet;
58 typedef std::map<GepNode*,UseSet> NodeToUsesMap;
60 // Numbering map for gep nodes. Used to keep track of ordering for
62 struct NodeNumbering : public std::map<const GepNode*,unsigned> {
65 struct NodeOrdering : public NodeNumbering {
66 NodeOrdering() : LastNum(0) {}
68 void special_insert_for_special_msvc(const GepNode *N)
70 using NodeNumbering::insert;
71 void insert(const GepNode* N)
74 insert(std::make_pair(N, ++LastNum));
76 bool operator() (const GepNode* N1, const GepNode *N2) const {
77 const_iterator F1 = find(N1), F2 = find(N2);
78 assert(F1 != end() && F2 != end());
79 return F1->second < F2->second;
86 class HexagonCommonGEP : public FunctionPass {
89 HexagonCommonGEP() : FunctionPass(ID) {
90 initializeHexagonCommonGEPPass(*PassRegistry::getPassRegistry());
92 virtual bool runOnFunction(Function &F);
93 virtual const char *getPassName() const {
94 return "Hexagon Common GEP";
97 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
98 AU.addRequired<DominatorTreeWrapperPass>();
99 AU.addPreserved<DominatorTreeWrapperPass>();
100 AU.addRequired<PostDominatorTree>();
101 AU.addPreserved<PostDominatorTree>();
102 AU.addRequired<LoopInfoWrapperPass>();
103 AU.addPreserved<LoopInfoWrapperPass>();
104 FunctionPass::getAnalysisUsage(AU);
108 typedef std::map<Value*,GepNode*> ValueToNodeMap;
109 typedef std::vector<Value*> ValueVect;
110 typedef std::map<GepNode*,ValueVect> NodeToValuesMap;
112 void getBlockTraversalOrder(BasicBlock *Root, ValueVect &Order);
113 bool isHandledGepForm(GetElementPtrInst *GepI);
114 void processGepInst(GetElementPtrInst *GepI, ValueToNodeMap &NM);
118 BasicBlock *recalculatePlacement(GepNode *Node, NodeChildrenMap &NCM,
119 NodeToValueMap &Loc);
120 BasicBlock *recalculatePlacementRec(GepNode *Node, NodeChildrenMap &NCM,
121 NodeToValueMap &Loc);
122 bool isInvariantIn(Value *Val, Loop *L);
123 bool isInvariantIn(GepNode *Node, Loop *L);
124 bool isInMainPath(BasicBlock *B, Loop *L);
125 BasicBlock *adjustForInvariance(GepNode *Node, NodeChildrenMap &NCM,
126 NodeToValueMap &Loc);
127 void separateChainForNode(GepNode *Node, Use *U, NodeToValueMap &Loc);
128 void separateConstantChains(GepNode *Node, NodeChildrenMap &NCM,
129 NodeToValueMap &Loc);
130 void computeNodePlacement(NodeToValueMap &Loc);
132 Value *fabricateGEP(NodeVect &NA, BasicBlock::iterator At,
134 void getAllUsersForNode(GepNode *Node, ValueVect &Values,
135 NodeChildrenMap &NCM);
136 void materialize(NodeToValueMap &Loc);
138 void removeDeadCode();
142 NodeOrdering NodeOrder; // Node ordering, for deterministic behavior.
143 SpecificBumpPtrAllocator<GepNode> *Mem;
147 PostDominatorTree *PDT;
153 char HexagonCommonGEP::ID = 0;
154 INITIALIZE_PASS_BEGIN(HexagonCommonGEP, "hcommgep", "Hexagon Common GEP",
156 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
157 INITIALIZE_PASS_DEPENDENCY(PostDominatorTree)
158 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
159 INITIALIZE_PASS_END(HexagonCommonGEP, "hcommgep", "Hexagon Common GEP",
177 Type *PTy; // Type of the pointer operand.
179 GepNode() : Flags(0), Parent(0), Idx(0), PTy(0) {}
180 GepNode(const GepNode *N) : Flags(N->Flags), Idx(N->Idx), PTy(N->PTy) {
182 BaseVal = N->BaseVal;
186 friend raw_ostream &operator<< (raw_ostream &OS, const GepNode &GN);
190 Type *next_type(Type *Ty, Value *Idx) {
192 if (!Ty->isStructTy()) {
193 Type *NexTy = cast<SequentialType>(Ty)->getElementType();
196 // Otherwise it is a struct type.
197 ConstantInt *CI = dyn_cast<ConstantInt>(Idx);
198 assert(CI && "Struct type with non-constant index");
199 int64_t i = CI->getValue().getSExtValue();
200 Type *NextTy = cast<StructType>(Ty)->getElementType(i);
205 raw_ostream &operator<< (raw_ostream &OS, const GepNode &GN) {
208 if (GN.Flags & GepNode::Root) {
212 if (GN.Flags & GepNode::Internal) {
218 if (GN.Flags & GepNode::Used) {
225 if (GN.Flags & GepNode::Root)
226 OS << "BaseVal:" << GN.BaseVal->getName() << '(' << GN.BaseVal << ')';
228 OS << "Parent:" << GN.Parent;
231 if (ConstantInt *CI = dyn_cast<ConstantInt>(GN.Idx))
232 OS << CI->getValue().getSExtValue();
233 else if (GN.Idx->hasName())
234 OS << GN.Idx->getName();
236 OS << "<anon> =" << *GN.Idx;
239 if (GN.PTy->isStructTy()) {
240 StructType *STy = cast<StructType>(GN.PTy);
241 if (!STy->isLiteral())
242 OS << GN.PTy->getStructName();
244 OS << "<anon-struct>:" << *STy;
253 template <typename NodeContainer>
254 void dump_node_container(raw_ostream &OS, const NodeContainer &S) {
255 typedef typename NodeContainer::const_iterator const_iterator;
256 for (const_iterator I = S.begin(), E = S.end(); I != E; ++I)
257 OS << *I << ' ' << **I << '\n';
260 raw_ostream &operator<< (raw_ostream &OS,
261 const NodeVect &S) LLVM_ATTRIBUTE_UNUSED;
262 raw_ostream &operator<< (raw_ostream &OS, const NodeVect &S) {
263 dump_node_container(OS, S);
268 raw_ostream &operator<< (raw_ostream &OS,
269 const NodeToUsesMap &M) LLVM_ATTRIBUTE_UNUSED;
270 raw_ostream &operator<< (raw_ostream &OS, const NodeToUsesMap &M){
271 typedef NodeToUsesMap::const_iterator const_iterator;
272 for (const_iterator I = M.begin(), E = M.end(); I != E; ++I) {
273 const UseSet &Us = I->second;
274 OS << I->first << " -> #" << Us.size() << '{';
275 for (UseSet::const_iterator J = Us.begin(), F = Us.end(); J != F; ++J) {
276 User *R = (*J)->getUser();
278 OS << ' ' << R->getName();
280 OS << " <?>(" << *R << ')';
289 in_set(const NodeSet &S) : NS(S) {}
290 bool operator() (GepNode *N) const {
291 return NS.find(N) != NS.end();
299 inline void *operator new(size_t, SpecificBumpPtrAllocator<GepNode> &A) {
304 void HexagonCommonGEP::getBlockTraversalOrder(BasicBlock *Root,
306 // Compute block ordering for a typical DT-based traversal of the flow
307 // graph: "before visiting a block, all of its dominators must have been
310 Order.push_back(Root);
311 DomTreeNode *DTN = DT->getNode(Root);
312 typedef GraphTraits<DomTreeNode*> GTN;
313 typedef GTN::ChildIteratorType Iter;
314 for (Iter I = GTN::child_begin(DTN), E = GTN::child_end(DTN); I != E; ++I)
315 getBlockTraversalOrder((*I)->getBlock(), Order);
319 bool HexagonCommonGEP::isHandledGepForm(GetElementPtrInst *GepI) {
321 if (!GepI->getType()->isPointerTy())
323 // No GEPs without any indices. (Is this possible?)
324 if (GepI->idx_begin() == GepI->idx_end())
330 void HexagonCommonGEP::processGepInst(GetElementPtrInst *GepI,
331 ValueToNodeMap &NM) {
332 DEBUG(dbgs() << "Visiting GEP: " << *GepI << '\n');
333 GepNode *N = new (*Mem) GepNode;
334 Value *PtrOp = GepI->getPointerOperand();
335 ValueToNodeMap::iterator F = NM.find(PtrOp);
338 N->Flags |= GepNode::Root;
340 // If PtrOp was a GEP instruction, it must have already been processed.
341 // The ValueToNodeMap entry for it is the last gep node in the generated
342 // chain. Link to it here.
343 N->Parent = F->second;
345 N->PTy = PtrOp->getType();
346 N->Idx = *GepI->idx_begin();
348 // Collect the list of users of this GEP instruction. Will add it to the
349 // last node created for it.
351 for (Value::user_iterator UI = GepI->user_begin(), UE = GepI->user_end();
353 // Check if this gep is used by anything other than other geps that
355 if (isa<GetElementPtrInst>(*UI)) {
356 GetElementPtrInst *UserG = cast<GetElementPtrInst>(*UI);
357 if (isHandledGepForm(UserG))
360 Us.insert(&UI.getUse());
364 NodeOrder.special_insert_for_special_msvc(N);
369 // Skip the first index operand, since we only handle 0. This dereferences
370 // the pointer operand.
372 Type *PtrTy = cast<PointerType>(PtrOp->getType())->getElementType();
373 for (User::op_iterator OI = GepI->idx_begin()+1, OE = GepI->idx_end();
376 GepNode *Nx = new (*Mem) GepNode;
377 Nx->Parent = PN; // Link Nx to the previous node.
378 Nx->Flags |= GepNode::Internal;
383 NodeOrder.special_insert_for_special_msvc(Nx);
385 NodeOrder.insert(Nx);
389 PtrTy = next_type(PtrTy, Op);
392 // After last node has been created, update the use information.
394 PN->Flags |= GepNode::Used;
395 Uses[PN].insert(Us.begin(), Us.end());
398 // Link the last node with the originating GEP instruction. This is to
399 // help with linking chained GEP instructions.
400 NM.insert(std::make_pair(GepI, PN));
404 void HexagonCommonGEP::collect() {
405 // Establish depth-first traversal order of the dominator tree.
407 getBlockTraversalOrder(Fn->begin(), BO);
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.
413 for (ValueVect::iterator I = BO.begin(), E = BO.end(); I != E; ++I) {
414 BasicBlock *B = cast<BasicBlock>(*I);
415 for (BasicBlock::iterator J = B->begin(), F = B->end(); J != F; ++J) {
416 if (!isa<GetElementPtrInst>(J))
418 GetElementPtrInst *GepI = cast<GetElementPtrInst>(J);
419 if (isHandledGepForm(GepI))
420 processGepInst(GepI, NM);
424 DEBUG(dbgs() << "Gep nodes after initial collection:\n" << Nodes);
429 void invert_find_roots(const NodeVect &Nodes, NodeChildrenMap &NCM,
431 typedef NodeVect::const_iterator const_iterator;
432 for (const_iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) {
434 if (N->Flags & GepNode::Root) {
438 GepNode *PN = N->Parent;
439 NCM[PN].push_back(N);
443 void nodes_for_root(GepNode *Root, NodeChildrenMap &NCM, NodeSet &Nodes) {
445 Work.push_back(Root);
448 while (!Work.empty()) {
449 NodeVect::iterator First = Work.begin();
452 NodeChildrenMap::iterator CF = NCM.find(N);
453 if (CF != NCM.end()) {
454 Work.insert(Work.end(), CF->second.begin(), CF->second.end());
455 Nodes.insert(CF->second.begin(), CF->second.end());
463 typedef std::set<NodeSet> NodeSymRel;
464 typedef std::pair<GepNode*,GepNode*> NodePair;
465 typedef std::set<NodePair> NodePairSet;
467 const NodeSet *node_class(GepNode *N, NodeSymRel &Rel) {
468 for (NodeSymRel::iterator I = Rel.begin(), E = Rel.end(); I != E; ++I)
474 // Create an ordered pair of GepNode pointers. The pair will be used in
475 // determining equality. The only purpose of the ordering is to eliminate
476 // duplication due to the commutativity of equality/non-equality.
477 NodePair node_pair(GepNode *N1, GepNode *N2) {
478 uintptr_t P1 = uintptr_t(N1), P2 = uintptr_t(N2);
480 return std::make_pair(N1, N2);
481 return std::make_pair(N2, N1);
484 unsigned node_hash(GepNode *N) {
485 // Include everything except flags and parent.
487 ID.AddPointer(N->Idx);
488 ID.AddPointer(N->PTy);
489 return ID.ComputeHash();
492 bool node_eq(GepNode *N1, GepNode *N2, NodePairSet &Eq, NodePairSet &Ne) {
493 // Don't cache the result for nodes with different hashes. The hash
494 // comparison is fast enough.
495 if (node_hash(N1) != node_hash(N2))
498 NodePair NP = node_pair(N1, N2);
499 NodePairSet::iterator FEq = Eq.find(NP);
502 NodePairSet::iterator FNe = Ne.find(NP);
505 // Not previously compared.
506 bool Root1 = N1->Flags & GepNode::Root;
507 bool Root2 = N2->Flags & GepNode::Root;
508 NodePair P = node_pair(N1, N2);
509 // If the Root flag has different values, the nodes are different.
510 // If both nodes are root nodes, but their base pointers differ,
511 // they are different.
512 if (Root1 != Root2 || (Root1 && N1->BaseVal != N2->BaseVal)) {
516 // Here the root flags are identical, and for root nodes the
517 // base pointers are equal, so the root nodes are equal.
518 // For non-root nodes, compare their parent nodes.
519 if (Root1 || node_eq(N1->Parent, N2->Parent, Eq, Ne)) {
528 void HexagonCommonGEP::common() {
529 // The essence of this commoning is finding gep nodes that are equal.
530 // To do this we need to compare all pairs of nodes. To save time,
531 // first, partition the set of all nodes into sets of potentially equal
532 // nodes, and then compare pairs from within each partition.
533 typedef std::map<unsigned,NodeSet> NodeSetMap;
536 for (NodeVect::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) {
538 unsigned H = node_hash(N);
539 MaybeEq[H].insert(N);
542 // Compute the equivalence relation for the gep nodes. Use two caches,
543 // one for equality and the other for non-equality.
544 NodeSymRel EqRel; // Equality relation (as set of equivalence classes).
545 NodePairSet Eq, Ne; // Caches.
546 for (NodeSetMap::iterator I = MaybeEq.begin(), E = MaybeEq.end();
548 NodeSet &S = I->second;
549 for (NodeSet::iterator NI = S.begin(), NE = S.end(); NI != NE; ++NI) {
551 // If node already has a class, then the class must have been created
552 // in a prior iteration of this loop. Since equality is transitive,
553 // nothing more will be added to that class, so skip it.
554 if (node_class(N, EqRel))
557 // Create a new class candidate now.
559 for (NodeSet::iterator NJ = std::next(NI); NJ != NE; ++NJ)
560 if (node_eq(N, *NJ, Eq, Ne))
562 // If Tmp is empty, N would be the only element in it. Don't bother
563 // creating a class for it then.
565 C.insert(N); // Finalize the set before adding it to the relation.
566 std::pair<NodeSymRel::iterator, bool> Ins = EqRel.insert(C);
568 assert(Ins.second && "Cannot add a class");
574 dbgs() << "Gep node equality:\n";
575 for (NodePairSet::iterator I = Eq.begin(), E = Eq.end(); I != E; ++I)
576 dbgs() << "{ " << I->first << ", " << I->second << " }\n";
578 dbgs() << "Gep equivalence classes:\n";
579 for (NodeSymRel::iterator I = EqRel.begin(), E = EqRel.end(); I != E; ++I) {
581 const NodeSet &S = *I;
582 for (NodeSet::const_iterator J = S.begin(), F = S.end(); J != F; ++J) {
592 // Create a projection from a NodeSet to the minimal element in it.
593 typedef std::map<const NodeSet*,GepNode*> ProjMap;
595 for (NodeSymRel::iterator I = EqRel.begin(), E = EqRel.end(); I != E; ++I) {
596 const NodeSet &S = *I;
597 GepNode *Min = *std::min_element(S.begin(), S.end(), NodeOrder);
598 std::pair<ProjMap::iterator,bool> Ins = PM.insert(std::make_pair(&S, Min));
600 assert(Ins.second && "Cannot add minimal element");
602 // Update the min element's flags, and user list.
604 UseSet &MinUs = Uses[Min];
605 for (NodeSet::iterator J = S.begin(), F = S.end(); J != F; ++J) {
607 uint32_t NF = N->Flags;
608 // If N is used, append all original values of N to the list of
609 // original values of Min.
610 if (NF & GepNode::Used)
611 MinUs.insert(Uses[N].begin(), Uses[N].end());
617 // The collected flags should include all the flags from the min element.
618 assert((Min->Flags & Flags) == Min->Flags);
622 // Commoning: for each non-root gep node, replace "Parent" with the
623 // selected (minimum) node from the corresponding equivalence class.
624 // If a given parent does not have an equivalence class, leave it
625 // unchanged (it means that it's the only element in its class).
626 for (NodeVect::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) {
628 if (N->Flags & GepNode::Root)
630 const NodeSet *PC = node_class(N->Parent, EqRel);
633 ProjMap::iterator F = PM.find(PC);
636 // Found a replacement, use it.
637 GepNode *Rep = F->second;
641 DEBUG(dbgs() << "Gep nodes after commoning:\n" << Nodes);
643 // Finally, erase the nodes that are no longer used.
645 for (NodeVect::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) {
647 const NodeSet *PC = node_class(N, EqRel);
650 ProjMap::iterator F = PM.find(PC);
658 NodeVect::iterator NewE = std::remove_if(Nodes.begin(), Nodes.end(),
660 Nodes.resize(std::distance(Nodes.begin(), NewE));
662 DEBUG(dbgs() << "Gep nodes after post-commoning cleanup:\n" << Nodes);
667 template <typename T>
668 BasicBlock *nearest_common_dominator(DominatorTree *DT, T &Blocks) {
670 dbgs() << "NCD of {";
671 for (typename T::iterator I = Blocks.begin(), E = Blocks.end();
675 BasicBlock *B = cast<BasicBlock>(*I);
676 dbgs() << ' ' << B->getName();
681 // Allow null basic blocks in Blocks. In such cases, return 0.
682 typename T::iterator I = Blocks.begin(), E = Blocks.end();
685 BasicBlock *Dom = cast<BasicBlock>(*I);
687 BasicBlock *B = cast_or_null<BasicBlock>(*I);
688 Dom = B ? DT->findNearestCommonDominator(Dom, B) : 0;
692 DEBUG(dbgs() << "computed:" << Dom->getName() << '\n');
696 template <typename T>
697 BasicBlock *nearest_common_dominatee(DominatorTree *DT, T &Blocks) {
698 // If two blocks, A and B, dominate a block C, then A dominates B,
700 typename T::iterator I = Blocks.begin(), E = Blocks.end();
701 // Find the first non-null block.
702 while (I != E && !*I)
705 return DT->getRoot();
706 BasicBlock *DomB = cast<BasicBlock>(*I);
710 BasicBlock *B = cast<BasicBlock>(*I);
711 if (DT->dominates(B, DomB))
713 if (!DT->dominates(DomB, B))
720 // Find the first use in B of any value from Values. If no such use,
722 template <typename T>
723 BasicBlock::iterator first_use_of_in_block(T &Values, BasicBlock *B) {
724 BasicBlock::iterator FirstUse = B->end(), BEnd = B->end();
725 typedef typename T::iterator iterator;
726 for (iterator I = Values.begin(), E = Values.end(); I != E; ++I) {
728 // If V is used in a PHI node, the use belongs to the incoming block,
729 // not the block with the PHI node. In the incoming block, the use
730 // would be considered as being at the end of it, so it cannot
731 // influence the position of the first use (which is assumed to be
732 // at the end to start with).
735 if (!isa<Instruction>(V))
737 Instruction *In = cast<Instruction>(V);
738 if (In->getParent() != B)
740 BasicBlock::iterator It = In;
741 if (std::distance(FirstUse, BEnd) < std::distance(It, BEnd))
747 bool is_empty(const BasicBlock *B) {
748 return B->empty() || (&*B->begin() == B->getTerminator());
753 BasicBlock *HexagonCommonGEP::recalculatePlacement(GepNode *Node,
754 NodeChildrenMap &NCM, NodeToValueMap &Loc) {
755 DEBUG(dbgs() << "Loc for node:" << Node << '\n');
756 // Recalculate the placement for Node, assuming that the locations of
757 // its children in Loc are valid.
758 // Return 0 if there is no valid placement for Node (for example, it
759 // uses an index value that is not available at the location required
760 // to dominate all children, etc.).
762 // Find the nearest common dominator for:
763 // - all users, if the node is used, and
766 if (Node->Flags & GepNode::Used) {
767 // Append all blocks with uses of the original values to the
769 NodeToUsesMap::iterator UF = Uses.find(Node);
770 assert(UF != Uses.end() && "Used node with no use information");
771 UseSet &Us = UF->second;
772 for (UseSet::iterator I = Us.begin(), E = Us.end(); I != E; ++I) {
774 User *R = U->getUser();
775 if (!isa<Instruction>(R))
777 BasicBlock *PB = isa<PHINode>(R)
778 ? cast<PHINode>(R)->getIncomingBlock(*U)
779 : cast<Instruction>(R)->getParent();
783 // Append the location of each child.
784 NodeChildrenMap::iterator CF = NCM.find(Node);
785 if (CF != NCM.end()) {
786 NodeVect &Cs = CF->second;
787 for (NodeVect::iterator I = Cs.begin(), E = Cs.end(); I != E; ++I) {
789 NodeToValueMap::iterator LF = Loc.find(CN);
790 // If the child is only used in GEP instructions (i.e. is not used in
791 // non-GEP instructions), the nearest dominator computed for it may
792 // have been null. In such case it won't have a location available.
795 Bs.push_back(LF->second);
799 BasicBlock *DomB = nearest_common_dominator(DT, Bs);
802 // Check if the index used by Node dominates the computed dominator.
803 Instruction *IdxI = dyn_cast<Instruction>(Node->Idx);
804 if (IdxI && !DT->dominates(IdxI->getParent(), DomB))
807 // Avoid putting nodes into empty blocks.
808 while (is_empty(DomB)) {
809 DomTreeNode *N = (*DT)[DomB]->getIDom();
812 DomB = N->getBlock();
815 // Otherwise, DomB is fine. Update the location map.
821 BasicBlock *HexagonCommonGEP::recalculatePlacementRec(GepNode *Node,
822 NodeChildrenMap &NCM, NodeToValueMap &Loc) {
823 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 DEBUG(dbgs() << "LocRec end for node:" << Node << '\n');
838 bool HexagonCommonGEP::isInvariantIn(Value *Val, Loop *L) {
839 if (isa<Constant>(Val) || isa<Argument>(Val))
841 Instruction *In = dyn_cast<Instruction>(Val);
844 BasicBlock *HdrB = L->getHeader(), *DefB = In->getParent();
845 return DT->properlyDominates(DefB, HdrB);
849 bool HexagonCommonGEP::isInvariantIn(GepNode *Node, Loop *L) {
850 if (Node->Flags & GepNode::Root)
851 if (!isInvariantIn(Node->BaseVal, L))
853 return isInvariantIn(Node->Idx, L);
857 bool HexagonCommonGEP::isInMainPath(BasicBlock *B, Loop *L) {
858 BasicBlock *HB = L->getHeader();
859 BasicBlock *LB = L->getLoopLatch();
860 // B must post-dominate the loop header or dominate the loop latch.
861 if (PDT->dominates(B, HB))
863 if (LB && DT->dominates(B, LB))
870 BasicBlock *preheader(DominatorTree *DT, Loop *L) {
871 if (BasicBlock *PH = L->getLoopPreheader())
875 DomTreeNode *DN = DT->getNode(L->getHeader());
878 return DN->getIDom()->getBlock();
883 BasicBlock *HexagonCommonGEP::adjustForInvariance(GepNode *Node,
884 NodeChildrenMap &NCM, NodeToValueMap &Loc) {
885 // Find the "topmost" location for Node: it must be dominated by both,
886 // its parent (or the BaseVal, if it's a root node), and by the index
889 if (Node->Flags & GepNode::Root) {
890 if (Instruction *PIn = dyn_cast<Instruction>(Node->BaseVal))
891 Bs.push_back(PIn->getParent());
893 Bs.push_back(Loc[Node->Parent]);
895 if (Instruction *IIn = dyn_cast<Instruction>(Node->Idx))
896 Bs.push_back(IIn->getParent());
897 BasicBlock *TopB = nearest_common_dominatee(DT, Bs);
899 // Traverse the loop nest upwards until we find a loop in which Node
900 // is no longer invariant, or until we get to the upper limit of Node's
901 // placement. The traversal will also stop when a suitable "preheader"
902 // cannot be found for a given loop. The "preheader" may actually be
903 // a regular block outside of the loop (i.e. not guarded), in which case
904 // the Node will be speculated.
905 // For nodes that are not in the main path of the containing loop (i.e.
906 // are not executed in each iteration), do not move them out of the loop.
907 BasicBlock *LocB = cast_or_null<BasicBlock>(Loc[Node]);
909 Loop *Lp = LI->getLoopFor(LocB);
911 if (!isInvariantIn(Node, Lp) || !isInMainPath(LocB, Lp))
913 BasicBlock *NewLoc = preheader(DT, Lp);
914 if (!NewLoc || !DT->dominates(TopB, NewLoc))
916 Lp = Lp->getParentLoop();
922 // Recursively compute the locations of all children nodes.
923 NodeChildrenMap::iterator CF = NCM.find(Node);
924 if (CF != NCM.end()) {
925 NodeVect &Cs = CF->second;
926 for (NodeVect::iterator I = Cs.begin(), E = Cs.end(); I != E; ++I)
927 adjustForInvariance(*I, NCM, Loc);
934 struct LocationAsBlock {
935 LocationAsBlock(const NodeToValueMap &L) : Map(L) {}
936 const NodeToValueMap ⤅
939 raw_ostream &operator<< (raw_ostream &OS,
940 const LocationAsBlock &Loc) LLVM_ATTRIBUTE_UNUSED ;
941 raw_ostream &operator<< (raw_ostream &OS, const LocationAsBlock &Loc) {
942 for (NodeToValueMap::const_iterator I = Loc.Map.begin(), E = Loc.Map.end();
944 OS << I->first << " -> ";
945 BasicBlock *B = cast<BasicBlock>(I->second);
946 OS << B->getName() << '(' << B << ')';
952 inline bool is_constant(GepNode *N) {
953 return isa<ConstantInt>(N->Idx);
958 void HexagonCommonGEP::separateChainForNode(GepNode *Node, Use *U,
959 NodeToValueMap &Loc) {
960 User *R = U->getUser();
961 DEBUG(dbgs() << "Separating chain for node (" << Node << ") user: "
963 BasicBlock *PB = cast<Instruction>(R)->getParent();
966 GepNode *C = 0, *NewNode = 0;
967 while (is_constant(N) && !(N->Flags & GepNode::Root)) {
968 // XXX if (single-use) dont-replicate;
969 GepNode *NewN = new (*Mem) GepNode(N);
970 Nodes.push_back(NewN);
975 NewN->Flags &= ~GepNode::Used;
984 // Move over all uses that share the same user as U from Node to NewNode.
985 NodeToUsesMap::iterator UF = Uses.find(Node);
986 assert(UF != Uses.end());
987 UseSet &Us = UF->second;
989 for (UseSet::iterator I = Us.begin(); I != Us.end(); ) {
990 User *S = (*I)->getUser();
991 UseSet::iterator Nx = std::next(I);
999 Node->Flags &= ~GepNode::Used;
1003 // Should at least have U in NewUs.
1004 NewNode->Flags |= GepNode::Used;
1005 DEBUG(dbgs() << "new node: " << NewNode << " " << *NewNode << '\n');
1006 assert(!NewUs.empty());
1007 Uses[NewNode] = NewUs;
1011 void HexagonCommonGEP::separateConstantChains(GepNode *Node,
1012 NodeChildrenMap &NCM, NodeToValueMap &Loc) {
1013 // First approximation: extract all chains.
1015 nodes_for_root(Node, NCM, Ns);
1017 DEBUG(dbgs() << "Separating constant chains for node: " << Node << '\n');
1018 // Collect all used nodes together with the uses from loads and stores,
1019 // where the GEP node could be folded into the load/store instruction.
1020 NodeToUsesMap FNs; // Foldable nodes.
1021 for (NodeSet::iterator I = Ns.begin(), E = Ns.end(); I != E; ++I) {
1023 if (!(N->Flags & GepNode::Used))
1025 NodeToUsesMap::iterator UF = Uses.find(N);
1026 assert(UF != Uses.end());
1027 UseSet &Us = UF->second;
1028 // Loads/stores that use the node N.
1030 for (UseSet::iterator J = Us.begin(), F = Us.end(); J != F; ++J) {
1032 User *R = U->getUser();
1033 // We're interested in uses that provide the address. It can happen
1034 // that the value may also be provided via GEP, but we won't handle
1035 // those cases here for now.
1036 if (LoadInst *Ld = dyn_cast<LoadInst>(R)) {
1037 unsigned PtrX = LoadInst::getPointerOperandIndex();
1038 if (&Ld->getOperandUse(PtrX) == U)
1040 } else if (StoreInst *St = dyn_cast<StoreInst>(R)) {
1041 unsigned PtrX = StoreInst::getPointerOperandIndex();
1042 if (&St->getOperandUse(PtrX) == U)
1046 // Even if the total use count is 1, separating the chain may still be
1047 // beneficial, since the constant chain may be longer than the GEP alone
1048 // would be (e.g. if the parent node has a constant index and also has
1051 FNs.insert(std::make_pair(N, LSs));
1054 DEBUG(dbgs() << "Nodes with foldable users:\n" << FNs);
1056 for (NodeToUsesMap::iterator I = FNs.begin(), E = FNs.end(); I != E; ++I) {
1057 GepNode *N = I->first;
1058 UseSet &Us = I->second;
1059 for (UseSet::iterator J = Us.begin(), F = Us.end(); J != F; ++J)
1060 separateChainForNode(N, *J, Loc);
1065 void HexagonCommonGEP::computeNodePlacement(NodeToValueMap &Loc) {
1066 // Compute the inverse of the Node.Parent links. Also, collect the set
1068 NodeChildrenMap NCM;
1070 invert_find_roots(Nodes, NCM, Roots);
1072 // Compute the initial placement determined by the users' locations, and
1073 // the locations of the child nodes.
1074 for (NodeVect::iterator I = Roots.begin(), E = Roots.end(); I != E; ++I)
1075 recalculatePlacementRec(*I, NCM, Loc);
1077 DEBUG(dbgs() << "Initial node placement:\n" << LocationAsBlock(Loc));
1080 for (NodeVect::iterator I = Roots.begin(), E = Roots.end(); I != E; ++I)
1081 adjustForInvariance(*I, NCM, Loc);
1083 DEBUG(dbgs() << "Node placement after adjustment for invariance:\n"
1084 << LocationAsBlock(Loc));
1086 if (OptEnableConst) {
1087 for (NodeVect::iterator I = Roots.begin(), E = Roots.end(); I != E; ++I)
1088 separateConstantChains(*I, NCM, Loc);
1090 DEBUG(dbgs() << "Node use information:\n" << Uses);
1092 // At the moment, there is no further refinement of the initial placement.
1093 // Such a refinement could include splitting the nodes if they are placed
1094 // too far from some of its users.
1096 DEBUG(dbgs() << "Final node placement:\n" << LocationAsBlock(Loc));
1100 Value *HexagonCommonGEP::fabricateGEP(NodeVect &NA, BasicBlock::iterator At,
1102 DEBUG(dbgs() << "Fabricating GEP in " << LocB->getName()
1103 << " for nodes:\n" << NA);
1104 unsigned Num = NA.size();
1105 GepNode *RN = NA[0];
1106 assert((RN->Flags & GepNode::Root) && "Creating GEP for non-root");
1109 Value *Input = RN->BaseVal;
1110 Value **IdxList = new Value*[Num+1];
1114 // If the type of the input of the first node is not a pointer,
1115 // we need to add an artificial i32 0 to the indices (because the
1116 // actual input in the IR will be a pointer).
1117 if (!NA[nax]->PTy->isPointerTy()) {
1118 Type *Int32Ty = Type::getInt32Ty(*Ctx);
1119 IdxList[IdxC++] = ConstantInt::get(Int32Ty, 0);
1122 // Keep adding indices from NA until we have to stop and generate
1123 // an "intermediate" GEP.
1124 while (++nax <= Num) {
1125 GepNode *N = NA[nax-1];
1126 IdxList[IdxC++] = N->Idx;
1128 // We have to stop, if the expected type of the output of this node
1129 // is not the same as the input type of the next node.
1130 Type *NextTy = next_type(N->PTy, N->Idx);
1131 if (NextTy != NA[nax]->PTy)
1135 ArrayRef<Value*> A(IdxList, IdxC);
1136 Type *InpTy = Input->getType();
1137 Type *ElTy = cast<PointerType>(InpTy->getScalarType())->getElementType();
1138 NewInst = GetElementPtrInst::Create(ElTy, Input, A, "cgep", At);
1139 DEBUG(dbgs() << "new GEP: " << *NewInst << '\n');
1141 } while (nax <= Num);
1148 void HexagonCommonGEP::getAllUsersForNode(GepNode *Node, ValueVect &Values,
1149 NodeChildrenMap &NCM) {
1151 Work.push_back(Node);
1153 while (!Work.empty()) {
1154 NodeVect::iterator First = Work.begin();
1155 GepNode *N = *First;
1157 if (N->Flags & GepNode::Used) {
1158 NodeToUsesMap::iterator UF = Uses.find(N);
1159 assert(UF != Uses.end() && "No use information for used node");
1160 UseSet &Us = UF->second;
1161 for (UseSet::iterator I = Us.begin(), E = Us.end(); I != E; ++I)
1162 Values.push_back((*I)->getUser());
1164 NodeChildrenMap::iterator CF = NCM.find(N);
1165 if (CF != NCM.end()) {
1166 NodeVect &Cs = CF->second;
1167 Work.insert(Work.end(), Cs.begin(), Cs.end());
1173 void HexagonCommonGEP::materialize(NodeToValueMap &Loc) {
1174 DEBUG(dbgs() << "Nodes before materialization:\n" << Nodes << '\n');
1175 NodeChildrenMap NCM;
1177 // Compute the inversion again, since computing placement could alter
1178 // "parent" relation between nodes.
1179 invert_find_roots(Nodes, NCM, Roots);
1181 while (!Roots.empty()) {
1182 NodeVect::iterator First = Roots.begin();
1183 GepNode *Root = *First, *Last = *First;
1186 NodeVect NA; // Nodes to assemble.
1187 // Append to NA all child nodes up to (and including) the first child
1189 // (1) has more than 1 child, or
1191 // (3) has a child located in a different block.
1192 bool LastUsed = false;
1193 unsigned LastCN = 0;
1194 // The location may be null if the computation failed (it can legitimately
1195 // happen for nodes created from dead GEPs).
1196 Value *LocV = Loc[Last];
1199 BasicBlock *LastB = cast<BasicBlock>(LocV);
1202 LastUsed = (Last->Flags & GepNode::Used);
1205 NodeChildrenMap::iterator CF = NCM.find(Last);
1206 LastCN = (CF != NCM.end()) ? CF->second.size() : 0;
1209 GepNode *Child = CF->second.front();
1210 BasicBlock *ChildB = cast_or_null<BasicBlock>(Loc[Child]);
1211 if (ChildB != 0 && LastB != ChildB)
1216 BasicBlock::iterator InsertAt = LastB->getTerminator();
1217 if (LastUsed || LastCN > 0) {
1219 getAllUsersForNode(Root, Urs, NCM);
1220 BasicBlock::iterator FirstUse = first_use_of_in_block(Urs, LastB);
1221 if (FirstUse != LastB->end())
1222 InsertAt = FirstUse;
1225 // Generate a new instruction for NA.
1226 Value *NewInst = fabricateGEP(NA, InsertAt, LastB);
1228 // Convert all the children of Last node into roots, and append them
1229 // to the Roots list.
1231 NodeVect &Cs = NCM[Last];
1232 for (NodeVect::iterator I = Cs.begin(), E = Cs.end(); I != E; ++I) {
1234 CN->Flags &= ~GepNode::Internal;
1235 CN->Flags |= GepNode::Root;
1236 CN->BaseVal = NewInst;
1237 Roots.push_back(CN);
1241 // Lastly, if the Last node was used, replace all uses with the new GEP.
1242 // The uses reference the original GEP values.
1244 NodeToUsesMap::iterator UF = Uses.find(Last);
1245 assert(UF != Uses.end() && "No use information found");
1246 UseSet &Us = UF->second;
1247 for (UseSet::iterator I = Us.begin(), E = Us.end(); I != E; ++I) {
1256 void HexagonCommonGEP::removeDeadCode() {
1258 BO.push_back(&Fn->front());
1260 for (unsigned i = 0; i < BO.size(); ++i) {
1261 BasicBlock *B = cast<BasicBlock>(BO[i]);
1262 DomTreeNode *N = DT->getNode(B);
1263 typedef GraphTraits<DomTreeNode*> GTN;
1264 typedef GTN::ChildIteratorType Iter;
1265 for (Iter I = GTN::child_begin(N), E = GTN::child_end(N); I != E; ++I)
1266 BO.push_back((*I)->getBlock());
1269 for (unsigned i = BO.size(); i > 0; --i) {
1270 BasicBlock *B = cast<BasicBlock>(BO[i-1]);
1271 BasicBlock::InstListType &IL = B->getInstList();
1272 typedef BasicBlock::InstListType::reverse_iterator reverse_iterator;
1274 for (reverse_iterator I = IL.rbegin(), E = IL.rend(); I != E; ++I)
1276 for (ValueVect::iterator I = Ins.begin(), E = Ins.end(); I != E; ++I) {
1277 Instruction *In = cast<Instruction>(*I);
1278 if (isInstructionTriviallyDead(In))
1279 In->eraseFromParent();
1285 bool HexagonCommonGEP::runOnFunction(Function &F) {
1286 // For now bail out on C++ exception handling.
1287 for (Function::iterator A = F.begin(), Z = F.end(); A != Z; ++A)
1288 for (BasicBlock::iterator I = A->begin(), E = A->end(); I != E; ++I)
1289 if (isa<InvokeInst>(I) || isa<LandingPadInst>(I))
1293 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1294 PDT = &getAnalysis<PostDominatorTree>();
1295 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1296 Ctx = &F.getContext();
1302 SpecificBumpPtrAllocator<GepNode> Allocator;
1309 computeNodePlacement(Loc);
1314 // Run this only when expensive checks are enabled.
1322 FunctionPass *createHexagonCommonGEP() {
1323 return new HexagonCommonGEP();