Changes

Add BOLT builder and worker configurations

Differential revision: https://reviews.llvm.org/D116062

Fix crash in patchELFPHDRTable when no functions are modified.

Summary:
patchELFPHDRTable was asserting that it could not find an entry
for .eh_frame_hdr in SectionMapInfo when no functions were modified
by BOLT.

This just changes code to skip modifying GNU_EH_FRAME program headers
hen SectionMapInfo is empty.  The existing header is copied and written
instead.

(cherry picked from FBD3557481)

Shorten instructions if possible.

Summary:
Generate short versions of branch instructions by default and rely on
relaxation to produce longer versions when needed.

Also produce short versions of arithmetic instructions if immediate
fits into one byte. This was only triggered once on HHVM binary.

(cherry picked from FBD3591466)

Move debug-handling code into DWARFRewriter (NFC).

Summary: RewriteInstance.cpp is getting too big. Split the code.

(cherry picked from FBD3596103)

Add BinaryContext::getSectionForAddress()

Summary: Interface for accessing section from BinaryContext.

(cherry picked from FBD3600854)

Add movabs -> mov shortening optimization.  Add peephole optimization pass that does instruction shortening.

Summary:
Shorten when a mov instruction has a 64-bit immediate that can be repesented as
a sign extended 32-bit number, use the smaller mov instruction (MOV64ri -> MOV64ri32).

Add peephole optimization pass that does instruction shortening.

(cherry picked from FBD3603099)

Loop detection for BOLT's CFG.

Summary:
Loop detection for the CFG data structure. Added a GraphTraits
specialization for BOLT's CFG that allows us to use LLVM's loop
detection interface.

(cherry picked from FBD3604837)

Simplification of loads from read-only data sections.

Summary:
Instructions that load data from the a read-only data section and their
target address can be computed statically (e.g. RIP-relative addressing)
are modified to corresponding instructions that use immediate operands.
We apply the transformation only when the resulting instruction will have
smaller or equal size.

(cherry picked from FBD3397112)

Factor out instruction printing and size computation.

Summary:
I've factored out the instruction printing and size computation routines to
methods on BinaryContext.  I've also added some more debug print functions.

This was split off the ICP diff to simplify it a bit.

(cherry picked from FBD3610690)

Identical Code Folding (ICF) pass

Summary:
Added an ICF pass to BOLT, that can recognize identical functions
and replace references to these functions with references to just one
representative.

(cherry picked from FBD3460297)

Basic block clustering algorithm for minimizing branches.

Summary:
This algorithm is similar to our main clustering algorithm but uses
a different heuristic for selecting edges to become fall-throughs.
The weight of an edge is calculated as the win in branches if we choose
to layout this edge as a fall-through. For example, the edges A -> B with
execution count 100 and A -> C with execution count 500 (where B and C
are the only successors of A) have weights -400 and +400 respectively.

(cherry picked from FBD3606591)

CFG editing functions

Summary:
This diff adds a number of methods to BinaryFunction that can be used to edit the CFG after it is created.

The basic public functions are:
  - createBasicBlock - create a new block that is not inserted into the CFG.
  - insertBasicBlocks - insert a range of blocks (made with createBasicBlock) into the CFG.
  - updateLayout - update the CFG layout (either by inserting new blocks at a certain point or recomputing the entire layout).
  - fixFallthroughBranch - add a direct jump to the fallthrough successor for a given block.

There are a number of private helper functions used to implement the above.

This was split off the ICP diff to simplify it a bit.

(cherry picked from FBD3611313)

Add printing support for indirect tail calls.

Summary:
LLVM was missing assembler print string for indirect tail
calls which are synthetic instructions created by us.

(cherry picked from FBD3640197)

Fix for correct disassembling of conditional tail calls.

Summary:
BOLT attempts to convert jumps that serve as tail calls to dedicated tail call
instructions, but this is impossible when the jump is conditional because there is
no corresponding tail call instruction. This was causing the creation of a duplicate
fall-through edge for basic blocks terminated with a conditional jump serving as
a tail call when there is profile data available for the non-taken branch. In this
case, the first fall-through edge had a count taken from the profile data, while
the second has a count computed (incorrectly) by
BinaryFunction::inferFallThroughCounts.

(cherry picked from FBD3560504)

Add MCInst annotation mechanism to MCInstrAnalysis class.

Summary:
Add three new MCOperand types: Annotation, LandingPad and GnuArgsSize.

Annotation is used for associating random data with MCInsts.  Clients can
construct their own annotation types (subclassed from MCAnnotation) and
associate them with instructions.  Annotations are looked up by string keys.

Annotations can be added, removed and queried using an instance of the
MCInstrAnalysis class.

The LandingPad operand is a MCSymbol, uint64_t pair used to encode exception
handling information for call instructions.

GnuArgsSize is used to annotate calls with the DW_CFA_GNU_args_size attribute.

(cherry picked from FBD3597877)

More aggressive inlining pass

Summary:
This adds functionality for a more aggressive inlining pass, that can
inline tail calls and functions with more than one basic block.

(cherry picked from FBD3677856)

Refactoring. Mainly NFC.

Summary:
Eliminated BinaryFunction::getName(). The function was confusing since
the name is ambigous. Instead we have BinaryFunction::getPrintName()
used for printing and whenever unique string identifier is needed
one can use getSymbol()->getName(). In the next diff I'll have
a map from MCSymbol to BinaryFunction in BinaryContext to facilitate
function lookup from instruction operand expressions.

There's one bug fixed where the function was called only under assert()
in ICF::foldFunction().

For output we update all symbols associated with the function. At the
moment it has no effect on the generated binary but in the future we
would like to have all symbols in the symbol table updated.

(cherry picked from FBD3704790)

More refactoring work.

Summary:
Avoid referring to BinaryFunction's by name.

Functions could be found by MCSymbol using
BinaryContext::getFunctionForSymbol().

(cherry picked from FBD3707685)

Add additional info to BOLT graphviz CFG dumps.

Summary:
Add the following info the graphviz CFG dump:
- Edges are labeled with the jmp instruction that leads to that edge.
- Edges include the count and misprediction count.
- Nodes have (offset, BB index, BB layout index)
- Nodes optionally have tooltips which contain the code of the basic block.
  (enabled with -dot-tooltip-code)
- Added dashed edges to landing pads.

(cherry picked from FBD3646568)

Check if operands are immediates before trying shortening.

Summary:
Operands in the initial instruction stream should all have immediate operands
for instructions that can be shortened.  But if a BOLT optimization pass adds
one of these instructions with a symbolic operand, the shortening operation
will assert.  This diff adds checks to make sure that the operands are
immediate.

I've also disabled shortening pass by default since it won't really be needed
until ICP is submitted.  It will still run at CFG creation time.

(cherry picked from FBD3610646)

Compute ClusterEdges only when necessary.

Summary:
We only need ClusterEdges in reordering algorithm optimized for
branches and the computation is quite resource-hungry, thus it
makes sense to only do it when needed.

Some refactoring too.

(cherry picked from FBD3721107)

Write padding for .eh_frame_hdr to a file.

