(i.e assign split edges to the correct loop group, now for real)
The fix of 25b6fae1

 did try fix QTBUG-41766
and simplify the logic to assign the inserted statement to a loop group.
Unfortunately that was incorrect if the target basic block starts a group.
In that case if the source was already inside the group we should add it
to the target basic block, otherwise to the one containing the target
block (as before).
There was no visible regression caused by this.

Change-Id: Id50c42305fc5ac6aedaffa89d8f8dc3b5e976aa4
Task-number: QTBUG-41766
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

edge splitting had a strange logic to assign the inserted statement to a loop,
which would go wrong for example for the statement just after the loop header.
I guess that was done to increase the likelihood that the goto removed from the
final instructions.
Given that we are talking about critical edges it is always possible to emit
them in a bad order, and I do not think that the old logic was really better
than simply always use the loop group of the target which is always correct.
It might be worthwhile to ensure that the block it is emitted just before the
target block, or improve the handling of empty gotos in the backend, but in this
patch we go for the simplest solution.
If one would notice worse code, either one of the provious improvements could be
done, or the old logic could be kept, changing just the if (container == 0) to
container = toBB->containingGroup();

Change-Id: I26a488e9e2cb2b692fa8187ee658fb4dd98bfa8b
Task-number: QTBUG-41766
Reviewed-by: Bernd Lamecker <bernd.lamecker@basyskom.com>
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

Loop peeling is always disabled. Type inference is still enabled for
QML code, because of the static-type nature of the properties.

This speeds up crypto.js by 20%.

Change-Id: Ibf51cb36f8904d64df0793980d463451dfd361e2
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

With gcc 4.6.3 armhf (defualt for Ubuntu 12.04) some optimization bug
results in QML2 v4 compiler hang during type inference.

Task-number: QTBUG-40364
Change-Id: Iea1a8be3b5a7d9410304110d89dae3735339cb72
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>
Reviewed-by: Erik Verbruggen <erik.verbruggen@digia.com>

- Renamed LICENSE.LGPL to LICENSE.LGPLv21
- Added LICENSE.LGPLv3 & LICENSE.GPLv2
- Removed LICENSE.GPL

Change-Id: I84a565e2e0caa3b76bf291a7d188a57a4b00e1b0
Reviewed-by: Jani Heikkinen <jani.heikkinen@digia.com>

By peeling the first iteration off of a loop and putting it in front of
the loop, type inference can deduce more type information for esp. loop
induction variables. To prevent increasing the code size too much, only
the inner-most loops are peeled.

This gives a 10% speed-up on crypto.js.

Change-Id: I57f9611695bc8defc0bff84e440b8a20b2c8a34e
Reviewed-by: Fawzi Mohamed <fawzi.mohamed@digia.com>

When removing edges, the control-flow graph changes, so some immediate
dominators might need to be updated. This change collects all candidates
and processes them in a single batch.

Change-Id: I928f42232427a84bcb9658e314dadd0bd021b12f
Reviewed-by: Fawzi Mohamed <fawzi.mohamed@digia.com>

New structure:
- "comments" now start with a semi-colon, and have a list of key: values.
    ; predecessors: L17 L26 L36, loop_header: yes
    ; line: 30, column: 3

- when a temporary has a known type, it is written in front of the
  teporary when it is being assigned, and not repeated.
    var %109 = this
    double %42 = 42

- an expression starts with the operation, followed by the operands that
  are separated by commas. The type of the operands is the type
  mentioned when they are assigned.
    int32 %115 = sub %184, %185
    if gt %27, 0 goto L40 else goto L41

- conversions do mention the operand type in order to make them easier
  to read.
    double %178 = convert var to double %60

- phi node operands are prefixed by the from-label to make it easy to
  match those operands with the from-block.
    double %62 = phi L35: %58, L34: %61

- all names except for "this" and built-ins are prefixed by a dot in
  order to make it clear that a lookup will occur, just like member
  accesses.
    $6 = call .int2char($0)
    %7 = this
    %8 = %7.toString()

Change-Id: I9f626a91f97ca7c3f27e01a5539f3c4fc10a46b4
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

