ELF: Implement ICF.

[ruiu]

Summary

This patch is in my queue for a long period of time, so I'd like
to flush this although it is not still compatible with most C++
programs.

This patch implements the same algorithm as LLD/COFF's ICF. I'm
not going to repeat the same description about how it works, so you
want to read the comment in ICF.cpp in this patch. This algorithm
should be more powerful than GNU gold ICF algorithm. It can even
merge mutually-recursive functions (which is harder than one might
think).

The lacking feature is "safe" version of ICF. This merges all
identical sections. That is not compatible with a C/C++ language
requirement that two distinct functions must not have the address.

But as long as your program do not rely on pointer equality,
your program should work with this patch. LLD works fine for
example.

GNU gold implements so-called "safe ICF" that identifies functions
that are safe to merge by heuristics -- for example, gold thinks
that constructors are safe to merge because there is no way to
take an address of a constructor in C++. We have a different idea
which David Majnemer suggested, which is to add NOPs at beginning
of merged functions so that two or more pointers can have distinct
values. We can do whichever we want, but this patch does not
include neither.

[ruiu]

• corrected a few typos.

[silvas]

The lacking feature is "safe" version of ICF. This merges all
identical sections. That is not compatible with C/C++ language
requirement that two distinct functions must not have the address.
I think violation this rule breaks many C++ ABIs.

How does the COFF ICF avoid this problem?

We have a different idea
which David Majnemer suggested, which is to add NOPs at beginning
of merged functions so that two or more pointers can have distinct
values.

If we do this, we need to be careful to not misalign the function as emitted by the compiler. E.g. even if we only need to insert a single nop before the current section contents, we still want to grow the section by the section's alignment.

ELF/ICF.cpp

16

Don't you use a partition-refinement approach instead of a graph approach? Why mention graphs?

ELF/InputSection.h

182

I know we aren't currently optimizing the sizeof of InputSection, but we should be aware of it since we potentially allocate many.
Out of curiosity, have you measured if the extra memory pressure of this GroupId causes any performance change?
It it has an adverse effect, we can always merge it with OutSecOff, since I don't think we need both simultaneously. (or we can make sure that Repl always points to a canonical group member).

[silvas]

ELF/ICF.cpp

285

Why only the first element of RelocSections?

[• rafael]

ELF/ICF.cpp

10

On ELF it is possible to merge non COMDAT sections. We can keep the acronym by doing what gold does and calling this Identical *Code* Folding.

[• rafael]

ELF/ICF.cpp

118

Assert that there only one? Return 0 if there is none?

120

It might be cleaner to just say RelSec->sh_size/RelSec->sh_entsize;

128

Not exactly true since the number of relocations is included.

Since this is the only use of numRels and it is only used for hashing, how about just using RelSec->sh_size?

150

Why only PROGBITS? OK if it is just to keep it simple for now.

168

Return true if a new group was created.

This could also return void and have the caller check NextId.

232

I don't think this is possible.

It is all SHT_RELA or SHT_REL.

247

It is possible to merge when the alignment is different, we just have to keep the larger one. A fixme for now is fine.

262

The same 'if' is in equalsContant. Do you need it here?

268

If both are null they could still be equal, no?

FIXME for now is fine.

272

This is also conservatively correct, right?

Two relocations pointing to the string "foobar" in a SHF_MERGE section are equivalent.

311

Do we need stable_sort to make this deterministic?

ELF/InputSection.cpp

31

When is Config null?

75

Can you commit the const fixes first?

ELF/OutputSections.cpp

1151

Can you commit the s/isLife/Life/ change first?

ELF/Symbols.h

236

Not sure I follow. Why is this not redundant with the Repl pointer in the section?

[silvas]

ELF/ICF.cpp

169

The naming of this function is confusing. The name 'partition' makes it sound like it is algorithmically similar to std::partition, but it doesn't do the same thing. I would maybe call it 'segregate'.

173

Please add a comment about the loop invariant. Currently it seems to be

• No element of [I,End) compares equal via Eq to any element in [Begin,I).
• If two elements of [Begin,I) compare equal via Eq, then they are part of a contiguous run of elements that all pairwise compare equal via Eq.

Also, this function is quadratic in the number of distinct elements (as determined by Eq). It is probably worth a comment explaining this and why pathological cases are not expected to happen. Without a stronger structure than Eq (e.g. a < ordering) I don't think it is actually algorithmically possible to make this non-quadratic though (since when Eq returns false you don't gain any information that can be transitively used.).

Note that in ICF<ELFT>::run the patch does a *sort* based on the hash (i.e. uses a stronger < structure). I believe the overall algorithm is actually correct without the initial hash assignment/sorting; it will just be quadratic in the size of the input instead of the maximum equivalence class size after the initial sort.

205

relocationsEq is probably a better name. Otherwise we have a function equalsConstant calling a function called constantEq which is confusing.

[ruiu]

ELF/ICF.cpp

10

Done.

118

Done.

120

Done.

128

Done.

150

It doesn't have to be PROGBITS only. Removed.

168

Done.

232

Removed.

247

Done.

262

Removed.

268

Yes, and in that case the above if (SA== SB) should be true, so it should already be covered.

272

I believe the above if (SA == SB) should cover most cases already.

311

Done.

ELF/InputSection.cpp

31

Discarded section is initialized statically, and when it is initialized, Config is still null.

75

Done.

ELF/OutputSections.cpp

1151

Done.

ELF/Symbols.h

236

In many places we write Sym->Section to get an input section for the symbol. We either update all such occurrences with Sym->Section->Repl, or make Section a reference like this.

[ruiu]

• Address review comments.

[ruiu]

• Address Sean's comments.

ELF/ICF.cpp

171

Done.

175

Done.

207

Done.

[ruiu]

• Make forEachGroup and segregate return void.

[silvas]

Some tiny wordsmithing nits.

ELF/ICF.cpp

169

I would say "rearranges" instead of "sorts", since "sort" implies an absolute order.

170

I think it is worth clarifying that it is quadratic in the number of *distinct* sections.

[ruiu]

• Update comment.

ELF/ICF.cpp

169

Done.

170

Done.

[• rafael]

ELF/ICF.cpp

121

The comment is out of date.

124

Range loop?

256

Two absolute relocations to different values would show up as equal in here, no?

Same issue for two relocations pointing to different strings.

[ruiu]

• Address review comments.
• Fixed a mislinking bug. Now it is able to link lld and clang with ICF enabled. All tests has passed except Clang's crash-report tests (it seems to have messed up something in stacktrace.)

[ruiu]

• Added a test for .init and .fini.

[ruiu]

• Removed dead code.

[grimar]

ELF/ICF.cpp

347

Knowing that you like to reduce the code:

