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