This is an archive of the discontinued LLVM Phabricator instance.

Paths

Table of Contentst

-
lib/Transforms/IPO/
-
Transforms/
-
IPO/
4/10
ConstantMerge.cpp
-
test/Transforms/ConstantMerge/
-
Transforms/
-
ConstantMerge/
4
initial-match.ll

Differential D50593

ConstantMerge: merge common initial sequences
AbandonedPublic

Authored by jfb on Aug 10 2018, 5:22 PM.

Download Raw Diff

Details

Reviewers

hiraditya

Summary

Global constants are currently merged only if they're idential, with appropriate update of their alignment and debug info, and only if semantically correct. We can do better by merging global constants which are 'smaller' into equivalent 'bigger' global constants, under the same update / semantic restrictions as before. This patch implements such merging for global constants with common initial sequences of the exact same type.

As noted in the patch there are other common global constant merging opportunities which this patch chooses not to pursue. They might pay off, but might be more computationally expensive.

Because the merged globals are constants this is a gain in final executable size, and can help reduce the dynamic amount of data cache usage because there might be some temporal redundancy in global constant access.

rdar://problem/43163738

Diff Detail

Repository

rL LLVM

Build Status

Buildable 21464
Build 21464: arc lint + arc unit

Event Timeline

jfb created this revision.Aug 10 2018, 5:22 PM

Herald added subscribers: llvm-commits, dexonsmith, JDevlieghere, aprantl. · View Herald TranscriptAug 10 2018, 5:22 PM

Harbormaster completed remote builds in B21354: Diff 160215.Aug 10 2018, 5:22 PM

Overall this is ready to review. I ran a bunch of tests and tried it out with asan, everything seems happy, but I'm a bit paranoid. I'm re-running the test-suite before / after the change to make sure everything works as I expect it to.

test/Transforms/ConstantMerge/initial-match.ll
79	I'll look into this soon :)

dmgreen added a subscriber: dmgreen.Aug 12 2018, 2:09 PM

hiraditya added a subscriber: hiraditya.Aug 14 2018, 5:51 AM

Have you tested this patch with some benchmarks or an open source project? What is the impact on compilation time?

lib/Transforms/IPO/ConstantMerge.cpp
111	if-else instead of switch?
181	Do we really need a goto here?
183	I think we should split the nested loop to separate function that may help remove goto.
test/Transforms/ConstantMerge/initial-match.ll
2	Can we reduce the size of this test case and maybe make multiple functions.

hiraditya added a reviewer: hiraditya.Aug 14 2018, 5:57 AM

xbolva00 added a subscriber: xbolva00.Aug 14 2018, 6:10 AM

xbolva00 added inline comments.

lib/Transforms/IPO/ConstantMerge.cpp
183	Yes, please split it.
365–366	while here, modernize to range based loop?
382	cannot we use for (for &I : CommonInitialSequenceRewrite)?

Address comments.

Harbormaster completed remote builds in B21464: Diff 160641.Aug 14 2018, 11:02 AM

In D50593#1198844, @hiraditya wrote:

Have you tested this patch with some benchmarks or an open source project? What is the impact on compilation time?

Yes! I did so over the weekend and then discarded my results on Monday because I'm Smart. I'll re-run a stage 2 bootstrap before / after.

