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//===----------------------------------------------------------------------===// 937b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/LD/GarbageCollection.h" 1037b74a387bb3993387029859c2d9d051c41c724eStephen Hines 1137b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/Fragment/Fragment.h" 1237b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/Fragment/Relocation.h" 1337b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/LD/LDContext.h" 1437b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/LD/LDFileFormat.h" 1537b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/LD/LDSection.h" 1637b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/LD/LDSymbol.h" 1737b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/LD/SectionData.h" 1837b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/LD/RelocData.h" 1937b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/LinkerConfig.h" 2037b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/LinkerScript.h" 2137b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/Module.h" 2237b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/Support/MsgHandling.h" 2337b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/Target/TargetLDBackend.h" 2487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 2587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#include <llvm/Support/Casting.h> 2687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 2787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#include <queue> 2887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#if !defined(MCLD_ON_WIN32) 2987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#include <fnmatch.h> 3037b74a387bb3993387029859c2d9d051c41c724eStephen Hines#define fnmatch0(pattern, string) (fnmatch(pattern, string, 0) == 0) 3187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#else 3287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#include <windows.h> 3387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#include <shlwapi.h> 3437b74a387bb3993387029859c2d9d051c41c724eStephen Hines#define fnmatch0(pattern, string) (PathMatchSpec(string, pattern) == true) 3587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#endif 3687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 3737b74a387bb3993387029859c2d9d051c41c724eStephen Hinesnamespace mcld { 3887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 3987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines//===----------------------------------------------------------------------===// 4087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines// Non-member functions 4187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines//===----------------------------------------------------------------------===// 4287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines// FIXME: these rules should be added into SectionMap, while currently adding to 4387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines// SectionMap will cause the output order change in .text section and leads to 4487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines// the .ARM.exidx order incorrect. We should sort the .ARM.exidx. 4537b74a387bb3993387029859c2d9d051c41c724eStephen Hinesstatic const char* pattern_to_keep[] = {".text*personality*", 4637b74a387bb3993387029859c2d9d051c41c724eStephen Hines ".data*personality*", 4737b74a387bb3993387029859c2d9d051c41c724eStephen Hines ".gnu.linkonce.d*personality*", 4837b74a387bb3993387029859c2d9d051c41c724eStephen Hines ".sdata*personality*"}; 4987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 5087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines/// shouldKeep - check the section name for the keep sections 5137b74a387bb3993387029859c2d9d051c41c724eStephen Hinesstatic bool shouldKeep(const std::string& pName) { 5287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines static const unsigned int pattern_size = 5337b74a387bb3993387029859c2d9d051c41c724eStephen Hines sizeof(pattern_to_keep) / sizeof(pattern_to_keep[0]); 5437b74a387bb3993387029859c2d9d051c41c724eStephen Hines for (unsigned int i = 0; i < pattern_size; ++i) { 5587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines if (fnmatch0(pattern_to_keep[i], pName.c_str())) 5687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines return true; 5787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines } 5887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines return false; 5987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 6087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 6187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines/// shouldProcessGC - check if the section kind is handled in GC 6237b74a387bb3993387029859c2d9d051c41c724eStephen Hinesstatic bool mayProcessGC(const LDSection& pSection) { 630dea6bc96bb52346737966839ac68644f7939f58Stephen Hines if (pSection.kind() == LDFileFormat::TEXT || 640dea6bc96bb52346737966839ac68644f7939f58Stephen Hines pSection.kind() == LDFileFormat::DATA || 6587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines pSection.kind() == LDFileFormat::BSS || 6687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines pSection.kind() == LDFileFormat::GCCExceptTable) 6787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines return true; 6887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines return false; 6987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 7087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 7187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines//===----------------------------------------------------------------------===// 7287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines// GarbageCollection::SectionReachedListMap 7387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines//===----------------------------------------------------------------------===// 7437b74a387bb3993387029859c2d9d051c41c724eStephen Hinesvoid GarbageCollection::SectionReachedListMap::addReference( 7537b74a387bb3993387029859c2d9d051c41c724eStephen Hines const LDSection& pFrom, 7637b74a387bb3993387029859c2d9d051c41c724eStephen Hines const LDSection& pTo) { 7787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines m_ReachedSections[&pFrom].insert(&pTo); 7887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 7987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 8087f34658dec9097d987d254a990ea7f311bfc95fStephen HinesGarbageCollection::SectionListTy& 8187f34658dec9097d987d254a990ea7f311bfc95fStephen HinesGarbageCollection::SectionReachedListMap::getReachedList( 8237b74a387bb3993387029859c2d9d051c41c724eStephen Hines const LDSection& pSection) { 8387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines return m_ReachedSections[&pSection]; 8487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 8587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 8687f34658dec9097d987d254a990ea7f311bfc95fStephen HinesGarbageCollection::SectionListTy* 8787f34658dec9097d987d254a990ea7f311bfc95fStephen HinesGarbageCollection::SectionReachedListMap::findReachedList( 8837b74a387bb3993387029859c2d9d051c41c724eStephen Hines const LDSection& pSection) { 8987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ReachedSectionsTy::iterator it = m_ReachedSections.find(&pSection); 9087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines if (it == m_ReachedSections.end()) 9187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines return NULL; 9287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines return &it->second; 9387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 9487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 9587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines//===----------------------------------------------------------------------===// 9687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines// GarbageCollection 9787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines//===----------------------------------------------------------------------===// 9887f34658dec9097d987d254a990ea7f311bfc95fStephen HinesGarbageCollection::GarbageCollection(const LinkerConfig& pConfig, 9987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines const TargetLDBackend& pBackend, 10087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines Module& pModule) 10137b74a387bb3993387029859c2d9d051c41c724eStephen Hines : m_Config(pConfig), m_Backend(pBackend), m_Module(pModule) { 10287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 10387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 10437b74a387bb3993387029859c2d9d051c41c724eStephen HinesGarbageCollection::~GarbageCollection() { 10587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 10687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 10737b74a387bb3993387029859c2d9d051c41c724eStephen Hinesbool GarbageCollection::run() { 10887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // 1. traverse all the relocations to set up the reached sections of each 10987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // section 11087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines setUpReachedSections(); 11187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines m_Backend.setUpReachedSectionsForGC(m_Module, m_SectionReachedListMap); 11287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 11387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // 2. get all sections defined the entry point 11487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines SectionVecTy entry; 11587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines getEntrySections(entry); 11687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 11787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // 3. find all the referenced sections those can be reached by entry 11887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines findReferencedSections(entry); 11987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 12087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // 4. stripSections - set the unreached sections to Ignore 12187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines stripSections(); 12287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines return true; 12387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 12487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 12537b74a387bb3993387029859c2d9d051c41c724eStephen Hinesvoid GarbageCollection::setUpReachedSections() { 12687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // traverse all the input relocations to setup the reached sections 12787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines Module::obj_iterator input, inEnd = m_Module.obj_end(); 12887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines for (input = m_Module.obj_begin(); input != inEnd; ++input) { 12987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines LDContext::sect_iterator rs, rsEnd = (*input)->context()->relocSectEnd(); 13087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines for (rs = (*input)->context()->relocSectBegin(); rs != rsEnd; ++rs) { 13187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // bypass the discarded relocation section 13287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // 1. its section kind is changed to Ignore. (The target section is a 13387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // discarded group section.) 13487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // 2. it has no reloc data. (All symbols in the input relocs are in the 13587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // discarded group sections) 13687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines LDSection* reloc_sect = *rs; 13787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines LDSection* apply_sect = reloc_sect->getLink(); 13887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines if ((LDFileFormat::Ignore == reloc_sect->kind()) || 13987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines (!reloc_sect->hasRelocData())) 14087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines continue; 14187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 14287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // bypass the apply target sections which are not handled by gc 14387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines if (!mayProcessGC(*apply_sect)) 14487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines continue; 14587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 14687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines bool add_first = false; 14787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines SectionListTy* reached_sects = NULL; 14887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines RelocData::iterator reloc_it, rEnd = reloc_sect->getRelocData()->end(); 14987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines for (reloc_it = reloc_sect->getRelocData()->begin(); reloc_it != rEnd; 15037b74a387bb3993387029859c2d9d051c41c724eStephen Hines ++reloc_it) { 15187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines Relocation* reloc = llvm::cast<Relocation>(reloc_it); 15287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ResolveInfo* sym = reloc->symInfo(); 15387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // only the target symbols defined in the input fragments can make the 15487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // reference 15537b74a387bb3993387029859c2d9d051c41c724eStephen Hines if (sym == NULL) 15687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines continue; 15787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines if (!sym->isDefine() || !sym->outSymbol()->hasFragRef()) 15887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines continue; 15987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 16087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // only the target symbols defined in the concerned sections can make 16187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // the reference 16287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines const LDSection* target_sect = 16337b74a387bb3993387029859c2d9d051c41c724eStephen Hines &sym->outSymbol()->fragRef()->frag()->getParent()->getSection(); 16487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines if (!mayProcessGC(*target_sect)) 16587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines continue; 16687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 16787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // setup the reached list, if we first add the element to reached list 16887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // of this section, create an entry in ReachedSections map 16987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines if (!add_first) { 17087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines reached_sects = &m_SectionReachedListMap.getReachedList(*apply_sect); 17187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines add_first = true; 17287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines } 17387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines reached_sects->insert(target_sect); 17487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines } 17587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines reached_sects = NULL; 17687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines add_first = false; 17787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines } 17887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines } 17987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 18087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 18137b74a387bb3993387029859c2d9d051c41c724eStephen Hinesvoid GarbageCollection::getEntrySections(SectionVecTy& pEntry) { 18287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // all the KEEP sections defined in ldscript are entries, traverse all the 18387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // input sections and check the SectionMap to find the KEEP sections 18487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines Module::obj_iterator obj, objEnd = m_Module.obj_end(); 18587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines SectionMap& sect_map = m_Module.getScript().sectionMap(); 18687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines for (obj = m_Module.obj_begin(); obj != objEnd; ++obj) { 18787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines const std::string input_name = (*obj)->name(); 18887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines LDContext::sect_iterator sect, sectEnd = (*obj)->context()->sectEnd(); 18987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines for (sect = (*obj)->context()->sectBegin(); sect != sectEnd; ++sect) { 19087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines LDSection* section = *sect; 19187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines if (!mayProcessGC(*section)) 19287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines continue; 19387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 19487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines SectionMap::Input* sm_input = 19537b74a387bb3993387029859c2d9d051c41c724eStephen Hines sect_map.find(input_name, section->name()).second; 19687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines if (((sm_input != NULL) && (InputSectDesc::Keep == sm_input->policy())) || 19787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines shouldKeep(section->name())) 19887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines pEntry.push_back(section); 19987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines } 20087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines } 20187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 202a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines // when building shared object or the --export-dynamic has been given, the 203a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines // global define symbols are entries 204a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines if (LinkerConfig::DynObj == m_Config.codeGenType() || 205a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines m_Config.options().exportDynamic()) { 20687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines NamePool::syminfo_iterator info_it, 20737b74a387bb3993387029859c2d9d051c41c724eStephen Hines info_end = m_Module.getNamePool().syminfo_end(); 20887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines for (info_it = m_Module.getNamePool().syminfo_begin(); info_it != info_end; 20937b74a387bb3993387029859c2d9d051c41c724eStephen Hines ++info_it) { 21087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ResolveInfo* info = info_it.getEntry(); 21137b74a387bb3993387029859c2d9d051c41c724eStephen Hines if (!info->isDefine() || info->isLocal() || 21287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines info->shouldForceLocal(m_Config)) 21387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines continue; 21487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines LDSymbol* sym = info->outSymbol(); 21537b74a387bb3993387029859c2d9d051c41c724eStephen Hines if (sym == NULL || !sym->hasFragRef()) 21687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines continue; 21787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 21887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // only the target symbols defined in the concerned sections can be 21987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // entries 22087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines const LDSection* sect = 22137b74a387bb3993387029859c2d9d051c41c724eStephen Hines &sym->fragRef()->frag()->getParent()->getSection(); 22287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines if (!mayProcessGC(*sect)) 22387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines continue; 22487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines pEntry.push_back(sect); 22587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines } 22687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines } 2270dea6bc96bb52346737966839ac68644f7939f58Stephen Hines 228a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines // when building executable or PIE 229a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines if (LinkerConfig::Exec == m_Config.codeGenType() || 230a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines m_Config.options().isPIE()) { 231a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines // 1. the entry symbol is the entry 232a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines LDSymbol* entry_sym = 233a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines m_Module.getNamePool().findSymbol(m_Backend.getEntry(m_Module)); 234a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines assert(entry_sym != NULL); 235a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines pEntry.push_back(&entry_sym->fragRef()->frag()->getParent()->getSection()); 236a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines 237a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines // 2. the symbols have been seen in dynamic objects are entries. If 238a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines // --export-dynamic is set, then these sections already been added. No need 239a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines // to add them again 240a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines if (!m_Config.options().exportDynamic()) { 241a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines NamePool::syminfo_iterator info_it, 242a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines info_end = m_Module.getNamePool().syminfo_end(); 24304c59f3b00def22b7c75f5a490c323cec58a7c71Stephen Hines for (info_it = m_Module.getNamePool().syminfo_begin(); 24404c59f3b00def22b7c75f5a490c323cec58a7c71Stephen Hines info_it != info_end; ++info_it) { 245a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines ResolveInfo* info = info_it.getEntry(); 246a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines if (!info->isDefine() || info->isLocal()) 247a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines continue; 248a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines 249a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines if (!info->isInDyn()) 250a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines continue; 251a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines 252a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines LDSymbol* sym = info->outSymbol(); 253a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines if (sym == NULL || !sym->hasFragRef()) 254a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines continue; 255a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines 256a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines // only the target symbols defined in the concerned sections can be 257a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines // entries 258a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines const LDSection* sect = 259a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines &sym->fragRef()->frag()->getParent()->getSection(); 260a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines if (!mayProcessGC(*sect)) 261a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines continue; 262a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines 263a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines pEntry.push_back(sect); 264a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines } 265a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines } 266a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines } 267a6c24dff8b7fa2551a3a885e77a2e814f5b764a2Stephen Hines 2680dea6bc96bb52346737966839ac68644f7939f58Stephen Hines // symbols set by -u should not be garbage collected. Set them entries. 2690dea6bc96bb52346737966839ac68644f7939f58Stephen Hines GeneralOptions::const_undef_sym_iterator usym; 2700dea6bc96bb52346737966839ac68644f7939f58Stephen Hines GeneralOptions::const_undef_sym_iterator usymEnd = 27137b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_Config.options().undef_sym_end(); 2720dea6bc96bb52346737966839ac68644f7939f58Stephen Hines for (usym = m_Config.options().undef_sym_begin(); usym != usymEnd; ++usym) { 2730dea6bc96bb52346737966839ac68644f7939f58Stephen Hines LDSymbol* sym = m_Module.getNamePool().findSymbol(*usym); 2740dea6bc96bb52346737966839ac68644f7939f58Stephen Hines assert(sym); 2750dea6bc96bb52346737966839ac68644f7939f58Stephen Hines ResolveInfo* info = sym->resolveInfo(); 2760dea6bc96bb52346737966839ac68644f7939f58Stephen Hines assert(info); 2770dea6bc96bb52346737966839ac68644f7939f58Stephen Hines if (!info->isDefine() || !sym->hasFragRef()) 2780dea6bc96bb52346737966839ac68644f7939f58Stephen Hines continue; 2790dea6bc96bb52346737966839ac68644f7939f58Stephen Hines // only the symbols defined in the concerned sections can be entries 2800dea6bc96bb52346737966839ac68644f7939f58Stephen Hines const LDSection* sect = &sym->fragRef()->frag()->getParent()->getSection(); 2810dea6bc96bb52346737966839ac68644f7939f58Stephen Hines if (!mayProcessGC(*sect)) 2820dea6bc96bb52346737966839ac68644f7939f58Stephen Hines continue; 2830dea6bc96bb52346737966839ac68644f7939f58Stephen Hines pEntry.push_back(sect); 2840dea6bc96bb52346737966839ac68644f7939f58Stephen Hines } 28587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 28687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 28737b74a387bb3993387029859c2d9d051c41c724eStephen Hinesvoid GarbageCollection::findReferencedSections(SectionVecTy& pEntry) { 28887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // list of sections waiting to be processed 28987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines typedef std::queue<const LDSection*> WorkListTy; 29087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines WorkListTy work_list; 29187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // start from each entry, resolve the transitive closure 29287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines SectionVecTy::iterator entry_it, entry_end = pEntry.end(); 29387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines for (entry_it = pEntry.begin(); entry_it != entry_end; ++entry_it) { 29487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // add entry point to work list 29587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines work_list.push(*entry_it); 29687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 29787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // add section from the work_list to the referencedSections until every 29887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // reached sections are added 29987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines while (!work_list.empty()) { 30087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines const LDSection* sect = work_list.front(); 30187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines work_list.pop(); 30287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // add section to the ReferencedSections, if the section has been put into 30387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // referencedSections, skip this section 30487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines if (!m_ReferencedSections.insert(sect).second) 30587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines continue; 30687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 30787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // get the section reached list, if the section do not has one, which 30887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // means no referenced between it and other sections, then skip it 30987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines SectionListTy* reach_list = 31037b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_SectionReachedListMap.findReachedList(*sect); 31137b74a387bb3993387029859c2d9d051c41c724eStephen Hines if (reach_list == NULL) 31287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines continue; 31387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 31487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // put the reached sections to work list, skip the one already be in 31587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // referencedSections 31687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines SectionListTy::iterator it, end = reach_list->end(); 31787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines for (it = reach_list->begin(); it != end; ++it) { 31887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines if (m_ReferencedSections.find(*it) == m_ReferencedSections.end()) 31987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines work_list.push(*it); 32087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines } 32187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines } 32287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines } 32387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 32487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 32537b74a387bb3993387029859c2d9d051c41c724eStephen Hinesvoid GarbageCollection::stripSections() { 32687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // Traverse all the input Regular and BSS sections, if a section is not found 32787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // in the ReferencedSections, then it should be garbage collected 32887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines Module::obj_iterator obj, objEnd = m_Module.obj_end(); 32987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines for (obj = m_Module.obj_begin(); obj != objEnd; ++obj) { 33087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines LDContext::sect_iterator sect, sectEnd = (*obj)->context()->sectEnd(); 33187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines for (sect = (*obj)->context()->sectBegin(); sect != sectEnd; ++sect) { 33287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines LDSection* section = *sect; 33387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines if (!mayProcessGC(*section)) 33487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines continue; 33587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 3360dea6bc96bb52346737966839ac68644f7939f58Stephen Hines if (m_ReferencedSections.find(section) == m_ReferencedSections.end()) { 33787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines section->setKind(LDFileFormat::Ignore); 3380dea6bc96bb52346737966839ac68644f7939f58Stephen Hines debug(diag::debug_print_gc_sections) << section->name() 3390dea6bc96bb52346737966839ac68644f7939f58Stephen Hines << (*obj)->name(); 3400dea6bc96bb52346737966839ac68644f7939f58Stephen Hines } 34187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines } 34287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines } 34387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 34487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // Traverse all the relocation sections, if its target section is set to 34587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // Ignore, then set the relocation section to Ignore as well 34687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines Module::obj_iterator input, inEnd = m_Module.obj_end(); 34787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines for (input = m_Module.obj_begin(); input != inEnd; ++input) { 34887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines LDContext::sect_iterator rs, rsEnd = (*input)->context()->relocSectEnd(); 34987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines for (rs = (*input)->context()->relocSectBegin(); rs != rsEnd; ++rs) { 35087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines LDSection* reloc_sect = *rs; 35187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines if (LDFileFormat::Ignore == reloc_sect->getLink()->kind()) 35287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines reloc_sect->setKind(LDFileFormat::Ignore); 35387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines } 35487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines } 35587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 35687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 35737b74a387bb3993387029859c2d9d051c41c724eStephen Hines} // namespace mcld 358