summaryrefslogtreecommitdiffstats
path: root/polly/lib/Support/ScopHelper.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Treat conditionally executed non-pure calls as errorsJohannes Doerfert2015-10-071-14/+23
| | | | | | | | | | | | | | This replaces the support for user defined error functions by a heuristic that tries to determine if a call to a non-pure function should be considered "an error". If so the block is assumed not to be executed at runtime. While treating all non-pure function calls as errors will allow a lot more regions to be analyzed, it will also cause us to dismiss a lot again due to an infeasible runtime context. This patch tries to limit that effect. A non-pure function call is considered an error if it is executed only in conditionally with regards to a cheap but simple heuristic. llvm-svn: 249611
* Allow invariant loads in the SCoP descriptionJohannes Doerfert2015-10-071-7/+16
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch allows invariant loads to be used in the SCoP description, e.g., as loop bounds, conditions or in memory access functions. First we collect "required invariant loads" during SCoP detection that would otherwise make an expression we care about non-affine. To this end a new level of abstraction was introduced before SCEVValidator::isAffineExpr() namely ScopDetection::isAffine() and ScopDetection::onlyValidRequiredInvariantLoads(). Here we can decide if we want a load inside the region to be optimistically assumed invariant or not. If we do, it will be marked as required and in the SCoP generation we bail if it is actually not invariant. If we don't it will be a non-affine expression as before. At the moment we optimistically assume all "hoistable" (namely non-loop-carried) loads to be invariant. This causes us to expand some SCoPs and dismiss them later but it also allows us to detect a lot we would dismiss directly if we would ask e.g., AliasAnalysis::canBasicBlockModify(). We also allow potential aliases between optimistically assumed invariant loads and other pointers as our runtime alias checks are sound in case the loads are actually invariant. Together with the invariant checks this combination allows to handle a lot more than LICM can. The code generation of the invariant loads had to be extended as we can now have dependences between parameters and invariant (hoisted) loads as well as the other way around, e.g., test/Isl/CodeGen/invariant_load_parameters_cyclic_dependence.ll First, it is important to note that we cannot have real cycles but only dependences from a hoisted load to a parameter and from another parameter to that hoisted load (and so on). To handle such cases we materialize llvm::Values for parameters that are referred by a hoisted load on demand and then materialize the remaining parameters. Second, there are new kinds of dependences between hoisted loads caused by the constraints on their execution. If a hoisted load is conditionally executed it might depend on the value of another hoisted load. To deal with such situations we sort them already in the ScopInfo such that they can be generated in the order they are listed in the Scop::InvariantAccesses list (see compareInvariantAccesses). The dependences between hoisted loads caused by indirect accesses are handled the same way as before. llvm-svn: 249607
* Consolidate the different ValueMapTypes we are usingTobias Grosser2015-10-041-3/+6
| | | | | | | | | | There have been various places where llvm::DenseMap<const llvm::Value *, llvm::Value *> types have been defined, but all types have been expected to be identical. We make this more clear by consolidating the different types and use BlockGenerator::ValueMapT wherever there is a need for types to match BlockGenerator::ValueMapT. llvm-svn: 249264
* Allow user defined error functionsJohannes Doerfert2015-10-011-6/+18
| | | | | | | | | | | | The user can provide function names with -polly-error-functions=name1,name2,name3 that will be treated as error functions. Any call to them is assumed not to be executed. This feature is mainly for developers to play around with the new "error block" feature. llvm-svn: 249098
* [FIX] Handle identity mappings in the ScopExpanderJohannes Doerfert2015-09-301-1/+2
| | | | | | | | If the VMap in the ScopExpander contains identity mappings we now ignore the mapping. Reported-by: Tobias Grosser <tobias@grosser.es> llvm-svn: 248946
* Move remapping functionality in the ScopExpanderJohannes Doerfert2015-09-301-4/+12
| | | | | | | | | Because we handle more than SCEV does it is not possible to rewrite an expression on the top-level using the SCEVParameterRewriter only. With this patch we will do the rewriting on demand only and also recursively, thus not only on the top-level. llvm-svn: 248916
* Allow switch instructions in SCoPsJohannes Doerfert2015-09-281-0/+14
| | | | | | | | | | | | | | | This patch allows switch instructions with affine conditions in the SCoP. Also switch instructions in non-affine subregions are allowed. Both did not require much changes to the code, though there was some refactoring needed to integrate them without code duplication. In the llvm-test suite the number of profitable SCoPs increased from 135 to 139 but more importantly we can handle more benchmarks and user inputs without preprocessing. Differential Revision: http://reviews.llvm.org/D13200 llvm-svn: 248701
* Runtime error check eliminationJohannes Doerfert2015-09-101-0/+14
| | | | | | | | | | | | | Hoist runtime checks in the loop nest if they guard an "error" like event. Such events are recognized as blocks with an unreachable terminator or a call to the ubsan function that deals with out of bound accesses. Other "error" events can be added easily. We will ignore these blocks when we detect/model/optmize and code generate SCoPs but we will make sure that they would not have been executed using the assumption framework. llvm-svn: 247310
* Allow general loops with one latchJohannes Doerfert2015-09-101-30/+0
| | | | | | | | | | | | | | | | | | | As we do not rely on ScalarEvolution any more we do not need to get the backedge taken count. Additionally, our domain generation handles everything that is affine and has one latch and our ScopDetection will over-approximate everything else. This change will therefor allow loops with: - one latch - exiting conditions that are affine Additionally, it will not check for structured control flow anymore. Hence, loops and conditionals are not necessarily single entry single exit regions any more. Differential Version: http://reviews.llvm.org/D12758 llvm-svn: 247289
* Introduce the ScopExpander as a SCEVExpander replacementJohannes Doerfert2015-08-181-0/+109
| | | | | | | | | | | | | | | The SCEVExpander cannot deal with all SCEVs Polly allows in all kinds of expressions. To this end we introduce a ScopExpander that handles the additional expressions separatly and falls back to the SCEVExpander for everything else. Reviewers: grosser, Meinersbur Subscribers: #polly Differential Revision: http://reviews.llvm.org/D12066 llvm-svn: 245288
* Revise the simplification of regionsMichael Kruse2015-08-111-79/+113
| | | | | | | | | | | | | | | | | | | | The previous code had several problems: For newly created BasicBlocks it did not (always) call RegionInfo::setRegionFor in order to update its analysis. At the moment RegionInfo does not verify its BBMap, but will in the future. This is fixed by determining the region new BBs belong to and set it accordingly. The new executeScopConditionally() requires accurate getRegionFor information. Which block is created by SplitEdge depends on the incoming and outgoing edges of the blocks it connects, which makes handling its output more difficult than it needs to be. Especially for finding which block has been created an to assign a region to it for the setRegionFor problem above. This patch uses an implementation for splitEdge that always creates a block between the predecessor and successor. simplifyRegion has also been simplified by using SplitBlockPredecessors instead of SplitEdge. Isolating the entries and exits have been refectored into individual functions. Previously simplifyRegion did more than just ensuring that there is only one entering and one exiting edge. It ensured that the entering block had no other outgoing edge which was necessary for executeScopConditionally(). Now the latter uses the alternative splitEdge implementation which can handle this situation so simplifyRegion really only needs to simplify the region. Also, executeScopConditionally assumed that there can be no PHI nodes in blocks with one incoming edge. This is wrong and LCSSA deliberately produces such edges. However, previous passes ensured that there can be no such PHIs in exit nodes, but which will no longer hold in the future. The new code that the property that it preserves the identity of region block (the property that the memory address of the BasicBlock containing the instructions remains the same; new blocks only contain PHI nodes and a terminator), especially the entry block. As a result, there is no need to update the reference to the BasicBlock of ScopStmt that contain its instructions because they have been moved to other basic blocks. Reviewers: grosser Part of Differential Revision: http://reviews.llvm.org/D11867 llvm-svn: 244606
* Introduce splitBlock and use it in splitEntryBlockForAllocaMichael Kruse2015-08-111-4/+36
| | | | | | | | | | | | | | RegionInfo::splitBlock did not update RegionInfo correctly. Specifically, it tried to make the new block the entry block if possible. This breaks for nested regions that have edges to the old block. We simply do not change the entry block. Updating RegionInfo becomes trivial as both block will always be in the same region. splitEntryBlockForAlloca makes use of the new splitBlock. Reviewers: grosser Part of Differential Revision: http://reviews.llvm.org/D11867 llvm-svn: 244600
* Use the branch instruction to define the location of a PHI-node writeTobias Grosser2015-08-021-8/+0
| | | | | | | | | | | | | | | | | | | We use the branch instruction as the location at which a PHI-node write takes place, instead of the PHI-node itself. This allows us to identify the basic-block in a region statement which is on the incoming edge of the PHI-node and for which the write access was originally introduced. As a result we can, during code generation, avoid generating PHI-node write accesses for basic blocks that do not preceed the PHI node without having to look at the IR again. This change fixes a bug which was introduced in r243420, when we started to explicitly model PHI-node reads and writes, but dropped some additional checks that where still necessary during code generation to not emit PHI-node writes for basic-blocks that are not on incoming edges of the original PHI node. Compared to the code before r243420 the new code does not need to inspect the IR any more and we also do not generate multiple redundant writes. llvm-svn: 243852
* [PM/AA] Update to reflect the new LLVM API which no longer requires anChandler Carruth2015-07-221-2/+1
| | | | | | AliasAnalysis pointer. llvm-svn: 242897
* Fix formattingTobias Grosser2015-02-251-1/+1
| | | | llvm-svn: 230504
* [FIX] Silence warningJohannes Doerfert2015-02-241-0/+1
| | | | llvm-svn: 230336
* [FIX] Create single exiting blockJohannes Doerfert2015-02-241-4/+3
| | | | llvm-svn: 230326
* [FIX] Correctly handle scalar dependences of branch instructionsJohannes Doerfert2015-02-111-0/+2
| | | | llvm-svn: 228866
* [PM] Update Polly for LLVM r226459 which removed another pass argumentChandler Carruth2015-01-191-6/+6
| | | | | | from an API in the process of preparing for the new pass manager. llvm-svn: 226460
* [PM] Update Polly for LLVM r226394 and r226396 which changed some of theChandler Carruth2015-01-181-3/+20
| | | | | | | block splitting interfaces to accept specific analyses rather than a pass. llvm-svn: 226398
* [Refactor][NFC] Generalize the creation of ScopArrayInfo objects.Johannes Doerfert2014-11-071-0/+6
| | | | | | Differential Revision: http://reviews.llvm.org/D6031 llvm-svn: 221512
* [Refactor][NFC] Map basic blocks to SCoP statements.Johannes Doerfert2014-10-311-5/+2
| | | | | | | This will simplify the construction of domains and the modeling of PHI's. llvm-svn: 221015
* [Refactor] Change the comment style to silence -WcommentJohannes Doerfert2014-10-071-2/+2
| | | | | | | | | -Wcomment complained about a "multi-line comment" caused by the ascii art used in ScopHelper to describe the CFG. Differential Revision: http://reviews.llvm.org/D5618 llvm-svn: 219207
* [Fix] Rewire the Region after a unconditional entry edge is createdJohannes Doerfert2014-09-151-11/+48
| | | | | | | | | | | | We use SplitEdge to split a conditional entry edge of the SCoP region. However, SplitEdge can cause two different situations (depending on whether or not the edge is critical). This patch tests which one is present and deals with the former unhandled one. It also refactors and unifies the case we have to change the basic blocks of the SCoP to new ones (see replaceScopAndRegionEntry). llvm-svn: 217802
* [Refactor] Cleanup isl code generationJohannes Doerfert2014-09-101-2/+14
| | | | | | | | | | | | | | | | | | | | Summary: + Refactor the runtime check (RTC) build function + Added helper function to create an PollyIRBuilder + Change the simplify region function to create not only unique entry and exit edges but also enfore that the entry edge is unconditional + Cleaned the IslCodeGeneration runOnScop function: - less post-creation changes of the created IR + Adjusted and added test cases Reviewers: grosser, sebpop, simbuerg, dpeixott Subscribers: llvm-commits, #polly Differential Revision: http://reviews.llvm.org/D5076 llvm-svn: 217508
* Update for RegionInfo changes.Matt Arsenault2014-07-191-2/+2
| | | | | | | Mostly related to missing includes and renaming of the pass to RegionInfoPass. llvm-svn: 213457
* [C++11] Use more range based forsTobias Grosser2014-06-281-5/+5
| | | | llvm-svn: 211981
* [Modules] Fix potential ODR violations by sinking the DEBUG_TYPEChandler Carruth2014-04-221-3/+3
| | | | | | | | | | definition below all of the header #include lines, Polly edition. If you want to know more details about this, you can see the recent commits to Debug.h in LLVM. This is just the Polly segment of a cleanup I'm doing globally for this macro. llvm-svn: 206852
* [Modules] Update to reflect the move of CFG.h to the IR library in LLVMChandler Carruth2014-03-041-1/+1
| | | | | | r202827. llvm-svn: 202830
* Sort includesTobias Grosser2013-05-071-1/+0
| | | | llvm-svn: 181297
* Reformat with clang-formatTobias Grosser2013-05-071-3/+3
| | | | | | | clang-format become way more stable. This time we mainly reformat function signatures. llvm-svn: 181294
* Support SCoPs with multiple entry edges.Tobias Grosser2013-04-161-0/+27
| | | | | | | | | | | | | | | | | | | | | Regions that have multiple entry edges are very common. A simple if condition yields e.g. such a region: if / \ then else \ / for_region This for_region contains two entry edges 'then' -> 'for_region' and 'else' -> 'for_region'. Previously we scheduled the RegionSimplify pass to translate such regions into simple regions. With this patch, we now support them natively when the region is in -loop-simplify form, which means the entry block should not be a loop header. Contributed by: Star Tan <tanmx_star@yeah.net> llvm-svn: 179586
* Remove dependence on canonical induction variableTobias Grosser2013-03-201-9/+0
| | | | | | | | When using the scev based code generation, we now do not rely on the presence of a canonical induction variable any more. This commit prepares the path to (conditionally) disable the induction variable canonicalization pass. llvm-svn: 177548
* ScopHelper: Remove some dead codeTobias Grosser2013-03-181-19/+0
| | | | llvm-svn: 177307
* Formatting fixesTobias Grosser2013-02-141-11/+14
| | | | llvm-svn: 175177
* Remove dead codeTobias Grosser2012-09-081-122/+0
| | | | | | This code has been replaced by the SCEVValidator a while ago. llvm-svn: 163471
* Update after LLVM API change.Benjamin Kramer2011-12-091-1/+1
| | | | llvm-svn: 146279
* Fix placement of the '*' that marks a pointerTobias Grosser2011-11-171-2/+2
| | | | | | Suggested by Sebastian Pop. llvm-svn: 144902
* CodeGeneration: Do not delete the old version of the Scop.Tobias Grosser2011-05-141-33/+0
| | | | | | | Instead of deleting the old code, keep it on the side in an if-branch. It will either be deleted by the dead code elimination or we can use it as fallback. llvm-svn: 131352
* Add initial version of PollyTobias Grosser2011-04-291-0/+280
This version is equivalent to commit ba26ebece8f5be84e9bd6315611d412af797147e in the old git repository. llvm-svn: 130476
OpenPOWER on IntegriCloud