src/ld/passes/code_dedup.cpp

/* -*- mode: C++; c-basic-offset: 4; tab-width: 4 -*-
 *
 * Copyright (c) 2015 Apple Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 *
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this
 * file.
 *
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 *
 * @APPLE_LICENSE_HEADER_END@
 */


#include <stdint.h>
#include <math.h>
#include <unistd.h>
#include <dlfcn.h>
#include <mach/machine.h>

#include <vector>
#include <map>
#include <algorithm>
#include <unordered_map>

#include "ld.hpp"
#include "code_dedup.h"

namespace ld {
namespace passes {
namespace dedup {


class DeDupAliasAtom : public ld::Atom
{
public:
										DeDupAliasAtom(const ld::Atom* dupOf, const ld::Atom* replacement) :
											ld::Atom(dupOf->section(), ld::Atom::definitionRegular, ld::Atom::combineNever,
													dupOf->scope(), dupOf->contentType(), ld::Atom::symbolTableIn,
													false, false, true, 0),
											_dedupOf(dupOf),
											_fixup(0, ld::Fixup::k1of1, ld::Fixup::kindNoneFollowOn, ld::Fixup::bindingDirectlyBound, replacement) {
                                                if ( dupOf->autoHide() )
                                                    setAutoHide();
                                            }

	virtual const ld::File*				file() const		{ return _dedupOf->file(); }
	virtual const char*					translationUnitSource() const
															{ return NULL; }
	virtual const char*					name() const		{ return _dedupOf->name(); }
	virtual uint64_t					size() const		{ return 0; }
	virtual uint64_t					objectAddress() const { return 0; }
	virtual void						copyRawContent(uint8_t buffer[]) const { }
	virtual ld::Fixup::iterator			fixupsBegin() const	{ return &((ld::Fixup*)&_fixup)[0]; }
	virtual ld::Fixup::iterator			fixupsEnd()	const	{ return &((ld::Fixup*)&_fixup)[1]; }

private:
	const ld::Atom*                     _dedupOf;
	ld::Fixup							_fixup;
};


namespace {
    typedef std::unordered_map<const ld::Atom*, unsigned long> CachedHashes;

    ld::Internal*   sState = nullptr;
    CachedHashes    sSavedHashes;
    unsigned long   sHashCount = 0;
    unsigned long   sFixupCompareCount = 0;
};


// A helper for std::unordered_map<> that hashes the instructions of a function
struct atom_hashing {

    static unsigned long hash(const ld::Atom* atom) {
        auto pos = sSavedHashes.find(atom);
        if ( pos != sSavedHashes.end() )
            return pos->second;

        const unsigned instructionBytes = atom->size();
        const uint8_t*	instructions = atom->rawContentPointer();
        unsigned long hash = instructionBytes;
        for (unsigned i=0; i < instructionBytes; ++i) {
            hash = (hash * 33) + instructions[i];
        }
		for (ld::Fixup::iterator fit = atom->fixupsBegin(), end=atom->fixupsEnd(); fit != end; ++fit) {
            const Atom* target = NULL;
            switch ( fit->binding ) {
                case ld::Fixup::bindingDirectlyBound:
                    target = fit->u.target;
                    break;
                case ld::Fixup::bindingsIndirectlyBound:
                    target = sState->indirectBindingTable[fit->u.bindingIndex];
                    break;
                default:
                    break;
            }
            // don't include calls to auto-hide functions in hash because they might be de-dup'ed
            switch ( fit->kind ) {
#if SUPPORT_ARCH_arm64
                case ld::Fixup::kindStoreTargetAddressARM64Branch26:
#endif
                case ld::Fixup::kindStoreTargetAddressX86BranchPCRel32:
                    if ( target && target->autoHide() )
                        continue; // don't include
                    break;
                default:
                    break;
            }
            if ( target != NULL ) {
                const char* name = target->name();
                if ( target->contentType() == ld::Atom::typeCString )
                    name = (const char*)target->rawContentPointer();
                for (const char* s = name; *s != '\0'; ++s)
                    hash = (hash * 33) + *s;
            }
        }
        ++sHashCount;
        sSavedHashes[atom] = hash;
        return hash;
    }