Summary:
We were applying padding to the calculated address but were never
writing it to a file triggering an assertion for cases when
.gcc_except_table size wasn't multiple of 4.

(cherry picked from FBD3744638)

Handling for indirect tail calls.

Summary:
Analyze indirect branches and convert them into indirect
tail calls when possible. We analyze the memory contents
when the address could be calculated statically and also
detect epilogue code.

(cherry picked from FBD3754395)

Emit remember_state CFI in the same code region as restore_state.

Summary:
While creating remember_state/restore_state CFI sequences, we
were always placing remember_state instruction into the first
basic block. However, when we have hot-cold splitting, the cold
part has and independent FDE entry in .eh_frame, and thus the
restore_state instruction was missing its counter part.

The fix is to adjust the basic block that is used for placing
remember_state instruction whenever we see the hot-cold split
boundary.

(cherry picked from FBD3767102)

Add verbosity level and clean up stream usage.

Summary:
I've added a verbosity level to help keep the BOLT spewage to a minimum.
The default level is pretty terse now, level 1 is closer to the original,
I've saved level 2 for the noisiest of messages.  Error messages should
never be suppressed by the verbosity level only warnings and info messages.

The rational behind stream usage is as follows:
outs() for info and debugging controlled by command line flags.
errs() for errors and warnings.
dbgs() for output within DEBUG().

With the exception of a few of the level 2 messages I don't have any strong feelings about the others.

(cherry picked from FBD3814259)

Fix tail call conversion and test cases.

Summary:
A previous diff accidentally disabled tail call conversion.

Additionally some test cases relied on output of "-v=2". Fix those.

(cherry picked from FBD3823760)

Inlining fixes/enhancements

Summary:
A number of fixes/enhancements to inline-small-functions
- Fixed size estimateHotSize to use computeCodeSize instead of the original layout offsets.
- Added -print-inline option to dump CFGs for functions that have been modified by inlining.
- Added flag to force consideration of functions without any profiling info (mostly for testing)
- Updated debug line info for inlined functions.
- Ignore the number of pseudo instructions when checking for candidates of suitable size.

Misc changes
- Moved most print flags to BinaryPasses.cpp

(cherry picked from FBD3812658)

BOLT: Make most command line options ZeroOrMore.

Summary:
This will make it easier to run experiments with the same baseline
BOLT binary but different command line options.

(cherry picked from FBD3831978)

Make BinaryFunction::fixBranches() more flexible and support CFG updates.

Summary:
The CFG represents "the ultimate source of truth". Transformations
on functions and blocks have to update the CFG and fixBranches() would
make sure the correct branch instructions are inserted at the end of
basic blocks (or removed when necessary).

We do require a conditional branch at the end of the basic block if
the block has 2 successors as CFG currently lacks the conditional
code support (it will probably stay that way). We only use this
branch instruction for its conditional code, the destination is
determined by CFG - first successor representing true/taken branch,
while the second successor - false/fall-through branch.

When we reverse the branch condition, the CFG is updated accordingly.

The previous version used to insert jumps after some terminating
instructions sometimes resulting in a larger code than needed. As a
result with the new version 1 extra function becomes overwritten for
HHVM binary.

With this diff we also convert conditional branches with one successor
(result of code from __builtin_unreachable()) into unconditional
jumps.

(cherry picked from FBD3802062)

Add dyno stats to BOLT.

Summary:
Add "-dyno-stats" option that prints instruction stats based on
the execution profile similar to below:

BOLT-INFO: program-wide dynostats after optimizations:
  executed forward branches : 109706407 (+8.1%)
  taken forward branches : 13769074 (-55.5%)
  executed backward branches : 24517582 (-25.0%)
  taken backward branches : 15330256 (-27.2%)
  executed unconditional branches : 6009826 (-35.5%)
  function calls : 17192114 (+0.0%)
  executed instructions : 837733057 (-0.4%)
  total branches : 140233815 (-2.3%)
  taken branches : 35109156 (-42.8%)

Also fixed pseudo instruction discrepancies and added assertions
for BinaryBasicBlock::getNumPseudos() to make sure the number is
synchronized with real number of pseudo instructions.

(cherry picked from FBD3826995)

Rewrite SCTC pass to do UCE and make it the last optimization pass.

Summary:
For now we make SCTC a special pass that runs at the end of all
optimizations and transformations right after fixupBranches().

Since it's the last pass, it has to do its own UCE.

(cherry picked from FBD3838051)

BOLT: Add per pass dyno stats + factor out post pass printing.

Summary:
I've added dyno stats printing per pass so we can see the results
of each optimization pass on the stats.  I've also factored out the
post pass function printing code since it was pretty much the same
after each pass.

(cherry picked from FBD3843587)

Use BB.getNumNonPseudos() in more places.

Summary:
Use BB.getNumNonPseudos() in more places.

Fix analyze_potential script to pass the new parameter.

(cherry picked from FBD3844416)

BOLT: Remove double jumps peephole.

Summary:
Replace jumps to other unconditional jumps with the final
destination, e.g.

  B0: ...
      jmp B1  (or jcc B1)

  B1: jmp B2

  ->

  B0: ...
      jmp B2  (or jcc B1)

This peephole removes 8928 double jumps from a test binary.

Note: after filtering out double jumps found in EH code and infinite
loops, the number of double jumps patched is 49 (24 for a clang
compiled test).  The 24 in the clang build are all from external
libraries which have probably been compiled with gcc.  This peephole
is still useful for cleaning up after ICP though.

(cherry picked from FBD3815420)

Fix switch table detection. Disassemble all instructions in non-simple functions.

Summary:
Switch table can contain __builtin_unreachable(). As a result,
a compiler may place an entry into a jump table that contains
an address immediately past the last instruction in the function.
Sometimes it may coincide with a start of the next function in
the binary. Thus when we check for switch tables in such cases
we have to check more than a single entry until we see either
an address inside containing function or some address outside
different from the address past the last instruction.

Additonally, don't stop disassembly after discovering that the
function was not simple. We need to detect all outside
references whenever possible.

(cherry picked from FBD3850825)

Add cluster randomization layout algorithm.

Summary:
Add "-reorder-blocks=cluster-shuffle" for performance experiments.
Use "-bolt-seed=<N>" to set a randomization seed.

(cherry picked from FBD3851035)

BOLT: Clean up interface between BinaryFunction and BinaryBasicBlock.

Summary:
This is just a bit of refactoring to make sure that BinaryFunction goes
through methods to get at the state in BinaryBasicBlock.  I did this so
that changing the way Index/LayoutIndex/Valid works will be easier.

(cherry picked from FBD3860899)

Add experimental jump table support.

Summary:
Option "-jump-tables=1" enables experimental support for jump tables.

The option hasn't been tested with optimizations other than block
re-ordering.

Only non-PIC jump tables are supported at the moment.

(cherry picked from FBD3867849)

Add dyno stats for jump tables.

Summary: Add dyno stats for jump tables.

(cherry picked from FBD3871035)

Fix issue with zero-size duplicate function symbols.

