This is limited to the src directory, and not (yet) the crosstest directory.

BUG= none
R=jfb@chromium.org

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

In particular, node lists for in and out edges of a CfgNode, and the live range segment list in a Variable.  This is done by making the Cfg allocator globally available through TLS, and providing the STL containers with an allocator struct that uses this.

This also cleans up some other allocation-related issues:

* The allocator is now hung off the Cfg via a pointer, rather than being embedded into the Cfg.  This allows a const Cfg pointer to be stored in TLS while still allowing its allocator to be mutated.

* Cfg is now created via a static create() method.

* The redundant Cfg::allocateInst<> methods are removed.

* The Variable::asType() method allocates a whole new Variable from the Cfg arena, rather than allocating it on the stack, removing the need for the move constructor in Variable and Operand.  This is OK since asType() is only used for textual asm emission.

* The same 1MB arena allocator is now used by the assembler as well.  The fact that it wasn't changed over to be the same as Cfg and GlobalContext was an oversight.  (It turns out this adds ~3MB to the translator memory footprint, so that could be tuned later.)

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

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

Randomize the order that registers appear in the free list.  Only
randomize fully "equivalent" registers to ensure no extra spills.

This adds the -randomize-regalloc option.

This is a continuation of https://codereview.chromium.org/456033003/ which Matt owns.

BUG= none
R=jfb@chromium.org

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

Removes the need to model LLVM types from the minimal subzero build.
It isn't removed from the nonminimal build because IceConverter still needs
to be able to convert LLVM types to corresponding Ice types.

Note that this CL reduces the size of Release+Min/llvm2ice (after
strip) to about 638K bytes.

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

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

Removes cast instruction checks (in PNaClTranslator.cpp) that used
LLVM utilities to use locally defined methods instead. Remove the need
to call naclbitc::DecodeCastOpcode and CastInst::castIsValid.

Also removes two more calls to convertToLLVMType.

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

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

Moves the deletion of newly dead instructions into the main liveness() routine.  The old livenessPostProcess() routine is renamed and now used purely for live range construction.

The hack is removed in which live in-args have a custom live range segment added to avoid an artifact of the live ranges.  It is replaced with a gentler hack that extends the instruction numbering range of the initial basic block to avoid the artifact.

Since special live range segments no longer need to be prepended, the live range representation is simplified and we can always assume that segments are being appended, never prepended (and as before, never added to the middle).

Some magic constants involving special instruction numbers are replaced with symbolic constants.

BUG= none
R=jvoung@chromium.org

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

In Subzero, we only need to be able to convert 64 bit constants in
bitcode files to the corresponding Ice integer or floating type. This
CL extracts the minimal implementation needed for Subzero. The intent
of this change is to remove loading unnecessary LLVM code into
(minimal) llvm2ice.

BUG=None
R=stichnot@chromium.org

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

Instead, extend 668a7a33 to include both CfgNode and Variable, keeping a pool of strings in the Cfg.

BUG= none
R=jvoung@chromium.org

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

Requires the LLVM option -track-memory to get meaningful results.

BUG= none
R=kschimpf@google.com

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

This is toward the goal of pulling non-POD fields out of the CfgNode
class so that CfgNode can be arena-allocated and not leak memory.

For now, PhiList and AssignList are defined as InstList.  Ideally,
they would be ilist<> of InstPhi and InstAssign, but SFINAE happens.

BUG= none
R=jvoung@chromium.org

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

Instead, non-empty node names are kept in a single vector in the Cfg
object.

This is toward the goal of pulling non-POD fields out of the CfgNode
class so that CfgNode can be arena-allocated and not leak memory.

Also, actual setting of the node name is now guarded by ALLOW_DUMP.

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

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

Removes the need to call function llvm::DecodeBinaryOp. In turn, this removes
the need for enum type llvm::Instruction::BinaryOps, llvm::Type.isFPOrFPVectorTy, and one call to llvm::convertToLLVMType.

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

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

