Detect when there is not enough available ILP, so if-conversion can't
speculate instructions for free.

Compute the lengthening of the critical path when inserting a select
instruction that depends on the condition as well as both sides of the
if.

Reject conversions that would stretch the critical path by more than
half a mispredict penalty.

llvm-svn: 161713

llvm-svn: 161712

Trace::getResourceLength() computes the number of cycles required to
execute the trace when ignoring data dependencies. The number can be
compared to the critical path to estimate the trace ILP.

Trace::getPHIDepth() computes the data dependency depth of a PHI in a
trace successor that isn't necessarily part of the trace.

llvm-svn: 161711

They identify the PHI predecessors in both diamonds and triangles.

llvm-svn: 161689

When a trace ends with a back-edge, include PHIs in the loop header in
the height computations. This makes the critical path through a loop
more accurate by including the latencies of the last instructions in the
loop.

llvm-svn: 161688

When replacing Old with New, it can happen that New is already a
successor. Add the old and new edge weights instead of creating a
duplicate edge.

llvm-svn: 161653

No changes to these patches, MRI needed to be notified when changing
uses into defs and vice versa.

llvm-svn: 161644

This was the cause of the buildbot failures.

llvm-svn: 161643

These commits broke a number of buildbots.

llvm-svn: 161640

This makes it possible to speed up def_iterator by stopping at the first
use. This makes def_empty() and getUniqueVRegDef() much faster when
there are many uses.

In a +Asserts build, LiveVariables is 100x faster in one case because
getVRegDef() has an assertion that would scan to the end of a
def_iterator chain.

Spill weight calculation is significantly faster (300x in one case)
because isTriviallyReMaterializable() calls MRI->isConstantPhysReg(%RIP)
which calls def_empty(%RIP).

llvm-svn: 161634

Use a more conventional doubly linked list where the Prev pointers form
a cycle. This means it is no longer necessary to adjust the Prev
pointers when reallocating the VRegInfo array.

The test changes are required because the register allocation hint is
using the use-list order to break ties.

llvm-svn: 161633

Register MachineOperands are kept in linked lists accessible via MRI's
reg_iterator interfaces. The linked list management was handled partly
by MachineOperand methods, partly by MRI methods.

Move all of the list management into MRI, delete
MO::AddRegOperandToRegInfo() and MO::RemoveRegOperandFromRegInfo().

Be more explicit about handling the cases where an MRI pointer isn't
available.

llvm-svn: 161632

No test case, the crash only happens when the default use list order is
changed.

llvm-svn: 161627

handle the cases where the memory value type was illegal. 
PR 13111. 

llvm-svn: 161565

That particular optimization was probably premature anyway.

llvm-svn: 161541

We filter out MachineLoop back-edges during the trace-building PO
traversals, but it is possible to have CFG cycles that aren't natural
loops, and MachineLoopInfo doesn't include such cycles.

Use a standard visited set to detect such CFG cycles, and completely
ignore them when picking traces.

llvm-svn: 161532

llvm-svn: 161513

Thanks, Andy!

llvm-svn: 161507

llvm-svn: 161470

It caused an assertion failure when compiling consumer-typeset.

llvm-svn: 161463

We perform the following:
1> Use SUB instead of CMP for i8,i16,i32 and i64 in ISel lowering.
2> Modify MachineCSE to correctly handle implicit defs.
3> Convert SUB back to CMP if possible at peephole.

Removed pattern matching of (a>b) ? (a-b):0 and like, since they are handled
by peephole now.

rdar://11873276

llvm-svn: 161462

The getSumForBlock function was quadratic in the number of successors
because getSuccWeight would perform a linear search for an already known
iterator.

llvm-svn: 161460

llvm-svn: 161454

This adds support for TargetIndex operands during isel. The meaning of
these (index, offset, flags) operands is entirely defined by the target.

llvm-svn: 161453

character arrays. This is in line with what GCC does.
<rdar://problem/10529227>

llvm-svn: 161446

A target index operand looks a lot like a constant pool reference, but
it is completely target-defined. It contains the 8-bit TargetFlags, a
32-bit index, and a 64-bit offset. It is preserved by all code generator
passes.

TargetIndex operands can be used to carry target-specific information in
cases where immediate operands won't suffice.

llvm-svn: 161441

llvm-svn: 161437

Compare the critical paths of the two traces through an if-conversion
candidate. If the difference is larger than the branch brediction
penalty, reject the if-conversion. If would never pay.

llvm-svn: 161433

Previously, MBP essentially aligned every branch target it could. This
bloats code quite a bit, especially non-looping code which has no real
reason to prefer aligned branch targets so heavily.

As Andy said in review, it's still a bit odd to do this without a real
cost model, but this at least has much more plausible heuristics.

Fixes PR13265.

llvm-svn: 161409

If the result of a common subexpression is used at all uses of the candidate
expression, CSE should not increase the live range of the common subexpression.

rdar://11393714 and rdar://11819721

llvm-svn: 161396

TwoAddressInstructionPass doesn't remat any more.

llvm-svn: 161285

llvm-svn: 161284

This patch is mostly just refactoring a bunch of copy-and-pasted code, but
it also adds a check that the call instructions are readnone or readonly.
That check was already present for sin, cos, sqrt, log2, and exp2 calls, but
it was missing for the rest of the builtins being handled in this code.

llvm-svn: 161282

No functional change intended, except replacing a DenseMap with a
SmallDenseMap which should behave identically.

llvm-svn: 161281

This is far from complete, and only changes behavior when the
-early-live-intervals flag is passed to llc.

llvm-svn: 161273

This option runs LiveIntervals before TwoAddressInstructionPass which
will eventually learn to exploit and update the analysis.

Eventually, LiveIntervals will run before PHIElimination, and we can get
rid of LiveVariables.

llvm-svn: 161270

Previously, the identity copy would survive through register allocation
before it was removed by the rewriter.

llvm-svn: 161269

The previous change caused fast isel to not attempt handling any calls to
builtin functions.  That included things like "printf" and caused some
noticable regressions in compile time.  I wanted to avoid having fast isel
keep a separate list of functions that had to be kept in sync with what the
code in SelectionDAGBuilder.cpp was handling.  I've resolved that here by
moving the list into TargetLibraryInfo.  This is somewhat redundant in
SelectionDAGBuilder but it will ensure that we keep things consistent.

llvm-svn: 161263

I noticed that SelectionDAGBuilder::visitCall was missing a check for memcmp
in TargetLibraryInfo, so that it would use custom code for memcmp calls even
with -fno-builtin.  I also had to add a new -disable-simplify-libcalls option
to llc so that I could write a test for this.

llvm-svn: 161262

The 'unused' state of a value number can be represented as an invalid
def SlotIndex. This also exposed code that shouldn't have been looking
at unused value VNInfos.

llvm-svn: 161258