Summary:
While working on PLT dyno stats I've noticed that we were missing
BinaryFunctions for some symbols that were not PLT. Upon closer inspection
turned out that those symbols were marked as zero-sized functions in
symbol table, but they had duplicates with non-zero size. Since the
zero-size symbols were preceding other duplicates, we were not creating
BinaryFunction for them and they were not added as duplicates.

The 2 most prominent functions that were missing for a test were free() and
malloc().  There's not much to optimize in these functions, but they were
contributing quite significantly to dyno stats.

As a result dyno stats for this test needed an adjustment.

Also several assembly functions (e.g. _init()) had zero size, and now we
set the size to the max size and start processing those. It's good for
coverage but will not affect the performance.

(cherry picked from FBD3874622)

Add PLT dyno stats.

Summary: Get PLT call stats.

(cherry picked from FBD3874799)

Do no collect dyno stats on functions with stale profile.

Summary:
Dyno stats collected on functions with invalid profile may appear
completely bogus. Skip them.

(cherry picked from FBD3879371)

BOLT: Add feature to sort functions by dyno stats.

Summary:
Add -print-sorted-by and -print-sorted-by-order command line options.
The first option takes a list of dyno stats keys used to sort functions
that are printed at the end of all optimization passes.  Only the top
100 functions are printed.  The -print-sorted-by-order option can be
either ascending or descending (descending is the default).

(cherry picked from FBD3898818)

BOLT: Refactoring BinaryFunction interface.

Summary:
Get rid of all uses of getIndex/getLayoutIndex/getOffset outside of BinaryFunction.
Also made some other offset related methods private.

(cherry picked from FBD3861968)

BOLT: Add ud2 after indirect tailcalls.

Summary:
Insert ud2 instructions after indirect tailcalls to prevent the CPU from
decoding instructions following the callsite.

A simple counter in the peephole pass shows 3260 tail call traps inserted.

(cherry picked from FBD3859737)

Support for splitting jump tables.

Summary:
Add level for "-jump-tables=<n>" option:
  1 - all jump tables are output in the same section (default).
  2 - basic splitting, if the table is used it is output to hot section
      otherwise to cold one.
  3 - aggressively split compound jump tables and collect profile for
      all entries.

Option "-print-jump-tables" outputs all jump tables for debugging
and/or analyzing purposes. Use with "-jump-tables=3" to get profile
values for every entry in a jump table.

(cherry picked from FBD3912119)

BOLT: Remove restrictions on unreachable code elimination

Summary:
Allow UCE when blocks have EH info.  Since UCE may remove blocks
that are referenced from debugging info data structures, we don't
actually delete them.  We just mark them with an "invalid" index
and store them in a different vector to be cleaned up later once
the BinaryFunction is destroyed.  The debugging code just skips
any BBs that have an invalid index.

Eliminating blocks may also expose useless jmp instructions, i.e.
a jmp around a dead block could just be a fallthrough.  I've added
a new routine to cleanup these jmps.  Although, @maks is working on
changing fixBranches() so that it can be used instead.

(cherry picked from FBD3793259)

Support for PIC-style jump tables.

Summary:
Added support for jump tables in code compiled with "-fpic".
Code pattern generated for position-independent jump tables
is quite different, as is the format of the tables.
More details in comments.

Coverage increased slightly for a test, mostly due to the code
coming from external lib that was compiled with "-fpic".

(cherry picked from FBD3940771)

New function discovery and support for multiple entries.

Summary:
Modified function discovery process to tolerate more functions and
symbols coming from assembly. The processing order now matches
the memory order of the functions (input symbol table is unsorted).

Added basic support for functions with multiple entries. When
a function references its internal address other than with
a branch instruction, that address could potentially escape.
We mark such addresses as entry points and make sure they
are treated as roots by unreachable code elimination.

Without relocations we have to mark multiple-entry functions
as non-simple.

(cherry picked from FBD3950243)

Fix EH for cold fragments that we fail to write.

Summary:
When we fail to write functions that are too big, we have to
effectively cancel their effect on exception handling by ignoring
their FDE entries in .eh_frame while writing .eh_frame_hdr.

This can happen to functions that we split too. In such cases
the cold part has its own FDE and we have to ignore that one too.
This doesn't happen very often - I've only seen one case on
hhvm binary, however it is a potential issue. The fix is to
add the cold part address to the list of failed-to-write
addresses.

(cherry picked from FBD3987984)

Disable processing of functions with EVEX-encoded instructions (AVX-512).

Summary:
AVX-512 disassembler support in LLVM is not quite ready yet.
Before we feel more comfortable about it we disable processing
of all functions that use any EVEX-encoded instructions.

(cherry picked from FBD4028706)

Support DWARF expressions in CFI instructions

Summary:
Modify the MC layer (MCDwarf.h|cpp) to understand CFI
instructions dealing with DWARF expressions. Add code to emit DWARF
expressions in MCDwarf. Change llvm-bolt to pass these CFI instructions
to streamer instead of bailing on them. Change -dump-eh-frame option in
llvm-bolt to dump the EH frame of the rewritten binary in addition to
the one in the original binary, allowing us to proper test this patch.

(cherry picked from FBD4194452)

Fix DW_CFA_def_cfa CFI duping in output binary

Summary:
CFI instructions may live in CIEs or FDEs. CIEs hold common
instructions used across many FDEs. When replaying CFIs to the output
binary, llvm-bolt needs to replay both instructions from CIE and the
corresponding FDE for the function. However, some instructions need not
to be replayed because MCStreamer/MCDwarf and friends will write them
by default in the output CIE. This patch fix the code that tried to
recognize one of these default instructions but was failing, resulting
in an extra CFI instruction in each FDE we outputted. With this patch,
the output binary should be a bit smaller.

(cherry picked from FBD4194753)

Another EH fix for cold fragments of functions that we fail to write.

Summary:
In a prev diff I disabled inclusion of FDEs for cold fragments that
we fail to write. The side effect of it was that we failed to
write FDE for the next function with a cold fragment since it
had the same assigned address that we had put in FailedAddresses.

The correct fix is to assign zero address to failed cold fragments
and ignore them when we write .eh_frame_hdr.

(cherry picked from FBD4156740)

Generate .eh_frame_hdr based on contents of .eh_frame's.

Summary:
We used to patch an existing .eh_frame_hdr and append contents
for split functions at the end. However, this approach does not
work in relocation mode since function addresses change and split
functions will not necessarily be at the end.

Instead of patching and appending we generate the new .eh_frame_hdr
based on contents of old and new .eh_frame sections.

(cherry picked from FBD4180756)

Relocate old .eh_frame section next to the new one.

Summary:
In order to improve gdb experience with BOLT we have to make
sure the output file has a single .eh_frame section. Otherwise
gdb will use either old or new section for unwinding purposes.

This diff relocates the original .eh_frame section next to
the new one generated by LLVM. Later we merge two sections
into one and make sure only the newly created section has
.eh_frame name.

(cherry picked from FBD4203943)

Detect default CFI frame instructions for the target

Summary:
Make BOLT resilient to changes in the LLVM's X86 target library
by not hardwiring the list of default CIE instructions, but detecting it
at run time.

(cherry picked from FBD4200982)

Add stats for "-optimize-bodyless-functions".

Summary: Print the number of calls eliminated.

