From a307401165e96b8a476df26440de9769e78e9102 Mon Sep 17 00:00:00 2001 From: Krzysztof Parzyszek Date: Wed, 8 Jul 2015 19:22:28 +0000 Subject: [PATCH] [Hexagon] Implement commoning of GetElementPtr instructions git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@241714 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Target/Hexagon/CMakeLists.txt | 1 + lib/Target/Hexagon/HexagonCommonGEP.cpp | 1325 +++++++++++++++++++ lib/Target/Hexagon/HexagonTargetMachine.cpp | 14 + test/CodeGen/Hexagon/common-gep-basic.ll | 37 + test/CodeGen/Hexagon/common-gep-icm.ll | 76 ++ 5 files changed, 1453 insertions(+) create mode 100644 lib/Target/Hexagon/HexagonCommonGEP.cpp create mode 100644 test/CodeGen/Hexagon/common-gep-basic.ll create mode 100644 test/CodeGen/Hexagon/common-gep-icm.ll diff --git a/lib/Target/Hexagon/CMakeLists.txt b/lib/Target/Hexagon/CMakeLists.txt index 20fa64f054d..6a5f5f93026 100644 --- a/lib/Target/Hexagon/CMakeLists.txt +++ b/lib/Target/Hexagon/CMakeLists.txt @@ -16,6 +16,7 @@ add_llvm_target(HexagonCodeGen HexagonAsmPrinter.cpp HexagonBitTracker.cpp HexagonCFGOptimizer.cpp + HexagonCommonGEP.cpp HexagonCopyToCombine.cpp HexagonExpandCondsets.cpp HexagonExpandPredSpillCode.cpp diff --git a/lib/Target/Hexagon/HexagonCommonGEP.cpp b/lib/Target/Hexagon/HexagonCommonGEP.cpp new file mode 100644 index 00000000000..9f5fac15652 --- /dev/null +++ b/lib/Target/Hexagon/HexagonCommonGEP.cpp @@ -0,0 +1,1325 @@ +//===--- HexagonCommonGEP.cpp ---------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "commgep" + +#include "llvm/Pass.h" +#include "llvm/ADT/FoldingSet.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/PostDominators.h" +#include "llvm/CodeGen/MachineFunctionAnalysis.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/Verifier.h" +#include "llvm/Support/Allocator.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Utils/Local.h" + +#include +#include +#include + +#include "HexagonTargetMachine.h" + +using namespace llvm; + +static cl::opt OptSpeculate("commgep-speculate", cl::init(true), + cl::Hidden, cl::ZeroOrMore); + +static cl::opt OptEnableInv("commgep-inv", cl::init(true), cl::Hidden, + cl::ZeroOrMore); + +static cl::opt OptEnableConst("commgep-const", cl::init(true), + cl::Hidden, cl::ZeroOrMore); + +namespace llvm { + void initializeHexagonCommonGEPPass(PassRegistry&); +} + +namespace { + struct GepNode; + typedef std::set NodeSet; + typedef std::map NodeToValueMap; + typedef std::vector NodeVect; + typedef std::map NodeChildrenMap; + typedef std::set UseSet; + typedef std::map NodeToUsesMap; + + // Numbering map for gep nodes. Used to keep track of ordering for + // gep nodes. + struct NodeNumbering : public std::map { + }; + + struct NodeOrdering : public NodeNumbering { + NodeOrdering() : LastNum(0) {} +#ifdef _MSC_VER + void special_insert_for_special_msvc(const GepNode *N) +#else + using NodeNumbering::insert; + void insert(const GepNode* N) +#endif + { + insert(std::make_pair(N, ++LastNum)); + } + bool operator() (const GepNode* N1, const GepNode *N2) const { + const_iterator F1 = find(N1), F2 = find(N2); + assert(F1 != end() && F2 != end()); + return F1->second < F2->second; + } + private: + unsigned LastNum; + }; + + + class HexagonCommonGEP : public FunctionPass { + public: + static char ID; + HexagonCommonGEP() : FunctionPass(ID) { + initializeHexagonCommonGEPPass(*PassRegistry::getPassRegistry()); + } + virtual bool runOnFunction(Function &F); + virtual const char *getPassName() const { + return "Hexagon Common GEP"; + } + + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequired(); + AU.addPreserved(); + AU.addRequired(); + AU.addPreserved(); + AU.addRequired(); + AU.addPreserved(); + FunctionPass::getAnalysisUsage(AU); + } + + private: + typedef std::map ValueToNodeMap; + typedef std::vector ValueVect; + typedef std::map NodeToValuesMap; + + void getBlockTraversalOrder(BasicBlock *Root, ValueVect &Order); + bool isHandledGepForm(GetElementPtrInst *GepI); + void processGepInst(GetElementPtrInst *GepI, ValueToNodeMap &NM); + void collect(); + void common(); + + BasicBlock *recalculatePlacement(GepNode *Node, NodeChildrenMap &NCM, + NodeToValueMap &Loc); + BasicBlock *recalculatePlacementRec(GepNode *Node, NodeChildrenMap &NCM, + NodeToValueMap &Loc); + bool isInvariantIn(Value *Val, Loop *L); + bool isInvariantIn(GepNode *Node, Loop *L); + bool isInMainPath(BasicBlock *B, Loop *L); + BasicBlock *adjustForInvariance(GepNode *Node, NodeChildrenMap &NCM, + NodeToValueMap &Loc); + void separateChainForNode(GepNode *Node, Use *U, NodeToValueMap &Loc); + void separateConstantChains(GepNode *Node, NodeChildrenMap &NCM, + NodeToValueMap &Loc); + void computeNodePlacement(NodeToValueMap &Loc); + + Value *fabricateGEP(NodeVect &NA, BasicBlock::iterator At, + BasicBlock *LocB); + void getAllUsersForNode(GepNode *Node, ValueVect &Values, + NodeChildrenMap &NCM); + void materialize(NodeToValueMap &Loc); + + void removeDeadCode(); + + NodeVect Nodes; + NodeToUsesMap Uses; + NodeOrdering NodeOrder; // Node ordering, for deterministic behavior. + SpecificBumpPtrAllocator *Mem; + LLVMContext *Ctx; + LoopInfo *LI; + DominatorTree *DT; + PostDominatorTree *PDT; + Function *Fn; + }; +} + + +char HexagonCommonGEP::ID = 0; +INITIALIZE_PASS_BEGIN(HexagonCommonGEP, "hcommgep", "Hexagon Common GEP", + false, false) +INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) +INITIALIZE_PASS_DEPENDENCY(PostDominatorTree) +INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) +INITIALIZE_PASS_END(HexagonCommonGEP, "hcommgep", "Hexagon Common GEP", + false, false) + +namespace { + struct GepNode { + enum { + None = 0, + Root = 0x01, + Internal = 0x02, + Used = 0x04 + }; + + uint32_t Flags; + union { + GepNode *Parent; + Value *BaseVal; + }; + Value *Idx; + Type *PTy; // Type of the pointer operand. + + GepNode() : Flags(0), Parent(0), Idx(0), PTy(0) {} + GepNode(const GepNode *N) : Flags(N->Flags), Idx(N->Idx), PTy(N->PTy) { + if (Flags & Root) + BaseVal = N->BaseVal; + else + Parent = N->Parent; + } + friend raw_ostream &operator<< (raw_ostream &OS, const GepNode &GN); + }; + + + Type *next_type(Type *Ty, Value *Idx) { + // Advance the type. + if (!Ty->isStructTy()) { + Type *NexTy = cast(Ty)->getElementType(); + return NexTy; + } + // Otherwise it is a struct type. + ConstantInt *CI = dyn_cast(Idx); + assert(CI && "Struct type with non-constant index"); + int64_t i = CI->getValue().getSExtValue(); + Type *NextTy = cast(Ty)->getElementType(i); + return NextTy; + } + + + raw_ostream &operator<< (raw_ostream &OS, const GepNode &GN) { + OS << "{ {"; + bool Comma = false; + if (GN.Flags & GepNode::Root) { + OS << "root"; + Comma = true; + } + if (GN.Flags & GepNode::Internal) { + if (Comma) + OS << ','; + OS << "internal"; + Comma = true; + } + if (GN.Flags & GepNode::Used) { + if (Comma) + OS << ','; + OS << "used"; + Comma = true; + } + OS << "} "; + if (GN.Flags & GepNode::Root) + OS << "BaseVal:" << GN.BaseVal->getName() << '(' << GN.BaseVal << ')'; + else + OS << "Parent:" << GN.Parent; + + OS << " Idx:"; + if (ConstantInt *CI = dyn_cast(GN.Idx)) + OS << CI->getValue().getSExtValue(); + else if (GN.Idx->hasName()) + OS << GN.Idx->getName(); + else + OS << " =" << *GN.Idx; + + OS << " PTy:"; + if (GN.PTy->isStructTy()) { + StructType *STy = cast(GN.PTy); + if (!STy->isLiteral()) + OS << GN.PTy->getStructName(); + else + OS << ":" << *STy; + } + else + OS << *GN.PTy; + OS << " }"; + return OS; + } + + + template + void dump_node_container(raw_ostream &OS, const NodeContainer &S) { + typedef typename NodeContainer::const_iterator const_iterator; + for (const_iterator I = S.begin(), E = S.end(); I != E; ++I) + OS << *I << ' ' << **I << '\n'; + } + + raw_ostream &operator<< (raw_ostream &OS, + const NodeVect &S) LLVM_ATTRIBUTE_UNUSED; + raw_ostream &operator<< (raw_ostream &OS, const NodeVect &S) { + dump_node_container(OS, S); + return OS; + } + + + raw_ostream &operator<< (raw_ostream &OS, + const NodeToUsesMap &M) LLVM_ATTRIBUTE_UNUSED; + raw_ostream &operator<< (raw_ostream &OS, const NodeToUsesMap &M){ + typedef NodeToUsesMap::const_iterator const_iterator; + for (const_iterator I = M.begin(), E = M.end(); I != E; ++I) { + const UseSet &Us = I->second; + OS << I->first << " -> #" << Us.size() << '{'; + for (UseSet::const_iterator J = Us.begin(), F = Us.end(); J != F; ++J) { + User *R = (*J)->getUser(); + if (R->hasName()) + OS << ' ' << R->getName(); + else + OS << " (" << *R << ')'; + } + OS << " }\n"; + } + return OS; + } + + + struct in_set { + in_set(const NodeSet &S) : NS(S) {} + bool operator() (GepNode *N) const { + return NS.find(N) != NS.end(); + } + private: + const NodeSet &NS; + }; +} + + +inline void *operator new(size_t, SpecificBumpPtrAllocator &A) { + return A.Allocate(); +} + + +void HexagonCommonGEP::getBlockTraversalOrder(BasicBlock *Root, + ValueVect &Order) { + // Compute block ordering for a typical DT-based traversal of the flow + // graph: "before visiting a block, all of its dominators must have been + // visited". + + Order.push_back(Root); + DomTreeNode *DTN = DT->getNode(Root); + typedef GraphTraits GTN; + typedef GTN::ChildIteratorType Iter; + for (Iter I = GTN::child_begin(DTN), E = GTN::child_end(DTN); I != E; ++I) + getBlockTraversalOrder((*I)->getBlock(), Order); +} + + +bool HexagonCommonGEP::isHandledGepForm(GetElementPtrInst *GepI) { + // No vector GEPs. + if (!GepI->getType()->isPointerTy()) + return false; + // No GEPs without any indices. (Is this possible?) + if (GepI->idx_begin() == GepI->idx_end()) + return false; + return true; +} + + +void HexagonCommonGEP::processGepInst(GetElementPtrInst *GepI, + ValueToNodeMap &NM) { + DEBUG(dbgs() << "Visiting GEP: " << *GepI << '\n'); + GepNode *N = new (*Mem) GepNode; + Value *PtrOp = GepI->getPointerOperand(); + ValueToNodeMap::iterator F = NM.find(PtrOp); + if (F == NM.end()) { + N->BaseVal = PtrOp; + N->Flags |= GepNode::Root; + } else { + // If PtrOp was a GEP instruction, it must have already been processed. + // The ValueToNodeMap entry for it is the last gep node in the generated + // chain. Link to it here. + N->Parent = F->second; + } + N->PTy = PtrOp->getType(); + N->Idx = *GepI->idx_begin(); + + // Collect the list of users of this GEP instruction. Will add it to the + // last node created for it. + UseSet Us; + for (Value::user_iterator UI = GepI->user_begin(), UE = GepI->user_end(); + UI != UE; ++UI) { + // Check if this gep is used by anything other than other geps that + // we will process. + if (isa(*UI)) { + GetElementPtrInst *UserG = cast(*UI); + if (isHandledGepForm(UserG)) + continue; + } + Us.insert(&UI.getUse()); + } + Nodes.push_back(N); +#ifdef _MSC_VER + NodeOrder.special_insert_for_special_msvc(N); +#else + NodeOrder.insert(N); +#endif + + // Skip the first index operand, since we only handle 0. This dereferences + // the pointer operand. + GepNode *PN = N; + Type *PtrTy = cast(PtrOp->getType())->getElementType(); + for (User::op_iterator OI = GepI->idx_begin()+1, OE = GepI->idx_end(); + OI != OE; ++OI) { + Value *Op = *OI; + GepNode *Nx = new (*Mem) GepNode; + Nx->Parent = PN; // Link Nx to the previous node. + Nx->Flags |= GepNode::Internal; + Nx->PTy = PtrTy; + Nx->Idx = Op; + Nodes.push_back(Nx); +#ifdef _MSC_VER + NodeOrder.special_insert_for_special_msvc(Nx); +#else + NodeOrder.insert(Nx); +#endif + PN = Nx; + + PtrTy = next_type(PtrTy, Op); + } + + // After last node has been created, update the use information. + if (!Us.empty()) { + PN->Flags |= GepNode::Used; + Uses[PN].insert(Us.begin(), Us.end()); + } + + // Link the last node with the originating GEP instruction. This is to + // help with linking chained GEP instructions. + NM.insert(std::make_pair(GepI, PN)); +} + + +void HexagonCommonGEP::collect() { + // Establish depth-first traversal order of the dominator tree. + ValueVect BO; + getBlockTraversalOrder(Fn->begin(), BO); + + // The creation of gep nodes requires DT-traversal. When processing a GEP + // instruction that uses another GEP instruction as the base pointer, the + // gep node for the base pointer should already exist. + ValueToNodeMap NM; + for (ValueVect::iterator I = BO.begin(), E = BO.end(); I != E; ++I) { + BasicBlock *B = cast(*I); + for (BasicBlock::iterator J = B->begin(), F = B->end(); J != F; ++J) { + if (!isa(J)) + continue; + GetElementPtrInst *GepI = cast(J); + if (isHandledGepForm(GepI)) + processGepInst(GepI, NM); + } + } + + DEBUG(dbgs() << "Gep nodes after initial collection:\n" << Nodes); +} + + +namespace { + void invert_find_roots(const NodeVect &Nodes, NodeChildrenMap &NCM, + NodeVect &Roots) { + typedef NodeVect::const_iterator const_iterator; + for (const_iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) { + GepNode *N = *I; + if (N->Flags & GepNode::Root) { + Roots.push_back(N); + continue; + } + GepNode *PN = N->Parent; + NCM[PN].push_back(N); + } + } + + void nodes_for_root(GepNode *Root, NodeChildrenMap &NCM, NodeSet &Nodes) { + NodeVect Work; + Work.push_back(Root); + Nodes.insert(Root); + + while (!Work.empty()) { + NodeVect::iterator First = Work.begin(); + GepNode *N = *First; + Work.erase(First); + NodeChildrenMap::iterator CF = NCM.find(N); + if (CF != NCM.end()) { + Work.insert(Work.end(), CF->second.begin(), CF->second.end()); + Nodes.insert(CF->second.begin(), CF->second.end()); + } + } + } +} + + +namespace { + typedef std::set NodeSymRel; + typedef std::pair NodePair; + typedef std::set NodePairSet; + + const NodeSet *node_class(GepNode *N, NodeSymRel &Rel) { + for (NodeSymRel::iterator I = Rel.begin(), E = Rel.end(); I != E; ++I) + if (I->count(N)) + return &*I; + return 0; + } + + // Create an ordered pair of GepNode pointers. The pair will be used in + // determining equality. The only purpose of the ordering is to eliminate + // duplication due to the commutativity of equality/non-equality. + NodePair node_pair(GepNode *N1, GepNode *N2) { + uintptr_t P1 = uintptr_t(N1), P2 = uintptr_t(N2); + if (P1 <= P2) + return std::make_pair(N1, N2); + return std::make_pair(N2, N1); + } + + unsigned node_hash(GepNode *N) { + // Include everything except flags and parent. + FoldingSetNodeID ID; + ID.AddPointer(N->Idx); + ID.AddPointer(N->PTy); + return ID.ComputeHash(); + } + + bool node_eq(GepNode *N1, GepNode *N2, NodePairSet &Eq, NodePairSet &Ne) { + // Don't cache the result for nodes with different hashes. The hash + // comparison is fast enough. + if (node_hash(N1) != node_hash(N2)) + return false; + + NodePair NP = node_pair(N1, N2); + NodePairSet::iterator FEq = Eq.find(NP); + if (FEq != Eq.end()) + return true; + NodePairSet::iterator FNe = Ne.find(NP); + if (FNe != Ne.end()) + return false; + // Not previously compared. + bool Root1 = N1->Flags & GepNode::Root; + bool Root2 = N2->Flags & GepNode::Root; + NodePair P = node_pair(N1, N2); + // If the Root flag has different values, the nodes are different. + // If both nodes are root nodes, but their base pointers differ, + // they are different. + if (Root1 != Root2 || (Root1 && N1->BaseVal != N2->BaseVal)) { + Ne.insert(P); + return false; + } + // Here the root flags are identical, and for root nodes the + // base pointers are equal, so the root nodes are equal. + // For non-root nodes, compare their parent nodes. + if (Root1 || node_eq(N1->Parent, N2->Parent, Eq, Ne)) { + Eq.insert(P); + return true; + } + return false; + } +} + + +void HexagonCommonGEP::common() { + // The essence of this commoning is finding gep nodes that are equal. + // To do this we need to compare all pairs of nodes. To save time, + // first, partition the set of all nodes into sets of potentially equal + // nodes, and then compare pairs from within each partition. + typedef std::map NodeSetMap; + NodeSetMap MaybeEq; + + for (NodeVect::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) { + GepNode *N = *I; + unsigned H = node_hash(N); + MaybeEq[H].insert(N); + } + + // Compute the equivalence relation for the gep nodes. Use two caches, + // one for equality and the other for non-equality. + NodeSymRel EqRel; // Equality relation (as set of equivalence classes). + NodePairSet Eq, Ne; // Caches. + for (NodeSetMap::iterator I = MaybeEq.begin(), E = MaybeEq.end(); + I != E; ++I) { + NodeSet &S = I->second; + for (NodeSet::iterator NI = S.begin(), NE = S.end(); NI != NE; ++NI) { + GepNode *N = *NI; + // If node already has a class, then the class must have been created + // in a prior iteration of this loop. Since equality is transitive, + // nothing more will be added to that class, so skip it. + if (node_class(N, EqRel)) + continue; + + // Create a new class candidate now. + NodeSet C; + for (NodeSet::iterator NJ = std::next(NI); NJ != NE; ++NJ) + if (node_eq(N, *NJ, Eq, Ne)) + C.insert(*NJ); + // If Tmp is empty, N would be the only element in it. Don't bother + // creating a class for it then. + if (!C.empty()) { + C.insert(N); // Finalize the set before adding it to the relation. + std::pair Ins = EqRel.insert(C); + (void)Ins; + assert(Ins.second && "Cannot add a class"); + } + } + } + + DEBUG({ + dbgs() << "Gep node equality:\n"; + for (NodePairSet::iterator I = Eq.begin(), E = Eq.end(); I != E; ++I) + dbgs() << "{ " << I->first << ", " << I->second << " }\n"; + + dbgs() << "Gep equivalence classes:\n"; + for (NodeSymRel::iterator I = EqRel.begin(), E = EqRel.end(); I != E; ++I) { + dbgs() << '{'; + const NodeSet &S = *I; + for (NodeSet::const_iterator J = S.begin(), F = S.end(); J != F; ++J) { + if (J != S.begin()) + dbgs() << ','; + dbgs() << ' ' << *J; + } + dbgs() << " }\n"; + } + }); + + + // Create a projection from a NodeSet to the minimal element in it. + typedef std::map ProjMap; + ProjMap PM; + for (NodeSymRel::iterator I = EqRel.begin(), E = EqRel.end(); I != E; ++I) { + const NodeSet &S = *I; + GepNode *Min = *std::min_element(S.begin(), S.end(), NodeOrder); + std::pair Ins = PM.insert(std::make_pair(&S, Min)); + (void)Ins; + assert(Ins.second && "Cannot add minimal element"); + + // Update the min element's flags, and user list. + uint32_t Flags = 0; + UseSet &MinUs = Uses[Min]; + for (NodeSet::iterator J = S.begin(), F = S.end(); J != F; ++J) { + GepNode *N = *J; + uint32_t NF = N->Flags; + // If N is used, append all original values of N to the list of + // original values of Min. + if (NF & GepNode::Used) + MinUs.insert(Uses[N].begin(), Uses[N].end()); + Flags |= NF; + } + if (MinUs.empty()) + Uses.erase(Min); + + // The collected flags should include all the flags from the min element. + assert((Min->Flags & Flags) == Min->Flags); + Min->Flags = Flags; + } + + // Commoning: for each non-root gep node, replace "Parent" with the + // selected (minimum) node from the corresponding equivalence class. + // If a given parent does not have an equivalence class, leave it + // unchanged (it means that it's the only element in its class). + for (NodeVect::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) { + GepNode *N = *I; + if (N->Flags & GepNode::Root) + continue; + const NodeSet *PC = node_class(N->Parent, EqRel); + if (!PC) + continue; + ProjMap::iterator F = PM.find(PC); + if (F == PM.end()) + continue; + // Found a replacement, use it. + GepNode *Rep = F->second; + N->Parent = Rep; + } + + DEBUG(dbgs() << "Gep nodes after commoning:\n" << Nodes); + + // Finally, erase the nodes that are no longer used. + NodeSet Erase; + for (NodeVect::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) { + GepNode *N = *I; + const NodeSet *PC = node_class(N, EqRel); + if (!PC) + continue; + ProjMap::iterator F = PM.find(PC); + if (F == PM.end()) + continue; + if (N == F->second) + continue; + // Node for removal. + Erase.insert(*I); + } + NodeVect::iterator NewE = std::remove_if(Nodes.begin(), Nodes.end(), + in_set(Erase)); + Nodes.resize(std::distance(Nodes.begin(), NewE)); + + DEBUG(dbgs() << "Gep nodes after post-commoning cleanup:\n" << Nodes); +} + + +namespace { + template + BasicBlock *nearest_common_dominator(DominatorTree *DT, T &Blocks) { + DEBUG({ + dbgs() << "NCD of {"; + for (typename T::iterator I = Blocks.begin(), E = Blocks.end(); + I != E; ++I) { + if (!*I) + continue; + BasicBlock *B = cast(*I); + dbgs() << ' ' << B->getName(); + } + dbgs() << " }\n"; + }); + + // Allow null basic blocks in Blocks. In such cases, return 0. + typename T::iterator I = Blocks.begin(), E = Blocks.end(); + if (I == E || !*I) + return 0; + BasicBlock *Dom = cast(*I); + while (++I != E) { + BasicBlock *B = cast_or_null(*I); + Dom = B ? DT->findNearestCommonDominator(Dom, B) : 0; + if (!Dom) + return 0; + } + DEBUG(dbgs() << "computed:" << Dom->getName() << '\n'); + return Dom; + } + + template + BasicBlock *nearest_common_dominatee(DominatorTree *DT, T &Blocks) { + // If two blocks, A and B, dominate a block C, then A dominates B, + // or B dominates A. + typename T::iterator I = Blocks.begin(), E = Blocks.end(); + // Find the first non-null block. + while (I != E && !*I) + ++I; + if (I == E) + return DT->getRoot(); + BasicBlock *DomB = cast(*I); + while (++I != E) { + if (!*I) + continue; + BasicBlock *B = cast(*I); + if (DT->dominates(B, DomB)) + continue; + if (!DT->dominates(DomB, B)) + return 0; + DomB = B; + } + return DomB; + } + + // Find the first use in B of any value from Values. If no such use, + // return B->end(). + template + BasicBlock::iterator first_use_of_in_block(T &Values, BasicBlock *B) { + BasicBlock::iterator FirstUse = B->end(), BEnd = B->end(); + typedef typename T::iterator iterator; + for (iterator I = Values.begin(), E = Values.end(); I != E; ++I) { + Value *V = *I; + // If V is used in a PHI node, the use belongs to the incoming block, + // not the block with the PHI node. In the incoming block, the use + // would be considered as being at the end of it, so it cannot + // influence the position of the first use (which is assumed to be + // at the end to start with). + if (isa(V)) + continue; + if (!isa(V)) + continue; + Instruction *In = cast(V); + if (In->getParent() != B) + continue; + BasicBlock::iterator It = In; + if (std::distance(FirstUse, BEnd) < std::distance(It, BEnd)) + FirstUse = It; + } + return FirstUse; + } + + bool is_empty(const BasicBlock *B) { + return B->empty() || (&*B->begin() == B->getTerminator()); + } +} + + +BasicBlock *HexagonCommonGEP::recalculatePlacement(GepNode *Node, + NodeChildrenMap &NCM, NodeToValueMap &Loc) { + DEBUG(dbgs() << "Loc for node:" << Node << '\n'); + // Recalculate the placement for Node, assuming that the locations of + // its children in Loc are valid. + // Return 0 if there is no valid placement for Node (for example, it + // uses an index value that is not available at the location required + // to dominate all children, etc.). + + // Find the nearest common dominator for: + // - all users, if the node is used, and + // - all children. + ValueVect Bs; + if (Node->Flags & GepNode::Used) { + // Append all blocks with uses of the original values to the + // block vector Bs. + NodeToUsesMap::iterator UF = Uses.find(Node); + assert(UF != Uses.end() && "Used node with no use information"); + UseSet &Us = UF->second; + for (UseSet::iterator I = Us.begin(), E = Us.end(); I != E; ++I) { + Use *U = *I; + User *R = U->getUser(); + if (!isa(R)) + continue; + BasicBlock *PB = isa(R) + ? cast(R)->getIncomingBlock(*U) + : cast(R)->getParent(); + Bs.push_back(PB); + } + } + // Append the location of each child. + NodeChildrenMap::iterator CF = NCM.find(Node); + if (CF != NCM.end()) { + NodeVect &Cs = CF->second; + for (NodeVect::iterator I = Cs.begin(), E = Cs.end(); I != E; ++I) { + GepNode *CN = *I; + NodeToValueMap::iterator LF = Loc.find(CN); + // If the child is only used in GEP instructions (i.e. is not used in + // non-GEP instructions), the nearest dominator computed for it may + // have been null. In such case it won't have a location available. + if (LF == Loc.end()) + continue; + Bs.push_back(LF->second); + } + } + + BasicBlock *DomB = nearest_common_dominator(DT, Bs); + if (!DomB) + return 0; + // Check if the index used by Node dominates the computed dominator. + Instruction *IdxI = dyn_cast(Node->Idx); + if (IdxI && !DT->dominates(IdxI->getParent(), DomB)) + return 0; + + // Avoid putting nodes into empty blocks. + while (is_empty(DomB)) { + DomTreeNode *N = (*DT)[DomB]->getIDom(); + if (!N) + break; + DomB = N->getBlock(); + } + + // Otherwise, DomB is fine. Update the location map. + Loc[Node] = DomB; + return DomB; +} + + +BasicBlock *HexagonCommonGEP::recalculatePlacementRec(GepNode *Node, + NodeChildrenMap &NCM, NodeToValueMap &Loc) { + DEBUG(dbgs() << "LocRec begin for node:" << Node << '\n'); + // Recalculate the placement of Node, after recursively recalculating the + // placements of all its children. + NodeChildrenMap::iterator CF = NCM.find(Node); + if (CF != NCM.end()) { + NodeVect &Cs = CF->second; + for (NodeVect::iterator I = Cs.begin(), E = Cs.end(); I != E; ++I) + recalculatePlacementRec(*I, NCM, Loc); + } + BasicBlock *LB = recalculatePlacement(Node, NCM, Loc); + DEBUG(dbgs() << "LocRec end for node:" << Node << '\n'); + return LB; +} + + +bool HexagonCommonGEP::isInvariantIn(Value *Val, Loop *L) { + if (isa(Val) || isa(Val)) + return true; + Instruction *In = dyn_cast(Val); + if (!In) + return false; + BasicBlock *HdrB = L->getHeader(), *DefB = In->getParent(); + return DT->properlyDominates(DefB, HdrB); +} + + +bool HexagonCommonGEP::isInvariantIn(GepNode *Node, Loop *L) { + if (Node->Flags & GepNode::Root) + if (!isInvariantIn(Node->BaseVal, L)) + return false; + return isInvariantIn(Node->Idx, L); +} + + +bool HexagonCommonGEP::isInMainPath(BasicBlock *B, Loop *L) { + BasicBlock *HB = L->getHeader(); + BasicBlock *LB = L->getLoopLatch(); + // B must post-dominate the loop header or dominate the loop latch. + if (PDT->dominates(B, HB)) + return true; + if (LB && DT->dominates(B, LB)) + return true; + return false; +} + + +namespace { + BasicBlock *preheader(DominatorTree *DT, Loop *L) { + if (BasicBlock *PH = L->getLoopPreheader()) + return PH; + if (!OptSpeculate) + return 0; + DomTreeNode *DN = DT->getNode(L->getHeader()); + if (!DN) + return 0; + return DN->getIDom()->getBlock(); + } +} + + +BasicBlock *HexagonCommonGEP::adjustForInvariance(GepNode *Node, + NodeChildrenMap &NCM, NodeToValueMap &Loc) { + // Find the "topmost" location for Node: it must be dominated by both, + // its parent (or the BaseVal, if it's a root node), and by the index + // value. + ValueVect Bs; + if (Node->Flags & GepNode::Root) { + if (Instruction *PIn = dyn_cast(Node->BaseVal)) + Bs.push_back(PIn->getParent()); + } else { + Bs.push_back(Loc[Node->Parent]); + } + if (Instruction *IIn = dyn_cast(Node->Idx)) + Bs.push_back(IIn->getParent()); + BasicBlock *TopB = nearest_common_dominatee(DT, Bs); + + // Traverse the loop nest upwards until we find a loop in which Node + // is no longer invariant, or until we get to the upper limit of Node's + // placement. The traversal will also stop when a suitable "preheader" + // cannot be found for a given loop. The "preheader" may actually be + // a regular block outside of the loop (i.e. not guarded), in which case + // the Node will be speculated. + // For nodes that are not in the main path of the containing loop (i.e. + // are not executed in each iteration), do not move them out of the loop. + BasicBlock *LocB = cast_or_null(Loc[Node]); + if (LocB) { + Loop *Lp = LI->getLoopFor(LocB); + while (Lp) { + if (!isInvariantIn(Node, Lp) || !isInMainPath(LocB, Lp)) + break; + BasicBlock *NewLoc = preheader(DT, Lp); + if (!NewLoc || !DT->dominates(TopB, NewLoc)) + break; + Lp = Lp->getParentLoop(); + LocB = NewLoc; + } + } + Loc[Node] = LocB; + + // Recursively compute the locations of all children nodes. + NodeChildrenMap::iterator CF = NCM.find(Node); + if (CF != NCM.end()) { + NodeVect &Cs = CF->second; + for (NodeVect::iterator I = Cs.begin(), E = Cs.end(); I != E; ++I) + adjustForInvariance(*I, NCM, Loc); + } + return LocB; +} + + +namespace { + struct LocationAsBlock { + LocationAsBlock(const NodeToValueMap &L) : Map(L) {} + const NodeToValueMap ⤅ + }; + + raw_ostream &operator<< (raw_ostream &OS, + const LocationAsBlock &Loc) LLVM_ATTRIBUTE_UNUSED ; + raw_ostream &operator<< (raw_ostream &OS, const LocationAsBlock &Loc) { + for (NodeToValueMap::const_iterator I = Loc.Map.begin(), E = Loc.Map.end(); + I != E; ++I) { + OS << I->first << " -> "; + BasicBlock *B = cast(I->second); + OS << B->getName() << '(' << B << ')'; + OS << '\n'; + } + return OS; + } + + inline bool is_constant(GepNode *N) { + return isa(N->Idx); + } +} + + +void HexagonCommonGEP::separateChainForNode(GepNode *Node, Use *U, + NodeToValueMap &Loc) { + User *R = U->getUser(); + DEBUG(dbgs() << "Separating chain for node (" << Node << ") user: " + << *R << '\n'); + BasicBlock *PB = cast(R)->getParent(); + + GepNode *N = Node; + GepNode *C = 0, *NewNode = 0; + while (is_constant(N) && !(N->Flags & GepNode::Root)) { + // XXX if (single-use) dont-replicate; + GepNode *NewN = new (*Mem) GepNode(N); + Nodes.push_back(NewN); + Loc[NewN] = PB; + + if (N == Node) + NewNode = NewN; + NewN->Flags &= ~GepNode::Used; + if (C) + C->Parent = NewN; + C = NewN; + N = N->Parent; + } + if (!NewNode) + return; + + // Move over all uses that share the same user as U from Node to NewNode. + NodeToUsesMap::iterator UF = Uses.find(Node); + assert(UF != Uses.end()); + UseSet &Us = UF->second; + UseSet NewUs; + for (UseSet::iterator I = Us.begin(); I != Us.end(); ) { + User *S = (*I)->getUser(); + UseSet::iterator Nx = std::next(I); + if (S == R) { + NewUs.insert(*I); + Us.erase(I); + } + I = Nx; + } + if (Us.empty()) { + Node->Flags &= ~GepNode::Used; + Uses.erase(UF); + } + + // Should at least have U in NewUs. + NewNode->Flags |= GepNode::Used; + DEBUG(dbgs() << "new node: " << NewNode << " " << *NewNode << '\n'); + assert(!NewUs.empty()); + Uses[NewNode] = NewUs; +} + + +void HexagonCommonGEP::separateConstantChains(GepNode *Node, + NodeChildrenMap &NCM, NodeToValueMap &Loc) { + // First approximation: extract all chains. + NodeSet Ns; + nodes_for_root(Node, NCM, Ns); + + DEBUG(dbgs() << "Separating constant chains for node: " << Node << '\n'); + // Collect all used nodes together with the uses from loads and stores, + // where the GEP node could be folded into the load/store instruction. + NodeToUsesMap FNs; // Foldable nodes. + for (NodeSet::iterator I = Ns.begin(), E = Ns.end(); I != E; ++I) { + GepNode *N = *I; + if (!(N->Flags & GepNode::Used)) + continue; + NodeToUsesMap::iterator UF = Uses.find(N); + assert(UF != Uses.end()); + UseSet &Us = UF->second; + // Loads/stores that use the node N. + UseSet LSs; + for (UseSet::iterator J = Us.begin(), F = Us.end(); J != F; ++J) { + Use *U = *J; + User *R = U->getUser(); + // We're interested in uses that provide the address. It can happen + // that the value may also be provided via GEP, but we won't handle + // those cases here for now. + if (LoadInst *Ld = dyn_cast(R)) { + unsigned PtrX = LoadInst::getPointerOperandIndex(); + if (&Ld->getOperandUse(PtrX) == U) + LSs.insert(U); + } else if (StoreInst *St = dyn_cast(R)) { + unsigned PtrX = StoreInst::getPointerOperandIndex(); + if (&St->getOperandUse(PtrX) == U) + LSs.insert(U); + } + } + // Even if the total use count is 1, separating the chain may still be + // beneficial, since the constant chain may be longer than the GEP alone + // would be (e.g. if the parent node has a constant index and also has + // other children). + if (!LSs.empty()) + FNs.insert(std::make_pair(N, LSs)); + } + + DEBUG(dbgs() << "Nodes with foldable users:\n" << FNs); + + for (NodeToUsesMap::iterator I = FNs.begin(), E = FNs.end(); I != E; ++I) { + GepNode *N = I->first; + UseSet &Us = I->second; + for (UseSet::iterator J = Us.begin(), F = Us.end(); J != F; ++J) + separateChainForNode(N, *J, Loc); + } +} + + +void HexagonCommonGEP::computeNodePlacement(NodeToValueMap &Loc) { + // Compute the inverse of the Node.Parent links. Also, collect the set + // of root nodes. + NodeChildrenMap NCM; + NodeVect Roots; + invert_find_roots(Nodes, NCM, Roots); + + // Compute the initial placement determined by the users' locations, and + // the locations of the child nodes. + for (NodeVect::iterator I = Roots.begin(), E = Roots.end(); I != E; ++I) + recalculatePlacementRec(*I, NCM, Loc); + + DEBUG(dbgs() << "Initial node placement:\n" << LocationAsBlock(Loc)); + + if (OptEnableInv) { + for (NodeVect::iterator I = Roots.begin(), E = Roots.end(); I != E; ++I) + adjustForInvariance(*I, NCM, Loc); + + DEBUG(dbgs() << "Node placement after adjustment for invariance:\n" + << LocationAsBlock(Loc)); + } + if (OptEnableConst) { + for (NodeVect::iterator I = Roots.begin(), E = Roots.end(); I != E; ++I) + separateConstantChains(*I, NCM, Loc); + } + DEBUG(dbgs() << "Node use information:\n" << Uses); + + // At the moment, there is no further refinement of the initial placement. + // Such a refinement could include splitting the nodes if they are placed + // too far from some of its users. + + DEBUG(dbgs() << "Final node placement:\n" << LocationAsBlock(Loc)); +} + + +Value *HexagonCommonGEP::fabricateGEP(NodeVect &NA, BasicBlock::iterator At, + BasicBlock *LocB) { + DEBUG(dbgs() << "Fabricating GEP in " << LocB->getName() + << " for nodes:\n" << NA); + unsigned Num = NA.size(); + GepNode *RN = NA[0]; + assert((RN->Flags & GepNode::Root) && "Creating GEP for non-root"); + + Value *NewInst = 0; + Value *Input = RN->BaseVal; + Value **IdxList = new Value*[Num+1]; + unsigned nax = 0; + do { + unsigned IdxC = 0; + // If the type of the input of the first node is not a pointer, + // we need to add an artificial i32 0 to the indices (because the + // actual input in the IR will be a pointer). + if (!NA[nax]->PTy->isPointerTy()) { + Type *Int32Ty = Type::getInt32Ty(*Ctx); + IdxList[IdxC++] = ConstantInt::get(Int32Ty, 0); + } + + // Keep adding indices from NA until we have to stop and generate + // an "intermediate" GEP. + while (++nax <= Num) { + GepNode *N = NA[nax-1]; + IdxList[IdxC++] = N->Idx; + if (nax < Num) { + // We have to stop, if the expected type of the output of this node + // is not the same as the input type of the next node. + Type *NextTy = next_type(N->PTy, N->Idx); + if (NextTy != NA[nax]->PTy) + break; + } + } + ArrayRef A(IdxList, IdxC); + Type *InpTy = Input->getType(); + Type *ElTy = cast(InpTy->getScalarType())->getElementType(); + NewInst = GetElementPtrInst::Create(ElTy, Input, A, "cgep", At); + DEBUG(dbgs() << "new GEP: " << *NewInst << '\n'); + Input = NewInst; + } while (nax <= Num); + + delete[] IdxList; + return NewInst; +} + + +void HexagonCommonGEP::getAllUsersForNode(GepNode *Node, ValueVect &Values, + NodeChildrenMap &NCM) { + NodeVect Work; + Work.push_back(Node); + + while (!Work.empty()) { + NodeVect::iterator First = Work.begin(); + GepNode *N = *First; + Work.erase(First); + if (N->Flags & GepNode::Used) { + NodeToUsesMap::iterator UF = Uses.find(N); + assert(UF != Uses.end() && "No use information for used node"); + UseSet &Us = UF->second; + for (UseSet::iterator I = Us.begin(), E = Us.end(); I != E; ++I) + Values.push_back((*I)->getUser()); + } + NodeChildrenMap::iterator CF = NCM.find(N); + if (CF != NCM.end()) { + NodeVect &Cs = CF->second; + Work.insert(Work.end(), Cs.begin(), Cs.end()); + } + } +} + + +void HexagonCommonGEP::materialize(NodeToValueMap &Loc) { + DEBUG(dbgs() << "Nodes before materialization:\n" << Nodes << '\n'); + NodeChildrenMap NCM; + NodeVect Roots; + // Compute the inversion again, since computing placement could alter + // "parent" relation between nodes. + invert_find_roots(Nodes, NCM, Roots); + + while (!Roots.empty()) { + NodeVect::iterator First = Roots.begin(); + GepNode *Root = *First, *Last = *First; + Roots.erase(First); + + NodeVect NA; // Nodes to assemble. + // Append to NA all child nodes up to (and including) the first child + // that: + // (1) has more than 1 child, or + // (2) is used, or + // (3) has a child located in a different block. + bool LastUsed = false; + unsigned LastCN = 0; + // The location may be null if the computation failed (it can legitimately + // happen for nodes created from dead GEPs). + Value *LocV = Loc[Last]; + if (!LocV) + continue; + BasicBlock *LastB = cast(LocV); + do { + NA.push_back(Last); + LastUsed = (Last->Flags & GepNode::Used); + if (LastUsed) + break; + NodeChildrenMap::iterator CF = NCM.find(Last); + LastCN = (CF != NCM.end()) ? CF->second.size() : 0; + if (LastCN != 1) + break; + GepNode *Child = CF->second.front(); + BasicBlock *ChildB = cast_or_null(Loc[Child]); + if (ChildB != 0 && LastB != ChildB) + break; + Last = Child; + } while (true); + + BasicBlock::iterator InsertAt = LastB->getTerminator(); + if (LastUsed || LastCN > 0) { + ValueVect Urs; + getAllUsersForNode(Root, Urs, NCM); + BasicBlock::iterator FirstUse = first_use_of_in_block(Urs, LastB); + if (FirstUse != LastB->end()) + InsertAt = FirstUse; + } + + // Generate a new instruction for NA. + Value *NewInst = fabricateGEP(NA, InsertAt, LastB); + + // Convert all the children of Last node into roots, and append them + // to the Roots list. + if (LastCN > 0) { + NodeVect &Cs = NCM[Last]; + for (NodeVect::iterator I = Cs.begin(), E = Cs.end(); I != E; ++I) { + GepNode *CN = *I; + CN->Flags &= ~GepNode::Internal; + CN->Flags |= GepNode::Root; + CN->BaseVal = NewInst; + Roots.push_back(CN); + } + } + + // Lastly, if the Last node was used, replace all uses with the new GEP. + // The uses reference the original GEP values. + if (LastUsed) { + NodeToUsesMap::iterator UF = Uses.find(Last); + assert(UF != Uses.end() && "No use information found"); + UseSet &Us = UF->second; + for (UseSet::iterator I = Us.begin(), E = Us.end(); I != E; ++I) { + Use *U = *I; + U->set(NewInst); + } + } + } +} + + +void HexagonCommonGEP::removeDeadCode() { + ValueVect BO; + BO.push_back(&Fn->front()); + + for (unsigned i = 0; i < BO.size(); ++i) { + BasicBlock *B = cast(BO[i]); + DomTreeNode *N = DT->getNode(B); + typedef GraphTraits GTN; + typedef GTN::ChildIteratorType Iter; + for (Iter I = GTN::child_begin(N), E = GTN::child_end(N); I != E; ++I) + BO.push_back((*I)->getBlock()); + } + + for (unsigned i = BO.size(); i > 0; --i) { + BasicBlock *B = cast(BO[i-1]); + BasicBlock::InstListType &IL = B->getInstList(); + typedef BasicBlock::InstListType::reverse_iterator reverse_iterator; + ValueVect Ins; + for (reverse_iterator I = IL.rbegin(), E = IL.rend(); I != E; ++I) + Ins.push_back(&*I); + for (ValueVect::iterator I = Ins.begin(), E = Ins.end(); I != E; ++I) { + Instruction *In = cast(*I); + if (isInstructionTriviallyDead(In)) + In->eraseFromParent(); + } + } +} + + +bool HexagonCommonGEP::runOnFunction(Function &F) { + // For now bail out on C++ exception handling. + for (Function::iterator A = F.begin(), Z = F.end(); A != Z; ++A) + for (BasicBlock::iterator I = A->begin(), E = A->end(); I != E; ++I) + if (isa(I) || isa(I)) + return false; + + Fn = &F; + DT = &getAnalysis().getDomTree(); + PDT = &getAnalysis(); + LI = &getAnalysis().getLoopInfo(); + Ctx = &F.getContext(); + + Nodes.clear(); + Uses.clear(); + NodeOrder.clear(); + + SpecificBumpPtrAllocator Allocator; + Mem = &Allocator; + + collect(); + common(); + + NodeToValueMap Loc; + computeNodePlacement(Loc); + materialize(Loc); + removeDeadCode(); + +#ifdef XDEBUG + // Run this only when expensive checks are enabled. + verifyFunction(F); +#endif + return true; +} + + +namespace llvm { + FunctionPass *createHexagonCommonGEP() { + return new HexagonCommonGEP(); + } +} diff --git a/lib/Target/Hexagon/HexagonTargetMachine.cpp b/lib/Target/Hexagon/HexagonTargetMachine.cpp index 10b809f51de..59007be934e 100644 --- a/lib/Target/Hexagon/HexagonTargetMachine.cpp +++ b/lib/Target/Hexagon/HexagonTargetMachine.cpp @@ -40,6 +40,10 @@ static cl::opt EnableExpandCondsets("hexagon-expand-condsets", static cl::opt EnableGenInsert("hexagon-insert", cl::init(true), cl::Hidden, cl::desc("Generate \"insert\" instructions")); +static cl::opt EnableCommGEP("hexagon-commgep", cl::init(true), + cl::Hidden, cl::ZeroOrMore, cl::desc("Enable commoning of GEP instructions")); + + /// HexagonTargetMachineModule - Note that this is used on hosts that /// cannot link in a library unless there are references into the /// library. In particular, it seems that it is not possible to get @@ -62,6 +66,7 @@ SchedCustomRegistry("hexagon", "Run Hexagon's custom scheduler", createVLIWMachineSched); namespace llvm { + FunctionPass *createHexagonCommonGEP(); FunctionPass *createHexagonExpandCondsets(); FunctionPass *createHexagonISelDag(HexagonTargetMachine &TM, CodeGenOpt::Level OptLevel); @@ -124,6 +129,7 @@ public: return createVLIWMachineSched(C); } + void addIRPasses() override; bool addInstSelector() override; void addPreRegAlloc() override; void addPostRegAlloc() override; @@ -136,6 +142,14 @@ TargetPassConfig *HexagonTargetMachine::createPassConfig(PassManagerBase &PM) { return new HexagonPassConfig(this, PM); } +void HexagonPassConfig::addIRPasses() { + TargetPassConfig::addIRPasses(); + + bool NoOpt = (getOptLevel() == CodeGenOpt::None); + if (!NoOpt && EnableCommGEP) + addPass(createHexagonCommonGEP()); +} + bool HexagonPassConfig::addInstSelector() { HexagonTargetMachine &TM = getHexagonTargetMachine(); bool NoOpt = (getOptLevel() == CodeGenOpt::None); diff --git a/test/CodeGen/Hexagon/common-gep-basic.ll b/test/CodeGen/Hexagon/common-gep-basic.ll new file mode 100644 index 00000000000..317bf868d0f --- /dev/null +++ b/test/CodeGen/Hexagon/common-gep-basic.ll @@ -0,0 +1,37 @@ +; RUN: llc -O2 -march=hexagon < %s | FileCheck %s +; CHECK: mpyi +; CHECK-NOT: mpyi +; The mpyis from the two GEPs should be commoned out. + +target datalayout = "e-m:e-p:32:32-i64:64-a:0-v32:32-n16:32" +target triple = "hexagon-unknown--elf" + +%struct.s_t = type { %struct.anon, i32 } +%struct.anon = type { i32, [5 x i32] } + +@g = common global [100 x %struct.s_t] zeroinitializer, align 8 + +; Function Attrs: nounwind +define void @foo(i32 %x) #0 { +entry: + %cmp = icmp slt i32 %x, 90 + br i1 %cmp, label %if.then, label %if.else + +if.then: ; preds = %entry + %arrayidx1 = getelementptr inbounds [100 x %struct.s_t], [100 x %struct.s_t]* @g, i32 0, i32 %x, i32 0, i32 1, i32 2 + tail call void @bar(i32* %arrayidx1) #0 + br label %if.end + +if.else: ; preds = %entry + %arrayidx5 = getelementptr inbounds [100 x %struct.s_t], [100 x %struct.s_t]* @g, i32 0, i32 %x, i32 0, i32 1, i32 3 + tail call void @bar(i32* %arrayidx5) #0 + br label %if.end + +if.end: ; preds = %if.else, %if.then + ret void +} + +declare void @bar(i32*) #0 + +attributes #0 = { nounwind } + diff --git a/test/CodeGen/Hexagon/common-gep-icm.ll b/test/CodeGen/Hexagon/common-gep-icm.ll new file mode 100644 index 00000000000..bc5719dfe1d --- /dev/null +++ b/test/CodeGen/Hexagon/common-gep-icm.ll @@ -0,0 +1,76 @@ +; RUN: llc -O2 -march=hexagon < %s | FileCheck %s +; Rely on the comments generated by llc. Make sure there are no add/addasl +; instructions in while.body13 (before the loads). +; CHECK: while.body13 +; CHECK-NOT: add +; CHECK: memw + +%struct.1 = type { i32, i32 } +%struct.2 = type { [24 x i32], [24 x i32], [24 x i32], [24 x i32], [24 x i32], [24 x i32], [24 x i32], [24 x i32], [24 x i32], [24 x i32], [24 x i32], [24 x i32], [24 x i32], [24 x i32], [24 x i32], [24 x i32], [24 x i32], [3 x i32], [24 x i32], [8 x %struct.1], [5 x i32] } + +@A1 = global i64 zeroinitializer +@A2 = global i64 zeroinitializer +@B1 = global i32 zeroinitializer +@B2 = global i32 zeroinitializer +@C1 = global i8 zeroinitializer + +declare i32 @llvm.hexagon.S2.cl0(i32) nounwind readnone +declare i32 @llvm.hexagon.S2.setbit.r(i32, i32) nounwind readnone +declare i64 @llvm.hexagon.M2.vmpy2s.s0(i32, i32) nounwind readnone +declare i64 @llvm.hexagon.M2.vmac2s.s0(i64, i32, i32) nounwind readnone +declare i64 @llvm.hexagon.A2.vaddws(i64, i64) nounwind readnone +declare i64 @llvm.hexagon.A2.vsubws(i64, i64) nounwind readnone +declare i32 @llvm.hexagon.A4.modwrapu(i32, i32) nounwind readnone + +define void @foo(i32 %n) nounwind { +entry: + br label %while.body + +while.body: + %count = phi i32 [ 0, %entry ], [ %next, %while.end ] + %idx = phi i32 [ 0, %entry ], [ %15, %while.end ] + %0 = load i32, i32* @B1, align 4 + %1 = load i32, i32* @B2, align 8 + %2 = and i32 %1, %0 + br label %while.body13 + +while.body13: ; preds = %while.body, %if.end + %3 = phi i64 [ %13, %if.end ], [ 0, %while.body ] + %4 = phi i64 [ %14, %if.end ], [ 0, %while.body ] + %m = phi i32 [ %6, %if.end ], [ %2, %while.body ] + %5 = tail call i32 @llvm.hexagon.S2.cl0(i32 %m) + %6 = tail call i32 @llvm.hexagon.S2.setbit.r(i32 %m, i32 %5) + %cgep85 = getelementptr [10 x %struct.2], [10 x %struct.2]* inttoptr (i32 -121502345 to [10 x %struct.2]*), i32 0, i32 %idx + %cgep90 = getelementptr %struct.2, %struct.2* %cgep85, i32 0, i32 12, i32 %5 + %7 = load i32, i32* %cgep90, align 4 + %8 = tail call i64 @llvm.hexagon.M2.vmpy2s.s0(i32 %7, i32 %7) + %cgep91 = getelementptr %struct.2, %struct.2* %cgep85, i32 0, i32 13, i32 %5 + %9 = load i32, i32* %cgep91, align 4 + %10 = tail call i64 @llvm.hexagon.M2.vmac2s.s0(i64 %8, i32 %9, i32 %9) + %11 = load i8, i8* @C1, align 1 + %and24 = and i8 %11, 1 + %cmp = icmp eq i8 %and24, 0 + br i1 %cmp, label %if.then, label %if.end + +if.then: ; preds = %while.body13 + %12 = tail call i64 @llvm.hexagon.A2.vaddws(i64 %3, i64 %10) + store i64 %12, i64* @A1, align 8 + br label %if.end + +if.end: ; preds = %if.then, %while.body13 + %13 = phi i64 [ %12, %if.then ], [ %3, %while.body13 ] + %14 = tail call i64 @llvm.hexagon.A2.vsubws(i64 %4, i64 %10) + %tobool12 = icmp eq i32 %6, 0 + br i1 %tobool12, label %while.end, label %while.body13 + +while.end: + %add40 = add i32 %idx, 1 + %15 = tail call i32 @llvm.hexagon.A4.modwrapu(i32 %add40, i32 10) nounwind + %next = add i32 %count, 1 + %cc = icmp eq i32 %next, %n + br i1 %cc, label %end, label %while.body + +end: + store i64 %10, i64* @A2, align 8 + ret void +} -- 2.34.1