while (++Cnt) {
...

365

What about to separate verbose() method to error.cpp file ?
Something alike:

void verbose(Twine Msg) {
  if (Config->Verbose)
    llvm::outs() << Msg;
}

Then it can be used from another code.

ELF/InputSection.h

49

s/instnace/instance

52

ditto

182

This comment is very tight. It has no value as anyone who look at this variable can quick search and find that it is used somewhere in ICF.
I suggest to expand or to remove it.

[• rafael]

Can you add a test showing that we merge sections with different alignments and keep the largest?

LGTM with that and George's suggestions addressed.

Thanks a lot!

[ruiu]

ELF/ICF.cpp

121

Done.

124

Done.

347

I love short and readable code but I don't think it's readable. Cnt is not a loop terminating condition and it just happened to be always true (so as a result it happens to work.) Your code is semantically equivalent to

for (;;) {
  if (++Cnt)
    break;

which is rather confusing.

365

That may be a good idea. I'm not going to do that in this patch, but it worths trying.

ELF/InputSection.h

182

I think the comments are valuable for first-time readers.

[ruiu]

Committed as r261912.

[grimar]

ELF/InputSection.h

182

Of course. What I meant - for me as for first time reader of this, it is not clear anyways what GroupId do from this comment.
It says it is used in ICF, that what I can find in few seconds, but question is "for what", right ? Comments should explain the details and not the obvious things.

[grimar]

I am observing multiple crashes in tests for this atm. All ICF tests are affected, using the latest code of lld. Going to debug it right now.
Example:

23> ****
23> FAIL: lld :: ELF/icf1.s (215 of 1104)
23> **** TEST 'lld :: ELF/icf1.s' FAILED ****
23> Script:
23> --
23> C:/access_softek/c_make_build_dir/Debug/bin\llvm-mc.EXE -filetype=obj -triple=x86_64-unknown-linux C:\access_softek\llvm\tools\lld\test\ELF\icf1.s -o C:\access_softek\c_make_build_dir\tools\lld\test\ELF\Output\icf1.s.tmp
23> C:/access_softek/c_make_build_dir/Debug/bin\ld.lld.EXE C:\access_softek\c_make_build_dir\tools\lld\test\ELF\Output\icf1.s.tmp -o C:\access_softek\c_make_build_dir\tools\lld\test\ELF\Output\icf1.s.tmp2 --icf=all --verbose | C:/access_softek/c_make_build_dir/Debug/bin\FileCheck.EXE C:\access_softek\llvm\tools\lld\test\ELF\icf1.s
23> --
23> Exit Code: 2
23>
23> Command Output (stdout):
23> --
23> Command 0: "C:/access_softek/c_make_build_dir/Debug/bin\llvm-mc.EXE" "-filetype=obj" "-triple=x86_64-unknown-linux" "C:\access_softek\llvm\tools\lld\test\ELF\icf1.s" "-o" "C:\access_softek\c_make_build_dir\tools\lld\test\ELF\Output\icf1.s.tmp"
23> Command 0 Result: 0
23> Command 0 Output:
23>
23>
23> Command 0 Stderr:
23>
23>
23> Command 1: "C:/access_softek/c_make_build_dir/Debug/bin\ld.lld.EXE" "C:\access_softek\c_make_build_dir\tools\lld\test\ELF\Output\icf1.s.tmp" "-o" "C:\access_softek\c_make_build_dir\tools\lld\test\ELF\Output\icf1.s.tmp2" "--icf=all" "--verbose"
23> Command 1 Result: -2147483645
23> Command 1 Output:
23>
23>
23> Command 1 Stderr:
23> 0x54322AA6 (0x03427A60 0x03427788 0x00000048 0x002B7887), ?_Debug_message@std@@YAXPB_W0I@Z() + 0x26 bytes(s)
23>
23> 0x029DF23E (0x0522F3B0 0x0522F3F8 0x029E88C6 0x044A1DE4), std::_Vector_const_iterator<std::_Vector_val<std::_Simple_types<lld::elf2::InputSection<llvm::object::ELFType<1,1> > *> > >::operator*() + 0x5E bytes(s), c:\program files (x86)\microsoft visual studio 14.0\vc\include\vector, line 72 + 0x14 byte(s)
23>
23> 0x029DF676 (0x044A1DE4 0x002D6C14 0x0522F3B0 0x00000000), std::_Vector_iterator<std::_Vector_val<std::_Simple_types<lld::elf2::InputSection<llvm::object::ELFType<1,1> > *> > >::operator*() + 0x16 bytes(s), c:\program files (x86)\microsoft visual studio 14.0\vc\include\vector, line 326
23>
23> 0x029E88C6 (0x0522F55C 0x044A1DE4 0x002D6C14 0x029EB753), lld::elf2::ICF<llvm::object::ELFType<1,1> >::forEachGroup() + 0xA6 bytes(s), c:\access_softek\llvm\tools\lld\elf\icf.cpp, line 209 + 0x16 byte(s)
23>
23> 0x029EB771 (0x0522F6CC 0x00000001 0x00000000 0x0522F7D0), lld::elf2::ICF<llvm::object::ELFType<1,1> >::run() + 0xF1 bytes(s), c:\access_softek\llvm\tools\lld\elf\icf.cpp, line 344
23>
23> 0x029D6C2F (0x0522F6CC 0x0522F8AC 0x04493668 0xCCCCCCCC), lld::elf2::doIcf<llvm::object::ELFType<1,1> >() + 0x2F bytes(s), c:\access_softek\llvm\tools\lld\elf\icf.cpp, line 374
23>
23> 0x0294362A (0x0522F7F4 0x0522FA80 0x00000002 0xCCCCCCCC), lld::elf2::LinkerDriver::link<llvm::object::ELFType<1,1> >() + 0x51A bytes(s), c:\access_softek\llvm\tools\lld\elf\driver.cpp, line 380 + 0xC byte(s)
23>
23> 0x029355A1 (0x054836F4 0x00000005 0x0522FC58 0xCCCCCCCC), lld::elf2::LinkerDriver::main() + 0x111 bytes(s), c:\access_softek\llvm\tools\lld\elf\driver.cpp, line 182
23>
23> 0x029353CC (0x054836F0 0x00000006 0x046694C8 0x0522FCA4), lld::elf2::link() + 0x9C bytes(s), c:\access_softek\llvm\tools\lld\elf\driver.cpp, line 45
23>
23> 0x00446D98 (0x054836F0 0x00000006 0x046694C8 0x002B7887), lld::UniversalDriver::link() + 0x2B8 bytes(s), c:\access_softek\llvm\tools\lld\lib\driver\universaldriver.cpp, line 208 + 0x29 byte(s)
23>
23> 0x0044686A (0x00000006 0x054836F0 0x0547F590 0x0522FD10), main() + 0x5A bytes(s), c:\access_softek\llvm\tools\lld\tools\lld\lld.cpp, line 35 + 0x22 byte(s)
23>
23> 0x0333EFDE (0x2E988591 0x002B7887 0x002B7887 0x7F034000), invoke_main() + 0x1E bytes(s), f:\dd\vctools\crt\vcstartup\src\startup\exe_common.inl, line 74 + 0x1B byte(s)
23>
23> 0x0333EE2A (0x0522FD20 0x0333EFF8 0x0522FD34 0x77897C04), scrt_common_main_seh() + 0x15A bytes(s), f:\dd\vctools\crt\vcstartup\src\startup\exe_common.inl, line 264 + 0x5 byte(s)
23>
23> 0x0333ECBD (0x0522FD34 0x77897C04 0x7F034000 0x77897BE0), scrt_common_main() + 0xD bytes(s), f:\dd\vctools\crt\vcstartup\src\startup\exe_common.inl, line 309
23>
23> 0x0333EFF8 (0x7F034000 0x77897BE0 0x5D66FCE8 0x0522FD7C), mainCRTStartup() + 0x8 bytes(s), f:\dd\vctools\crt\vcstartup\src\startup\exe_main.cpp, line 17
23>
23> 0x77897C04 (0x7F034000 0x5D45F739 0x00000000 0x00000000), BaseThreadInitThunk() + 0x24 bytes(s)
23>
23> 0x77B0AD1F (0xFFFFFFFF 0x77AF024A 0x00000000 0x00000000), RtlInitializeExceptionChain() + 0x8F bytes(s)
23>
23> 0x77B0ACEA (0x002B7887 0x7F034000 0x00000000 0x00000000), RtlInitializeExceptionChain() + 0x5A bytes(s)

[grimar]

Problem is in

template <class ELFT>
void ICF<ELFT>::forEachGroup(std::vector<InputSection<ELFT> *> &V,
                             Comparator Eq) {
  for (auto I = V.begin(), E = V.end(); I != E;) {
    InputSection<ELFT> *Head = *I;
    auto Bound = std::find_if(I + 1, E, [&](InputSection<ELFT> *S) {
      return S->GroupId != Head->GroupId;
    });
    segregate(&*I, &*Bound, Eq);
    I = Bound;
  }
}

Bound == V.end() and that crashes at

segregate(&*I, &*Bound, Eq);

Have next values for V:
+ [0] 0x0096f698 {RelocSections={Val={Val={Value=0x00000000 } } } OutSecOff=0x0000000000000000 GroupId=0x8000000055626995 }
+ [1] 0x0096f6c8 {RelocSections={Val={Val={Value=0x00000000 } } } OutSecOff=0x0000000000000000 GroupId=0x8000000055626995 }
+ [2] 0x0096f668 {RelocSections={Val={Val={Value=0x00000000 } } } OutSecOff=0x0000000000000000 GroupId=0x80000000af442220 }
Head->GroupId == 0x8000000055626995

at first iteration it sets I to V[2]. Then on next one finds nothing, because I + 1 is already == E.
If I add next after "auto Bound ="

if (Bound == V.end())
  return;

all tests pass for me.

[ruiu]

Thank you for your investigation. On it.

[ruiu]

Should be fixed in r262022.

[grimar]

In D17529#362806, @ruiu wrote:

Should be fixed in r262022.

Yep, fixed for me. Thanks !

[ruiu]

ELF/InputSection.h

182

That is explained in ICF.cpp so we don't want to repeat that in the other file. The point is that you can just ignore this field unless you are working on ICF because it is used (only) by ICF.

ELF/CMakeLists.txt

 set(LLVM_TARGET_DEFINITIONS Options.td)
 tablegen(LLVM Options.inc -gen-opt-parser-defs)
 add_public_tablegen_target(ELFOptionsTableGen)
 
 add_lld_library(lldELF2
   Driver.cpp
   DriverUtils.cpp
   Error.cpp
+  ICF.cpp
   InputFiles.cpp
   InputSection.cpp
   LinkerScript.cpp
   MarkLive.cpp
   OutputSections.cpp
   SymbolTable.cpp
   Symbols.cpp
   Target.cpp

ELF/Config.h

struct Configuration {
   bool DiscardAll;
   bool DiscardLocals;
   bool DiscardNone;
   bool EhFrameHdr;
   bool EnableNewDtags;
   bool ExportDynamic;
   bool GcSections;
   bool GnuHash = false;
+  bool ICF;
   bool Mips64EL = false;
   bool NoInhibitExec;
   bool NoUndefined;
   bool PrintGcSections;
   bool Shared;
   bool Static = false;
   bool StripAll;
   bool SysvHash = true;

ELF/Driver.cpp

 //===- Driver.cpp ---------------------------------------------------------===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "Driver.h"
 #include "Config.h"
 #include "Error.h"
+#include "ICF.h"
 #include "InputFiles.h"
 #include "LinkerScript.h"
 #include "SymbolTable.h"
 #include "Target.h"
 #include "Writer.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Support/TargetSelect.h"
void LinkerDriver::readConfigs(opt::InputArgList &Args) {
   Config->Demangle = !Args.hasArg(OPT_no_demangle);
   Config->DiscardAll = Args.hasArg(OPT_discard_all);
   Config->DiscardLocals = Args.hasArg(OPT_discard_locals);
   Config->DiscardNone = Args.hasArg(OPT_discard_none);
   Config->EhFrameHdr = Args.hasArg(OPT_eh_frame_hdr);
   Config->EnableNewDtags = !Args.hasArg(OPT_disable_new_dtags);
   Config->ExportDynamic = Args.hasArg(OPT_export_dynamic);
   Config->GcSections = Args.hasArg(OPT_gc_sections);
+  Config->ICF = Args.hasArg(OPT_icf);
   Config->NoInhibitExec = Args.hasArg(OPT_noinhibit_exec);
   Config->NoUndefined = Args.hasArg(OPT_no_undefined);
   Config->PrintGcSections = Args.hasArg(OPT_print_gc_sections);
   Config->Shared = Args.hasArg(OPT_shared);
   Config->StripAll = Args.hasArg(OPT_strip_all);
   Config->Verbose = Args.hasArg(OPT_verbose);
 
   Config->DynamicLinker = getString(Args, OPT_dynamic_linker);
template <class ELFT> void LinkerDriver::link(opt::InputArgList &Args) {
 
   if (Config->OutputFile.empty())
     Config->OutputFile = "a.out";
 
   // Write the result to the file.
   Symtab.scanShlibUndefined();
   if (Config->GcSections)
     markLive<ELFT>(&Symtab);
+  if (Config->ICF)
+    doIcf<ELFT>(&Symtab);
   writeResult<ELFT>(&Symtab);
 }

ELF/ICF.h

+//===- ICF.h --------------------------------------------------------------===//
+//
+//                             The LLVM Linker
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLD_ELF_ICF_H
+#define LLD_ELF_ICF_H
+
+namespace lld {
+namespace elf2 {
+
+template <class ELFT> class SymbolTable;
+
+template <class ELFT> void doIcf(SymbolTable<ELFT> *);
+}
+}
+
+#endif

ELF/ICF.cpp

+//===- ICF.cpp ------------------------------------------------------------===//
+//
+//                             The LLVM Linker
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Identical COMDAT Folding is a feature to merge COMDAT sections not by
+// name (which is regular COMDAT handling) but by contents. If two COMDAT
+// sections have the same data, relocations, attributes, etc., then the two
+// are considered identical and merged by the linker. This optimization
+// makes outputs smaller.
+//
+// ICF is theoretically a problem of reducing graphs by merging as many
+// identical subgraphs as possible if we consider sections as vertices and
+// relocations as edges. It may sound simple, but it is a bit more
+// complicated than you might think. The order of processing sections
+// matters because merging two sections can make other sections, whose
+// relocations now point to the same section, mergeable. Graphs may contain
+// cycles. We need a sophisticated algorithm to do this properly and
+// efficiently.
+//
+// What we do in this file is this. We split sections into groups. Sections
+// in the same group are considered identical.
+//
+// First, all sections are grouped by their "constant" values. Constant
+// values are values that are never changed by ICF, such as section contents,
+// section name, number of relocations, type and offset of each relocation,
+// etc. Because we do not care about some relocation targets in this step,
+// two sections in the same group may not be identical, but at least two
+// sections in different groups can never be identical.
+//
+// Then, we try to split each group by relocation targets. Relocations are
+// considered identical if and only if the relocation targets are in the
+// same group. Splitting a group may make more groups to be splittable,
+// because two relocations that were previously considered identical might
+// now point to different groups. We repeat this step until the convergence
+// is obtained.
+//
+// Our algorithm is smart enough to merge the following two functions.
+//
+//   void foo() { bar(); }
+//   void bar() { foo(); }
+//
+// This algorithm is so-called "optimistic" algorithm described in
+// http://research.google.com/pubs/pub36912.html. (Note that what GNU
+// gold implemented is different from the optimistic algorithm.)
+//
+//===----------------------------------------------------------------------===//
+
+#include "ICF.h"
+#include "Config.h"
+#include "OutputSections.h"
+#include "SymbolTable.h"
+
+#include "llvm/ADT/Hashing.h"
+#include "llvm/Object/ELF.h"
+#include "llvm/Support/ELF.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace lld;
+using namespace lld::elf2;
+using namespace llvm;
+using namespace llvm::ELF;
+using namespace llvm::object;
+
+namespace lld {
+namespace elf2 {
+template <class ELFT> class ICF {
+  typedef typename ELFFile<ELFT>::Elf_Shdr Elf_Shdr;
+  typedef typename ELFFile<ELFT>::Elf_Sym Elf_Sym;
+  typedef typename ELFFile<ELFT>::uintX_t uintX_t;
+
+  using Comparator = std::function<bool(const InputSection<ELFT> *,
+                                        const InputSection<ELFT> *)>;
+
+public:
+  void run(SymbolTable<ELFT> *Symtab);
+
+private:
+  uint64_t NextId = 1;
+
+  static void setLive(SymbolTable<ELFT> *S);
+  static uint64_t numRels(InputSection<ELFT> *S);
+  static uint64_t getHash(InputSection<ELFT> *S);
+  static bool isEligible(InputSectionBase<ELFT> *Sec);
+  static std::vector<InputSection<ELFT> *> getSections(SymbolTable<ELFT> *S);
+
+  bool partition(InputSection<ELFT> **Begin, InputSection<ELFT> **End,
+                 Comparator Eq);
+
+  bool forEachGroup(std::vector<InputSection<ELFT> *> &V, Comparator Eq);
+
+  template <class RelTy>
+  static bool constantEq(iterator_range<const RelTy *> RA,
+                         iterator_range<const RelTy *> RB);
+
+  template <class RelTy>
+  static bool variableEq(const InputSection<ELFT> *A,
+                         const InputSection<ELFT> *B,
+                         iterator_range<const RelTy *> RA,
+                         iterator_range<const RelTy *> RB);
+
+  static bool equalsConstant(const InputSection<ELFT> *A,
+                             const InputSection<ELFT> *B);
+
+  static bool equalsVariable(const InputSection<ELFT> *A,
+                             const InputSection<ELFT> *B);
+};
+}
+}
+
+// Returns the number of relocations that S has.
+template <class ELFT> uint64_t ICF<ELFT>::numRels(InputSection<ELFT> *S) {
+  ELFFile<ELFT> &EObj = S->File->getObj();
+  const Elf_Shdr *RelSec = S->RelocSections[0];
+
+  if (RelSec->sh_type == SHT_RELA) {
+    auto Rels = EObj.relas(RelSec);
+    return Rels.end() - Rels.begin();
+  }
+  auto Rels = EObj.rels(RelSec);
+  return Rels.end() - Rels.begin();
+}
+
+// Returns a hash value for S. Note that relocation information is not
+// included in the hash value.
+template <class ELFT> uint64_t ICF<ELFT>::getHash(InputSection<ELFT> *S) {
+  uint64_t H = hash_combine((uint64_t)S->getSectionHdr()->sh_flags,
+                            S->getSize(), S->getAlign());
+  if (S->RelocSections.empty())
+    return H;
+  return hash_combine(H, numRels(S));
+}
+
+// Returns true if Sec is subject of ICF.
+template <class ELFT> bool ICF<ELFT>::isEligible(InputSectionBase<ELFT> *Sec) {
+  if (!Sec || Sec == &InputSection<ELFT>::Discarded || !Sec->Live)
+    return false;
+  auto *S = dyn_cast<InputSection<ELFT>>(Sec);
+  if (!S)
+    return false;
+  if (S->RelocSections.size() > 1)
+    // Technically, nothing wrong with sections with more than one relocation
+    // sections, but we don't bother handling such unusual ones.
+    return false;
+  const Elf_Shdr &H = *S->getSectionHdr();
+  return H.sh_type == SHT_PROGBITS &&
+         (H.sh_flags & SHF_ALLOC) &&
+         (~H.sh_flags & SHF_WRITE);
+}
+
+template <class ELFT>
+std::vector<InputSection<ELFT> *>
+ICF<ELFT>::getSections(SymbolTable<ELFT> *Symtab) {
+  std::vector<InputSection<ELFT> *> V;
+  for (const std::unique_ptr<ObjectFile<ELFT>> &F : Symtab->getObjectFiles())
+    for (InputSectionBase<ELFT> *S : F->getSections())
+      if (isEligible(S))
+        V.push_back(cast<InputSection<ELFT>>(S));
+  return V;
+}
+
+// Compare sections between Begin and End using Eq and assign new group IDs
+// for new groups.
+template <class ELFT>
+bool ICF<ELFT>::partition(InputSection<ELFT> **Begin, InputSection<ELFT> **End,
+                          Comparator Eq) {
+  bool Ret = false;
+  InputSection<ELFT> **I = Begin;
+  for (;;) {
+    InputSection<ELFT> *Head = *I;
+    auto Bound = std::partition(
+        I + 1, End, [&](InputSection<ELFT> *S) { return Eq(Head, S); });
+    if (Bound == End)
+      return Ret;
+    uint64_t Id = NextId++;
+    for (; I != Bound; ++I)
+      (*I)->GroupId = Id;
+    Ret = true;
+  }
+}
+
+template <class ELFT>
+bool ICF<ELFT>::forEachGroup(std::vector<InputSection<ELFT> *> &V,
+                             Comparator Eq) {
+  bool Ret = false;
+  for (auto I = V.begin(), E = V.end(); I != E;) {
+    InputSection<ELFT> *Head = *I;
+    auto Bound = std::find_if(I + 1, E, [&](InputSection<ELFT> *S) {
+      return S->GroupId != Head->GroupId;
+    });
+    if (partition(&*I, &*Bound, Eq))
+      Ret = true;
+    I = Bound;
+  }
+  return Ret;
+}
+
+// Compare two list of relocations.
+template <class ELFT>
+template <class RelTy>
+bool ICF<ELFT>::constantEq(iterator_range<const RelTy *> RelsA,
+                           iterator_range<const RelTy *> RelsB) {
+  const RelTy *IA = RelsA.begin();
+  const RelTy *EA = RelsA.end();
+  const RelTy *IB = RelsB.begin();
+  const RelTy *EB = RelsB.end();
+  if (EA - IA != EB - IB)
+    return false;
+  for (; IA != EA; ++IA, ++IB)
+    if (IA->r_offset != IB->r_offset ||
+        IA->getType(Config->Mips64EL) != IB->getType(Config->Mips64EL) ||
+        getAddend<ELFT>(*IA) != getAddend<ELFT>(*IB))
+      return false;
+  return true;
+}
+
+// Compare "non-moving" part of two InputSections, namely everything
+// except relocations.
+template <class ELFT>
+bool ICF<ELFT>::equalsConstant(const InputSection<ELFT> *A,
+                               const InputSection<ELFT> *B) {
+  if (A->RelocSections.size() != B->RelocSections.size())
+    return false;
+
+  if (!A->RelocSections.empty()) {
+    const Elf_Shdr *RA = A->RelocSections[0];
+    const Elf_Shdr *RB = B->RelocSections[0];
+    if (RA->sh_type != RB->sh_type)
+      return false;
+    ELFFile<ELFT> &FileA = A->File->getObj();
+    ELFFile<ELFT> &FileB = B->File->getObj();
+    if (RA->sh_type == SHT_RELA) {
+      if (!constantEq(FileA.relas(RA), FileB.relas(RB)))
+        return false;
+    } else {
+      if (!constantEq(FileA.rels(RA), FileB.rels(RB)))
+        return false;
+    }
+  }
+
+  return A->getSectionHdr()->sh_flags == B->getSectionHdr()->sh_flags &&
+         A->getSize() == B->getSize() &&
+         A->getAlign() == B->getAlign() &&
+         A->getSectionData() == B->getSectionData();
+}
+
+template <class ELFT>
+template <class RelTy>
+bool ICF<ELFT>::variableEq(const InputSection<ELFT> *A,
+                           const InputSection<ELFT> *B,
+                           iterator_range<const RelTy *> RelsA,
+                           iterator_range<const RelTy *> RelsB) {
+  const RelTy *IA = RelsA.begin();
+  const RelTy *EA = RelsA.end();
+  const RelTy *IB = RelsB.begin();
+  const RelTy *EB = RelsB.end();
+  if (EA - IA != EB - IB)
+    return false;
+  for (; IA != EA; ++IA, ++IB) {
+    InputSectionBase<ELFT> *SA = A->getRelocTarget(*IA);
+    InputSectionBase<ELFT> *SB = B->getRelocTarget(*IB);
+    if (SA == SB)
+      continue;
+    if (!SA || !SB)
+      return false;
+    InputSection<ELFT> *X = dyn_cast<InputSection<ELFT>>(SA);
+    InputSection<ELFT> *Y = dyn_cast<InputSection<ELFT>>(SB);
+    if (!X || !Y || X->GroupId != Y->GroupId)
+      return false;
+  }
+  return true;
+}
+
+// Compare "moving" part of two InputSections, namely relocations.
+template <class ELFT>
+bool ICF<ELFT>::equalsVariable(const InputSection<ELFT> *A,
+                               const InputSection<ELFT> *B) {
+  if (A->RelocSections.empty())
+    return true;
+
+  const Elf_Shdr *RA = A->RelocSections[0];
+  const Elf_Shdr *RB = B->RelocSections[0];
+  ELFFile<ELFT> &FileA = A->File->getObj();
+  ELFFile<ELFT> &FileB = B->File->getObj();
+  if (RA->sh_type == SHT_RELA) {
+    if (!variableEq(A, B, FileA.relas(RA), FileB.relas(RB)))
+      return false;
+  } else {
+    if (!variableEq(A, B, FileA.rels(RA), FileB.rels(RB)))
+      return false;
+  }
+  return true;
+}
+
+// The main function of ICF.
+template <class ELFT> void ICF<ELFT>::run(SymbolTable<ELFT> *Symtab) {
+  // Initially, we use hash values as section group IDs. Therefore,
+  // if two sections have the same ID, they are likely (but not
+  // guaranteed) to have the same static contents in terms of ICF.
+  std::vector<InputSection<ELFT> *> V = getSections(Symtab);
+  for (InputSection<ELFT> *S : V)
+    // Set MSB on to avoid collisions with serial group IDs
+    S->GroupId = getHash(S) | (uint64_t(1) << 63);
+
+  // From now on, sections in Chunks are ordered so that sections in
+  // the same group are consecutive in the vector.
+  std::sort(V.begin(), V.end(),
+            [](InputSection<ELFT> *A, InputSection<ELFT> *B) {
+              return A->GroupId < B->GroupId;
+            });
+
+  // Compare static contents and assign unique IDs for each static content.
+  forEachGroup(V, equalsConstant);
+
+  // Split groups by comparing relocations until we get a convergence.
+  int Cnt = 1;
+  while (forEachGroup(V, equalsVariable))
+    ++Cnt;
+  if (Config->Verbose)
+    llvm::outs() << "ICF needed " << Cnt << " iterations.\n";
+
+  // Merge sections in the same group.
+  for (auto I = V.begin(), E = V.end(); I != E;) {
+    InputSection<ELFT> *Head = *I++;
+    auto Bound = std::find_if(I, E, [&](InputSection<ELFT> *S) {
+      return Head->GroupId != S->GroupId;
+    });
+    if (I == Bound)
+      continue;
+    if (Config->Verbose)
+      llvm::outs() << "Selected " << Head->getSectionName() << "\n";
+    while (I != Bound) {
+      InputSection<ELFT> *S = *I++;
+      if (Config->Verbose)
+        llvm::outs() << "  Removed " << S->getSectionName() << "\n";
+      Head->replace(S);
+    }
+  }
+}
+
+// ICF entry point function.
+template <class ELFT> void elf2::doIcf(SymbolTable<ELFT> *Symtab) {
+  ICF<ELFT>().run(Symtab);
+}
+
+template void elf2::doIcf(SymbolTable<ELF32LE> *);
+template void elf2::doIcf(SymbolTable<ELF32BE> *);
+template void elf2::doIcf(SymbolTable<ELF64LE> *);
+template void elf2::doIcf(SymbolTable<ELF64BE> *);

ELF/InputFiles.cpp

 template <class ELFT>
 InputSectionBase<ELFT> *
 elf2::ObjectFile<ELFT>::getSection(const Elf_Sym &Sym) const {
   uint32_t Index = this->getSectionIndex(Sym);
   if (Index == 0)
     return nullptr;
   if (Index >= Sections.size() || !Sections[Index])
     fatal("Invalid section index");
-  return Sections[Index];
+  return Sections[Index]->Repl;
 }
 
 template <class ELFT>
 SymbolBody *elf2::ObjectFile<ELFT>::createSymbolBody(const Elf_Sym *Sym) {
   ErrorOr<StringRef> NameOrErr = Sym->getName(this->StringTable);
   fatal(NameOrErr);
   StringRef Name = *NameOrErr;
 

ELF/InputSection.h

 
 #include "Config.h"
 #include "lld/Core/LLVM.h"
 #include "llvm/Object/ELF.h"
 
 namespace lld {
 namespace elf2 {
 
+template <class ELFT> class ICF;
 template <class ELFT> class ObjectFile;
 template <class ELFT> class OutputSection;
 template <class ELFT> class OutputSectionBase;
 
 // This corresponds to a section of an input file.
 template <class ELFT> class InputSectionBase {
 protected:
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Rel Elf_Rel;
public:
   enum Kind { Regular, EHFrame, Merge, MipsReginfo };
   Kind SectionKind;
 
   InputSectionBase(ObjectFile<ELFT> *File, const Elf_Shdr *Header,
                    Kind SectionKind);
   OutputSectionBase<ELFT> *OutSec = nullptr;
 
   // Used for garbage collection.
-  // Live bit makes sense only when Config->GcSections is true.
-  bool isLive() const { return !Config->GcSections || Live; }
-  bool Live = false;
+  bool Live;
+
+  // This pointer points to the "real" instance of this instnace.
+  // Usually Repl == this. However, if ICF merges two sections,
+  // Repl pointer of one section points to another section. So,
+  // if you need to get a pointer to this instnace, do not use
+  // this but instead this->Repl.
+  InputSectionBase<ELFT> *Repl;
 
   // Returns the size of this section (even if this is a common or BSS.)
   size_t getSize() const { return Header->sh_size; }
 
   static InputSectionBase<ELFT> Discarded;
 
   StringRef getSectionName() const;
   const Elf_Shdr *getSectionHdr() const { return Header; }
   ObjectFile<ELFT> *getFile() const { return File; }
 
   // The writer sets and uses the addresses.
-  uintX_t getAlign() {
+  uintX_t getAlign() const {
     // The ELF spec states that a value of 0 means the section has no alignment
     // constraits.
     return std::max<uintX_t>(Header->sh_addralign, 1);
   }
 
   uintX_t getOffset(const Elf_Sym &Sym);
 
   // Translate an offset in the input section to an offset in the output
   // section.
   uintX_t getOffset(uintX_t Offset);
 
   ArrayRef<uint8_t> getSectionData() const;
 
   // Returns a section that Rel is pointing to. Used by the garbage collector.
-  InputSectionBase<ELFT> *getRelocTarget(const Elf_Rel &Rel);
-  InputSectionBase<ELFT> *getRelocTarget(const Elf_Rela &Rel);
+  InputSectionBase<ELFT> *getRelocTarget(const Elf_Rel &Rel) const;
+  InputSectionBase<ELFT> *getRelocTarget(const Elf_Rela &Rel) const;
 
   template <bool isRela>
   using RelIteratorRange =
       llvm::iterator_range<const llvm::object::Elf_Rel_Impl<ELFT, isRela> *>;
 
   template <bool isRela>
   void relocate(uint8_t *Buf, uint8_t *BufEnd, RelIteratorRange<isRela> Rels);
 
public:
   uintX_t getOffset(uintX_t Offset);
 
   // Relocation section that refer to this one.
   const Elf_Shdr *RelocSection = nullptr;
 };
 
 // This corresponds to a non SHF_MERGE section of an input file.
 template <class ELFT> class InputSection : public InputSectionBase<ELFT> {
+  friend ICF<ELFT>;
   typedef InputSectionBase<ELFT> Base;
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Shdr Elf_Shdr;
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Rela Elf_Rela;
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Rel Elf_Rel;
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Sym Elf_Sym;
   typedef typename llvm::object::ELFFile<ELFT>::uintX_t uintX_t;
 
 public:
   InputSection(ObjectFile<ELFT> *F, const Elf_Shdr *Header);
 
   // Write this section to a mmap'ed file, assuming Buf is pointing to
   // beginning of the output section.
   void writeTo(uint8_t *Buf);
 
   // Relocation sections that refer to this one.
   SmallVector<const Elf_Shdr *, 1> RelocSections;
 
   // The offset from beginning of the output sections this section was assigned
   // to. The writer sets a value.
   uint64_t OutSecOff = 0;
 
   static bool classof(const InputSectionBase<ELFT> *S);
+
+  // Called by ICF to merge two input sections.
+  void replace(InputSection<ELFT> *Other);
+
+  // Used by ICF.
+  uint64_t GroupId = 0;
 };
 
 // MIPS .reginfo section provides information on the registers used by the code
 // in the object file. Linker should collect this information and write a single
 // .reginfo section in the output file. The output section contains a union of
 // used registers masks taken from input .reginfo sections and final value
 // of the `_gp` symbol.  For details: Chapter 4 / "Register Information" at
 // ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf

ELF/InputSection.cpp

 
 using namespace lld;
 using namespace lld::elf2;
 
 template <class ELFT>
 InputSectionBase<ELFT>::InputSectionBase(ObjectFile<ELFT> *File,
                                          const Elf_Shdr *Header,
                                          Kind SectionKind)
-    : Header(Header), File(File), SectionKind(SectionKind) {}
+    : Header(Header), File(File), SectionKind(SectionKind), Repl(this) {
+  // The garbage collector sets sections' Live bits.
+  // If GC is disabled, all sections are considered live by default.
+  Live = Config && !Config->GcSections;
+}
 
 template <class ELFT> StringRef InputSectionBase<ELFT>::getSectionName() const {
   ErrorOr<StringRef> Name = File->getObj().getSectionName(this->Header);
   fatal(Name);
   return *Name;
 }
 
 template <class ELFT>

 typename ELFFile<ELFT>::uintX_t
 InputSectionBase<ELFT>::getOffset(const Elf_Sym &Sym) {
   return getOffset(Sym.st_value);
 }
 
 // Returns a section that Rel relocation is pointing to.
 template <class ELFT>
 InputSectionBase<ELFT> *
-InputSectionBase<ELFT>::getRelocTarget(const Elf_Rel &Rel) {
+InputSectionBase<ELFT>::getRelocTarget(const Elf_Rel &Rel) const {
   // Global symbol
   uint32_t SymIndex = Rel.getSymbol(Config->Mips64EL);
   if (SymbolBody *B = File->getSymbolBody(SymIndex))
     if (auto *D = dyn_cast<DefinedRegular<ELFT>>(B->repl()))
-      return D->Section;
+      return D->Section->Repl;
   // Local symbol
   if (const Elf_Sym *Sym = File->getLocalSymbol(SymIndex))
     if (InputSectionBase<ELFT> *Sec = File->getSection(*Sym))
       return Sec;
   return nullptr;
 }
 
 template <class ELFT>
 InputSectionBase<ELFT> *
-InputSectionBase<ELFT>::getRelocTarget(const Elf_Rela &Rel) {
+InputSectionBase<ELFT>::getRelocTarget(const Elf_Rela &Rel) const {
   return getRelocTarget(reinterpret_cast<const Elf_Rel &>(Rel));
 }
 
 template <class ELFT>
 InputSection<ELFT>::InputSection(ObjectFile<ELFT> *F, const Elf_Shdr *Header)
     : InputSectionBase<ELFT>(F, Header, Base::Regular) {}
 
 template <class ELFT>
for (const Elf_Shdr *RelSec : this->RelocSections) {
     if (RelSec->sh_type == SHT_RELA)
       this->relocate(Buf, BufEnd, EObj.relas(RelSec));
     else
       this->relocate(Buf, BufEnd, EObj.rels(RelSec));
   }
 }
 
 template <class ELFT>
+void InputSection<ELFT>::replace(InputSection<ELFT> *Other) {
+  Other->Repl = this->Repl;
+  Other->Live = false;
+}
+
+template <class ELFT>
 SplitInputSection<ELFT>::SplitInputSection(
     ObjectFile<ELFT> *File, const Elf_Shdr *Header,
     typename InputSectionBase<ELFT>::Kind SectionKind)
     : InputSectionBase<ELFT>(File, Header, SectionKind) {}
 
 template <class ELFT>
 EHInputSection<ELFT>::EHInputSection(ObjectFile<ELFT> *F,
                                      const Elf_Shdr *Header)

ELF/Options.td

def export_dynamic : Flag<["--", "-"], "export-dynamic">,
   HelpText<"Put symbols in the dynamic symbol table">;
 
 def fini : Separate<["-"], "fini">, MetaVarName<"<symbol>">,
   HelpText<"Specify a finalizer function">;
 
 def hash_style : Separate<["--", "-"], "hash-style">,
   HelpText<"Specify hash style (sysv, gnu or both)">;
 
+def icf : Flag<["--"], "icf=all">,
+  HelpText<"Enable Identical Comdat Folding.">;
+
 def gc_sections : Flag<["--"], "gc-sections">,
   HelpText<"Enable garbage collection of unused sections">;
 
 def init : Separate<["-"], "init">, MetaVarName<"<symbol>">,
   HelpText<"Specify an initializer function">;
 
 def l : JoinedOrSeparate<["-"], "l">, MetaVarName<"<libName>">,
   HelpText<"Root name of library to use">;

ELF/OutputSections.cpp

 
 template <class ELFT>
 OutputSection<ELFT>::OutputSection(StringRef Name, uint32_t Type,
                                    uintX_t Flags)
     : OutputSectionBase<ELFT>(Name, Type, Flags) {}
 
 template <class ELFT>
 void OutputSection<ELFT>::addSection(InputSectionBase<ELFT> *C) {
+  assert(C->Live);
   auto *S = cast<InputSection<ELFT>>(C);
   Sections.push_back(S);
   S->OutSec = this;
   uint32_t Align = S->getAlign();
   this->updateAlign(Align);
 
   uintX_t Off = this->Header.sh_size;
   Off = alignTo(Off, Align);
elf2::getLocalRelTarget(const ObjectFile<ELFT> &File,
   if (Sym->getType() == STT_TLS)
     return (Section->OutSec->getVA() + Section->getOffset(*Sym) + Addend) -
            Out<ELFT>::TlsPhdr->p_vaddr;
 
   // According to the ELF spec reference to a local symbol from outside
   // the group are not allowed. Unfortunately .eh_frame breaks that rule
   // and must be treated specially. For now we just replace the symbol with
   // 0.
-  if (Section == &InputSection<ELFT>::Discarded || !Section->isLive())
+  if (Section == &InputSection<ELFT>::Discarded || !Section->Live)
     return Addend;
 
   uintX_t Offset = Sym->st_value;
   if (Sym->getType() == STT_SECTION) {
     Offset += Addend;
     Addend = 0;
   }
   return Section->OutSec->getVA() + Section->getOffset(Offset) + Addend;
if (ID == 0) {
         Cies.push_back(C);
         this->Header.sh_size += alignTo(Length, sizeof(uintX_t));
       }
       OffsetToIndex[Offset] = P.first->second;
     } else {
       if (!HasReloc)
         fatal("FDE doesn't reference another section");
       InputSectionBase<ELFT> *Target = S->getRelocTarget(*RelI);
-      if (Target != &InputSection<ELFT>::Discarded && Target->isLive()) {
+      if (Target != &InputSection<ELFT>::Discarded && Target->Live) {
         uint32_t CieOffset = Offset + 4 - ID;
         auto I = OffsetToIndex.find(CieOffset);
         if (I == OffsetToIndex.end())
           fatal("Invalid CIE reference");
         Cies[I->second].Fdes.push_back(EHRegion<ELFT>(S, Index));
         Out<ELFT>::EhFrameHdr->reserveFde();
         this->Header.sh_size += alignTo(Length, sizeof(uintX_t));
       }

ELF/Symbols.h

 // Regular defined symbols read from object file symbol tables.
 template <class ELFT> class DefinedRegular : public DefinedElf<ELFT> {
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Sym Elf_Sym;
 
 public:
   DefinedRegular(StringRef N, const Elf_Sym &Sym,
                  InputSectionBase<ELFT> *Section)
       : DefinedElf<ELFT>(SymbolBody::DefinedRegularKind, N, Sym),
-        Section(Section) {}
+        Section(Section ? Section->Repl : NullInputSection) {}
 
   static bool classof(const SymbolBody *S) {
     return S->kind() == SymbolBody::DefinedRegularKind;
   }
 
-  // If this is null, the symbol is absolute.
-  InputSectionBase<ELFT> *Section;
+  // The input section this symbol belongs to. Notice that this is
+  // a reference to a pointer. We are using two levels of indirections
+  // because of ICF. If ICF decides two sections need to be merged, it
+  // manipulates this Section pointers so that they point to the same
+  // section. This is a bit tricky, so be careful to not be confused.
+  // If this is null, the symbol is an absolute symbol.
+  InputSectionBase<ELFT> *&Section;
+
+private:
+  static InputSectionBase<ELFT> *NullInputSection;
 };
 
+template <class ELFT>
+InputSectionBase<ELFT> *DefinedRegular<ELFT>::NullInputSection;
+
 // DefinedSynthetic is a class to represent linker-generated ELF symbols.
 // The difference from the regular symbol is that DefinedSynthetic symbols
 // don't belong to any input files or sections. Thus, its constructor
 // takes an output section to calculate output VA, etc.
 template <class ELFT> class DefinedSynthetic : public Defined {
 public:
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Sym Elf_Sym;
   typedef typename llvm::object::ELFFile<ELFT>::uintX_t uintX_t;

ELF/Symbols.cpp

typename ELFFile<ELFT>::uintX_t SymbolBody::getVA() const {
   }
   case DefinedRegularKind: {
     auto *D = cast<DefinedRegular<ELFT>>(this);
     InputSectionBase<ELFT> *SC = D->Section;
 
     // This is an absolute symbol.
     if (!SC)
       return D->Sym.st_value;
+    assert(SC->Live);
 
     // Symbol offsets for AMDGPU need to be the offset in bytes of the symbol
     // from the beginning of the section.
     if (Config->EMachine == EM_AMDGPU)
       return SC->getOffset(D->Sym);
     if (D->Sym.getType() == STT_TLS)
       return SC->OutSec->getVA() + SC->getOffset(D->Sym) -
              Out<ELFT>::TlsPhdr->p_vaddr;

ELF/Writer.cpp

for (const std::unique_ptr<ObjectFile<ELFT>> &F : Symtab.getObjectFiles()) {
     for (const Elf_Sym &Sym : F->getLocalSymbols()) {
       ErrorOr<StringRef> SymNameOrErr = Sym.getName(F->getStringTable());
       fatal(SymNameOrErr);
       StringRef SymName = *SymNameOrErr;
       if (!shouldKeepInSymtab<ELFT>(*F, SymName, Sym))
         continue;
       if (Sym.st_shndx != SHN_ABS) {
         InputSectionBase<ELFT> *Section = F->getSection(Sym);
-        if (!Section->isLive())
+        if (!Section->Live)
           continue;
       }
       ++Out<ELFT>::SymTab->NumLocals;
       F->KeptLocalSyms.push_back(std::make_pair(
           &Sym, Out<ELFT>::SymTab->StrTabSec.addString(SymName)));
     }
   }
 }
for (StringRef V : {".text.", ".rodata.", ".data.rel.ro.", ".data.", ".bss.",
     if (Name.startswith(V))
       return V.drop_back();
   return Name;
 }
 
 template <class ELFT>
 void reportDiscarded(InputSectionBase<ELFT> *IS,
                      const std::unique_ptr<ObjectFile<ELFT>> &File) {
-  if (!Config->PrintGcSections || !IS || IS->isLive())
+  if (!Config->PrintGcSections || !IS || IS->Live)
     return;
   llvm::errs() << "removing unused section from '" << IS->getSectionName()
                << "' in file '" << File->getName() << "'\n";
 }
 
 template <class ELFT>
 bool Writer<ELFT>::isDiscarded(InputSectionBase<ELFT> *S) const {
-  return !S || !S->isLive() || S == &InputSection<ELFT>::Discarded ||
+  return !S || !S->Live || S == &InputSection<ELFT>::Discarded ||
          Script->isDiscarded(S);
 }
 
 // The beginning and the ending of .rel[a].plt section are marked
 // with __rel[a]_iplt_{start,end} symbols if it is a statically linked
 // executable. The runtime needs these symbols in order to resolve
 // all IRELATIVE relocs on startup. For dynamic executables, we don't
 // need these symbols, since IRELATIVE relocs are resolved through GOT
template <class ELFT> static bool includeInSymtab(const SymbolBody &B) {
   if (!B.isUsedInRegularObj())
     return false;
 
   if (auto *D = dyn_cast<DefinedRegular<ELFT>>(&B)) {
     // Don't include synthetic symbols like __init_array_start in every output.
     if (&D->Sym == &ElfSym<ELFT>::Ignored)
       return false;
     // Exclude symbols pointing to garbage-collected sections.
-    if (D->Section && !D->Section->isLive())
+    if (D->Section && !D->Section->Live)
       return false;
   }
   return true;
 }
 
 static bool includeInDynsym(const SymbolBody &B) {
   uint8_t V = B.getVisibility();
   if (V != STV_DEFAULT && V != STV_PROTECTED)

test/ELF/Inputs/icf2.s

+.globl f1, f2
+.section .text.f2, "ax"
+f2:
+  mov $60, %rdi
+  call f1

test/ELF/icf1.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+# RUN: ld.lld %t -o %t2 --icf=all --verbose | FileCheck %s
+
+# CHECK: Selected .text.f1
+# CHECK:   Removed .text.f2
+
+.globl _start, f1, f2
+_start:
+  ret
+
+.section .text.f1, "ax"
+f1:
+  mov $60, %rax
+  mov $42, %rdi
+  syscall
+
+.section .text.f2, "ax"
+f2:
+  mov $60, %rax
+  mov $42, %rdi
+  syscall

test/ELF/icf2.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t1
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %p/Inputs/icf2.s -o %t2
+# RUN: ld.lld %t1 %t2 -o %t --icf=all --verbose | FileCheck %s
+
+# CHECK: Selected .text.f1
+# CHECK:   Removed .text.f2
+
+.globl _start, f1, f2
+_start:
+  ret
+
+.section .text.f1, "ax"
+f1:
+  mov $60, %rdi
+  call f2

test/ELF/icf3.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t1
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %p/Inputs/icf2.s -o %t2
+# RUN: ld.lld %t1 %t2 -o %t --icf=all --verbose | FileCheck %s
+
+# CHECK-NOT: Selected .text.f1
+# CHECK-NOT: Selected .text.f2
+
+.globl _start, f1, f2
+_start:
+  ret
+
+# This section is not mergeable because the content is different from f2.
+.section .text.f1, "ax"
+f1:
+  mov $60, %rdi
+  call f2
+  mov $0, %rax

test/ELF/icf4.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+# RUN: ld.lld %t -o %t --icf=all --verbose | FileCheck %s
+
+# CHECK-NOT: Selected .text.f1
+# CHECK-NOT: Selected .text.f2
+
+.globl _start, f1, f2
+_start:
+  ret
+
+.section .text.f1, "ax"
+f1:
+  mov $1, %rax
+
+.section .text.f2, "ax"
+f2:
+  mov $0, %rax

test/ELF/icf5.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+# RUN: ld.lld %t -o %t --icf=all --verbose | FileCheck %s
+
+# CHECK-NOT: Selected .text.f1
+# CHECK-NOT: Selected .text.f2
+
+.globl _start, f1, f2
+_start:
+  ret
+
+.section .text.f1, "ax"
+f1:
+  mov $0, %rax
+
+.section .text.f2, "awx"
+f2:
+  mov $0, %rax