(cherry picked from FBD4010698)

Fix clang warning about switch covering all enums

Summary:
This is part of a series of clean-up patches to make bolt
cleanly compile with clang 4.0. This patch fixes the following warning:
default label in switch which covers all enumeration values

(cherry picked from FBD4242168)

Remove pessimizing std::move

Summary:
This is part of a series of clean-up patches to make bolt
cleanly compile with clang 4.0. This patch fixes the following warning:
moving a temporary object prevents copy elision

(cherry picked from FBD4242236)

Avoid const_iterator on std::vector::emplace

Summary:
This is part of a series of clean-up patches to make bolt
cleanly compile with clang 4.0. This patch fixes an error where clang
will fail to compile because it does not support passing a
const_iterator to std::vector<T>::emplace(Iter, ...).

(cherry picked from FBD4242546)

Fix memory leak in DWARFRewriter

Summary:
Clang's Address Sanitizer caught this leak where MCAsmBackend
and MCObjectWriter instances were being created but not freed. Fix this.

(cherry picked from FBD4249941)

Fix undefined behavior in DebugInfo

Summary:
The CFI instructions parser in libDebugInfo was relying on
undefined behavior to parse operands by assuming the order function
parameters are evaluated in a function call site is defined (it is
not). This patch fix this and makes our clang and gcc tests agree.
It also fixes wrong LIT tests in our codebase with respect to the
order of DW_CFA_def_cfa operands.

(cherry picked from FBD4255227)

Remove unused private var in CFIReaderWriter (NFC)

Summary: This member variable is dead.

(cherry picked from FBD4255342)

Add option to time passes

Summary:
As we begin to work on optimization passes for bolt, it is important to
keep track of the time spent in each of these to measure their
contribution to the time bolt takes to finish rewriting a program.

(cherry picked from FBD4301136)

Fix typo in time passes

Summary:
Previously NamedRegionTimer's constructor was being called
with no local variable associated with it owing to a typo. We need a
local variable to keep track of the time spent in the scope. At the
end of the scope, the destructor will be called an then the timer will
stop.

(cherry picked from FBD4301844)

BOLT: Use profiling info to control branch simplification optimization.

Summary:
An optimization to simplify conditional tail calls by removing unnecessary branches.  It adds the following two command line options:

  -simplify-conditional-tail-calls  - simplify conditional tail calls by removing unnecessary jumps
  -sctc-mode                        - mode for simplify conditional tail calls
    =always                         -   always perform sctc
    =preserve                       -   only perform sctc when branch direction is preserved
    =heuristic                      -   use branch prediction data to control sctc

This optimization considers both of the following cases:

  foo: ...
       jcc L1   original
       ...
  L1:  jmp bar  # TAILJMP

->

  foo: ...
       jcc bar  iff jcc L1 is expected
       ...

  L1 is unreachable

OR

  foo: ...
       jcc  L2
  L1:  jmp  dest  # TAILJMP
  L2:  ...

->

  foo: jncc dest  # TAILJMP
  L2:  ...

  L1 is unreachable

For this particular case, the first basic block ends with a conditional branch and has two successors, one fall-through and one for when the condition is true.  The target of the conditional is a basic block with a single unconditional branch (i.e. tail call) to another function.  We don't care about the contents of the fall-through block.

(cherry picked from FBD3719617)

Add a frame optimization pass

Summary:
This is a first attempt to perform data flow analyses on bolt
and try to rebuild the stack frame for functions. The goal of the frame
optimization pass is to detect instructions that are accessing stack and,
if loading values, evaluate whether this load is redundant and we can
substitute the memory operation for a register load or immediate load.
To find opportunities, this pass also builds a map of clobbered registers
by function, so we use this in our analysis at call sites. If a call site
is found out to not clobber a caller-saved register but the caller is
spilling it anyway to the stack (to comply with the ABI), we should
detect these cases and remove this unnecessary move.

(cherry picked from FBD4337238)

Relocations support for BOLT.

Summary: Read relocation from linker and relocate all functions.

(cherry picked from FBD4223901)

ICF improvements.

Summary:
Re-worked the way ICF operates. The pass now checks for more than just
call instructions, but also for all references including function
pointers. Jump tables are handled too.

(cherry picked from FBD4372491)

[ICF] Don't re-fold functions in non-relocation mode.

Summary:
In-non relocation mode, when we run ICF the second time,
we fold the same functions again since they were not
removed from the function set. This diff marks them as
folded and ignores them during ICF optimization. Note
that we still want to optimize such functions since they
are potentially called from the code not covered by BOLT
in non-relocation mode.

Folded functions are also excluded from dyno stats with
this diff

Also print the number of times folded functions were called.
When 2 functions -  f1() and f2() are folded, that number
would be min(call_frequency(f1), call_frequency(f2)).

(cherry picked from FBD4399993)

[BOLT] Fix debug info update for zero-length ranges.

Summary:
Due to a clowntown on my part we were generating wrong ranges
when an empty range was seen on input. We were basically expanding
the range to include all basic blocks following such range and setting
wrong sizes at the same time.

Add "-dump-cu" option to llvm-dwarfdump that allows to look at debug
info of a single compile unit only. Saves time if we are only interested
in a subset of information.

(cherry picked from FBD4430989)

[BOLT] Report stale functions' percentage wrt all profiled functions.

Summary:
Report stale functions percentage with respect to all profiled
functions instead of all simple functions in the binary.
The new reporting format should make it more apparent if the
profile is out-of-date. Compare:

  BOLT-INFO: 341 (16.7% of all profiled) functions have invalid (possibly
stale) profile.

vs old:

  BOLT-INFO: 341 (0.3%)  functions have invalid (possibly stale) profile.

(cherry picked from FBD4451746)

Cover RSP-indexed accesses in frame optimization

Summary:
Add a new dataflow analysis to recover the value of RSP at a
given point of the program. This value is expressed as an offset from
the CFA. Use this information to detect redundant load in memory
accesses performed via RSP as well, not only RBP as done previously.
Bail when RSP value (as an offset of the CFA) can't be reliably
determined with a simple dataflow analysis.

(cherry picked from FBD4372261)

[BOLT] Support overwriting jump tables in-place.

Summary:
Add an option to overwrite jump tables without moving and make it a
default:

  -jump-tables   - jump tables support (default=basic)
    =none        -   do not optimize functions with jump tables
    =basic       -   optimize functions with jump tables
    =move        -   move jump tables to a separate section
    =split       - split jump tables section into hot and cold based on
                   function execution frequency
    =aggressive  - aggressively split jump tables section based on usage of
                   the tables

(cherry picked from FBD4448499)

Indirect call promotion optimization.

Summary:
Perform indirect call promotion optimization in BOLT.

The code scans the instructions during CFG creation for all
indirect calls.  Right now indirect tail calls are not handled
since the functions are marked not simple.  The offsets of the
indirect calls are stored for later use by the ICP pass.

The indirect call promotion pass visits each indirect call and
examines the BranchData for each.  If the most frequent targets
from that callsite exceed the specified threshold (default 90%),
the call is promoted.  Otherwise, it is ignored.  By default,
only one target is considered at each callsite.

