blob: a07ba77e6f3e1b33d724bbeafb72df9b56a5d6f1 [file] [log] [blame]
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +00001//===--- HexagonCommonGEP.cpp ---------------------------------------------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9
10#define DEBUG_TYPE "commgep"
11
Eugene Zelenko82085922016-12-13 22:13:50 +000012#include "llvm/ADT/ArrayRef.h"
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +000013#include "llvm/ADT/FoldingSet.h"
14#include "llvm/ADT/STLExtras.h"
Eugene Zelenko82085922016-12-13 22:13:50 +000015#include "llvm/ADT/StringRef.h"
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +000016#include "llvm/Analysis/LoopInfo.h"
17#include "llvm/Analysis/PostDominators.h"
Eugene Zelenko82085922016-12-13 22:13:50 +000018#include "llvm/IR/BasicBlock.h"
19#include "llvm/IR/Constant.h"
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +000020#include "llvm/IR/Constants.h"
Eugene Zelenko82085922016-12-13 22:13:50 +000021#include "llvm/IR/DerivedTypes.h"
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +000022#include "llvm/IR/Dominators.h"
23#include "llvm/IR/Function.h"
Eugene Zelenko82085922016-12-13 22:13:50 +000024#include "llvm/IR/Instruction.h"
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +000025#include "llvm/IR/Instructions.h"
Eugene Zelenko82085922016-12-13 22:13:50 +000026#include "llvm/IR/Type.h"
27#include "llvm/IR/Use.h"
28#include "llvm/IR/User.h"
29#include "llvm/IR/Value.h"
Serge Pavlovfe8cb932016-12-20 08:48:51 +000030#include "llvm/IR/Verifier.h"
Eugene Zelenko82085922016-12-13 22:13:50 +000031#include "llvm/Pass.h"
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +000032#include "llvm/Support/Allocator.h"
Eugene Zelenko82085922016-12-13 22:13:50 +000033#include "llvm/Support/Casting.h"
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +000034#include "llvm/Support/CommandLine.h"
Eugene Zelenko82085922016-12-13 22:13:50 +000035#include "llvm/Support/Compiler.h"
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +000036#include "llvm/Support/Debug.h"
37#include "llvm/Support/raw_ostream.h"
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +000038#include "llvm/Transforms/Utils/Local.h"
Eugene Zelenko82085922016-12-13 22:13:50 +000039#include <algorithm>
40#include <cassert>
41#include <cstddef>
42#include <cstdint>
43#include <iterator>
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +000044#include <map>
45#include <set>
Eugene Zelenko82085922016-12-13 22:13:50 +000046#include <utility>
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +000047#include <vector>
48
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +000049using namespace llvm;
50
51static cl::opt<bool> OptSpeculate("commgep-speculate", cl::init(true),
52 cl::Hidden, cl::ZeroOrMore);
53
54static cl::opt<bool> OptEnableInv("commgep-inv", cl::init(true), cl::Hidden,
55 cl::ZeroOrMore);
56
57static cl::opt<bool> OptEnableConst("commgep-const", cl::init(true),
58 cl::Hidden, cl::ZeroOrMore);
59
60namespace llvm {
Eugene Zelenko82085922016-12-13 22:13:50 +000061
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +000062 void initializeHexagonCommonGEPPass(PassRegistry&);
Eugene Zelenko82085922016-12-13 22:13:50 +000063
64} // end namespace llvm
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +000065
66namespace {
Eugene Zelenko82085922016-12-13 22:13:50 +000067
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +000068 struct GepNode;
69 typedef std::set<GepNode*> NodeSet;
70 typedef std::map<GepNode*,Value*> NodeToValueMap;
71 typedef std::vector<GepNode*> NodeVect;
72 typedef std::map<GepNode*,NodeVect> NodeChildrenMap;
73 typedef std::set<Use*> UseSet;
74 typedef std::map<GepNode*,UseSet> NodeToUsesMap;
75
76 // Numbering map for gep nodes. Used to keep track of ordering for
77 // gep nodes.
Benjamin Kramer9a5d7882015-07-18 17:43:23 +000078 struct NodeOrdering {
Eugene Zelenko82085922016-12-13 22:13:50 +000079 NodeOrdering() = default;
Benjamin Kramer9a5d7882015-07-18 17:43:23 +000080
81 void insert(const GepNode *N) { Map.insert(std::make_pair(N, ++LastNum)); }
82 void clear() { Map.clear(); }
83
84 bool operator()(const GepNode *N1, const GepNode *N2) const {
85 auto F1 = Map.find(N1), F2 = Map.find(N2);
86 assert(F1 != Map.end() && F2 != Map.end());
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +000087 return F1->second < F2->second;
88 }
Benjamin Kramer9a5d7882015-07-18 17:43:23 +000089
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +000090 private:
Benjamin Kramer9a5d7882015-07-18 17:43:23 +000091 std::map<const GepNode *, unsigned> Map;
Eugene Zelenko82085922016-12-13 22:13:50 +000092 unsigned LastNum = 0;
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +000093 };
94
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +000095 class HexagonCommonGEP : public FunctionPass {
96 public:
97 static char ID;
Eugene Zelenko82085922016-12-13 22:13:50 +000098
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +000099 HexagonCommonGEP() : FunctionPass(ID) {
100 initializeHexagonCommonGEPPass(*PassRegistry::getPassRegistry());
101 }
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000102
Eugene Zelenko82085922016-12-13 22:13:50 +0000103 bool runOnFunction(Function &F) override;
104 StringRef getPassName() const override { return "Hexagon Common GEP"; }
105
106 void getAnalysisUsage(AnalysisUsage &AU) const override {
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000107 AU.addRequired<DominatorTreeWrapperPass>();
108 AU.addPreserved<DominatorTreeWrapperPass>();
Hongbin Zheng3f978402016-02-25 17:54:07 +0000109 AU.addRequired<PostDominatorTreeWrapperPass>();
110 AU.addPreserved<PostDominatorTreeWrapperPass>();
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000111 AU.addRequired<LoopInfoWrapperPass>();
112 AU.addPreserved<LoopInfoWrapperPass>();
113 FunctionPass::getAnalysisUsage(AU);
114 }
115
116 private:
117 typedef std::map<Value*,GepNode*> ValueToNodeMap;
118 typedef std::vector<Value*> ValueVect;
119 typedef std::map<GepNode*,ValueVect> NodeToValuesMap;
120
121 void getBlockTraversalOrder(BasicBlock *Root, ValueVect &Order);
122 bool isHandledGepForm(GetElementPtrInst *GepI);
123 void processGepInst(GetElementPtrInst *GepI, ValueToNodeMap &NM);
124 void collect();
125 void common();
126
127 BasicBlock *recalculatePlacement(GepNode *Node, NodeChildrenMap &NCM,
128 NodeToValueMap &Loc);
129 BasicBlock *recalculatePlacementRec(GepNode *Node, NodeChildrenMap &NCM,
130 NodeToValueMap &Loc);
131 bool isInvariantIn(Value *Val, Loop *L);
132 bool isInvariantIn(GepNode *Node, Loop *L);
133 bool isInMainPath(BasicBlock *B, Loop *L);
134 BasicBlock *adjustForInvariance(GepNode *Node, NodeChildrenMap &NCM,
135 NodeToValueMap &Loc);
136 void separateChainForNode(GepNode *Node, Use *U, NodeToValueMap &Loc);
137 void separateConstantChains(GepNode *Node, NodeChildrenMap &NCM,
138 NodeToValueMap &Loc);
139 void computeNodePlacement(NodeToValueMap &Loc);
140
141 Value *fabricateGEP(NodeVect &NA, BasicBlock::iterator At,
142 BasicBlock *LocB);
143 void getAllUsersForNode(GepNode *Node, ValueVect &Values,
144 NodeChildrenMap &NCM);
145 void materialize(NodeToValueMap &Loc);
146
147 void removeDeadCode();
148
149 NodeVect Nodes;
150 NodeToUsesMap Uses;
151 NodeOrdering NodeOrder; // Node ordering, for deterministic behavior.
152 SpecificBumpPtrAllocator<GepNode> *Mem;
153 LLVMContext *Ctx;
154 LoopInfo *LI;
155 DominatorTree *DT;
156 PostDominatorTree *PDT;
157 Function *Fn;
158 };
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000159
Eugene Zelenko82085922016-12-13 22:13:50 +0000160} // end anonymous namespace
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000161
162char HexagonCommonGEP::ID = 0;
163INITIALIZE_PASS_BEGIN(HexagonCommonGEP, "hcommgep", "Hexagon Common GEP",
164 false, false)
165INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
Hongbin Zheng3f978402016-02-25 17:54:07 +0000166INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000167INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
168INITIALIZE_PASS_END(HexagonCommonGEP, "hcommgep", "Hexagon Common GEP",
169 false, false)
170
171namespace {
Eugene Zelenko82085922016-12-13 22:13:50 +0000172
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000173 struct GepNode {
174 enum {
175 None = 0,
176 Root = 0x01,
177 Internal = 0x02,
178 Used = 0x04
179 };
180
181 uint32_t Flags;
182 union {
183 GepNode *Parent;
184 Value *BaseVal;
185 };
186 Value *Idx;
187 Type *PTy; // Type of the pointer operand.
188
Eugene Zelenko82085922016-12-13 22:13:50 +0000189 GepNode() : Flags(0), Parent(nullptr), Idx(nullptr), PTy(nullptr) {}
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000190 GepNode(const GepNode *N) : Flags(N->Flags), Idx(N->Idx), PTy(N->PTy) {
191 if (Flags & Root)
192 BaseVal = N->BaseVal;
193 else
194 Parent = N->Parent;
195 }
Eugene Zelenko82085922016-12-13 22:13:50 +0000196
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000197 friend raw_ostream &operator<< (raw_ostream &OS, const GepNode &GN);
198 };
199
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000200 Type *next_type(Type *Ty, Value *Idx) {
Peter Collingbourne45681582016-12-02 03:05:41 +0000201 if (auto *PTy = dyn_cast<PointerType>(Ty))
202 return PTy->getElementType();
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000203 // Advance the type.
204 if (!Ty->isStructTy()) {
205 Type *NexTy = cast<SequentialType>(Ty)->getElementType();
206 return NexTy;
207 }
208 // Otherwise it is a struct type.
209 ConstantInt *CI = dyn_cast<ConstantInt>(Idx);
210 assert(CI && "Struct type with non-constant index");
211 int64_t i = CI->getValue().getSExtValue();
212 Type *NextTy = cast<StructType>(Ty)->getElementType(i);
213 return NextTy;
214 }
215
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000216 raw_ostream &operator<< (raw_ostream &OS, const GepNode &GN) {
217 OS << "{ {";
218 bool Comma = false;
219 if (GN.Flags & GepNode::Root) {
220 OS << "root";
221 Comma = true;
222 }
223 if (GN.Flags & GepNode::Internal) {
224 if (Comma)
225 OS << ',';
226 OS << "internal";
227 Comma = true;
228 }
229 if (GN.Flags & GepNode::Used) {
230 if (Comma)
231 OS << ',';
232 OS << "used";
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000233 }
234 OS << "} ";
235 if (GN.Flags & GepNode::Root)
236 OS << "BaseVal:" << GN.BaseVal->getName() << '(' << GN.BaseVal << ')';
237 else
238 OS << "Parent:" << GN.Parent;
239
240 OS << " Idx:";
241 if (ConstantInt *CI = dyn_cast<ConstantInt>(GN.Idx))
242 OS << CI->getValue().getSExtValue();
243 else if (GN.Idx->hasName())
244 OS << GN.Idx->getName();
245 else
246 OS << "<anon> =" << *GN.Idx;
247
248 OS << " PTy:";
249 if (GN.PTy->isStructTy()) {
250 StructType *STy = cast<StructType>(GN.PTy);
251 if (!STy->isLiteral())
252 OS << GN.PTy->getStructName();
253 else
254 OS << "<anon-struct>:" << *STy;
255 }
256 else
257 OS << *GN.PTy;
258 OS << " }";
259 return OS;
260 }
261
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000262 template <typename NodeContainer>
263 void dump_node_container(raw_ostream &OS, const NodeContainer &S) {
264 typedef typename NodeContainer::const_iterator const_iterator;
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;
271 raw_ostream &operator<< (raw_ostream &OS, const NodeVect &S) {
272 dump_node_container(OS, S);
273 return OS;
274 }
275
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000276 raw_ostream &operator<< (raw_ostream &OS,
277 const NodeToUsesMap &M) LLVM_ATTRIBUTE_UNUSED;
278 raw_ostream &operator<< (raw_ostream &OS, const NodeToUsesMap &M){
279 typedef NodeToUsesMap::const_iterator const_iterator;
280 for (const_iterator I = M.begin(), E = M.end(); I != E; ++I) {
281 const UseSet &Us = I->second;
282 OS << I->first << " -> #" << Us.size() << '{';
283 for (UseSet::const_iterator J = Us.begin(), F = Us.end(); J != F; ++J) {
284 User *R = (*J)->getUser();
285 if (R->hasName())
286 OS << ' ' << R->getName();
287 else
288 OS << " <?>(" << *R << ')';
289 }
290 OS << " }\n";
291 }
292 return OS;
293 }
294
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000295 struct in_set {
296 in_set(const NodeSet &S) : NS(S) {}
297 bool operator() (GepNode *N) const {
298 return NS.find(N) != NS.end();
299 }
Eugene Zelenko82085922016-12-13 22:13:50 +0000300
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000301 private:
302 const NodeSet &NS;
303 };
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000304
Eugene Zelenko82085922016-12-13 22:13:50 +0000305} // end anonymous namespace
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000306
307inline void *operator new(size_t, SpecificBumpPtrAllocator<GepNode> &A) {
308 return A.Allocate();
309}
310
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000311void HexagonCommonGEP::getBlockTraversalOrder(BasicBlock *Root,
312 ValueVect &Order) {
313 // Compute block ordering for a typical DT-based traversal of the flow
314 // graph: "before visiting a block, all of its dominators must have been
315 // visited".
316
317 Order.push_back(Root);
Daniel Berlin73ad5cb2017-02-09 20:37:46 +0000318 for (auto *DTN : children<DomTreeNode*>(DT->getNode(Root)))
Daniel Berlin58a6e572017-02-09 20:37:24 +0000319 getBlockTraversalOrder(DTN->getBlock(), Order);
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000320}
321
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000322bool HexagonCommonGEP::isHandledGepForm(GetElementPtrInst *GepI) {
323 // No vector GEPs.
324 if (!GepI->getType()->isPointerTy())
325 return false;
326 // No GEPs without any indices. (Is this possible?)
327 if (GepI->idx_begin() == GepI->idx_end())
328 return false;
329 return true;
330}
331
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000332void HexagonCommonGEP::processGepInst(GetElementPtrInst *GepI,
333 ValueToNodeMap &NM) {
334 DEBUG(dbgs() << "Visiting GEP: " << *GepI << '\n');
335 GepNode *N = new (*Mem) GepNode;
336 Value *PtrOp = GepI->getPointerOperand();
337 ValueToNodeMap::iterator F = NM.find(PtrOp);
338 if (F == NM.end()) {
339 N->BaseVal = PtrOp;
340 N->Flags |= GepNode::Root;
341 } else {
342 // If PtrOp was a GEP instruction, it must have already been processed.
343 // The ValueToNodeMap entry for it is the last gep node in the generated
344 // chain. Link to it here.
345 N->Parent = F->second;
346 }
347 N->PTy = PtrOp->getType();
348 N->Idx = *GepI->idx_begin();
349
350 // Collect the list of users of this GEP instruction. Will add it to the
351 // last node created for it.
352 UseSet Us;
353 for (Value::user_iterator UI = GepI->user_begin(), UE = GepI->user_end();
354 UI != UE; ++UI) {
355 // Check if this gep is used by anything other than other geps that
356 // we will process.
357 if (isa<GetElementPtrInst>(*UI)) {
358 GetElementPtrInst *UserG = cast<GetElementPtrInst>(*UI);
359 if (isHandledGepForm(UserG))
360 continue;
361 }
362 Us.insert(&UI.getUse());
363 }
364 Nodes.push_back(N);
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000365 NodeOrder.insert(N);
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000366
367 // Skip the first index operand, since we only handle 0. This dereferences
368 // the pointer operand.
369 GepNode *PN = N;
370 Type *PtrTy = cast<PointerType>(PtrOp->getType())->getElementType();
371 for (User::op_iterator OI = GepI->idx_begin()+1, OE = GepI->idx_end();
372 OI != OE; ++OI) {
373 Value *Op = *OI;
374 GepNode *Nx = new (*Mem) GepNode;
375 Nx->Parent = PN; // Link Nx to the previous node.
376 Nx->Flags |= GepNode::Internal;
377 Nx->PTy = PtrTy;
378 Nx->Idx = Op;
379 Nodes.push_back(Nx);
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000380 NodeOrder.insert(Nx);
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000381 PN = Nx;
382
383 PtrTy = next_type(PtrTy, Op);
384 }
385
386 // After last node has been created, update the use information.
387 if (!Us.empty()) {
388 PN->Flags |= GepNode::Used;
389 Uses[PN].insert(Us.begin(), Us.end());
390 }
391
392 // Link the last node with the originating GEP instruction. This is to
393 // help with linking chained GEP instructions.
394 NM.insert(std::make_pair(GepI, PN));
395}
396
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000397void HexagonCommonGEP::collect() {
398 // Establish depth-first traversal order of the dominator tree.
399 ValueVect BO;
Duncan P. N. Exon Smitha72c6e22015-10-20 00:46:39 +0000400 getBlockTraversalOrder(&Fn->front(), BO);
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000401
402 // The creation of gep nodes requires DT-traversal. When processing a GEP
403 // instruction that uses another GEP instruction as the base pointer, the
404 // gep node for the base pointer should already exist.
405 ValueToNodeMap NM;
406 for (ValueVect::iterator I = BO.begin(), E = BO.end(); I != E; ++I) {
407 BasicBlock *B = cast<BasicBlock>(*I);
408 for (BasicBlock::iterator J = B->begin(), F = B->end(); J != F; ++J) {
409 if (!isa<GetElementPtrInst>(J))
410 continue;
411 GetElementPtrInst *GepI = cast<GetElementPtrInst>(J);
412 if (isHandledGepForm(GepI))
413 processGepInst(GepI, NM);
414 }
415 }
416
417 DEBUG(dbgs() << "Gep nodes after initial collection:\n" << Nodes);
418}
419
Eugene Zelenko82085922016-12-13 22:13:50 +0000420static void invert_find_roots(const NodeVect &Nodes, NodeChildrenMap &NCM,
421 NodeVect &Roots) {
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000422 typedef NodeVect::const_iterator const_iterator;
423 for (const_iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) {
424 GepNode *N = *I;
425 if (N->Flags & GepNode::Root) {
426 Roots.push_back(N);
427 continue;
428 }
429 GepNode *PN = N->Parent;
430 NCM[PN].push_back(N);
431 }
Eugene Zelenko82085922016-12-13 22:13:50 +0000432}
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000433
Eugene Zelenko82085922016-12-13 22:13:50 +0000434static void nodes_for_root(GepNode *Root, NodeChildrenMap &NCM,
435 NodeSet &Nodes) {
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000436 NodeVect Work;
437 Work.push_back(Root);
438 Nodes.insert(Root);
439
440 while (!Work.empty()) {
441 NodeVect::iterator First = Work.begin();
442 GepNode *N = *First;
443 Work.erase(First);
444 NodeChildrenMap::iterator CF = NCM.find(N);
445 if (CF != NCM.end()) {
446 Work.insert(Work.end(), CF->second.begin(), CF->second.end());
447 Nodes.insert(CF->second.begin(), CF->second.end());
448 }
449 }
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000450}
451
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000452namespace {
Eugene Zelenko82085922016-12-13 22:13:50 +0000453
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000454 typedef std::set<NodeSet> NodeSymRel;
455 typedef std::pair<GepNode*,GepNode*> NodePair;
456 typedef std::set<NodePair> NodePairSet;
457
Eugene Zelenko82085922016-12-13 22:13:50 +0000458} // end anonymous namespace
459
460static const NodeSet *node_class(GepNode *N, NodeSymRel &Rel) {
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000461 for (NodeSymRel::iterator I = Rel.begin(), E = Rel.end(); I != E; ++I)
462 if (I->count(N))
463 return &*I;
Eugene Zelenko82085922016-12-13 22:13:50 +0000464 return nullptr;
465}
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000466
467 // Create an ordered pair of GepNode pointers. The pair will be used in
468 // determining equality. The only purpose of the ordering is to eliminate
469 // duplication due to the commutativity of equality/non-equality.
Eugene Zelenko82085922016-12-13 22:13:50 +0000470static NodePair node_pair(GepNode *N1, GepNode *N2) {
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000471 uintptr_t P1 = uintptr_t(N1), P2 = uintptr_t(N2);
472 if (P1 <= P2)
473 return std::make_pair(N1, N2);
474 return std::make_pair(N2, N1);
Eugene Zelenko82085922016-12-13 22:13:50 +0000475}
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000476
Eugene Zelenko82085922016-12-13 22:13:50 +0000477static unsigned node_hash(GepNode *N) {
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000478 // Include everything except flags and parent.
479 FoldingSetNodeID ID;
480 ID.AddPointer(N->Idx);
481 ID.AddPointer(N->PTy);
482 return ID.ComputeHash();
Eugene Zelenko82085922016-12-13 22:13:50 +0000483}
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000484
Eugene Zelenko82085922016-12-13 22:13:50 +0000485static bool node_eq(GepNode *N1, GepNode *N2, NodePairSet &Eq,
486 NodePairSet &Ne) {
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000487 // Don't cache the result for nodes with different hashes. The hash
488 // comparison is fast enough.
489 if (node_hash(N1) != node_hash(N2))
490 return false;
491
492 NodePair NP = node_pair(N1, N2);
493 NodePairSet::iterator FEq = Eq.find(NP);
494 if (FEq != Eq.end())
495 return true;
496 NodePairSet::iterator FNe = Ne.find(NP);
497 if (FNe != Ne.end())
498 return false;
499 // Not previously compared.
500 bool Root1 = N1->Flags & GepNode::Root;
501 bool Root2 = N2->Flags & GepNode::Root;
502 NodePair P = node_pair(N1, N2);
503 // If the Root flag has different values, the nodes are different.
504 // If both nodes are root nodes, but their base pointers differ,
505 // they are different.
506 if (Root1 != Root2 || (Root1 && N1->BaseVal != N2->BaseVal)) {
507 Ne.insert(P);
508 return false;
509 }
510 // Here the root flags are identical, and for root nodes the
511 // base pointers are equal, so the root nodes are equal.
512 // For non-root nodes, compare their parent nodes.
513 if (Root1 || node_eq(N1->Parent, N2->Parent, Eq, Ne)) {
514 Eq.insert(P);
515 return true;
516 }
517 return false;
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000518}
519
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000520void HexagonCommonGEP::common() {
521 // The essence of this commoning is finding gep nodes that are equal.
522 // To do this we need to compare all pairs of nodes. To save time,
523 // first, partition the set of all nodes into sets of potentially equal
524 // nodes, and then compare pairs from within each partition.
525 typedef std::map<unsigned,NodeSet> NodeSetMap;
526 NodeSetMap MaybeEq;
527
528 for (NodeVect::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) {
529 GepNode *N = *I;
530 unsigned H = node_hash(N);
531 MaybeEq[H].insert(N);
532 }
533
534 // Compute the equivalence relation for the gep nodes. Use two caches,
535 // one for equality and the other for non-equality.
536 NodeSymRel EqRel; // Equality relation (as set of equivalence classes).
537 NodePairSet Eq, Ne; // Caches.
538 for (NodeSetMap::iterator I = MaybeEq.begin(), E = MaybeEq.end();
539 I != E; ++I) {
540 NodeSet &S = I->second;
541 for (NodeSet::iterator NI = S.begin(), NE = S.end(); NI != NE; ++NI) {
542 GepNode *N = *NI;
543 // If node already has a class, then the class must have been created
544 // in a prior iteration of this loop. Since equality is transitive,
545 // nothing more will be added to that class, so skip it.
546 if (node_class(N, EqRel))
547 continue;
548
549 // Create a new class candidate now.
550 NodeSet C;
551 for (NodeSet::iterator NJ = std::next(NI); NJ != NE; ++NJ)
552 if (node_eq(N, *NJ, Eq, Ne))
553 C.insert(*NJ);
554 // If Tmp is empty, N would be the only element in it. Don't bother
555 // creating a class for it then.
556 if (!C.empty()) {
557 C.insert(N); // Finalize the set before adding it to the relation.
558 std::pair<NodeSymRel::iterator, bool> Ins = EqRel.insert(C);
559 (void)Ins;
560 assert(Ins.second && "Cannot add a class");
561 }
562 }
563 }
564
565 DEBUG({
566 dbgs() << "Gep node equality:\n";
567 for (NodePairSet::iterator I = Eq.begin(), E = Eq.end(); I != E; ++I)
568 dbgs() << "{ " << I->first << ", " << I->second << " }\n";
569
570 dbgs() << "Gep equivalence classes:\n";
571 for (NodeSymRel::iterator I = EqRel.begin(), E = EqRel.end(); I != E; ++I) {
572 dbgs() << '{';
573 const NodeSet &S = *I;
574 for (NodeSet::const_iterator J = S.begin(), F = S.end(); J != F; ++J) {
575 if (J != S.begin())
576 dbgs() << ',';
577 dbgs() << ' ' << *J;
578 }
579 dbgs() << " }\n";
580 }
581 });
582
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000583 // Create a projection from a NodeSet to the minimal element in it.
584 typedef std::map<const NodeSet*,GepNode*> ProjMap;
585 ProjMap PM;
586 for (NodeSymRel::iterator I = EqRel.begin(), E = EqRel.end(); I != E; ++I) {
587 const NodeSet &S = *I;
588 GepNode *Min = *std::min_element(S.begin(), S.end(), NodeOrder);
589 std::pair<ProjMap::iterator,bool> Ins = PM.insert(std::make_pair(&S, Min));
590 (void)Ins;
591 assert(Ins.second && "Cannot add minimal element");
592
593 // Update the min element's flags, and user list.
594 uint32_t Flags = 0;
595 UseSet &MinUs = Uses[Min];
596 for (NodeSet::iterator J = S.begin(), F = S.end(); J != F; ++J) {
597 GepNode *N = *J;
598 uint32_t NF = N->Flags;
599 // If N is used, append all original values of N to the list of
600 // original values of Min.
601 if (NF & GepNode::Used)
602 MinUs.insert(Uses[N].begin(), Uses[N].end());
603 Flags |= NF;
604 }
605 if (MinUs.empty())
606 Uses.erase(Min);
607
608 // The collected flags should include all the flags from the min element.
609 assert((Min->Flags & Flags) == Min->Flags);
610 Min->Flags = Flags;
611 }
612
613 // Commoning: for each non-root gep node, replace "Parent" with the
614 // selected (minimum) node from the corresponding equivalence class.
615 // If a given parent does not have an equivalence class, leave it
616 // unchanged (it means that it's the only element in its class).
617 for (NodeVect::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) {
618 GepNode *N = *I;
619 if (N->Flags & GepNode::Root)
620 continue;
621 const NodeSet *PC = node_class(N->Parent, EqRel);
622 if (!PC)
623 continue;
624 ProjMap::iterator F = PM.find(PC);
625 if (F == PM.end())
626 continue;
627 // Found a replacement, use it.
628 GepNode *Rep = F->second;
629 N->Parent = Rep;
630 }
631
632 DEBUG(dbgs() << "Gep nodes after commoning:\n" << Nodes);
633
634 // Finally, erase the nodes that are no longer used.
635 NodeSet Erase;
636 for (NodeVect::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) {
637 GepNode *N = *I;
638 const NodeSet *PC = node_class(N, EqRel);
639 if (!PC)
640 continue;
641 ProjMap::iterator F = PM.find(PC);
642 if (F == PM.end())
643 continue;
644 if (N == F->second)
645 continue;
646 // Node for removal.
647 Erase.insert(*I);
648 }
David Majnemerc7004902016-08-12 04:32:37 +0000649 NodeVect::iterator NewE = remove_if(Nodes, in_set(Erase));
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000650 Nodes.resize(std::distance(Nodes.begin(), NewE));
651
652 DEBUG(dbgs() << "Gep nodes after post-commoning cleanup:\n" << Nodes);
653}
654
Eugene Zelenko82085922016-12-13 22:13:50 +0000655template <typename T>
656static BasicBlock *nearest_common_dominator(DominatorTree *DT, T &Blocks) {
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000657 DEBUG({
658 dbgs() << "NCD of {";
659 for (typename T::iterator I = Blocks.begin(), E = Blocks.end();
660 I != E; ++I) {
661 if (!*I)
662 continue;
663 BasicBlock *B = cast<BasicBlock>(*I);
664 dbgs() << ' ' << B->getName();
665 }
666 dbgs() << " }\n";
667 });
668
Eugene Zelenko82085922016-12-13 22:13:50 +0000669 // Allow null basic blocks in Blocks. In such cases, return nullptr.
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000670 typename T::iterator I = Blocks.begin(), E = Blocks.end();
671 if (I == E || !*I)
Eugene Zelenko82085922016-12-13 22:13:50 +0000672 return nullptr;
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000673 BasicBlock *Dom = cast<BasicBlock>(*I);
674 while (++I != E) {
675 BasicBlock *B = cast_or_null<BasicBlock>(*I);
Eugene Zelenko82085922016-12-13 22:13:50 +0000676 Dom = B ? DT->findNearestCommonDominator(Dom, B) : nullptr;
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000677 if (!Dom)
Eugene Zelenko82085922016-12-13 22:13:50 +0000678 return nullptr;
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000679 }
680 DEBUG(dbgs() << "computed:" << Dom->getName() << '\n');
681 return Dom;
Eugene Zelenko82085922016-12-13 22:13:50 +0000682}
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000683
Eugene Zelenko82085922016-12-13 22:13:50 +0000684template <typename T>
685static BasicBlock *nearest_common_dominatee(DominatorTree *DT, T &Blocks) {
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000686 // If two blocks, A and B, dominate a block C, then A dominates B,
687 // or B dominates A.
688 typename T::iterator I = Blocks.begin(), E = Blocks.end();
689 // Find the first non-null block.
690 while (I != E && !*I)
691 ++I;
692 if (I == E)
693 return DT->getRoot();
694 BasicBlock *DomB = cast<BasicBlock>(*I);
695 while (++I != E) {
696 if (!*I)
697 continue;
698 BasicBlock *B = cast<BasicBlock>(*I);
699 if (DT->dominates(B, DomB))
700 continue;
701 if (!DT->dominates(DomB, B))
Eugene Zelenko82085922016-12-13 22:13:50 +0000702 return nullptr;
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000703 DomB = B;
704 }
705 return DomB;
Eugene Zelenko82085922016-12-13 22:13:50 +0000706}
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000707
Eugene Zelenko82085922016-12-13 22:13:50 +0000708// Find the first use in B of any value from Values. If no such use,
709// return B->end().
710template <typename T>
711static BasicBlock::iterator first_use_of_in_block(T &Values, BasicBlock *B) {
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000712 BasicBlock::iterator FirstUse = B->end(), BEnd = B->end();
713 typedef typename T::iterator iterator;
714 for (iterator I = Values.begin(), E = Values.end(); I != E; ++I) {
715 Value *V = *I;
716 // If V is used in a PHI node, the use belongs to the incoming block,
717 // not the block with the PHI node. In the incoming block, the use
718 // would be considered as being at the end of it, so it cannot
719 // influence the position of the first use (which is assumed to be
720 // at the end to start with).
721 if (isa<PHINode>(V))
722 continue;
723 if (!isa<Instruction>(V))
724 continue;
725 Instruction *In = cast<Instruction>(V);
726 if (In->getParent() != B)
727 continue;
Duncan P. N. Exon Smitha72c6e22015-10-20 00:46:39 +0000728 BasicBlock::iterator It = In->getIterator();
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000729 if (std::distance(FirstUse, BEnd) < std::distance(It, BEnd))
730 FirstUse = It;
731 }
732 return FirstUse;
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000733}
734
Eugene Zelenko82085922016-12-13 22:13:50 +0000735static bool is_empty(const BasicBlock *B) {
736 return B->empty() || (&*B->begin() == B->getTerminator());
737}
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000738
739BasicBlock *HexagonCommonGEP::recalculatePlacement(GepNode *Node,
740 NodeChildrenMap &NCM, NodeToValueMap &Loc) {
741 DEBUG(dbgs() << "Loc for node:" << Node << '\n');
742 // Recalculate the placement for Node, assuming that the locations of
743 // its children in Loc are valid.
Eugene Zelenko82085922016-12-13 22:13:50 +0000744 // Return nullptr if there is no valid placement for Node (for example, it
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000745 // uses an index value that is not available at the location required
746 // to dominate all children, etc.).
747
748 // Find the nearest common dominator for:
749 // - all users, if the node is used, and
750 // - all children.
751 ValueVect Bs;
752 if (Node->Flags & GepNode::Used) {
753 // Append all blocks with uses of the original values to the
754 // block vector Bs.
755 NodeToUsesMap::iterator UF = Uses.find(Node);
756 assert(UF != Uses.end() && "Used node with no use information");
757 UseSet &Us = UF->second;
758 for (UseSet::iterator I = Us.begin(), E = Us.end(); I != E; ++I) {
759 Use *U = *I;
760 User *R = U->getUser();
761 if (!isa<Instruction>(R))
762 continue;
763 BasicBlock *PB = isa<PHINode>(R)
764 ? cast<PHINode>(R)->getIncomingBlock(*U)
765 : cast<Instruction>(R)->getParent();
766 Bs.push_back(PB);
767 }
768 }
769 // Append the location of each child.
770 NodeChildrenMap::iterator CF = NCM.find(Node);
771 if (CF != NCM.end()) {
772 NodeVect &Cs = CF->second;
773 for (NodeVect::iterator I = Cs.begin(), E = Cs.end(); I != E; ++I) {
774 GepNode *CN = *I;
775 NodeToValueMap::iterator LF = Loc.find(CN);
776 // If the child is only used in GEP instructions (i.e. is not used in
777 // non-GEP instructions), the nearest dominator computed for it may
778 // have been null. In such case it won't have a location available.
779 if (LF == Loc.end())
780 continue;
781 Bs.push_back(LF->second);
782 }
783 }
784
785 BasicBlock *DomB = nearest_common_dominator(DT, Bs);
786 if (!DomB)
Eugene Zelenko82085922016-12-13 22:13:50 +0000787 return nullptr;
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000788 // Check if the index used by Node dominates the computed dominator.
789 Instruction *IdxI = dyn_cast<Instruction>(Node->Idx);
790 if (IdxI && !DT->dominates(IdxI->getParent(), DomB))
Eugene Zelenko82085922016-12-13 22:13:50 +0000791 return nullptr;
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000792
793 // Avoid putting nodes into empty blocks.
794 while (is_empty(DomB)) {
795 DomTreeNode *N = (*DT)[DomB]->getIDom();
796 if (!N)
797 break;
798 DomB = N->getBlock();
799 }
800
801 // Otherwise, DomB is fine. Update the location map.
802 Loc[Node] = DomB;
803 return DomB;
804}
805
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000806BasicBlock *HexagonCommonGEP::recalculatePlacementRec(GepNode *Node,
807 NodeChildrenMap &NCM, NodeToValueMap &Loc) {
808 DEBUG(dbgs() << "LocRec begin for node:" << Node << '\n');
809 // Recalculate the placement of Node, after recursively recalculating the
810 // placements of all its children.
811 NodeChildrenMap::iterator CF = NCM.find(Node);
812 if (CF != NCM.end()) {
813 NodeVect &Cs = CF->second;
814 for (NodeVect::iterator I = Cs.begin(), E = Cs.end(); I != E; ++I)
815 recalculatePlacementRec(*I, NCM, Loc);
816 }
817 BasicBlock *LB = recalculatePlacement(Node, NCM, Loc);
818 DEBUG(dbgs() << "LocRec end for node:" << Node << '\n');
819 return LB;
820}
821
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000822bool HexagonCommonGEP::isInvariantIn(Value *Val, Loop *L) {
823 if (isa<Constant>(Val) || isa<Argument>(Val))
824 return true;
825 Instruction *In = dyn_cast<Instruction>(Val);
826 if (!In)
827 return false;
828 BasicBlock *HdrB = L->getHeader(), *DefB = In->getParent();
829 return DT->properlyDominates(DefB, HdrB);
830}
831
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000832bool HexagonCommonGEP::isInvariantIn(GepNode *Node, Loop *L) {
833 if (Node->Flags & GepNode::Root)
834 if (!isInvariantIn(Node->BaseVal, L))
835 return false;
836 return isInvariantIn(Node->Idx, L);
837}
838
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000839bool HexagonCommonGEP::isInMainPath(BasicBlock *B, Loop *L) {
840 BasicBlock *HB = L->getHeader();
841 BasicBlock *LB = L->getLoopLatch();
842 // B must post-dominate the loop header or dominate the loop latch.
843 if (PDT->dominates(B, HB))
844 return true;
845 if (LB && DT->dominates(B, LB))
846 return true;
847 return false;
848}
849
Eugene Zelenko82085922016-12-13 22:13:50 +0000850static BasicBlock *preheader(DominatorTree *DT, Loop *L) {
851 if (BasicBlock *PH = L->getLoopPreheader())
852 return PH;
853 if (!OptSpeculate)
854 return nullptr;
855 DomTreeNode *DN = DT->getNode(L->getHeader());
856 if (!DN)
857 return nullptr;
858 return DN->getIDom()->getBlock();
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000859}
860
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000861BasicBlock *HexagonCommonGEP::adjustForInvariance(GepNode *Node,
862 NodeChildrenMap &NCM, NodeToValueMap &Loc) {
863 // Find the "topmost" location for Node: it must be dominated by both,
864 // its parent (or the BaseVal, if it's a root node), and by the index
865 // value.
866 ValueVect Bs;
867 if (Node->Flags & GepNode::Root) {
868 if (Instruction *PIn = dyn_cast<Instruction>(Node->BaseVal))
869 Bs.push_back(PIn->getParent());
870 } else {
871 Bs.push_back(Loc[Node->Parent]);
872 }
873 if (Instruction *IIn = dyn_cast<Instruction>(Node->Idx))
874 Bs.push_back(IIn->getParent());
875 BasicBlock *TopB = nearest_common_dominatee(DT, Bs);
876
877 // Traverse the loop nest upwards until we find a loop in which Node
878 // is no longer invariant, or until we get to the upper limit of Node's
879 // placement. The traversal will also stop when a suitable "preheader"
880 // cannot be found for a given loop. The "preheader" may actually be
881 // a regular block outside of the loop (i.e. not guarded), in which case
882 // the Node will be speculated.
883 // For nodes that are not in the main path of the containing loop (i.e.
884 // are not executed in each iteration), do not move them out of the loop.
885 BasicBlock *LocB = cast_or_null<BasicBlock>(Loc[Node]);
886 if (LocB) {
887 Loop *Lp = LI->getLoopFor(LocB);
888 while (Lp) {
889 if (!isInvariantIn(Node, Lp) || !isInMainPath(LocB, Lp))
890 break;
891 BasicBlock *NewLoc = preheader(DT, Lp);
892 if (!NewLoc || !DT->dominates(TopB, NewLoc))
893 break;
894 Lp = Lp->getParentLoop();
895 LocB = NewLoc;
896 }
897 }
898 Loc[Node] = LocB;
899
900 // Recursively compute the locations of all children nodes.
901 NodeChildrenMap::iterator CF = NCM.find(Node);
902 if (CF != NCM.end()) {
903 NodeVect &Cs = CF->second;
904 for (NodeVect::iterator I = Cs.begin(), E = Cs.end(); I != E; ++I)
905 adjustForInvariance(*I, NCM, Loc);
906 }
907 return LocB;
908}
909
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000910namespace {
Eugene Zelenko82085922016-12-13 22:13:50 +0000911
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000912 struct LocationAsBlock {
913 LocationAsBlock(const NodeToValueMap &L) : Map(L) {}
Eugene Zelenko82085922016-12-13 22:13:50 +0000914
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000915 const NodeToValueMap &Map;
916 };
917
918 raw_ostream &operator<< (raw_ostream &OS,
919 const LocationAsBlock &Loc) LLVM_ATTRIBUTE_UNUSED ;
920 raw_ostream &operator<< (raw_ostream &OS, const LocationAsBlock &Loc) {
921 for (NodeToValueMap::const_iterator I = Loc.Map.begin(), E = Loc.Map.end();
922 I != E; ++I) {
923 OS << I->first << " -> ";
924 BasicBlock *B = cast<BasicBlock>(I->second);
925 OS << B->getName() << '(' << B << ')';
926 OS << '\n';
927 }
928 return OS;
929 }
930
931 inline bool is_constant(GepNode *N) {
932 return isa<ConstantInt>(N->Idx);
933 }
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000934
Eugene Zelenko82085922016-12-13 22:13:50 +0000935} // end anonymous namespace
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000936
937void HexagonCommonGEP::separateChainForNode(GepNode *Node, Use *U,
938 NodeToValueMap &Loc) {
939 User *R = U->getUser();
940 DEBUG(dbgs() << "Separating chain for node (" << Node << ") user: "
941 << *R << '\n');
942 BasicBlock *PB = cast<Instruction>(R)->getParent();
943
944 GepNode *N = Node;
Eugene Zelenko82085922016-12-13 22:13:50 +0000945 GepNode *C = nullptr, *NewNode = nullptr;
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000946 while (is_constant(N) && !(N->Flags & GepNode::Root)) {
947 // XXX if (single-use) dont-replicate;
948 GepNode *NewN = new (*Mem) GepNode(N);
949 Nodes.push_back(NewN);
950 Loc[NewN] = PB;
951
952 if (N == Node)
953 NewNode = NewN;
954 NewN->Flags &= ~GepNode::Used;
955 if (C)
956 C->Parent = NewN;
957 C = NewN;
958 N = N->Parent;
959 }
960 if (!NewNode)
961 return;
962
963 // Move over all uses that share the same user as U from Node to NewNode.
964 NodeToUsesMap::iterator UF = Uses.find(Node);
965 assert(UF != Uses.end());
966 UseSet &Us = UF->second;
967 UseSet NewUs;
968 for (UseSet::iterator I = Us.begin(); I != Us.end(); ) {
969 User *S = (*I)->getUser();
970 UseSet::iterator Nx = std::next(I);
971 if (S == R) {
972 NewUs.insert(*I);
973 Us.erase(I);
974 }
975 I = Nx;
976 }
977 if (Us.empty()) {
978 Node->Flags &= ~GepNode::Used;
979 Uses.erase(UF);
980 }
981
982 // Should at least have U in NewUs.
983 NewNode->Flags |= GepNode::Used;
984 DEBUG(dbgs() << "new node: " << NewNode << " " << *NewNode << '\n');
985 assert(!NewUs.empty());
986 Uses[NewNode] = NewUs;
987}
988
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +0000989void HexagonCommonGEP::separateConstantChains(GepNode *Node,
990 NodeChildrenMap &NCM, NodeToValueMap &Loc) {
991 // First approximation: extract all chains.
992 NodeSet Ns;
993 nodes_for_root(Node, NCM, Ns);
994
995 DEBUG(dbgs() << "Separating constant chains for node: " << Node << '\n');
996 // Collect all used nodes together with the uses from loads and stores,
997 // where the GEP node could be folded into the load/store instruction.
998 NodeToUsesMap FNs; // Foldable nodes.
999 for (NodeSet::iterator I = Ns.begin(), E = Ns.end(); I != E; ++I) {
1000 GepNode *N = *I;
1001 if (!(N->Flags & GepNode::Used))
1002 continue;
1003 NodeToUsesMap::iterator UF = Uses.find(N);
1004 assert(UF != Uses.end());
1005 UseSet &Us = UF->second;
1006 // Loads/stores that use the node N.
1007 UseSet LSs;
1008 for (UseSet::iterator J = Us.begin(), F = Us.end(); J != F; ++J) {
1009 Use *U = *J;
1010 User *R = U->getUser();
1011 // We're interested in uses that provide the address. It can happen
1012 // that the value may also be provided via GEP, but we won't handle
1013 // those cases here for now.
1014 if (LoadInst *Ld = dyn_cast<LoadInst>(R)) {
1015 unsigned PtrX = LoadInst::getPointerOperandIndex();
1016 if (&Ld->getOperandUse(PtrX) == U)
1017 LSs.insert(U);
1018 } else if (StoreInst *St = dyn_cast<StoreInst>(R)) {
1019 unsigned PtrX = StoreInst::getPointerOperandIndex();
1020 if (&St->getOperandUse(PtrX) == U)
1021 LSs.insert(U);
1022 }
1023 }
1024 // Even if the total use count is 1, separating the chain may still be
1025 // beneficial, since the constant chain may be longer than the GEP alone
1026 // would be (e.g. if the parent node has a constant index and also has
1027 // other children).
1028 if (!LSs.empty())
1029 FNs.insert(std::make_pair(N, LSs));
1030 }
1031
1032 DEBUG(dbgs() << "Nodes with foldable users:\n" << FNs);
1033
1034 for (NodeToUsesMap::iterator I = FNs.begin(), E = FNs.end(); I != E; ++I) {
1035 GepNode *N = I->first;
1036 UseSet &Us = I->second;
1037 for (UseSet::iterator J = Us.begin(), F = Us.end(); J != F; ++J)
1038 separateChainForNode(N, *J, Loc);
1039 }
1040}
1041
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +00001042void HexagonCommonGEP::computeNodePlacement(NodeToValueMap &Loc) {
1043 // Compute the inverse of the Node.Parent links. Also, collect the set
1044 // of root nodes.
1045 NodeChildrenMap NCM;
1046 NodeVect Roots;
1047 invert_find_roots(Nodes, NCM, Roots);
1048
1049 // Compute the initial placement determined by the users' locations, and
1050 // the locations of the child nodes.
1051 for (NodeVect::iterator I = Roots.begin(), E = Roots.end(); I != E; ++I)
1052 recalculatePlacementRec(*I, NCM, Loc);
1053
1054 DEBUG(dbgs() << "Initial node placement:\n" << LocationAsBlock(Loc));
1055
1056 if (OptEnableInv) {
1057 for (NodeVect::iterator I = Roots.begin(), E = Roots.end(); I != E; ++I)
1058 adjustForInvariance(*I, NCM, Loc);
1059
1060 DEBUG(dbgs() << "Node placement after adjustment for invariance:\n"
1061 << LocationAsBlock(Loc));
1062 }
1063 if (OptEnableConst) {
1064 for (NodeVect::iterator I = Roots.begin(), E = Roots.end(); I != E; ++I)
1065 separateConstantChains(*I, NCM, Loc);
1066 }
1067 DEBUG(dbgs() << "Node use information:\n" << Uses);
1068
1069 // At the moment, there is no further refinement of the initial placement.
1070 // Such a refinement could include splitting the nodes if they are placed
1071 // too far from some of its users.
1072
1073 DEBUG(dbgs() << "Final node placement:\n" << LocationAsBlock(Loc));
1074}
1075
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +00001076Value *HexagonCommonGEP::fabricateGEP(NodeVect &NA, BasicBlock::iterator At,
1077 BasicBlock *LocB) {
1078 DEBUG(dbgs() << "Fabricating GEP in " << LocB->getName()
1079 << " for nodes:\n" << NA);
1080 unsigned Num = NA.size();
1081 GepNode *RN = NA[0];
1082 assert((RN->Flags & GepNode::Root) && "Creating GEP for non-root");
1083
Eugene Zelenko82085922016-12-13 22:13:50 +00001084 Value *NewInst = nullptr;
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +00001085 Value *Input = RN->BaseVal;
1086 Value **IdxList = new Value*[Num+1];
1087 unsigned nax = 0;
1088 do {
1089 unsigned IdxC = 0;
1090 // If the type of the input of the first node is not a pointer,
1091 // we need to add an artificial i32 0 to the indices (because the
1092 // actual input in the IR will be a pointer).
1093 if (!NA[nax]->PTy->isPointerTy()) {
1094 Type *Int32Ty = Type::getInt32Ty(*Ctx);
1095 IdxList[IdxC++] = ConstantInt::get(Int32Ty, 0);
1096 }
1097
1098 // Keep adding indices from NA until we have to stop and generate
1099 // an "intermediate" GEP.
1100 while (++nax <= Num) {
1101 GepNode *N = NA[nax-1];
1102 IdxList[IdxC++] = N->Idx;
1103 if (nax < Num) {
1104 // We have to stop, if the expected type of the output of this node
1105 // is not the same as the input type of the next node.
1106 Type *NextTy = next_type(N->PTy, N->Idx);
1107 if (NextTy != NA[nax]->PTy)
1108 break;
1109 }
1110 }
1111 ArrayRef<Value*> A(IdxList, IdxC);
1112 Type *InpTy = Input->getType();
1113 Type *ElTy = cast<PointerType>(InpTy->getScalarType())->getElementType();
Duncan P. N. Exon Smitha72c6e22015-10-20 00:46:39 +00001114 NewInst = GetElementPtrInst::Create(ElTy, Input, A, "cgep", &*At);
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +00001115 DEBUG(dbgs() << "new GEP: " << *NewInst << '\n');
1116 Input = NewInst;
1117 } while (nax <= Num);
1118
1119 delete[] IdxList;
1120 return NewInst;
1121}
1122
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +00001123void HexagonCommonGEP::getAllUsersForNode(GepNode *Node, ValueVect &Values,
1124 NodeChildrenMap &NCM) {
1125 NodeVect Work;
1126 Work.push_back(Node);
1127
1128 while (!Work.empty()) {
1129 NodeVect::iterator First = Work.begin();
1130 GepNode *N = *First;
1131 Work.erase(First);
1132 if (N->Flags & GepNode::Used) {
1133 NodeToUsesMap::iterator UF = Uses.find(N);
1134 assert(UF != Uses.end() && "No use information for used node");
1135 UseSet &Us = UF->second;
1136 for (UseSet::iterator I = Us.begin(), E = Us.end(); I != E; ++I)
1137 Values.push_back((*I)->getUser());
1138 }
1139 NodeChildrenMap::iterator CF = NCM.find(N);
1140 if (CF != NCM.end()) {
1141 NodeVect &Cs = CF->second;
1142 Work.insert(Work.end(), Cs.begin(), Cs.end());
1143 }
1144 }
1145}
1146
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +00001147void HexagonCommonGEP::materialize(NodeToValueMap &Loc) {
1148 DEBUG(dbgs() << "Nodes before materialization:\n" << Nodes << '\n');
1149 NodeChildrenMap NCM;
1150 NodeVect Roots;
1151 // Compute the inversion again, since computing placement could alter
1152 // "parent" relation between nodes.
1153 invert_find_roots(Nodes, NCM, Roots);
1154
1155 while (!Roots.empty()) {
1156 NodeVect::iterator First = Roots.begin();
1157 GepNode *Root = *First, *Last = *First;
1158 Roots.erase(First);
1159
1160 NodeVect NA; // Nodes to assemble.
1161 // Append to NA all child nodes up to (and including) the first child
1162 // that:
1163 // (1) has more than 1 child, or
1164 // (2) is used, or
1165 // (3) has a child located in a different block.
1166 bool LastUsed = false;
1167 unsigned LastCN = 0;
1168 // The location may be null if the computation failed (it can legitimately
1169 // happen for nodes created from dead GEPs).
1170 Value *LocV = Loc[Last];
1171 if (!LocV)
1172 continue;
1173 BasicBlock *LastB = cast<BasicBlock>(LocV);
1174 do {
1175 NA.push_back(Last);
1176 LastUsed = (Last->Flags & GepNode::Used);
1177 if (LastUsed)
1178 break;
1179 NodeChildrenMap::iterator CF = NCM.find(Last);
1180 LastCN = (CF != NCM.end()) ? CF->second.size() : 0;
1181 if (LastCN != 1)
1182 break;
1183 GepNode *Child = CF->second.front();
1184 BasicBlock *ChildB = cast_or_null<BasicBlock>(Loc[Child]);
Eugene Zelenko82085922016-12-13 22:13:50 +00001185 if (ChildB != nullptr && LastB != ChildB)
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +00001186 break;
1187 Last = Child;
1188 } while (true);
1189
Duncan P. N. Exon Smitha72c6e22015-10-20 00:46:39 +00001190 BasicBlock::iterator InsertAt = LastB->getTerminator()->getIterator();
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +00001191 if (LastUsed || LastCN > 0) {
1192 ValueVect Urs;
1193 getAllUsersForNode(Root, Urs, NCM);
1194 BasicBlock::iterator FirstUse = first_use_of_in_block(Urs, LastB);
1195 if (FirstUse != LastB->end())
1196 InsertAt = FirstUse;
1197 }
1198
1199 // Generate a new instruction for NA.
1200 Value *NewInst = fabricateGEP(NA, InsertAt, LastB);
1201
1202 // Convert all the children of Last node into roots, and append them
1203 // to the Roots list.
1204 if (LastCN > 0) {
1205 NodeVect &Cs = NCM[Last];
1206 for (NodeVect::iterator I = Cs.begin(), E = Cs.end(); I != E; ++I) {
1207 GepNode *CN = *I;
1208 CN->Flags &= ~GepNode::Internal;
1209 CN->Flags |= GepNode::Root;
1210 CN->BaseVal = NewInst;
1211 Roots.push_back(CN);
1212 }
1213 }
1214
1215 // Lastly, if the Last node was used, replace all uses with the new GEP.
1216 // The uses reference the original GEP values.
1217 if (LastUsed) {
1218 NodeToUsesMap::iterator UF = Uses.find(Last);
1219 assert(UF != Uses.end() && "No use information found");
1220 UseSet &Us = UF->second;
1221 for (UseSet::iterator I = Us.begin(), E = Us.end(); I != E; ++I) {
1222 Use *U = *I;
1223 U->set(NewInst);
1224 }
1225 }
1226 }
1227}
1228
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +00001229void HexagonCommonGEP::removeDeadCode() {
1230 ValueVect BO;
1231 BO.push_back(&Fn->front());
1232
1233 for (unsigned i = 0; i < BO.size(); ++i) {
1234 BasicBlock *B = cast<BasicBlock>(BO[i]);
Daniel Berlin73ad5cb2017-02-09 20:37:46 +00001235 for (auto DTN : children<DomTreeNode*>(DT->getNode(B)))
Daniel Berlin58a6e572017-02-09 20:37:24 +00001236 BO.push_back(DTN->getBlock());
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +00001237 }
1238
1239 for (unsigned i = BO.size(); i > 0; --i) {
1240 BasicBlock *B = cast<BasicBlock>(BO[i-1]);
1241 BasicBlock::InstListType &IL = B->getInstList();
1242 typedef BasicBlock::InstListType::reverse_iterator reverse_iterator;
1243 ValueVect Ins;
1244 for (reverse_iterator I = IL.rbegin(), E = IL.rend(); I != E; ++I)
1245 Ins.push_back(&*I);
1246 for (ValueVect::iterator I = Ins.begin(), E = Ins.end(); I != E; ++I) {
1247 Instruction *In = cast<Instruction>(*I);
1248 if (isInstructionTriviallyDead(In))
1249 In->eraseFromParent();
1250 }
1251 }
1252}
1253
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +00001254bool HexagonCommonGEP::runOnFunction(Function &F) {
Andrew Kaylor5b444a22016-04-26 19:46:28 +00001255 if (skipFunction(F))
1256 return false;
1257
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +00001258 // For now bail out on C++ exception handling.
1259 for (Function::iterator A = F.begin(), Z = F.end(); A != Z; ++A)
1260 for (BasicBlock::iterator I = A->begin(), E = A->end(); I != E; ++I)
1261 if (isa<InvokeInst>(I) || isa<LandingPadInst>(I))
1262 return false;
1263
1264 Fn = &F;
1265 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
Hongbin Zheng3f978402016-02-25 17:54:07 +00001266 PDT = &getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +00001267 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1268 Ctx = &F.getContext();
1269
1270 Nodes.clear();
1271 Uses.clear();
1272 NodeOrder.clear();
1273
1274 SpecificBumpPtrAllocator<GepNode> Allocator;
1275 Mem = &Allocator;
1276
1277 collect();
1278 common();
1279
1280 NodeToValueMap Loc;
1281 computeNodePlacement(Loc);
1282 materialize(Loc);
1283 removeDeadCode();
1284
Filipe Cabecinhas0da99372016-04-29 15:22:48 +00001285#ifdef EXPENSIVE_CHECKS
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +00001286 // Run this only when expensive checks are enabled.
1287 verifyFunction(F);
1288#endif
1289 return true;
1290}
1291
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +00001292namespace llvm {
Eugene Zelenko82085922016-12-13 22:13:50 +00001293
Krzysztof Parzyszek79b24332015-07-08 19:22:28 +00001294 FunctionPass *createHexagonCommonGEP() {
1295 return new HexagonCommonGEP();
1296 }
Eugene Zelenko82085922016-12-13 22:13:50 +00001297
1298} // end namespace llvm