[Dominators] Make IsPostDominator a template parameter

Summary:
DominatorTreeBase used to have IsPostDominators (bool) member to indicate if the tree is a dominator or a postdominator tree. This mad

[Dominators] Make IsPostDominator a template parameter

Summary:
DominatorTreeBase used to have IsPostDominators (bool) member to indicate if the tree is a dominator or a postdominator tree. This made it possible to switch between the two 'modes' at runtime, but it isn't used in practice anywhere.

This patch makes IsPostDominator a template argument. This way, it is easier to switch between different algorithms at compile-time based on this argument and design external utilities around it. It also makes it impossible to incidentally assign a postdominator tree to a dominator tree (and vice versa), and to further simplify template code in GenericDominatorTreeConstruction.

Reviewers: dberlin, sanjoy, davide, grosser

Reviewed By: dberlin

Subscribers: mzolotukhin, llvm-commits

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

llvm-svn: 308040

show more ...

[Dominators] Reapply r306892, r306893, r306893.

This reverts commit r306907 and reapplies the patches in the title.
The patches used to make one of the
CodeGen/ARM/2011-02-07-AntidepClobber.ll test

[Dominators] Reapply r306892, r306893, r306893.

This reverts commit r306907 and reapplies the patches in the title.
The patches used to make one of the
CodeGen/ARM/2011-02-07-AntidepClobber.ll test to fail because of a
missing null check.

llvm-svn: 306919

show more ...

Revert "[Dominators] Teach IDF to use level information"

This reverts commit r306894.

Revert "[Dominators] Add NearestCommonDominator verification"

This reverts commit r306893.

Revert "[Dominator

Revert "[Dominators] Teach IDF to use level information"

This reverts commit r306894.

Revert "[Dominators] Add NearestCommonDominator verification"

This reverts commit r306893.

Revert "[Dominators] Keep tree level in DomTreeNode and use it to find NCD and answer dominance queries"

This reverts commit r306892.

llvm-svn: 306907

show more ...

[Dominators] Keep tree level in DomTreeNode and use it to find NCD and answer dominance queries

Summary:
This patch makes DomTreeNodes keep their level (depth) in the DomTree. By having this informa

[Dominators] Keep tree level in DomTreeNode and use it to find NCD and answer dominance queries

Summary:
This patch makes DomTreeNodes keep their level (depth) in the DomTree. By having this information always available, it is possible to speedup and simplify findNearestCommonDominator and certain dominance queries.

In the future, level information will be also needed to perform incremental updates.

My testing doesn't show any noticeable performance differences after applying this patch. There may be some improvements when other passes are thought to use the level information.

Reviewers: dberlin, sanjoy, chandlerc, grosser

Reviewed By: dberlin

Subscribers: llvm-commits

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

llvm-svn: 306892

show more ...

[Dominators] Don't compute DFS InOut numbers eagerly.

Summary:
DFS InOut numbers currently get eagerly computer upon DomTree construction. They are only needed to answer dome dominance queries and t

[Dominators] Don't compute DFS InOut numbers eagerly.

Summary:
DFS InOut numbers currently get eagerly computer upon DomTree construction. They are only needed to answer dome dominance queries and they get invalidated by updates and recalculations. Because of that, it is faster in practice to compute them lazily when they are actually needed.

Clang built without this patch takes 6m 45s to boostrap on my machine, and with the patch applied 6m 38s.

Reviewers: sanjoy, dberlin, chandlerc

Reviewed By: dberlin

Subscribers: davide, llvm-commits

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

llvm-svn: 306778

show more ...

Handle non-unique edges in edge-dominance

This removes a quadratic behavior in assert-enabled builds.

GVN propagates the equivalence from a condition into the blocks guarded by the
condition. E.g.

Handle non-unique edges in edge-dominance

This removes a quadratic behavior in assert-enabled builds.

GVN propagates the equivalence from a condition into the blocks guarded by the
condition. E.g. for 'if (a == 7) { ... }', 'a' will be replaced in the block
with 7. It does this by replacing all the uses of 'a' that are dominated by
the true edge.

For a switch with N cases and U uses of the value, this will mean N * U calls
to 'dominates'. Asserting isSingleEdge in 'dominates' make this N^2 * U
because this function checks for the uniqueness of the edge. I.e. traverses
each edge between the SwitchInst's block and the cases.

