50 #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();
210 BaseVal =
N->BaseVal;
221 if (GN.
Flags & GepNode::Root) {
225 if (GN.
Flags & GepNode::Internal) {
231 if (GN.
Flags & GepNode::Used) {
236 if (GN.
Flags & GepNode::InBounds) {
241 if (GN.
Flags & GepNode::Pointer) {
247 if (GN.
Flags & GepNode::Root)
250 OS <<
"Parent:" << GN.
Parent;
254 OS << CI->getValue().getSExtValue();
258 OS <<
"<anon> =" << *GN.
Idx;
266 OS <<
"<anon-struct>:" << *STy;
274 template <
typename NodeContainer>
276 using const_iterator =
typename NodeContainer::const_iterator;
278 for (const_iterator
I =
S.begin(),
E =
S.end();
I !=
E; ++
I)
279 OS << *
I <<
' ' << **
I <<
'\n';
292 for (
const auto &
I :
M) {
293 const UseSet &Us =
I.second;
294 OS <<
I.first <<
" -> #" << Us.size() <<
'{';
295 for (
const Use *U : Us) {
296 User *R = U->getUser();
298 OS <<
' ' << R->getName();
300 OS <<
" <?>(" << *R <<
')';
311 return NS.find(
N) != NS.end();
324 void HexagonCommonGEP::getBlockTraversalOrder(
BasicBlock *Root,
330 Order.push_back(Root);
331 for (
auto *DTN : children<DomTreeNode*>(DT->getNode(Root)))
332 getBlockTraversalOrder(DTN->getBlock(), Order);
346 ValueToNodeMap &NM) {
348 GepNode *
N =
new (*Mem) GepNode;
351 ValueToNodeMap::iterator
F = NM.find(PtrOp);
354 N->Flags |= GepNode::Root | InBounds;
359 N->Parent =
F->second;
362 N->Flags |= GepNode::Pointer;
372 if (isa<GetElementPtrInst>(*UI)) {
374 if (isHandledGepForm(UserG))
377 Us.insert(&UI.getUse());
388 GepNode *Nx =
new (*Mem) GepNode;
390 Nx->Flags |= GepNode::Internal | InBounds;
402 PN->Flags |= GepNode::Used;
403 Uses[PN].insert(Us.begin(), Us.end());
408 NM.insert(std::make_pair(GepI, PN));
411 void HexagonCommonGEP::collect() {
414 getBlockTraversalOrder(&Fn->front(), BO);
423 if (
auto *GepI = dyn_cast<GetElementPtrInst>(&J))
424 if (isHandledGepForm(GepI))
425 processGepInst(GepI, NM);
428 LLVM_DEBUG(
dbgs() <<
"Gep nodes after initial collection:\n" << Nodes);
433 for (GepNode *
N : Nodes) {
434 if (
N->Flags & GepNode::Root) {
438 GepNode *PN =
N->Parent;
439 NCM[PN].push_back(
N);
446 Work.push_back(Root);
449 while (!Work.empty()) {
450 NodeVect::iterator
First = Work.begin();
453 NodeChildrenMap::iterator CF = NCM.find(
N);
454 if (CF != NCM.end()) {
456 Nodes.
insert(CF->second.begin(), CF->second.end());
463 using NodeSymRel = std::set<NodeSet>;
464 using NodePair = std::pair<GepNode *, GepNode *>;
465 using NodePairSet = std::set<NodePair>;
480 uintptr_t P1 =
reinterpret_cast<uintptr_t
>(N1);
481 uintptr_t
P2 =
reinterpret_cast<uintptr_t
>(N2);
483 return std::make_pair(N1, N2);
484 return std::make_pair(N2, N1);
490 ID.AddPointer(
N->Idx);
491 ID.AddPointer(
N->PTy);
492 return ID.ComputeHash();
495 static bool node_eq(GepNode *N1, GepNode *N2, NodePairSet &Eq,
503 NodePairSet::iterator FEq = Eq.find(NP);
506 NodePairSet::iterator FNe = Ne.find(NP);
510 bool Root1 = N1->Flags & GepNode::Root;
511 uint32_t CmpFlags = GepNode::Root | GepNode::Pointer;
512 bool Different = (N1->Flags & CmpFlags) != (N2->Flags & CmpFlags);
518 if (Different || (Root1 && N1->BaseVal != N2->BaseVal)) {
525 if (Root1 ||
node_eq(N1->Parent, N2->Parent, Eq, Ne)) {
532 void HexagonCommonGEP::common() {
537 using NodeSetMap = std::map<unsigned, NodeSet>;
540 for (GepNode *
N : Nodes) {
542 MaybeEq[
H].insert(
N);
549 for (
auto &
I : MaybeEq) {
568 std::pair<NodeSymRel::iterator, bool>
Ins = EqRel.insert(
C);
570 assert(
Ins.second &&
"Cannot add a class");
576 dbgs() <<
"Gep node equality:\n";
577 for (NodePairSet::iterator
I = Eq.begin(),
E = Eq.end();
I !=
E; ++
I)
578 dbgs() <<
"{ " <<
I->first <<
", " <<
I->second <<
" }\n";
580 dbgs() <<
"Gep equivalence classes:\n";
583 for (NodeSet::const_iterator J =
S.begin(),
F =
S.end(); J !=
F; ++J) {
593 using ProjMap = std::map<const NodeSet *, GepNode *>;
596 GepNode *Min = *std::min_element(
S.begin(),
S.end(),
NodeOrder);
597 std::pair<ProjMap::iterator,bool>
Ins = PM.insert(std::make_pair(&
S, Min));
599 assert(
Ins.second &&
"Cannot add minimal element");
603 UseSet &MinUs =
Uses[Min];
604 for (GepNode *
N :
S) {
608 if (NF & GepNode::Used)
616 assert((Min->Flags & Flags) == Min->Flags);
624 for (GepNode *
N : Nodes) {
625 if (
N->Flags & GepNode::Root)
630 ProjMap::iterator
F = PM.find(PC);
634 GepNode *Rep =
F->second;
642 for (GepNode *
N : Nodes) {
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;
765 User *
R = U->getUser();
766 if (!isa<Instruction>(R))
769 ? cast<PHINode>(R)->getIncomingBlock(*U)
770 : cast<Instruction>(R)->getParent();
775 NodeChildrenMap::iterator CF = NCM.find(Node);
776 if (CF != NCM.end()) {
777 NodeVect &Cs = CF->second;
778 for (GepNode *CN : Cs) {
779 NodeToValueMap::iterator LF = Loc.find(CN);
785 Bs.push_back(LF->second);
793 Instruction *IdxI = dyn_cast<Instruction>(Node->Idx);
794 if (IdxI && !DT->dominates(IdxI->
getParent(), DomB))
802 DomB =
N->getBlock();
810 BasicBlock *HexagonCommonGEP::recalculatePlacementRec(GepNode *Node,
811 NodeChildrenMap &NCM, NodeToValueMap &Loc) {
815 NodeChildrenMap::iterator CF = NCM.find(Node);
816 if (CF != NCM.end()) {
817 NodeVect &Cs = CF->second;
818 for (GepNode *
C : Cs)
819 recalculatePlacementRec(
C, NCM, Loc);
821 BasicBlock *LB = recalculatePlacement(Node, NCM, Loc);
826 bool HexagonCommonGEP::isInvariantIn(
Value *Val,
Loop *L) {
827 if (isa<Constant>(Val) || isa<Argument>(Val))
833 return DT->properlyDominates(DefB, HdrB);
836 bool HexagonCommonGEP::isInvariantIn(GepNode *Node,
Loop *L) {
837 if (Node->Flags & GepNode::Root)
838 if (!isInvariantIn(Node->BaseVal, L))
840 return isInvariantIn(Node->Idx, L);
847 if (PDT->dominates(
B, HB))
849 if (LB && DT->dominates(
B, LB))
865 BasicBlock *HexagonCommonGEP::adjustForInvariance(GepNode *Node,
866 NodeChildrenMap &NCM, NodeToValueMap &Loc) {
871 if (Node->Flags & GepNode::Root) {
872 if (
Instruction *PIn = dyn_cast<Instruction>(Node->BaseVal))
873 Bs.push_back(PIn->getParent());
875 Bs.push_back(Loc[Node->Parent]);
877 if (
Instruction *IIn = dyn_cast<Instruction>(Node->Idx))
878 Bs.push_back(IIn->getParent());
889 BasicBlock *LocB = cast_or_null<BasicBlock>(Loc[Node]);
891 Loop *Lp = LI->getLoopFor(LocB);
893 if (!isInvariantIn(Node, Lp) || !isInMainPath(LocB, Lp))
896 if (!NewLoc || !DT->dominates(TopB, NewLoc))
905 NodeChildrenMap::iterator CF = NCM.find(Node);
906 if (CF != NCM.end()) {
907 NodeVect &Cs = CF->second;
908 for (GepNode *
C : Cs)
909 adjustForInvariance(
C, NCM, Loc);
916 struct LocationAsBlock {
917 LocationAsBlock(
const NodeToValueMap &L) :
Map(L) {}
919 const NodeToValueMap &
Map;
925 for (
const auto &
I : Loc.Map) {
926 OS <<
I.first <<
" -> ";
928 OS <<
B->getName() <<
'(' <<
B <<
')';
930 OS <<
"<null-block>";
936 inline bool is_constant(GepNode *
N) {
937 return isa<ConstantInt>(
N->Idx);
942 void HexagonCommonGEP::separateChainForNode(GepNode *Node,
Use *U,
943 NodeToValueMap &Loc) {
944 User *
R = U->getUser();
945 LLVM_DEBUG(
dbgs() <<
"Separating chain for node (" << Node <<
") user: " << *R
950 GepNode *
C =
nullptr, *NewNode =
nullptr;
951 while (is_constant(
N) && !(
N->Flags & GepNode::Root)) {
953 GepNode *NewN =
new (*Mem) GepNode(
N);
954 Nodes.push_back(NewN);
959 NewN->Flags &= ~GepNode::Used;
969 NodeToUsesMap::iterator UF =
Uses.find(Node);
971 UseSet &Us = UF->second;
974 if (U->getUser() == R)
981 Node->Flags &= ~GepNode::Used;
986 NewNode->Flags |= GepNode::Used;
987 LLVM_DEBUG(
dbgs() <<
"new node: " << NewNode <<
" " << *NewNode <<
'\n');
989 Uses[NewNode] = NewUs;
992 void HexagonCommonGEP::separateConstantChains(GepNode *Node,
993 NodeChildrenMap &NCM, NodeToValueMap &Loc) {
998 LLVM_DEBUG(
dbgs() <<
"Separating constant chains for node: " << Node <<
'\n');
1002 for (GepNode *
N : Ns) {
1003 if (!(
N->Flags & GepNode::Used))
1005 NodeToUsesMap::iterator UF =
Uses.find(
N);
1007 UseSet &Us = UF->second;
1011 User *
R = U->getUser();
1015 if (
LoadInst *Ld = dyn_cast<LoadInst>(R)) {
1017 if (&Ld->getOperandUse(PtrX) == U)
1019 }
else if (
StoreInst *St = dyn_cast<StoreInst>(R)) {
1021 if (&St->getOperandUse(PtrX) == U)
1030 FNs.insert(std::make_pair(
N, LSs));
1035 for (
auto &FN : FNs) {
1036 GepNode *
N = FN.first;
1037 UseSet &Us = FN.second;
1039 separateChainForNode(
N, U, Loc);
1043 void HexagonCommonGEP::computeNodePlacement(NodeToValueMap &Loc) {
1046 NodeChildrenMap NCM;
1052 for (GepNode *Root : Roots)
1053 recalculatePlacementRec(Root, NCM, Loc);
1055 LLVM_DEBUG(
dbgs() <<
"Initial node placement:\n" << LocationAsBlock(Loc));
1058 for (GepNode *Root : Roots)
1059 adjustForInvariance(Root, NCM, Loc);
1061 LLVM_DEBUG(
dbgs() <<
"Node placement after adjustment for invariance:\n"
1062 << LocationAsBlock(Loc));
1065 for (GepNode *Root : Roots)
1066 separateConstantChains(Root, NCM, Loc);
1074 LLVM_DEBUG(
dbgs() <<
"Final node placement:\n" << LocationAsBlock(Loc));
1082 unsigned Num = NA.size();
1083 GepNode *
RN = NA[0];
1084 assert((
RN->Flags & GepNode::Root) &&
"Creating GEP for non-root");
1096 if (!(NA[Idx]->Flags & GepNode::Pointer)) {
1103 while (++Idx <= Num) {
1104 GepNode *
N = NA[Idx-1];
1105 IdxList.push_back(
N->Idx);
1108 if (NA[Idx]->Flags & GepNode::Pointer)
1117 InpTy = NA[Idx]->PTy;
1119 }
while (Idx <= Num);
1124 void HexagonCommonGEP::getAllUsersForNode(GepNode *Node, ValueVect &Values,
1125 NodeChildrenMap &NCM) {
1127 Work.push_back(Node);
1129 while (!Work.empty()) {
1130 NodeVect::iterator
First = Work.begin();
1133 if (
N->Flags & GepNode::Used) {
1134 NodeToUsesMap::iterator UF =
Uses.find(
N);
1135 assert(UF !=
Uses.end() &&
"No use information for used node");
1136 UseSet &Us = UF->second;
1137 for (
const auto &U : Us)
1138 Values.push_back(U->getUser());
1140 NodeChildrenMap::iterator CF = NCM.find(
N);
1141 if (CF != NCM.end()) {
1142 NodeVect &Cs = CF->second;
1148 void HexagonCommonGEP::materialize(NodeToValueMap &Loc) {
1149 LLVM_DEBUG(
dbgs() <<
"Nodes before materialization:\n" << Nodes <<
'\n');
1150 NodeChildrenMap NCM;
1156 while (!Roots.empty()) {
1157 NodeVect::iterator
First = Roots.begin();
1167 bool LastUsed =
false;
1168 unsigned LastCN = 0;
1177 LastUsed = (
Last->Flags & GepNode::Used);
1180 NodeChildrenMap::iterator CF = NCM.find(Last);
1181 LastCN = (CF != NCM.end()) ? CF->second.size() : 0;
1184 GepNode *Child = CF->second.front();
1185 BasicBlock *ChildB = cast_or_null<BasicBlock>(Loc[Child]);
1186 if (ChildB !=
nullptr && LastB != ChildB)
1192 if (LastUsed || LastCN > 0) {
1194 getAllUsersForNode(Root, Urs, NCM);
1196 if (FirstUse != LastB->
end())
1197 InsertAt = FirstUse;
1201 Value *NewInst = fabricateGEP(NA, InsertAt, LastB);
1206 NodeVect &Cs = NCM[
Last];
1207 for (GepNode *CN : Cs) {
1208 CN->Flags &= ~GepNode::Internal;
1209 CN->Flags |= GepNode::Root;
1210 CN->BaseVal = NewInst;
1211 Roots.push_back(CN);
1218 NodeToUsesMap::iterator UF =
Uses.find(Last);
1219 assert(UF !=
Uses.end() &&
"No use information found");
1220 UseSet &Us = UF->second;
1227 void HexagonCommonGEP::removeDeadCode() {
1229 BO.push_back(&Fn->front());
1231 for (
unsigned i = 0;
i < BO.size(); ++
i) {
1233 for (
auto DTN : children<DomTreeNode*>(DT->getNode(
B)))
1234 BO.push_back(DTN->getBlock());
1245 In->eraseFromParent();
1251 if (skipFunction(
F))
1257 if (isa<InvokeInst>(
I) || isa<LandingPadInst>(
I))
1261 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1262 PDT = &getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
1263 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1264 Ctx = &
F.getContext();
1277 computeNodePlacement(Loc);
1281 #ifdef EXPENSIVE_CHECKS
1292 return new HexagonCommonGEP();