Subzero. Fixes a bug in the register allocator.

This bug was uncovered While implementing the llvm.nacl.atomic.cmpxchg
lowering for i64 for ARM32. For reference, the lowering is

retry:
    ldrexd     tmp_i, tmp_i+1 [addr]
    cmp        tmp_i+1, expected_i+1
    cmpeq      tmp_i, expected_i
    strexdeq   success, new_i, new_i+1, [addr]
    movne      expected_i+1, tmp_i+1
    movne      expected_i, tmp_i
    cmpeq      success, #0
    bne        retry
    mov        dest_i+1, tmp_i+1
    mov        dest_i, tmp_i

The register allocator would allocate r4 to both success and new_i,
which is clearly wrong (expected_i is alive thought the cmpxchg loop.)
Adding a fake-use(new_i) after the loop caused the register allocator
to fail due to the impossibility to allocate a register for an infinite
weight register. The problem was being caused for not evicting live
ranges that were assigned registers that alias the selected register.

BUG=
R=kschimpf@google.com, stichnot@chromium.org

Review URL: https://codereview.chromium.org/1373823006 .

Subzero. Adds ldrex, strex, and dmb support (ARM32)

These instructions are used to load/store data atomically, and to
notify the processor about a data memory barrier. They are used for
implementing the llvm.nacl.atomic.* lowerings.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4076
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1378303003 .

Add include files so that IceCompilerServer.cpp can compile on MSC.

A recent change to IceCompilerServer.cpp was added to allow fatal
errors to return exit status zero. However, this code called ::write
(a C function) that is not defined when compiling with MSC. This CL
adds includes to fix this problem.

BUG=None
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1379613005 .

Subzero: Fix a bug in register allocator overlap computation.

When the register allocator decides whether to allow the candidate's live range to overlap its preferred variable's live range (and share their register), it needs to consider whether any redefinitions in one variable occur within the live range of the other variable, in which case overlap should not be allowed.

There was a bug in the API for iterating over the defining instructions for a variable, in which the earliest definition might be ignored in some cases.  This came from the fact that the first definition and latter definitions are split apart for translation speed reasons, and a particular API is needed for finding an unambiguous first definition, which is possible when all definitions are within a single block but not so possible when definitions cross block boundaries.  (This only happens for the simple phi lowering.)

Since both semantics are needed, a separate API is added to support both.

For spec2k, the asm output is identical to before, so this changes nothing.  When translating spec2k with "-O2 -phi-edge-split=0", there is a single minor difference in ammp that actually looks legit in both cases.

However, when testing an upcoming CL, -phi-edge-split=0 triggered the bug, causing gcc and crafty to fail with incorrect output.

This CL also fixes some minor issues, and adds dump output of the instruction definition list when available.

BUG= none
R=jpp@chromium.org

Review URL: https://codereview.chromium.org/1381563004 .

Subzero: Add missing content to CfgLocalAllocator.

The std::list<> implementation used by g++ needs some extra stuff defined in the custom allocator.

This can be smoke-tested with:

  make -f Makefile.standalone CXX=g++ LLVM_EXTRA_WARNINGS="-Wno-unknown-pragmas -Wno-unused-parameter -Wno-comment -Wno-enum-compare -Wno-strict-aliasing" STDLIB_FLAGS=

until the link fails for unrelated reasons.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4325
R=kschimpf@google.com

Review URL: https://codereview.chromium.org/1367403004 .

Subzero: Change -asm-verbose output to print more useful info.

Frame offsets for variables are emitted using a symbolic name based on the variable's name.  This makes it a bit easier to digest the asm code.

For example, if variable Foo gets an esp offset 24, asm like this:
  ... 24(%esp) ...
will instead be emitted like this:
  lv$Foo = 24
  ...
  ... lv$Foo(%esp) ...

Predecessor labels are printed for each basic block.

Loop nest depth is printed for each basic block.  (Would be nice if we had loop header info as well.)

BUG= none
R=jpp@chromium.org

Review URL: https://codereview.chromium.org/1377323002 .

Add check to verify alignment on global variables.

Moves the alignment check method from the function block parser, to the
top-level parser, and then uses it to also check alignment on global
variables.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4329
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1378163002 .

Fix pnacl-sz to return with staus 0 in report_fatal_error.

Fixes pnacl-sz to return with exit status 0 in report_fatal_error, if
command line flag --exit-status is specified. The importance of this
is that it allows afl-fuzz to not report the mutation as a crash.

In addition, afl-fuzz doesn't record crash paths in its search
history.  By returning success, afl-fuzz can continue to apply
additional mutations to the bad input. This allows afl-fuzz to add
errors that require multiple changes to occur on the input.

BUG=None
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1382653002 .

Check that address is i32 for indirect calls.

Fixes bug where code did not check that the address of an indirect call must be i32.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4321
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1363983002 .

Subzero. Eliminates the use of Variable64On32 as operands in ARM.

This is in preparation for adding atomic support to the ARM backend.
Moreover, the code is becoming increasingly complicated due to the use
of Variable64On32 as instruction operands.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4076
R=kschimpf@google.com

Review URL: https://codereview.chromium.org/1372083002 .

Subzero: Improve usability of liveness-related tools.

1. Rename all identifiers containing "nonkillable" to use the more understandable "redefined".

2. Change inferTwoAddress() to be called inferRedefinition(), and to check *all* instruction source variables (instead of just the first source operand) against the Dest variable.  This eliminates the need for several instances of _set_dest_redefined().  The performance impact on translation time is something like 0.1%, which is dwarfed by the usability gain.

