1 //===- IndenticalCodeFolding.cpp ------------------------------------------===//
2 //
3 // The MCLinker Project
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 #include "mcld/LD/IdenticalCodeFolding.h"
10
11 #include "mcld/GeneralOptions.h"
12 #include "mcld/Module.h"
13 #include "mcld/Fragment/RegionFragment.h"
14 #include "mcld/LD/LDContext.h"
15 #include "mcld/LD/LDSection.h"
16 #include "mcld/LD/RelocData.h"
17 #include "mcld/LD/Relocator.h"
18 #include "mcld/LD/ResolveInfo.h"
19 #include "mcld/LD/SectionData.h"
20 #include "mcld/LinkerConfig.h"
21 #include "mcld/MC/Input.h"
22 #include "mcld/Support/Demangle.h"
23 #include "mcld/Support/MsgHandling.h"
24 #include "mcld/Target/GNULDBackend.h"
25
26 #include <llvm/ADT/StringRef.h>
27 #include <llvm/Support/Casting.h>
28 #include <llvm/Support/Format.h>
29
30 #include <cassert>
31 #include <map>
32 #include <set>
33
34 #include <zlib.h>
35
36 namespace mcld {
37
isSymCtorOrDtor(const ResolveInfo & pSym)38 static bool isSymCtorOrDtor(const ResolveInfo& pSym) {
39 // We can always fold ctors and dtors since accessing function pointer in C++
40 // is forbidden.
41 llvm::StringRef name(pSym.name(), pSym.nameSize());
42 if (!name.startswith("_ZZ") && !name.startswith("_ZN")) {
43 return false;
44 }
45 return isCtorOrDtor(pSym.name(), pSym.nameSize());
46 }
47
IdenticalCodeFolding(const LinkerConfig & pConfig,const TargetLDBackend & pBackend,Module & pModule)48 IdenticalCodeFolding::IdenticalCodeFolding(const LinkerConfig& pConfig,
49 const TargetLDBackend& pBackend,
50 Module& pModule)
51 : m_Config(pConfig), m_Backend(pBackend), m_Module(pModule) {
52 }
53
foldIdenticalCode()54 void IdenticalCodeFolding::foldIdenticalCode() {
55 // 1. Find folding candidates.
56 FoldingCandidates candidate_list;
57 findCandidates(candidate_list);
58
59 // 2. Initialize constant section content
60 for (size_t i = 0; i < candidate_list.size(); ++i) {
61 candidate_list[i].initConstantContent(m_Backend, m_KeptSections);
62 }
63
64 // 3. Find identical code until convergence
65 bool converged = false;
66 size_t iterations = 0;
67 while (!converged && (iterations < m_Config.options().getICFIterations())) {
68 converged = matchCandidates(candidate_list);
69 ++iterations;
70 }
71 if (m_Config.options().printICFSections()) {
72 debug(diag::debug_icf_iterations) << iterations;
73 }
74
75 // 4. Fold the identical code
76 typedef std::set<Input*> FoldedObjects;
77 FoldedObjects folded_objs;
78 KeptSections::iterator kept, keptEnd = m_KeptSections.end();
79 size_t index = 0;
80 for (kept = m_KeptSections.begin(); kept != keptEnd; ++kept, ++index) {
81 LDSection* sect = (*kept).first;
82 Input* obj = (*kept).second.first;
83 size_t kept_index = (*kept).second.second;
84 if (index != kept_index) {
85 sect->setKind(LDFileFormat::Folded);
86 folded_objs.insert(obj);
87
88 if (m_Config.options().printICFSections()) {
89 KeptSections::iterator it = m_KeptSections.begin() + kept_index;
90 LDSection* kept_sect = (*it).first;
91 Input* kept_obj = (*it).second.first;
92 debug(diag::debug_icf_folded_section) << sect->name() << obj->name()
93 << kept_sect->name()
94 << kept_obj->name();
95 }
96 }
97 }
98
99 // Adjust the fragment reference of the folded symbols.
100 FoldedObjects::iterator fobj, fobjEnd = folded_objs.end();
101 for (fobj = folded_objs.begin(); fobj != fobjEnd; ++fobj) {
102 LDContext::sym_iterator sym, symEnd = (*fobj)->context()->symTabEnd();
103 for (sym = (*fobj)->context()->symTabBegin(); sym != symEnd; ++sym) {
104 if ((*sym)->hasFragRef() && ((*sym)->type() == ResolveInfo::Function)) {
105 LDSymbol* out_sym = (*sym)->resolveInfo()->outSymbol();
106 FragmentRef* frag_ref = out_sym->fragRef();
107 LDSection* sect = &(frag_ref->frag()->getParent()->getSection());
108 if (sect->kind() == LDFileFormat::Folded) {
109 size_t kept_index = m_KeptSections[sect].second;
110 LDSection* kept_sect = (*(m_KeptSections.begin() + kept_index)).first;
111 frag_ref->assign(kept_sect->getSectionData()->front(),
112 frag_ref->offset());
113 }
114 }
115 } // for each symbol
116 } // for each folded object
117 }
118
findCandidates(FoldingCandidates & pCandidateList)119 void IdenticalCodeFolding::findCandidates(FoldingCandidates& pCandidateList) {
120 Module::obj_iterator obj, objEnd = m_Module.obj_end();
121 for (obj = m_Module.obj_begin(); obj != objEnd; ++obj) {
122 std::set<const LDSection*> funcptr_access_set;
123 typedef std::map<LDSection*, LDSection*> CandidateMap;
124 CandidateMap candidate_map;
125 LDContext::sect_iterator sect, sectEnd = (*obj)->context()->sectEnd();
126 for (sect = (*obj)->context()->sectBegin(); sect != sectEnd; ++sect) {
127 switch ((*sect)->kind()) {
128 case LDFileFormat::TEXT: {
129 candidate_map.insert(std::make_pair(*sect, nullptr));
130 break;
131 }
132 case LDFileFormat::Relocation: {
133 LDSection* target = (*sect)->getLink();
134 if (target->kind() == LDFileFormat::TEXT) {
135 candidate_map[target] = *sect;
136 }
137
138 // Safe icf
139 if (m_Config.options().getICFMode() == GeneralOptions::ICF::Safe) {
140 RelocData::iterator rel, relEnd = (*sect)->getRelocData()->end();
141 for (rel = (*sect)->getRelocData()->begin(); rel != relEnd; ++rel) {
142 LDSymbol* sym = rel->symInfo()->outSymbol();
143 if (sym->hasFragRef() && (sym->type() == ResolveInfo::Function)) {
144 const LDSection* def =
145 &sym->fragRef()->frag()->getParent()->getSection();
146 if (!isSymCtorOrDtor(*rel->symInfo()) &&
147 m_Backend.mayHaveUnsafeFunctionPointerAccess(*target) &&
148 m_Backend.getRelocator()
149 ->mayHaveFunctionPointerAccess(*rel)) {
150 funcptr_access_set.insert(def);
151 }
152 }
153 } // for each reloc
154 }
155
156 break;
157 }
158 default: {
159 // skip
160 break;
161 }
162 } // end of switch
163 } // for each section
164
165 CandidateMap::iterator candidate, candidateEnd = candidate_map.end();
166 for (candidate = candidate_map.begin(); candidate != candidateEnd;
167 ++candidate) {
168 if ((m_Config.options().getICFMode() == GeneralOptions::ICF::All) ||
169 (funcptr_access_set.count(candidate->first) == 0)) {
170 size_t index = m_KeptSections.size();
171 m_KeptSections[candidate->first] = ObjectAndId(*obj, index);
172 pCandidateList.push_back(
173 FoldingCandidate(candidate->first, candidate->second, *obj));
174 }
175 } // for each possible candidate
176 } // for each obj
177 }
178
matchCandidates(FoldingCandidates & pCandidateList)179 bool IdenticalCodeFolding::matchCandidates(FoldingCandidates& pCandidateList) {
180 typedef std::multimap<uint32_t, size_t> ChecksumMap;
181 ChecksumMap checksum_map;
182 std::vector<std::string> contents(pCandidateList.size());
183 bool converged = true;
184
185 for (size_t index = 0; index < pCandidateList.size(); ++index) {
186 contents[index] = pCandidateList[index].getContentWithVariables(
187 m_Backend, m_KeptSections);
188 uint32_t checksum = ::crc32(0xFFFFFFFF,
189 (const uint8_t*)contents[index].c_str(),
190 contents[index].length());
191
192 size_t count = checksum_map.count(checksum);
193 if (count == 0) {
194 checksum_map.insert(std::make_pair(checksum, index));
195 } else {
196 std::pair<ChecksumMap::iterator, ChecksumMap::iterator> ret =
197 checksum_map.equal_range(checksum);
198 for (ChecksumMap::iterator it = ret.first; it != ret.second; ++it) {
199 size_t kept_index = (*it).second;
200 if (contents[index].compare(contents[kept_index]) == 0) {
201 m_KeptSections[pCandidateList[index].sect].second = kept_index;
202 converged = false;
203 break;
204 }
205 }
206 }
207 }
208
209 return converged;
210 }
211
initConstantContent(const TargetLDBackend & pBackend,const IdenticalCodeFolding::KeptSections & pKeptSections)212 void IdenticalCodeFolding::FoldingCandidate::initConstantContent(
213 const TargetLDBackend& pBackend,
214 const IdenticalCodeFolding::KeptSections& pKeptSections) {
215 // Get the static content from text.
216 assert(sect != NULL && sect->hasSectionData());
217 SectionData::const_iterator frag, fragEnd = sect->getSectionData()->end();
218 for (frag = sect->getSectionData()->begin(); frag != fragEnd; ++frag) {
219 switch (frag->getKind()) {
220 case Fragment::Region: {
221 const RegionFragment& region = llvm::cast<RegionFragment>(*frag);
222 content.append(region.getRegion().begin(), region.size());
223 break;
224 }
225 default: {
226 // FIXME: Currently we only take care of RegionFragment.
227 break;
228 }
229 }
230 }
231
232 // Get the static content from relocs.
233 if (reloc_sect != NULL && reloc_sect->hasRelocData()) {
234 for (Relocation& rel : *reloc_sect->getRelocData()) {
235 llvm::format_object<Relocation::Type,
236 Relocation::Address,
237 Relocation::Address,
238 Relocation::Address> rel_info("%x%llx%llx%llx",
239 rel.type(),
240 rel.symValue(),
241 rel.addend(),
242 rel.place());
243 char rel_str[48];
244 rel_info.print(rel_str, sizeof(rel_str));
245 content.append(rel_str);
246
247 // Handle the recursive call.
248 LDSymbol* sym = rel.symInfo()->outSymbol();
249 if ((sym->type() == ResolveInfo::Function) && sym->hasFragRef()) {
250 LDSection* def = &sym->fragRef()->frag()->getParent()->getSection();
251 if (def == sect) {
252 continue;
253 }
254 }
255
256 if (!pBackend.isSymbolPreemptible(*rel.symInfo()) && sym->hasFragRef() &&
257 (pKeptSections.find(
258 &sym->fragRef()->frag()->getParent()->getSection()) !=
259 pKeptSections.end())) {
260 // Mark this reloc as a variable.
261 variable_relocs.push_back(&rel);
262 } else {
263 // TODO: Support inlining merge sections if possible (target-dependent).
264 if ((sym->binding() == ResolveInfo::Local) ||
265 (sym->binding() == ResolveInfo::Absolute)) {
266 // ABS or Local symbols.
267 content.append(sym->name()).append(obj->name()).append(
268 obj->path().native());
269 } else {
270 content.append(sym->name());
271 }
272 }
273 }
274 }
275 }
276
getContentWithVariables(const TargetLDBackend & pBackend,const IdenticalCodeFolding::KeptSections & pKeptSections)277 std::string IdenticalCodeFolding::FoldingCandidate::getContentWithVariables(
278 const TargetLDBackend& pBackend,
279 const IdenticalCodeFolding::KeptSections& pKeptSections) {
280 std::string result(content);
281 // Compute the variable content from relocs.
282 std::vector<Relocation*>::const_iterator rel, relEnd = variable_relocs.end();
283 for (rel = variable_relocs.begin(); rel != relEnd; ++rel) {
284 LDSymbol* sym = (*rel)->symInfo()->outSymbol();
285 LDSection* def = &sym->fragRef()->frag()->getParent()->getSection();
286 // Use the kept section index.
287 KeptSections::const_iterator it = pKeptSections.find(def);
288 llvm::format_object<size_t> kept_info("%x", (*it).second.second);
289 char kept_str[8];
290 kept_info.print(kept_str, sizeof(kept_str));
291 result.append(kept_str);
292 }
293
294 return result;
295 }
296
297 } // namespace mcld
298