49 #define DEBUG_TYPE "commgep"
71 using NodeSet = std::set<GepNode *>;
72 using NodeToValueMap = std::map<GepNode *, Value *>;
73 using NodeVect = std::vector<GepNode *>;
74 using NodeChildrenMap = std::map<GepNode *, NodeVect>;
76 using NodeToUsesMap = std::map<GepNode *, UseSet>;
81 NodeOrdering() =
default;
83 void insert(
const GepNode *
N) {
Map.insert(std::make_pair(
N, ++LastNum)); }
86 bool operator()(
const GepNode *N1,
const GepNode *N2)
const {
87 auto F1 =
Map.find(N1), F2 =
Map.find(N2);
89 return F1->second < F2->second;
93 std::map<const GepNode *, unsigned>
Map;
106 StringRef getPassName()
const override {
return "Hexagon Common GEP"; }
119 using ValueToNodeMap = std::map<Value *, GepNode *>;
120 using ValueVect = std::vector<Value *>;
121 using NodeToValuesMap = std::map<GepNode *, ValueVect>;
123 void getBlockTraversalOrder(
BasicBlock *Root, ValueVect &Order);
129 BasicBlock *recalculatePlacement(GepNode *Node, NodeChildrenMap &NCM,
130 NodeToValueMap &Loc);
131 BasicBlock *recalculatePlacementRec(GepNode *Node, NodeChildrenMap &NCM,
132 NodeToValueMap &Loc);
134 bool isInvariantIn(GepNode *Node,
Loop *L);
136 BasicBlock *adjustForInvariance(GepNode *Node, NodeChildrenMap &NCM,
137 NodeToValueMap &Loc);
138 void separateChainForNode(GepNode *Node,
Use *U, NodeToValueMap &Loc);
139 void separateConstantChains(GepNode *Node, NodeChildrenMap &NCM,
140 NodeToValueMap &Loc);
141 void computeNodePlacement(NodeToValueMap &Loc);
145 void getAllUsersForNode(GepNode *Node, ValueVect &Values,
146 NodeChildrenMap &NCM);
147 void materialize(NodeToValueMap &Loc);
149 void removeDeadCode();
196 BaseVal =
N->BaseVal;
205 if (
auto *PTy = dyn_cast<PointerType>(Ty))
206 return PTy->getElementType();
213 if (GN.
Flags & GepNode::Root) {
217 if (GN.
Flags & GepNode::Internal) {
223 if (GN.
Flags & GepNode::Used) {
228 if (GN.
Flags & GepNode::InBounds) {
234 if (GN.
Flags & GepNode::Root)
237 OS <<
"Parent:" << GN.
Parent;
241 OS << CI->getValue().getSExtValue();
245 OS <<
"<anon> =" << *GN.
Idx;
253 OS <<
"<anon-struct>:" << *STy;
261 template <
typename NodeContainer>
263 using const_iterator =
typename NodeContainer::const_iterator;
265 for (const_iterator
I =
S.begin(),
E =
S.end();
I !=
E; ++
I)
266 OS << *
I <<
' ' << **
I <<
'\n';
279 using const_iterator = NodeToUsesMap::const_iterator;
281 for (const_iterator
I =
M.begin(),
E =
M.end();
I !=
E; ++
I) {
282 const UseSet &Us =
I->second;
283 OS <<
I->first <<
" -> #" << Us.size() <<
'{';
284 for (UseSet::const_iterator J = Us.begin(),
F = Us.end(); J !=
F; ++J) {
285 User *R = (*J)->getUser();
287 OS <<
' ' << R->getName();
289 OS <<
" <?>(" << *R <<
')';
300 return NS.find(
N) != NS.end();
313 void HexagonCommonGEP::getBlockTraversalOrder(
BasicBlock *Root,
319 Order.push_back(Root);
320 for (
auto *DTN : children<DomTreeNode*>(DT->getNode(Root)))
321 getBlockTraversalOrder(DTN->getBlock(), Order);
335 ValueToNodeMap &NM) {
337 GepNode *
N =
new (*Mem) GepNode;
340 ValueToNodeMap::iterator
F = NM.find(PtrOp);
343 N->Flags |= GepNode::Root | InBounds;
348 N->Parent =
F->second;
360 if (isa<GetElementPtrInst>(*UI)) {
362 if (isHandledGepForm(UserG))
365 Us.insert(&UI.getUse());
373 Type *PtrTy = cast<PointerType>(PtrOp->
getType())->getElementType();
377 GepNode *Nx =
new (*Mem) GepNode;
379 Nx->Flags |= GepNode::Internal | InBounds;
391 PN->Flags |= GepNode::Used;
392 Uses[PN].insert(Us.begin(), Us.end());
397 NM.insert(std::make_pair(GepI, PN));
400 void HexagonCommonGEP::collect() {
403 getBlockTraversalOrder(&Fn->front(), BO);
409 for (ValueVect::iterator
I = BO.begin(),
E = BO.end();
I !=
E; ++
I) {
412 if (!isa<GetElementPtrInst>(J))
415 if (isHandledGepForm(GepI))
416 processGepInst(GepI, NM);
420 LLVM_DEBUG(
dbgs() <<
"Gep nodes after initial collection:\n" << Nodes);
425 using const_iterator = NodeVect::const_iterator;
427 for (const_iterator
I = Nodes.begin(),
E = Nodes.end();
I !=
E; ++
I) {
429 if (
N->Flags & GepNode::Root) {
433 GepNode *PN =
N->Parent;
434 NCM[PN].push_back(
N);
441 Work.push_back(Root);
444 while (!Work.empty()) {
445 NodeVect::iterator
First = Work.begin();
448 NodeChildrenMap::iterator CF = NCM.find(
N);
449 if (CF != NCM.end()) {
451 Nodes.
insert(CF->second.begin(), CF->second.end());
458 using NodeSymRel = std::set<NodeSet>;
459 using NodePair = std::pair<GepNode *, GepNode *>;
460 using NodePairSet = std::set<NodePair>;
465 for (NodeSymRel::iterator
I = Rel.begin(),
E = Rel.end();
I !=
E; ++
I)
475 uintptr_t P1 =
reinterpret_cast<uintptr_t
>(N1);
476 uintptr_t
P2 =
reinterpret_cast<uintptr_t
>(N2);
478 return std::make_pair(N1, N2);
479 return std::make_pair(N2, N1);
485 ID.AddPointer(
N->Idx);
486 ID.AddPointer(
N->PTy);
487 return ID.ComputeHash();
490 static bool node_eq(GepNode *N1, GepNode *N2, NodePairSet &Eq,
498 NodePairSet::iterator FEq = Eq.find(NP);
501 NodePairSet::iterator FNe = Ne.find(NP);
505 bool Root1 = N1->Flags & GepNode::Root;
506 bool Root2 = N2->Flags & GepNode::Root;
511 if (Root1 != Root2 || (Root1 && N1->BaseVal != N2->BaseVal)) {
518 if (Root1 ||
node_eq(N1->Parent, N2->Parent, Eq, Ne)) {
525 void HexagonCommonGEP::common() {
530 using NodeSetMap = std::map<unsigned, NodeSet>;
533 for (NodeVect::iterator
I = Nodes.begin(),
E = Nodes.end();
I !=
E; ++
I) {
536 MaybeEq[
H].insert(
N);
543 for (NodeSetMap::iterator
I = MaybeEq.begin(),
E = MaybeEq.end();
563 std::pair<NodeSymRel::iterator, bool>
Ins = EqRel.insert(
C);
565 assert(
Ins.second &&
"Cannot add a class");
571 dbgs() <<
"Gep node equality:\n";
572 for (NodePairSet::iterator
I = Eq.begin(),
E = Eq.end();
I !=
E; ++
I)
573 dbgs() <<
"{ " <<
I->first <<
", " <<
I->second <<
" }\n";
575 dbgs() <<
"Gep equivalence classes:\n";
576 for (NodeSymRel::iterator
I = EqRel.begin(),
E = EqRel.end();
I !=
E; ++
I) {
579 for (NodeSet::const_iterator J =
S.begin(),
F =
S.end(); J !=
F; ++J) {
589 using ProjMap = std::map<const NodeSet *, GepNode *>;
591 for (NodeSymRel::iterator
I = EqRel.begin(),
E = EqRel.end();
I !=
E; ++
I) {
593 GepNode *Min = *std::min_element(
S.begin(),
S.end(),
NodeOrder);
594 std::pair<ProjMap::iterator,bool>
Ins = PM.insert(std::make_pair(&
S, Min));
596 assert(
Ins.second &&
"Cannot add minimal element");
600 UseSet &MinUs =
Uses[Min];
606 if (NF & GepNode::Used)
614 assert((Min->Flags & Flags) == Min->Flags);
622 for (NodeVect::iterator
I = Nodes.begin(),
E = Nodes.end();
I !=
E; ++
I) {
624 if (
N->Flags & GepNode::Root)
629 ProjMap::iterator
F = PM.find(PC);
633 GepNode *Rep =
F->second;
641 for (NodeVect::iterator
I = Nodes.begin(),
E = Nodes.end();
I !=
E; ++
I) {
646 ProjMap::iterator
F = PM.find(PC);
656 LLVM_DEBUG(
dbgs() <<
"Gep nodes after post-commoning cleanup:\n" << Nodes);
659 template <
typename T>
662 dbgs() <<
"NCD of {";
663 for (
typename T::iterator
I = Blocks.begin(),
E = Blocks.end();
I !=
E;
668 dbgs() <<
' ' <<
B->getName();
674 typename T::iterator
I = Blocks.begin(),
E = Blocks.end();
688 template <
typename T>
692 typename T::iterator
I = Blocks.begin(),
E = Blocks.end();
694 while (
I !=
E && !*
I)
714 template <
typename T>
718 using iterator =
typename T::iterator;
720 for (iterator
I = Values.begin(),
E = Values.end();
I !=
E; ++
I) {
729 if (!isa<Instruction>(V))
732 if (
In->getParent() !=
B)
735 if (std::distance(FirstUse, BEnd) < std::distance(It, BEnd))
742 return B->empty() || (&*
B->begin() ==
B->getTerminator());
745 BasicBlock *HexagonCommonGEP::recalculatePlacement(GepNode *Node,
746 NodeChildrenMap &NCM, NodeToValueMap &Loc) {
758 if (Node->Flags & GepNode::Used) {
761 NodeToUsesMap::iterator UF =
Uses.find(Node);
762 assert(UF !=
Uses.end() &&
"Used node with no use information");
763 UseSet &Us = UF->second;
764 for (UseSet::iterator
I = Us.begin(),
E = Us.end();
I !=
E; ++
I) {
766 User *
R = U->getUser();
767 if (!isa<Instruction>(R))
770 ? cast<PHINode>(R)->getIncomingBlock(*U)
776 NodeChildrenMap::iterator CF = NCM.find(Node);
777 if (CF != NCM.end()) {
778 NodeVect &Cs = CF->second;
779 for (NodeVect::iterator
I = Cs.begin(),
E = Cs.end();
I !=
E; ++
I) {
781 NodeToValueMap::iterator LF = Loc.find(CN);
787 Bs.push_back(LF->second);
795 Instruction *IdxI = dyn_cast<Instruction>(Node->Idx);
796 if (IdxI && !DT->dominates(IdxI->
getParent(), DomB))
804 DomB =
N->getBlock();
812 BasicBlock *HexagonCommonGEP::recalculatePlacementRec(GepNode *Node,
813 NodeChildrenMap &NCM, NodeToValueMap &Loc) {
817 NodeChildrenMap::iterator CF = NCM.find(Node);
818 if (CF != NCM.end()) {
819 NodeVect &Cs = CF->second;
820 for (NodeVect::iterator
I = Cs.begin(),
E = Cs.end();
I !=
E; ++
I)
821 recalculatePlacementRec(*
I, NCM, Loc);
823 BasicBlock *LB = recalculatePlacement(Node, NCM, Loc);
828 bool HexagonCommonGEP::isInvariantIn(
Value *Val,
Loop *L) {
829 if (isa<Constant>(Val) || isa<Argument>(Val))
835 return DT->properlyDominates(DefB, HdrB);
838 bool HexagonCommonGEP::isInvariantIn(GepNode *Node,
Loop *L) {
839 if (Node->Flags & GepNode::Root)
840 if (!isInvariantIn(Node->BaseVal, L))
842 return isInvariantIn(Node->Idx, L);
849 if (PDT->dominates(
B, HB))
851 if (LB && DT->dominates(
B, LB))
867 BasicBlock *HexagonCommonGEP::adjustForInvariance(GepNode *Node,
868 NodeChildrenMap &NCM, NodeToValueMap &Loc) {
873 if (Node->Flags & GepNode::Root) {
874 if (
Instruction *PIn = dyn_cast<Instruction>(Node->BaseVal))
875 Bs.push_back(PIn->getParent());
877 Bs.push_back(Loc[Node->Parent]);
879 if (
Instruction *IIn = dyn_cast<Instruction>(Node->Idx))
880 Bs.push_back(IIn->getParent());
891 BasicBlock *LocB = cast_or_null<BasicBlock>(Loc[Node]);
893 Loop *Lp = LI->getLoopFor(LocB);
895 if (!isInvariantIn(Node, Lp) || !isInMainPath(LocB, Lp))
898 if (!NewLoc || !DT->dominates(TopB, NewLoc))
907 NodeChildrenMap::iterator CF = NCM.find(Node);
908 if (CF != NCM.end()) {
909 NodeVect &Cs = CF->second;
910 for (NodeVect::iterator
I = Cs.begin(),
E = Cs.end();
I !=
E; ++
I)
911 adjustForInvariance(*
I, NCM, Loc);
918 struct LocationAsBlock {
919 LocationAsBlock(
const NodeToValueMap &L) :
Map(L) {}
921 const NodeToValueMap &
Map;
927 for (NodeToValueMap::const_iterator
I = Loc.Map.begin(),
E = Loc.Map.end();
929 OS <<
I->first <<
" -> ";
931 OS <<
B->getName() <<
'(' <<
B <<
')';
937 inline bool is_constant(GepNode *
N) {
938 return isa<ConstantInt>(
N->Idx);
943 void HexagonCommonGEP::separateChainForNode(GepNode *Node,
Use *U,
944 NodeToValueMap &Loc) {
945 User *
R = U->getUser();
946 LLVM_DEBUG(
dbgs() <<
"Separating chain for node (" << Node <<
") user: " << *R
951 GepNode *
C =
nullptr, *NewNode =
nullptr;
952 while (is_constant(
N) && !(
N->Flags & GepNode::Root)) {
954 GepNode *NewN =
new (*Mem) GepNode(
N);
955 Nodes.push_back(NewN);
960 NewN->Flags &= ~GepNode::Used;
970 NodeToUsesMap::iterator UF =
Uses.find(Node);
972 UseSet &Us = UF->second;
975 if (U->getUser() == R)
982 Node->Flags &= ~GepNode::Used;
987 NewNode->Flags |= GepNode::Used;
988 LLVM_DEBUG(
dbgs() <<
"new node: " << NewNode <<
" " << *NewNode <<
'\n');
990 Uses[NewNode] = NewUs;
993 void HexagonCommonGEP::separateConstantChains(GepNode *Node,
994 NodeChildrenMap &NCM, NodeToValueMap &Loc) {
999 LLVM_DEBUG(
dbgs() <<
"Separating constant chains for node: " << Node <<
'\n');
1005 if (!(
N->Flags & GepNode::Used))
1007 NodeToUsesMap::iterator UF =
Uses.find(
N);
1009 UseSet &Us = UF->second;
1012 for (UseSet::iterator J = Us.begin(),
F = Us.end(); J !=
F; ++J) {
1014 User *
R = U->getUser();
1018 if (
LoadInst *Ld = dyn_cast<LoadInst>(R)) {
1020 if (&Ld->getOperandUse(PtrX) == U)
1022 }
else if (
StoreInst *St = dyn_cast<StoreInst>(R)) {
1024 if (&St->getOperandUse(PtrX) == U)
1033 FNs.insert(std::make_pair(
N, LSs));
1038 for (NodeToUsesMap::iterator
I = FNs.begin(),
E = FNs.end();
I !=
E; ++
I) {
1039 GepNode *
N =
I->first;
1040 UseSet &Us =
I->second;
1041 for (UseSet::iterator J = Us.begin(),
F = Us.end(); J !=
F; ++J)
1042 separateChainForNode(
N, *J, Loc);
1046 void HexagonCommonGEP::computeNodePlacement(NodeToValueMap &Loc) {
1049 NodeChildrenMap NCM;
1055 for (NodeVect::iterator
I = Roots.begin(),
E = Roots.end();
I !=
E; ++
I)
1056 recalculatePlacementRec(*
I, NCM, Loc);
1058 LLVM_DEBUG(
dbgs() <<
"Initial node placement:\n" << LocationAsBlock(Loc));
1061 for (NodeVect::iterator
I = Roots.begin(),
E = Roots.end();
I !=
E; ++
I)
1062 adjustForInvariance(*
I, NCM, Loc);
1064 LLVM_DEBUG(
dbgs() <<
"Node placement after adjustment for invariance:\n"
1065 << LocationAsBlock(Loc));
1068 for (NodeVect::iterator
I = Roots.begin(),
E = Roots.end();
I !=
E; ++
I)
1069 separateConstantChains(*
I, NCM, Loc);
1077 LLVM_DEBUG(
dbgs() <<
"Final node placement:\n" << LocationAsBlock(Loc));
1085 unsigned Num = NA.size();
1086 GepNode *
RN = NA[0];
1087 assert((
RN->Flags & GepNode::Root) &&
"Creating GEP for non-root");
1098 if (!NA[nax]->PTy->isPointerTy()) {
1105 while (++nax <= Num) {
1106 GepNode *
N = NA[nax-1];
1107 IdxList[IdxC++] =
N->Idx;
1112 if (NextTy != NA[nax]->PTy)
1123 }
while (nax <= Num);
1129 void HexagonCommonGEP::getAllUsersForNode(GepNode *Node, ValueVect &Values,
1130 NodeChildrenMap &NCM) {
1132 Work.push_back(Node);
1134 while (!Work.empty()) {
1135 NodeVect::iterator
First = Work.begin();
1138 if (
N->Flags & GepNode::Used) {
1139 NodeToUsesMap::iterator UF =
Uses.find(
N);
1140 assert(UF !=
Uses.end() &&
"No use information for used node");
1141 UseSet &Us = UF->second;
1142 for (UseSet::iterator
I = Us.begin(),
E = Us.end();
I !=
E; ++
I)
1143 Values.push_back((*I)->getUser());
1145 NodeChildrenMap::iterator CF = NCM.find(
N);
1146 if (CF != NCM.end()) {
1147 NodeVect &Cs = CF->second;
1153 void HexagonCommonGEP::materialize(NodeToValueMap &Loc) {
1154 LLVM_DEBUG(
dbgs() <<
"Nodes before materialization:\n" << Nodes <<
'\n');
1155 NodeChildrenMap NCM;
1161 while (!Roots.empty()) {
1162 NodeVect::iterator
First = Roots.begin();
1172 bool LastUsed =
false;
1173 unsigned LastCN = 0;
1182 LastUsed = (
Last->Flags & GepNode::Used);
1185 NodeChildrenMap::iterator CF = NCM.find(Last);
1186 LastCN = (CF != NCM.end()) ? CF->second.size() : 0;
1189 GepNode *Child = CF->second.front();
1190 BasicBlock *ChildB = cast_or_null<BasicBlock>(Loc[Child]);
1191 if (ChildB !=
nullptr && LastB != ChildB)
1197 if (LastUsed || LastCN > 0) {
1199 getAllUsersForNode(Root, Urs, NCM);
1201 if (FirstUse != LastB->
end())
1202 InsertAt = FirstUse;
1206 Value *NewInst = fabricateGEP(NA, InsertAt, LastB);
1211 NodeVect &Cs = NCM[
Last];
1212 for (NodeVect::iterator
I = Cs.begin(),
E = Cs.end();
I !=
E; ++
I) {
1214 CN->Flags &= ~GepNode::Internal;
1215 CN->Flags |= GepNode::Root;
1216 CN->BaseVal = NewInst;
1217 Roots.push_back(CN);
1224 NodeToUsesMap::iterator UF =
Uses.find(Last);
1225 assert(UF !=
Uses.end() &&
"No use information found");
1226 UseSet &Us = UF->second;
1227 for (UseSet::iterator
I = Us.begin(),
E = Us.end();
I !=
E; ++
I) {
1235 void HexagonCommonGEP::removeDeadCode() {
1237 BO.push_back(&Fn->front());
1239 for (
unsigned i = 0;
i < BO.size(); ++
i) {
1241 for (
auto DTN : children<DomTreeNode*>(DT->getNode(
B)))
1242 BO.push_back(DTN->getBlock());
1245 for (
unsigned i = BO.size();
i > 0; --
i) {
1249 using reverse_iterator = BasicBlock::InstListType::reverse_iterator;
1252 for (reverse_iterator
I = IL.rbegin(),
E = IL.rend();
I !=
E; ++
I)
1254 for (ValueVect::iterator
I =
Ins.begin(),
E =
Ins.end();
I !=
E; ++
I) {
1257 In->eraseFromParent();
1263 if (skipFunction(
F))
1269 if (isa<InvokeInst>(
I) || isa<LandingPadInst>(
I))
1273 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1274 PDT = &getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
1275 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1276 Ctx = &
F.getContext();
1289 computeNodePlacement(Loc);
1293 #ifdef EXPENSIVE_CHECKS
1304 return new HexagonCommonGEP();