Generate better code for in-place binary operations where the right-hand
side is either a constant or a memory address. Now that the JIT can do
this, also tell the register allocator not to un-spill that right-hand
side.

Change-Id: I0ab852f6b92f90dfed99c05fbaf91aad2549ecf4
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

To be used in later patches.

Change-Id: I379addaea225482bcbfd7a0b03dbdbaa254dd579
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

Avoid errors like

compiler/qv4ssa.cpp:660:59: error: no matching function for call to
'sort(QVector<QV4::IR::BasicBlock*>::iterator, QVector<QV4::IR::BasicBlock*>::iterator,
(anonymous namespace)::DominatorTree::calculateDFNodeIterOrder() const::Cmp)'

Change-Id: I4189bd621f1cef5e00b06f5b6b6dd430fefe653f
Reviewed-by: Erik Verbruggen <erik.verbruggen@digia.com>

Now loop-specific algorithms can easily query which blocks are loop
headers, which blocks make up a loop body, and whether loops are nested.

Change-Id: I442af34d3cca816b61ee761335ff3571b72a6d3e
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

Move all data needed to calculate the immediate dominators into a struct
that is freed immediately after finishing this calculation.

Change-Id: Id0cefa4088643539d59c4c593cba1848422c1726
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

- CFG verification: check if all edges are correctly registered on both
  the outgoing basic-block and the incoming one, and that jumps/cjumps
  targets correspond to outgoing edges.
- immediate dominator verification: check if the current immediate
  dominators are the same as they would be if being recalculated from
  scratch.
- no shared expressions/statements: check if not more than one IR node
  points to a statement/expression.

Also add a function that writes out the CFG as a .dot file for graphviz.

Will be used in upcoming patches.

Change-Id: I784561f581f9f8ec22f3ab449afd87a9e7a8bdaf
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

The ++operator of std::vector<bool>::iterator in libc++ has a bug when
using it on an iterator pointing to the last element. It will not be set
to ::end(), but beyond that. (It will be set to the first multiple of
the native word size that is bigger than size().)

See http://llvm.org/bugs/show_bug.cgi?id=19663



Task-number: QTBUG-39911
Change-Id: Ic244d9c90ee6b596261a6e322301c411a14820a8
Reviewed-by: Fawzi Mohamed <fawzi.mohamed@digia.com>
Reviewed-by: Lars Knoll <lars.knoll@digia.com>
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

This will make sure that debug code gets compiled/checked, even when
it is disabled. An optimized build will remove the code.

Change-Id: Ia32de550ea95c44afa5ed84bc17cfeeada06f2f4
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

When arguments cannot "escape" from the current context, and when the
arguments array is not used, actual arguments can be treated the same
as temporaries instead of memory locations. This has the benefits that
they are subject to the same optimizations, and type deduction can
assume that the value/type didn't change since its assignment. Another
effect is that the values can be kept in registers, and loads from the
stack take only 1 indirect load instead of 2 (from the formals array).

Change-Id: I209da7991ec5d903b3c5acdbcaf6b1cc67502520
Reviewed-by: Lars Knoll <lars.knoll@digia.com>

We perform loop detection to be able to assign to each block its loop,
an chain them up from inner loop to outer loop. The new algorithm works
on each basic block just once, and looks at a basic block just the
number of connections it has. As it relies on the dominator tree it is
more robust on actually finding al looping constructs and only those
rather than relying on the statements used. It assumes that a basic
block is analyzed before the one that dominate it (to guarantee finding
outer loop headers before inner loop headers), so blocks are ordered to
work on them in a way that guarantees that, using dominator tree depth,
that is trivially available.

Loop detection allows us to then schedule the loop body before the part
after the loop (the header dominates both so just domination cannot
choose between both), and can be used to optimize loops (either
unrolling the first iteration or hoisting constant parts out of it).

It also helps with generated JavaScript code: in order to simulate gotos
or other unconditional branches, nested labeled do-while(false) loops
are often used in combination with break/continue to "jump" between
"loops".

Change-Id: Idfcc74589e057b191f74880ffd309d0a9c301811
Reviewed-by: Fawzi Mohamed <fawzi.mohamed@digia.com>

Change-Id: I67667b74672b94b951361bf2a446476edf44b826
Reviewed-by: Lars Knoll <lars.knoll@digia.com>

