GarbageCollection.cpp revision 0dea6bc96bb52346737966839ac68644f7939f58
187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines//===- GarbageCollection.cpp ----------------------------------------------===// 287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines// 387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines// The MCLinker Project 487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines// 587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines// This file is distributed under the University of Illinois Open Source 687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines// License. See LICENSE.TXT for details. 787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines// 887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines//===----------------------------------------------------------------------===// 987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#include <mcld/Fragment/Fragment.h> 1087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#include <mcld/Fragment/Relocation.h> 1187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#include <mcld/LD/GarbageCollection.h> 1287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#include <mcld/LD/LDContext.h> 1387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#include <mcld/LD/LDFileFormat.h> 1487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#include <mcld/LD/LDSection.h> 1587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#include <mcld/LD/LDSymbol.h> 1687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#include <mcld/LD/SectionData.h> 1787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#include <mcld/LD/RelocData.h> 1887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#include <mcld/LinkerConfig.h> 1987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#include <mcld/LinkerScript.h> 2087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#include <mcld/Module.h> 210dea6bc96bb52346737966839ac68644f7939f58Stephen Hines#include <mcld/Support/MsgHandling.h> 2287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#include <mcld/Target/TargetLDBackend.h> 2387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 2487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#include <llvm/Support/Casting.h> 2587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 2687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#include <queue> 2787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#if !defined(MCLD_ON_WIN32) 2887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#include <fnmatch.h> 2987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#define fnmatch0(pattern,string) (fnmatch(pattern,string,0) == 0) 3087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#else 3187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#include <windows.h> 3287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#include <shlwapi.h> 3387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#define fnmatch0(pattern,string) (PathMatchSpec(string, pattern) == true) 3487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#endif 3587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 3687f34658dec9097d987d254a990ea7f311bfc95fStephen Hinesusing namespace mcld; 3787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 3887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines//===----------------------------------------------------------------------===// 3987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines// Non-member functions 4087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines//===----------------------------------------------------------------------===// 4187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines// FIXME: these rules should be added into SectionMap, while currently adding to 4287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines// SectionMap will cause the output order change in .text section and leads to 4387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines// the .ARM.exidx order incorrect. We should sort the .ARM.exidx. 4487f34658dec9097d987d254a990ea7f311bfc95fStephen Hinesstatic const char* pattern_to_keep[] = 4587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines{ 4687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ".text*personality*", 4787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ".data*personality*", 4887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ".gnu.linkonce.d*personality*", 4987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ".sdata*personality*" 5087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines}; 5187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 5287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines/// shouldKeep - check the section name for the keep sections 5387f34658dec9097d987d254a990ea7f311bfc95fStephen Hinesstatic bool shouldKeep(const std::string& pName) 5487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines{ 5587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines static const unsigned int pattern_size = 5687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines sizeof(pattern_to_keep) / sizeof(pattern_to_keep[0]); 5787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines for (unsigned int i=0; i < pattern_size; ++i) { 5887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines if (fnmatch0(pattern_to_keep[i], pName.c_str())) 5987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines return true; 6087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines } 6187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines return false; 6287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 6387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 6487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines/// shouldProcessGC - check if the section kind is handled in GC 6587f34658dec9097d987d254a990ea7f311bfc95fStephen Hinesstatic bool mayProcessGC(const LDSection& pSection) 6687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines{ 670dea6bc96bb52346737966839ac68644f7939f58Stephen Hines if (pSection.kind() == LDFileFormat::TEXT || 680dea6bc96bb52346737966839ac68644f7939f58Stephen Hines pSection.kind() == LDFileFormat::DATA || 6987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines pSection.kind() == LDFileFormat::BSS || 7087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines pSection.kind() == LDFileFormat::GCCExceptTable) 7187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines return true; 7287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines return false; 7387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 7487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 7587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines//===----------------------------------------------------------------------===// 7687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines// GarbageCollection::SectionReachedListMap 7787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines//===----------------------------------------------------------------------===// 7887f34658dec9097d987d254a990ea7f311bfc95fStephen Hinesvoid 7987f34658dec9097d987d254a990ea7f311bfc95fStephen HinesGarbageCollection::SectionReachedListMap::addReference(const LDSection& pFrom, 8087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines const LDSection& pTo) 8187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines{ 8287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines m_ReachedSections[&pFrom].insert(&pTo); 8387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 8487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 8587f34658dec9097d987d254a990ea7f311bfc95fStephen HinesGarbageCollection::SectionListTy& 8687f34658dec9097d987d254a990ea7f311bfc95fStephen HinesGarbageCollection::SectionReachedListMap::getReachedList( 8787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines const LDSection& pSection) 8887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines{ 8987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines return m_ReachedSections[&pSection]; 9087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 9187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 9287f34658dec9097d987d254a990ea7f311bfc95fStephen HinesGarbageCollection::SectionListTy* 9387f34658dec9097d987d254a990ea7f311bfc95fStephen HinesGarbageCollection::SectionReachedListMap::findReachedList( 9487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines const LDSection& pSection) 9587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines{ 9687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ReachedSectionsTy::iterator it = m_ReachedSections.find(&pSection); 9787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines if (it == m_ReachedSections.end()) 9887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines return NULL; 9987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines return &it->second; 10087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 10187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 10287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines//===----------------------------------------------------------------------===// 10387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines// GarbageCollection 10487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines//===----------------------------------------------------------------------===// 10587f34658dec9097d987d254a990ea7f311bfc95fStephen HinesGarbageCollection::GarbageCollection(const LinkerConfig& pConfig, 10687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines const TargetLDBackend& pBackend, 10787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines Module& pModule) 10887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines : m_Config(pConfig), m_Backend(pBackend), m_Module(pModule) 10987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines{ 11087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 11187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 11287f34658dec9097d987d254a990ea7f311bfc95fStephen HinesGarbageCollection::~GarbageCollection() 11387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines{ 11487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 11587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 11687f34658dec9097d987d254a990ea7f311bfc95fStephen Hinesbool GarbageCollection::run() 11787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines{ 11887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // 1. traverse all the relocations to set up the reached sections of each 11987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // section 12087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines setUpReachedSections(); 12187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines m_Backend.setUpReachedSectionsForGC(m_Module, m_SectionReachedListMap); 12287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 12387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // 2. get all sections defined the entry point 12487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines SectionVecTy entry; 12587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines getEntrySections(entry); 12687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 12787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // 3. find all the referenced sections those can be reached by entry 12887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines findReferencedSections(entry); 12987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 13087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // 4. stripSections - set the unreached sections to Ignore 13187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines stripSections(); 13287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines return true; 13387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 13487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 13587f34658dec9097d987d254a990ea7f311bfc95fStephen Hinesvoid GarbageCollection::setUpReachedSections() 13687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines{ 13787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // traverse all the input relocations to setup the reached sections 13887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines Module::obj_iterator input, inEnd = m_Module.obj_end(); 13987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines for (input = m_Module.obj_begin(); input != inEnd; ++input) { 14087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines LDContext::sect_iterator rs, rsEnd = (*input)->context()->relocSectEnd(); 14187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines for (rs = (*input)->context()->relocSectBegin(); rs != rsEnd; ++rs) { 14287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // bypass the discarded relocation section 14387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // 1. its section kind is changed to Ignore. (The target section is a 14487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // discarded group section.) 14587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // 2. it has no reloc data. (All symbols in the input relocs are in the 14687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // discarded group sections) 14787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines LDSection* reloc_sect = *rs; 14887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines LDSection* apply_sect = reloc_sect->getLink(); 14987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines if ((LDFileFormat::Ignore == reloc_sect->kind()) || 15087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines (!reloc_sect->hasRelocData())) 15187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines continue; 15287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 15387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // bypass the apply target sections which are not handled by gc 15487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines if (!mayProcessGC(*apply_sect)) 15587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines continue; 15687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 15787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines bool add_first = false; 15887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines SectionListTy* reached_sects = NULL; 15987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines RelocData::iterator reloc_it, rEnd = reloc_sect->getRelocData()->end(); 16087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines for (reloc_it = reloc_sect->getRelocData()->begin(); reloc_it != rEnd; 16187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ++reloc_it) { 16287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines Relocation* reloc = llvm::cast<Relocation>(reloc_it); 16387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ResolveInfo* sym = reloc->symInfo(); 16487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // only the target symbols defined in the input fragments can make the 16587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // reference 16687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines if (NULL == sym) 16787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines continue; 16887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines if (!sym->isDefine() || !sym->outSymbol()->hasFragRef()) 16987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines continue; 17087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 17187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // only the target symbols defined in the concerned sections can make 17287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // the reference 17387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines const LDSection* target_sect = 17487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines &sym->outSymbol()->fragRef()->frag()->getParent()->getSection(); 17587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines if (!mayProcessGC(*target_sect)) 17687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines continue; 17787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 17887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // setup the reached list, if we first add the element to reached list 17987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // of this section, create an entry in ReachedSections map 18087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines if (!add_first) { 18187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines reached_sects = &m_SectionReachedListMap.getReachedList(*apply_sect); 18287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines add_first = true; 18387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines } 18487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines reached_sects->insert(target_sect); 18587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines } 18687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines reached_sects = NULL; 18787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines add_first = false; 18887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines } 18987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines } 19087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 19187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 19287f34658dec9097d987d254a990ea7f311bfc95fStephen Hinesvoid GarbageCollection::getEntrySections(SectionVecTy& pEntry) 19387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines{ 19487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // all the KEEP sections defined in ldscript are entries, traverse all the 19587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // input sections and check the SectionMap to find the KEEP sections 19687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines Module::obj_iterator obj, objEnd = m_Module.obj_end(); 19787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines SectionMap& sect_map = m_Module.getScript().sectionMap(); 19887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines for (obj = m_Module.obj_begin(); obj != objEnd; ++obj) { 19987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines const std::string input_name = (*obj)->name(); 20087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines LDContext::sect_iterator sect, sectEnd = (*obj)->context()->sectEnd(); 20187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines for (sect = (*obj)->context()->sectBegin(); sect != sectEnd; ++sect) { 20287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines LDSection* section = *sect; 20387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines if (!mayProcessGC(*section)) 20487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines continue; 20587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 20687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines SectionMap::Input* sm_input = 20787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines sect_map.find(input_name, section->name()).second; 20887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines if (((sm_input != NULL) && (InputSectDesc::Keep == sm_input->policy())) || 20987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines shouldKeep(section->name())) 21087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines pEntry.push_back(section); 21187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines } 21287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines } 21387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 21487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // get the sections those the entry symbols defined in 21587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines if (LinkerConfig::Exec == m_Config.codeGenType() || 21687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines m_Config.options().isPIE()) { 21787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // when building executable 21887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // 1. the entry symbol is the entry 21987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines LDSymbol* entry_sym = 22087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines m_Module.getNamePool().findSymbol(m_Backend.getEntry(m_Module)); 22187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines assert(NULL != entry_sym); 22287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines pEntry.push_back(&entry_sym->fragRef()->frag()->getParent()->getSection()); 22387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 22487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // 2. the symbols have been seen in dynamice objects are entries 22587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines NamePool::syminfo_iterator info_it, 22687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines info_end = m_Module.getNamePool().syminfo_end(); 22787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines for (info_it = m_Module.getNamePool().syminfo_begin(); info_it != info_end; 22887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ++info_it) { 22987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ResolveInfo* info = info_it.getEntry(); 23087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines if (!info->isDefine() || info->isLocal()) 23187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines continue; 23287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 23387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines if (!info->isInDyn()) 23487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines continue; 23587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 23687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines LDSymbol* sym = info->outSymbol(); 23787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines if (NULL == sym || !sym->hasFragRef()) 23887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines continue; 23987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 24087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // only the target symbols defined in the concerned sections can be 24187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // entries 24287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines const LDSection* sect = 24387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines &sym->fragRef()->frag()->getParent()->getSection(); 24487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines if (!mayProcessGC(*sect)) 24587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines continue; 24687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 24787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines pEntry.push_back(sect); 24887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines } 24987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines } 25087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 25187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines else { 25287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // when building shared objects, the global define symbols are entries 25387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines NamePool::syminfo_iterator info_it, 25487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines info_end = m_Module.getNamePool().syminfo_end(); 25587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines for (info_it = m_Module.getNamePool().syminfo_begin(); info_it != info_end; 25687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ++info_it) { 25787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ResolveInfo* info = info_it.getEntry(); 25887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines if (!info->isDefine() || 25987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines info->isLocal() || 26087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines info->shouldForceLocal(m_Config)) 26187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines continue; 26287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines LDSymbol* sym = info->outSymbol(); 26387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines if (NULL == sym || !sym->hasFragRef()) 26487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines continue; 26587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 26687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // only the target symbols defined in the concerned sections can be 26787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // entries 26887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines const LDSection* sect = 26987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines &sym->fragRef()->frag()->getParent()->getSection(); 27087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines if (!mayProcessGC(*sect)) 27187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines continue; 27287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines pEntry.push_back(sect); 27387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines } 27487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines } 2750dea6bc96bb52346737966839ac68644f7939f58Stephen Hines 2760dea6bc96bb52346737966839ac68644f7939f58Stephen Hines // symbols set by -u should not be garbage collected. Set them entries. 2770dea6bc96bb52346737966839ac68644f7939f58Stephen Hines GeneralOptions::const_undef_sym_iterator usym; 2780dea6bc96bb52346737966839ac68644f7939f58Stephen Hines GeneralOptions::const_undef_sym_iterator usymEnd = 2790dea6bc96bb52346737966839ac68644f7939f58Stephen Hines m_Config.options().undef_sym_end(); 2800dea6bc96bb52346737966839ac68644f7939f58Stephen Hines for (usym = m_Config.options().undef_sym_begin(); usym != usymEnd; ++usym) { 2810dea6bc96bb52346737966839ac68644f7939f58Stephen Hines LDSymbol* sym = m_Module.getNamePool().findSymbol(*usym); 2820dea6bc96bb52346737966839ac68644f7939f58Stephen Hines assert(sym); 2830dea6bc96bb52346737966839ac68644f7939f58Stephen Hines ResolveInfo* info = sym->resolveInfo(); 2840dea6bc96bb52346737966839ac68644f7939f58Stephen Hines assert(info); 2850dea6bc96bb52346737966839ac68644f7939f58Stephen Hines if (!info->isDefine() || !sym->hasFragRef()) 2860dea6bc96bb52346737966839ac68644f7939f58Stephen Hines continue; 2870dea6bc96bb52346737966839ac68644f7939f58Stephen Hines // only the symbols defined in the concerned sections can be entries 2880dea6bc96bb52346737966839ac68644f7939f58Stephen Hines const LDSection* sect = &sym->fragRef()->frag()->getParent()->getSection(); 2890dea6bc96bb52346737966839ac68644f7939f58Stephen Hines if (!mayProcessGC(*sect)) 2900dea6bc96bb52346737966839ac68644f7939f58Stephen Hines continue; 2910dea6bc96bb52346737966839ac68644f7939f58Stephen Hines pEntry.push_back(sect); 2920dea6bc96bb52346737966839ac68644f7939f58Stephen Hines } 29387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 29487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 29587f34658dec9097d987d254a990ea7f311bfc95fStephen Hinesvoid GarbageCollection::findReferencedSections(SectionVecTy& pEntry) 29687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines{ 29787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // list of sections waiting to be processed 29887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines typedef std::queue<const LDSection*> WorkListTy; 29987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines WorkListTy work_list; 30087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // start from each entry, resolve the transitive closure 30187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines SectionVecTy::iterator entry_it, entry_end = pEntry.end(); 30287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines for (entry_it = pEntry.begin(); entry_it != entry_end; ++entry_it) { 30387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // add entry point to work list 30487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines work_list.push(*entry_it); 30587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 30687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // add section from the work_list to the referencedSections until every 30787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // reached sections are added 30887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines while (!work_list.empty()) { 30987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines const LDSection* sect = work_list.front(); 31087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines work_list.pop(); 31187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // add section to the ReferencedSections, if the section has been put into 31287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // referencedSections, skip this section 31387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines if (!m_ReferencedSections.insert(sect).second) 31487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines continue; 31587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 31687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // get the section reached list, if the section do not has one, which 31787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // means no referenced between it and other sections, then skip it 31887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines SectionListTy* reach_list = 31987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines m_SectionReachedListMap.findReachedList(*sect); 32087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines if (NULL == reach_list) 32187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines continue; 32287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 32387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // put the reached sections to work list, skip the one already be in 32487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // referencedSections 32587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines SectionListTy::iterator it, end = reach_list->end(); 32687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines for (it = reach_list->begin(); it != end; ++it) { 32787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines if (m_ReferencedSections.find(*it) == m_ReferencedSections.end()) 32887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines work_list.push(*it); 32987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines } 33087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines } 33187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines } 33287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 33387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 33487f34658dec9097d987d254a990ea7f311bfc95fStephen Hinesvoid GarbageCollection::stripSections() 33587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines{ 33687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // Traverse all the input Regular and BSS sections, if a section is not found 33787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // in the ReferencedSections, then it should be garbage collected 33887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines Module::obj_iterator obj, objEnd = m_Module.obj_end(); 33987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines for (obj = m_Module.obj_begin(); obj != objEnd; ++obj) { 34087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines LDContext::sect_iterator sect, sectEnd = (*obj)->context()->sectEnd(); 34187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines for (sect = (*obj)->context()->sectBegin(); sect != sectEnd; ++sect) { 34287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines LDSection* section = *sect; 34387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines if (!mayProcessGC(*section)) 34487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines continue; 34587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 3460dea6bc96bb52346737966839ac68644f7939f58Stephen Hines if (m_ReferencedSections.find(section) == m_ReferencedSections.end()) { 34787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines section->setKind(LDFileFormat::Ignore); 3480dea6bc96bb52346737966839ac68644f7939f58Stephen Hines debug(diag::debug_print_gc_sections) << section->name() 3490dea6bc96bb52346737966839ac68644f7939f58Stephen Hines << (*obj)->name(); 3500dea6bc96bb52346737966839ac68644f7939f58Stephen Hines } 35187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines } 35287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines } 35387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 35487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // Traverse all the relocation sections, if its target section is set to 35587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // Ignore, then set the relocation section to Ignore as well 35687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines Module::obj_iterator input, inEnd = m_Module.obj_end(); 35787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines for (input = m_Module.obj_begin(); input != inEnd; ++input) { 35887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines LDContext::sect_iterator rs, rsEnd = (*input)->context()->relocSectEnd(); 35987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines for (rs = (*input)->context()->relocSectBegin(); rs != rsEnd; ++rs) { 36087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines LDSection* reloc_sect = *rs; 36187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines if (LDFileFormat::Ignore == reloc_sect->getLink()->kind()) 36287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines reloc_sect->setKind(LDFileFormat::Ignore); 36387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines } 36487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines } 36587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 36687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 367