Page MenuHomePhabricator

Please use GitHub pull requests for new patches. Phabricator shutdown timeline

Differential D50593 Diff 160641 lib/Transforms/IPO/ConstantMerge.cpp

Changeset View

Standalone View

View Options

lib/Transforms/IPO/ConstantMerge.cpp

Show All 13 Lines
// //
// Algorithm: ConstantMerge is designed to build up a map of available constants // Algorithm: ConstantMerge is designed to build up a map of available constants
// and eliminate duplicates when it is initialized. // and eliminate duplicates when it is initialized.
// //
//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
#include "llvm/Transforms/IPO/ConstantMerge.h" #include "llvm/Transforms/IPO/ConstantMerge.h"
#include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h" #include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h" #include "llvm/ADT/Statistic.h"
#include "llvm/IR/Constants.h" #include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h" #include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h" #include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/GlobalValue.h" #include "llvm/IR/GlobalValue.h"
#include "llvm/IR/GlobalVariable.h" #include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/LLVMContext.h" #include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h" #include "llvm/IR/Module.h"
#include "llvm/Pass.h" #include "llvm/Pass.h"
#include "llvm/Support/Casting.h" #include "llvm/Support/Casting.h"
#include "llvm/Transforms/IPO.h" #include "llvm/Transforms/IPO.h"
#include <algorithm> #include <algorithm>
#include <cassert> #include <cassert>
#include <utility> #include <utility>
using namespace llvm; using namespace llvm;
#define DEBUG_TYPE "constmerge" #define DEBUG_TYPE "constmerge"
STATISTIC(NumIdenticalMerged, "Number of identical global constants merged"); STATISTIC(NumIdenticalMerged, "Number of identical global constants merged");
STATISTIC(NumCommonInitialSequenceMerged,
"Number of global constants with common initial sequence merged");
/// Find values that are marked as llvm.used. /// Find values that are marked as llvm.used.
static void FindUsedValues(GlobalVariable *LLVMUsed, static void FindUsedValues(GlobalVariable *LLVMUsed,
SmallPtrSetImpl<const GlobalValue*> &UsedValues) { SmallPtrSetImpl<const GlobalValue*> &UsedValues) {
if (!LLVMUsed) return; if (!LLVMUsed) return;
ConstantArray *Inits = cast<ConstantArray>(LLVMUsed->getInitializer()); ConstantArray *Inits = cast<ConstantArray>(LLVMUsed->getInitializer());
for (unsigned i = 0, e = Inits->getNumOperands(); i != e; ++i) { for (unsigned i = 0, e = Inits->getNumOperands(); i != e; ++i) {
▲ Show 20 Lines • Show All 46 Lines • ▼ Show 20 Linesstatic CanMerge makeMergeable(GlobalVariable *Old, GlobalVariable *New) {
if (hasMetadataOtherThanDebugLoc(Old)) if (hasMetadataOtherThanDebugLoc(Old))
return CanMerge::No; return CanMerge::No;
assert(!hasMetadataOtherThanDebugLoc(New)); assert(!hasMetadataOtherThanDebugLoc(New));
if (!Old->hasGlobalUnnamedAddr()) if (!Old->hasGlobalUnnamedAddr())
New->setUnnamedAddr(GlobalValue::UnnamedAddr::None); New->setUnnamedAddr(GlobalValue::UnnamedAddr::None);
return CanMerge::Yes; return CanMerge::Yes;
} }
static void replace(Module &M, GlobalVariable *Old, GlobalVariable *New) { enum class CommonSequence { Same, Initial };
Constant *NewConstant = New; const char *toString(CommonSequence S) {
switch (S) {
hiradityaUnsubmitted
Not Done
ReplyInline Actions

if-else instead of switch?

hiraditya: if-else instead of switch?
jfbAuthorUnsubmitted
Not Done
ReplyInline Actions

This is on purpose: a switch without default will cause a diagnostic if a new entry is added to the enum class but isn't handled here.

jfb: This is on purpose: a `switch` without `default` will cause a diagnostic if a new entry is…
case CommonSequence::Same:
return "same";
case CommonSequence::Initial:
return "common initial sequence";
}
}
LLVM_DEBUG(dbgs() << "Replacing global: @" << Old->getName() << " -> @" static void replace(Module &M, GlobalVariable *Old, GlobalVariable *New,
<< New->getName() << "\n"); CommonSequence Common) {
Constant *NewConstant;
switch (Common) {
case CommonSequence::Same:
NewConstant = New;
break;
case CommonSequence::Initial:
NewConstant =
ConstantExpr::getCast(Instruction::BitCast, New, Old->getType());
break;
}
LLVM_DEBUG(dbgs() << "Replacing " << toString(Common) << " global: @"
<< Old->getName() << " -> @" << New->getName() << "\n");
// Bump the alignment if necessary. // Bump the alignment if necessary.
if (Old->getAlignment() || New->getAlignment()) if (Old->getAlignment() || New->getAlignment())
New->setAlignment(std::max(getAlignment(Old), getAlignment(New))); New->setAlignment(std::max(getAlignment(Old), getAlignment(New)));
copyDebugLocMetadata(Old, New); copyDebugLocMetadata(Old, New);
Old->replaceAllUsesWith(NewConstant); Old->replaceAllUsesWith(NewConstant);
// Delete the global value from the module. // Delete the global value from the module.
assert(Old->hasLocalLinkage() && assert(Old->hasLocalLinkage() &&
"Refusing to delete an externally visible global variable."); "Refusing to delete an externally visible global variable.");
Old->eraseFromParent(); Old->eraseFromParent();
} }
template <typename Container>
static void findCommonInitialSequence(
MapVector<Constant *, Constant *> &CommonInitialSequenceRewrite,
Container &Initializers) {
using Contained = typename Container::value_type;
// We only deduplicate array-like / sequenced types with the same element
// type, and we try to deduplicate to the larger of all potential prefix
// matches. Sorting by size means we can look at the larger ones first.
std::stable_sort(
Initializers.begin(), Initializers.end(), [](Contained L, Contained R) {
return L->getType()->getNumElements() > R->getType()->getNumElements();
});
auto different = [](Contained L, Contained R, unsigned Size) {
for (unsigned Idx = 0; Idx != Size; ++Idx)
if (L->getAggregateElement(Idx) != R->getAggregateElement(Idx))
return true;
return false;
};
auto registerBiggerMatchFor = [&](Contained Smaller,
unsigned SmallerNumElements) {
for (Contained *Bigger = Initializers.begin();; ++Bigger) {
auto *BiggerTy = (*Bigger)->getType();
unsigned BiggerNumElements = BiggerTy->getNumElements();
if (SmallerNumElements >= BiggerNumElements)
return;
if (different(Smaller, *Bigger, SmallerNumElements))
continue;
LLVM_DEBUG(dbgs() << "Common initial sequence: " << *Smaller << " -> "
<< **Bigger << "\n");
CommonInitialSequenceRewrite[Smaller] = *Bigger;
return;
}
hiradityaUnsubmitted
Done
ReplyInline Actions

Do we really need a goto here?

hiraditya: Do we really need a goto here?
jfbAuthorUnsubmitted
Not Done
ReplyInline Actions

I like goto to break out of loop nests. :-)

jfb: I like `goto` to break out of loop nests. :-)
return;
};
hiradityaUnsubmitted
Done
ReplyInline Actions

I think we should split the nested loop to separate function that may help remove goto.

hiraditya: I think we should split the nested loop to separate function that may help remove goto.
xbolva00Unsubmitted
Done
ReplyInline Actions

Yes, please split it.

xbolva00: Yes, please split it.
jfbAuthorUnsubmitted
Not Done
ReplyInline Actions

Done... but I still like goto for loop nests.

jfb: Done... but I still like `goto` for loop nests.
for (auto Smaller = Initializers.rbegin(), LastSmaller = Initializers.rend();
Smaller != LastSmaller; ++Smaller) {
if (CommonInitialSequenceRewrite.find(*Smaller) !=
CommonInitialSequenceRewrite.end())
continue;
registerBiggerMatchFor(*Smaller, (*Smaller)->getType()->getNumElements());
}
}
template <typename Container>
static void findCommonInitialSequenceForEach(
MapVector<Constant *, Constant *> &CommonInitialSequenceRewrite,
Container &Con) {
for (auto &Pair : Con)
findCommonInitialSequence(CommonInitialSequenceRewrite, Pair.second);
}
static bool mergeConstants(Module &M) { static bool mergeConstants(Module &M) {
// Find all the globals that are marked "used". These cannot be merged. // Find all the globals that are marked "used". These cannot be merged.
SmallPtrSet<const GlobalValue*, 8> UsedGlobals; SmallPtrSet<const GlobalValue*, 8> UsedGlobals;
FindUsedValues(M.getGlobalVariable("llvm.used"), UsedGlobals); FindUsedValues(M.getGlobalVariable("llvm.used"), UsedGlobals);
FindUsedValues(M.getGlobalVariable("llvm.compiler.used"), UsedGlobals); FindUsedValues(M.getGlobalVariable("llvm.compiler.used"), UsedGlobals);
// Map unique constants to globals. // Map unique constants to globals.
DenseMap<Constant *, GlobalVariable *> CMap; DenseMap<Constant *, GlobalVariable *> CMap;
SmallVector<std::pair<GlobalVariable *, GlobalVariable *>, 32> SmallVector<std::pair<GlobalVariable *, GlobalVariable *>, 32>
SameContentReplacements; SameContentReplacements;
// Keep track of constant array-like / sequenced initializers because they're
// candidates for common sequence deduplication. We restrict ourselves in the
// following way:
//
// - Only try to deduplicate the ones with the same element types instead
// of guessing at byte-level layout. This reduced how many things we
// compare.
// - Don't look for constant scalars which are duplicated in non-scalars.
// - Don't try to find tail sequences which match (this would benefit null
// terminated strings).
// - Don't try to find internal sequences which match.
// - Greedily match shorter sequences with the longest one we can find,
// even though it might be better to match with a shorter one.
// - Don't treat undef as a wildcard which can match any value.
//
// Lifting these restrictions might be profitable.
DenseMap<Type *, SmallVector<ConstantDataArray *, 4>> CDAs;
DenseMap<Type *, SmallVector<ConstantDataVector *, 4>> CDVs;
DenseMap<Type *, SmallVector<ConstantArray *, 4>> CAs;
DenseMap<Type *, SmallVector<ConstantVector *, 4>> CVs;
SmallVector<ConstantStruct *, 4> CSs;
MapVector<Constant *, Constant *> CommonInitialSequenceRewrite;
auto watchConstant = [&](Constant *WatchMe) {
if (auto *I = dyn_cast<ConstantDataArray>(WatchMe))
CDAs[I->getType()->getArrayElementType()].push_back(I);
else if (auto *I = dyn_cast<ConstantDataVector>(WatchMe))
CDVs[I->getType()->getElementType()].push_back(I);
else if (auto *I = dyn_cast<ConstantArray>(WatchMe))
CAs[I->getType()->getArrayElementType()].push_back(I);
else if (auto *I = dyn_cast<ConstantVector>(WatchMe))
CVs[I->getType()->getElementType()].push_back(I);
else if (auto *I = dyn_cast<ConstantStruct>(WatchMe))
CSs.push_back(I);
};
auto findAllCommonInitialSequences = [&]() {
findCommonInitialSequenceForEach(CommonInitialSequenceRewrite, CDAs);
findCommonInitialSequenceForEach(CommonInitialSequenceRewrite, CDVs);
findCommonInitialSequenceForEach(CommonInitialSequenceRewrite, CAs);
findCommonInitialSequenceForEach(CommonInitialSequenceRewrite, CVs);
findCommonInitialSequence(CommonInitialSequenceRewrite, CSs);
};
auto clearAllCommonInitialSequences = [&]() {
CDAs.clear();
CDVs.clear();
CAs.clear();
CVs.clear();
CSs.clear();
CommonInitialSequenceRewrite.clear();
};
size_t ChangesMade = 0; size_t ChangesMade = 0;
size_t OldChangesMade = 0; size_t OldChangesMade = 0;
// Iterate constant merging while we are still making progress. Merging two // Iterate constant merging while we are still making progress. Merging two
// constants together may allow us to merge other constants together if the // constants together may allow us to merge other constants together if the
// second level constants have initializers which point to the globals that // second level constants have initializers which point to the globals that
// were just merged. // were just merged.
while (true) { while (true) {
Show All 36 Lines for (Module::global_iterator GVI = M.global_begin(), E = M.global_end();
// If this is the first constant we find or if the old one is local, // If this is the first constant we find or if the old one is local,
// replace with the current one. If the current is externally visible // replace with the current one. If the current is externally visible
// it cannot be replace, but can be the canonical constant we merge with. // it cannot be replace, but can be the canonical constant we merge with.
bool FirstConstantFound = !Slot; bool FirstConstantFound = !Slot;
if (FirstConstantFound || IsBetterCanonical(*GV, *Slot)) { if (FirstConstantFound || IsBetterCanonical(*GV, *Slot)) {
Slot = GV; Slot = GV;
LLVM_DEBUG(dbgs() << "Cmap[" << *Init << "] = " << GV->getName() LLVM_DEBUG(dbgs() << "Cmap[" << *Init << "] = " << GV->getName()
<< (FirstConstantFound ? "\n" : " (updated)\n")); << (FirstConstantFound ? "\n" : " (updated)\n"));
if (FirstConstantFound)
watchConstant(Init);
} }
} }
// Find initializers which have a common initial sequence.
findAllCommonInitialSequences();
// Identify all globals that can be merged together, filling in the // Identify all globals that can be merged together, filling in the
// SameContentReplacements vector. We cannot do the replacement in this pass // SameContentReplacements vector. We cannot do the replacement in this pass
// because doing so may cause initializers of other globals to be rewritten, // because doing so may cause initializers of other globals to be rewritten,
// invalidating the Constant* pointers in CMap. // invalidating the Constant* pointers in CMap.
for (Module::global_iterator GVI = M.global_begin(), E = M.global_end(); for (Module::global_iterator GVI = M.global_begin(), E = M.global_end();
GVI != E; ) { GVI != E; ) {
GlobalVariable *GV = &*GVI++; GlobalVariable *GV = &*GVI++;
Show All 22 Lines for (Module::global_iterator GVI = M.global_begin(), E = M.global_end();
if (makeMergeable(GV, Slot) == CanMerge::No) if (makeMergeable(GV, Slot) == CanMerge::No)
continue; continue;
// Make all uses of the duplicate constant use the canonical version. // Make all uses of the duplicate constant use the canonical version.
LLVM_DEBUG(dbgs() << "Will replace: @" << GV->getName() << " -> @" LLVM_DEBUG(dbgs() << "Will replace: @" << GV->getName() << " -> @"
<< Slot->getName() << "\n"); << Slot->getName() << "\n");
SameContentReplacements.push_back(std::make_pair(GV, Slot)); SameContentReplacements.push_back(std::make_pair(GV, Slot));
} }
// Now that we have figured out which replacements must be made, do them all // Now that we have figured out which replacements must be made, do them
xbolva00Unsubmitted
Done
ReplyInline Actions

while here, modernize to range based loop?

xbolva00: while here, modernize to range based loop?
// now. This avoid invalidating the pointers in CMap, which are unneeded // all. Do the replacements where initializers are the exactly same,
// now. // updating the pointers in CMap for common sequence replacement.
for (unsigned i = 0, e = SameContentReplacements.size(); i != e; ++i) { for (auto &&R : SameContentReplacements) {
GlobalVariable *Old = SameContentReplacements[i].first; GlobalVariable *Old = R.first;
GlobalVariable *New = SameContentReplacements[i].second; GlobalVariable *New = R.second;
replace(M, Old, New); Constant *OldInitializer = Old->getInitializer();
replace(M, Old, New, CommonSequence::Same);
LLVM_DEBUG(dbgs() << "Cmap[" << *OldInitializer
<< "] = " << New->getName() << " (same updated)\n");
CMap[OldInitializer] = New;
++ChangesMade; ++ChangesMade;
++NumIdenticalMerged; ++NumIdenticalMerged;
} }
// We might have dropped some constant in a previous iteration or through
// an exact match. No need to consider them again.
xbolva00Unsubmitted
Not Done
ReplyInline Actions

cannot we use for (for &I : CommonInitialSequenceRewrite)?

xbolva00: cannot we use for (for &I : CommonInitialSequenceRewrite)?
jfbAuthorUnsubmitted
Not Done
ReplyInline Actions

erase needs an iterator, and I was previously using another container type. Now that I use MapVector it's better to do a first-pass erase_if and then do the rest of the loop with a range-based for, so I updated the code to do so.

jfb: `erase` needs an iterator, and I was previously using another container type. Now that I use…
CommonInitialSequenceRewrite.remove_if(
[&](std::pair<Constant *, Constant *> &P) {
return CMap.find(P.first) == CMap.end() ||
CMap.find(P.second) == CMap.end();
});
// Replacements where initializers have a common initial sequence.
for (auto &&I : CommonInitialSequenceRewrite) {
GlobalVariable *Old = CMap.find(I.first)->second;
GlobalVariable *New = CMap.find(I.second)->second;
if (makeMergeable(Old, New) == CanMerge::No)
continue;
Constant *OldInitializer = Old->getInitializer();
replace(M, Old, New, CommonSequence::Initial);
LLVM_DEBUG(dbgs() << "Cmap[" << *OldInitializer
<< "] = " << New->getName()
<< " (common initial sequence updated)\n");
CMap[OldInitializer] = New;
++NumCommonInitialSequenceMerged;
++ChangesMade;
}
if (ChangesMade == OldChangesMade) if (ChangesMade == OldChangesMade)
break; break;
OldChangesMade = ChangesMade; OldChangesMade = ChangesMade;
SameContentReplacements.clear(); SameContentReplacements.clear();
CMap.clear(); CMap.clear();
clearAllCommonInitialSequences();
} }
return ChangesMade; return ChangesMade;
} }
PreservedAnalyses ConstantMergePass::run(Module &M, ModuleAnalysisManager &) { PreservedAnalyses ConstantMergePass::run(Module &M, ModuleAnalysisManager &) {
if (!mergeConstants(M)) if (!mergeConstants(M))
return PreservedAnalyses::all(); return PreservedAnalyses::all();
Show All 31 Lines