When an candiate callsite is processed, we modify the callsite
to test for the most common call targets before calling through
the original generic call mechanism.

The CFG and layout are modified by ICP.

A few new command line options have been added:
-indirect-call-promotion
-indirect-call-promotion-threshold=<percentage>
-indirect-call-promotion-topn=<int>

The threshold is the minimum frequency of a call target needed
before ICP is triggered.

The topn option controls the number of targets to consider for
each callsite, e.g. ICP is triggered if topn=2 and the total
requency of the top two call targets exceeds the threshold.

Example of ICP:

C++ code:

  int B_count = 0;
  int C_count = 0;

  struct A { virtual void foo() = 0; }
  struct B : public A { virtual void foo() { ++B_count; }; };
  struct C : public A { virtual void foo() { ++C_count; }; };

  A* a = ...
  a->foo();
  ...

original:
  400863:	49 8b 07             	mov    (%r15),%rax
  400866:	4c 89 ff             	mov    %r15,%rdi
  400869:	ff 10                	callq  *(%rax)
  40086b:	41 83 e6 01          	and    $0x1,%r14d
  40086f:	4d 89 e6             	mov    %r12,%r14
  400872:	4c 0f 44 f5          	cmove  %rbp,%r14
  400876:	4c 89 f7             	mov    %r14,%rdi
  ...

after ICP:
  40085e:	49 8b 07             	mov    (%r15),%rax
  400861:	4c 89 ff             	mov    %r15,%rdi
  400864:	49 ba e0 0b 40 00 00 	movabs $0x400be0,%r10
  40086b:	00 00 00
  40086e:	4c 3b 10             	cmp    (%rax),%r10
  400871:	75 29                	jne    40089c <main+0x9c>
  400873:	41 ff d2             	callq  *%r10
  400876:	41 83 e6 01          	and    $0x1,%r14d
  40087a:	4d 89 e6             	mov    %r12,%r14
  40087d:	4c 0f 44 f5          	cmove  %rbp,%r14
  400881:	4c 89 f7             	mov    %r14,%rdi
  ...

  40089c:	ff 10                	callq  *(%rax)
  40089e:	eb d6                	jmp    400876 <main+0x76>

(cherry picked from FBD3612218)

[BOLT] Update section names in output file.

Summary:
Re-write section header string table to reflect new names
given to sections. Old sections get ".bolt.org" prefix.

E.g. when we write ".eh_frame" section, we keep the old copy
but rename it to ".bolt.org.eh_frame".

Note: the new code section is named ".bolt.text" - it contains split
function bodies, while original ".text" name is left unchanged.

(cherry picked from FBD4524935)

[BOLT] Detect and prevent re-optimization attempts.

Summary:
Whenever we try to re-optimize a binary with BOLT we should
issue an error and exit.

(cherry picked from FBD4525228)

[BOLT] Reject sanitized binaries.

Summary:
Whenever input binary is suspected to have been sanitized we print an error
message and exit. I've checked that "__asan_init*" symbol
presence is the most conservative way to detect "sanitization".

(cherry picked from FBD4525478)

[BOLT] Skip disassembly of padding at function end.

Summary:
Some functions coming from assembly may not have been marked
with size. We assume the size to include all bytes up to
the next function/object in the file. As a result,
function body will include any padding inserted by the linker.
If linker inserts 0-value bytes this could be misinterpreted
as invalid instruction and BOLT will bail out on such functions
in non-relocation mode, and give up on a binary in relocation
mode.

This diff detects zero-padding, ignores it, and continues processing
as normal.

(cherry picked from FBD4528893)

[BOLT] Emit short tail calls in relocation mode.

Summary:
To minimize size of the output code we should emit tail calls
that are as short as possible. For this we have to convert a synthetic
TAILJMPd into JMP_1 instruction. This should be one of the last passes
as most of analysis passes could break since tail calls will no longer
be marked as such.

The total size of the code is smaller, but not by much - hot text was
reduced by 192 bytes.

(cherry picked from FBD4557804)

[BOLT] Add support for *GOTPCRELX relocation type.

Summary:
gcc5 can generate new types of relocations that give linker a freedom
to substitute instructions. These relocations are PC-relative, and
since we manually process such relocations they don't present
much of a problem.

Additionally, detect non-pc-relative access from code into a middle of
a function. Occasionally I've seen such code, but don't know exactly
how to trigger its generation. Just issue a warning for now.

(cherry picked from FBD4566473)

[BOLT] Move BOLT passes under Passes subdirectory (NFC).

Summary:
Move passes under Passes subdirectory.

Move inlining passes under Passes/Inliner.*

(cherry picked from FBD4575832)

[BOLT] Fix -jump-tables=basic in relocation mode.

Summary:
In a prev diff I added an option to update jump tables in-place (on by default)
and accidentally broke the default handling of jump tables in relocation
mode. The update should be happening semi-automatically, but because
we ignore relocations for jump tables it wasn't happening (derp).

Since we mostly use '-jump-tables=move' this hasn't been noticed for
some time.

This diff gets rid of IgnoredRelocations and removes relocations
from a relocation set when they are no longer needed. If relocations
are created later for jump tables they are no longer ignored.

(cherry picked from FBD4595159)

[BOLT] Don't set code skew in relocations mode.

Summary:
We use code skew in non-relocation mode since functions have fixed
addresses, and internal alignment has to be adjusted wrt the skew.
However in relocation mode it interferes with effective code
alignment, and has to be disabled. I missed it when was re-basing
the relocation diff.

(cherry picked from FBD4599670)

[BOLT] Strip 'repz' prefix from 'repz retq'.

Summary:
Add pass to strip 'repz' prefix from 'repz retq' sequence. The prefix
is not used in Intel CPUs afaik. The pass is on by default.

(cherry picked from FBD4610329)

Fix warnings when compiling with clang (NFC)

Summary:
Fix inconsistent override keyword usages and initializes a
missing field of a Relocation object when using braced initializers.

(cherry picked from FBD4622856)

[BOLT] New CFI handling policy.

