[MBP] do not reorder and move up loop latch block

Do not reorder and move up a loop latch block before a loop header
when optimising for size because this will generate an extra
unconditional branc

[MBP] do not reorder and move up loop latch block

Do not reorder and move up a loop latch block before a loop header
when optimising for size because this will generate an extra
unconditional branch.

Differential Revision: https://reviews.llvm.org/D22521

llvm-svn: 278840

show more ...

Use the range variant of remove_if instead of unpacking begin/end

No functionality change is intended.

llvm-svn: 278475

Use the range variant of find instead of unpacking begin/end

If the result of the find is only used to compare against end(), just
use is_contained instead.

No functionality change is intended.

ll

Use the range variant of find instead of unpacking begin/end

If the result of the find is only used to compare against end(), just
use is_contained instead.

No functionality change is intended.

llvm-svn: 278433

show more ...

Codegen: MachineBlockPlacement Improve probability layout.

The following pattern was being layed out poorly:

A
/ \
B C
/ \ / \
D E

Codegen: MachineBlockPlacement Improve probability layout.

The following pattern was being layed out poorly:

A
/ \
B C
/ \ / \
D E ? (Doesn't matter)

Where A->B is far more likely than A->C, and prob(B->D) = prob(B->E)

The current algorithm gives:
A,B,C,E (D goes on worklist)

It does this even if C has a frequency count of 0. This patch
adjusts the layout calculation so that if freq(B->E) >> freq(C->E)
then we go ahead and layout E rather than C. Fallthrough half the time
is better than fallthrough never, or fallthrough very rarely. The
resulting layout is:

A,B,E, (C and D are in a worklist)

llvm-svn: 277187

show more ...

[MBP] Added some more debug messages and some clean ups /NFC

Differential Revision: https://reviews.llvm.org/D22669

llvm-svn: 276849

[MBP] Clean up of the comments, and a first attempt to better describe a part
of the algorithm.

Differential Revision: https://reviews.llvm.org/D22364

llvm-svn: 275595

Rename AnalyzeBranch* to analyzeBranch*.

Summary: NFC. Rename AnalyzeBranch/AnalyzeBranchPredicate to analyzeBranch/analyzeBranchPredicate to follow LLVM coding style and be consistent with TargetIn

Rename AnalyzeBranch* to analyzeBranch*.

Summary: NFC. Rename AnalyzeBranch/AnalyzeBranchPredicate to analyzeBranch/analyzeBranchPredicate to follow LLVM coding style and be consistent with TargetInstrInfo's analyzeCompare and analyzeSelect.

Reviewers: tstellarAMD, mcrosier

Subscribers: mcrosier, jholewinski, jfb, arsenm, dschuff, jyknight, dsanders, nemanjai

Differential Revision: https://reviews.llvm.org/D22409

llvm-svn: 275564

show more ...

[MBP] method interface cleanup

Make worklist and ehworklist member of the
class so that they don't need to be passed around.

llvm-svn: 274333

Codegen: [MBP] Add messages to asserts. NFC

llvm-svn: 274075

[MBP] show function name in debug dump

llvm-svn: 273744

Codegen: [MBP] Add assert strings. NFC

llvm-svn: 273067

[MBP] add comments and bug fix

Document the new parameter and threshod computation
model. Also fix a bug when the threshold parameter
is set to be different from the default.



llvm-svn: 272749

Set machine block placement hot prob threshold for both static and runtime profile.

Summary: With runtime profile, we have more confidence in branch probability, thus during basic block layout, we s

Set machine block placement hot prob threshold for both static and runtime profile.

Summary: With runtime profile, we have more confidence in branch probability, thus during basic block layout, we set a lower hot prob threshold so that blocks can be layouted optimally.

Reviewers: djasper, davidxl

Subscribers: llvm-commits

Differential Revision: http://reviews.llvm.org/D20991

llvm-svn: 272729

show more ...

[MBP] Interface cleanups /NFC

Save machine function pointer so that
the reference does not need to be passed around.

This also gives other methods access to machine
function for information such as

[MBP] Interface cleanups /NFC

Save machine function pointer so that
the reference does not need to be passed around.

This also gives other methods access to machine
function for information such as entry count etc.



llvm-svn: 272594

show more ...

[MBP] Code cleanup #3 /NFC

This is third patch to clean up the code.

Included in this patch:
1. Further unclutter trace/chain formation main routine;
2. Isolate the logic to compute global cost/con

[MBP] Code cleanup #3 /NFC

This is third patch to clean up the code.

Included in this patch:
1. Further unclutter trace/chain formation main routine;
2. Isolate the logic to compute global cost/conflict detection
into its own method;
3. Heavily document the selection algorithm;
4. Added helper hook to allow PGO specific logic to be
added in the future.


llvm-svn: 272582

show more ...

[MBP] Code cleanup /NFC

This is second patch to clean up the code.

In this patch, the logic to determine block outlinining
is refactored and more comments are added.


llvm-svn: 272514

[MBP] Code cleanup /NFC

This is one of the patches to clean up the code so that
it is in a better form to make future enhancements easier.

In htis patch, the logic to collect viable successors are

[MBP] Code cleanup /NFC

This is one of the patches to clean up the code so that
it is in a better form to make future enhancements easier.

In htis patch, the logic to collect viable successors are
extrated as a helper to unclutter the caller which gets very
large recenty. Also cleaned up BP adjustment code.


llvm-svn: 272482

show more ...

Reapply "[MBP] Reduce code size by running tail merging in MBP.""

This reapplies commit r271930, r271915, r271923. They hit a bug in
Thumb which is fixed in r272258 now.

The original message:

The

Reapply "[MBP] Reduce code size by running tail merging in MBP.""

This reapplies commit r271930, r271915, r271923. They hit a bug in
Thumb which is fixed in r272258 now.

The original message:

The code layout that TailMerging (inside BranchFolding) works on is not the
final layout optimized based on the branch probability. Generally, after
BlockPlacement, many new merging opportunities emerge.

This patch calls Tail Merging after MBP and calls MBP again if Tail Merging
merges anything.

llvm-svn: 272267

show more ...

Revive http://reviews.llvm.org/D12778 to handle forward-hot-prob and backward-hot-prob consistently.

Summary:
Consider the following diamond CFG:

A
/ \
B C
\/
D

Suppose A->B and A->C have proba

Revive http://reviews.llvm.org/D12778 to handle forward-hot-prob and backward-hot-prob consistently.

Summary:
Consider the following diamond CFG:

A
/ \
B C
\/
D

Suppose A->B and A->C have probabilities 81% and 19%. In block-placement, A->B is called a hot edge and the final placement should be ABDC. However, the current implementation outputs ABCD. This is because when choosing the next block of B, it checks if Freq(C->D) > Freq(B->D) * 20%, which is true (if Freq(A) = 100, then Freq(B->D) = 81, Freq(C->D) = 19, and 19 > 81*20%=16.2). Actually, we should use 25% instead of 20% as the probability here, so that we have 19 < 81*25%=20.25, and the desired ABDC layout will be generated.

Reviewers: djasper, davidxl

Subscribers: llvm-commits

Differential Revision: http://reviews.llvm.org/D20989

llvm-svn: 272203

show more ...

Revert "[MBP] Reduce code size by running tail merging in MBP."

This reverts commit r271930, r271915, r271923. They break a thumb selfhosting
bot.

llvm-svn: 272017

[MBP] Reduce code size by running tail merging in MBP.

The code layout that TailMerging (inside BranchFolding) works on is not the
final layout optimized based on the branch probability. Generally,

[MBP] Reduce code size by running tail merging in MBP.

The code layout that TailMerging (inside BranchFolding) works on is not the
final layout optimized based on the branch probability. Generally, after
BlockPlacement, many new merging opportunities emerge.

This patch calls Tail Merging after MBP and calls MBP again if Tail Merging
merges anything.

Differential Revision: http://reviews.llvm.org/D20276

llvm-svn: 271925

show more ...

Replace hard coded probability threshold with parameter /NFC

llvm-svn: 271751

[MBP] Factor out the optimizations on branch conditions and unanalyzable branches. NFCI.

The benefits of this patch are

-- We call AnalyzeBranch() to optimize unanalyzable branches, but the result

[MBP] Factor out the optimizations on branch conditions and unanalyzable branches. NFCI.

The benefits of this patch are

-- We call AnalyzeBranch() to optimize unanalyzable branches, but the result of
AnalyzeBranch() is not used. Now the result is useful.

-- Before the layout of all the MBBs is set, the result of AnalyzeBranch() is
not correct and needs to be fixed before using it to optimize the branch
conditions. Now this optimization is called after the layout, the code used
to fix the result of AnalyzeBranch() is not needed.

-- The branch condition of the last block is not optimized before. Now it is
optimized.

Differential Revision: http://reviews.llvm.org/D20177

llvm-svn: 270623

show more ...

[MBP] Remove a redundant skipFunction(). NFC.

skipFunction() is called twice.

Differential Revision: http://reviews.llvm.org/D20377

llvm-svn: 269994

Fix option description /NFC

llvm-svn: 269307