summaryrefslogtreecommitdiffstats
path: root/polly/lib/Analysis/ScopBuilder.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* [ScopInfo] Use statement lists for entry blocks of region statementsTobias Grosser2017-08-301-3/+11
| | | | | | | | | | | | | By using statement lists in the entry blocks of region statements, instruction level analyses also work on region statements. We currently only model the entry block of a region statements, as this is sufficient for most transformations the known-passes currently execute. Modeling instructions in the presence of control flow (e.g. infinite loops) is left out to not increase code complexity too much. It can be added when good use cases are found. llvm-svn: 312128
* [ScopBuilder/ScopInfo] Move reduction detection to ScopBuilder. NFC.Michael Kruse2017-08-301-1/+147
| | | | | | | | Reduction detection is only executed in the SCoP building phase. Hence it fits better into ScopBuilder to separate SCoP-construction from SCoP modeling. llvm-svn: 312118
* [ScopBuilder/ScopInfo] Move ScopStmt::collectSurroundingLoops to ↵Michael Kruse2017-08-301-1/+9
| | | | | | | | | | ScopBuilder. NFC. This method is only called in the SCoP building phase. Therefore it fits better into ScopBuilder to separate SCoP-construction from SCoP modeling. llvm-svn: 312117
* [ScopBuilder/ScopInfo] Move ScopStmt::buildDomain to ScopBuilder. NFC.Michael Kruse2017-08-301-1/+8
| | | | | | | | This method is only called in the SCoP building phase. Therefore it fits better into ScopBuilder to separate SCoP-construction from SCoP modeling. llvm-svn: 312116
* [ScopBuilder/ScopInfo] Move ScopStmt::buildAccessRelations to ScopBuilder. NFC.Michael Kruse2017-08-301-1/+22
| | | | | | | | | | | | This method is only called in the SCoP building phase. Therefore it fits better into ScopBuilder to separate SCoP-construction from SCoP modeling. This mostly mechanical change makes ScopBuilder directly access some of ScopStmt/MemoryAccess private fields. We add ScopBuilder as a friend class and will add proper accessor functions sometime later. llvm-svn: 312115
* [ScopBuilder/ScopInfo] Move and inline Scop::init into ↵Michael Kruse2017-08-301-2/+13
| | | | | | | | | ScopBuilder::buildScop. NFC. The method is only needed in the SCoP building phase, and doesn't need to be part of the general API. llvm-svn: 312114
* [ScopBuilder] Report to dbgs() on SCoP bailout. NFC.Michael Kruse2017-08-301-5/+17
| | | | | | | This allows to use -debug to see that a SCoP was found in ScopDetect, but dismissed by ScopBuilder. llvm-svn: 312113
* [ScopBuilder] Introduce metadata for splitting scop statement.Michael Kruse2017-08-301-1/+21
| | | | | | | | | | | | This patch allows annotating of metadata in ir instruction (with "polly_split_after"), which specifies where to split a particular scop statement. Contributed-by: Nandini Singhal <cs15mtech01004@iith.ac.in> Differential Revision: https://reviews.llvm.org/D36402 llvm-svn: 312107
* [PM] Properly require and preserve OptimizationRemarkEmitter. NFCI.Michael Kruse2017-08-281-10/+12
| | | | | | | | | | | | | | | | | | | | | | Properly require and preserve the OptimizationRemarkEmitter for use in ScopPass. Previously one had to get the ORE from ScopDetection because CodeGeneration did not mark it as preserved. It would need to be recomputed which results in the legacy PM to throw away all previous SCoP analysis. This also changes the implementation of ScopPass::getAnalysisUsage to not unconditionally preserve all passes, but only those needed to be preserved by any SCoP pass (at least when using the legacy PM). This allows invalidating DependenceInfo (and IslAstInfo) in case the pass would cause them to change (e.g. OpTree, DeLICM, MaximalArrayExpansion) JSONImporter should also invalidate the DependenceInfo. In this patch it marks DependenceInfo as preserved anyway because some regression tests depend on it. Differential Revision: https://reviews.llvm.org/D37010 llvm-svn: 311888
* [Polly] Fix some Clang-tidy modernize and Include What You Use warnings; ↵Eugene Zelenko2017-08-221-7/+44
| | | | | | other minor fixes (NFC). llvm-svn: 311489
* [ScopInfo] Move InvalidDomain to isl++ [NFC]Tobias Grosser2017-08-061-4/+3
| | | | llvm-svn: 310203
* [ScopBuilder/Simplify] Refactor isEscaping. NFC.Michael Kruse2017-07-271-21/+2
| | | | | | | | | | | | ScopBuilder and Simplify (through VirtualInstruction.cpp) previously used this functionality in their own implementation. Refactor them both into a common one into the Scop class. BlockGenerator also makes use of a similiar functionality, but also records outside users and takes place after region simplification. Merging it as well would be more complicated. llvm-svn: 309273
* [ScopInfo] Rename ScopStmt::contains(BB) to represents(BB). NFC.Michael Kruse2017-07-251-1/+1
| | | | | | | | | | | In future, there will be no more a 1:1 correspondence between statements and basic blocks, the name `contains` does not correctly capture their relationship. A BB may infact comprise of multiple statements; hence we describe a statement 'representing' a basic block. Differential Revision: https://reviews.llvm.org/D35838 llvm-svn: 308982
* [ForwardOpTree] Support read-only value uses.Michael Kruse2017-07-241-2/+13
| | | | | | | | | | | | Read-only values (values defined before the SCoP) require special handing with -polly-analyze-read-only-scalars=true (which is the default). If active, each use of a value requires a read access. When a copied value uses a read-only value, we must also ensure that such a MemoryAccess is available or is created. Differential Revision: https://reviews.llvm.org/D35764 llvm-svn: 308876
* [ScopInfo] Print instructions in dump().Michael Kruse2017-07-211-1/+1
| | | | | | | | | | | | | | | | | | | Print a statement's instruction on dump() regardless of -polly-print-instructions. dump() is supposed to be used in the debugger only and never in regression tests. While debugging, get all the information we have and we are not bound to break anything. For non-dump purposes of print, forward the setting of -polly-print-instructions as parameters. Some calls to print() had to be changed because the PollyPrintInstructions setting is only available in ScopInfo.cpp. In ScheduleOptimizer.cpp, dump() was used in regression tests. That's not what dump() is for. The print parameter "PrintInstructions" will also be useful for an explicit print SCoP pass in a future patch. llvm-svn: 308746
* [ScopBuilder] Avoid use of getStmtFor(BB). NFC.Michael Kruse2017-07-201-4/+4
| | | | | | | | | | | | | Since there will be no more a 1:1 correspondence between statements and basic blocks, we would like to get rid of the method getStmtFor(BB) and its uses. Here we remove one of its uses in ScopBuilder by fetching the statement in which the instruction lies. Contributed-by: Nandini Singhal <cs15mtech01004@iith.ac.in> Differential Revision: https://reviews.llvm.org/D35610 llvm-svn: 308610
* [Polly] [OptDiag] Updating Polly Diagnostics RemarksEli Friedman2017-07-171-7/+13
| | | | | | | | | | | | | | | | | Utilizing newer LLVM diagnostic remark API in order to enable use of opt-viewer tool. Polly Diagnostic Remarks also now appear in YAML remark file. In this patch, I've added the OptimizationRemarkEmitter into certain classes where remarks are being emitted and update the remark emit calls itself. I also provide each remark a BasicBlock or Instruction from where it is being called, in order to compute the hotness of the remark. Patch by Tarun Rajendran! Differential Revision: https://reviews.llvm.org/D35399 llvm-svn: 308233
* ScopInfo: Remove not-in-DomainMap statements in separate functionTobias Grosser2017-07-161-0/+1
| | | | | | This separates ScopBuilder internal and ScopBuilder external functionality. llvm-svn: 308152
* [Polly] Use Isl c++ for InvalidDomainMapTobias Grosser2017-07-151-12/+5
| | | | | | | | | | | | | | Reviewers: grosser, Meinersbur, bollu Subscribers: maxf, pollydev Tags: #polly Contributed-by: Nandini Singhal <cs15mtech01004@iith.ac.in> Differential Revision: https://reviews.llvm.org/D35308 llvm-svn: 308089
* [ScopInfo] Do not use ScopStmt in Domain derivation of ScopInfo. NFCMichael Kruse2017-06-291-6/+29
| | | | | | | | | | | | | | ScopStmts were being used in the computation of the Domain of the SCoPs in ScopInfo. Once statements are split, there will not be a 1-to-1 correspondence between Stmts and Basic blocks. Thus this patch avoids the use of getStmtFor() by creating a map of BB to InvalidDomain and using it to compute the domain of the statements. Contributed-by: Nanidini Singhal <cs15mtech01004@iith.ac.in> Differential Revision: https://reviews.llvm.org/D33942 llvm-svn: 306667
* [ScopBuilder] Pass ScopStmts around instead of BasicBlocks. NFC.Michael Kruse2017-06-231-73/+85
| | | | | | | | | | | | | | | | | | | | | | | During the construction of MemoryAccesses in ScopBuilder, BasicBlocks were used in function parameters, assuming that the ScopStmt an be directly derived from it. This won't be true anymore once we split BasicBlocks into multiple ScopStmt. As a preparation for such a change in the future, we instead pass the ScopStmt and avoid the use of getStmtFor(). There are two occasions where a kind of mapping from BasicBlock to ScopStmt is still required. 1. Get the statement representing the incoming block of a `PHINode` using `getLastStmtOf`. 2. One statement is required to write a scalar to be readable by those which need it. This is most often the statement which contains its definition, which we get using `getStmtFor(Instruction*)`. Differential Revision: https://reviews.llvm.org/D34369 llvm-svn: 306132
* Fix a lot of typos. NFC.Michael Kruse2017-06-081-1/+1
| | | | llvm-svn: 304974
* [ScopBuilder] Exclude ignored intrinsics from explicit instruction list.Michael Kruse2017-06-011-1/+2
| | | | | | | | | | | | | | Ignored intrinsics are ignored at code generation, therefore do not need to be part of the instruction list. Specifically, llvm.lifetime.* intrinisics are removed before code generation, referencing them would cause a use-after-free error. Contributed-by: Nandini Singhal <cs15mtech01004@iith.ac.in> Differential Revision: https://reviews.llvm.org/D33768 llvm-svn: 304483
* [ScopInfo] Do not add terminator & synthesizable instructions to the output ↵Michael Kruse2017-05-291-2/+5
| | | | | | | | | | | instructions. Such instructions are generates on-demand by the CodeGenerator and thus do not need representation in a statement. Differential Revision: https://reviews.llvm.org/D33642 llvm-svn: 304151
* Delinearize memory accesses that reference parameters coming from function callsTobias Grosser2017-05-271-0/+7
| | | | | | | | | | | | | | Certain affine memory accesses which we model today might contain products of parameters which we might combined into a new parameter to be able to create an affine expression that represents these memory accesses. Especially in the context of OpenCL, this approach looses information as memory accesses such as A[get_global_id(0) * N + get_global_id(1)] are assumed to be linear. We correctly recover their multi-dimensional structure by assuming that parameters that are the result of a function call at IR level likely are not parameters, but indeed induction variables. The resulting access is now A[get_global_id(0)][get_global_id(1)] for an array A[][N]. llvm-svn: 304075
* [Polly] Added the list of Instructions to output in ScopInfo passTobias Grosser2017-05-271-1/+5
| | | | | | | | | | | | Summary: This patch outputs all the list of instructions in BlockStmts. Reviewers: Meinersbur, grosser, bollu Subscribers: bollu, llvm-commits, pollydev Differential Revision: https://reviews.llvm.org/D33163 llvm-svn: 304062
* [Polly] Add handling of Top Level RegionsPhilip Pfaffe2017-05-241-6/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: My goal is to make the newly added `AllowWholeFunctions` options more usable/powerful. The changes to ScopBuilder.cpp are exclusively checks to prevent `Region.getExit()` from being dereferenced, since Top Level Regions (TLRs) don't have an exit block. In ScopDetection's `isValidCFG`, I removed a check that disallowed ReturnInstructions to have return values. This might of course have been intentional, so I would welcome your feedback on this and maybe a small explanation why return values are forbidden. Maybe it can be done but needs more changes elsewhere? The remaining changes in ScopDetection are simply to consider the AllowWholeFunctions option in more places, i.e. allow TLRs when it is set and once again avoid derefererncing `getExit()` if it doesn't exist. Finally, in ScopHelper.cpp I extended `polly::isErrorBlock` to handle regions without exit blocks as well: The original check was if a given BasicBlock dominates all predecessors of the exit block. Therefore I do the same for TLRs by regarding all BasicBlocks terminating with a ReturnInst as predecessors of a "virtual" function exit block. Patch by: Lukas Boehm Reviewers: philip.pfaffe, grosser, Meinersbur Reviewed By: grosser Subscribers: pollydev, llvm-commits, bollu Tags: #polly Differential Revision: https://reviews.llvm.org/D33411 llvm-svn: 303790
* [Fortran Support] Change "global" pattern match to work for paramsSiddharth Bhat2017-05-181-44/+4
| | | | | | | | | | | | | | | | | | Summary: - Rename global / local naming convention that did not make much sense to Visible / Invisible, where the visible refers to whether the ALLOCATE call to the Fortran array is present in the current module or not. - This match now works on both cross fortran module globals and on parameters to functions since neither of them are necessarily allocated at the point of their usage. - Add testcase that matches against both a load and a store against function parameters. Differential Revision: https://reviews.llvm.org/D33190 llvm-svn: 303356
* [Fortran Support] Add pattern match for Fortran Arrays that are parameters.Siddharth Bhat2017-05-151-69/+66
| | | | | | | | | | | - This breaks the previous assumption that Fortran Arrays are `GlobalValue`. - The names of functions were getting unwieldy. So, I renamed the Fortran related functions. Differential Revision: https://reviews.llvm.org/D33075 llvm-svn: 303040
* [Fortran Support] Detect Fortran arrays & metadata from dragonegg outputSiddharth Bhat2017-05-101-3/+243
| | | | | | | | | | | | | | Add the ability to tag certain memory accesses as those belonging to Fortran arrays. We do this by pattern matching against known patterns of Dragonegg's LLVM IR output from Fortran code. Fortran arrays have metadata stored with them in a struct. This struct is called the "Fortran array descriptor", and a reference to this is stored in each MemoryAccess. Differential Revision: https://reviews.llvm.org/D32639 llvm-svn: 302653
* [Polly] Canonicalize arrays according to base-ptr equivalence classTobias Grosser2017-05-101-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: In case two arrays share base pointers in the same invariant load equivalence class, we canonicalize all memory accesses to the first of these arrays (according to their order in the equivalence class). This enables us to optimize kernels such as boost::ublas by ensuring that different references to the C array are interpreted as accesses to the same array. Before this change the runtime alias check for ublas would fail, as it would assume models of the C array with differing (but identically valued) base pointers would reference distinct regions of memory whereas the referenced memory regions were indeed identical. As part of this change we remove most of the MemoryAccess::get*BaseAddr interface. We removed already all references to get*BaseAddr in previous commits to ensure that no code relies on matching base pointers between memory accesses and scop arrays -- except for three remaining uses where we need the original base pointer. We document for these situations that MemoryAccess::getOriginalBaseAddr may return a base pointer that is distinct to the base pointer of the scop array referenced by this memory access. Reviewers: sebpop, Meinersbur, zinob, gareevroman, pollydev, huihuiz, efriedma, jdoerfert Reviewed By: Meinersbur Subscribers: etherzhhb Tags: #polly Differential Revision: https://reviews.llvm.org/D28518 llvm-svn: 302636
* [ScopBuilder] Move Scop::init to ScopBuilder. NFC.Michael Kruse2017-05-051-7/+57
| | | | | | | | | | | Scop::init is used only during SCoP construction. Therefore ScopBuilder seems the more appropriate place for it. We integrate it onto its only caller ScopBuilder::buildScop where some other construction steps already took place. Differential Revision: https://reviews.llvm.org/D32908 llvm-svn: 302276
* [ScopBuilder] Do not verify unfeasible SCoPs.Michael Kruse2017-05-051-0/+6
| | | | | | | | | | | | | | | | SCoPs with unfeasible runtime context are thrown away and therefore do not need their uses verified. The added test case requires a complexity limit to exceed. Normally, error statements are removed from the SCoP and for that reason are skipped during the verification. If there is a unfeasible runtime context (here: because of the complexity limit being reached), the removal of error statements and other SCoP construction steps are skipped to not waste time. Error statements are not modeled in SCoPs and therefore have no requirements on whether the scalars used in them are available. llvm-svn: 302234
* [ScopBuilder] Add missing semicolon after LLVM_FALLTHROUGH.Michael Kruse2017-05-041-1/+1
| | | | | | It was forgotten in r302157. llvm-svn: 302163
* Introduce VirtualUse. NFC.Michael Kruse2017-05-041-43/+104
| | | | | | | | | | | | | | | | | | | If a ScopStmt references a (scalar) value, there are multiple possibilities where this value can come. The decision about what kind of use it is must be handled consistently at different places, which can be error-prone. VirtualUse is meant to centralize the handling of the different types of value uses. This patch makes ScopBuilder and CodeGeneration use VirtualUse. This already helps to show inconsistencies with the value handling. In order to keep this patch NFC, exceptions to the general rules are added. These might be fixed later if they turn to problems. Overall, this should result in fewer post-codegen IR-verification errors, but instead assertion failures in `getNewValue` that are closer to the actual error. Differential Revision: https://reviews.llvm.org/D32667 llvm-svn: 302157
* [ScopInfo] Remove code not needed anymore after r302004Tobias Grosser2017-05-031-6/+2
| | | | llvm-svn: 302005
* Revert "Remove references to AssumptionCache. NFC."Michael Kruse2017-03-171-6/+6
| | | | | | | | | | The AssumptionCache removal of r289756 has been reverted in r290086/r290087. A different solution has been implemented in r291671 which keeps the AssumptionCache. We can therefore use it again in Polly. This reverts r289791. llvm-svn: 298089
* [ScopInfo] Introduce ScopStmt::getSurroundingLoop(). NFC.Michael Kruse2017-03-151-25/+39
| | | | | | | | | | | | | | Introduce ScopStmt::getSurroundingLoop() to replace getFirstNonBoxedLoopFor. getSurroundingLoop() returns the precomputed surrounding/first non-boxed loop. Except in ScopDetection, the list of boxed loops is only used to get the surrounding loop. getFirstNonBoxedLoopFor also requires LoopInfo at every use which is not necessarily available everywhere where we may want to use it. Differential Revision: https://reviews.llvm.org/D30985 llvm-svn: 297899
* Tidy up getFirstNonBoxedLoopFor [NFC]Eli Friedman2017-01-161-11/+0
| | | | | | | | | | | | Move the function getFirstNonBoxedLoopFor which is used in ScopBuilder and in ScopInfo to Support/ScopHelpers to make it reusable in other locations. No functionality change. Patch by Sameer Abu Asal. Differential Revision: https://reviews.llvm.org/D28754 llvm-svn: 292168
* Use typed enums to model MemoryKind and move MemoryKind out of ScopArrayInfoTobias Grosser2017-01-141-15/+16
| | | | | | | | | | | | | | | | | | To benefit of the type safety guarantees of C++11 typed enums, which would have caught the type mismatch fixed in r291960, we make MemoryKind a typed enum. This change also allows us to drop the 'MK_' prefix and to instead use the more descriptive full name of the enum as prefix. To reduce the amount of typing needed, we use this opportunity to move MemoryKind from ScopArrayInfo to a global scope, which means the ScopArrayInfo:: prefix is not needed. This move also makes historically sense. In the beginning of Polly we had different MemoryKind enums in both MemoryAccess and ScopArrayInfo, which were later canonicalized to one. During this canonicalization we just choose the enum in ScopArrayInfo, but did not consider to move this shared enum to global scope. Reviewed-by: Michael Kruse <llvm@meinersbur.de> Differential Revision: https://reviews.llvm.org/D28090 llvm-svn: 292030
* Fix some typos in commentsTobias Grosser2017-01-061-1/+1
| | | | llvm-svn: 291247
* Remove references to AssumptionCache. NFC.Michael Kruse2016-12-151-6/+6
| | | | | | | | | | The AssumptionCache was removed in r289756 after being replaced by the an addtional operand list of affected values in r289755. The absence of that cache means that we have now have to manually search for llvm.assume intrinsics as now done by other passes (LazyValueInfo, CodeMetrics) do not take into account an llvm::Instruction's user lists (ScalarEvolution). llvm-svn: 289791
* canSynthesize: Remove unused argument LI. NFC.Michael Kruse2016-11-291-2/+2
| | | | | | | The helper function polly::canSynthesize() does not directly use the LoopInfo analysis, hence remove it from its argument list. llvm-svn: 288144
* Split ScopInfo::addScopStmt into two versions. NFCHongbin Zheng2016-11-211-2/+2
| | | | | | One for adding statement for region, another one for BB llvm-svn: 287566
* [NFC] Adjust naming scheme of statistic variablesJohannes Doerfert2016-11-181-2/+2
| | | | | Suggested-by: Tobias Grosser <tobias@grosser.es> llvm-svn: 287347
* [DBG] Collect statistics about statically infeasible SCoPsJohannes Doerfert2016-11-171-0/+3
| | | | llvm-svn: 287263
* [ScopBuilder] Drop unnecessary namespace identifiers [NFC]Tobias Grosser2016-11-131-8/+8
| | | | llvm-svn: 286781
* [ScopDetect] Conservatively handle inaccessible memory alias attributesTobias Grosser2016-11-131-0/+2
| | | | | | | | | | | Commit r286294 introduced support for inaccessiblememonly and inaccessiblemem_or_argmemonly attributes to BasicAA, which we need to support to avoid undefined behavior. This change just refuses all calls which are annotated with these attributes, which is conservatively correct. In the future we may consider to model and support such function calls in Polly. llvm-svn: 286771
* [ScopInfo] Make memset etc. affine where possible.Eli Friedman2016-11-011-4/+6
| | | | | | | | | We don't actually check whether a MemoryAccess is affine in very many places, but one important one is in checks for aliasing. Differential Revision: https://reviews.llvm.org/D25706 llvm-svn: 285746
* [ScopInfo/CodeGen] ExitPHI reads are implicit.Michael Kruse2016-10-121-6/+2
| | | | | | | | | | | | | | | | | Under some conditions MK_Value read accessed where converted to MK_ExitPHI read accessed. This is unexpected because MK_ExitPHI read accesses are implicit after the scop execution. This behaviour was introduced in r265261, which fixed a failed assertion/crash in CodeGen. Instead, we fix this failure in CodeGen itself. createExitPHINodeMerges(), despite its name, also handles accesses of kind MK_Value, only to skip them because they access values that are usually not PHI nodes in the SCoP region's exit block. Except in the situation observed in r265261. Do not convert value accessed to ExitPHI accesses and do not handle value accesses like ExitPHI accessed in CodeGen anymore. llvm-svn: 284023
OpenPOWER on IntegriCloud