Summary:
The new interface for handling Call Frame Information:

  * CFI state at any point in a function (in CFG state) is defined by
    CFI state at basic block entry and CFI instructions inside the
    block. The state is independent of basic blocks layout order
    (this is implied by CFG state but wasn't always true in the past).
  * Use BinaryBasicBlock::getCFIStateAtInstr(const MCInst *Inst) to
    get CFI state at any given instruction in the program.
  * No need to call fixCFIState() after any given pass. fixCFIState()
    is called only once during function finalization, and any function
    transformations after that point are prohibited.
  * When introducing new basic blocks, make sure CFI state at entry
    is set correctly and matches CFI instructions in the basic block
    (if any).
  * When splitting basic blocks, use getCFIStateAtInstr() to get
    a state at the split point, and set the new basic block's CFI
    state to this value.

Introduce CFG_Finalized state to indicate that no further optimizations
are allowed on the function. This state is reached after we have synced
CFI instructions and updated EH info.

Rename "-print-after-fixup" option to "-print-finalized".

This diffs fixes CFI for cases when we split conditional tail calls,
and for indirect call promotion optimization.

(cherry picked from FBD4629307)

[BOLT] Detect and handle __builtin_unreachable().

Summary:
Calls to __builtin_unreachable() can result in a inconsistent CFG.
It was possible for basic block to end with a conditional branche
and have a single successor. Or there could exist non-terminated
basic block without successors.

We also often treated conditional jumps with destination past the end
of a function as conditional tail calls. This can be prevented
reliably at least when the byte past the end of the function does
not belong to the next function.

This diff includes several changes:
  * At disassembly stage jumps past the end of a function are converted
    into 'nops'. This is done only for cases when we can guarantee that
    the jump is not a tail call. Conversion to nop is required since the
    instruction could be referenced either by exception handling
    tables and/or debug info. Nops are later removed.
  * In CFG insert 'ret' into non-terminated basic blocks without
    successors (this almost never happens).
  * Conditional jumps at the end of the function are removed from
    CFG. The block will still have a single successor.
  * Cases where a destination of a jump instruction is the start
    of the next function, are still conservatively handled as
    (conditional) tail calls.

(cherry picked from FBD4655046)

[BOLT] Detect unmarked data in text.

Summary:
Sometimes a code written in assembly will have unmarked data (such as
constants) embedded into text.

Typically such data falls into a "padding" address space of a function.

This diffs detects such references, and adjusts the padding space to
prevent overwriting of code in data.

Note that in relocation mode we prefer to overwrite the original code
(-use-old-text) and thus cannot simply ignore data in text.

(cherry picked from FBD4662780)

[BOLT] Update tests

Summary:
Fix validateCFG to handle BBs that were generated from code that used
_builtin_unreachable().
Add -verify-cfg option to run CFG validation after every optimization
pass.

(cherry picked from FBD4641174)

[BOLT] Fix verbose output.

Summary:
Inadvertently, output of BOLT became way too verbose. Discovered while
building HHVM on master.

(cherry picked from FBD4669881)

[BOLT] Fix gcc5 build.

Summary: A <numeric> include is required for gcc5 build.

(cherry picked from FBD4671953)

Fix hfsort callgraph stats, add hfsort test.

Summary:
The stats for call sites that are not included in the call graph were broken.
The intention is to count the total number of call sites vs. the number of call sites that are ignored because they have targets that are not BinaryFunctions.

Also add a new test for hfsort.

(cherry picked from FBD4668631)

[BOLT] Do not process empty functions.

Summary:
While running on a recent test binary BOLT failed with an error. We were
trying to process '__hot_end' (which is not really a function), and asserted
that it had no basic blocks.

This diff marks functions with empty basic blocks list as non-simple since
there's no need to process them.

(cherry picked from FBD4696517)

[BOLT] Improve dynostats output.

Summary:
Reduce verbosity of dynostats to make them more readable.

  * Don't print "before" dynostats twice.
  * Detect if dynostats have changed after optimization and print
    before/after only if at least one metric have changed. Otherwise
    just print dynostats once and indicate "no change".
  * If any given metric hasn't changed, then print the difference as
    "(=)" as opposed to (+0.0%).

(cherry picked from FBD4705920)

[BOLT] Do not overwrite starting address in non-relocation mode.

Summary:
In non-relocation mode we shouldn't attemtp to change ELF
entry point.

What made matters worse - it broke '-max-funcs=' and '-funcs=' options
since an entry function more often than not was excluded from the list
of processed functions, and we were setting entry point to 0.

(cherry picked from FBD4720044)

[BOLT] Add option to print only specific functions.

Summary:
Add option '-print-only=func1,func2,...' to print only functions
of interest. The rest of the functions are still processed and
optimized (e.g. inlined), but only the ones on the list are printed.

(cherry picked from FBD4734610)

[BOLT] Don't allow non-symbol targets in ICP

Summary:
ICP was letting through call targets that weren't symbols.  This diff
filters out the non-symbol targets before running ICP.

(cherry picked from FBD4735358)

Change dynostats dynamic instruction count policy

Summary:
Also add LOAD/STORE counters.

(cherry picked from FBD4732284)

[BOLT] Issue error in relocs mode if input is lacking relocations.

Summary:
If we specify "-relocs" flag and an input has no relocations we
proceed with assumptions that relocations were there and break the
binary.

Detect the condition above, and reject the input.

(cherry picked from FBD4761239)

[BOLT] Organize options in categories for pretty printing (near NFC).

Summary:
Each BOLT-specific option now belongs to BoltCategory or BoltOptCategory.

Use alphabetical order for options in source code (does not affect
output).

The result is a cleaner output of "llvm-bolt -help" which does not
include any unrelated llvm options and is close to the following:

.....

BOLT generic options:

  -data=<string>                                       - <data file>
  -dyno-stats                                          - print execution info based on profile
  -hot-text                                            - hot text symbols support (relocation mode)
  -o=<string>                                          - <output file>
  -relocs                                              - relocation mode - use relocations to move functions in the binary
  -update-debug-sections                               - update DWARF debug sections of the executable
  -use-gnu-stack                                       - use GNU_STACK program header for new segment (workaround for issues with strip/objcopy)
  -use-old-text                                        - re-use space in old .text if possible (relocation mode)
  -v=<uint>                                            - set verbosity level for diagnostic output

BOLT optimization options:

  -align-blocks                                        - try to align BBs inserting nops
  -align-functions=<uint>                              - align functions at a given value (relocation mode)
  -align-functions-max-bytes=<uint>                    - maximum number of bytes to use to align functions
  -boost-macroops                                      - try to boost macro-op fusions by avoiding the cache-line boundary
  -eliminate-unreachable                               - eliminate unreachable code
  -frame-opt                                           - optimize stack frame accesses
  ......

(cherry picked from FBD4793684)

[BOLT] Fix debug info update for inlining.

Summary:
When inlining, if a callee has debug info and a caller does not
(i.e. a containing compilation unit was compiled without "-g"), we try
to update a nonexistent compilation unit. Instead we should skip
updating debug info in such cases.

Minor refactoring of line number emitting code.

(cherry picked from FBD4823982)

[BOLT] Detect and reject binaries built for coverage.

Summary: Don't attempt to optimize binaries built with coverage support.

(cherry picked from FBD4810330)

[BOLT] Fix double jump peephole, remove useless conditional branches.

Summary:
I split some of this out from the jumptable diff since it fixes the
double jump peephole.

I've changed the pass manager so that UCE and peepholes are not called
after SCTC.  I've incorporated a call to the double jump fixer to SCTC
since it is needed to fix things up afterwards.

While working on fixing the double jump peephole I discovered a few
useless conditional branches that could be removed as well.  I highly
doubt that removing them will improve perf at all but it does seem
odd to leave in useless conditional branches.

There are also some minor logging improvements.

(cherry picked from FBD4751875)

[BOLT] Fix branch count in removeDuplicateConditionalSuccessor().

Summary:
When we merge the original branch counts we have to make sure
both of them have a profile. Otherwise set the count to COUNT_NO_PROFILE.

The misprediction count should be 0.

(cherry picked from FBD4837774)

[BOLT] Relocation support for non-allocatable sections.

Summary:
Relocations can be created for non-allocatable (aka Note) sections.

To start using this for debug info, the emission has to be moved
earlier in the pipeline for relocation processing to kick in.

(cherry picked from FBD4835204)

[BOLT] Enable SCTC by default.

(cherry picked from FBD4837849)

[BOLT] Don't abort on processing binaries with .gdb_index section

Summary:
While writing non-allocatable sections we had an assumption that the
size of such section is congruent to the alignment, as typically
such sections are a collections of fixed-sized elements. .gdb_index
breaks this assumption.

This diff removes the assertion that was triggered by a presence of
.gdb_index section, and makes sure that we insert a padding if we are
appending to a section with a size not congruent to section alignment.

(cherry picked from FBD4844553)

[BOLT] Fix branch data for __builtin_unreachable().

Summary:
When we have a conditional branch past the end of function (a result
of a call to__builtin_unreachable()), we replace the branch with nop,
but keep branch information for validation purposes. If that branch
has a recorded profile we mistakenly create an additional successor
to a containing basic block (a 3rd successor).

Instead of adding the branch to FTBranches list we should be adding
to IgnoredBranches.

(cherry picked from FBD4912840)

[BOLT] Update function address and size in relocation mode.

Summary:
Set function addresses after code emission but before we update
debug info and symbol table entries.

(cherry picked from FBD5029609)

[BOLT] Update .gdb_index section.

Summary: Update address table in .gdb_index section.

(cherry picked from FBD5068255)

[BOLT] Support adding new non-allocatable sections.

Summary:
We had the ability to add allocatable sections before. This diff
expands this capability to non-allocatable sections.

(cherry picked from FBD5082018)

[BOLT] Add option to keep/generate .debug_aranges.

Summary:
GOLD linker removes .debug_aranges while generating .gdb_index.
Some tools however rely on the presence of this section.
Add an option to generate .debug_aranges if it was removed,
or keep it in the file if it was present.

Generally speaking .debug_aranges duplicates information present
in .gdb_index addresses table.

(cherry picked from FBD5084808)

[BOLT] Add jump table support to ICP

Summary:
Add jump table support to ICP.  The optimization is basically the same
as ICP for tail calls.  The big difference is that the profiling data
comes from the jump table and the targets are local symbols rather than
global.

I've removed an instruction from ICP for tail calls.  The code used to
have a conditional jump to a block with a direct jump to the target, i.e.

  B1: cmp foo,(%rax)
      jne B3
  B2: jmp foo
  B3: ...

this code is now:

  B1: cmp foo,(%rax)
      je  foo
  B2: ...

The other changes in this diff:
- Move ICP + new jump table support to separate file in Passes.
- Improve the CFG validation to handle jump tables.
- Fix the double jump peephole so that the successor of the modified
  block is updated properly.  Also make sure that any existing branches
  in the block are modified to properly reflect the new CFG.
- Add an invocation of the double jump peephole to SCTC.  This allows
  us to remove a call to peepholes/UCE occurring after fixBranches() in
  the pass manager.
- Miscellaneous cleanups to BOLT output.

(cherry picked from FBD4727757)

[BOLT] Fix debug info for input with continuous range.

Summary:
When we see a compilation unit with continuous range on input,
it has two attributes: DW_AT_low_pc and DW_AT_high_pc. We convert the
range to a non-continuous one and change the attributes to
DW_AT_ranges and DW_AT_producer. However, gdb seems to expect
every compilation unit to have a base address specified via
DW_AT_low_pc, even when its value is always 0. Otherwise gdb will
not show proper debug info for such modules.

With this diff we produce DW_AT_ranges followed by DW_AT_low_pc.
The problem is that the first attribute takes DW_FORM_sec_offset
which is exactly 4 bytes, and in many cases we are left with
12 bytes to fill in. We used to fill this space with DW_AT_producer,
which took an arbitrary-length field. For DW_AT_low_pc we can
use a trick of using DW_FORM_udata (unsigned ULEB128 encoded
integer) which can take up to 12 bytes, even when the value is 0.

(cherry picked from FBD5109798)

[BOLT] Add dataflow infrastructure

Summary:
This diff introduces a common infrastructure for performing
dataflow analyses in BinaryFunctions as well as a few analyses that are
useful in a variety of scenarios. The largest user of this
infrastructure so far is shrink wrapping, which will be added in a
separate diff.

(cherry picked from FBD4983671)

[BOLT] Rework debug info processing.

Summary:
Multiple improvements to debug info handling:
  * Add support for relocation mode.
  * Speed-up processing.
  * Reduce memory consumption.
  * Bug fixes.

The high-level idea behind the new debug handling is that we don't save
intermediate state for ranges and location lists. Instead we depend
on function and basic block address transformations to update the info
as a final post-processing step.

For HHVM in non-relocation mode the peak memory went down from 55GB to 35GB. Processing time went from over 6 minutes to under 5 minutes.

(cherry picked from FBD5113431)

Don't add useless uncond branch to fallthroughs when running SCTC.

Summary:
SCTC was sometimes adding unconditional branches to fallthrough blocks.
This diff checks to see if the unconditional branch is really necessary, e.g.
it's not to a fallthrough block.

(cherry picked from FBD5098493)

[BOLT] Optimize jump tables with hot entries

Summary:
This diff is similar to Bill's diff for optimizing jump tables
(and is built on top of it), but it differs in the strategy used to
optimize the jump table. The previous approach loads the target address
from the jump table and compare it to check if it is a hot target. This
accomplishes branch misprediction reduction by promote the indirect jmp
to a (more predictable) direct jmp.

  load  %r10, JMPTABLE
  cmp   %r10, HOTTARGET
  je    HOTTARGET
  ijmp  [JMPTABLE + %index * scale]

The idea in this diff is instead to make dcache better by avoiding the
load of the jump table, leaving branch mispredictions as a secondary
target. To do this we compare the index used in the indirect jmp and if
it matches a known hot entry, it performs a direct jump to the target.

  cmp  %index, HOTINDEX
  je   CORRESPONDING_TARGET
  ijmp [JMPTABLE + %index * scale]

The downside of this approach is that we may have multiple indices
associated with a single target, but we only have profiling to show
which targets are hot and we have no clue about which indices are hot.

  INDEX    TARGET
  0        4004f8
  8        4004f8
  10       4003d0
  18       4004f8

  Profiling data:
  TARGET   COUNT
  4004f8   10020
  4003d0   17

In this example, we know 4004f8 is hot, but to make a direct call to it
we need to check for indices 0, 8 and 18 -- 3 comparisons instead of 1.

Therefore, once we know a target is hot, we must generate code to
compare against all possible indices associated with this target because
we don't know which index is the hot one (IF there's a hotter index).

  cmp %index, 0
  je  4004f8
  cmp %index, 8
  je  4004f8
  cmp %index, 18
  je  4004f8
  (... up to N comparisons as in --indirect-call-promotion-topn=N )
  ijmp [JMPTABLE + %index * scale]

