additionally rename data-flow.* to bit-vector.* as at some point these file became very inaccurately named

BUG=
R=svenpanne@chromium.org

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

Cr-Commit-Position: refs/heads/master@{#25030}
git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@25030 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

This adds a series of checks to the output of scheduling, including properties
of the RPO order, the dominance relation, phi placement, and the SSA property
that definitions dominate all their uses.

R=jarin@chromium.org
BUG=

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

git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@23310 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

The bit counting functions provided by CompilerIntrinsics were undefined
for zero, which was easily overlooked and unsafe in general. Also their
implementation was kinda hacky and mostly untested. Fixed the
implementation and moved the functions to base/bits.h.

TEST=base-unittests,cctest,compiler-unittests,mjsunit
R=hpayer@chromium.org

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

git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@23229 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

This way we don't clash with the ASSERT* macros
defined by GoogleTest, and we are one step closer
to being able to replace our homegrown base/ with
base/ from Chrome.

R=jochen@chromium.org, svenpanne@chromium.org

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

git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@22812 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

R=mstarzinger@chromium.org

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

git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@22709 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

- this avoids using relative include paths which are forbidden by the style guide
- makes the code more readable since it's clear which header is meant
- allows for starting to use checkdeps

BUG=none
R=jkummerow@chromium.org, danno@chromium.org
LOG=n

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

git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@21625 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

R=svenpanne@chromium.org

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

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@21035 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

This allows the deoptimizer to materialize objects (e.g. the arguments
object) while deopting without having a consective stack area holding
the object values. The LEnvironment explicitly tracks locations for
these values and preserves them in the translation.

R=svenpanne@chromium.org
TEST=mjsunit/compiler/inline-arguments

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

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@15087 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

This reduces the time take for mjsunit/limit-locals from 56.8s to 15.1s in debug
mode and from 12.0s to 1.6s in release mode.

Note that GrowableBitVector and BitVector should really be merged, and probably
have their allocation strategy parmeterized. The current state of affairs
involving tons of checks and delegation is extremely ugly, and it is far from
clear if all that special casing is a clear win. STL FTW! :-P

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

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@13327 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

This reduces the time to run our test suite in debug mode considerably (from
8:43 to 4:05 on my local workstation using 32 threads). Note that the assertion
is so fast now that it doesn't need to be hidden behind --enable-slow-asserts.
Furthermore, the bookkeeping of the set is not measurable in all our benchmarks,
so I intentionally avoided any #ifdef chaos to keep things simple.

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

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@13312 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

Review URL: https://chromiumcodereview.appspot.com/9416092

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@10791 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

header which uses BASE_EMBEDDED and/or AllStatic. Note that still only
45 out of 135 headers in src/ can be used stand-alone, but at least
this is a little bit more than before...
Review URL: http://codereview.chromium.org/6931031

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@7798 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

Try to make sure that accessors.h, data-flow.h, list-inl.h, and
scopeinfo.h are included only where needed, but without introducing
implicit dependencies.

Review URL: http://codereview.chromium.org/6903175

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@7756 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

Not used in Crankshaft anymore.
Review URL: http://codereview.chromium.org/6849023

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@7619 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@7271 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@7269 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

Review URL: http://codereview.chromium.org/6685088

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@7268 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

Review URL: http://codereview.chromium.org/6065010

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@6138 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@5922 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@5921 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@5920 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

Change more functions used by the Compiler class to have a uniform
interface: they get passed as argument an input/output pointer to a
CompilationInfo that they mutate if they succeed, and they return a
flag telling whether they succeeded.

Also, remove some unnecessary timers.

Review URL: http://codereview.chromium.org/3561012

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@5583 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

flow graph code completely. Add new AST node for null compares
and use it to make the full codegens better at generating code
for null comparisons.
Review URL: http://codereview.chromium.org/3146037

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@5323 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

The flow graph has been simplified to remove the special branch, join,
and exit nodes.  All nodes are now basic blocks (possibly empty to
preserve edge-split form) with a distinguished entry and exit block.

Most trivial expressions are not added to the flow graph as
instructions.  The assigned variable analyzer has been changed to
sometimes work right-to-left so that right subexpressions can be
marked as trivial.

The reaching definitions analysis has been temporarily removed, and
the analyses that depended on it (primitivity analysis, dead code
marking) as well.

Review URL: http://codereview.chromium.org/1530003

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@4307 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

The FlowGraph, FlowGraphBuilder, and flow graph node classes are moved
to src/flow-graph.cc.

Review URL: http://codereview.chromium.org/1253009

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@4287 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

As part of aggressive dead code elimination, we initially assume all
flow-graph instructions are not live.  We mark those that are critical
and recursively all their children.  The children of variable
references (VariableProxies occurring as rvalues) include all their
reaching definitions.

Review URL: http://codereview.chromium.org/1159005

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@4246 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

This change adds a data-flow pass to statically determine
if a variable contains a primitive type.

It requires building the flow graph and computing reaching
definitions as pre-requisites. The analysis annotates all
VariableProxy nodes with the result.

Review URL: http://codereview.chromium.org/1132005

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@4224 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

Include the initial definitions for parameters on input to the
function, and the initial definition of stack-allocated locals as
undefined.

Review URL: http://codereview.chromium.org/1155006

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@4206 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

This change adds the option to peel off the first iteration of inner loops.

Loop peeling is off by default and can enabled by a flag. It also requires building a flow graph.

As part of this I added the possibility to clone AST nodes.

Review URL: http://codereview.chromium.org/998001

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@4205 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

Also remove unused attributes related to it from the ast.
Review URL: http://codereview.chromium.org/1117003

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@4194 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

After computing RD_in for all flow graph nodes, push the reaching
definitions through the basic blocks to annotate all variable
references in the AST.

Review URL: http://codereview.chromium.org/889003

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@4143 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

Single argument constructors should be marked explicit.

TBR=fschneider@chromium.org

Review URL: http://codereview.chromium.org/876005

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@4114 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

Use the classical worklist algorithm to compute reaching definitions.
All nodes are initially put on the worklist.  Until the worklist is
empty, nodes are removed, their RD_in is recomputed, and if it changes
their successors are added to the worklist.

Review URL: http://codereview.chromium.org/853004

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@4113 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

Reaching definitions in (RD_in) is initially empty for all nodes.  Gen
and kill sets are computed.  AST node numbers are used for nodes to
refer to their definition number.

Also: two small changes to flow graph printing.  Children of branch
nodes are visited in right-to-left order when performing depth first
search.  Instructions are numbered locally within blocks so as to not
destroy AST node number before printing (it's useful to print the
definition).

Review URL: http://codereview.chromium.org/876001

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@4107 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

This change fixes a bug with the arguments object that occurred with
r4087 and r4088. The fix is not marking the arguments variable as trivial
since it can have side effects.


Review URL: http://codereview.chromium.org/851002

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@4099 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

Review URL: http://codereview.chromium.org/805005

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@4089 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

This change adds a pass over the AST that computes the
set of assigned variables for locals and parameters for each expression.

The result of this analysis is used to for two purposes:
1. Recognize variables that are trivial subexpressions. A left sub-expression
   of a binary operation is trivial if it is a local variable or a parameter
   and it is not assigned in the right sub-expression. In the case of a 
   trivial left sub-expression we evaluate the right first.
   Currently only binary operations and compare operations are considered
   when finding trivial left sub-expressions.

2. Recogize certain simple for-loops with a constant trip count where the loop
   variable is always within smi range. If the loop count variable is not
   assigned in the body of the loop (except in the update expression the
   for-loop). This allows omitting smi checks on operation using the loop
   count variable.

Review URL: http://codereview.chromium.org/669155

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@4087 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

Visitor stack overflow is used to signal an unsupported construct in
the flow graph.  Check for it in more places.  Make the utility
functions for appending to graphs handle more cases if they can be
handled correctly.

Remove the entry node in favor of a block with a NULL predecessor as
single entry.  Represent the empty flow graph as a single empty block.
Add empty blocks lazily where needed to preserve edge-split form.

Review URL: http://codereview.chromium.org/804003

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@4086 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

Change the BitVector utility class to allow allocation via 'new' in the
Zone.  Change the backing store to be always zone-allocated.

Review URL: http://codereview.chromium.org/730001

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@4071 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

Before computing reaching definitions, the set of all definitions in a
function must be collected and they must be numbered.  Have the flow
graph builder collect definitions for stack-allocated variables into a
list, and implicitly number them with their list index.

Review URL: http://codereview.chromium.org/668257

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@4064 ce2b1a6d-e550-0410-aec6-3dcde31c8c00