The change removes the assert and makes 'dominates' works correctly in the
presence of non-unique edges.

This brings build time down by an order of magnitude for an input that has
~10k cases in a switch statement.

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

llvm-svn: 304721

show more ...

Rearrange Dom unittest to accommodate multiple tests

I've taken the approach from the LoopInfo test:

* Rather than running in the pass manager just build the analyses manually
* Split out the commo

Rearrange Dom unittest to accommodate multiple tests

I've taken the approach from the LoopInfo test:

* Rather than running in the pass manager just build the analyses manually
* Split out the common parts (makeLLVMModule, runWithDomTree) into helpers

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

llvm-svn: 304061

show more ...

clang-format DomTree unittest

llvm-svn: 304060

Fix test typo. NFC

llvm-svn: 303489

[StructurizeCfg] Update dominator info.

In some cases StructurizeCfg updates root node, but dominator info
remains unchanges, it causes crash when expensive checks are enabled.
To cope with this pro

[StructurizeCfg] Update dominator info.

In some cases StructurizeCfg updates root node, but dominator info
remains unchanges, it causes crash when expensive checks are enabled.
To cope with this problem a new method was added to DominatorTreeBase
that allows adding new root nodes, it is called in StructurizeCfg to
put dominator tree in sync.

This change fixes PR27488.

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

llvm-svn: 291530

show more ...

Remove every uses of getGlobalContext() in LLVM (but the C API)

At the same time, fixes InstructionsTest::CastInst unittest: yes
you can leave the IR in an invalid state and exit when you don't
dest

Remove every uses of getGlobalContext() in LLVM (but the C API)

At the same time, fixes InstructionsTest::CastInst unittest: yes
you can leave the IR in an invalid state and exit when you don't
destroy the context (like the global one), no longer now.

This is the first part of http://reviews.llvm.org/D19094

From: Mehdi Amini <mehdi.amini@apple.com>
llvm-svn: 266379

show more ...

Introduce analysis pass to compute PostDominators in the new pass manager. NFC

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

llvm-svn: 261902

Revert "Introduce analysis pass to compute PostDominators in the new pass manager. NFC"

This reverts commit a3e5cc6a51ab5ad88d1760c63284294a4e34c018.

llvm-svn: 261891

Introduce analysis pass to compute PostDominators in the new pass manager. NFC

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

llvm-svn: 261882

unittests: Remove implicit ilist iterator conversions, NFC

llvm-svn: 250843

Move the personality function from LandingPadInst to Function

The personality routine currently lives in the LandingPadInst.

This isn't desirable because:
- All LandingPadInsts in the same function

Move the personality function from LandingPadInst to Function

The personality routine currently lives in the LandingPadInst.

This isn't desirable because:
- All LandingPadInsts in the same function must have the same
personality routine. This means that each LandingPadInst beyond the
first has an operand which produces no additional information.

- There is ongoing work to introduce EH IR constructs other than
LandingPadInst. Moving the personality routine off of any one
particular Instruction and onto the parent function seems a lot better
than have N different places a personality function can sneak onto an
exceptional function.

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

llvm-svn: 239940

show more ...

Only recalculate DFS Numbers if invalid. Invalidate DFS numbers on reset. Add unit test to verify recalculation

llvm-svn: 234933

Use 'override/final' instead of 'virtual' for overridden methods

The patch is generated using clang-tidy misc-use-override check.

This command was used:

tools/clang/tools/extra/clang-tidy/tool/r

Use 'override/final' instead of 'virtual' for overridden methods

The patch is generated using clang-tidy misc-use-override check.

This command was used:

tools/clang/tools/extra/clang-tidy/tool/run-clang-tidy.py \
-checks='-*,misc-use-override' -header-filter='llvm|clang' \
-j=32 -fix -format

http://reviews.llvm.org/D8925

llvm-svn: 234679

show more ...

[PM] Remove the old 'PassManager.h' header file at the top level of
LLVM's include tree and the use of using declarations to hide the
'legacy' namespace for the old pass manager.

This undoes the pri

[PM] Remove the old 'PassManager.h' header file at the top level of
LLVM's include tree and the use of using declarations to hide the
'legacy' namespace for the old pass manager.