3. Change a cryptic assert in (O2) live range construction to print detailed information on the liveness errors.

4. Change a cryptic assert in (Om1) live range construction to do the same.

BUG= none
R=jpp@chromium.org

Review URL: https://codereview.chromium.org/1368993004 .

Subzero. Enables (most) crosstests for ARM32.

This patch enables many crosstests for ARM32. Very limited vector
support is implemented (essentially, whatever it takes to compile the
.ll files contain vector operations.)

Atomics as well as vector crosstests are still disabled.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4076
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1359193003 .

Consolidate shift processing into utility function

Move the three shift processing blocks into one function, refactor for some
removal of commonality.
BUG=none
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1364603002 .

Subzero: Improve handling of alloca instructions of constant size.

PNaCl simplifies varargs calls by creating a known-size argument array with an alloca instruction, and passing the address of that argument array.  These alloca instructions don't necessarily require use of a frame pointer, freeing up the frame pointer register for normal register allocation.

These varargs calls sometimes show up in cold paths of hot functions, so increasing the number of registers available to the register allocator can produce tangible gains.

This patch does a simple recognition of these alloca patterns, and on x86 doesn't force a frame pointer if all alloca instructions are suitable.

Future work is to avoid saving the alloca result as a local variable, and instead rematerialize the address as needed with respect to the stack or frame pointer.

BUG= none
R=jpp@chromium.org

Review URL: https://codereview.chromium.org/1361803002 .

Subzero: Enable the asm-verbose.ll test for ARM32.

BUG= none
R=jpp@chromium.org

Review URL: https://codereview.chromium.org/1356953003 .

Fix code checking arguments to an intrinsic call.

Fixes instrinsic function "validateCall" to properly define which
parameter type doesn't match the expected signature for that
intrinsic. Previous code did not take into account that the first
element of the intrinsic signature was the return type.

Also fixes error messages to print the name of the intrinsic function.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4326
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1359993002 .

Require that the module symbol table can't appear after function.

The bitcode parser assumes that the module symbol table, if it exists,
must appear before the first function
block (i.e. defininition). However, the parser did not check this
constraint. This patch fixes that omission.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4320
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1359923002 .

Fix pnacl-sz to not accept files containing multiple modules.

Previous code checked, after the fact, that there weren't multiple
modules in the block. However, the code for TopLevelParser assumes
that there is only on module block, allowing it to more efficiently
test internal state. To fix the problem, modified
TopLevelParser::ParseBlock to fail, and not attempt to parse the second
block if the file contains more than one block.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4260
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1362643002 .

Optimize 64-bit shifts by constants for x86-32
Hopefully improves perf in fpclassifyd in ammp spec test.

BUG=none
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1351133003 .

Check that element type correct in vector insert element.

Fixes bug where pnacl-sz was not checking if the inserted type matched
the element type of the corresponding vector. Also fixes operand look
up (within a function) to error recover rather than always die with a
fatal error.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4313
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1357273004 .

Subzero. ARM32 Fcmp lowering.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4076
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1356763004 .

Subzero: Fix -enable-block-profile.

Defer hi/lo i64 var splitting until after the block profiling IR is inserted, since block profiling operates on i64 counters.

BUG= none
R=jpp@chromium.org

Review URL: https://codereview.chromium.org/1357733004 .

Fix call instructions to check parameter types for consistency.

Checks each parameter of a call against the corresponding function
signature.  It also checks that parameters are valid PNaCl parameter
types, unless the call is to an intrinsic.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4309
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1354673002 .

Subzero. Implements TargetDataARM32::lowerConstants.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4076
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1347223003 .

Subzero: Fix a couple of debugging tools.

1. Regalloc dump output was displaying status updates for the wrong variable in some cases.

2. getPhysicalRegister() creates a variable for referring to a specific physical register for low-level purposes, such as the stack pointer, or the frame pointer, or a pushed/popped callee-save register.  We change its behavior so that all such physical registers do not have their liveness tracked/validated, not just the stack pointer.

For #2, the original behavior was causing a liveness validation failure if a function had a single basic block and used callee-save registers, and the -asm-verbose flag was used.  This is because -asm-verbose runs a final liveness pass after the prolog/epilog are generated, and the initial callee-save register pushes would make it look like single-basic-block variables are live coming into a basic block, which is a hallmark of a liveness problem.

BUG= none
R=jpp@chromium.org

Review URL: https://codereview.chromium.org/1353923004 .

Refactor Hi and Lo out of Variable.

BUG=
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1326013002 .

Don't allow multiple symbol tables in the module block.

Fix handling of module value symbol tables. Also deals with
case where the module doesn't have a global variables block.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4320
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1345293002 .

Improve use of CfgLocalAllocator and introduce containers that use it.

This doesn't make a big difference but does reduce the proportion of time spent
in malloc and free.

BUG=
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1349833005 .

Fixes ARM32 VFP calling convetion.

Packs VFP arguments as tight as the ABI wants, and adds tests for
float and double arguments. vector argument tests will come soon.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4076
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1348393002 .

Check that symbol names in symbol tables are unique.

Makes sure that names within a symbol table are unique. Also cleans
up error reporting to be more consistent between symbol tables.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4301
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1347683003 .

Fix operand lookup in functions to check if local index out of range.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4302
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1346723002 .

Reflow comments to use the full width.

BUG=
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1341423002 .

Subzero: Remove an unwanted assert.