    unsigned long operator()(const ld::Atom* atom) const {
        return hash(atom);
    }
};


// A helper for std::unordered_map<> that compares functions
struct atom_equal {

    struct VisitedSet {
        std::unordered_set<const ld::Atom*> atoms1;
        std::unordered_set<const ld::Atom*> atoms2;
    };

    static bool sameFixups(const ld::Atom* atom1, const ld::Atom* atom2, VisitedSet& visited) {
        ++sFixupCompareCount;
        //fprintf(stderr, "sameFixups(%s,%s)\n", atom1->name(), atom2->name());
        Fixup::iterator	f1   = atom1->fixupsBegin();
        Fixup::iterator	end1 = atom1->fixupsEnd();
        Fixup::iterator	f2   = atom2->fixupsBegin();
        Fixup::iterator	end2 = atom2->fixupsEnd();
        // two atoms must have same number of fixups
        if ( (end1 - f1) != (end2 - f2) )
            return false;
        // if no fixups, fixups are equal
        if ( f1 == end1 )
            return true;
        // all fixups must be the same
        do {
            if ( f1->offsetInAtom != f2->offsetInAtom )
                return false;
            if ( f1->kind != f2->kind )
                return false;
            if ( f1->clusterSize != f2->clusterSize )
                return false;
            if ( f1->binding != f2->binding )
                return false;
            const Atom* target1 = NULL;
            const Atom* target2 = NULL;
            switch ( f1->binding ) {
                case ld::Fixup::bindingDirectlyBound:
                    target1 = f1->u.target;
                    target2 = f2->u.target;
                    break;
                case ld::Fixup::bindingsIndirectlyBound:
                    target1 = sState->indirectBindingTable[f1->u.bindingIndex];
                    target2 = sState->indirectBindingTable[f2->u.bindingIndex];
                    break;
                 case ld::Fixup::bindingNone:
                    break;
               default:
                    return false;
            }
            if ( target1 != target2 ) {
                // targets must match unless they are both calls to functions that will de-dup together
    #if SUPPORT_ARCH_arm64
                if ( (f1->kind != ld::Fixup::kindStoreTargetAddressARM64Branch26) && (f1->kind != ld::Fixup::kindStoreTargetAddressX86BranchPCRel32) )
    #else
                if ( f1->kind != ld::Fixup::kindStoreTargetAddressX86BranchPCRel32 )
    #endif
                    return false;
                if ( target1->section().type() != target2->section().type() )
                    return false;
                if ( target1->section().type() != ld::Section::typeCode )
                    return false;
                // to support co-recursive functions, don't call equals() on targets we've already visited
                if ( ((visited.atoms1.count(target1) == 0) || (visited.atoms2.count(target2) == 0)) && !equal(target1, target2, visited) )
                    return false;
              }

            ++f1;
            ++f2;
        } while (f1 != end1);

        return true;
    }

    static bool equal(const ld::Atom* atom1, const ld::Atom* atom2, VisitedSet& visited) {
        if ( atom_hashing::hash(atom1) != atom_hashing::hash(atom2) )
            return false;
        visited.atoms1.insert(atom1);
        visited.atoms2.insert(atom2);
        return sameFixups(atom1, atom2, visited);
    }

