50 #define DEBUG_TYPE "commgep"
72 using NodeSet = std::set<GepNode *>;
73 using NodeToValueMap = std::map<GepNode *, Value *>;
74 using NodeVect = std::vector<GepNode *>;
75 using NodeChildrenMap = std::map<GepNode *, NodeVect>;
77 using NodeToUsesMap = std::map<GepNode *, UseSet>;
82 NodeOrdering() =
default;
84 void insert(
const GepNode *
N) {
Map.insert(std::make_pair(
N, ++LastNum)); }
87 bool operator()(
const GepNode *N1,
const GepNode *N2)
const {
88 auto F1 =
Map.find(N1), F2 =
Map.find(N2);
90 return F1->second < F2->second;
94 std::map<const GepNode *, unsigned>
Map;
107 StringRef getPassName()
const override {
return "Hexagon Common GEP"; }
120 using ValueToNodeMap = std::map<Value *, GepNode *>;
121 using ValueVect = std::vector<Value *>;
122 using NodeToValuesMap = std::map<GepNode *, ValueVect>;
124 void getBlockTraversalOrder(
BasicBlock *Root, ValueVect &Order);
130 BasicBlock *recalculatePlacement(GepNode *Node, NodeChildrenMap &NCM,
131 NodeToValueMap &Loc);
132 BasicBlock *recalculatePlacementRec(GepNode *Node, NodeChildrenMap &NCM,
133 NodeToValueMap &Loc);
135 bool isInvariantIn(GepNode *Node,
Loop *L);
137 BasicBlock *adjustForInvariance(GepNode *Node, NodeChildrenMap &NCM,
138 NodeToValueMap &Loc);
139 void separateChainForNode(GepNode *Node,
Use *U, NodeToValueMap &Loc);
140 void separateConstantChains(GepNode *Node, NodeChildrenMap &NCM,
141 NodeToValueMap &Loc);
142 void computeNodePlacement(NodeToValueMap &Loc);
146 void getAllUsersForNode(GepNode *Node, ValueVect &Values,
147 NodeChildrenMap &NCM);
148 void materialize(NodeToValueMap &Loc);
150 void removeDeadCode();
211 BaseVal =
N->BaseVal;
222 if (GN.
Flags & GepNode::Root) {
226 if (GN.
Flags & GepNode::Internal) {
232 if (GN.
Flags & GepNode::Used) {
237 if (GN.
Flags & GepNode::InBounds) {
242 if (GN.
Flags & GepNode::Pointer) {
248 if (GN.
Flags & GepNode::Root)
251 OS <<
"Parent:" << GN.
Parent;
255 OS << CI->getValue().getSExtValue();
259 OS <<
"<anon> =" << *GN.
Idx;
267 OS <<
"<anon-struct>:" << *STy;
275 template <
typename NodeContainer>
277 using const_iterator =
typename NodeContainer::const_iterator;
279 for (const_iterator
I =
S.begin(),
E =
S.end();
I !=
E; ++
I)
280 OS << *
I <<
' ' << **
I <<
'\n';
293 for (
const auto &
I :
M) {
294 const UseSet &Us =
I.second;
295 OS <<
I.first <<
" -> #" << Us.size() <<
'{';
296 for (
const Use *U : Us) {
297 User *R = U->getUser();
299 OS <<
' ' << R->getName();
301 OS <<
" <?>(" << *R <<
')';
312 return NS.find(
N) != NS.end();
325 void HexagonCommonGEP::getBlockTraversalOrder(
BasicBlock *Root,
331 Order.push_back(Root);
332 for (
auto *DTN : children<DomTreeNode*>(DT->getNode(Root)))
333 getBlockTraversalOrder(DTN->getBlock(), Order);
347 ValueToNodeMap &NM) {
349 GepNode *
N =
new (*Mem) GepNode;
352 ValueToNodeMap::iterator
F = NM.find(PtrOp);
355 N->Flags |= GepNode::Root | InBounds;
360 N->Parent =
F->second;
363 N->Flags |= GepNode::Pointer;
373 if (isa<GetElementPtrInst>(*UI)) {
375 if (isHandledGepForm(UserG))
378 Us.insert(&UI.getUse());
389 GepNode *Nx =
new (*Mem) GepNode;
391 Nx->Flags |= GepNode::Internal | InBounds;
403 PN->Flags |= GepNode::Used;
404 Uses[PN].insert(Us.begin(), Us.end());
409 NM.insert(std::make_pair(GepI, PN));
412 void HexagonCommonGEP::collect() {
415 getBlockTraversalOrder(&Fn->front(), BO);
424 if (
auto *GepI = dyn_cast<GetElementPtrInst>(&J))
425 if (isHandledGepForm(GepI))
426 processGepInst(GepI, NM);
429 LLVM_DEBUG(
dbgs() <<
"Gep nodes after initial collection:\n" << Nodes);
434 for (GepNode *
N : Nodes) {
435 if (
N->Flags & GepNode::Root) {
439 GepNode *PN =
N->Parent;
440 NCM[PN].push_back(
N);
447 Work.push_back(Root);
450 while (!Work.empty()) {
451 NodeVect::iterator
First = Work.begin();
454 NodeChildrenMap::iterator CF = NCM.find(
N);
455 if (CF != NCM.end()) {
457 Nodes.
insert(CF->second.begin(), CF->second.end());
464 using NodeSymRel = std::set<NodeSet>;
465 using NodePair = std::pair<GepNode *, GepNode *>;
466 using NodePairSet = std::set<NodePair>;
481 uintptr_t P1 =
reinterpret_cast<uintptr_t
>(N1);
482 uintptr_t
P2 =
reinterpret_cast<uintptr_t
>(N2);
484 return std::make_pair(N1, N2);
485 return std::make_pair(N2, N1);
491 ID.AddPointer(
N->Idx);
492 ID.AddPointer(
N->PTy);
493 return ID.ComputeHash();
496 static bool node_eq(GepNode *N1, GepNode *N2, NodePairSet &Eq,
504 NodePairSet::iterator FEq = Eq.find(NP);
507 NodePairSet::iterator FNe = Ne.find(NP);
511 bool Root1 = N1->Flags & GepNode::Root;
512 uint32_t CmpFlags = GepNode::Root | GepNode::Pointer;
513 bool Different = (N1->Flags & CmpFlags) != (N2->Flags & CmpFlags);
519 if (Different || (Root1 && N1->BaseVal != N2->BaseVal)) {
526 if (Root1 ||
node_eq(N1->Parent, N2->Parent, Eq, Ne)) {
533 void HexagonCommonGEP::common() {
538 using NodeSetMap = std::map<unsigned, NodeSet>;
541 for (GepNode *
N : Nodes) {
543 MaybeEq[
H].insert(
N);
550 for (
auto &
I : MaybeEq) {
569 std::pair<NodeSymRel::iterator, bool>
Ins = EqRel.insert(
C);
571 assert(
Ins.second &&
"Cannot add a class");
577 dbgs() <<
"Gep node equality:\n";
578 for (NodePairSet::iterator
I = Eq.begin(),
E = Eq.end();
I !=
E; ++
I)
579 dbgs() <<
"{ " <<
I->first <<
", " <<
I->second <<
" }\n";
581 dbgs() <<
"Gep equivalence classes:\n";
584 for (NodeSet::const_iterator J =
S.begin(),
F =
S.end(); J !=
F; ++J) {
594 using ProjMap = std::map<const NodeSet *, GepNode *>;
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");
604 UseSet &MinUs =
Uses[Min];
605 for (GepNode *
N :
S) {
609 if (NF & GepNode::Used)
617 assert((Min->Flags & Flags) == Min->Flags);
625 for (GepNode *
N : Nodes) {
626 if (
N->Flags & GepNode::Root)
631 ProjMap::iterator
F = PM.find(PC);
635 GepNode *Rep =
F->second;
643 for (GepNode *
N : Nodes) {
647 ProjMap::iterator
F = PM.find(PC);
657 LLVM_DEBUG(
dbgs() <<
"Gep nodes after post-commoning cleanup:\n" << Nodes);
660 template <
typename T>
663 dbgs() <<
"NCD of {";
664 for (
typename T::iterator
I = Blocks.begin(),
E = Blocks.end();
I !=
E;
669 dbgs() <<
' ' <<
B->getName();
675 typename T::iterator
I = Blocks.begin(),
E = Blocks.end();
689 template <
typename T>
693 typename T::iterator
I = Blocks.begin(),
E = Blocks.end();
695 while (
I !=
E && !*
I)
715 template <
typename T>
719 using iterator =
typename T::iterator;
721 for (iterator
I = Values.begin(),
E = Values.end();
I !=
E; ++
I) {
730 if (!isa<Instruction>(V))
733 if (
In->getParent() !=
B)
736 if (std::distance(FirstUse, BEnd) < std::distance(It, BEnd))
743 return B->empty() || (&*
B->begin() ==
B->getTerminator());
746 BasicBlock *HexagonCommonGEP::recalculatePlacement(GepNode *Node,
747 NodeChildrenMap &NCM, NodeToValueMap &Loc) {
759 if (Node->Flags & GepNode::Used) {
762 NodeToUsesMap::iterator UF =
Uses.find(Node);
763 assert(UF !=
Uses.end() &&
"Used node with no use information");
764 UseSet &Us = UF->second;
766 User *
R = U->getUser();
767 if (!isa<Instruction>(R))
770 ? cast<PHINode>(R)->getIncomingBlock(*U)
771 : cast<Instruction>(R)->getParent();
776 NodeChildrenMap::iterator CF = NCM.find(Node);
777 if (CF != NCM.end()) {
778 NodeVect &Cs = CF->second;
779 for (GepNode *CN : Cs) {
780 NodeToValueMap::iterator LF = Loc.find(CN);
786 Bs.push_back(LF->second);
794 Instruction *IdxI = dyn_cast<Instruction>(Node->Idx);
795 if (IdxI && !DT->dominates(IdxI->
getParent(), DomB))
803 DomB =
N->getBlock();
811 BasicBlock *HexagonCommonGEP::recalculatePlacementRec(GepNode *Node,
812 NodeChildrenMap &NCM, NodeToValueMap &Loc) {
816 NodeChildrenMap::iterator CF = NCM.find(Node);
817 if (CF != NCM.end()) {
818 NodeVect &Cs = CF->second;
819 for (GepNode *
C : Cs)
820 recalculatePlacementRec(
C, NCM, Loc);
822 BasicBlock *LB = recalculatePlacement(Node, NCM, Loc);
827 bool HexagonCommonGEP::isInvariantIn(
Value *Val,
Loop *L) {
828 if (isa<Constant>(Val) || isa<Argument>(Val))
834 return DT->properlyDominates(DefB, HdrB);
837 bool HexagonCommonGEP::isInvariantIn(GepNode *Node,
Loop *L) {
838 if (Node->Flags & GepNode::Root)
839 if (!isInvariantIn(Node->BaseVal, L))
841 return isInvariantIn(Node->Idx, L);
848 if (PDT->dominates(
B, HB))
850 if (LB && DT->dominates(
B, LB))
866 BasicBlock *HexagonCommonGEP::adjustForInvariance(GepNode *Node,
867 NodeChildrenMap &NCM, NodeToValueMap &Loc) {
872 if (Node->Flags & GepNode::Root) {
873 if (
Instruction *PIn = dyn_cast<Instruction>(Node->BaseVal))
874 Bs.push_back(PIn->getParent());
876 Bs.push_back(Loc[Node->Parent]);
878 if (
Instruction *IIn = dyn_cast<Instruction>(Node->Idx))
879 Bs.push_back(IIn->getParent());
890 BasicBlock *LocB = cast_or_null<BasicBlock>(Loc[Node]);
892 Loop *Lp = LI->getLoopFor(LocB);
894 if (!isInvariantIn(Node, Lp) || !isInMainPath(LocB, Lp))
897 if (!NewLoc || !DT->dominates(TopB, NewLoc))
906 NodeChildrenMap::iterator CF = NCM.find(Node);
907 if (CF != NCM.end()) {
908 NodeVect &Cs = CF->second;
909 for (GepNode *
C : Cs)
910 adjustForInvariance(
C, NCM, Loc);
917 struct LocationAsBlock {
918 LocationAsBlock(
const NodeToValueMap &L) :
Map(L) {}
920 const NodeToValueMap &
Map;
926 for (
const auto &
I : Loc.Map) {
927 OS <<
I.first <<
" -> ";
929 OS <<
B->getName() <<
'(' <<
B <<
')';
931 OS <<
"<null-block>";
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');
1003 for (GepNode *
N : Ns) {
1004 if (!(
N->Flags & GepNode::Used))
1006 NodeToUsesMap::iterator UF =
Uses.find(
N);
1008 UseSet &Us = UF->second;
1012 User *
R = U->getUser();
1016 if (
LoadInst *Ld = dyn_cast<LoadInst>(R)) {
1018 if (&Ld->getOperandUse(PtrX) == U)
1020 }
else if (
StoreInst *St = dyn_cast<StoreInst>(R)) {
1022 if (&St->getOperandUse(PtrX) == U)
1031 FNs.insert(std::make_pair(
N, LSs));
1036 for (
auto &FN : FNs) {
1037 GepNode *
N = FN.first;
1038 UseSet &Us = FN.second;
1040 separateChainForNode(
N, U, Loc);
1044 void HexagonCommonGEP::computeNodePlacement(NodeToValueMap &Loc) {
1047 NodeChildrenMap NCM;
1053 for (GepNode *Root : Roots)
1054 recalculatePlacementRec(Root, NCM, Loc);
1056 LLVM_DEBUG(
dbgs() <<
"Initial node placement:\n" << LocationAsBlock(Loc));
1059 for (GepNode *Root : Roots)
1060 adjustForInvariance(Root, NCM, Loc);
1062 LLVM_DEBUG(
dbgs() <<
"Node placement after adjustment for invariance:\n"
1063 << LocationAsBlock(Loc));
1066 for (GepNode *Root : Roots)
1067 separateConstantChains(Root, NCM, Loc);
1075 LLVM_DEBUG(
dbgs() <<
"Final node placement:\n" << LocationAsBlock(Loc));
1083 unsigned Num = NA.size();
1084 GepNode *
RN = NA[0];
1085 assert((
RN->Flags & GepNode::Root) &&
"Creating GEP for non-root");
1097 if (!(NA[Idx]->Flags & GepNode::Pointer)) {
1104 while (++Idx <= Num) {
1105 GepNode *
N = NA[Idx-1];
1106 IdxList.push_back(
N->Idx);
1109 if (NA[Idx]->Flags & GepNode::Pointer)
1118 InpTy = NA[Idx]->PTy;
1120 }
while (Idx <= Num);
1125 void HexagonCommonGEP::getAllUsersForNode(GepNode *Node, ValueVect &Values,
1126 NodeChildrenMap &NCM) {
1128 Work.push_back(Node);
1130 while (!Work.empty()) {
1131 NodeVect::iterator
First = Work.begin();
1134 if (
N->Flags & GepNode::Used) {
1135 NodeToUsesMap::iterator UF =
Uses.find(
N);
1136 assert(UF !=
Uses.end() &&
"No use information for used node");
1137 UseSet &Us = UF->second;
1138 for (
const auto &U : Us)
1139 Values.push_back(U->getUser());
1141 NodeChildrenMap::iterator CF = NCM.find(
N);
1142 if (CF != NCM.end()) {
1143 NodeVect &Cs = CF->second;
1149 void HexagonCommonGEP::materialize(NodeToValueMap &Loc) {
1150 LLVM_DEBUG(
dbgs() <<
"Nodes before materialization:\n" << Nodes <<
'\n');
1151 NodeChildrenMap NCM;
1157 while (!Roots.empty()) {
1158 NodeVect::iterator
First = Roots.begin();
1168 bool LastUsed =
false;
1169 unsigned LastCN = 0;
1178 LastUsed = (
Last->Flags & GepNode::Used);
1181 NodeChildrenMap::iterator CF = NCM.find(Last);
1182 LastCN = (CF != NCM.end()) ? CF->second.size() : 0;
1185 GepNode *Child = CF->second.front();
1186 BasicBlock *ChildB = cast_or_null<BasicBlock>(Loc[Child]);
1187 if (ChildB !=
nullptr && LastB != ChildB)
1193 if (LastUsed || LastCN > 0) {
1195 getAllUsersForNode(Root, Urs, NCM);
1197 if (FirstUse != LastB->
end())
1198 InsertAt = FirstUse;
1202 Value *NewInst = fabricateGEP(NA, InsertAt, LastB);
1207 NodeVect &Cs = NCM[
Last];
1208 for (GepNode *CN : Cs) {
1209 CN->Flags &= ~GepNode::Internal;
1210 CN->Flags |= GepNode::Root;
1211 CN->BaseVal = NewInst;
1212 Roots.push_back(CN);
1219 NodeToUsesMap::iterator UF =
Uses.find(Last);
1220 assert(UF !=
Uses.end() &&
"No use information found");
1221 UseSet &Us = UF->second;
1228 void HexagonCommonGEP::removeDeadCode() {
1230 BO.push_back(&Fn->front());
1232 for (
unsigned i = 0;
i < BO.size(); ++
i) {
1234 for (
auto DTN : children<DomTreeNode*>(DT->getNode(
B)))
1235 BO.push_back(DTN->getBlock());
1246 In->eraseFromParent();
1252 if (skipFunction(
F))
1258 if (isa<InvokeInst>(
I) || isa<LandingPadInst>(
I))
1262 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1263 PDT = &getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
1264 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1265 Ctx = &
F.getContext();
1278 computeNodePlacement(Loc);
1282 #ifdef EXPENSIVE_CHECKS
1293 return new HexagonCommonGEP();