There are two changes in this patch, that go hand-in-hand. First, when
re-numbering the statements in order of occurrence in the scheduled
basic-blocks, the (new) position is not stored in the statement itself,
but in the LifeTimeIntervals class. This makes it possible to re-use
information gathered during SSA formation or optimization.

The re-numbering itself has also changed, resulting in some minor
changes to the life-time interval calculation. The new numbering
is described in LifeTimeIntervals::renumber(). The reason is to make it
easy for the register allocator and stack-slot allocator to distinguish
between definition of a temporary and its uses. Example:

  20: %3 = %2 + %1
  22: print(%3)

If the life-time of %2 or %1 ends at 20, then at the point that %3 gets
assigned, it can re-use the storage occupied by %1 or %2. Also, when
both %1 and %2 need to get a register assigned (because they were
spilled to the stack, for example), %3 should be allocated "after" both
%1 and %2. So, instead of having a closed interval of [20-22] for %3, we
want to use an open interval of (20-22]. To simulate the "open" part, the
life-time of %3 is set to [21-22]. So, all statements live on even
positions, and temporaries defined by a statement start at
statmentPosition + 1.

Change-Id: I0eda2c653b0edf1a529bd0762d338b0ea9a66aa0
Sanity-Review: Qt Sanity Bot <qt_sanitybot@qt-project.org>
Reviewed-by: Lars Knoll <lars.knoll@digia.com>

The statement ids are now stable, so the life-time interval calculation
can re-use information calculated by the optimizer. This re-use will
be done in a separate patch.

It also allows for changes to the numbering in a non-intrusive way. This
will also come in a later patch.

Change-Id: Ie3a2e1d9e3537cc8070ff3e3007f3a5e8ca0579a
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

When removing a phi node, add the def statement for the (previously)
used temps to the worklist. These statements might now be eligible for
further optimizations (specifically removal when there are no uses
left).

Change-Id: I05d7c7bc0a243d328b5f9d1c2dcc53a10bd7491d
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

Change-Id: Iedd751424ff0b651ba9e00a30f50e197ecd7967d
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

By storing LifeTimeIntervals by pointer (instead of by value), other
data-structures can safely use pointers too. This removes a lot of
copies, especially in vectors that act as worklists.

Also change the order of the "unhandled" list of intervals to be sorted
in descending order. Not only is this more efficient, but it also
removes the need to reverse the results of the life-range calculation
(which produces the list in exactly this order).

This change speeds up register allocation by about 20%.

Change-Id: I6ea3dcd110f250d9ccc881753dc7392510a26d87
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

By using vectors indexed on temp-id instead of hashes.

Also record the order in which intervals are removed from the list of
life ranges. This order is the inverse of the list of ranges sorted by
start position. So instead of building _sortedIntervals and then sorting
them, reverse iterating over the finished intervals will do the same.

This speeds up the interval calculation by 40%.

Change-Id: If3c78496d7ca2d0e23f0a51302dcd1094dad7d4a
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

This makes it easier to turn it off when needed.

Change-Id: I1a9f2882dd7a1ad7bc76143e3c44e4677e49357a
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

Previously, the DefUsesCalculator was a pass over the IR to find all
definitions and uses of temps. This is now merged with the variable
renaming when transforming into SSA form, where all definitions and all
uses are already visited (and changed). As it no longer calculates
anything, the class is also renamed to DefUses.

The interface is also cleaned up, as are all usages. This involved some
small changes to the data-structures storing return values from DefUses.

Change-Id: I40e665f5dee6144fc81066fbf6950355ebe8dfa4
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

Every statement in the IR now gets a fixed unique number. This number
can be used to store statements or information for a statement into an
array where the number is used as an index. This removes the need for
many hashes.

In the process of changing the code the two statement worklists in the
optimizer are merged into one. A single instance can be (and is) re-used
by the various algorithms.

Change-Id: I8f49ec7b1df79cf6914c5747f5d2c994dad110b2
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

Change-Id: Ibf21f5fe0f8ab035add5354f45f7869f4cdfead8
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

Change-Id: I09f9aa1921745b9aa323349d90c334b156f690cb
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

