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