summaryrefslogtreecommitdiffstats
path: root/polly/lib/CodeGen/BlockGenerators.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Let MemoryAccess remember its purposeMichael Kruse2015-09-251-3/+3
| | | | | | | | | | There are three possible reasons to add a memory memory access: For explicit load and stores, for llvm::Value defs/uses, and to emulate PHI nodes (the latter two called implicit accesses). Previously MemoryAccess only stored IsPHI. Register accesses could be identified through the isScalar() method if it was no IsPHI. isScalar() determined the number of dimensions of the underlaying array, scalars represented by zero dimensions. For the work on de-LICM, implicit accesses can have more than zero dimensions, making the distinction of isScalars() useless, hence now stored explicitly in the MemoryAccess. Instead, we replace it by isImplicit() and avoid the term scalar for zero-dimensional arrays as it might be confused with llvm::Value which are also often referred to as scalars (or alternatively, as registers). No behavioral change intended, under the condition that it was impossible to create explicit accesses to zero-dimensional "arrays". llvm-svn: 248616
* Merge IRAccess into MemoryAccessMichael Kruse2015-09-181-4/+4
| | | | | | | | | | | | | | | All MemoryAccess objects will be owned by ScopInfo::AccFuncMap which previously stored the IRAccess objects. Instead of creating new MemoryAccess objects, the already created ones are reused, but their order might be different now. Some fields of IRAccess and MemoryAccess had the same meaning and are merged. This is the last step of fusioning TempScopInfo.{h|cpp} and ScopInfo.{h.cpp}. Some refactoring might still make sense. Differential Revision: http://reviews.llvm.org/D12843 llvm-svn: 248024
* Store EscapeMap as Value* instead of AllocInstTobias Grosser2015-09-181-6/+6
| | | | | | | This currently does not change the behavior in Polly, but it allows us to later also overwrite the EscapeMap with our GlobalMap. llvm-svn: 247970
* [FIX] Handle error blocks in non-affine regions correctlyJohannes Doerfert2015-09-141-2/+10
| | | | llvm-svn: 247545
* Allow PHI nodes in the region exit blockJohannes Doerfert2015-09-081-2/+25
| | | | | | | | | | | | While we do not need to model PHI nodes in the region exit (as it is not part of the SCoP), we need to prepare for the case that the exit block is split in code generation to create a single exiting block. If this will happen, hence if the region did not have a single exiting block before, we will model the operands of the PHI nodes as escaping scalars in the SCoP. Differential Revision: http://reviews.llvm.org/D12051 llvm-svn: 247078
* Add option -polly-codegen-add-debug-printingTobias Grosser2015-09-061-0/+15
| | | | | | | | | | | | | When this option is enabled, Polly will emit printf calls for each scalar load/and store which dump the scalar value loaded/stored at run time. This patch also refactors the RuntimeDebugBuilder to use variadic templates when generating CPU printfs. As result, it now becomes easier to print strings that consist of a set of arguments. Also, as a single printf call is emitted, it is more likely for such strings to be emitted atomically if executed multi-threaded. llvm-svn: 246941
* RegionGenerator: Do not modify GlobalMapsTobias Grosser2015-09-051-5/+0
| | | | | | | | | | | | By inspection the update of the GlobalMaps in the RegionGenerator seems unneed, and is removed as also no test cases fail when dropping this. Johannes Doerfert confirmed that this is indeed save: "I think that code was needed when we did not use the scalar codegen by default. Now everything defined in a non-affine region should be communicated via memory and reloaded in the user block. Hence, we should be good removing this code." llvm-svn: 246926
* BlockGenerator: Make GlobalMap a member variableTobias Grosser2015-09-051-117/+81
| | | | | | | | | | | | | | | | | | | The GlobalMap variable used in BlockGenerator should always reference the same list througout the entire code generation, hence we can make it a member variable to avoid passing it around through every function call. History: Before we switched to the SCEV based code generation the GlobalMap also contained a mapping form old to new induction variables, hence it was different for each ScopStmt, which is why we passed it as function argument to copyStmt. The new SCEV based code generation now uses a separate mapping called LTS -> LoopToSCEV that maps each original loop to a new loop iteration variable provided as a SCEVExpr. The GlobalMap is currently mostly used for OpenMP code generation, where references to parameters in the original function need to be rewritten to the locations of these variables after they have been passed to the subfunction. Suggested-by: Johannes Doerfert <doerfert@cs.uni-saarland.de> llvm-svn: 246920
* Generate scalar initialization loads at the beginning of the start BBTobias Grosser2015-08-311-1/+1
| | | | | | | | | Our OpenMP code generation generated part of its launching code directly into the start basic block and without this change the scalar initialization was run _after_ the OpenMP threads have been launched. This resulted in uninitialized scalar values to be used. llvm-svn: 246427
* Add support for scalar dependences to OpenMP code generationTobias Grosser2015-08-311-26/+39
| | | | | | | | | | | | | | | Scalar dependences between scop statements have caused troubles during parallel code generation as we did not pass on the new stack allocation created for such scalars to the parallel subfunctions. This change now detects all scalar reads/writes in parallel subfunctions, creates the allocas for these scalar objects, passes the resulting memory locations to the subfunctions and ensures that within the subfunction requests for these memory locations will return the rewritten values. Johannes suggested as a future optimization to privatizing some of the scalars in the subfunction. llvm-svn: 246414
* Do not store into a temporary twineTobias Grosser2015-08-301-2/+2
| | | | | | For some reason, this causes memory corruption issues. Let's just avoid it. llvm-svn: 246396
* Store scalar dependences from outside the scop into alloca locationsTobias Grosser2015-08-301-13/+32
| | | | | | | | | | | | We already modeled read-only dependences to scalar values defined outside the scop as memory reads and also generated read accesses from the corresponding alloca instructions that have been used to pass these scalar values around during code generation. However, besides for PHI nodes that have already been handled, we failed to store the orignal read-only scalar values into these alloc. This commit extends the initialization of scalar values to all read-only scalar values used within the scop. llvm-svn: 246394
* getNewScalarValue: Get ScalarMap directly from member variable [NFC]Tobias Grosser2015-08-301-6/+4
| | | | | | | There is no need to pass the ScalarMap to getNewScalarValue as this map is (indirectly) used when calling getOrCreateScalarAlloca. llvm-svn: 246390
* createScalarInitialization: Always store PHI-node valueTobias Grosser2015-08-301-7/+3
| | | | | | | | | | | | | | | | | | | | | | | The current code really tries hard to use getNewScalarValue(), which checks if not the original value, but a possible copy or demoted value needs to be stored. In this calling context it seems, that we _always_ use the ScalarValue that comes from the incoming PHI node, but never any other value. As also no test cases fail, it seems right to just drop this call to getNewScalarValue and remove the parameters that are not needed any more. Johannes suggested that code like this might be needed for parallel code generation with offloading, but it was still unclear if/what exactly would be needed. As the parallel code generation does currently not support scalars at all, we will remove this code for now and add relevant code back when complitng the support of scalars in the parallel code generation. Reviewers: jdoerfert Subscribers: pollydev, llvm-commits Differential Revision: http://reviews.llvm.org/D12470 llvm-svn: 246389
* Ignore debug intrinsics and do not model their potential scalar metadata readsTobias Grosser2015-08-301-0/+3
| | | | | | | | | | Our code generation currently does not support scalar references to metadata values. Hence, it would crash if we try to model scalar dependences to metadata values. Fortunately, for one of the common uses, debug information, we can for now just ignore the relevant intrinsics and consequently the issue of how to model scalar dependences to metadata. llvm-svn: 246388
* Remove some code duplication [NFC]Tobias Grosser2015-08-301-21/+2
| | | | llvm-svn: 246387
* Minor code style improvement [NFC]Tobias Grosser2015-08-301-4/+3
| | | | llvm-svn: 246386
* Remove isNew from getOrCreateAllocaTobias Grosser2015-08-301-22/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This commit drops some dead code. Specifically, there is no need to initialize the virtual memory locations of scalars in BlockGenerator::handleOutsideUsers, the function that initalizes the escape map that keeps track of out-of-scope uses of scalar values. We already model instructions inside the scop that are used outside the scope (escaping instructions) as scalar memory writes at the position of the instruction. As a result, the virtual memory location of this instructions is already initialized when code-generating the corresponding virtual scalar write and consequently does not need to be initialized later on when generating the set of escaping values. Code references: In TempScopInfo::buildScalarDependences we detect scalar cross-statement dependences for all instructions (including PHIs) that have uses outside of the scop's region: // Check whether or not the use is in the SCoP. if (!R->contains(UseParent)) { AnyCrossStmtUse = true; continue; } We use this information in TempScopInfo::buildAccessFunctions were we build scalar write memory accesses for all these instructions: if (!isa<StoreInst>(Inst) && buildScalarDependences(Inst, &R, NonAffineSubRegion)) { // If the Instruction is used outside the statement, we need to build the // write access. IRAccess ScalarAccess(IRAccess::MUST_WRITE, Inst, ZeroOffset, 1, true, Inst); Functions.push_back(std::make_pair(ScalarAccess, Inst)); } Reviewers: jdoerfert Subscribers: pollydev, llvm-commits Differential Revision: http://reviews.llvm.org/D12472 llvm-svn: 246383
* Remove some code duplication when creating Allocas [NFC]Tobias Grosser2015-08-291-22/+13
| | | | llvm-svn: 246364
* BlockGenerator: Make scalar memory locations accessibleTobias Grosser2015-08-281-8/+15
| | | | | | | | | | For external users, the memory locations into which we generate scalar values may be of interest. This change introduces two functions that allow to obtain (or create) the AllocInsts for a given BasePointer. We use this change to simplify the code in BlockGenerators. llvm-svn: 246285
* BlockGenerator: Add the possiblity to pass a set of new access functionsTobias Grosser2015-08-271-85/+83
| | | | | | | | | | | | | | | | | | This change allows the BlockGenerator to be reused in contexts where we want to provide different/modified isl_ast_expressions, which are not only changed to a different access relation than the original statement, but which may indeed be different for each code-generated instance of the statement. We ensure testing of this feature by moving Polly's support to import changed access functions through a jscop file to use the BlockGenerators support for generating arbitary access functions if provided. This commit should not change the behavior of Polly for now. The diff is rather large, but most changes are due to us passing the NewAccesses hash table through functions. This style, even though rather verbose, matches what is done throughout the BlockGenerator with other per-statement properties. llvm-svn: 246144
* Fix 'unused variable' warning in NASSERTS buildTobias Grosser2015-08-211-3/+3
| | | | llvm-svn: 245723
* Move early exit to the beginning of the functionMichael Kruse2015-08-181-8/+7
| | | | | | If the function exits early there is no reason to enter the loop. llvm-svn: 245316
* Introduce the ScopExpander as a SCEVExpander replacementJohannes Doerfert2015-08-181-11/+10
| | | | | | | | | | | | | | | 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
* Add a field to the memory access class for a related value.Johannes Doerfert2015-08-171-19/+7
| | | | | | | | | | | | | | | | | | | | | The new field in the MemoryAccess allows us to track a value related to that access: - For real memory accesses the value is the loaded result or the stored value. - For straigt line scalar accesses it is the access instruction itself. - For PHI operand accesses it is the operand value. We use this value to simplify code which deduced information about the value later in the Polly pipeline and was known to be error prone. Reviewers: grosser, Meinsersbur Subscribers: #polly Differential Revision: http://reviews.llvm.org/D12062 llvm-svn: 245213
* [FIX] Create location if a needed value was not yet demotedJohannes Doerfert2015-08-171-3/+1
| | | | | | | | | | | | | | | | | This allows the code generation to continue working even if a needed value (that is reloaded anyway) was not yet demoted. Instead of failing it will now create the location for future demotion to memory and load from that location. The stores will use the same location and by construction execute before the load even if the textual order in the generated AST is otherwise. Reviewers: grosser, Meinersbur Subscribers: #polly Differential Revision: http://reviews.llvm.org/D12072 llvm-svn: 245203
* Remove trivially true conditionJohannes Doerfert2015-08-161-3/+1
| | | | llvm-svn: 245174
* Enable code generation of scalar dependences from function argumentsTobias Grosser2015-08-131-2/+2
| | | | | | | | | This change extends the BlockGenerator to not only allow Instructions as base elements of scalar dependences, but any llvm::Value. This allows us to code-generate scalar dependences which reference function arguments, as they arise when moddeling read-only scalar dependences. llvm-svn: 244874
* BlockGenerator: Do not store 'store' statements in BBMapTobias Grosser2015-08-111-12/+5
| | | | | | | A store statement has no return value and can consequently not be referenced from another statement. llvm-svn: 244576
* Add an assertionMichael Kruse2015-08-081-0/+1
| | | | | | Check whether a block is a direct predecessor. llvm-svn: 244401
* Optionally model read-only scalarsTobias Grosser2015-08-041-3/+3
| | | | | | | | | Even though read-only accesses to scalars outside of a scop do not need to be modeled to derive valid transformations or to generate valid sequential code, but information about them is useful when we considering memory footprint analysis and/or kernel offloading. llvm-svn: 243981
* Use the branch instruction to define the location of a PHI-node writeTobias Grosser2015-08-021-0/+4
| | | | | | | | | | | | | | | | | | | 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
* Only use instructions as insert locations for SCEVExpanderTobias Grosser2015-08-011-1/+3
| | | | | | | | | | | | | | | | | | | | | | | SCEVExpander, which we are using during code generation, only allows instructions as insert locations, but breaks in case BasicBlock->end() iterators are passed to it due to it trying to obtain the basic block in which code should be generated by calling Instruction->getParent(), which is not defined for ->end() iterators. This change adds an assert to Polly that ensures we only pass valid instructions to SCEVExpander and it fixes one case, where we used IRBuilder->SetInsertBlock() to set an ->end() insert location which was later passed to SCEVExpander. In general, Polly is always trying to build up the CFG first, before we actually insert instructions into the CFG sceleton. As a result, each basic block should already have at least one branch instruction before we start adding code. Hence, always requiring the IRBuilder insert location to be set to a real instruction should always be possible. Thanks Utpal Bora <cs14mtech11017@iith.ac.in> for his help with test case reduction. llvm-svn: 243830
* Fix typoTobias Grosser2015-08-011-1/+1
| | | | llvm-svn: 243829
* Keep track of ScopArrayInfo objects that model PHI node storageTobias Grosser2015-07-281-100/+22
| | | | | | | | | | | | | | | | | | | | | Summary: When translating PHI nodes into memory dependences during code generation we require two kinds of memory. 'Normal memory' as for all scalar dependences and 'PHI node memory' to store the incoming values of the PHI node. With this patch we now mark and track these two kinds of memories, which we previously incorrectly marked as a single memory object. Being aware of PHI node storage makes code generation easier, as we do not need to guess what kind of storage a scalar reference requires. This simplifies the code nicely. Reviewers: jdoerfert Subscribers: pollydev, llvm-commits Differential Revision: http://reviews.llvm.org/D11554 llvm-svn: 243420
* Simplify code in BlockGenerator::generateScalarLoads [NFC]Tobias Grosser2015-07-271-27/+16
| | | | | | | | | | | We hoist statements that are used on both branches of an if-condition, shorten and unify some variable names and fold some variable declarations into their only uses. We also drop a comment which just describes the elements the loop iterates over. No functional change intended. llvm-svn: 243291
* Add scalar and phi code generationJohannes Doerfert2015-05-221-17/+548
| | | | | | | | | | | | | | | | | | | | | | | | | | | | To reduce compile time and to allow more and better quality SCoPs in the long run we introduced scalar dependences and PHI-modeling. This patch will now allow us to generate code if one or both of those options are set. While the principle of demoting scalars as well as PHIs to memory in order to communicate their value stays the same, this allows to delay the demotion till the very end (the actual code generation). Consequently: - We __almost__ do not modify the code if we do not generate code for an optimized SCoP in the end. Thus, the early exit as well as the unprofitable option will now actually preven us from introducing regressions in case we will probably not get better code. - Polly can be used as a "pure" analyzer tool as long as the code generator is set to none. - The original SCoP is almost not touched when the optimized version is placed next to it. Runtime regressions if the runtime checks chooses the original are not to be expected and later optimizations do not need to revert the demotion for that part. - We will generate direct accesses to the demoted values, thus there are no "trivial GEPs" that select the first element of a scalar we demoted and treated as an array. Differential Revision: http://reviews.llvm.org/D7513 llvm-svn: 238070
* Sort include directivesTobias Grosser2015-05-091-5/+1
| | | | | | | | | | Upcoming revisions of isl require us to include header files explicitly, which have previously been already transitively included. Before we add them, we sort the existing includes. Thanks to Chandler for sort_includes.py. A simple, but very convenient script. llvm-svn: 236930
* Drop -polly-vectorizer-unroll-only optionTobias Grosser2015-03-231-2/+1
| | | | | | | | This options was earlier used for experiments with the vectorizer, but to my knowledge is not really used anymore. If anybody needs this, we can always reintroduce this feature. llvm-svn: 232934
* Drop option to prepare code for the BB vectorizerTobias Grosser2015-03-121-1/+1
| | | | | | | | The BB vectorizer is deprecated and there is no point in generating code for it any more. This option was introduced when there was not yet any loop vectorizer in sight. Now being matured, Polly should target the loop vectorizer. llvm-svn: 232099
* Fix compilation after DataLayout was added to ScevExpanderTobias Grosser2015-03-101-1/+8
| | | | | | The corresponding LLVM commit is 231740. llvm-svn: 231793
* [Refactor] Include explicitly what is usedJohannes Doerfert2015-03-011-4/+10
| | | | llvm-svn: 230901
* [FIX] Teach RegionGenerator to respect and update dominanceJohannes Doerfert2015-02-271-15/+54
| | | | | | | | | | | | | | | | When we generate code for a whole region we have to respect dominance and update it too. The first is achieved with multiple "BBMap"s. Each copied block in the region gets its own map. It is initialized only with values mapped in the immediate dominator block, if this block is in the region and was therefor already copied. This way no values defined in a block that doesn't dominate the current one will be used. To update dominance information we check if the immediate dominator of the original block we want to copy is in the region. If so we set the immediate dominator of the current block to the copy of the immediate dominator of the original block. llvm-svn: 230774
* Allow non-affine control flow -- Code GenerationJohannes Doerfert2015-02-241-5/+76
| | | | | | | | | | This is the code generation for region statements that are created when non-affine control flow was present in the input. A new generator, similar to the block or vector generator, for regions is used to traverse and copy the region statement and to adjust the control flow inside the new region in the end. llvm-svn: 230340
* [REFACTOR] Replace Pass* from BlockGen by the DomTreeJohannes Doerfert2015-02-231-11/+6
| | | | llvm-svn: 230220
* [Refactor] Use the LoopInfo object already presentJohannes Doerfert2015-02-081-10/+4
| | | | llvm-svn: 228540
* [Refactor] Use only one BlockGenerator for a SCoPJohannes Doerfert2015-02-061-93/+95
| | | | | | | | | | | | | | | | This change has two main purposes: 1) We do not use a static interface to hide an object we create and destroy for every basic block we copy. 2) We allow the BlockGenerator to store information between calls to the copyBB method. This will ease scalar/phi code generation later on. While a lot of method signatures were changed this should not cause any real behaviour change. Differential Revision: http://reviews.llvm.org/D7467 llvm-svn: 228443
* [FIX] Debug build + instrinsic handlingJohannes Doerfert2015-01-261-0/+24
| | | | | | | The ignored intrinsics needed to be ignored in three other places as well. Tests and lnt pass now. llvm-svn: 227092
* Support for math/misc intrinsicsJohannes Doerfert2015-01-251-0/+24
| | | | | | | | | The support is currently limited as we only allow them in the input but do not emit them in the transformed SCoP due to the possible semantic changes. Differential Revision: http://reviews.llvm.org/D5225 llvm-svn: 227054
* Remove redundant semicolon clang-format complained aboutTobias Grosser2015-01-181-2/+2
| | | | llvm-svn: 226402
OpenPOWER on IntegriCloud