There are a couple of reasons to split the temporaries off from the
arguments and locals:

Temporaries are invisible, and changes to them cannot be observed.
On the other hand, arguments and locals are visible, and writes to them
can be seen from other places (nested functions), or by using the
arguments array. So, in practice these correspond to memory locations.
(One could argue that if neither nested functions, nor eval(), nor
arguments[] is used, the loads/stores are invisible too. But that's an
optimization, and changing locals/arguments to temporaries can be done
in a separate pass.)

Because of the "volatile" nature of arguments and locals, their usage
cannot be optimized. All optimizations (SSA construction, register
allocation, copy elimination, etc.) work on temporaries. Being able to
easily ignore all non-temporaries has the benefit that optimizations can
be faster.

Previously, Temps were not uniquely numbered: argument 1, local 1, and
temporary 1 all had the same number and were distinguishable by their
type. So, for any mapping from Temp to something else, a QHash was used.
Now that Temps only hold proper temporaries, the indexes do uniquely
identify them. Add to that the fact that after transforming to SSA form
all temporaries are renumbered starting from 0 and without any holes in
the numbering, many of those datastructures can be changed to simple
vectors. That change gives a noticeable performance improvement.

One implication of this change is that a number of functions that took
a Temp as their argument, now need to take Temp-or-ArgLocal, so Expr.
However, it turns out that there are very few places where that applies,
as many of those places also need to take constants or names. However,
explicitly separating memory loads/stores for arguments/locals from
temporaries adds the benefit that it's now easier to do a peep-hole
optimizer for those load/store operations in the future: when a load is
directly preceded by a store, it can be eliminated if the value is
still available in a temporary.

Change-Id: I4114006b076795d9ea9fe3649cdb3b9d7b7508f0
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

No sets, no cry, and no mallocs of QHashNodes.

QBitArray is not used on purpose: good STL implementations specialize
std::find for std::vector<bool>, with a significant speed gain.

Change-Id: Ic986bbd746e96eb494496f0508acb17318f4f0fb
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

This allows for overriding methods to customize the printing of nodes.
It also removes some duplicate code.

Change-Id: Ieb9eec2fa7d4e211932d7772586a1d62b119a90a
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

When the storage in the BasicBlockSet is a std::vector<bool>, the
begin() iterator and the ++operator now use std::find. Good STL
implementations have an optimized version specifically for
std::vector<bool> that is a lot faster than the iterating that was used
before. The change also makes the code more readable.

Change-Id: Ic37bac694c133c597b3d61a91b04a0b758516dc3
Reviewed-by: Lars Knoll <lars.knoll@digia.com>

Change-Id: Ie86bf5902328ad105fb07eb3e2809db21ff024d9
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

Change-Id: I565e0a22d4e94495eb427b85a59a62733a815527
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

This is among other things needed to fix the qml import scanner to detect
dependencies from .js files correctly.

The patch also fixes the use of Q_QML_EXPORT towards Q_QML_PRIVATE_EXPORT
where appropriate and corrects the wrong include path for the double conversion
code to actually be relative to the file it is included from. This worked by
accident because of other include paths present in the build.

Change-Id: I338583dad2f76300819af8ab0dae8e5724c84430
Reviewed-by: Lars Knoll <lars.knoll@digia.com>

- Replace 2 QHash<BasicBlock *, ...> with QVector<...>, where the
  basic-block index is the index of the vector.
- Nearly all QHashes and QSets will have a minimal fill rate. So,
  initialize/reserve all of them with a reasonable minimal size to
  prevent re-allocations and re-hashing.

Change-Id: Iade857991d73fddd0b92cecb8d458064b253a08d
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

Change-Id: I20ebf44ff0609f6833f7e59a4f2fb312be11b8c1
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

BasicBlocks have an index property which points to the index of that
basic block in the container array in Function. This property can be
used to store calculated information about basic blocks in a vector,
where the vector index corresponds to the basic block index. This is
a lot cheaper than storing any information in a
QHash<BasicBlock *, ....>.

However, this numbering requires that no re-ordering or deletion of
blocks happens. This change cleans up all that handling which was
scattered over a number of places.

Change-Id: I337abd39c030b9d30c82b7bbcf2ba89e50a08e63
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>