At the end, the ELF emitter code marks all the external symbols that are undefined in this object file, but it filters intrinsics out of this set.  Previously, it was asserting on a "bad intrinsic", meaning a function whose name starts with "llvm." but doesn't match a known intrinsic.

The assert doesn't really make sense here.  Either it should be more strongly validated early on in the translation, or it should just pass through (and the link will probably fail, or maybe not).

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4319
R=kschimpf@google.com

Review URL: https://codereview.chromium.org/1343283002 .

Subzero: Validate phi instructions after CFG construction.

It checks that each phi label corresponds to an incoming edge, and that each incoming edge has a corresponding phi label.

It does not check that duplicate incoming edges get the same phi value.

Performance impact is minimal (~0.2%) despite the O(N^2) implementation.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4304
R=jpp@chromium.org

Review URL: https://codereview.chromium.org/1351433002 .

Subzero: Generate correct code for shifts by a large immediate.

X86 requires an immediate shift value to fit within 8 bits.  It's undefined LLVM behavior if it doesn't (or in fact if the value exceeds the number of bits in the type width), but at least we can produce valid x86 instructions.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4316
R=ascull@google.com

Review URL: https://codereview.chromium.org/1339603006 .

Subzero: Add a flag to mock up bounds checking on unsafe references.

The idea is that, before each load or store operation, we add a couple of compares/branches against the load/store address, one for the lower bound and one for the upper bound.  The conditional branches would be to an error throwing routine, and would never be taken in practice.  The compares might be against an immediate or a global location.  So a load of [reg] will mock-expand to this:

  cmp reg, 0
  je label
  cmp reg, 1
  je label
label:
  mov xxx, [reg]

We also make address mode inference less aggressive, because for a load of e.g. [eax+4*ecx], we can't compare that address expression against anything in any instruction, so we would have to reconstruct the address and undo at least part of the address mode inference.

The bounds-check mock is added for loads, stores, and rmw operations (with an exclusion for stores to the stack for out-arg pushes).  There are probably a small handful of other cases that are missing the bounds check, but if we add the transformation inside legalize(), which is the most obvious place, we may add extra bounds checks because sometimes legalize() is called twice on the same operand.

BUG= none
R=ascull@google.com

Review URL: https://codereview.chromium.org/1338633005 .

Subzero: Fix off-by-one asserts in intrinsic info lookup routines.

It turns out that getNumArgs() and getReturnType() were never actually called except to print errors, so this bug was never encountered until now.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4315
R=ascull@google.com

Review URL: https://codereview.chromium.org/1347683002 .

Subzero: Fix labels for block profiling.

The problem is that the block profiling pass runs at the very beginning and commits to particular label strings, but the actual label names might change by emission time because of node reordering.

There was actually something of a workaround - given a label string from the profile output, inspect the *profiled* asm code and search for the block containing the increment of the counter location, as the name of the counter location label is related to the label string in the profile output.  However, it's tedious to mentally filter out the counter update code, and the counter update code has a huge impact on register allocation.

The solution is to use a persistent number in CfgNode for constructing the label string, which doesn't change when the nodes are reordered.

One note (independent of this change): Without block profiling, empty basic blocks are deleted and don't appear in the asm output.  But with block profiling, these blocks are never empty because they contain profile update instructions.  This means the profile output may contain labels that don't exist in the non-profiled asm.

Another note: New nodes created as a result of edge splitting from advanced phi lowering are not profiled.

BUG= none
R=ascull@google.com, jpp@chromium.org

Review URL: https://codereview.chromium.org/1341613002 .

Subzero: Don't contract an empty node that branches to itself.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4307
R=ascull@google.com

Review URL: https://codereview.chromium.org/1337113008 .

Subzero. Implements the scalar bitcast operations for ARM32.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4076
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1343783003 .

Refactor all instances of `typedef y x` to the C++11 `using x = y` syntax.

The C++11 syntax is more powerful as it also allows templating. This commit
converts all type aliasing to the same syntax for consistency.

BUG=
R=jpp@chromium.org

Review URL: https://codereview.chromium.org/1343843003 .

Implements int2fp, fp2int, and fp2fp conversions for ARM32.

64-bit ints (and vectors) are future work.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4076
R=kschimpf@google.com, stichnot@chromium.org

Review URL: https://codereview.chromium.org/1330933002 .

Add UBSAN build option and fix undefined behaviour errors.

1. The assembler tried to write to unaligned addresses but memcpy fixes this.
2. The InstKind and OperandKind enums allowed target specific kinds that did not
   fall in the defined range. Defining the maximum target kind in the enum sorts
   this problem.

BUG=
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1311653003 .

Fix the build for clang 3.8 and MINIMAL=1.

3.8 has stricter warnings which LLVM doesn't pass so we turn them off when
including the offending headers.

BUG=
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1318883007 .

Fix warnings produced by g++ on Windows.

Scraped non-pragma related warnings from a recent trybot run:

wget -O - 'http://build.chromium.org/p/tryserver.nacl/builders/nacl-toolchain-win7-pnacl-x86_64/builds/3221/steps/llvm_i686_w64_mingw32%20%28build%29/logs/stdio' | grep subzero | grep warning | grep -v pragma

BUG= none
R=ascull@google.com, jpp@chromium.org

Review URL: https://codereview.chromium.org/1315193020.

Subzero. Changes the declaration for ARM32 registers.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4076
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1310863007.

Subzero. Changes the Register Allocator so that it is aware of register
aliases.

BUG=
R=jvoung@chromium.org, stichnot@chromium.org

