| commit | 3d42d549554889ca182e1f3d31b23fa1383c6678 | [log] [tgz] |
|---|---|---|
| author | Florian Hahn <flo@fhahn.com> | Tue Sep 15 14:47:23 2020 +0100 |
| committer | Florian Hahn <flo@fhahn.com> | Tue Sep 15 19:31:11 2020 +0100 |
| tree | 7b5d789e5eec15de65fad50aee4e08901a27479d | |
| parent | ca76d6e94a30b8fe11a63d3a55d3903c7cd25b5d [diff] |
[ConstraintElimination] Add constraint elimination pass.
This patch is a first draft of a new pass that adds a more flexible way
to eliminate compares based on more complex constraints collected from
dominating conditions.
In particular, it aims at simplifying conditions of the forms below
using a forward propagation approach, rather than instcomine-style
ad-hoc backwards walking of def-use chains.
if (x < y)
if (y < z)
if (x < z) <- simplify
or
if (x + 2 < y)
if (x + 1 < y) <- simplify assuming no wraps
The general approach is to collect conditions and blocks, sort them by
dominance and then iterate over the sorted list. Conditions are turned
into a linear inequality and add it to a system containing the linear
inequalities that hold on entry to the block. For blocks, we check each
compare against the system and see if it is implied by the constraints
in the system.
We also keep a stack of processed conditions and remove conditions from
the stack and the constraint system once they go out-of-scope (= do not
dominate the current block any longer).
Currently there still are the least the following areas for improvements
* Currently large unsigned constants cannot be added to the system
(coefficients must be represented as integers)
* The way constraints are managed currently is not very optimized.
Reviewed By: spatel
Differential Revision: https://reviews.llvm.org/D84547
This directory and its sub-directories contain source code for LLVM, a toolkit for the construction of highly optimized compilers, optimizers, and run-time environments.
The README briefly describes how to get started with building LLVM. For more information on how to contribute to the LLVM project, please take a look at the Contributing to LLVM guide.
Taken from https://llvm.org/docs/GettingStarted.html.
Welcome to the LLVM project!
The LLVM project has multiple components. The core of the project is itself called “LLVM”. This contains all of the tools, libraries, and header files needed to process intermediate representations and converts it into object files. Tools include an assembler, disassembler, bitcode analyzer, and bitcode optimizer. It also contains basic regression tests.
C-like languages use the Clang front end. This component compiles C, C++, Objective-C, and Objective-C++ code into LLVM bitcode -- and from there into object files, using LLVM.
Other components include: the libc++ C++ standard library, the LLD linker, and more.
The LLVM Getting Started documentation may be out of date. The Clang Getting Started page might have more accurate information.
This is an example work-flow and configuration to get and build the LLVM source:
Checkout LLVM (including related sub-projects like Clang):
git clone https://github.com/llvm/llvm-project.git
Or, on windows, git clone --config core.autocrlf=false https://github.com/llvm/llvm-project.git
Configure and build LLVM and Clang:
cd llvm-project
mkdir build
cd build
cmake -G <generator> [options] ../llvm
Some common build system generators are:
Ninja --- for generating Ninja build files. Most llvm developers use Ninja.Unix Makefiles --- for generating make-compatible parallel makefiles.Visual Studio --- for generating Visual Studio projects and solutions.Xcode --- for generating Xcode projects.Some Common options:
-DLLVM_ENABLE_PROJECTS='...' --- semicolon-separated list of the LLVM sub-projects you'd like to additionally build. Can include any of: clang, clang-tools-extra, libcxx, libcxxabi, libunwind, lldb, compiler-rt, lld, polly, or debuginfo-tests.
For example, to build LLVM, Clang, libcxx, and libcxxabi, use -DLLVM_ENABLE_PROJECTS="clang;libcxx;libcxxabi".
-DCMAKE_INSTALL_PREFIX=directory --- Specify for directory the full path name of where you want the LLVM tools and libraries to be installed (default /usr/local).
-DCMAKE_BUILD_TYPE=type --- Valid options for type are Debug, Release, RelWithDebInfo, and MinSizeRel. Default is Debug.
-DLLVM_ENABLE_ASSERTIONS=On --- Compile with assertion checks enabled (default is Yes for Debug builds, No for all other build types).
cmake --build . [-- [options] <target>] or your build system specified above directly.
The default target (i.e. ninja or make) will build all of LLVM.
The check-all target (i.e. ninja check-all) will run the regression tests to ensure everything is in working order.
CMake will generate targets for each tool and library, and most LLVM sub-projects generate their own check-<project> target.
Running a serial build will be slow. To improve speed, try running a parallel build. That's done by default in Ninja; for make, use the option -j NNN, where NNN is the number of parallel jobs, e.g. the number of CPUs you have.
For more information see CMake
Consult the Getting Started with LLVM page for detailed information on configuring and compiling LLVM. You can visit Directory Layout to learn about the layout of the source code tree.