Also removes the need for DataLayout.

BUG=None
R=stichnot@chromium.org

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

Specifically, don't bother to collect "-timing" and "-szstats" information since they anyway don't get printed out under the MINIMAL build.  This is done by using the ALLOW_DUMP flag to guard whether code and timing stats are collected.  This ends up reducing the native translator size by about 3%.  ALLOW_DUMP is used as the guard since it already guards the output of the collected data - no sense collecting the data if it can never be printed out.

To minimize the number of ALLOW_DUMP tests, we push the tests into the timing/stats class methods.

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

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

This is consistent with how LLVM is built, and makes it easier to analyze the potential size of a translator build and what may be inappropriately brought into the build.

BUG= none
R=kschimpf@google.com

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

BUG= none
R=jvoung@chromium.org

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

BUG= none
R=kschimpf@google.com

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

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

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

This generally uses less memory and fewer allocations.

Also removes the commented-out alternative implementation using std::set<>, which would almost certainly never be a good idea here.

BUG= none
R=jvoung@chromium.org

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

BUG= none
R=jvoung@chromium.org

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

Profiling indicated a noticeable amount of time spent on malloc/free related to the std::list<> implementation of UnorderedRanges.  Therefore, we change the implementation to be std::vector<>, and up-front reserve a conservative amount of space to avoid expansion.  The push_back() operation is always constant time with no allocation.  Removing an element from the middle of the vector is done by swapping with the last element and then popping the last element, which is reasonable in principle because it is used as an unordered collection.  Because of the swapping trick, the UnorderedRanges iterators are changed to iterate in reverse.

BUG= none
R=jvoung@chromium.org

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

BUG=build failure
R=kschimpf@google.com

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

When LLVM 3.5 was merged, the handling of errors was broken. This
is being fixed in the CL listed below. This CL fixes Subzero's
call so that it will work with the CL listed below.

Relavant LLVM CL: https://codereview.chromium.org/770853002

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

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

Able to write out the ELF file header w/ a text section,
a symbol table, and string table. Write text buffer
directly to file after translating each CFG.
This means that the header is written out early w/ fake
data and then we seek back and write the real header
at the very end.

Does not yet handle relocations, data, rodata, constant
pools, bss, or -ffunction-sections, more than 64K sections
or more than 2^24 symbols.

Numbers w/ current NOASSERT=1 build on 176.gcc:

w/out -elf-writer:
    0.233771 (21.1%): [ 1287] emit
    28MB .s file

w/ -elf-writer:
    0.051056 ( 5.6%): [ 1287] emit
    2.4MB .o file

BUG=none
R=stichnot@chromium.org

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

Using lit.local.cfg, don't allow reader tests unless dumping
of IR is allowed.

This was suggested by Jan in: https://codereview.chromium.org/686913005

BUG=None
R=jvoung@chromium.org

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

In -O2 mode, postLower() is supposed to iterate over just the
instructions that were most recently added.  Instead, it was iterating
all the way to the end of the block, also post-lowering high-level ICE
instructions that hadn't yet been lowered.  This was basically
harmless, given that the spec2k asm code is identical after this
patch, but it improves performance.

BUG= none
R=jvoung@chromium.org

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

Use a bigger block size in the bump-pointer allocators, since we
basically know up front that we'll need lots of memory.  The 1MB value
(versus the default of 4KB) was chosen somewhat arbitrarily, and
succeeds in pretty much removing bump-pointer related mallocs from the
profile.

Pre-reserve the a priori known number of edges in getTerminatorEdges()
to avoid vector resizing.

BUG= none
R=kschimpf@google.com

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

We need to link with -lpthread now.

The CALLTARGETS workaround in our lit tests can be removed, since llvm-objdump has gotten more accurate than before with respect to symbols.

The -stats and -rng-seed options need to be renamed to avoid conflicting with the LLVM options being brought in.

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

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

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

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