Review URL: https://codereview.chromium.org/1319203005.

Subzero: Fix MINIMAL build error.

A NOASSERT/MINIMAL build complains that private field Func is unused, which turned out to be true because of shadowing.

BUG= none
R=ascull@google.com

Review URL: https://codereview.chromium.org/1312903015

This improves the variable use weight by taking into account use in loops. It
further improves spec2k performance and fixes the regression in ammp. Loops are
identified using an extension to Tarjan's algorithm.

BUG=
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1318553003.

Subzero: Add a detailed design document.

This is a reStructuredText version of https://docs.google.com/a/google.com/document/d/1DmLVyZqqwWSZ0is91lipTm4xsfjInSba2KBOOxatYhg/edit?usp=sharing which for technical reasons is only visible to @google.com accounts.

Also update README.rst to be more accurate.

BUG= none
R=jfb@chromium.org, jpp@chromium.org, jvoung@chromium.org

Review URL: https://codereview.chromium.org/1309073003.

Subzero: Provide a macro for iterating over instruction variables.

This makes it easier and less error-prone to implement the relatively common
pattern of looking at all the Variable operands contained within an instruction.

BUG= none
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1323693002.

Weight variables for register allocation by their number of uses.

Count the number of instructions that use a variable following the heuristic
that more uses implies higher register priority. This is currently very simple
but is precursor work for weighting variables by loop nest depth.

BUG=
R=jvoung@chromium.org

Review URL: https://codereview.chromium.org/1312433004.

Fix Subzero's LLVM bitcode reader to use a diagnostic handler.

This encorporate the changes introduced by llvm CL
https://codereview.chromium.org/1310883003 (see for details).

BUG=None
R=dschuff@chromium.org, stichnot@chromium.org

Review URL: https://codereview.chromium.org/1312473006 .

Refactor LinearScan::scan from one huge function into smaller functions.

BUG=
R=jvoung@chromium.org, stichnot@chromium.org

Review URL: https://codereview.chromium.org/1310833003.

Fix handling unknown branches when parsing switch instructions.

The bitcode reader for the switch insruction did not check if the
branch labels were defined. This patch fixes the problem. Includes
test for such a case.

BUG=None
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1303003002 .

Fix bug in the call to random number generator in Cfg's ctor

BUG=
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1306713002.

Use separate random number generator for each randomization pass

This removes random number generator from GlobalContext class and decouples different randomization passes

1. Add a new constructor for random number generator which merge three arguments to into one seed for the underlying implementation of random number generator.

RandomNumberGenerator(uint64_t Seed, RandomizationPassesEnum RandomizationPassID, uint64_t Salt=0)

param Seed: Should be the global random number seed passed through command line.
param RandomizationPassID: Should be the ID for different randomization passes.
param Salt: Should be an additional integer salt, default to be 0.

2. Move the creation of random number generators to the call sites of randomization passes. Each randomization pass create its own random number generator with specific salt value.

Function reordering: Salt = 0 (default)
Basic Block reordering: Salt = Function Sequence Number
Global Variable reordering: Salt = 0 (default)
Pooled Constants reordering: Salt = Constants' Kind value (return of getKind())
               *Jump Tables: Salt = 0
Nop Insertion: Salt = Function Sequence Number
Register Alloc Randomization: Salt = (Function Sequence Number << 1) ^ (Kind == RAK_Phi ? 0u : 1u)
Constants Blinding: Salt = Function Sequence Number

*Jump tables are treated as pooled constants, but without Kind value as salt.

BUG=
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1300993002.

Inline memove for small constant sizes and refactor memcpy and memset.

The memory intrinsics are only optimized at -O1 and higher unless the
-fmem-intrin-opt flag is set to force to optimization to take place.

This change also introduces the xchg instruction for two register operands. This
is no longer used in the memory intrinsic lowering (or by anything else) but the
implementation is left for future use.

BUG=
R=jvoung@chromium.org, stichnot@chromium.org

Review URL: https://codereview.chromium.org/1278173009.

Change to use arena allocation for function-local data in parser.

Changes to use arena allocator of the CFG associated with function, for
vectors in the function parser.

BUG=None
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1293343003 .

Restore function-local variables to use a vector.

CL 1282523002 changed the bitcode parser from using a vector, to using
an unordered map. This was done because one could forward reference a
local variable, and would freeze the computer trying to allocate a
vector large enough to contain the index.

This patch goes back to using vectors. To fix the forward variable
reference, we use the number of bytes in the function to determine if
the index is possible. This stops very large (probematic) vector
resizes from happening.

BUG=None
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1293923002 .

Change tracking of basic blocks (within function) to use a vector.

Changing the code to "preallocate" basic blocks in a vector, rather
than dynamically creating on demand. This has the advantage of not
requiring basic blocks to be sorted after the bitcode is parsed.

This also means that the name of the basic blocks remain constant,
even during parsing, making debugging easier.

The drawback is that the DECLAREBLOCKS bitcode record of a function
block can define a very large number of basic blocks. To control this,
we look at the function block size (within the bitstream) to determine
the maximal number of basic blocks that could be defined. If the
DECLAREBLOCKS record specifies a number larger than this, we generate
an error and recover (if applicable).

We also add an cleanup test that confirms the number of declared basic
blocks correspond to the number of basic blocks defined in the
function.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4261
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1297433002 .

Subzero. Native 64-bit int arithmetic on x86-64.

This CL modifies the x86 instruction selection template to allow native
64-bit GPR support. It also enables x86-64 crosstests.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4077
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1273153002.