This undoes the primary modules-hostile change I made to keep
out-of-tree targets building. I sent an email inquiring about whether
this would be reasonable to do at this phase and people seemed fine with
it, so making it a reality. This should allow us to start bootstrapping
with modules to a certain extent along with making it easier to mix and
match headers in general.

The updates to any code for users of LLVM are very mechanical. Switch
from including "llvm/PassManager.h" to "llvm/IR/LegacyPassManager.h".
Qualify the types which now produce compile errors with "legacy::". The
most common ones are "PassManager", "PassManagerBase", and
"FunctionPassManager".

llvm-svn: 229094

show more ...

Modernize the .ll parsing interface.

* Use StringRef instead of std::string&
* Return a std::unique_ptr<Module> instead of taking an optional module to write
to (was not really used).
* Use curren

Modernize the .ll parsing interface.

* Use StringRef instead of std::string&
* Return a std::unique_ptr<Module> instead of taking an optional module to write
to (was not really used).
* Use current comment style.
* Use current naming convention.

llvm-svn: 215989

show more ...

[C++11] Use 'nullptr'.

llvm-svn: 210442

Replace OwningPtr<T> with std::unique_ptr<T>.

This compiles with no changes to clang/lld/lldb with MSVC and includes
overloads to various functions which are used by those projects and llvm
which ha

Replace OwningPtr<T> with std::unique_ptr<T>.

This compiles with no changes to clang/lld/lldb with MSVC and includes
overloads to various functions which are used by those projects and llvm
which have OwningPtr's as parameters. This should allow out of tree
projects some time to move. There are also no changes to libs/Target,
which should help out of tree targets have time to move, if necessary.

llvm-svn: 203083

show more ...

[PM] Split DominatorTree into a concrete analysis result object which
can be used by both the new pass manager and the old.

This removes it from any of the virtual mess of the pass interfaces and
le

[PM] Split DominatorTree into a concrete analysis result object which
can be used by both the new pass manager and the old.

This removes it from any of the virtual mess of the pass interfaces and
lets it derive cleanly from the DominatorTreeBase<> template. In turn,
tons of boilerplate interface can be nuked and it turns into a very
straightforward extension of the base DominatorTree interface.

The old analysis pass is now a simple wrapper. The names and style of
this split should match the split between CallGraph and
CallGraphWrapperPass. All of the users of DominatorTree have been
updated to match using many of the same tricks as with CallGraph. The
goal is that the common type remains the resulting DominatorTree rather
than the pass. This will make subsequent work toward the new pass
manager significantly easier.

Also in numerous places things became cleaner because I switched from
re-running the pass (!!! mid way through some other passes run!!!) to
directly recomputing the domtree.

llvm-svn: 199104

show more ...

[cleanup] Move the Dominators.h and Verifier.h headers into the IR
directory. These passes are already defined in the IR library, and it
doesn't make any sense to have the headers in Analysis.

Long

[cleanup] Move the Dominators.h and Verifier.h headers into the IR
directory. These passes are already defined in the IR library, and it
doesn't make any sense to have the headers in Analysis.

Long term, I think there is going to be a much better way to divide
these matters. The dominators code should be fully separated into the
abstract graph algorithm and have that put in Support where it becomes
obvious that evn Clang's CFGBlock's can use it. Then the verifier can
manually construct dominance information from the Support-driven
interface while the Analysis library can provide a pass which both
caches, reconstructs, and supports a nice update API.

But those are very long term, and so I don't want to leave the really
confusing structure until that day arrives.

llvm-svn: 199082

show more ...

Move the LLVM IR asm writer header files into the IR directory, as they
are part of the core IR library in order to support dumping and other
basic functionality.

Rename the 'Assembly' include direc

Move the LLVM IR asm writer header files into the IR directory, as they
are part of the core IR library in order to support dumping and other
basic functionality.

Rename the 'Assembly' include directory to 'AsmParser' to match the
library name and the only functionality left their -- printing has been
in the core IR library for quite some time.

Update all of the #includes to match.

All of this started because I wanted to have the layering in good shape
before I started adding support for printing LLVM IR using the new pass
infrastructure, and commandline support for the new pass infrastructure.

llvm-svn: 198688

show more ...