(cherry picked from FBD5005620)

Add .bolt_info notes section containing BOLT revision and command line args.

Summary:
Optinally add a .bolt_info notes section containing BOLT revision and command line args.
The new section is controlled by the -add-bolt-info flag which is on by default.

(cherry picked from FBD5125890)

[BOLT] Fix C++ ABI function alignment.

Summary: C++ functions have to be aligned at 2-bytes minimum on x86-64.

(cherry picked from FBD5128185)

[BOLT] Fix no-assertions build.

(cherry picked from FBD5130285)

Add option to generate function order file.

Summary: Add -generate-function-order=<filename> option to write the computed function order to a file.  We can read this order in later rather than recomputing each time we process a binary with BOLT.

(cherry picked from FBD5127915)

[BOLT] Emit sorted DWARF ranges and location lists.

Summary:
When producing address ranges and location lists for debug info
add a post-processing step that sorts them and merges adjacent
entries.

Fix a memory allocation/free issue for .debug_ranges section.

(cherry picked from FBD5130583)

[BOLT] Fix SCTC again.

Summary: Respect hot/cold boundaries when using BinaryFunction::getBasicBlockAfter().

(cherry picked from FBD5153379)

[BOLT] Update addresses for DW_TAG_GNU_call_site and DW_TAG_label.