Remove error-recovery TODO comments from bitcode parser.

The bitcode parser contained a number of TODO commments about
removing error recovery once the parser was implemented. This
was based on the fact that (1) pnacl-sz in the browser didn't
need it, and (2) it would be trivial to remove.

The advantage of leaving error recovery in is that multiple errors can
be found at once.

It turns out it isn't so easy to remove, since several methods assume
that recovery can be applied, and hence do not need propagate back up
an (optional) error code. Parsing backs out relatively quickly anyway,
since the code exits between bitcode records anyway.

BUG=None
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1286513002 .

Subzero: Misc fixes/cleanup.

1. Fix MINIMAL build.
  (a) Add a void cast to a var only used in asserts.
  (b) Use "REQUIRES:" instead of "REQUIRES" in a .ll file.
2. Use StrError instead of StrDump for errors.
3. Use a lambda instead of a functor because C++11.
4. Explicit check for -filetype=obj in a non-dump-enabled build, to avoid cryptic downstream error messages.
5. Run "make format" which was neglected earlier.

BUG= none
R=kschimpf@google.com

Review URL: https://codereview.chromium.org/1284493003.

Fix processing of local variable indices in fuction blocks.

The previous code used a vector to hold local values associated with
indices in the bitcode file. The problem was that the vector would be
expanded to match the index of a "variable index forward reference".
If the index was very large, the program would freeze the computer
trying to allocate an array large enough to contain the index.

This patch fixes this by using a local unordered map instead of a
vector.  Hence, forward index references just add a sinle entry into
the map.

Note that this fix doesn't have a corresponding issue. However, the
problem was made apparent from the problems noted in issues 4257 and
4261.

BUG=None
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1282523002 .

Add the ARM32 FP register table entries, simple arith, and args.

Lower some instructions, without much guarantee of
correctness. *Running* generated code will be risky
because the register allocator isn't aware of register
aliasing.

Fill in v{add,div,mul,sub}.f{32,64}, vmov, vldr
and vsqrt.f{32,64}. I tried to make the nacl-other-intrinsics
test not explode, so added vsqrt too. That was pretty
easy for sqrt, but then fabs tests also exploded. Those are not
truly fixed but are currently "fixed" by adding a FakeDef to
satisfy liveness.

Propagate float/double arguments to the right register
in lowerArguments, lowerCall, and propagate to s0/d0/q0
for lowerReturn. May need to double check the calling convention.
Currently can't test call-ret because vpush/vpop for prologues
and epilogues isn't done.

Legalize FP immediates to make the nacl-other-intrinsics sqrt
test happy. Use the correct type of load (vldr (.32 and .64 are
optional) instead of ldr{b,h,,d}).

Whether or not the float/vector instructions can be
predicated is a bit interesting. The float/double ones
can, but the SIMD versions cannot. E.g.

vadd<cond>.f32 s0, s0, s1 is okay
vadd<cond>.f32 q0, q0, q1 is not okay.

For now, just omit conditions from instructions that may
end up being reused for SIMD.

Split up the fp.pnacl.ll test into multiple ones so that
parts of lowering can be tested incrementally.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4076
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1266263003 .

Subzero: Fix a memory leak.

The problem was that Translator and subclasses need to have virtual destructors since they are used as unique_ptr<>.  As a result, only the Translator base class destructor was being invoked.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4290
TEST= make -f Makefile.standalone ASAN=1 check-lit
R=ascull@google.com

Review URL: https://codereview.chromium.org/1281003003.

Fix processing of global variable indices in the global vars block.

The code used to use a vector to hold global variables associated with
indices. The problem was that the count record in the global vars
block would generate variables for the given count (even if very
large).

To fix this, we created a local unordered map to associate indices
with defined/referenced globals. After processing the global vars
block, this unordered map is used to verify the size makes sense, and
then install the recognized global variables into the (top-level)
contents.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4257
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1278793006 .

Inline memcpy for small constant sizes.

Combined with memset inlining, this has shown an improvement of over 11% on
the eon benchmark. This the only C++ program in spec2k and it seems C++
programs have a significantly larger number of memset/memcpy calls. Other
benchmarks also showed improvement of ~5% (perlbmk, parser) while most had
a 1-2% improvement.

This commit also includes a refactoring of lowerMemset which is much more
readable and also removed the fake use of the destination pointer register.

BUG=
R=jvoung@chromium.org, stichnot@chromium.org

Review URL: https://codereview.chromium.org/1279833005.

Subzero: Completely remove tracking of stack pointer live range.

Specifically, if a variable is marked with IgnoreLiveness=true, then:
  1. Completely avoid adding any segments to its live range
  2. Assert that no one tries to add segments to its live range

This is done in part by incorporating Variable::IgnoreLiveness into Liveness::RangeMask.

Also, change a functor into a lambda because C++11.

BUG= none
R=jvoung@chromium.org

Review URL: https://codereview.chromium.org/1273823003.

Subzero: Fix szbuild.py linking.

The symbol __Sz_block_profile_info needs to be explicitly globalized when combining llc and Subzero .o output, i.e. when the --include or --exclude options are used.

BUG= none
R=jpp@chromium.org

Review URL: https://codereview.chromium.org/1275983003.

Fix translator handling of basic block indices.

The code used to use a vector to hold basic blocks associated with
indices. This had two problem: 1) The "number of blocks" record would
generate a vector of the given size (even if very large); and 2)
Indices would expand the vector to define the index (even if very
large).

