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 .

Introduction of improved switch lowering.

This includes the high level analysis of switches, the x86 lowering,
the repointing of targets in jump tables and ASM emission of jump
tables.

The technique uses jump tables, range test and binary search with
worst case O(lg n) which improves the previous worst case of O(n)
from a sequential search.

Use is hidden by the --adv-switch flag as the IAS emission still
needs to be implemented.

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

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

Factor out prelowerPhi for 32-bit targets. Disable adv phi lowering for ARM.

This way, prelowerPhi can be shared between 32-bit targets (split 64-bit
values into 32-bit ones, and legalize undef). Suggestions from template
experts on how to share prelowerPhi welcome. I'm not particularly happy
with the first pass in that legalizeUndef has to be made public (though
other methods used are also public). Also the methods required from the
template type TargetT aren't clear without looking through the code.

The current advanced phi lowering code depends on lowerPhiAssignments.
That is a special case of lowerAssign that does some adhoc register
allocation. The current adhoc register allocation doesn't work as
well when a target may need to spill more than one register.
Disable that optimization for ARM for now, until we have a better
way that works for ARM, and enable O2 cross testing on ARM.

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

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

Factor out legalization of undef, and handle more cases for ARM.

By factoring out legalizeUndef(), we can use the same
logic in prelowerPhis which may help if we ever change the
value used (though if we switch from zero-ing out regs to
using uninitialized regs, it'll take more work -- e.g.,
can't return a 64-bit reg).

For x86, use legalizeUndef where it's clear that the value
is immediately fed to loOperand/hiOperand then another
legalize() call. Otherwise, leave the general
X = legalize(X); alone where the code is counting on that
being the sole legalization.

For x86 legalize(const64) is a pass-through, which can then
be passed to loOperand/hiOperand nicely. However, for ARM,
legalize(const64) may end up trying to copy the const64 to
a register, but we don't have 64-bit registers. Instead do
legalizeUndef(X) where x86 would have just done
legalize(X). This happens to work because legalizeUndef
doesn't try to copy to reg, and we immediately pass the
result to loOperand/hiOperand() which then passes the
result to a real legalization call.

Add a few more undef tests.

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

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

Subzero: Fix register encodings.

Specifically, we were ending up with Encoded_Reg_xmm0=0 yet Encoded_Reg_xmm1=10, Encoded_Reg_xmm2=11, etc.

It's a mystery as to why this wasn't triggering any failures with filetype!=asm.

BUG= none
R=jpp@chromium.org

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

Add an cross include path for ARM to work around clang bug 22937.

Clang appears to be missing an include path to find
bits/c++config.h so we were unable to compile the
unsandboxed c++ based cross tests and link against the
subzero unsandboxed ARM object files.

Work around this for now by finding and including the
missing path.

Turn on a few ARM cross tests that should be working
(mem_intrin and test_strengthreduce -- though the
strength-reduction isn't done for ARM). The test_bitmanip
still fails, because under Om1 we overflow the stack offset
and need to materialize that offset with a register first.

Update a few other references that still say x8632.

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

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

Adds basic tests to the AssemblerX8632.

More tests will be added during the AssemblerX8664 (on a separate CL.)

BUG=
R=jvoung@chromium.org

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

Change MIPS to avoid "none-nacl" for unsandboxed tests.

This changes the run-pnacl-sz script to be more consistent
with the other targets.

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

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

Patch from Reed Kotler <reed.kotler@imgtec.com>.

ARM32: Lower more integer intrinsics and test.

Lower stacksave/restore.
Lower ctlz, cttz, bswap, and popcount. Popcount is just
done with a helper call. Ctz can use the clz instruction
after reversing the bits.

We can only crosstest stacksave/restore for now which
happens to be written in C for the C99 VLAs. The CXX
crosstests I can't seem to compile with the arm-cross-g++
(missing headers), so I will check that later after
resolving the cross compilation issue.

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

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

Followup to previous MIPS commit: implement dump(), rebase more.

When compiling with DEBUG, there is a problem linking
InstMIPS32. It overrides dump, but never defined that.

Also, update the code for some recent changes.  Namely, we
no longer check ALLOW_DUMP but instead check
BuildDefs::dump().  Also, the instruction dtors have been
deleted.

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

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

implement the null function for the Mips32 subzero compiler

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

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

Patch from Reed Kotler <reed.kotler@imgtec.com>.

X8632 Templatization completed.

This CL introduces the X86Inst templates. The previous implementation relied on template specialization which did not played nice with the new design. This required a lot of other boilerplate code (i.e., tons of new named constructors, one for each X86Inst.)

This CL also moves X8632 code out of the X86Base{Impl}?.h files so that they are **almost** target agnostic. As we move to adding other X86 targets more methods will be moved to the target-specific trait class (e.g., call/ret/argument lowering.)

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

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

Redelete IceAssemblerX8632.cpp

Accidentally resurrected during rebase when it shouldn't have been.

BUG=
R=jvoung@chromium.org

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

Doxygenize the documentation comments

There were many // comment used to document classes, functions etc. but
those are not picked up by doxygen which expects /// comments. This
converts many comments from // to /// in order to improve the generated
documentation.

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

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

Fix ARM Om1 lowering for arithmetic, and test.

The original arithmetic lowering was introducing some
unused mov instructions from legalization (e.g., the upper
part of shift num bits -- which should be 0 anyway), and
div helper calls don't actually use the legalized
parameters (handled separately by lowerCall). These unused
instructions cause the Om1 allocator to assert that LRBegin
exists but LREnd does not.

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

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

Move X8632-specific Assembler stuff to Machine Traits.

As part of the refactoring moves the MachineTraits<TargetX8632> to a separate header.

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

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

Fix invalid tests to not run when minimal.

Deals with fact that minimal builds generate simple "generic" error
messages, rather than descriptive error messages.

BUG=None
R=stichnot@chromium.org

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

Small fixes for unused argument warnings w/ Makefile.standalone "sb" target.

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

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

ARM lowering integer divide and remainder, with div by 0 checks.

ARM normally just returns 0 when dividing by 0 with the
software and hw implementations, which is different from
what X86 does. So, for NaCl, we've modified LLVM to trap
by inserting explicit 0 checks.

Uses -mattr=hwdiv-arm attribute to decide if 32-bit
sdiv/udiv are supported.

Also lower the unreachable-inst to a trap-inst, since we
need a trap instruction for divide by 0 anyway.

Misc: fix switch test under MINIMAL=1, since ARM requires
allow_dump for filetype=asm.
Random clang-format changes...

TODO: check via cross tests

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

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

Fixes case where terminator instruction is missing at end of function.

If the bitcode parser detects that the last block in the function
is missing a terminator, generate an error message and insert
a terminator instruction.

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

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

ARM: lowerSelect for integers.

No bool-folding optimization, just the straightforward
compare followed by mov and conditional mov.

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

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

Implement ARM32 switch lowering.

A naive implementation of switch lowering using sequential tests for each of the cases.

BUG= none
TEST=switch-opt.ll
R=jvoung@chromium.org

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

Add doxygen build target.

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

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

Enables llvm dyn_cast for Assemblers.

IceCfg::getAssembler() is a template that simply static_casts the CFG's assembler. This could potentially be problematic in the future, so we enabled the (relatively) cheap llvm dyn_cast operator for Assemblers.

This CL also renames assembler_mips32.h to IceAssemblerMIPS32.h.

BUG=
R=stichnot@chromium.org

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

Subzero: Fix a new test under MINIMAL mode.

It tests dump output and therefore requires allow_dump.

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

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

Subzero: Enable errors for unused parameters.

Uses pragmas when including problematic LLVM headers, so that clang
doesn't warn about unused parameters -- a rampant problem in the LLVM
code.  This way, we can increase clang's pickiness on Subzero code,
and also not drown in LLVM warnings.

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

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

Adds X8664 Condition codes.

Also fixes the X8664 Registers file.

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

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

Adds the X8664 register definition.

BUG=
R=stichnot@chromium.org

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

Fixes bug on conditional branch where the targets are the same.

Fixes constructor InstBr when it is a conditional branch, and the
true and false branches are the same.

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

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

Function Layout, Global Variable Layout and Pooled Constants Layout Reordering

PURPOSE:
The purpose of function layout reordering is to defend against code-reuse attacks as the location of code blocks will be various among different binaries. The layout reordering for global variables and pooled constants can be considered as static data randomization. This is to stop memory corruption attacks by randomizing the locations of the static data. After function layout reordering, the order of function blocks in TEXT section will be randomized. Global variable reordering randomize the order of global variables, and pooled constant reordering randomize the order of pooled constants. Note the order of constant pools won’t be affected and all pooled constants will remain in their original constant pools.

USAGE:
-reorder-functions: bool type command line option, enables function layout shuffling in TEXT section. Note when -threads=0 is set, function reordering will be forced off.

-reorder-functions-window-size: uint32 type command line option, specify the length of the shuffling queue. Note -reorder-functions-window-size=0 or 1 means no shuffling applied to functions.

-reorder-global-variables: bool type command line option, enables global variables shuffling.

-reorder-pooled-constants: bool type command line option, enables pooled constants shuffling.

APPROACH:
Randomization is introduced at the code emission time. We use a shuffling method to randomize the emission of function code, global variables and pooled constants. For function code emission, we also introduce “window size” as a parameter to control the size of the function holding buffer for shuffling. Window size 1 and 0 mean no shuffling applied, and a value higher than the number of translated functions means holding all the functions and shuffling them before emitting any of them.

IMPLEMENTATION:
    Function reordering:
        GlobalContext::emitItems(): Call RandomShuffle() routine to shuffle a specific part of the Pending vector.

    Global variable reorder:
        GlobalContext::lowerGlobals(const IceString &SectionSuffix): Call RandomShuffle() routine upon declaration list: Globals.

    Pooled constant reordering:
        TargetDataX8632::emitConstantPool(GlobalContext *Ctx): Add call to RandomShuffle() to shuffle the constant pool to be emitted. This is for asm output.

        ELFObjectWriter::writeConstantPool(Type Tu): Add call to RandomShuffle() to shuffle the constant pool before emitting it. This is only for elf output.

ISSUES:
    The initialization of global variables are emitted along with function code, all of them are considered as EmitterWorkItem. However, we do need to first emit global variables to keep the block profiling workflow untouched. To fulfill this, a “kind” check is added in the while loop of GlobalContext::emitItems(). The “if” statement at line 480 shows the workaround of this issue.
BUG=
R=jpp@chromium.org, jvoung@chromium.org, stichnot@chromium.org

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

Includes module header first.

This "include module header first" is part of the llvm style guide.

This change exposes "broken" headers that were accessing undefined types, or
even using types without forward declaring them.

BUG=
R=stichnot@chromium.org

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

Subzero: Fix cmake build.

Also fixes a set of warnings that only show up for the cmake build.

BUG= none
R=jpp@chromium.org

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

Fixes the X86 Base template.

It turns out that using using TargetLowering::<member> causes problems when compiling with g++. The problem was fixed by using
Machine:: instead, where Machine is the template parameter. With name-dependent identifier, g++ does the right thing.

BUG= None
R=stichnot@chromium.org

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

Subzero: Reduce the amount of #ifdef'd code.

Try to make most #ifdef'd code be compiled under all configurations,
to catch code rot earlier.  When #ifdef code is required, try to use
it only to guard trivial code like "return;".

BUG= none
R=jpp@chromium.org

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

Remove unnecessary TEXTBC_LIBS makefile definition.

Jan correctly pointed out that this makefie definition was redundant
since -lLLVMNaClBitTestUtils was already defined in LLVM_LIBS_LIST.
Removing the definition and simplifying makefile.

BUG=None
R=jpp@chromium.org

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

Subzero. Adds x86-64 to the list of supported Subzero targets.

Related changes:
NaCl change: https://codereview.chromium.org/1201483005
LLVM change: https://codereview.chromium.org/1193843016

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

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

Subzero: Make life a little easier for emacs users.

Emacs will try to execute .dir-locals.el whenever loading a file under
the subzero directory.  It sets local variables depending on the mode.

Set the fill-column to 80 for c++-mode, c-mode, and python-mode.  The
main use is when using M-q to reformat multi-line comments.

Disable tabs (use spaces instead) in c++-mode, c-mode, and
python-mode.

Set the tab-width to 2 spaces in python-mode.  (The tab-width doesn't
really matter in c++-mode or c-mode thanks to clang-format.)

BUG= none
R=kschimpf@google.com

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

Fix handling of TYPE_CODE_NUMENTRY record when size large.

Fixes how (very) large size entries in the TYPE_CODE_NUMENTRY is
handled when reading bitcode. Makes sure that we con't call
vector.resize() with too large a value (replacing an allocation
exception with a parse error).

Also tries to clean up type modeling of bitcode indices (references to
values etc in the bitcode). Uses common type NaClBcIndexSize_t and
NaClRelBcIndexSize_t (defined in nacl) to describe these (32-bit)
values.

Note: We use cast truncation of 64-bit values to NaClBcIndexSize_t and
NaClRelBcIndexSize_t, since negative value indices are stored both as
32 and 64 bit values. The truncation cast handles this differences
correctly (and efficiently).

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

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

Extracts an TargetX86Base target which will be used as the common X86{32,64} implementation.

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

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

Subzero: Use more "= default;" for ctors and dtors.

Look for "() override {}" and "() final {}" patterns.

Don't touch IceTargetLoweringX8632.* to spare a refactoring in
progress.

BUG= none
R=jpp@chromium.org

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

Fix llvm makefile to handle macro INPUT_IS_TEXTUAL_BITCODE.

BUG=None
R=stichnot@chromium.org

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

Allow pnacl-sz to be compiled to textual bitcode records.

This has been added to allow fuzzing to be applied to textual bitcode
records. When built with make option TEXTUAL_BITCODE=1, the
corresponding generated pnacl-sz will preprocess the input file
(containing the textual form of bitcode records) and generate
a corresponding data stream with the binary form.

Note that the texual form of bitcode records is not LLVM assembly
(i.e. .ll files). Rather, it is sequences of texual integers
corresponding to bitcode records.

Dependent on: https://codereview.chromium.org/1191393004

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

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