summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Target/Hexagon/HexagonCommonGEP.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/Target/Hexagon/HexagonCommonGEP.cpp')
-rw-r--r--llvm/lib/Target/Hexagon/HexagonCommonGEP.cpp189
1 files changed, 91 insertions, 98 deletions
diff --git a/llvm/lib/Target/Hexagon/HexagonCommonGEP.cpp b/llvm/lib/Target/Hexagon/HexagonCommonGEP.cpp
index 9336e0fd50b..3c9b1ec5953 100644
--- a/llvm/lib/Target/Hexagon/HexagonCommonGEP.cpp
+++ b/llvm/lib/Target/Hexagon/HexagonCommonGEP.cpp
@@ -9,29 +9,42 @@
#define DEBUG_TYPE "commgep"
-#include "llvm/Pass.h"
+#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/FoldingSet.h"
#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/StringRef.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/PostDominators.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/Constant.h"
#include "llvm/IR/Constants.h"
+#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
+#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
-#include "llvm/IR/Verifier.h"
+#include "llvm/IR/Type.h"
+#include "llvm/IR/Use.h"
+#include "llvm/IR/User.h"
+#include "llvm/IR/Value.h"
+#include "llvm/Pass.h"
#include "llvm/Support/Allocator.h"
+#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
-#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/Local.h"
-
+#include <algorithm>
+#include <cassert>
+#include <cstddef>
+#include <cstdint>
+#include <iterator>
#include <map>
#include <set>
+#include <utility>
#include <vector>
-#include "HexagonTargetMachine.h"
-
using namespace llvm;
static cl::opt<bool> OptSpeculate("commgep-speculate", cl::init(true),
@@ -44,10 +57,13 @@ static cl::opt<bool> OptEnableConst("commgep-const", cl::init(true),
cl::Hidden, cl::ZeroOrMore);
namespace llvm {
+
void initializeHexagonCommonGEPPass(PassRegistry&);
-}
+
+} // end namespace llvm
namespace {
+
struct GepNode;
typedef std::set<GepNode*> NodeSet;
typedef std::map<GepNode*,Value*> NodeToValueMap;
@@ -59,7 +75,7 @@ namespace {
// Numbering map for gep nodes. Used to keep track of ordering for
// gep nodes.
struct NodeOrdering {
- NodeOrdering() : LastNum(0) {}
+ NodeOrdering() = default;
void insert(const GepNode *N) { Map.insert(std::make_pair(N, ++LastNum)); }
void clear() { Map.clear(); }
@@ -72,19 +88,21 @@ namespace {
private:
std::map<const GepNode *, unsigned> Map;
- unsigned LastNum;
+ unsigned LastNum = 0;
};
class HexagonCommonGEP : public FunctionPass {
public:
static char ID;
+
HexagonCommonGEP() : FunctionPass(ID) {
initializeHexagonCommonGEPPass(*PassRegistry::getPassRegistry());
}
- virtual bool runOnFunction(Function &F);
- virtual StringRef getPassName() const { return "Hexagon Common GEP"; }
- virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ bool runOnFunction(Function &F) override;
+ StringRef getPassName() const override { return "Hexagon Common GEP"; }
+
+ void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.addRequired<DominatorTreeWrapperPass>();
AU.addPreserved<DominatorTreeWrapperPass>();
AU.addRequired<PostDominatorTreeWrapperPass>();
@@ -137,8 +155,8 @@ namespace {
PostDominatorTree *PDT;
Function *Fn;
};
-}
+} // end anonymous namespace
char HexagonCommonGEP::ID = 0;
INITIALIZE_PASS_BEGIN(HexagonCommonGEP, "hcommgep", "Hexagon Common GEP",
@@ -150,6 +168,7 @@ INITIALIZE_PASS_END(HexagonCommonGEP, "hcommgep", "Hexagon Common GEP",
false, false)
namespace {
+
struct GepNode {
enum {
None = 0,
@@ -166,17 +185,17 @@ namespace {
Value *Idx;
Type *PTy; // Type of the pointer operand.
- GepNode() : Flags(0), Parent(0), Idx(0), PTy(0) {}
+ GepNode() : Flags(0), Parent(nullptr), Idx(nullptr), PTy(nullptr) {}
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) {
if (auto *PTy = dyn_cast<PointerType>(Ty))
return PTy->getElementType();
@@ -193,7 +212,6 @@ namespace {
return NextTy;
}
-
raw_ostream &operator<< (raw_ostream &OS, const GepNode &GN) {
OS << "{ {";
bool Comma = false;
@@ -240,7 +258,6 @@ namespace {
return OS;
}
-
template <typename NodeContainer>
void dump_node_container(raw_ostream &OS, const NodeContainer &S) {
typedef typename NodeContainer::const_iterator const_iterator;
@@ -255,7 +272,6 @@ namespace {
return OS;
}
-
raw_ostream &operator<< (raw_ostream &OS,
const NodeToUsesMap &M) LLVM_ATTRIBUTE_UNUSED;
raw_ostream &operator<< (raw_ostream &OS, const NodeToUsesMap &M){
@@ -275,23 +291,22 @@ namespace {
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;
};
-}
+} // end anonymous namespace
inline void *operator new(size_t, SpecificBumpPtrAllocator<GepNode> &A) {
return A.Allocate();
}
-
void HexagonCommonGEP::getBlockTraversalOrder(BasicBlock *Root,
ValueVect &Order) {
// Compute block ordering for a typical DT-based traversal of the flow
@@ -306,7 +321,6 @@ void HexagonCommonGEP::getBlockTraversalOrder(BasicBlock *Root,
getBlockTraversalOrder((*I)->getBlock(), Order);
}
-
bool HexagonCommonGEP::isHandledGepForm(GetElementPtrInst *GepI) {
// No vector GEPs.
if (!GepI->getType()->isPointerTy())
@@ -317,7 +331,6 @@ bool HexagonCommonGEP::isHandledGepForm(GetElementPtrInst *GepI) {
return true;
}
-
void HexagonCommonGEP::processGepInst(GetElementPtrInst *GepI,
ValueToNodeMap &NM) {
DEBUG(dbgs() << "Visiting GEP: " << *GepI << '\n');
@@ -383,7 +396,6 @@ void HexagonCommonGEP::processGepInst(GetElementPtrInst *GepI,
NM.insert(std::make_pair(GepI, PN));
}
-
void HexagonCommonGEP::collect() {
// Establish depth-first traversal order of the dominator tree.
ValueVect BO;
@@ -407,10 +419,8 @@ void HexagonCommonGEP::collect() {
DEBUG(dbgs() << "Gep nodes after initial collection:\n" << Nodes);
}
-
-namespace {
- void invert_find_roots(const NodeVect &Nodes, NodeChildrenMap &NCM,
- NodeVect &Roots) {
+static 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;
@@ -421,9 +431,10 @@ namespace {
GepNode *PN = N->Parent;
NCM[PN].push_back(N);
}
- }
+}
- void nodes_for_root(GepNode *Root, NodeChildrenMap &NCM, NodeSet &Nodes) {
+static void nodes_for_root(GepNode *Root, NodeChildrenMap &NCM,
+ NodeSet &Nodes) {
NodeVect Work;
Work.push_back(Root);
Nodes.insert(Root);
@@ -438,41 +449,43 @@ namespace {
Nodes.insert(CF->second.begin(), CF->second.end());
}
}
- }
}
-
namespace {
+
typedef std::set<NodeSet> NodeSymRel;
typedef std::pair<GepNode*,GepNode*> NodePair;
typedef std::set<NodePair> NodePairSet;
- const NodeSet *node_class(GepNode *N, NodeSymRel &Rel) {
+} // end anonymous namespace
+
+static 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;
- }
+ return nullptr;
+}
// 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) {
+static 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) {
+static 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) {
+static 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))
@@ -504,10 +517,8 @@ namespace {
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,
@@ -571,7 +582,6 @@ void HexagonCommonGEP::common() {
}
});
-
// Create a projection from a NodeSet to the minimal element in it.
typedef std::map<const NodeSet*,GepNode*> ProjMap;
ProjMap PM;
@@ -644,10 +654,8 @@ void HexagonCommonGEP::common() {
DEBUG(dbgs() << "Gep nodes after post-commoning cleanup:\n" << Nodes);
}
-
-namespace {
- template <typename T>
- BasicBlock *nearest_common_dominator(DominatorTree *DT, T &Blocks) {
+template <typename T>
+static BasicBlock *nearest_common_dominator(DominatorTree *DT, T &Blocks) {
DEBUG({
dbgs() << "NCD of {";
for (typename T::iterator I = Blocks.begin(), E = Blocks.end();
@@ -660,23 +668,23 @@ namespace {
dbgs() << " }\n";
});
- // Allow null basic blocks in Blocks. In such cases, return 0.
+ // Allow null basic blocks in Blocks. In such cases, return nullptr.
typename T::iterator I = Blocks.begin(), E = Blocks.end();
if (I == E || !*I)
- return 0;
+ return nullptr;
BasicBlock *Dom = cast<BasicBlock>(*I);
while (++I != E) {
BasicBlock *B = cast_or_null<BasicBlock>(*I);
- Dom = B ? DT->findNearestCommonDominator(Dom, B) : 0;
+ Dom = B ? DT->findNearestCommonDominator(Dom, B) : nullptr;
if (!Dom)
- return 0;
+ return nullptr;
}
DEBUG(dbgs() << "computed:" << Dom->getName() << '\n');
return Dom;
- }
+}
- template <typename T>
- BasicBlock *nearest_common_dominatee(DominatorTree *DT, T &Blocks) {
+template <typename T>
+static 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();
@@ -693,16 +701,16 @@ namespace {
if (DT->dominates(B, DomB))
continue;
if (!DT->dominates(DomB, B))
- return 0;
+ return nullptr;
DomB = B;
}
return DomB;
- }
+}
- // Find the first use in B of any value from Values. If no such use,
- // return B->end().
- template <typename T>
- BasicBlock::iterator first_use_of_in_block(T &Values, BasicBlock *B) {
+// Find the first use in B of any value from Values. If no such use,
+// return B->end().
+template <typename T>
+static 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) {
@@ -724,20 +732,18 @@ namespace {
FirstUse = It;
}
return FirstUse;
- }
+}
- bool is_empty(const BasicBlock *B) {
+static 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
+ // Return nullptr 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.).
@@ -780,11 +786,11 @@ BasicBlock *HexagonCommonGEP::recalculatePlacement(GepNode *Node,
BasicBlock *DomB = nearest_common_dominator(DT, Bs);
if (!DomB)
- return 0;
+ return nullptr;
// Check if the index used by Node dominates the computed dominator.
Instruction *IdxI = dyn_cast<Instruction>(Node->Idx);
if (IdxI && !DT->dominates(IdxI->getParent(), DomB))
- return 0;
+ return nullptr;
// Avoid putting nodes into empty blocks.
while (is_empty(DomB)) {
@@ -799,7 +805,6 @@ BasicBlock *HexagonCommonGEP::recalculatePlacement(GepNode *Node,
return DomB;
}
-
BasicBlock *HexagonCommonGEP::recalculatePlacementRec(GepNode *Node,
NodeChildrenMap &NCM, NodeToValueMap &Loc) {
DEBUG(dbgs() << "LocRec begin for node:" << Node << '\n');
@@ -816,7 +821,6 @@ BasicBlock *HexagonCommonGEP::recalculatePlacementRec(GepNode *Node,
return LB;
}
-
bool HexagonCommonGEP::isInvariantIn(Value *Val, Loop *L) {
if (isa<Constant>(Val) || isa<Argument>(Val))
return true;
@@ -827,7 +831,6 @@ bool HexagonCommonGEP::isInvariantIn(Value *Val, Loop *L) {
return DT->properlyDominates(DefB, HdrB);
}
-
bool HexagonCommonGEP::isInvariantIn(GepNode *Node, Loop *L) {
if (Node->Flags & GepNode::Root)
if (!isInvariantIn(Node->BaseVal, L))
@@ -835,7 +838,6 @@ bool HexagonCommonGEP::isInvariantIn(GepNode *Node, Loop *L) {
return isInvariantIn(Node->Idx, L);
}
-
bool HexagonCommonGEP::isInMainPath(BasicBlock *B, Loop *L) {
BasicBlock *HB = L->getHeader();
BasicBlock *LB = L->getLoopLatch();
@@ -847,21 +849,17 @@ bool HexagonCommonGEP::isInMainPath(BasicBlock *B, Loop *L) {
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();
- }
+static BasicBlock *preheader(DominatorTree *DT, Loop *L) {
+ if (BasicBlock *PH = L->getLoopPreheader())
+ return PH;
+ if (!OptSpeculate)
+ return nullptr;
+ DomTreeNode *DN = DT->getNode(L->getHeader());
+ if (!DN)
+ return nullptr;
+ 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,
@@ -911,10 +909,11 @@ BasicBlock *HexagonCommonGEP::adjustForInvariance(GepNode *Node,
return LocB;
}
-
namespace {
+
struct LocationAsBlock {
LocationAsBlock(const NodeToValueMap &L) : Map(L) {}
+
const NodeToValueMap &Map;
};
@@ -934,8 +933,8 @@ namespace {
inline bool is_constant(GepNode *N) {
return isa<ConstantInt>(N->Idx);
}
-}
+} // end anonymous namespace
void HexagonCommonGEP::separateChainForNode(GepNode *Node, Use *U,
NodeToValueMap &Loc) {
@@ -945,7 +944,7 @@ void HexagonCommonGEP::separateChainForNode(GepNode *Node, Use *U,
BasicBlock *PB = cast<Instruction>(R)->getParent();
GepNode *N = Node;
- GepNode *C = 0, *NewNode = 0;
+ GepNode *C = nullptr, *NewNode = nullptr;
while (is_constant(N) && !(N->Flags & GepNode::Root)) {
// XXX if (single-use) dont-replicate;
GepNode *NewN = new (*Mem) GepNode(N);
@@ -989,7 +988,6 @@ void HexagonCommonGEP::separateChainForNode(GepNode *Node, Use *U,
Uses[NewNode] = NewUs;
}
-
void HexagonCommonGEP::separateConstantChains(GepNode *Node,
NodeChildrenMap &NCM, NodeToValueMap &Loc) {
// First approximation: extract all chains.
@@ -1043,7 +1041,6 @@ void HexagonCommonGEP::separateConstantChains(GepNode *Node,
}
}
-
void HexagonCommonGEP::computeNodePlacement(NodeToValueMap &Loc) {
// Compute the inverse of the Node.Parent links. Also, collect the set
// of root nodes.
@@ -1078,7 +1075,6 @@ void HexagonCommonGEP::computeNodePlacement(NodeToValueMap &Loc) {
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()
@@ -1087,7 +1083,7 @@ Value *HexagonCommonGEP::fabricateGEP(NodeVect &NA, BasicBlock::iterator At,
GepNode *RN = NA[0];
assert((RN->Flags & GepNode::Root) && "Creating GEP for non-root");
- Value *NewInst = 0;
+ Value *NewInst = nullptr;
Value *Input = RN->BaseVal;
Value **IdxList = new Value*[Num+1];
unsigned nax = 0;
@@ -1126,7 +1122,6 @@ Value *HexagonCommonGEP::fabricateGEP(NodeVect &NA, BasicBlock::iterator At,
return NewInst;
}
-
void HexagonCommonGEP::getAllUsersForNode(GepNode *Node, ValueVect &Values,
NodeChildrenMap &NCM) {
NodeVect Work;
@@ -1151,7 +1146,6 @@ void HexagonCommonGEP::getAllUsersForNode(GepNode *Node, ValueVect &Values,
}
}
-
void HexagonCommonGEP::materialize(NodeToValueMap &Loc) {
DEBUG(dbgs() << "Nodes before materialization:\n" << Nodes << '\n');
NodeChildrenMap NCM;
@@ -1190,7 +1184,7 @@ void HexagonCommonGEP::materialize(NodeToValueMap &Loc) {
break;
GepNode *Child = CF->second.front();
BasicBlock *ChildB = cast_or_null<BasicBlock>(Loc[Child]);
- if (ChildB != 0 && LastB != ChildB)
+ if (ChildB != nullptr && LastB != ChildB)
break;
Last = Child;
} while (true);
@@ -1234,7 +1228,6 @@ void HexagonCommonGEP::materialize(NodeToValueMap &Loc) {
}
}
-
void HexagonCommonGEP::removeDeadCode() {
ValueVect BO;
BO.push_back(&Fn->front());
@@ -1263,7 +1256,6 @@ void HexagonCommonGEP::removeDeadCode() {
}
}
-
bool HexagonCommonGEP::runOnFunction(Function &F) {
if (skipFunction(F))
return false;
@@ -1302,9 +1294,10 @@ bool HexagonCommonGEP::runOnFunction(Function &F) {
return true;
}
-
namespace llvm {
+
FunctionPass *createHexagonCommonGEP() {
return new HexagonCommonGEP();
}
-}
+
+} // end namespace llvm
OpenPOWER on IntegriCloud