In most cases, such large values are incorrect. To fix this, this
patch uses a map from block index, to the corresponding basic block.
Only after all basic block indices have been processed, we check that
the size makes sense, and convert it to a vector.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4261
R=jpp@chromium.org, stichnot@chromium.org

Review URL: https://codereview.chromium.org/1275953002 .

Introduce the ability to insert IACA (Intel Architecture Code Analyzer) marks.

The IACI marks identify the code which should be analyzed with the IACA.

The generated binaries are not executable due to the marks. This feature should
only be used during develpoment when analyzing generated code so it is protected
behind the --allow-iaca-marks flag.

ScopedIacaMark is a helper class which opens mark and closes it at the end of
the scope. This is useful when there are many returns as you don't have to write
`_iaca_end()` before them all.

BUG=
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1260093003.

Subzero. Moves code around in preparations for 64-bit lowering.

Specifically, it moves

lowerArguments
lowerRet
addProlog
addEpilog

from the x86 lowering template to the concrete lowering implementations.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4077
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1261383002.

Subzero: Fix an Om1 crash from memset lowering.

With a certain combination of memset arguments, legalizeToReg() is called but its result is unused.  Om1 register allocation does not like this because it sees an infinite-weight variable with a definition but no uses.  The simplest fix is to add a fake use.

The problem shows up when building spec2k with -Om1.

BUG= none
R=ascull@google.com

Review URL: https://codereview.chromium.org/1272823004.

Subzero: Slight improvement to phi lowering.

When doing post phi lowering register allocation, the original code limited register allocation to pre-colored or infinite-weight variables with a non-empty live range within the new edge-split nodes.  This limitation ends up missing some opportunities.  Specifically, when a temporary is introduced to break a dependency cycle, e.g.:
  // a = phi(b)
  // b = phi(a)
  t = a
  a = b
  b = t
then t was always stack-allocated, even if a physical register was available.

In the new design, the RangeMask bitvector specifies which variables should have their live ranges tracked and computed.  For normal liveness analysis, all variables are tracked.  For post phi lowering liveness analysis, all variables created from phi lowering, plus all pre-colored variables, plus all infinite-weight variables, are tracked.

The result is slightly better code quality, and sometimes the frame size is 1 or 2 words smaller.

The hope was to narrow the 10% translation-time degradation in pnacl-llc.pexe compared to the old, hackish way of phi lowering, but that goal still proves to be elusive.

BUG= none
R=jvoung@chromium.org

Review URL: https://codereview.chromium.org/1271923002.

Subzero. Implements x86-64 lowerCall.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4077
R=jvoung@chromium.org, stichnot@chromium.org

Review URL: https://codereview.chromium.org/1266673003.

Clarify which type "Label" refers to (generic vs X86)

There is a generic Label that can be used as-is for ARM
and MIPS, and there is an x86 derived class Label which
adds the concept of near and far (for 8-bit vs 32-bit
jumps). Previously, one method "getOrCreateCfgNodeLabel"
would say that it returns a Label when it means the generic
one in some cases and the x86 one in other cases.

Split that into getCfgNodeLabel and getOrCreateCfgNodeLabel
where getCfgNodeLabel returns the generic one and
getOrCreateCfgNodeLabel is part of the x86 code and
returns the x86 one.

BUG=none
R=ascull@google.com, stichnot@chromium.org

Review URL: https://codereview.chromium.org/1265023003 .

Order jump tables for deterministic or randomized emission.

BUG=
R=stichnot@chromium.org, jvoung, stichnot

Review URL: https://codereview.chromium.org/1260183008.

Subzero: Fix x86 lowering for shift-by-relocatable-constant.

Trying to shift by a ConstantRelocatable causes an assertion failure in the integrated assembler, because the shift value must be Imm8.  Maybe this is possible to express via ELF relocations, but it doesn't seem worth it.  Especially since ConstantRelocatables refer to addresses and it doesn't make sense to shift by an address.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4256
R=jvoung@chromium.org, kschimpf@google.com

Review URL: https://codereview.chromium.org/1262003003.

Inline memset when there is a constant value and count.

BUG=
R=jvoung@chromium.org, jvoung, stichnot

Review URL: https://codereview.chromium.org/1255053008.

Subzero: Expand the liveness consistency check.

Liveness analysis includes a consistency check on each node, to verify that variables referenced in only one block do not appear to be live coming into a block (and are therefore live across multiple blocks).  This check was disabled in the entry block because there might be function arguments that are referenced only in the entry block but are still live coming in.

It seems that this entry-block exclusion has been largely unnecessary for some time.  This is because input arguments and other special variables are now pre-marked as multi-block.  The exclusion masks problems in some single-block lit tests, so it's best if it can be removed.

This CL removes the exclusion, and fixes some minor issues uncovered in the MIPS and ARM target lowering.  A key issue is that when implementing a new target lowering and using --skip-unimplemented to make progress with existing tests, it may be necessary to add FakeDef instructions to avoid liveness inconsistency errors.

Note that when this patch is applied to 448c16f0f6905460a3d27e728ed0f14a1c08ff69, it correctly identifies the liveness consistency error (as shown by a "make check-lit" failure) that was fixed in 59f2d925252faa7ae7cc688cfdfcf7c4a6f62cce.

BUG= none
R=jpp@chromium.org

Review URL: https://codereview.chromium.org/1265093002.

Subzero. Buildable, non-functional TargetLoweringX8664.

This CL adds a TargetLoweringX8664 that inherits from TargetX86Base, but
other than that it does nothing to generate runnable code.

