summaryrefslogtreecommitdiffstats
path: root/polly/lib/ScheduleOptimizer.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Move transformations into own directoryAndreas Simbuerger2014-03-111-610/+0
| | | | | | | Move all transformations into their own directory. CMakeLists are adjusted accordingly. llvm-svn: 203607
* ScheduleOptimizer: Fix prevectorization.Tobias Grosser2014-03-111-2/+7
| | | | | | | | | | | | In case we are at the innermost band, we try to prepare for vectorization. This means, we look for the innermost parallel loop and strip mine this loop to the innermost level using a strip-mine factor corresponding to the number of vector iterations. For whatever reason, the code that implemented this feature was broken. We now added a comment, a test case and obviously also the right code. llvm-svn: 203544
* Do not fail in case we do not have valid dependencesTobias Grosser2014-02-231-0/+3
| | | | | | | | In case we do not have valid dependences, we do not run dead code elimination or the schedule optimizer. This fixes an infinite loop in the dead code elimination (PR12110). llvm-svn: 201982
* Optimizer: Do not accidentally set schedule to NULLTobias Grosser2014-02-211-9/+1
| | | | | | | | | | | In case the domain of a statement is empty, the schedule optimizer set by accident the schedule to a NULL pointer. This is incorrect. Instead, we set it to an empty isl_map with zero schedule dimensions. We already checked for this in our test cases, but unfortunately the test cases did not fail as expected. The assert we add in this commit now ensures that the test cases fail properly in case we regress on this again. llvm-svn: 201886
* Update to isl 1b3ba3b72c0482fd36bf0b4a1186a259f7bafeedTobias Grosser2014-01-261-2/+11
| | | | | | | | | | | | | | | This includes the following very useful isl commit: commit d962967ab42323ea5ca0398956fbff6a98c782fa Author: Sven Verdoolaege <skimo@kotnet.org> Date: Wed Dec 18 12:05:32 2013 +0100 allow the user to impose a bound on the number of low-level operations This should allow the user to deterministically limit the effort spent on a computation. llvm-svn: 200155
* Integrate latest clang-format changesTobias Grosser2013-06-231-2/+3
| | | | llvm-svn: 184655
* Use isl_val instead of isl_int in the core of PollyTobias Grosser2013-06-211-5/+3
| | | | | | | | | | | isl recently introduced isl_val as an abstract interface to represent arbitrary precision numbers. This interface superseeds the old isl_int interface. In contrast to the old interface which implemented arbitrary precision arithmetic using macros that forward to the gmp library, the new library hides the math library implementation in isl. This allows us to switch the math library used by isl without affecting users such as Polly. llvm-svn: 184529
* Sort includesTobias Grosser2013-05-071-7/+5
| | | | llvm-svn: 181297
* Move polly options into separate option categoryTobias Grosser2013-05-071-9/+9
| | | | | | | | | | | | | | | | | | | | | | | | | | Use the new cl::OptionCategory support to move the Polly options into a separate option category. The aim is to hide most options and show by default only the options a user needs to influence '-O3 -polly'. The available options probably need some care, but here is the current status: Polly Options: Configure the polly loop optimizer -enable-polly-openmp - Generate OpenMP parallel code -polly - Enable the polly optimizer (only at -O3) -polly-no-tiling - Disable tiling in the scheduler -polly-only-func=<function-name> - Only run on a single function -polly-report - Print information about the activities of Polly -polly-vectorizer - Select the vectorization strategy =none - No Vectorization =polly - Polly internal vectorizer =unroll-only - Only grouped unroll the vectorize candidate loops =bb - The Basic Block vectorizer driven by Polly llvm-svn: 181295
* Reformat with clang-formatTobias Grosser2013-05-071-15/+21
| | | | | | | clang-format become way more stable. This time we mainly reformat function signatures. llvm-svn: 181294
* ScheduleOptimizer: Use isl_map_from_union_map to extract map.Tobias Grosser2013-04-111-19/+13
| | | | llvm-svn: 179268
* ScheduleOpt: Do not crash on statements with empty iteration domainsTobias Grosser2013-04-101-1/+14
| | | | | | | | | | | Statements with an empty iteration domain may not have a schedule assigned by the isl schedule optimizer. As Polly expects each statement to have a schedule, we keep the old schedule for such statements. This fixes http://llvm.org/PR15645` Reported-by: Johannes Doerfert <johannesdoerfert@gmx.de> llvm-svn: 179233
* clang-format: Many more filesTobias Grosser2013-03-231-185/+168
| | | | | | | | | | | | | After this commit, polly is clang-format clean. This can be tested with 'ninja polly-check-format'. Updates to clang-format may change this, but the differences will hopefully be both small and general improvements to the formatting. We currently have some not very nice formatting for a couple of items, DEBUG() stmts for example. I believe the benefit of being clang-format clean outweights the not perfect layout of this code. llvm-svn: 177796
* isl scheduler: Do not fail when returning an empty band listTobias Grosser2012-10-161-4/+35
| | | | | | | | | The bug was within isl. To fix it, we simply update the isl version that is used by Polly. We still have some changes within Polly to be able to write a proper test case. Reported-by: Sameer Sahasrabuddhe <Sameer.Sahasrabuddhe@amd.com> llvm-svn: 166021
* ScheduleOptimizer: Simplify some codeTobias Grosser2012-05-221-22/+10
| | | | | | We now use isl_map_equate, which makes the code a lot simpler. llvm-svn: 157246
* Allow polly ask bb-vectorizer to vectorize the loop body.Hongbin Zheng2012-05-061-1/+1
| | | | llvm-svn: 156254
* ScheduleOptimizer: Move functions into classTobias Grosser2012-04-251-83/+105
| | | | llvm-svn: 155548
* Refactor: Move the code generation related header files to ↵Hongbin Zheng2012-04-251-1/+1
| | | | | | include/polly/CodeGen. llvm-svn: 155547
* ScheduleOpt: Fix crash with -enable-polly-vectorTobias Grosser2012-04-161-3/+4
| | | | llvm-svn: 154808
* Fix typos.Tobias Grosser2012-04-091-1/+1
| | | | | | Pointed out by: Sebastian Pop <sebpop@gmail.com> llvm-svn: 154337
* ScheduleOptimizer: Remove forgotten debug outputTobias Grosser2012-03-161-2/+0
| | | | llvm-svn: 152936
* ScheduleOptimizer: Do not get dependences, if we do not calculate a scheduleTobias Grosser2012-03-161-2/+3
| | | | | | | This solves the 'isl_ctx freed, but some objects still reference it' problem reported in PR12276. llvm-svn: 152917
* Remove FinalReadTobias Grosser2012-03-081-8/+0
| | | | | | | | | | | | | The FinalRead statement represented a virtual read that is executed after the SCoP. It was used when we verified the correctness of a schedule by checking if it yields the same FLOW dependences as the original code. This is only works, if we have a final read that reads all memory at the end of the SCoP. We now switched to just checking if a schedule does not introduce negative dependences and also consider WAW WAR dependences. This restricts the schedules a little bit more, but we do not have any optimizer that would calculate a more complex schedule. Hence, for now final reads are obsolete. llvm-svn: 152319
* ScheduleOpt: Add option to bound scheduling coefficients of dimensions.Tobias Grosser2012-02-201-0/+6
| | | | llvm-svn: 150953
* ScheduleOptimizer: Dump the calculated schedule in debug modeTobias Grosser2012-02-201-0/+3
| | | | llvm-svn: 150951
* ScheduleOpt: Add option to bound constant term coefficientsTobias Grosser2012-02-201-0/+6
| | | | llvm-svn: 150950
* ScheduleOpt: Only get RAW dependences if we asked for rawTobias Grosser2012-02-151-2/+1
| | | | llvm-svn: 150574
* ScheduleOpt: Allow to configure for which dependences to optimizeTobias Grosser2012-02-141-2/+21
| | | | | | | We can either optimize for RAW dependences or for all dependences. For the moment, I do not see a big difference here. llvm-svn: 150484
* CodeGen: Get dependences for validity and proximity separatelyTobias Grosser2012-02-141-12/+12
| | | | | | | | This change itself should not change functionality, but it will make it easier to support use different dependence kinds in for validity and proximity constraints. llvm-svn: 150483
* ScopInfo: Add Scop::getDomains()Tobias Grosser2012-02-141-10/+1
| | | | llvm-svn: 150482
* ScheduleOptimizer: Change vars to start with uppercase letterTobias Grosser2012-02-131-34/+34
| | | | llvm-svn: 150430
* Schedule: Sort includes and remove useless onesTobias Grosser2012-01-311-11/+5
| | | | llvm-svn: 149383
* Remove leftover constantTobias Grosser2012-01-301-2/+0
| | | | llvm-svn: 149290
* Scheduling: Limiting the constant term is not necessary any moreTobias Grosser2012-01-301-1/+0
| | | | | | | | | Due to our gist simplifications, limiting the constant term does not seem to be necessary any more. Pointed out by Sven Verdoolaege llvm-svn: 149288
* Typo: Maxize -> MazimizeTobias Grosser2012-01-301-4/+4
| | | | | | Found by Sebastian Pop. llvm-svn: 149287
* Scheduling: Set fusion strategy to minimalTobias Grosser2012-01-301-1/+1
| | | | | | | | | This has shown better results for 2mm, 3mm and a couple of other benchmarks. After this we show consistenly better results as PoCC with maxfuse. We need to see if PoCC can also give better results with another fusion strategy. llvm-svn: 149267
* Scheduling: Add option to disable schedule_maximise_band_depthTobias Grosser2012-01-301-1/+18
| | | | | | | | maximise_band_depth does not seem to have any effect for now, but it may help to increase the amount of tileable loops. We expose the flag to be able to analyze its effects when looking into individual benchmarks. llvm-svn: 149266
* Scheduler: Allow to select the fusion strategyTobias Grosser2012-01-301-0/+18
| | | | llvm-svn: 149265
* Scheduling: Use original schedule if we cannot find a new oneTobias Grosser2012-01-301-0/+9
| | | | | | | After this we can now compile all polybench 2.0 kernels without any compiler crash. llvm-svn: 149264
* Scheduler: Simplify dependences by default (only isl)Tobias Grosser2012-01-301-4/+27
| | | | | | | | | | | | | | | | | | This speeds up the scheduler by orders of magnitude and in addition yields often to a better schedule. With this we can compile all polybench kernels with less than 5x compile time overhead. In general the overhead is even less than 2-3x. This is still with running a lot of redundant passes and no compile time tuning at all. There are several obvious areas where we can improve here further. There are also two test cases where we cannot find a schedule any more (cholesky and another). I will look into them later on. With this we have a very solid base line from which we can start to optimize further. llvm-svn: 149263
* Scheduler: Try to maximize the band depthTobias Grosser2011-12-141-0/+1
| | | | | | | | | | | | | | | | Previously the scheduler was splitting bands at the level at which it detected that the splitting of the band is necessary. This may introduce an additional level of bands, that can be avoided by backtracking and splitting on a higher level. Additional splits reduce the number of loops that can be tiled, such that avoiding splits and maximizing the band depth seems preferable. As a first data point we looked at 2mm and 3mm from the polybench test suite. For both maximizing the tilable bands results in a significant (5-10x) performance improvement. This patch enables the isl scheduler option to maximize the band depth. llvm-svn: 146557
* Scheduler: Set maximal constant termTobias Grosser2011-12-141-0/+3
| | | | | | | | | | | | | | | | | | | | | | | If larger coefficients appear as part of the input dependences, the schedule calculation can take a very long time. We observed that the main overhead in this calculation is due to optimizing the constant coefficients. They are misused to increase locality by merging several unrelated dimensions into a single dimension. This unwanted optimization increases the complexity of the generated code and furthermore slows it down. We use a new isl scheduler option to bound the values in the constant dimension by a user defined value (20 in our case). If the right value is choosen, costly overoptimization is prevented. This solution works, but requires a specific (here almost randomly choosen) value by which the constants are bound. For the moment, this is our best solution, but we hope to to find a more generic one later on. After these patch the extremly long compile time for simple kernels like 2mm or 3mm is reduced to a reasonable amount of time (Not more than a couple of seconds even in debug mode). llvm-svn: 146556
* ScheduleOptimizer: Do not tile bands with just one dimensionTobias Grosser2011-12-081-9/+14
| | | | llvm-svn: 146149
* ScheduleOptimizer: Rewrite getPrevectorMap to use isl_pw_affTobias Grosser2011-12-071-52/+92
| | | | | | | This increases the readablity. This also adds some comments that explain what this function does. llvm-svn: 146028
* Register Passes: Use -polly-optimizer=(isl|pocc) to switch optimizersTobias Grosser2011-11-221-3/+3
| | | | | | | This replaces the old option -polly-use-pocc. Also call the passes uniformly -polly-opt-pocc and -polly-opt-isl. llvm-svn: 145071
* ScheduleOptimizer: Start with an empty union_map and add elementsTobias Grosser2011-11-171-5/+2
| | | | llvm-svn: 144900
* ScheduleOptimizer: Some style changesTobias Grosser2011-11-171-64/+75
| | | | | | | | - Use uppercase letters according to the LLVM coding style - Rename functions to not include 'tiledSchedule', but just Schedule. This is more correct as tiling might be disabled. llvm-svn: 144899
* ScheduleOptimizer: Use early exitTobias Grosser2011-11-171-11/+10
| | | | | | Style fix, noted by Sebastian Pop. llvm-svn: 144898
* Only have a single option to disable tiling for both isl and Pocc optimzerTobias Grosser2011-10-231-4/+8
| | | | | | This also documents the new option on the website. llvm-svn: 142775
* Enable prevectorization with -enable-polly-vector.Tobias Grosser2011-10-231-7/+2
| | | | | | This removes the separate prevector options for the Pluto and isl scheduler. llvm-svn: 142774
OpenPOWER on IntegriCloud