Summary:
Some DWARF tags (such as GNU_call_site and label) reference instruction
addresses in the input binary. When we update debug info we need to
update these tags too with new addresses.

Also fix base address used for calculation of output addresses in
relocation mode.

(cherry picked from FBD5155814)

[BOLT] Fix SCTC again again.

Summary: I put the const_cast<BinaryFunction *>(this) on the wrong version of getBasicBlockAfter().  It's on the right one now.

(cherry picked from FBD5159127)

HFSort/call graph refactoring

Summary:
I've factored out the call graph code from dataflow and function reordering code and done a few small renames/cleanups.  I've also moved the function reordering pass into a separate file because it was starting to get big.

I've got more refactoring planned for hfsort/call graph but this is a start.

(cherry picked from FBD5140771)

[BOLT] Do not assert on an empty location list.

Summary:
Clang generates an empty debug location list, which doesn't make sense,
but we probably shouldn't assert on it and instead issue a warning
in verbosity mode. There is only a single empty location list in the
whole llvm binary.

(cherry picked from FBD5166666)

[BOLT] More CG refactoring

Summary:
Do some additional refactoring of the CallGraph class.  Add a BinaryFunctionCallGraph class that has the BOLT specific bits.  This is in preparation to moving the generic CallGraph class into a library that both BOLT and HHVM can use.

Make data members of CallGraph private and add the appropriate accessor methods.

(cherry picked from FBD5143468)

[BOLT] Make hfsort+ deterministic and add test case

Summary:
Make hfsort+ algorithm deterministic.
We only had a test for hfsort.  Since hfsort+ is going to be the default, I've added a test for that too.

(cherry picked from FBD5143143)

[BOLT] Fix misc issues in relocation mode.

Summary:
Fix issues discovered while testing LTO mode with bfd linker:

  * Correctly update absolute function references from code
    with addend.
  * Support .got.plt section generated by bfd linker.
  * Support quirks of .tbss section.
  * Don't ignore functions if the size in FDE doesn't match the
    size in the symbol table. Instead keep processing using the
    maximum indicated size.

(cherry picked from FBD5178831)

[BOLT] Add shrink wrapping pass

Summary:
Add an implementation for shrink wrapping, a frame optimization
that moves callee-saved register spills from hot prologues to cold
successors.

(cherry picked from FBD4983706)

Split FrameAnalysis and improve LivenessAnalysis

Summary:
Split FrameAnalysis into FrameAnalysis and RegAnalysis, since
some optimizations only require register information about functions,
not frame information. Refactor callgraph walking code into the
CallGraphWalker class, allowing any analysis that depend on the call
graph to easily traverse it via a visitor pattern. Also fix
LivenessAnalysis, which was broken because it was not considering
registers read into callees and incorporating this into caller.

(cherry picked from FBD5177901)

[BOLT] Fix ELF inter-section references

Summary:
Since we are stripping non-allocatable relocation sections from
the binary and adding new sections it changes section indices
in the binary. Some sections refer to other sections by their index
which is stored in sh_link or sh_info field. Hence we need to update
these field.

In the past update of indices was done ad-hoc and as we started
adding more complex updates to section header table the update
mechanism became broken in some cases. As a result, we were putting
wrong indices into sh_link/sh_info.

The broken case was discovered while investigating a problem with
a stripped BOLTed binary. In BOLTed binary .rela.plt was incorrectly
pointing to one of the debug sections and strip command removed
the debug section together with .rela section that was referencing it.

The new update mechanism computes complete old to new section index
mapping and updates sh_link/sh_info fields based on the mapping
before writing section header entries into an output file.

(cherry picked from FBD5207378)

[BOLT] Fix hfsort+ crash when no perf data is present.

Summary: hfsort+ was trying to access the back() of an empty vector when no perf data is present.  Just add a guard around that code.

(cherry picked from FBD5206962)

[BOLT] Only print stats when requested

Summary:
Make LLVM timers only output numbers when the -time-opts option
is used.

(cherry picked from FBD5212221)

Fix dynostats for conditional tail calls

Summary:
Don't treat conditional tail calls as branches for dynostats. Count
taken conditional tails calls as calls. Change SCTC to report dynamic
numbers after it is done.

(cherry picked from FBD5203708)

[BOLT] Fix hfsort+ caching mechanism

Summary:
There's good news and bad news.

The good news is that this fixes the caching mechanism used by hfsort+ so that we always get the correct end results, i.e. the order is the same whether the cache is enabled or not.
The bad news is that it takes about the same amount of time as the original to run. (~6min)
The good news is that I can make some improvements on this implementation which I'll put up in another diff.

The problem with the old caching mechanism is that it was caching values that were dependent on adjacent sets of clusters.  It only invalidated the clusters being merged and none of other clusters that might have been affected.  This version computes the adjacency information up front and updates it after every merge, rather than recomputing it for each iteration.  It uses the adjacency data to properly invalidate any cached values.

(cherry picked from FBD5203023)

[BOLT] Expand BOLT report for basic block ordering

Summary:
Add a new positional option onto bolt: "-print-function-statistics=<uint64>"
which prints information about block ordering for requested number of functions.

(cherry picked from FBD5105323)

[BOLT] Fix SCTC execution count assertion

Summary:
SCTC is currently asserting (my fault :-) when running in
combination with hot jump table entries optimization. This optimization
sets the frequency for edges connecting basic blocks it creates and jump
table targets based on the execution count of the original BB containing
the indirect jump.

This is OK as an estimation, but it breaks our assumption that the sum of
the frequency of preds edges equals to our BB frequency. This happens
because the frequency of the BB is rarely equal to its outgoing edges
frequency.

SCTC, in turn, was updating the execution count for BBs with tail calls
by subtracting the frequency count of predecessor edges. Because hot
jump table entries optimization broke the BB exec count = sum(preds freq)
invariant, SCTC was asserting.

To trigger this, the input program must have a jump table where each
entry contains a tail call. This happens in the HHVM binary for func
_ZN4HPHP11collections5issetEPNS_10ObjectDataEPKNS_10TypedValueE.

(cherry picked from FBD5222504)