Things that need to be addressed in follow up CLs:
1) lowerCall
2) lowerArguments
3) lowerRet
4) addPrologue
5) addEpilogue
6) Native 64-bit arithmetic
7) 32- to 64-bit addressing

(7) will be particularly interesting. Pointers in Pexes are always
32-bit wide, so pexes have a de facto 32-bit address space. In
Sandboxed mode that's solved by using RZP (i.e., r15) as a base
register. For native codegen, we still need to decide what to do
-- very likely we will start targeting X32.

NOTE: This CL also

s/IceType_ForceRexW/RexTypeForceRexW/g

because I forgot to do it in the X8664 assembler cl.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4077
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1257643004.

Subzero. Misc fixes.

This CL disables the X86 assembler tests by default. They take too long
to compile, so there's very little point in running them with the other
unittests.

This CL fixes a bug introduced in
https://codereview.chromium.org/1260163003/ that caused liveness
analysis to assert due to a uninitialized Variable.

BUG=
R=jvoung@chromium.org, stichnot@chromium.org

Review URL: https://codereview.chromium.org/1266863002.

ARM: Add a postRA pass to legalize stack offsets. Greedy approach (reserve IP).

Make a post-register allocation and post-addProlog pass to
go through variables with stack offsets and legalize them
in case the offsets are not encodeable. The naive approach
is to reserve IP, and use IP to movw/movt the offset, then
add/sub the frame/stack pointer to IP and use IP as the new
base instead of the frame/stack pointer. We do some amount
of CSE within a basic block, and share the IP base pointer
when it is (a) within range for later stack references,
and (b) IP hasn't been clobbered (e.g., by a function call).
I chose to do this greedy approach for both Om1 and O2,
since it should just be a linear pass, and it reduces the
amount of variables/instructions created compared to the
super-naive peephole approach (so might be faster?).

Introduce a test-only flag and use that to artificially
bloat the stack frame so that spill offsets are out
of range for ARM. Use that flag for cross tests to
stress this new code a bit more (than would have been
stressed by simply doing a lit test + FileCheck).

Also, the previous version of emitVariable() was using the
Var's type to determine the range (only +/- 255 for i16,
vs +/- 4095 for i32), even though mov's emit() always
uses a full 32-bit "ldr" instead of a 16-bit "ldrh".
Use a common legality check, which uses the stackSlotType
instead of the Var's type. This previously caused the
test_bitmanip to spuriously complain, even though the
offsets for Om1 were "only" in the 300 byte range. With this
fixed, we can then enable the test_bitmanip test too.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4076
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1241763002 .

Add -reorder-basic-blocks option and fix nop insertion

1. Basic block reordering can be enabled with -reorder-basic-blocks option enabled.

Blocks will be sorted according to the Reversed Post Traversal Order, but the next
node to visit among all candidate children nodes is selected 'randomly'.

Example:
  A
 / \
B   C
 \ /
  D

This CFG can generate two possible layouts:
A-B-C-D or A-C-B-D

2. Fix nop insetion

Add checks to avoiding insertions in empty basic blocks(dead blocks) and bundle locked instructions.

BUG=
R=jpp@chromium.org, jvoung@chromium.org, stichnot@chromium.org

Review URL: https://codereview.chromium.org/1255303004.

Fix a -Wcovered-switch-default warning in emitJumpTables.

The Subzero build inside of the LLVM build system turns this on.

BUG=none
R=ascull@google.com

Review URL: https://codereview.chromium.org/1264913005 .

Iasm and obj lowering for advanced switch lowering.

Jump table emission is delayed until offsets are known. X86 local jumps can be
near or far. Sanboxing is applied to indirect jumps from jump table.

BUG=
R=stichnot@chromium.org, jvoung

Review URL: https://codereview.chromium.org/1257283004.

Subzero: Cleanly implement register allocation after phi lowering.

After finding a valid linearization of phi assignments, the old approach calls a complicated target-specific method that lowers and ad-hoc register allocates the phi assignments.

In the new approach, we use existing target lowering to lower assignments into mov/whatever instructions, and enhance the register allocator to be able to forcibly spill and reload a register if one is needed but none are available.

The new approach incrementally updates liveness and live ranges for newly added nodes and variable uses, to avoid having to expensively recompute it all.

Advanced phi lowering is enabled now on ARM, and constant blinding no longer needs to be disabled during phi lowering.

Some of the metadata regarding which CfgNode a local variable belongs to, needed to be made non-const, in order to add spill/fill instructions to a CfgNode during register allocation.

Most of the testing came from spec2k.  There are some minor differences in the output regarding stack frame offsets, probably related to the order that new nodes are phi-lowered.  The changes related to constant blinding were tested by running spec with "-randomize-pool-immediates=randomize -randomize-pool-threshold=8".

Unfortunately, this appears to add about 10% to the translation time for 176.gcc.  The cost is clear in the -timing output so it can be investigated later.  There is a TODO suggesting the possible cause and solution, for later investigation.

BUG= none
R=jvoung@chromium.org

Review URL: https://codereview.chromium.org/1253833002.

Removes references to ah.

AH is a thorn in the flesh for our X86-64 backend. The assembler was
designed to always encode the low 8-bit registers, so %ah would become
%spl. While it is true we **could** force %spl to always be encoded as
%ah, that would not work if the instruction has a rex prefix.

This CL removes references to %ah from TargetX86Base. There used to be
2 uses of ah in the target lowering:

1) To zero-extend %al before an unsigned div:
    mov <<src0>>, %al
    mov 0, %ah
    div <<src1>>

This pattern has been changed to
    xor %eax, %eax
    mov <<src0>>, %al
    div <<src1>>

2) To access the 8-bit remainder for 8-bit division:
    mov %ah, <<dest>>

This pattern has been changed to
    shr $8, %eax
    mov %al, <<Dest>>

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4077
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1260163003.

Adds the x86-64 assembler.

As part of this CL, x86-32 assembler tests are also introduced. They were implemented before the x86 base assembler template was modified for x86-64 support.

BUG=https://code.google.com/p/nativeclient/issues/detail?id=4077
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1224173006.

Handle UINT64_MAX edge case in switch lowering.

BUG=
R=jvoung@chromium.org, jvoung

Review URL: https://codereview.chromium.org/1247833003.

Avoid heap allocation for binary search work stack.

During switch lowering a binary search tree is created. The height of this
tree is usually small so no need for heap allocation.

BUG=
R=jvoung@chromium.org, jvoung, stichnot

Review URL: https://codereview.chromium.org/1240323005.

Modify how textual bitcode is injected into pnacl-sz.

Added command line flag "--bitcode-as-text", and triggered
the acceptance of textual bitcode on this flag. To make sure
this isn't added to the sandboxed translator, the reading of
bitcode text is also dependent on the translator not being a
minimal build.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4222
R=jvoung@chromium.org, stichnot@chromium.org

Review URL: https://codereview.chromium.org/1215463014 .

Remove jumps over empty blocks.

After contracting a node reorder it as unreachable even if it
hasn't yet been placed.

BUG=
R=jvoung@chromium.org, jvoung, stichnot

Review URL: https://codereview.chromium.org/1246173003.

Make ARM RegNames[] static like X86 (no ARM syms in X86-only build).

The X86 code was switch out here:
https://codereview.chromium.org/1216933015/diff/150001/src/IceTargetLoweringX86Base.h

The important bit might be that it's static const char * instead of
static IceString. This removes static ctor/dtor for that array,
which LTO doesn't seem to be able to optimize out, leaving ARM
and MIPS symbols in the X86-only build. After changing it to static
const char *, LTO is able to optimize out the ARM and MIPS
symbols in the x86-only build, saving about 3KB of .text and
few bytes of .rodata.

BUG=none
R=jpp@chromium.org

Review URL: https://codereview.chromium.org/1246013004 .

Changes the TargetX8632 to inherit from TargetX86Base<TargetX8632>.

Previously, TargetX8632 was defined as

class TargetX8632 : public TargetLowering;

and its create method would do

TargetX8632 *TargetX8632::create() {
  return TargetX86Base<TargetX8632>::create()
}

TargetX86Base<M> was defined was

template <class M> class TargetX86Base : public M;

which meant TargetX8632 had no way to access methods defined in
TargetX86Base<M>. This used to not be a problem, but with the X8664
backend around the corner it became obvious that the actual TargetX86
targets (e.g., X8632. X8664SysV, X8664Win) would need access to some
methods in TargetX86Base (e.g., _mov, _fld, _fstp etc.)

This CL changes the class hierarchy to something like

TargetLowering <-- TargetX86Base<X8632> <-- X8632
               <-- TargetX86Base<X8664SysV> <-- X8664SysV (TODO)
               <-- TargetX86Base<X8664Win> <-- X8664Win (TODO)

One problem with this new design is that TargetX86Base<M> needs to be
able to invoke methods in the actual backends. For example, each
backend will have its own way of lowering llvm.nacl.read.tp. This
creates a chicken/egg problem that is solved with (you guessed)
template machinery (some would call it voodoo.)

In this CL, as a proof of concept, we introduce the

   TargetX86Base::dispatchToConcrete

template method. It is a very simple method: it downcasts "this" from
the template base class (TargetX86Base<TargetX8664>) to the actual
(concrete) class (TargetX8632), and then it invokes the requested
method. It uses perfect forwarding for passing arguments to the method
being invoked, and returns whatever that method returns.

A simple proof-of-concept for using dispatchToConcrete is introduced
with this CL: it is used to invoke createNaClReadTPSrcOperand on the
concrete target class. In a way, dispatchToConcrete is a poor man's
virtual method call, without the virtual method call overhead.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4077
R=jvoung@chromium.org, stichnot@chromium.org

Review URL: https://codereview.chromium.org/1217443024.

Only run adv-switch test when asm is allowed.

BUG=
R=stichnot@chromium.org, jvoung@chromium.org

Review URL: https://codereview.chromium.org/1248823003.

Rename legalizeToVar to the more accurate legalizeToReg.

BUG=
R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1245063003.

Fix --filetype=iasm non-pc-rel fixup offsets (double counted).

For pc-rel fixups, we have a ConstantRelocatable referring
to Foo+0, and and the offset "-4" is encoded in the code
buffer (but not the ConstantRelocatable object). Thus we
need to load from the code buffer in order to
get that "-4" instead of just taking the +0 from Foo+0.

For non-pc-rel fixups, we have the ConstantRelocatable
with a true offset, and we also write that offset into the
code buffer (for ELF REL and not RELA, it expects the
offset in the code buffer). In this case, we want to choose
one and not double-count.

BUG=none
176.gcc seemed to be failing when compiled with --filetype=iasm...
load address for 64-bit pointers were +8 instead of +4

R=stichnot@chromium.org

Review URL: https://codereview.chromium.org/1241313002 .