    bool operator()(const ld::Atom* atom1, const ld::Atom* atom2) const {
        VisitedSet visited;
        return equal(atom1, atom2, visited);
    }
};


void doPass(const Options& opts, ld::Internal& state)
{
	const bool log = false;

	// only de-duplicate in final linked images
	if ( opts.outputKind() == Options::kObjectFile )
		return;

	// only de-duplicate for architectures that use relocations that don't store bits in instructions
	if ( (opts.architecture() != CPU_TYPE_ARM64) && (opts.architecture() != CPU_TYPE_X86_64) )
		return;

    // support -no_deduplicate to suppress this pass
    if ( ! opts.deduplicateFunctions() )
        return;

    const bool verbose = opts.verboseDeduplicate();

    // find __text section
    ld::Internal::FinalSection* textSection = NULL;
    for (ld::Internal::FinalSection* sect : state.sections) {
        if ( (sect->type() == ld::Section::typeCode) && (strcmp(sect->sectionName(), "__text") == 0) ) {
            textSection = sect;
            break;
        }
    }
    if ( textSection == NULL )
        return;

    // build map of auto-hide functions and their duplicates
    // the key for the map is always the first element in the value vector
    // the key is always earlier in the atoms list then matching other atoms
    sState = &state;
    std::unordered_map<const ld::Atom*, std::vector<const ld::Atom*>, atom_hashing, atom_equal> map;
    std::unordered_set<const ld::Atom*> masterAtoms;
    for (const ld::Atom* atom : textSection->atoms) {
        // ignore empty (alias) atoms
        if ( atom->size() == 0 )
            continue;
        if ( atom->autoHide() )
            map[atom].push_back(atom);
	}

    if ( log ) {
        for (auto& entry : map) {
            if ( entry.second.size() > 1 ) {
                printf("Found following matching functions:\n");
                for (const ld::Atom* atom : entry.second) {
                    printf("  %p %s\n", atom, atom->name());
                }
            }
        }
        fprintf(stderr, "duplicate sets count:\n");
        for (auto& entry : map)
            fprintf(stderr, "  %p -> %lu\n", entry.first, entry.second.size());
    }

    // construct alias atoms to replace atoms found to be duplicates
    unsigned atomsBeingComparedCount = 0;
    uint64_t dedupSavings = 0;
    std::vector<const ld::Atom*>& textAtoms = textSection->atoms;
    std::unordered_map<const ld::Atom*, const ld::Atom*> replacementMap;
    for (auto& entry : map) {
        const ld::Atom* masterAtom = entry.first;
        std::vector<const ld::Atom*>& dups = entry.second;
        atomsBeingComparedCount += dups.size();
        if ( dups.size() == 1 )
            continue;
        if ( verbose )  {
            dedupSavings += ((dups.size() - 1) * masterAtom->size());
            fprintf(stderr, "deduplicate the following %lu functions (%llu bytes apiece):\n", dups.size(), masterAtom->size());
        }
        for (const ld::Atom* dupAtom : dups) {
            if ( verbose )
                fprintf(stderr, "    %s\n", dupAtom->name());
            if ( dupAtom == masterAtom )
                continue;
            const ld::Atom* aliasAtom = new DeDupAliasAtom(dupAtom, masterAtom);
            auto pos = std::find(textAtoms.begin(), textAtoms.end(), masterAtom);
            if ( pos != textAtoms.end() ) {
                textAtoms.insert(pos, aliasAtom);
                state.atomToSection[aliasAtom] = textSection;
                replacementMap[dupAtom] = aliasAtom;
            }
        }
    }
    if ( verbose )  {
        fprintf(stderr, "deduplication saved %llu bytes of __text\n", dedupSavings);
    }

    if ( log ) {
        fprintf(stderr, "replacement map:\n");
        for (auto& entry : replacementMap)
            fprintf(stderr, "  %p -> %p\n", entry.first, entry.second);
    }

    // walk all atoms and replace references to dups with references to alias
    for (ld::Internal::FinalSection* sect : state.sections) {
        for (const ld::Atom* atom : sect->atoms) {
			for (ld::Fixup::iterator fit = atom->fixupsBegin(), end=atom->fixupsEnd(); fit != end; ++fit) {
                std::unordered_map<const ld::Atom*, const ld::Atom*>::iterator pos;
                switch ( fit->binding ) {
                    case ld::Fixup::bindingsIndirectlyBound:
                        pos = replacementMap.find(state.indirectBindingTable[fit->u.bindingIndex]);
                        if ( pos != replacementMap.end() )
                            state.indirectBindingTable[fit->u.bindingIndex] = pos->second;
                        break;
                    case ld::Fixup::bindingDirectlyBound:
                        pos = replacementMap.find(fit->u.target);
                        if ( pos != replacementMap.end() )
                            fit->u.target = pos->second;
                        break;
                    default:
                        break;
                }
			}
        }
    }

    if ( log ) {
        fprintf(stderr, "atoms before pruning:\n");
        for (const ld::Atom* atom : textSection->atoms)
            fprintf(stderr, "  %p (size=%llu) %sp\n", atom, atom->size(), atom->name());
    }
    // remove replaced atoms from section
	textSection->atoms.erase(std::remove_if(textSection->atoms.begin(), textSection->atoms.end(),
                [&](const ld::Atom* atom) {
                    return (replacementMap.count(atom) != 0);
                }),
                textSection->atoms.end());

   for (auto& entry : replacementMap)
        state.atomToSection.erase(entry.first);

    if ( log ) {
        fprintf(stderr, "atoms after pruning:\n");
        for (const ld::Atom* atom : textSection->atoms)
            fprintf(stderr, "  %p (size=%llu) %sp\n", atom, atom->size(), atom->name());
    }

   //fprintf(stderr, "hash-count=%lu, fixup-compares=%lu, atom-count=%u\n", sHashCount, sFixupCompareCount, atomsBeingComparedCount);
}


} // namespace dedup
} // namespace passes
} // namespace ld
Commit	Line	Data
	1	/* -- mode: C++; c-basic-offset: 4; tab-width: 4 --
	2	*
	3	* Copyright (c) 2015 Apple Inc. All rights reserved.
	4	*
	5	* @APPLE_LICENSE_HEADER_START@
	6	*
	7	* This file contains Original Code and/or Modifications of Original Code
	8	* as defined in and that are subject to the Apple Public Source License
	9	* Version 2.0 (the 'License'). You may not use this file except in
	10	* compliance with the License. Please obtain a copy of the License at
	11	* http://www.opensource.apple.com/apsl/ and read it before using this
	12	* file.
	13	*
	14	* The Original Code and all software distributed under the License are
	15	* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
	16	* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
	17	* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
	18	* FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
	19	* Please see the License for the specific language governing rights and
	20	* limitations under the License.
	21	*
	22	* @APPLE_LICENSE_HEADER_END@
	23	*/
	24
	25
	26	#include <stdint.h>
	27	#include <math.h>
	28	#include <unistd.h>
	29	#include <dlfcn.h>
	30	#include <mach/machine.h>
	31
	32	#include <vector>
	33	#include <map>
	34	#include <algorithm>
	35	#include <unordered_map>
	36
	37	#include "ld.hpp"
	38	#include "code_dedup.h"
	39
	40	namespace ld {
	41	namespace passes {
	42	namespace dedup {
	43
	44
	45
	46	class DeDupAliasAtom : public ld::Atom
	47	{
	48	public:
	49	DeDupAliasAtom(const ld::Atom* dupOf, const ld::Atom* replacement) :
	50	ld::Atom(dupOf->section(), ld::Atom::definitionRegular, ld::Atom::combineNever,
	51	dupOf->scope(), dupOf->contentType(), ld::Atom::symbolTableIn,
	52	false, false, true, 0),
	53	_dedupOf(dupOf),
	54	_fixup(0, ld::Fixup::k1of1, ld::Fixup::kindNoneFollowOn, ld::Fixup::bindingDirectlyBound, replacement) {
	55	if ( dupOf->autoHide() )
	56	setAutoHide();
	57	}
	58
	59	virtual const ld::File* file() const { return _dedupOf->file(); }
	60	virtual const char* translationUnitSource() const
	61	{ return NULL; }
	62	virtual const char* name() const { return _dedupOf->name(); }
	63	virtual uint64_t size() const { return 0; }
	64	virtual uint64_t objectAddress() const { return 0; }
	65	virtual void copyRawContent(uint8_t buffer[]) const { }
	66	virtual ld::Fixup::iterator fixupsBegin() const { return &((ld::Fixup*)&_fixup)[0]; }
	67	virtual ld::Fixup::iterator fixupsEnd() const { return &((ld::Fixup*)&_fixup)[1]; }
	68
	69	private:
	70	const ld::Atom* _dedupOf;
	71	ld::Fixup _fixup;
	72	};
	73
	74
	75	namespace {
	76	typedef std::unordered_map<const ld::Atom*, unsigned long> CachedHashes;
	77
	78	ld::Internal* sState = nullptr;
	79	CachedHashes sSavedHashes;
	80	unsigned long sHashCount = 0;
	81	unsigned long sFixupCompareCount = 0;
	82	};
	83
	84
	85	// A helper for std::unordered_map<> that hashes the instructions of a function
	86	struct atom_hashing {
	87
	88	static unsigned long hash(const ld::Atom* atom) {
	89	auto pos = sSavedHashes.find(atom);
	90	if ( pos != sSavedHashes.end() )
	91	return pos->second;
	92
	93	const unsigned instructionBytes = atom->size();
	94	const uint8_t* instructions = atom->rawContentPointer();
	95	unsigned long hash = instructionBytes;
	96	for (unsigned i=0; i < instructionBytes; ++i) {
	97	hash = (hash * 33) + instructions[i];
	98	}
	99	for (ld::Fixup::iterator fit = atom->fixupsBegin(), end=atom->fixupsEnd(); fit != end; ++fit) {
	100	const Atom* target = NULL;
	101	switch ( fit->binding ) {
	102	case ld::Fixup::bindingDirectlyBound:
	103	target = fit->u.target;
	104	break;
	105	case ld::Fixup::bindingsIndirectlyBound:
	106	target = sState->indirectBindingTable[fit->u.bindingIndex];
	107	break;
	108	default:
	109	break;
	110	}
	111	// don't include calls to auto-hide functions in hash because they might be de-dup'ed
	112	switch ( fit->kind ) {
	113	#if SUPPORT_ARCH_arm64
	114	case ld::Fixup::kindStoreTargetAddressARM64Branch26:
	115	#endif
	116	case ld::Fixup::kindStoreTargetAddressX86BranchPCRel32:
	117	if ( target && target->autoHide() )
	118	continue; // don't include
	119	break;
	120	default:
	121	break;
	122	}
	123	if ( target != NULL ) {
	124	const char* name = target->name();
	125	if ( target->contentType() == ld::Atom::typeCString )
	126	name = (const char*)target->rawContentPointer();
	127	for (const char* s = name; *s != '\0'; ++s)
	128	hash = (hash * 33) + *s;
	129	}
	130	}
	131	++sHashCount;
	132	sSavedHashes[atom] = hash;
	133	return hash;
	134	}
	135
	136	unsigned long operator()(const ld::Atom* atom) const {
	137	return hash(atom);
	138	}
	139	};
	140
	141
	142	// A helper for std::unordered_map<> that compares functions
	143	struct atom_equal {
	144
	145	struct VisitedSet {
	146	std::unordered_set<const ld::Atom*> atoms1;
	147	std::unordered_set<const ld::Atom*> atoms2;
	148	};
	149
	150	static bool sameFixups(const ld::Atom* atom1, const ld::Atom* atom2, VisitedSet& visited) {
	151	++sFixupCompareCount;
	152	//fprintf(stderr, "sameFixups(%s,%s)\n", atom1->name(), atom2->name());
	153	Fixup::iterator f1 = atom1->fixupsBegin();
	154	Fixup::iterator end1 = atom1->fixupsEnd();
	155	Fixup::iterator f2 = atom2->fixupsBegin();
	156	Fixup::iterator end2 = atom2->fixupsEnd();
	157	// two atoms must have same number of fixups
	158	if ( (end1 - f1) != (end2 - f2) )
	159	return false;
	160	// if no fixups, fixups are equal
	161	if ( f1 == end1 )
	162	return true;
	163	// all fixups must be the same
	164	do {
	165	if ( f1->offsetInAtom != f2->offsetInAtom )
	166	return false;
	167	if ( f1->kind != f2->kind )
	168	return false;
	169	if ( f1->clusterSize != f2->clusterSize )
	170	return false;
	171	if ( f1->binding != f2->binding )
	172	return false;
	173	const Atom* target1 = NULL;
	174	const Atom* target2 = NULL;
	175	switch ( f1->binding ) {
	176	case ld::Fixup::bindingDirectlyBound:
	177	target1 = f1->u.target;
	178	target2 = f2->u.target;
	179	break;
	180	case ld::Fixup::bindingsIndirectlyBound:
	181	target1 = sState->indirectBindingTable[f1->u.bindingIndex];
	182	target2 = sState->indirectBindingTable[f2->u.bindingIndex];
	183	break;
	184	case ld::Fixup::bindingNone:
	185	break;
	186	default:
	187	return false;
	188	}
	189	if ( target1 != target2 ) {
	190	// targets must match unless they are both calls to functions that will de-dup together
	191	#if SUPPORT_ARCH_arm64
	192	if ( (f1->kind != ld::Fixup::kindStoreTargetAddressARM64Branch26) && (f1->kind != ld::Fixup::kindStoreTargetAddressX86BranchPCRel32) )
	193	#else
	194	if ( f1->kind != ld::Fixup::kindStoreTargetAddressX86BranchPCRel32 )
	195	#endif
	196	return false;
	197	if ( target1->section().type() != target2->section().type() )
	198	return false;
	199	if ( target1->section().type() != ld::Section::typeCode )
	200	return false;
	201	// to support co-recursive functions, don't call equals() on targets we've already visited
	202	if ( ((visited.atoms1.count(target1) == 0) \|\| (visited.atoms2.count(target2) == 0)) && !equal(target1, target2, visited) )
	203	return false;
	204	}
	205
	206	++f1;
	207	++f2;
	208	} while (f1 != end1);
	209
	210	return true;
	211	}
	212
	213	static bool equal(const ld::Atom* atom1, const ld::Atom* atom2, VisitedSet& visited) {
	214	if ( atom_hashing::hash(atom1) != atom_hashing::hash(atom2) )
	215	return false;
	216	visited.atoms1.insert(atom1);
	217	visited.atoms2.insert(atom2);
	218	return sameFixups(atom1, atom2, visited);
	219	}
	220
	221	bool operator()(const ld::Atom* atom1, const ld::Atom* atom2) const {
	222	VisitedSet visited;
	223	return equal(atom1, atom2, visited);
	224	}
	225	};
	226
	227
	228
	229	void doPass(const Options& opts, ld::Internal& state)
	230	{
	231	const bool log = false;
	232
	233	// only de-duplicate in final linked images
	234	if ( opts.outputKind() == Options::kObjectFile )
	235	return;
	236
	237	// only de-duplicate for architectures that use relocations that don't store bits in instructions
	238	if ( (opts.architecture() != CPU_TYPE_ARM64) && (opts.architecture() != CPU_TYPE_X86_64) )
	239	return;
	240
	241	// support -no_deduplicate to suppress this pass
	242	if ( ! opts.deduplicateFunctions() )
	243	return;
	244
	245	const bool verbose = opts.verboseDeduplicate();
	246
	247	// find __text section
	248	ld::Internal::FinalSection* textSection = NULL;
	249	for (ld::Internal::FinalSection* sect : state.sections) {
	250	if ( (sect->type() == ld::Section::typeCode) && (strcmp(sect->sectionName(), "__text") == 0) ) {
	251	textSection = sect;
	252	break;
	253	}
	254	}
	255	if ( textSection == NULL )
	256	return;
	257
	258	// build map of auto-hide functions and their duplicates
	259	// the key for the map is always the first element in the value vector
	260	// the key is always earlier in the atoms list then matching other atoms
	261	sState = &state;
	262	std::unordered_map<const ld::Atom, std::vector<const ld::Atom>, atom_hashing, atom_equal> map;
	263	std::unordered_set<const ld::Atom*> masterAtoms;
	264	for (const ld::Atom* atom : textSection->atoms) {
	265	// ignore empty (alias) atoms
	266	if ( atom->size() == 0 )
	267	continue;
	268	if ( atom->autoHide() )
	269	map[atom].push_back(atom);
	270	}
	271
	272	if ( log ) {
	273	for (auto& entry : map) {
	274	if ( entry.second.size() > 1 ) {
	275	printf("Found following matching functions:\n");
	276	for (const ld::Atom* atom : entry.second) {
	277	printf(" %p %s\n", atom, atom->name());
	278	}
	279	}
	280	}
	281	fprintf(stderr, "duplicate sets count:\n");
	282	for (auto& entry : map)
	283	fprintf(stderr, " %p -> %lu\n", entry.first, entry.second.size());
	284	}
	285
	286	// construct alias atoms to replace atoms found to be duplicates
	287	unsigned atomsBeingComparedCount = 0;
	288	uint64_t dedupSavings = 0;
	289	std::vector<const ld::Atom*>& textAtoms = textSection->atoms;
	290	std::unordered_map<const ld::Atom, const ld::Atom> replacementMap;
	291	for (auto& entry : map) {
	292	const ld::Atom* masterAtom = entry.first;
	293	std::vector<const ld::Atom*>& dups = entry.second;
	294	atomsBeingComparedCount += dups.size();
	295	if ( dups.size() == 1 )
	296	continue;
	297	if ( verbose ) {
	298	dedupSavings += ((dups.size() - 1) * masterAtom->size());
	299	fprintf(stderr, "deduplicate the following %lu functions (%llu bytes apiece):\n", dups.size(), masterAtom->size());
	300	}
	301	for (const ld::Atom* dupAtom : dups) {
	302	if ( verbose )
	303	fprintf(stderr, " %s\n", dupAtom->name());
	304	if ( dupAtom == masterAtom )
	305	continue;
	306	const ld::Atom* aliasAtom = new DeDupAliasAtom(dupAtom, masterAtom);
	307	auto pos = std::find(textAtoms.begin(), textAtoms.end(), masterAtom);
	308	if ( pos != textAtoms.end() ) {
	309	textAtoms.insert(pos, aliasAtom);
	310	state.atomToSection[aliasAtom] = textSection;
	311	replacementMap[dupAtom] = aliasAtom;
	312	}
	313	}
	314	}
	315	if ( verbose ) {
	316	fprintf(stderr, "deduplication saved %llu bytes of __text\n", dedupSavings);
	317	}
	318
	319	if ( log ) {
	320	fprintf(stderr, "replacement map:\n");
	321	for (auto& entry : replacementMap)
	322	fprintf(stderr, " %p -> %p\n", entry.first, entry.second);
	323	}
	324
	325	// walk all atoms and replace references to dups with references to alias
	326	for (ld::Internal::FinalSection* sect : state.sections) {
	327	for (const ld::Atom* atom : sect->atoms) {
	328	for (ld::Fixup::iterator fit = atom->fixupsBegin(), end=atom->fixupsEnd(); fit != end; ++fit) {
	329	std::unordered_map<const ld::Atom, const ld::Atom>::iterator pos;
	330	switch ( fit->binding ) {
	331	case ld::Fixup::bindingsIndirectlyBound:
	332	pos = replacementMap.find(state.indirectBindingTable[fit->u.bindingIndex]);
	333	if ( pos != replacementMap.end() )
	334	state.indirectBindingTable[fit->u.bindingIndex] = pos->second;
	335	break;
	336	case ld::Fixup::bindingDirectlyBound:
	337	pos = replacementMap.find(fit->u.target);
	338	if ( pos != replacementMap.end() )
	339	fit->u.target = pos->second;
	340	break;
	341	default:
	342	break;
	343	}
	344	}
	345	}
	346	}
	347
	348	if ( log ) {
	349	fprintf(stderr, "atoms before pruning:\n");
	350	for (const ld::Atom* atom : textSection->atoms)
	351	fprintf(stderr, " %p (size=%llu) %sp\n", atom, atom->size(), atom->name());
	352	}
	353	// remove replaced atoms from section
	354	textSection->atoms.erase(std::remove_if(textSection->atoms.begin(), textSection->atoms.end(),
	355	[&](const ld::Atom* atom) {
	356	return (replacementMap.count(atom) != 0);
	357	}),
	358	textSection->atoms.end());
	359
	360	for (auto& entry : replacementMap)
	361	state.atomToSection.erase(entry.first);
	362
	363	if ( log ) {
	364	fprintf(stderr, "atoms after pruning:\n");
	365	for (const ld::Atom* atom : textSection->atoms)
	366	fprintf(stderr, " %p (size=%llu) %sp\n", atom, atom->size(), atom->name());
	367	}
	368
	369	//fprintf(stderr, "hash-count=%lu, fixup-compares=%lu, atom-count=%u\n", sHashCount, sFixupCompareCount, atomsBeingComparedCount);
	370	}
	371
	372
	373	} // namespace dedup
	374	} // namespace passes
	375	} // namespace ld