Internally, create a separate constant pool for each integer type, instead of a single i64 pool that uses the Ice::Type value as part of the key.  This means each constant pool key can be a simple primitive value, rather than a tuple.

Represent the pools using std::unordered_map instead of std::map since we're using C++11 now.

Use signed integers instead of unsigned integers for the integer constant pools, to benefit from sign extension and to be more consistent.

Remove the SuppressMangling field from hash and comparison functions on RelocatableTuple, since we'll never have two symbols with the same name but different values of SuppressMangling.

BUG= none
R=jvoung@chromium.org

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

It's not meant to be comprehensive, but rather to help someone new get started, assuming they already have PNaCl working.

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

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

Remove the dump/emit routines when ALLOW_DUMP=0. Also fixes some
verbosity messages to not print if ALLOW_DUMP=0. Note: emit routines
needed for emitIAS are not turned off.

BUG=None
R=stichnot@chromium.org

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

This removes the need for Om1's postLower() code which did its own ad-hoc register allocation.  And it actually speeds up Om1 translation significantly.

This mode of register allocation only allocates for infinite-weight Variables, while respecting live ranges of pre-colored Variables.

BUG= none
R=jvoung@chromium.org

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

Seems to be part of the non-sfi link now:
https://codereview.chromium.org/686723003/diff/180001/pnacl/driver/pnacl-translate.py

Otherwise I get:
x86-32-linux/lib/unsandboxed_irt.o:(.rodata+0x68): undefined reference to `nacl_secure_random'

BUG=none
R=stichnot@chromium.org

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

Even after earlier simplifications, FakeKill was still handled somewhat inefficiently for the register allocator.  For x86-32, any function containing call instructions would result in about 11 pre-colored Variables, each with an identical and relatively complex live range consisting of points.  They would start out on the UnhandledPrecolored list, then all move to the Inactive list, where they would be repeatedly compared against each register allocation candidate via overlapsRange().

We improve this by keeping around a single copy of that live range and directly masking out the Free[] register set when that live range overlaps the current candidate's live range.  This saves ~10 overlaps() calculations per candidate while FakeKills are still pending.

Also, slightly rearrange the initialization of the Unhandled etc. sets into a separate init routine, which will make it easier to reuse the register allocator in other situations such as Om1 post-lowering.

BUG= none
R=jvoung@chromium.org

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

This is purely for convenience of personal testing/debugging.

To demonstrate its correctness in this CL, -build-on-read=0 is removed
from the two .ll lit tests that explicitly use it, and also from the
crosstest.py script.  The lit test wrapper run-llvm2ice.py is left
unchanged to be safe.

BUG= none
R=kschimpf@google.com

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

Instead, separately compute it during prolog generation via another
pass over the Cfg.

This may slow down translation by ~1%, but it greatly simplifies the
management of this flag/property.

The higher motivation is to pull this management out of register
allocation to make it easier to extend register allocation for other
uses.

BUG= none
R=jvoung@chromium.org

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

Use LLVM's intrusive list ADT template to implement instruction lists.  This embeds prev/next pointers into the instruction, and as such, iterators essentially double as instruction pointers.  This means stripping off one level of indirection when dereferencing, and also the range-based for loop can't be used.

The performance difference in translation time seems to be 1-2%.

I tried to also do this for the much less used PhiList and AssignList, but ran into SFINAE problems.

BUG= none
R=jvoung@chromium.org

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

This CL allows one to time Subzero's bitcode parsing without IR generation
(other than types, function declarations, and uninitialized global variables)
for performance testing.

BUG=None
R=jvoung@chromium.org

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

Eventually, I wanted to have a flag "UseELFWriter" like:
https://codereview.chromium.org/678533005/diff/120001/src/IceCfg.cpp

Where the emit OStream would not have text, and only have
binary. This refactor hopefully means fewer places to
check for a flag to disable the text version of IAS,
and be able to write binary. Otherwise, there are some
text labels for branches that are still being dumped out.

BUG=none
R=stichnot@chromium.org

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