1327952Sdim//===- HexagonCommonGEP.cpp -----------------------------------------------===// 2286425Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6286425Sdim// 7286425Sdim//===----------------------------------------------------------------------===// 8286425Sdim 9314564Sdim#include "llvm/ADT/ArrayRef.h" 10286425Sdim#include "llvm/ADT/FoldingSet.h" 11327952Sdim#include "llvm/ADT/GraphTraits.h" 12360784Sdim#include "llvm/ADT/STLExtras.h" 13353358Sdim#include "llvm/ADT/SetVector.h" 14314564Sdim#include "llvm/ADT/StringRef.h" 15286425Sdim#include "llvm/Analysis/LoopInfo.h" 16286425Sdim#include "llvm/Analysis/PostDominators.h" 17314564Sdim#include "llvm/IR/BasicBlock.h" 18314564Sdim#include "llvm/IR/Constant.h" 19286425Sdim#include "llvm/IR/Constants.h" 20314564Sdim#include "llvm/IR/DerivedTypes.h" 21286425Sdim#include "llvm/IR/Dominators.h" 22286425Sdim#include "llvm/IR/Function.h" 23314564Sdim#include "llvm/IR/Instruction.h" 24286425Sdim#include "llvm/IR/Instructions.h" 25314564Sdim#include "llvm/IR/Type.h" 26314564Sdim#include "llvm/IR/Use.h" 27314564Sdim#include "llvm/IR/User.h" 28314564Sdim#include "llvm/IR/Value.h" 29286425Sdim#include "llvm/IR/Verifier.h" 30360784Sdim#include "llvm/InitializePasses.h" 31314564Sdim#include "llvm/Pass.h" 32286425Sdim#include "llvm/Support/Allocator.h" 33314564Sdim#include "llvm/Support/Casting.h" 34286425Sdim#include "llvm/Support/CommandLine.h" 35314564Sdim#include "llvm/Support/Compiler.h" 36286425Sdim#include "llvm/Support/Debug.h" 37286425Sdim#include "llvm/Support/raw_ostream.h" 38360784Sdim#include "llvm/Transforms/Utils/Local.h" 39314564Sdim#include <algorithm> 40314564Sdim#include <cassert> 41314564Sdim#include <cstddef> 42314564Sdim#include <cstdint> 43314564Sdim#include <iterator> 44286425Sdim#include <map> 45286425Sdim#include <set> 46314564Sdim#include <utility> 47286425Sdim#include <vector> 48286425Sdim 49360784Sdim#define DEBUG_TYPE "commgep" 50360784Sdim 51286425Sdimusing namespace llvm; 52286425Sdim 53286425Sdimstatic cl::opt<bool> OptSpeculate("commgep-speculate", cl::init(true), 54286425Sdim cl::Hidden, cl::ZeroOrMore); 55286425Sdim 56286425Sdimstatic cl::opt<bool> OptEnableInv("commgep-inv", cl::init(true), cl::Hidden, 57286425Sdim cl::ZeroOrMore); 58286425Sdim 59286425Sdimstatic cl::opt<bool> OptEnableConst("commgep-const", cl::init(true), 60286425Sdim cl::Hidden, cl::ZeroOrMore); 61286425Sdim 62286425Sdimnamespace llvm { 63314564Sdim 64286425Sdim void initializeHexagonCommonGEPPass(PassRegistry&); 65286425Sdim 66314564Sdim} // end namespace llvm 67314564Sdim 68286425Sdimnamespace { 69314564Sdim 70286425Sdim struct GepNode; 71327952Sdim using NodeSet = std::set<GepNode *>; 72327952Sdim using NodeToValueMap = std::map<GepNode *, Value *>; 73327952Sdim using NodeVect = std::vector<GepNode *>; 74327952Sdim using NodeChildrenMap = std::map<GepNode *, NodeVect>; 75353358Sdim using UseSet = SetVector<Use *>; 76327952Sdim using NodeToUsesMap = std::map<GepNode *, UseSet>; 77286425Sdim 78286425Sdim // Numbering map for gep nodes. Used to keep track of ordering for 79286425Sdim // gep nodes. 80296417Sdim struct NodeOrdering { 81314564Sdim NodeOrdering() = default; 82286425Sdim 83296417Sdim void insert(const GepNode *N) { Map.insert(std::make_pair(N, ++LastNum)); } 84296417Sdim void clear() { Map.clear(); } 85296417Sdim 86296417Sdim bool operator()(const GepNode *N1, const GepNode *N2) const { 87296417Sdim auto F1 = Map.find(N1), F2 = Map.find(N2); 88296417Sdim assert(F1 != Map.end() && F2 != Map.end()); 89286425Sdim return F1->second < F2->second; 90286425Sdim } 91296417Sdim 92286425Sdim private: 93296417Sdim std::map<const GepNode *, unsigned> Map; 94314564Sdim unsigned LastNum = 0; 95286425Sdim }; 96286425Sdim 97286425Sdim class HexagonCommonGEP : public FunctionPass { 98286425Sdim public: 99286425Sdim static char ID; 100314564Sdim 101286425Sdim HexagonCommonGEP() : FunctionPass(ID) { 102286425Sdim initializeHexagonCommonGEPPass(*PassRegistry::getPassRegistry()); 103286425Sdim } 104286425Sdim 105314564Sdim bool runOnFunction(Function &F) override; 106314564Sdim StringRef getPassName() const override { return "Hexagon Common GEP"; } 107314564Sdim 108314564Sdim void getAnalysisUsage(AnalysisUsage &AU) const override { 109286425Sdim AU.addRequired<DominatorTreeWrapperPass>(); 110286425Sdim AU.addPreserved<DominatorTreeWrapperPass>(); 111309124Sdim AU.addRequired<PostDominatorTreeWrapperPass>(); 112309124Sdim AU.addPreserved<PostDominatorTreeWrapperPass>(); 113286425Sdim AU.addRequired<LoopInfoWrapperPass>(); 114286425Sdim AU.addPreserved<LoopInfoWrapperPass>(); 115286425Sdim FunctionPass::getAnalysisUsage(AU); 116286425Sdim } 117286425Sdim 118286425Sdim private: 119327952Sdim using ValueToNodeMap = std::map<Value *, GepNode *>; 120327952Sdim using ValueVect = std::vector<Value *>; 121327952Sdim using NodeToValuesMap = std::map<GepNode *, ValueVect>; 122286425Sdim 123286425Sdim void getBlockTraversalOrder(BasicBlock *Root, ValueVect &Order); 124286425Sdim bool isHandledGepForm(GetElementPtrInst *GepI); 125286425Sdim void processGepInst(GetElementPtrInst *GepI, ValueToNodeMap &NM); 126286425Sdim void collect(); 127286425Sdim void common(); 128286425Sdim 129286425Sdim BasicBlock *recalculatePlacement(GepNode *Node, NodeChildrenMap &NCM, 130286425Sdim NodeToValueMap &Loc); 131286425Sdim BasicBlock *recalculatePlacementRec(GepNode *Node, NodeChildrenMap &NCM, 132286425Sdim NodeToValueMap &Loc); 133286425Sdim bool isInvariantIn(Value *Val, Loop *L); 134286425Sdim bool isInvariantIn(GepNode *Node, Loop *L); 135286425Sdim bool isInMainPath(BasicBlock *B, Loop *L); 136286425Sdim BasicBlock *adjustForInvariance(GepNode *Node, NodeChildrenMap &NCM, 137286425Sdim NodeToValueMap &Loc); 138286425Sdim void separateChainForNode(GepNode *Node, Use *U, NodeToValueMap &Loc); 139286425Sdim void separateConstantChains(GepNode *Node, NodeChildrenMap &NCM, 140286425Sdim NodeToValueMap &Loc); 141286425Sdim void computeNodePlacement(NodeToValueMap &Loc); 142286425Sdim 143286425Sdim Value *fabricateGEP(NodeVect &NA, BasicBlock::iterator At, 144286425Sdim BasicBlock *LocB); 145286425Sdim void getAllUsersForNode(GepNode *Node, ValueVect &Values, 146286425Sdim NodeChildrenMap &NCM); 147286425Sdim void materialize(NodeToValueMap &Loc); 148286425Sdim 149286425Sdim void removeDeadCode(); 150286425Sdim 151286425Sdim NodeVect Nodes; 152286425Sdim NodeToUsesMap Uses; 153286425Sdim NodeOrdering NodeOrder; // Node ordering, for deterministic behavior. 154286425Sdim SpecificBumpPtrAllocator<GepNode> *Mem; 155286425Sdim LLVMContext *Ctx; 156286425Sdim LoopInfo *LI; 157286425Sdim DominatorTree *DT; 158286425Sdim PostDominatorTree *PDT; 159286425Sdim Function *Fn; 160286425Sdim }; 161286425Sdim 162314564Sdim} // end anonymous namespace 163286425Sdim 164286425Sdimchar HexagonCommonGEP::ID = 0; 165327952Sdim 166286425SdimINITIALIZE_PASS_BEGIN(HexagonCommonGEP, "hcommgep", "Hexagon Common GEP", 167286425Sdim false, false) 168286425SdimINITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 169309124SdimINITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass) 170286425SdimINITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) 171286425SdimINITIALIZE_PASS_END(HexagonCommonGEP, "hcommgep", "Hexagon Common GEP", 172286425Sdim false, false) 173286425Sdim 174286425Sdimnamespace { 175314564Sdim 176286425Sdim struct GepNode { 177286425Sdim enum { 178286425Sdim None = 0, 179286425Sdim Root = 0x01, 180286425Sdim Internal = 0x02, 181321369Sdim Used = 0x04, 182321369Sdim InBounds = 0x08 183286425Sdim }; 184286425Sdim 185327952Sdim uint32_t Flags = 0; 186286425Sdim union { 187286425Sdim GepNode *Parent; 188286425Sdim Value *BaseVal; 189286425Sdim }; 190327952Sdim Value *Idx = nullptr; 191327952Sdim Type *PTy = nullptr; // Type of the pointer operand. 192286425Sdim 193327952Sdim GepNode() : Parent(nullptr) {} 194286425Sdim GepNode(const GepNode *N) : Flags(N->Flags), Idx(N->Idx), PTy(N->PTy) { 195286425Sdim if (Flags & Root) 196286425Sdim BaseVal = N->BaseVal; 197286425Sdim else 198286425Sdim Parent = N->Parent; 199286425Sdim } 200314564Sdim 201286425Sdim friend raw_ostream &operator<< (raw_ostream &OS, const GepNode &GN); 202286425Sdim }; 203286425Sdim 204286425Sdim Type *next_type(Type *Ty, Value *Idx) { 205314564Sdim if (auto *PTy = dyn_cast<PointerType>(Ty)) 206314564Sdim return PTy->getElementType(); 207286425Sdim // Advance the type. 208286425Sdim if (!Ty->isStructTy()) { 209286425Sdim Type *NexTy = cast<SequentialType>(Ty)->getElementType(); 210286425Sdim return NexTy; 211286425Sdim } 212286425Sdim // Otherwise it is a struct type. 213286425Sdim ConstantInt *CI = dyn_cast<ConstantInt>(Idx); 214286425Sdim assert(CI && "Struct type with non-constant index"); 215286425Sdim int64_t i = CI->getValue().getSExtValue(); 216286425Sdim Type *NextTy = cast<StructType>(Ty)->getElementType(i); 217286425Sdim return NextTy; 218286425Sdim } 219286425Sdim 220286425Sdim raw_ostream &operator<< (raw_ostream &OS, const GepNode &GN) { 221286425Sdim OS << "{ {"; 222286425Sdim bool Comma = false; 223286425Sdim if (GN.Flags & GepNode::Root) { 224286425Sdim OS << "root"; 225286425Sdim Comma = true; 226286425Sdim } 227286425Sdim if (GN.Flags & GepNode::Internal) { 228286425Sdim if (Comma) 229286425Sdim OS << ','; 230286425Sdim OS << "internal"; 231286425Sdim Comma = true; 232286425Sdim } 233286425Sdim if (GN.Flags & GepNode::Used) { 234286425Sdim if (Comma) 235286425Sdim OS << ','; 236286425Sdim OS << "used"; 237286425Sdim } 238321369Sdim if (GN.Flags & GepNode::InBounds) { 239321369Sdim if (Comma) 240321369Sdim OS << ','; 241321369Sdim OS << "inbounds"; 242321369Sdim } 243286425Sdim OS << "} "; 244286425Sdim if (GN.Flags & GepNode::Root) 245286425Sdim OS << "BaseVal:" << GN.BaseVal->getName() << '(' << GN.BaseVal << ')'; 246286425Sdim else 247286425Sdim OS << "Parent:" << GN.Parent; 248286425Sdim 249286425Sdim OS << " Idx:"; 250286425Sdim if (ConstantInt *CI = dyn_cast<ConstantInt>(GN.Idx)) 251286425Sdim OS << CI->getValue().getSExtValue(); 252286425Sdim else if (GN.Idx->hasName()) 253286425Sdim OS << GN.Idx->getName(); 254286425Sdim else 255286425Sdim OS << "<anon> =" << *GN.Idx; 256286425Sdim 257286425Sdim OS << " PTy:"; 258286425Sdim if (GN.PTy->isStructTy()) { 259286425Sdim StructType *STy = cast<StructType>(GN.PTy); 260286425Sdim if (!STy->isLiteral()) 261286425Sdim OS << GN.PTy->getStructName(); 262286425Sdim else 263286425Sdim OS << "<anon-struct>:" << *STy; 264286425Sdim } 265286425Sdim else 266286425Sdim OS << *GN.PTy; 267286425Sdim OS << " }"; 268286425Sdim return OS; 269286425Sdim } 270286425Sdim 271286425Sdim template <typename NodeContainer> 272286425Sdim void dump_node_container(raw_ostream &OS, const NodeContainer &S) { 273327952Sdim using const_iterator = typename NodeContainer::const_iterator; 274327952Sdim 275286425Sdim for (const_iterator I = S.begin(), E = S.end(); I != E; ++I) 276286425Sdim OS << *I << ' ' << **I << '\n'; 277286425Sdim } 278286425Sdim 279286425Sdim raw_ostream &operator<< (raw_ostream &OS, 280286425Sdim const NodeVect &S) LLVM_ATTRIBUTE_UNUSED; 281286425Sdim raw_ostream &operator<< (raw_ostream &OS, const NodeVect &S) { 282286425Sdim dump_node_container(OS, S); 283286425Sdim return OS; 284286425Sdim } 285286425Sdim 286286425Sdim raw_ostream &operator<< (raw_ostream &OS, 287286425Sdim const NodeToUsesMap &M) LLVM_ATTRIBUTE_UNUSED; 288286425Sdim raw_ostream &operator<< (raw_ostream &OS, const NodeToUsesMap &M){ 289327952Sdim using const_iterator = NodeToUsesMap::const_iterator; 290327952Sdim 291286425Sdim for (const_iterator I = M.begin(), E = M.end(); I != E; ++I) { 292286425Sdim const UseSet &Us = I->second; 293286425Sdim OS << I->first << " -> #" << Us.size() << '{'; 294286425Sdim for (UseSet::const_iterator J = Us.begin(), F = Us.end(); J != F; ++J) { 295286425Sdim User *R = (*J)->getUser(); 296286425Sdim if (R->hasName()) 297286425Sdim OS << ' ' << R->getName(); 298286425Sdim else 299286425Sdim OS << " <?>(" << *R << ')'; 300286425Sdim } 301286425Sdim OS << " }\n"; 302286425Sdim } 303286425Sdim return OS; 304286425Sdim } 305286425Sdim 306286425Sdim struct in_set { 307286425Sdim in_set(const NodeSet &S) : NS(S) {} 308327952Sdim 309286425Sdim bool operator() (GepNode *N) const { 310286425Sdim return NS.find(N) != NS.end(); 311286425Sdim } 312314564Sdim 313286425Sdim private: 314286425Sdim const NodeSet &NS; 315286425Sdim }; 316286425Sdim 317314564Sdim} // end anonymous namespace 318286425Sdim 319286425Sdiminline void *operator new(size_t, SpecificBumpPtrAllocator<GepNode> &A) { 320286425Sdim return A.Allocate(); 321286425Sdim} 322286425Sdim 323286425Sdimvoid HexagonCommonGEP::getBlockTraversalOrder(BasicBlock *Root, 324286425Sdim ValueVect &Order) { 325286425Sdim // Compute block ordering for a typical DT-based traversal of the flow 326286425Sdim // graph: "before visiting a block, all of its dominators must have been 327286425Sdim // visited". 328286425Sdim 329286425Sdim Order.push_back(Root); 330321369Sdim for (auto *DTN : children<DomTreeNode*>(DT->getNode(Root))) 331321369Sdim getBlockTraversalOrder(DTN->getBlock(), Order); 332286425Sdim} 333286425Sdim 334286425Sdimbool HexagonCommonGEP::isHandledGepForm(GetElementPtrInst *GepI) { 335286425Sdim // No vector GEPs. 336286425Sdim if (!GepI->getType()->isPointerTy()) 337286425Sdim return false; 338286425Sdim // No GEPs without any indices. (Is this possible?) 339286425Sdim if (GepI->idx_begin() == GepI->idx_end()) 340286425Sdim return false; 341286425Sdim return true; 342286425Sdim} 343286425Sdim 344286425Sdimvoid HexagonCommonGEP::processGepInst(GetElementPtrInst *GepI, 345286425Sdim ValueToNodeMap &NM) { 346341825Sdim LLVM_DEBUG(dbgs() << "Visiting GEP: " << *GepI << '\n'); 347286425Sdim GepNode *N = new (*Mem) GepNode; 348286425Sdim Value *PtrOp = GepI->getPointerOperand(); 349321369Sdim uint32_t InBounds = GepI->isInBounds() ? GepNode::InBounds : 0; 350286425Sdim ValueToNodeMap::iterator F = NM.find(PtrOp); 351286425Sdim if (F == NM.end()) { 352286425Sdim N->BaseVal = PtrOp; 353321369Sdim N->Flags |= GepNode::Root | InBounds; 354286425Sdim } else { 355286425Sdim // If PtrOp was a GEP instruction, it must have already been processed. 356286425Sdim // The ValueToNodeMap entry for it is the last gep node in the generated 357286425Sdim // chain. Link to it here. 358286425Sdim N->Parent = F->second; 359286425Sdim } 360286425Sdim N->PTy = PtrOp->getType(); 361286425Sdim N->Idx = *GepI->idx_begin(); 362286425Sdim 363286425Sdim // Collect the list of users of this GEP instruction. Will add it to the 364286425Sdim // last node created for it. 365286425Sdim UseSet Us; 366286425Sdim for (Value::user_iterator UI = GepI->user_begin(), UE = GepI->user_end(); 367286425Sdim UI != UE; ++UI) { 368286425Sdim // Check if this gep is used by anything other than other geps that 369286425Sdim // we will process. 370286425Sdim if (isa<GetElementPtrInst>(*UI)) { 371286425Sdim GetElementPtrInst *UserG = cast<GetElementPtrInst>(*UI); 372286425Sdim if (isHandledGepForm(UserG)) 373286425Sdim continue; 374286425Sdim } 375286425Sdim Us.insert(&UI.getUse()); 376286425Sdim } 377286425Sdim Nodes.push_back(N); 378286425Sdim NodeOrder.insert(N); 379286425Sdim 380286425Sdim // Skip the first index operand, since we only handle 0. This dereferences 381286425Sdim // the pointer operand. 382286425Sdim GepNode *PN = N; 383286425Sdim Type *PtrTy = cast<PointerType>(PtrOp->getType())->getElementType(); 384286425Sdim for (User::op_iterator OI = GepI->idx_begin()+1, OE = GepI->idx_end(); 385286425Sdim OI != OE; ++OI) { 386286425Sdim Value *Op = *OI; 387286425Sdim GepNode *Nx = new (*Mem) GepNode; 388286425Sdim Nx->Parent = PN; // Link Nx to the previous node. 389321369Sdim Nx->Flags |= GepNode::Internal | InBounds; 390286425Sdim Nx->PTy = PtrTy; 391286425Sdim Nx->Idx = Op; 392286425Sdim Nodes.push_back(Nx); 393286425Sdim NodeOrder.insert(Nx); 394286425Sdim PN = Nx; 395286425Sdim 396286425Sdim PtrTy = next_type(PtrTy, Op); 397286425Sdim } 398286425Sdim 399286425Sdim // After last node has been created, update the use information. 400286425Sdim if (!Us.empty()) { 401286425Sdim PN->Flags |= GepNode::Used; 402286425Sdim Uses[PN].insert(Us.begin(), Us.end()); 403286425Sdim } 404286425Sdim 405286425Sdim // Link the last node with the originating GEP instruction. This is to 406286425Sdim // help with linking chained GEP instructions. 407286425Sdim NM.insert(std::make_pair(GepI, PN)); 408286425Sdim} 409286425Sdim 410286425Sdimvoid HexagonCommonGEP::collect() { 411286425Sdim // Establish depth-first traversal order of the dominator tree. 412286425Sdim ValueVect BO; 413296417Sdim getBlockTraversalOrder(&Fn->front(), BO); 414286425Sdim 415286425Sdim // The creation of gep nodes requires DT-traversal. When processing a GEP 416286425Sdim // instruction that uses another GEP instruction as the base pointer, the 417286425Sdim // gep node for the base pointer should already exist. 418286425Sdim ValueToNodeMap NM; 419286425Sdim for (ValueVect::iterator I = BO.begin(), E = BO.end(); I != E; ++I) { 420286425Sdim BasicBlock *B = cast<BasicBlock>(*I); 421286425Sdim for (BasicBlock::iterator J = B->begin(), F = B->end(); J != F; ++J) { 422286425Sdim if (!isa<GetElementPtrInst>(J)) 423286425Sdim continue; 424286425Sdim GetElementPtrInst *GepI = cast<GetElementPtrInst>(J); 425286425Sdim if (isHandledGepForm(GepI)) 426286425Sdim processGepInst(GepI, NM); 427286425Sdim } 428286425Sdim } 429286425Sdim 430341825Sdim LLVM_DEBUG(dbgs() << "Gep nodes after initial collection:\n" << Nodes); 431286425Sdim} 432286425Sdim 433314564Sdimstatic void invert_find_roots(const NodeVect &Nodes, NodeChildrenMap &NCM, 434314564Sdim NodeVect &Roots) { 435327952Sdim using const_iterator = NodeVect::const_iterator; 436327952Sdim 437286425Sdim for (const_iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) { 438286425Sdim GepNode *N = *I; 439286425Sdim if (N->Flags & GepNode::Root) { 440286425Sdim Roots.push_back(N); 441286425Sdim continue; 442286425Sdim } 443286425Sdim GepNode *PN = N->Parent; 444286425Sdim NCM[PN].push_back(N); 445286425Sdim } 446314564Sdim} 447286425Sdim 448314564Sdimstatic void nodes_for_root(GepNode *Root, NodeChildrenMap &NCM, 449314564Sdim NodeSet &Nodes) { 450286425Sdim NodeVect Work; 451286425Sdim Work.push_back(Root); 452286425Sdim Nodes.insert(Root); 453286425Sdim 454286425Sdim while (!Work.empty()) { 455286425Sdim NodeVect::iterator First = Work.begin(); 456286425Sdim GepNode *N = *First; 457286425Sdim Work.erase(First); 458286425Sdim NodeChildrenMap::iterator CF = NCM.find(N); 459286425Sdim if (CF != NCM.end()) { 460286425Sdim Work.insert(Work.end(), CF->second.begin(), CF->second.end()); 461286425Sdim Nodes.insert(CF->second.begin(), CF->second.end()); 462286425Sdim } 463286425Sdim } 464286425Sdim} 465286425Sdim 466314564Sdimnamespace { 467286425Sdim 468327952Sdim using NodeSymRel = std::set<NodeSet>; 469327952Sdim using NodePair = std::pair<GepNode *, GepNode *>; 470327952Sdim using NodePairSet = std::set<NodePair>; 471286425Sdim 472314564Sdim} // end anonymous namespace 473314564Sdim 474314564Sdimstatic const NodeSet *node_class(GepNode *N, NodeSymRel &Rel) { 475286425Sdim for (NodeSymRel::iterator I = Rel.begin(), E = Rel.end(); I != E; ++I) 476286425Sdim if (I->count(N)) 477286425Sdim return &*I; 478314564Sdim return nullptr; 479314564Sdim} 480286425Sdim 481286425Sdim // Create an ordered pair of GepNode pointers. The pair will be used in 482286425Sdim // determining equality. The only purpose of the ordering is to eliminate 483286425Sdim // duplication due to the commutativity of equality/non-equality. 484314564Sdimstatic NodePair node_pair(GepNode *N1, GepNode *N2) { 485286425Sdim uintptr_t P1 = uintptr_t(N1), P2 = uintptr_t(N2); 486286425Sdim if (P1 <= P2) 487286425Sdim return std::make_pair(N1, N2); 488286425Sdim return std::make_pair(N2, N1); 489314564Sdim} 490286425Sdim 491314564Sdimstatic unsigned node_hash(GepNode *N) { 492286425Sdim // Include everything except flags and parent. 493286425Sdim FoldingSetNodeID ID; 494286425Sdim ID.AddPointer(N->Idx); 495286425Sdim ID.AddPointer(N->PTy); 496286425Sdim return ID.ComputeHash(); 497314564Sdim} 498286425Sdim 499314564Sdimstatic bool node_eq(GepNode *N1, GepNode *N2, NodePairSet &Eq, 500314564Sdim NodePairSet &Ne) { 501286425Sdim // Don't cache the result for nodes with different hashes. The hash 502286425Sdim // comparison is fast enough. 503286425Sdim if (node_hash(N1) != node_hash(N2)) 504286425Sdim return false; 505286425Sdim 506286425Sdim NodePair NP = node_pair(N1, N2); 507286425Sdim NodePairSet::iterator FEq = Eq.find(NP); 508286425Sdim if (FEq != Eq.end()) 509286425Sdim return true; 510286425Sdim NodePairSet::iterator FNe = Ne.find(NP); 511286425Sdim if (FNe != Ne.end()) 512286425Sdim return false; 513286425Sdim // Not previously compared. 514286425Sdim bool Root1 = N1->Flags & GepNode::Root; 515286425Sdim bool Root2 = N2->Flags & GepNode::Root; 516286425Sdim NodePair P = node_pair(N1, N2); 517286425Sdim // If the Root flag has different values, the nodes are different. 518286425Sdim // If both nodes are root nodes, but their base pointers differ, 519286425Sdim // they are different. 520286425Sdim if (Root1 != Root2 || (Root1 && N1->BaseVal != N2->BaseVal)) { 521286425Sdim Ne.insert(P); 522286425Sdim return false; 523286425Sdim } 524286425Sdim // Here the root flags are identical, and for root nodes the 525286425Sdim // base pointers are equal, so the root nodes are equal. 526286425Sdim // For non-root nodes, compare their parent nodes. 527286425Sdim if (Root1 || node_eq(N1->Parent, N2->Parent, Eq, Ne)) { 528286425Sdim Eq.insert(P); 529286425Sdim return true; 530286425Sdim } 531286425Sdim return false; 532286425Sdim} 533286425Sdim 534286425Sdimvoid HexagonCommonGEP::common() { 535286425Sdim // The essence of this commoning is finding gep nodes that are equal. 536286425Sdim // To do this we need to compare all pairs of nodes. To save time, 537286425Sdim // first, partition the set of all nodes into sets of potentially equal 538286425Sdim // nodes, and then compare pairs from within each partition. 539327952Sdim using NodeSetMap = std::map<unsigned, NodeSet>; 540286425Sdim NodeSetMap MaybeEq; 541286425Sdim 542286425Sdim for (NodeVect::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) { 543286425Sdim GepNode *N = *I; 544286425Sdim unsigned H = node_hash(N); 545286425Sdim MaybeEq[H].insert(N); 546286425Sdim } 547286425Sdim 548286425Sdim // Compute the equivalence relation for the gep nodes. Use two caches, 549286425Sdim // one for equality and the other for non-equality. 550286425Sdim NodeSymRel EqRel; // Equality relation (as set of equivalence classes). 551286425Sdim NodePairSet Eq, Ne; // Caches. 552286425Sdim for (NodeSetMap::iterator I = MaybeEq.begin(), E = MaybeEq.end(); 553286425Sdim I != E; ++I) { 554286425Sdim NodeSet &S = I->second; 555286425Sdim for (NodeSet::iterator NI = S.begin(), NE = S.end(); NI != NE; ++NI) { 556286425Sdim GepNode *N = *NI; 557286425Sdim // If node already has a class, then the class must have been created 558286425Sdim // in a prior iteration of this loop. Since equality is transitive, 559286425Sdim // nothing more will be added to that class, so skip it. 560286425Sdim if (node_class(N, EqRel)) 561286425Sdim continue; 562286425Sdim 563286425Sdim // Create a new class candidate now. 564286425Sdim NodeSet C; 565286425Sdim for (NodeSet::iterator NJ = std::next(NI); NJ != NE; ++NJ) 566286425Sdim if (node_eq(N, *NJ, Eq, Ne)) 567286425Sdim C.insert(*NJ); 568286425Sdim // If Tmp is empty, N would be the only element in it. Don't bother 569286425Sdim // creating a class for it then. 570286425Sdim if (!C.empty()) { 571286425Sdim C.insert(N); // Finalize the set before adding it to the relation. 572286425Sdim std::pair<NodeSymRel::iterator, bool> Ins = EqRel.insert(C); 573286425Sdim (void)Ins; 574286425Sdim assert(Ins.second && "Cannot add a class"); 575286425Sdim } 576286425Sdim } 577286425Sdim } 578286425Sdim 579341825Sdim LLVM_DEBUG({ 580286425Sdim dbgs() << "Gep node equality:\n"; 581286425Sdim for (NodePairSet::iterator I = Eq.begin(), E = Eq.end(); I != E; ++I) 582286425Sdim dbgs() << "{ " << I->first << ", " << I->second << " }\n"; 583286425Sdim 584286425Sdim dbgs() << "Gep equivalence classes:\n"; 585286425Sdim for (NodeSymRel::iterator I = EqRel.begin(), E = EqRel.end(); I != E; ++I) { 586286425Sdim dbgs() << '{'; 587286425Sdim const NodeSet &S = *I; 588286425Sdim for (NodeSet::const_iterator J = S.begin(), F = S.end(); J != F; ++J) { 589286425Sdim if (J != S.begin()) 590286425Sdim dbgs() << ','; 591286425Sdim dbgs() << ' ' << *J; 592286425Sdim } 593286425Sdim dbgs() << " }\n"; 594286425Sdim } 595286425Sdim }); 596286425Sdim 597286425Sdim // Create a projection from a NodeSet to the minimal element in it. 598327952Sdim using ProjMap = std::map<const NodeSet *, GepNode *>; 599286425Sdim ProjMap PM; 600286425Sdim for (NodeSymRel::iterator I = EqRel.begin(), E = EqRel.end(); I != E; ++I) { 601286425Sdim const NodeSet &S = *I; 602286425Sdim GepNode *Min = *std::min_element(S.begin(), S.end(), NodeOrder); 603286425Sdim std::pair<ProjMap::iterator,bool> Ins = PM.insert(std::make_pair(&S, Min)); 604286425Sdim (void)Ins; 605286425Sdim assert(Ins.second && "Cannot add minimal element"); 606286425Sdim 607286425Sdim // Update the min element's flags, and user list. 608286425Sdim uint32_t Flags = 0; 609286425Sdim UseSet &MinUs = Uses[Min]; 610286425Sdim for (NodeSet::iterator J = S.begin(), F = S.end(); J != F; ++J) { 611286425Sdim GepNode *N = *J; 612286425Sdim uint32_t NF = N->Flags; 613286425Sdim // If N is used, append all original values of N to the list of 614286425Sdim // original values of Min. 615286425Sdim if (NF & GepNode::Used) 616286425Sdim MinUs.insert(Uses[N].begin(), Uses[N].end()); 617286425Sdim Flags |= NF; 618286425Sdim } 619286425Sdim if (MinUs.empty()) 620286425Sdim Uses.erase(Min); 621286425Sdim 622286425Sdim // The collected flags should include all the flags from the min element. 623286425Sdim assert((Min->Flags & Flags) == Min->Flags); 624286425Sdim Min->Flags = Flags; 625286425Sdim } 626286425Sdim 627286425Sdim // Commoning: for each non-root gep node, replace "Parent" with the 628286425Sdim // selected (minimum) node from the corresponding equivalence class. 629286425Sdim // If a given parent does not have an equivalence class, leave it 630286425Sdim // unchanged (it means that it's the only element in its class). 631286425Sdim for (NodeVect::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) { 632286425Sdim GepNode *N = *I; 633286425Sdim if (N->Flags & GepNode::Root) 634286425Sdim continue; 635286425Sdim const NodeSet *PC = node_class(N->Parent, EqRel); 636286425Sdim if (!PC) 637286425Sdim continue; 638286425Sdim ProjMap::iterator F = PM.find(PC); 639286425Sdim if (F == PM.end()) 640286425Sdim continue; 641286425Sdim // Found a replacement, use it. 642286425Sdim GepNode *Rep = F->second; 643286425Sdim N->Parent = Rep; 644286425Sdim } 645286425Sdim 646341825Sdim LLVM_DEBUG(dbgs() << "Gep nodes after commoning:\n" << Nodes); 647286425Sdim 648286425Sdim // Finally, erase the nodes that are no longer used. 649286425Sdim NodeSet Erase; 650286425Sdim for (NodeVect::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) { 651286425Sdim GepNode *N = *I; 652286425Sdim const NodeSet *PC = node_class(N, EqRel); 653286425Sdim if (!PC) 654286425Sdim continue; 655286425Sdim ProjMap::iterator F = PM.find(PC); 656286425Sdim if (F == PM.end()) 657286425Sdim continue; 658286425Sdim if (N == F->second) 659286425Sdim continue; 660286425Sdim // Node for removal. 661286425Sdim Erase.insert(*I); 662286425Sdim } 663314564Sdim NodeVect::iterator NewE = remove_if(Nodes, in_set(Erase)); 664286425Sdim Nodes.resize(std::distance(Nodes.begin(), NewE)); 665286425Sdim 666341825Sdim LLVM_DEBUG(dbgs() << "Gep nodes after post-commoning cleanup:\n" << Nodes); 667286425Sdim} 668286425Sdim 669314564Sdimtemplate <typename T> 670314564Sdimstatic BasicBlock *nearest_common_dominator(DominatorTree *DT, T &Blocks) { 671341825Sdim LLVM_DEBUG({ 672341825Sdim dbgs() << "NCD of {"; 673341825Sdim for (typename T::iterator I = Blocks.begin(), E = Blocks.end(); I != E; 674341825Sdim ++I) { 675341825Sdim if (!*I) 676341825Sdim continue; 677341825Sdim BasicBlock *B = cast<BasicBlock>(*I); 678341825Sdim dbgs() << ' ' << B->getName(); 679341825Sdim } 680341825Sdim dbgs() << " }\n"; 681341825Sdim }); 682286425Sdim 683341825Sdim // Allow null basic blocks in Blocks. In such cases, return nullptr. 684341825Sdim typename T::iterator I = Blocks.begin(), E = Blocks.end(); 685341825Sdim if (I == E || !*I) 686341825Sdim return nullptr; 687341825Sdim BasicBlock *Dom = cast<BasicBlock>(*I); 688341825Sdim while (++I != E) { 689341825Sdim BasicBlock *B = cast_or_null<BasicBlock>(*I); 690341825Sdim Dom = B ? DT->findNearestCommonDominator(Dom, B) : nullptr; 691341825Sdim if (!Dom) 692314564Sdim return nullptr; 693286425Sdim } 694341825Sdim LLVM_DEBUG(dbgs() << "computed:" << Dom->getName() << '\n'); 695286425Sdim return Dom; 696314564Sdim} 697286425Sdim 698314564Sdimtemplate <typename T> 699314564Sdimstatic BasicBlock *nearest_common_dominatee(DominatorTree *DT, T &Blocks) { 700286425Sdim // If two blocks, A and B, dominate a block C, then A dominates B, 701286425Sdim // or B dominates A. 702286425Sdim typename T::iterator I = Blocks.begin(), E = Blocks.end(); 703286425Sdim // Find the first non-null block. 704286425Sdim while (I != E && !*I) 705286425Sdim ++I; 706286425Sdim if (I == E) 707286425Sdim return DT->getRoot(); 708286425Sdim BasicBlock *DomB = cast<BasicBlock>(*I); 709286425Sdim while (++I != E) { 710286425Sdim if (!*I) 711286425Sdim continue; 712286425Sdim BasicBlock *B = cast<BasicBlock>(*I); 713286425Sdim if (DT->dominates(B, DomB)) 714286425Sdim continue; 715286425Sdim if (!DT->dominates(DomB, B)) 716314564Sdim return nullptr; 717286425Sdim DomB = B; 718286425Sdim } 719286425Sdim return DomB; 720314564Sdim} 721286425Sdim 722314564Sdim// Find the first use in B of any value from Values. If no such use, 723314564Sdim// return B->end(). 724314564Sdimtemplate <typename T> 725314564Sdimstatic BasicBlock::iterator first_use_of_in_block(T &Values, BasicBlock *B) { 726286425Sdim BasicBlock::iterator FirstUse = B->end(), BEnd = B->end(); 727327952Sdim 728327952Sdim using iterator = typename T::iterator; 729327952Sdim 730286425Sdim for (iterator I = Values.begin(), E = Values.end(); I != E; ++I) { 731286425Sdim Value *V = *I; 732286425Sdim // If V is used in a PHI node, the use belongs to the incoming block, 733286425Sdim // not the block with the PHI node. In the incoming block, the use 734286425Sdim // would be considered as being at the end of it, so it cannot 735286425Sdim // influence the position of the first use (which is assumed to be 736286425Sdim // at the end to start with). 737286425Sdim if (isa<PHINode>(V)) 738286425Sdim continue; 739286425Sdim if (!isa<Instruction>(V)) 740286425Sdim continue; 741286425Sdim Instruction *In = cast<Instruction>(V); 742286425Sdim if (In->getParent() != B) 743286425Sdim continue; 744296417Sdim BasicBlock::iterator It = In->getIterator(); 745286425Sdim if (std::distance(FirstUse, BEnd) < std::distance(It, BEnd)) 746286425Sdim FirstUse = It; 747286425Sdim } 748286425Sdim return FirstUse; 749314564Sdim} 750286425Sdim 751314564Sdimstatic bool is_empty(const BasicBlock *B) { 752286425Sdim return B->empty() || (&*B->begin() == B->getTerminator()); 753286425Sdim} 754286425Sdim 755286425SdimBasicBlock *HexagonCommonGEP::recalculatePlacement(GepNode *Node, 756286425Sdim NodeChildrenMap &NCM, NodeToValueMap &Loc) { 757341825Sdim LLVM_DEBUG(dbgs() << "Loc for node:" << Node << '\n'); 758286425Sdim // Recalculate the placement for Node, assuming that the locations of 759286425Sdim // its children in Loc are valid. 760314564Sdim // Return nullptr if there is no valid placement for Node (for example, it 761286425Sdim // uses an index value that is not available at the location required 762286425Sdim // to dominate all children, etc.). 763286425Sdim 764286425Sdim // Find the nearest common dominator for: 765286425Sdim // - all users, if the node is used, and 766286425Sdim // - all children. 767286425Sdim ValueVect Bs; 768286425Sdim if (Node->Flags & GepNode::Used) { 769286425Sdim // Append all blocks with uses of the original values to the 770286425Sdim // block vector Bs. 771286425Sdim NodeToUsesMap::iterator UF = Uses.find(Node); 772286425Sdim assert(UF != Uses.end() && "Used node with no use information"); 773286425Sdim UseSet &Us = UF->second; 774286425Sdim for (UseSet::iterator I = Us.begin(), E = Us.end(); I != E; ++I) { 775286425Sdim Use *U = *I; 776286425Sdim User *R = U->getUser(); 777286425Sdim if (!isa<Instruction>(R)) 778286425Sdim continue; 779286425Sdim BasicBlock *PB = isa<PHINode>(R) 780286425Sdim ? cast<PHINode>(R)->getIncomingBlock(*U) 781286425Sdim : cast<Instruction>(R)->getParent(); 782286425Sdim Bs.push_back(PB); 783286425Sdim } 784286425Sdim } 785286425Sdim // Append the location of each child. 786286425Sdim NodeChildrenMap::iterator CF = NCM.find(Node); 787286425Sdim if (CF != NCM.end()) { 788286425Sdim NodeVect &Cs = CF->second; 789286425Sdim for (NodeVect::iterator I = Cs.begin(), E = Cs.end(); I != E; ++I) { 790286425Sdim GepNode *CN = *I; 791286425Sdim NodeToValueMap::iterator LF = Loc.find(CN); 792286425Sdim // If the child is only used in GEP instructions (i.e. is not used in 793286425Sdim // non-GEP instructions), the nearest dominator computed for it may 794286425Sdim // have been null. In such case it won't have a location available. 795286425Sdim if (LF == Loc.end()) 796286425Sdim continue; 797286425Sdim Bs.push_back(LF->second); 798286425Sdim } 799286425Sdim } 800286425Sdim 801286425Sdim BasicBlock *DomB = nearest_common_dominator(DT, Bs); 802286425Sdim if (!DomB) 803314564Sdim return nullptr; 804286425Sdim // Check if the index used by Node dominates the computed dominator. 805286425Sdim Instruction *IdxI = dyn_cast<Instruction>(Node->Idx); 806286425Sdim if (IdxI && !DT->dominates(IdxI->getParent(), DomB)) 807314564Sdim return nullptr; 808286425Sdim 809286425Sdim // Avoid putting nodes into empty blocks. 810286425Sdim while (is_empty(DomB)) { 811286425Sdim DomTreeNode *N = (*DT)[DomB]->getIDom(); 812286425Sdim if (!N) 813286425Sdim break; 814286425Sdim DomB = N->getBlock(); 815286425Sdim } 816286425Sdim 817286425Sdim // Otherwise, DomB is fine. Update the location map. 818286425Sdim Loc[Node] = DomB; 819286425Sdim return DomB; 820286425Sdim} 821286425Sdim 822286425SdimBasicBlock *HexagonCommonGEP::recalculatePlacementRec(GepNode *Node, 823286425Sdim NodeChildrenMap &NCM, NodeToValueMap &Loc) { 824341825Sdim LLVM_DEBUG(dbgs() << "LocRec begin for node:" << Node << '\n'); 825286425Sdim // Recalculate the placement of Node, after recursively recalculating the 826286425Sdim // placements of all its children. 827286425Sdim NodeChildrenMap::iterator CF = NCM.find(Node); 828286425Sdim if (CF != NCM.end()) { 829286425Sdim NodeVect &Cs = CF->second; 830286425Sdim for (NodeVect::iterator I = Cs.begin(), E = Cs.end(); I != E; ++I) 831286425Sdim recalculatePlacementRec(*I, NCM, Loc); 832286425Sdim } 833286425Sdim BasicBlock *LB = recalculatePlacement(Node, NCM, Loc); 834341825Sdim LLVM_DEBUG(dbgs() << "LocRec end for node:" << Node << '\n'); 835286425Sdim return LB; 836286425Sdim} 837286425Sdim 838286425Sdimbool HexagonCommonGEP::isInvariantIn(Value *Val, Loop *L) { 839286425Sdim if (isa<Constant>(Val) || isa<Argument>(Val)) 840286425Sdim return true; 841286425Sdim Instruction *In = dyn_cast<Instruction>(Val); 842286425Sdim if (!In) 843286425Sdim return false; 844286425Sdim BasicBlock *HdrB = L->getHeader(), *DefB = In->getParent(); 845286425Sdim return DT->properlyDominates(DefB, HdrB); 846286425Sdim} 847286425Sdim 848286425Sdimbool HexagonCommonGEP::isInvariantIn(GepNode *Node, Loop *L) { 849286425Sdim if (Node->Flags & GepNode::Root) 850286425Sdim if (!isInvariantIn(Node->BaseVal, L)) 851286425Sdim return false; 852286425Sdim return isInvariantIn(Node->Idx, L); 853286425Sdim} 854286425Sdim 855286425Sdimbool HexagonCommonGEP::isInMainPath(BasicBlock *B, Loop *L) { 856286425Sdim BasicBlock *HB = L->getHeader(); 857286425Sdim BasicBlock *LB = L->getLoopLatch(); 858286425Sdim // B must post-dominate the loop header or dominate the loop latch. 859286425Sdim if (PDT->dominates(B, HB)) 860286425Sdim return true; 861286425Sdim if (LB && DT->dominates(B, LB)) 862286425Sdim return true; 863286425Sdim return false; 864286425Sdim} 865286425Sdim 866314564Sdimstatic BasicBlock *preheader(DominatorTree *DT, Loop *L) { 867314564Sdim if (BasicBlock *PH = L->getLoopPreheader()) 868314564Sdim return PH; 869314564Sdim if (!OptSpeculate) 870314564Sdim return nullptr; 871314564Sdim DomTreeNode *DN = DT->getNode(L->getHeader()); 872314564Sdim if (!DN) 873314564Sdim return nullptr; 874314564Sdim return DN->getIDom()->getBlock(); 875286425Sdim} 876286425Sdim 877286425SdimBasicBlock *HexagonCommonGEP::adjustForInvariance(GepNode *Node, 878286425Sdim NodeChildrenMap &NCM, NodeToValueMap &Loc) { 879286425Sdim // Find the "topmost" location for Node: it must be dominated by both, 880286425Sdim // its parent (or the BaseVal, if it's a root node), and by the index 881286425Sdim // value. 882286425Sdim ValueVect Bs; 883286425Sdim if (Node->Flags & GepNode::Root) { 884286425Sdim if (Instruction *PIn = dyn_cast<Instruction>(Node->BaseVal)) 885286425Sdim Bs.push_back(PIn->getParent()); 886286425Sdim } else { 887286425Sdim Bs.push_back(Loc[Node->Parent]); 888286425Sdim } 889286425Sdim if (Instruction *IIn = dyn_cast<Instruction>(Node->Idx)) 890286425Sdim Bs.push_back(IIn->getParent()); 891286425Sdim BasicBlock *TopB = nearest_common_dominatee(DT, Bs); 892286425Sdim 893286425Sdim // Traverse the loop nest upwards until we find a loop in which Node 894286425Sdim // is no longer invariant, or until we get to the upper limit of Node's 895286425Sdim // placement. The traversal will also stop when a suitable "preheader" 896286425Sdim // cannot be found for a given loop. The "preheader" may actually be 897286425Sdim // a regular block outside of the loop (i.e. not guarded), in which case 898286425Sdim // the Node will be speculated. 899286425Sdim // For nodes that are not in the main path of the containing loop (i.e. 900286425Sdim // are not executed in each iteration), do not move them out of the loop. 901286425Sdim BasicBlock *LocB = cast_or_null<BasicBlock>(Loc[Node]); 902286425Sdim if (LocB) { 903286425Sdim Loop *Lp = LI->getLoopFor(LocB); 904286425Sdim while (Lp) { 905286425Sdim if (!isInvariantIn(Node, Lp) || !isInMainPath(LocB, Lp)) 906286425Sdim break; 907286425Sdim BasicBlock *NewLoc = preheader(DT, Lp); 908286425Sdim if (!NewLoc || !DT->dominates(TopB, NewLoc)) 909286425Sdim break; 910286425Sdim Lp = Lp->getParentLoop(); 911286425Sdim LocB = NewLoc; 912286425Sdim } 913286425Sdim } 914286425Sdim Loc[Node] = LocB; 915286425Sdim 916286425Sdim // Recursively compute the locations of all children nodes. 917286425Sdim NodeChildrenMap::iterator CF = NCM.find(Node); 918286425Sdim if (CF != NCM.end()) { 919286425Sdim NodeVect &Cs = CF->second; 920286425Sdim for (NodeVect::iterator I = Cs.begin(), E = Cs.end(); I != E; ++I) 921286425Sdim adjustForInvariance(*I, NCM, Loc); 922286425Sdim } 923286425Sdim return LocB; 924286425Sdim} 925286425Sdim 926314564Sdimnamespace { 927286425Sdim 928286425Sdim struct LocationAsBlock { 929286425Sdim LocationAsBlock(const NodeToValueMap &L) : Map(L) {} 930314564Sdim 931286425Sdim const NodeToValueMap ⤅ 932286425Sdim }; 933286425Sdim 934286425Sdim raw_ostream &operator<< (raw_ostream &OS, 935286425Sdim const LocationAsBlock &Loc) LLVM_ATTRIBUTE_UNUSED ; 936286425Sdim raw_ostream &operator<< (raw_ostream &OS, const LocationAsBlock &Loc) { 937286425Sdim for (NodeToValueMap::const_iterator I = Loc.Map.begin(), E = Loc.Map.end(); 938286425Sdim I != E; ++I) { 939286425Sdim OS << I->first << " -> "; 940286425Sdim BasicBlock *B = cast<BasicBlock>(I->second); 941286425Sdim OS << B->getName() << '(' << B << ')'; 942286425Sdim OS << '\n'; 943286425Sdim } 944286425Sdim return OS; 945286425Sdim } 946286425Sdim 947286425Sdim inline bool is_constant(GepNode *N) { 948286425Sdim return isa<ConstantInt>(N->Idx); 949286425Sdim } 950286425Sdim 951314564Sdim} // end anonymous namespace 952286425Sdim 953286425Sdimvoid HexagonCommonGEP::separateChainForNode(GepNode *Node, Use *U, 954286425Sdim NodeToValueMap &Loc) { 955286425Sdim User *R = U->getUser(); 956341825Sdim LLVM_DEBUG(dbgs() << "Separating chain for node (" << Node << ") user: " << *R 957341825Sdim << '\n'); 958286425Sdim BasicBlock *PB = cast<Instruction>(R)->getParent(); 959286425Sdim 960286425Sdim GepNode *N = Node; 961314564Sdim GepNode *C = nullptr, *NewNode = nullptr; 962286425Sdim while (is_constant(N) && !(N->Flags & GepNode::Root)) { 963286425Sdim // XXX if (single-use) dont-replicate; 964286425Sdim GepNode *NewN = new (*Mem) GepNode(N); 965286425Sdim Nodes.push_back(NewN); 966286425Sdim Loc[NewN] = PB; 967286425Sdim 968286425Sdim if (N == Node) 969286425Sdim NewNode = NewN; 970286425Sdim NewN->Flags &= ~GepNode::Used; 971286425Sdim if (C) 972286425Sdim C->Parent = NewN; 973286425Sdim C = NewN; 974286425Sdim N = N->Parent; 975286425Sdim } 976286425Sdim if (!NewNode) 977286425Sdim return; 978286425Sdim 979286425Sdim // Move over all uses that share the same user as U from Node to NewNode. 980286425Sdim NodeToUsesMap::iterator UF = Uses.find(Node); 981286425Sdim assert(UF != Uses.end()); 982286425Sdim UseSet &Us = UF->second; 983286425Sdim UseSet NewUs; 984353358Sdim for (Use *U : Us) { 985353358Sdim if (U->getUser() == R) 986353358Sdim NewUs.insert(U); 987286425Sdim } 988353358Sdim for (Use *U : NewUs) 989353358Sdim Us.remove(U); // erase takes an iterator. 990353358Sdim 991286425Sdim if (Us.empty()) { 992286425Sdim Node->Flags &= ~GepNode::Used; 993286425Sdim Uses.erase(UF); 994286425Sdim } 995286425Sdim 996286425Sdim // Should at least have U in NewUs. 997286425Sdim NewNode->Flags |= GepNode::Used; 998341825Sdim LLVM_DEBUG(dbgs() << "new node: " << NewNode << " " << *NewNode << '\n'); 999286425Sdim assert(!NewUs.empty()); 1000286425Sdim Uses[NewNode] = NewUs; 1001286425Sdim} 1002286425Sdim 1003286425Sdimvoid HexagonCommonGEP::separateConstantChains(GepNode *Node, 1004286425Sdim NodeChildrenMap &NCM, NodeToValueMap &Loc) { 1005286425Sdim // First approximation: extract all chains. 1006286425Sdim NodeSet Ns; 1007286425Sdim nodes_for_root(Node, NCM, Ns); 1008286425Sdim 1009341825Sdim LLVM_DEBUG(dbgs() << "Separating constant chains for node: " << Node << '\n'); 1010286425Sdim // Collect all used nodes together with the uses from loads and stores, 1011286425Sdim // where the GEP node could be folded into the load/store instruction. 1012286425Sdim NodeToUsesMap FNs; // Foldable nodes. 1013286425Sdim for (NodeSet::iterator I = Ns.begin(), E = Ns.end(); I != E; ++I) { 1014286425Sdim GepNode *N = *I; 1015286425Sdim if (!(N->Flags & GepNode::Used)) 1016286425Sdim continue; 1017286425Sdim NodeToUsesMap::iterator UF = Uses.find(N); 1018286425Sdim assert(UF != Uses.end()); 1019286425Sdim UseSet &Us = UF->second; 1020286425Sdim // Loads/stores that use the node N. 1021286425Sdim UseSet LSs; 1022286425Sdim for (UseSet::iterator J = Us.begin(), F = Us.end(); J != F; ++J) { 1023286425Sdim Use *U = *J; 1024286425Sdim User *R = U->getUser(); 1025286425Sdim // We're interested in uses that provide the address. It can happen 1026286425Sdim // that the value may also be provided via GEP, but we won't handle 1027286425Sdim // those cases here for now. 1028286425Sdim if (LoadInst *Ld = dyn_cast<LoadInst>(R)) { 1029286425Sdim unsigned PtrX = LoadInst::getPointerOperandIndex(); 1030286425Sdim if (&Ld->getOperandUse(PtrX) == U) 1031286425Sdim LSs.insert(U); 1032286425Sdim } else if (StoreInst *St = dyn_cast<StoreInst>(R)) { 1033286425Sdim unsigned PtrX = StoreInst::getPointerOperandIndex(); 1034286425Sdim if (&St->getOperandUse(PtrX) == U) 1035286425Sdim LSs.insert(U); 1036286425Sdim } 1037286425Sdim } 1038286425Sdim // Even if the total use count is 1, separating the chain may still be 1039286425Sdim // beneficial, since the constant chain may be longer than the GEP alone 1040286425Sdim // would be (e.g. if the parent node has a constant index and also has 1041286425Sdim // other children). 1042286425Sdim if (!LSs.empty()) 1043286425Sdim FNs.insert(std::make_pair(N, LSs)); 1044286425Sdim } 1045286425Sdim 1046341825Sdim LLVM_DEBUG(dbgs() << "Nodes with foldable users:\n" << FNs); 1047286425Sdim 1048286425Sdim for (NodeToUsesMap::iterator I = FNs.begin(), E = FNs.end(); I != E; ++I) { 1049286425Sdim GepNode *N = I->first; 1050286425Sdim UseSet &Us = I->second; 1051286425Sdim for (UseSet::iterator J = Us.begin(), F = Us.end(); J != F; ++J) 1052286425Sdim separateChainForNode(N, *J, Loc); 1053286425Sdim } 1054286425Sdim} 1055286425Sdim 1056286425Sdimvoid HexagonCommonGEP::computeNodePlacement(NodeToValueMap &Loc) { 1057286425Sdim // Compute the inverse of the Node.Parent links. Also, collect the set 1058286425Sdim // of root nodes. 1059286425Sdim NodeChildrenMap NCM; 1060286425Sdim NodeVect Roots; 1061286425Sdim invert_find_roots(Nodes, NCM, Roots); 1062286425Sdim 1063286425Sdim // Compute the initial placement determined by the users' locations, and 1064286425Sdim // the locations of the child nodes. 1065286425Sdim for (NodeVect::iterator I = Roots.begin(), E = Roots.end(); I != E; ++I) 1066286425Sdim recalculatePlacementRec(*I, NCM, Loc); 1067286425Sdim 1068341825Sdim LLVM_DEBUG(dbgs() << "Initial node placement:\n" << LocationAsBlock(Loc)); 1069286425Sdim 1070286425Sdim if (OptEnableInv) { 1071286425Sdim for (NodeVect::iterator I = Roots.begin(), E = Roots.end(); I != E; ++I) 1072286425Sdim adjustForInvariance(*I, NCM, Loc); 1073286425Sdim 1074341825Sdim LLVM_DEBUG(dbgs() << "Node placement after adjustment for invariance:\n" 1075341825Sdim << LocationAsBlock(Loc)); 1076286425Sdim } 1077286425Sdim if (OptEnableConst) { 1078286425Sdim for (NodeVect::iterator I = Roots.begin(), E = Roots.end(); I != E; ++I) 1079286425Sdim separateConstantChains(*I, NCM, Loc); 1080286425Sdim } 1081341825Sdim LLVM_DEBUG(dbgs() << "Node use information:\n" << Uses); 1082286425Sdim 1083286425Sdim // At the moment, there is no further refinement of the initial placement. 1084286425Sdim // Such a refinement could include splitting the nodes if they are placed 1085286425Sdim // too far from some of its users. 1086286425Sdim 1087341825Sdim LLVM_DEBUG(dbgs() << "Final node placement:\n" << LocationAsBlock(Loc)); 1088286425Sdim} 1089286425Sdim 1090286425SdimValue *HexagonCommonGEP::fabricateGEP(NodeVect &NA, BasicBlock::iterator At, 1091286425Sdim BasicBlock *LocB) { 1092341825Sdim LLVM_DEBUG(dbgs() << "Fabricating GEP in " << LocB->getName() 1093341825Sdim << " for nodes:\n" 1094341825Sdim << NA); 1095286425Sdim unsigned Num = NA.size(); 1096286425Sdim GepNode *RN = NA[0]; 1097286425Sdim assert((RN->Flags & GepNode::Root) && "Creating GEP for non-root"); 1098286425Sdim 1099321369Sdim GetElementPtrInst *NewInst = nullptr; 1100286425Sdim Value *Input = RN->BaseVal; 1101286425Sdim Value **IdxList = new Value*[Num+1]; 1102286425Sdim unsigned nax = 0; 1103286425Sdim do { 1104286425Sdim unsigned IdxC = 0; 1105286425Sdim // If the type of the input of the first node is not a pointer, 1106286425Sdim // we need to add an artificial i32 0 to the indices (because the 1107286425Sdim // actual input in the IR will be a pointer). 1108286425Sdim if (!NA[nax]->PTy->isPointerTy()) { 1109286425Sdim Type *Int32Ty = Type::getInt32Ty(*Ctx); 1110286425Sdim IdxList[IdxC++] = ConstantInt::get(Int32Ty, 0); 1111286425Sdim } 1112286425Sdim 1113286425Sdim // Keep adding indices from NA until we have to stop and generate 1114286425Sdim // an "intermediate" GEP. 1115286425Sdim while (++nax <= Num) { 1116286425Sdim GepNode *N = NA[nax-1]; 1117286425Sdim IdxList[IdxC++] = N->Idx; 1118286425Sdim if (nax < Num) { 1119286425Sdim // We have to stop, if the expected type of the output of this node 1120286425Sdim // is not the same as the input type of the next node. 1121286425Sdim Type *NextTy = next_type(N->PTy, N->Idx); 1122286425Sdim if (NextTy != NA[nax]->PTy) 1123286425Sdim break; 1124286425Sdim } 1125286425Sdim } 1126286425Sdim ArrayRef<Value*> A(IdxList, IdxC); 1127286425Sdim Type *InpTy = Input->getType(); 1128286425Sdim Type *ElTy = cast<PointerType>(InpTy->getScalarType())->getElementType(); 1129296417Sdim NewInst = GetElementPtrInst::Create(ElTy, Input, A, "cgep", &*At); 1130321369Sdim NewInst->setIsInBounds(RN->Flags & GepNode::InBounds); 1131341825Sdim LLVM_DEBUG(dbgs() << "new GEP: " << *NewInst << '\n'); 1132286425Sdim Input = NewInst; 1133286425Sdim } while (nax <= Num); 1134286425Sdim 1135286425Sdim delete[] IdxList; 1136286425Sdim return NewInst; 1137286425Sdim} 1138286425Sdim 1139286425Sdimvoid HexagonCommonGEP::getAllUsersForNode(GepNode *Node, ValueVect &Values, 1140286425Sdim NodeChildrenMap &NCM) { 1141286425Sdim NodeVect Work; 1142286425Sdim Work.push_back(Node); 1143286425Sdim 1144286425Sdim while (!Work.empty()) { 1145286425Sdim NodeVect::iterator First = Work.begin(); 1146286425Sdim GepNode *N = *First; 1147286425Sdim Work.erase(First); 1148286425Sdim if (N->Flags & GepNode::Used) { 1149286425Sdim NodeToUsesMap::iterator UF = Uses.find(N); 1150286425Sdim assert(UF != Uses.end() && "No use information for used node"); 1151286425Sdim UseSet &Us = UF->second; 1152286425Sdim for (UseSet::iterator I = Us.begin(), E = Us.end(); I != E; ++I) 1153286425Sdim Values.push_back((*I)->getUser()); 1154286425Sdim } 1155286425Sdim NodeChildrenMap::iterator CF = NCM.find(N); 1156286425Sdim if (CF != NCM.end()) { 1157286425Sdim NodeVect &Cs = CF->second; 1158286425Sdim Work.insert(Work.end(), Cs.begin(), Cs.end()); 1159286425Sdim } 1160286425Sdim } 1161286425Sdim} 1162286425Sdim 1163286425Sdimvoid HexagonCommonGEP::materialize(NodeToValueMap &Loc) { 1164341825Sdim LLVM_DEBUG(dbgs() << "Nodes before materialization:\n" << Nodes << '\n'); 1165286425Sdim NodeChildrenMap NCM; 1166286425Sdim NodeVect Roots; 1167286425Sdim // Compute the inversion again, since computing placement could alter 1168286425Sdim // "parent" relation between nodes. 1169286425Sdim invert_find_roots(Nodes, NCM, Roots); 1170286425Sdim 1171286425Sdim while (!Roots.empty()) { 1172286425Sdim NodeVect::iterator First = Roots.begin(); 1173286425Sdim GepNode *Root = *First, *Last = *First; 1174286425Sdim Roots.erase(First); 1175286425Sdim 1176286425Sdim NodeVect NA; // Nodes to assemble. 1177286425Sdim // Append to NA all child nodes up to (and including) the first child 1178286425Sdim // that: 1179286425Sdim // (1) has more than 1 child, or 1180286425Sdim // (2) is used, or 1181286425Sdim // (3) has a child located in a different block. 1182286425Sdim bool LastUsed = false; 1183286425Sdim unsigned LastCN = 0; 1184286425Sdim // The location may be null if the computation failed (it can legitimately 1185286425Sdim // happen for nodes created from dead GEPs). 1186286425Sdim Value *LocV = Loc[Last]; 1187286425Sdim if (!LocV) 1188286425Sdim continue; 1189286425Sdim BasicBlock *LastB = cast<BasicBlock>(LocV); 1190286425Sdim do { 1191286425Sdim NA.push_back(Last); 1192286425Sdim LastUsed = (Last->Flags & GepNode::Used); 1193286425Sdim if (LastUsed) 1194286425Sdim break; 1195286425Sdim NodeChildrenMap::iterator CF = NCM.find(Last); 1196286425Sdim LastCN = (CF != NCM.end()) ? CF->second.size() : 0; 1197286425Sdim if (LastCN != 1) 1198286425Sdim break; 1199286425Sdim GepNode *Child = CF->second.front(); 1200286425Sdim BasicBlock *ChildB = cast_or_null<BasicBlock>(Loc[Child]); 1201314564Sdim if (ChildB != nullptr && LastB != ChildB) 1202286425Sdim break; 1203286425Sdim Last = Child; 1204286425Sdim } while (true); 1205286425Sdim 1206296417Sdim BasicBlock::iterator InsertAt = LastB->getTerminator()->getIterator(); 1207286425Sdim if (LastUsed || LastCN > 0) { 1208286425Sdim ValueVect Urs; 1209286425Sdim getAllUsersForNode(Root, Urs, NCM); 1210286425Sdim BasicBlock::iterator FirstUse = first_use_of_in_block(Urs, LastB); 1211286425Sdim if (FirstUse != LastB->end()) 1212286425Sdim InsertAt = FirstUse; 1213286425Sdim } 1214286425Sdim 1215286425Sdim // Generate a new instruction for NA. 1216286425Sdim Value *NewInst = fabricateGEP(NA, InsertAt, LastB); 1217286425Sdim 1218286425Sdim // Convert all the children of Last node into roots, and append them 1219286425Sdim // to the Roots list. 1220286425Sdim if (LastCN > 0) { 1221286425Sdim NodeVect &Cs = NCM[Last]; 1222286425Sdim for (NodeVect::iterator I = Cs.begin(), E = Cs.end(); I != E; ++I) { 1223286425Sdim GepNode *CN = *I; 1224286425Sdim CN->Flags &= ~GepNode::Internal; 1225286425Sdim CN->Flags |= GepNode::Root; 1226286425Sdim CN->BaseVal = NewInst; 1227286425Sdim Roots.push_back(CN); 1228286425Sdim } 1229286425Sdim } 1230286425Sdim 1231286425Sdim // Lastly, if the Last node was used, replace all uses with the new GEP. 1232286425Sdim // The uses reference the original GEP values. 1233286425Sdim if (LastUsed) { 1234286425Sdim NodeToUsesMap::iterator UF = Uses.find(Last); 1235286425Sdim assert(UF != Uses.end() && "No use information found"); 1236286425Sdim UseSet &Us = UF->second; 1237286425Sdim for (UseSet::iterator I = Us.begin(), E = Us.end(); I != E; ++I) { 1238286425Sdim Use *U = *I; 1239286425Sdim U->set(NewInst); 1240286425Sdim } 1241286425Sdim } 1242286425Sdim } 1243286425Sdim} 1244286425Sdim 1245286425Sdimvoid HexagonCommonGEP::removeDeadCode() { 1246286425Sdim ValueVect BO; 1247286425Sdim BO.push_back(&Fn->front()); 1248286425Sdim 1249286425Sdim for (unsigned i = 0; i < BO.size(); ++i) { 1250286425Sdim BasicBlock *B = cast<BasicBlock>(BO[i]); 1251321369Sdim for (auto DTN : children<DomTreeNode*>(DT->getNode(B))) 1252321369Sdim BO.push_back(DTN->getBlock()); 1253286425Sdim } 1254286425Sdim 1255286425Sdim for (unsigned i = BO.size(); i > 0; --i) { 1256286425Sdim BasicBlock *B = cast<BasicBlock>(BO[i-1]); 1257286425Sdim BasicBlock::InstListType &IL = B->getInstList(); 1258327952Sdim 1259327952Sdim using reverse_iterator = BasicBlock::InstListType::reverse_iterator; 1260327952Sdim 1261286425Sdim ValueVect Ins; 1262286425Sdim for (reverse_iterator I = IL.rbegin(), E = IL.rend(); I != E; ++I) 1263286425Sdim Ins.push_back(&*I); 1264286425Sdim for (ValueVect::iterator I = Ins.begin(), E = Ins.end(); I != E; ++I) { 1265286425Sdim Instruction *In = cast<Instruction>(*I); 1266286425Sdim if (isInstructionTriviallyDead(In)) 1267286425Sdim In->eraseFromParent(); 1268286425Sdim } 1269286425Sdim } 1270286425Sdim} 1271286425Sdim 1272286425Sdimbool HexagonCommonGEP::runOnFunction(Function &F) { 1273309124Sdim if (skipFunction(F)) 1274309124Sdim return false; 1275309124Sdim 1276286425Sdim // For now bail out on C++ exception handling. 1277286425Sdim for (Function::iterator A = F.begin(), Z = F.end(); A != Z; ++A) 1278286425Sdim for (BasicBlock::iterator I = A->begin(), E = A->end(); I != E; ++I) 1279286425Sdim if (isa<InvokeInst>(I) || isa<LandingPadInst>(I)) 1280286425Sdim return false; 1281286425Sdim 1282286425Sdim Fn = &F; 1283286425Sdim DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 1284309124Sdim PDT = &getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree(); 1285286425Sdim LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 1286286425Sdim Ctx = &F.getContext(); 1287286425Sdim 1288286425Sdim Nodes.clear(); 1289286425Sdim Uses.clear(); 1290286425Sdim NodeOrder.clear(); 1291286425Sdim 1292286425Sdim SpecificBumpPtrAllocator<GepNode> Allocator; 1293286425Sdim Mem = &Allocator; 1294286425Sdim 1295286425Sdim collect(); 1296286425Sdim common(); 1297286425Sdim 1298286425Sdim NodeToValueMap Loc; 1299286425Sdim computeNodePlacement(Loc); 1300286425Sdim materialize(Loc); 1301286425Sdim removeDeadCode(); 1302286425Sdim 1303309124Sdim#ifdef EXPENSIVE_CHECKS 1304286425Sdim // Run this only when expensive checks are enabled. 1305286425Sdim verifyFunction(F); 1306286425Sdim#endif 1307286425Sdim return true; 1308286425Sdim} 1309286425Sdim 1310314564Sdimnamespace llvm { 1311286425Sdim 1312286425Sdim FunctionPass *createHexagonCommonGEP() { 1313286425Sdim return new HexagonCommonGEP(); 1314286425Sdim } 1315314564Sdim 1316314564Sdim} // end namespace llvm 1317