lib/Transforms/IPO/ConstantMerge.cpp
111	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.
181	I like `goto` to break out of loop nests. :-)
183	Done... but I still like `goto` for loop nests.
382	`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.
test/Transforms/ConstantMerge/initial-match.ll
2	I could, but one of the goals is to make sure things work through multiple iterations of the outer `while` (because an earlier implementation I had didn't). If I break it up then you end up with some single-iteration things. These (if implemented improperly) would break as tested, but wouldn't break in single-iteration. In particular, `removeDeadConstantUsers` and `eraseFromParent` are trip hazards because they can invalidate values we discover. For example, you might be tempted to cache initial sequence matches found from one iteration to another (so you don't re-discover them every iteration), but that would break if `removeDeadConstantUsers` kicks in.

Do you have numbers of the size win? (maybe on clang/llvm itself)

test/Transforms/ConstantMerge/initial-match.ll
11–25	CHECK-NOT are really brittle, is there any way you can make this slightly more robust?

If you have the code-size numbers, please provide that then I can accept the patch.

In D50593#1228463, @hiraditya wrote:

If you have the code-size numbers, please provide that then I can accept the patch.

I want to get back to this after addressing a few related things. My main worry is that this is only useful with LTO because the linker should do this work otherwise, so at a minimum I need to change the code accordingly. I'm working on other ways to achieve the size wins I want, and then I'll fiddle with LTO to see how much can be done.

My main worry is that this is only useful with LTO because the linker should do this work otherwise, so at a minimum I need to change the code accordingly.

This is still useful even if it helps during LTO. As long as you have numbers to validate, it should be fine. We can add a flag to disable this by default.

vsk added a subscriber: vsk.Jan 22 2019, 11:11 AM

Herald added a subscriber: jkorous. · View Herald TranscriptJan 22 2019, 11:11 AM

This is probably still useful, if someone wants to pick it up.

Herald added a project: Restricted Project. · View Herald TranscriptAug 26 2020, 8:41 AM

Herald added a subscriber: ributzka. · View Herald Transcript

Revision Contents

Path

Size

lib/

Transforms/

IPO/

ConstantMerge.cpp

188 lines

test/

Transforms/

ConstantMerge/

initial-match.ll

150 lines

Diff 160641

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 Lines	static 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 Reply Inline Actions if-else instead of switch? hiraditya: if-else instead of switch?
		jfbAuthorUnsubmitted Not Done Reply Inline 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 Reply Inline Actions Do we really need a goto here? hiraditya: Do we really need a goto here?
		jfbAuthorUnsubmitted Not Done Reply Inline Actions I like `goto` to break out of loop nests. :-) jfb: I like `goto` to break out of loop nests. :-)
		return;
		};
		hiradityaUnsubmitted Done Reply Inline 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 Reply Inline Actions Yes, please split it. xbolva00: Yes, please split it.
		jfbAuthorUnsubmitted Not Done Reply Inline 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 Reply Inline 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 Reply Inline Actions cannot we use for (for &I : CommonInitialSequenceRewrite)? xbolva00: cannot we use for (for &I : CommonInitialSequenceRewrite)?
		jfbAuthorUnsubmitted Not Done Reply Inline 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

test/Transforms/ConstantMerge/initial-match.ll

This file was added.

				; RUN: opt -constmerge -S < %s \| FileCheck %s

				hiradityaUnsubmitted Not Done Reply Inline Actions Can we reduce the size of this test case and maybe make multiple functions. hiraditya: Can we reduce the size of this test case and maybe make multiple functions.
				jfbAuthorUnsubmitted Not Done Reply Inline Actions I could, but one of the goals is to make sure things work through multiple iterations of the outer `while` (because an earlier implementation I had didn't). If I break it up then you end up with some single-iteration things. These (if implemented improperly) would break as tested, but wouldn't break in single-iteration. In particular, `removeDeadConstantUsers` and `eraseFromParent` are trip hazards because they can invalidate values we discover. For example, you might be tempted to cache initial sequence matches found from one iteration to another (so you don't re-discover them every iteration), but that would break if `removeDeadConstantUsers` kicks in. jfb: I could, but one of the goals is to make sure things work through multiple iterations of the…
				; Test that constants with similar initial sequence of bytes are merged.

				%foo = type { i16, i8 }
				%baz = type { i16, i8, i8* }
				%bat = type { i16, i8, i8*, i16 }

				; Make sure these are entirely gone:

				; CHECK-NOT: bar_1
				; CHECK-NOT: bar_2
				; CHECK-NOT: bar_3
				; CHECK-NOT: bar_4
				; CHECK-NOT: bar_5
				; CHECK-NOT: bar_6
				; CHECK-NOT: bar_7
				; CHECK-NOT: bar_8_drop
				; CHECK-NOT: hello_drop
				; CHECK-NOT: hello_drop_me_too
				; CHECK-NOT: arr_2
				; CHECK-NOT: struct_1
				; CHECK-NOT: struct_2
				; CHECK-NOT: vec_2
				; CHECK-NOT: vec_ptr_1
				davideUnsubmitted Not Done Reply Inline Actions CHECK-NOT are really brittle, is there any way you can make this slightly more robust? davide: CHECK-NOT are really brittle, is there any way you can make this slightly more robust?

				; Make sure only these are present:

				; CHECK: @unused = constant
				; CHECK-NEXT: @different = private unnamed_addr constant
				; CHECK-NEXT: @bar_8_keep = private unnamed_addr constant
				; CHECK-NEXT: @helloer = private unnamed_addr constant
				; CHECK-NEXT: @helloworld = private unnamed_addr constant

				; This one is tricky because it contains references to other global constants which should get replaced.
				; CHECK-NEXT: @arr_3 = private unnamed_addr constant [3 x i8] [{{.}} @helloworld, {{.}} @helloer, {{.}} @helloworld, {{.*}}], align 32

				; CHECK-NEXT: @struct_3 = private unnamed_addr constant %bat { i16 42, i8 69, i8* getelementptr inbounds ([12 x i8], [12 x i8]* @helloworld, i64 0, i64 0), i16 1337 }
				; CHECK-NEXT: @vec_3 = private unnamed_addr constant <3 x i32> <i32 69, i32 1337, i32 42>
				; CHECK-NEXT: @vec_ptr_2 = private unnamed_addr constant <2 x <2 x i32>> <<2 x i32> bitcast (<3 x i32>* @vec_3 to <2 x i32>), <2 x i32> bitcast (<3 x i32>* @vec_3 to <2 x i32>*)>

				; CHECK-NEXT: @last = constant i32 1337

				@unused = constant i32 42

				@bar_1 = private unnamed_addr constant [1 x %foo] [%foo { i16 257, i8 1 }], align 2
				@bar_2 = private unnamed_addr constant [2 x %foo] [%foo { i16 257, i8 1 }, %foo { i16 257, i8 1 }], align 2
				@different = private unnamed_addr constant [2 x %foo] [%foo { i16 257, i8 1 }, %foo { i16 257, i8 42 }], align 2
				@bar_2_electric_boogaloo = private unnamed_addr constant [2 x %foo] [%foo { i16 257, i8 1 }, %foo { i16 257, i8 1 }], align 2
				@bar_3 = private unnamed_addr constant [3 x %foo] [%foo { i16 257, i8 1 }, %foo { i16 257, i8 1 }, %foo { i16 257, i8 1 }], align 2
				@bar_4 = private unnamed_addr constant [4 x %foo] [%foo { i16 257, i8 1 }, %foo { i16 257, i8 1 }, %foo { i16 257, i8 1 }, %foo { i16 257, i8 1 }], align 16
				@bar_5 = private unnamed_addr constant [5 x %foo] [%foo { i16 257, i8 1 }, %foo { i16 257, i8 1 }, %foo { i16 257, i8 1 }, %foo { i16 257, i8 1 }, %foo { i16 257, i8 1 }], align 16
				@bar_6 = private unnamed_addr constant [6 x %foo] [%foo { i16 257, i8 1 }, %foo { i16 257, i8 1 }, %foo { i16 257, i8 1 }, %foo { i16 257, i8 1 }, %foo { i16 257, i8 1 }, %foo { i16 257, i8 1 }], align 16
				@bar_7 = private unnamed_addr constant [7 x %foo] [%foo { i16 257, i8 1 }, %foo { i16 257, i8 1 }, %foo { i16 257, i8 1 }, %foo { i16 257, i8 1 }, %foo { i16 257, i8 1 }, %foo { i16 257, i8 1 }, %foo { i16 257, i8 1 }], align 16
				@bar_8_drop = private unnamed_addr constant [8 x %foo] [%foo { i16 257, i8 1 }, %foo { i16 257, i8 1 }, %foo { i16 257, i8 1 }, %foo { i16 257, i8 1 }, %foo { i16 257, i8 1 }, %foo { i16 257, i8 1 }, %foo { i16 257, i8 1 }, %foo { i16 257, i8 1 }], align 16
				@bar_8_keep = private unnamed_addr constant [8 x %foo] [%foo { i16 257, i8 1 }, %foo { i16 257, i8 1 }, %foo { i16 257, i8 1 }, %foo { i16 257, i8 1 }, %foo { i16 257, i8 1 }, %foo { i16 257, i8 1 }, %foo { i16 257, i8 1 }, %foo { i16 257, i8 1 }], align 16

				@hello_drop = private unnamed_addr constant [5 x i8] c"hello", align 1
				@hello_drop_me_too = private unnamed_addr constant [5 x i8] c"hello", align 1
				@helloer = private unnamed_addr constant [7 x i8] c"helloer", align 1
				@helloworld = private unnamed_addr constant [12 x i8] c"hello world!", align 1

				@arr_2 = private unnamed_addr constant [2 x i8] [i8 getelementptr inbounds ([5 x i8], [5 x i8]* @hello_drop, i64 0, i64 0), i8* getelementptr inbounds ([7 x i8], [7 x i8]* @helloer, i64 0, i64 0)], align 32
				@arr_3 = private unnamed_addr constant [3 x i8] [i8 getelementptr inbounds ([5 x i8], [5 x i8]* @hello_drop, i64 0, i64 0), i8* getelementptr inbounds ([7 x i8], [7 x i8]* @helloer, i64 0, i64 0), i8* getelementptr inbounds ([5 x i8], [5 x i8]* @hello_drop_me_too, i64 0, i64 0)], align 16

				@struct_1 = private unnamed_addr constant %foo { i16 42, i8 69 }
				@struct_2 = private unnamed_addr constant %baz { i16 42, i8 69, i8* getelementptr inbounds ([5 x i8], [5 x i8]* @hello_drop_me_too, i64 0, i64 0) }
				@struct_3 = private unnamed_addr constant %bat { i16 42, i8 69, i8* getelementptr inbounds ([5 x i8], [5 x i8]* @hello_drop, i64 0, i64 0), i16 1337 }

				@vec_2 = private unnamed_addr constant <2 x i32> <i32 69, i32 1337>
				@vec_3 = private unnamed_addr constant <3 x i32> <i32 69, i32 1337, i32 42>

				@vec_ptr_1 = private unnamed_addr constant <1 x <2 x i32>> <<2 x i32> @vec_2>
				@vec_ptr_2 = private unnamed_addr constant <2 x <2 x i32>> <<2 x i32> @vec_2, <2 x i32>* @vec_2>

				; FIXME: test that two zeroinitializer things get common initial sequence deduplication. Ditto undef.

				@last = constant i32 1337

				jfbAuthorUnsubmitted Not Done Reply Inline Actions I'll look into this soon :) jfb: I'll look into this soon :)
				declare void @usefoo(%foo*)
				declare void @usebaz(%baz*)
				declare void @usebat(%bat*)
				declare void @usefoo1([1 x %foo]*)
				declare void @usefoo2([2 x %foo]*)
				declare void @usefoo3([3 x %foo]*)
				declare void @usefoo4([4 x %foo]*)
				declare void @usefoo5([5 x %foo]*)
				declare void @usefoo6([6 x %foo]*)
				declare void @usefoo7([7 x %foo]*)
				declare void @usefoo8([8 x %foo]*)
				declare void @usei8(i8*)
				declare void @usei8_5([5 x i8]*)
				declare void @usei8_7([7 x i8]*)
				declare void @usei8_12([12 x i8]*)
				declare void @usearr2([2 x i8])
				declare void @usearr3([3 x i8])
				declare void @usevec2(<2 x i32>*)
				declare void @usevec3(<3 x i32>*)
				declare void @usevecptr1(<1 x <2 x i32>>)
				declare void @usevecptr2(<2 x <2 x i32>>)

				define i32 @main() { ; CHECK-LABEL: @main()
				entry: ; CHECK-LABEL: entry
				tail call void @usefoo(%foo* getelementptr inbounds ([1 x %foo], [1 x %foo]* @bar_1, i64 0, i64 0)) ; CHECK-NEXT: tail call void @usefoo({{.*}}@bar_8_keep, i64 0, i64 0))
				tail call void @usefoo(%foo* getelementptr inbounds ([2 x %foo], [2 x %foo]* @bar_2, i64 0, i64 0)) ; CHECK-NEXT: tail call void @usefoo({{.*}}@bar_8_keep, i64 0, i64 0))
				tail call void @usefoo(%foo* getelementptr inbounds ([2 x %foo], [2 x %foo]* @different, i64 0, i64 0)) ; CHECK-NEXT: tail call void @usefoo({{.*}}@different, i64 0, i64 0))
				tail call void @usefoo(%foo* getelementptr inbounds ([2 x %foo], [2 x %foo]* @bar_2_electric_boogaloo, i64 0, i64 0)) ; CHECK-NEXT: tail call void @usefoo({{.*}}@bar_8_keep, i64 0, i64 0))
				tail call void @usefoo(%foo* getelementptr inbounds ([3 x %foo], [3 x %foo]* @bar_3, i64 0, i64 0)) ; CHECK-NEXT: tail call void @usefoo({{.*}}@bar_8_keep, i64 0, i64 0))
				tail call void @usefoo(%foo* getelementptr inbounds ([4 x %foo], [4 x %foo]* @bar_4, i64 0, i64 0)) ; CHECK-NEXT: tail call void @usefoo({{.*}}@bar_8_keep, i64 0, i64 0))
				tail call void @usefoo(%foo* getelementptr inbounds ([5 x %foo], [5 x %foo]* @bar_5, i64 0, i64 0)) ; CHECK-NEXT: tail call void @usefoo({{.*}}@bar_8_keep, i64 0, i64 0))
				tail call void @usefoo(%foo* getelementptr inbounds ([6 x %foo], [6 x %foo]* @bar_6, i64 0, i64 0)) ; CHECK-NEXT: tail call void @usefoo({{.*}}@bar_8_keep, i64 0, i64 0))
				tail call void @usefoo(%foo* getelementptr inbounds ([7 x %foo], [7 x %foo]* @bar_7, i64 0, i64 0)) ; CHECK-NEXT: tail call void @usefoo({{.*}}@bar_8_keep, i64 0, i64 0))
				tail call void @usefoo(%foo* getelementptr inbounds ([8 x %foo], [8 x %foo]* @bar_8_drop, i64 0, i64 0)) ; CHECK-NEXT: tail call void @usefoo({{.*}}@bar_8_keep, i64 0, i64 0))
				tail call void @usefoo(%foo* getelementptr inbounds ([8 x %foo], [8 x %foo]* @bar_8_keep, i64 0, i64 0)) ; CHECK-NEXT: tail call void @usefoo({{.*}}@bar_8_keep, i64 0, i64 0))

				tail call void @usefoo1([1 x %foo]* @bar_1) ; CHECK-NEXT: tail call void @usefoo1({{.}} bitcast {{.}}@bar_8_keep
				tail call void @usefoo2([2 x %foo]* @bar_2) ; CHECK-NEXT: tail call void @usefoo2({{.}} bitcast {{.}}@bar_8_keep
				tail call void @usefoo2([2 x %foo]* @different) ; CHECK-NEXT: tail call void @usefoo2([2 x %foo]* @different)
				tail call void @usefoo2([2 x %foo]* @bar_2_electric_boogaloo) ; CHECK-NEXT: tail call void @usefoo2({{.}} bitcast {{.}}@bar_8_keep
				tail call void @usefoo3([3 x %foo]* @bar_3) ; CHECK-NEXT: tail call void @usefoo3({{.}} bitcast {{.}}@bar_8_keep
				tail call void @usefoo4([4 x %foo]* @bar_4) ; CHECK-NEXT: tail call void @usefoo4({{.}} bitcast {{.}}@bar_8_keep
				tail call void @usefoo5([5 x %foo]* @bar_5) ; CHECK-NEXT: tail call void @usefoo5({{.}} bitcast {{.}}@bar_8_keep
				tail call void @usefoo6([6 x %foo]* @bar_6) ; CHECK-NEXT: tail call void @usefoo6({{.}} bitcast {{.}}@bar_8_keep
				tail call void @usefoo7([7 x %foo]* @bar_7) ; CHECK-NEXT: tail call void @usefoo7({{.}} bitcast {{.}}@bar_8_keep
				tail call void @usefoo8([8 x %foo]* @bar_8_drop) ; CHECK-NEXT: tail call void @usefoo8([8 x %foo]* @bar_8_keep)
				tail call void @usefoo8([8 x %foo]* @bar_8_keep) ; CHECK-NEXT: tail call void @usefoo8([8 x %foo]* @bar_8_keep)

				tail call void @usei8(i8* getelementptr inbounds ([5 x i8], [5 x i8]* @hello_drop, i64 0, i64 0)) ; CHECK-NEXT: tail call void @usei8({{.*}}@helloworld, i64 0, i64 0))
				tail call void @usei8(i8* getelementptr inbounds ([7 x i8], [7 x i8]* @helloer, i64 0, i64 0)) ; CHECK-NEXT: tail call void @usei8({{.*}}@helloer, i64 0, i64 0))
				tail call void @usei8(i8* getelementptr inbounds ([12 x i8], [12 x i8]* @helloworld, i64 0, i64 0)) ; CHECK-NEXT: tail call void @usei8({{.*}}@helloworld, i64 0, i64 0))

				tail call void @usei8_5([5 x i8]* @hello_drop) ; CHECK-NEXT: tail call void @usei8_5({{.}} bitcast {{.}}@helloworld
				tail call void @usei8_7([7 x i8]* @helloer) ; CHECK-NEXT: tail call void @usei8_7([7 x i8]* @helloer)
				tail call void @usei8_12([12 x i8]* @helloworld) ; CHECK-NEXT: tail call void @usei8_12([12 x i8]* @helloworld)

				tail call void @usearr2([2 x i8] @arr_2) ; CHECK-NEXT: tail call void @usearr2([2 x i8] bitcast ([3 x i8] @arr_3 to [2 x i8]))
				tail call void @usearr3([3 x i8] @arr_3) ; CHECK-NEXT: tail call void @usearr3([3 x i8] @arr_3)

				tail call void @usefoo(%foo* @struct_1) ; CHECK-NEXT: tail call void @usefoo(%foo* bitcast (%bat* @struct_3 to %foo*))
				tail call void @usebaz(%baz* @struct_2) ; CHECK-NEXT: tail call void @usebaz(%baz* bitcast (%bat* @struct_3 to %baz*))
				tail call void @usebat(%bat* @struct_3) ; CHECK-NEXT: tail call void @usebat(%bat* @struct_3)

				tail call void @usevec2(<2 x i32>* @vec_2) ; CHECK-NEXT: tail call void @usevec2(<2 x i32>* bitcast (<3 x i32>* @vec_3 to <2 x i32>*))
				tail call void @usevec3(<3 x i32>* @vec_3) ; CHECK-NEXT: tail call void @usevec3(<3 x i32>* @vec_3)

				tail call void @usevecptr1(<1 x <2 x i32>> @vec_ptr_1) ; CHECK-NEXT: tail call void @usevecptr1(<1 x <2 x i32>> bitcast (<2 x <2 x i32>> @vec_ptr_2 to <1 x <2 x i32>>))
				tail call void @usevecptr2(<2 x <2 x i32>> @vec_ptr_2) ; CHECK-NEXT: tail call void @usevecptr2(<2 x <2 x i32>> @vec_ptr_2)

				ret i32 0
				}