summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Utils
Commit message (Collapse)AuthorAgeFilesLines
...
* Adds missing TLI check for library simplification ofMichael Kuperstein2013-08-191-3/+6
| | | | | | | * pow(x, 0.5) -> fabs(sqrt(x)) * pow(2.0, x) -> exp2(x) llvm-svn: 188656
* Remove SpecialCaseList::findCategory.Peter Collingbourne2013-08-191-35/+0
| | | | | | It turned out that I didn't need this for DFSan. llvm-svn: 188646
* Fixing a corner-case bug in strchr and strrchr lib call optimizations whereYunzhong Gao2013-08-151-2/+2
| | | | | | | | | the input character is not converted to char before comparing with zero. The patch was discussed in this thread: http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20130812/184069.html llvm-svn: 188489
* Fix small typo: s/succ/Succ/Mark Lacey2013-08-141-1/+1
| | | | llvm-svn: 188415
* Fix a really terrifying but improbable bug in mem2reg. If you have seenChandler Carruth2013-08-141-1/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | extremely subtle miscompilations (such as a load getting replaced with the value stored *below* the load within a basic block) related to promoting an alloca to an SSA value, there is the dim possibility that you hit this. Please let me know if you won this unfortunate lottery. The first half of mem2reg's core logic (as it is used both in the standalone mem2reg pass and in SROA) builds up a mapping from 'Instruction *' to the index of that instruction within its basic block. This allows quickly establishing which store dominate a particular load even for large basic blocks. We cache this information throughout the run of mem2reg over a function in order to amortize the cost of computing it. This is not in and of itself a strange pattern in LLVM. However, it introduces a very important constraint: absolutely no instruction can be deleted from the program without updating the mapping. Otherwise a newly allocated instruction might get the same pointer address, and then end up with a wrong index. Yes, LLVM routinely suffers from a *single threaded* variant of the ABA problem. Most places in LLVM don't find avoiding this an imposition because they don't both delete and create new instructions iteratively, but mem2reg *loves* to do this... All the time. Fortunately, the mem2reg code was really careful about updating this cache to handle this eventuallity... except when it comes to the debug declare intrinsic. Oops. The fix is to invalidate that pointer in the cache when we delete it, the same as we do when deleting alloca instructions and other instructions. I've also caused the same bug in new code while working on a fix to PR16867, so this seems to be a really unfortunate pattern. Hopefully in subsequent patches the deletion of dead instructions can be consolidated sufficiently to make it less likely that we'll see future occurences of this bug. Sorry for not having a test case, but I have literally no idea how to reliably trigger this kind of thing. It may be single-threaded, but it remains an ABA problem. It would require a really amazing number of stars to align. llvm-svn: 188367
* Revert r187191, which broke opt -mem2reg on the testcases included in PR16867.Nick Lewycky2013-08-132-169/+100
| | | | | | | | | | | | However, opt -O2 doesn't run mem2reg directly so nobody noticed until r188146 when SROA started sending more things directly down the PromoteMemToReg path. In order to revert r187191, I also revert dependent revisions r187296, r187322 and r188146. Fixes PR16867. Does not add the testcases from that PR, but both of them should get added for both mem2reg and sroa when this revert gets unreverted. llvm-svn: 188327
* Reapply r188119 now that the bug it exposed is fixed.Peter Collingbourne2013-08-121-12/+135
| | | | llvm-svn: 188217
* Remove unused SpecialCaseList constructorsAlexey Samsonov2013-08-121-20/+0
| | | | llvm-svn: 188171
* Add SpecialCaseList::createOrDie() factory and use it in sanitizer passesAlexey Samsonov2013-08-121-0/+7
| | | | llvm-svn: 188169
* Introduce factory methods for SpecialCaseListAlexey Samsonov2013-08-121-10/+43
| | | | | | | | | | | | | | | | | | | | Summary: Doing work in constructors is bad: this change suggests to call SpecialCaseList::create(Path, Error) instead of "new SpecialCaseList(Path)". Currently the latter may crash with report_fatal_error, which is undesirable - sometimes we want to report the error to user gracefully - for example, if he provides an incorrect file as an argument of Clang's -fsanitize-blacklist flag. Reviewers: pcc Reviewed By: pcc CC: llvm-commits Differential Revision: http://llvm-reviews.chandlerc.com/D1327 llvm-svn: 188156
* Revert r188119 "Kill some duplicated code for removing unreachable BBs."Arnold Schwaighofer2013-08-101-135/+12
| | | | | | | | | | | | | | It is breaking builbots with libgmalloc enabled on Mac OS X. $ cd llvm ; mkdir release ; cd release $ ../configure --enable-optimized —prefix=$PWD/install $ make $ make check $ Release+Asserts/bin/llvm-lit -v --param use_gmalloc=1 --param \ gmalloc_path=/usr/lib/libgmalloc.dylib \ ../test/Instrumentation/DataFlowSanitizer/args-unreachable-bb.ll llvm-svn: 188142
* Kill some duplicated code for removing unreachable BBs.Peter Collingbourne2013-08-091-12/+135
| | | | | | | | | | | This moves removeUnreachableBlocksFromFn from SimplifyCFGPass.cpp to Utils/Local.cpp and uses it to replace the implementation of llvm::removeUnreachableBlocks, which appears to do a strict subset of what removeUnreachableBlocksFromFn does. Differential Revision: http://llvm-reviews.chandlerc.com/D1334 llvm-svn: 188119
* Unbreak Debug build on WindowsSerge Pavlov2013-08-061-0/+1
| | | | llvm-svn: 187786
* Factor FlattenCFG out from SimplifyCFGTom Stellard2013-08-064-516/+593
| | | | | | Patch by: Mei Ye llvm-svn: 187764
* Introduce an optimisation for special case lists with large numbers of ↵Peter Collingbourne2013-08-051-13/+38
| | | | | | | | | | | | | | | | | | | | | | | | | | literal entries. Our internal regex implementation does not cope with large numbers of anchors very efficiently. Given a ~3600-entry special case list, regex compilation can take on the order of seconds. This patch solves the problem for the special case of patterns matching literal global names (i.e. patterns with no regex metacharacters). Rather than forming regexes from literal global name patterns, add them to a StringSet which is checked before matching against the regex. This reduces regex compilation time by an order of roughly thousands when reading the aforementioned special case list, according to a completely unscientific study. No test cases. I figure that any new tests for this code should check that regex metacharacters are properly recognised. However, I could not find any documentation which documents the fact that the syntax of global names in special case lists is based on regexes. The extent to which regex syntax is supported in special case lists should probably be decided on/documented before writing tests. Differential Revision: http://llvm-reviews.chandlerc.com/D1150 llvm-svn: 187732
* Fix dereferencing end iterator in SimplifyCFG. Patch by Ye Mei.Alexey Samsonov2013-08-021-5/+8
| | | | llvm-svn: 187646
* Teach getOrEnforceKnownAlignment about address spacesMatt Arsenault2013-08-011-4/+5
| | | | llvm-svn: 187629
* Fix -Wdocumentation warnings.Rafael Espindola2013-07-281-4/+4
| | | | llvm-svn: 187336
* Update comments for SSAUpdater to use the modern doxygen commentChandler Carruth2013-07-281-41/+3
| | | | | | | | | | | | standards for LLVM. Remove duplicated comments on the interface from the implementation file (implementation comments are left there of course). Also clean up, re-word, and fix a few typos and errors in the commenst spotted along the way. This is in preparation for changes to these files and to keep the uninteresting tidying in a separate commit. llvm-svn: 187335
* Thread DataLayout through the callers and into mem2reg. This will beChandler Carruth2013-07-282-10/+18
| | | | | | | useful in a subsequent patch, but causes an unfortunate amount of noise, so I pulled it out into a separate patch. llvm-svn: 187322
* Merge the removal of dead instructions and lifetime markers with theChandler Carruth2013-07-271-41/+32
| | | | | | | | | | | analysis of the alloca. We don't need to visit all the users twice for this. We build up a kill list during the analysis and then just process it afterward. This recovers the tiny bit of performance lost by moving to the visitor based analysis system as it removes one entire use-list walk from mem2reg. In some cases, this is now faster than mem2reg was previously. llvm-svn: 187296
* Reimplement isPotentiallyReachable to make nocapture deduction much stronger.Nick Lewycky2013-07-273-95/+3
| | | | | | | | | | Adds unit tests for it too. Split BasicBlockUtils into an analysis-half and a transforms-half, and put the analysis bits into a new Analysis/CFG.{h,cpp}. Promote isPotentiallyReachable into llvm::isPotentiallyReachable and move it into Analysis/CFG. llvm-svn: 187283
* SimplifyCFG: Use parallel-and and parallel-or mode to consolidate branch ↵Tom Stellard2013-07-271-11/+432
| | | | | | | | | | | | | | conditions Merge consecutive if-regions if they contain identical statements. Both transformations reduce number of branches. The transformation is guarded by a target-hook, and is currently enabled only for +R600, but the correctness has been tested on X86 target using a variety of CPU benchmarks. Patch by: Mei Ye llvm-svn: 187278
* Re-implement the analysis of uses in mem2reg to be significantly moreChandler Carruth2013-07-261-87/+157
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | robust. It now uses an InstVisitor and worklist to actually walk the uses of the Alloca transitively and detect the pattern which we can directly promote: loads & stores of the whole alloca and instructions we can completely ignore. Also, with this new implementation teach both the predicate for testing whether we can promote and the promotion engine itself to use the same code so we no longer have strange divergence between the two code paths. I've added some silly test cases to demonstrate that we can handle slightly more degenerate code patterns now. See the below for why this is even interesting. Performance impact: roughly 1% regression in the performance of SROA or ScalarRepl on a large C++-ish test case where most of the allocas are basically ready for promotion. The reason is because of silly redundant work that I've left FIXMEs for and which I'll address in the next commit. I wanted to separate this commit as it changes the behavior. Once the redundant work in removing the dead uses of the alloca is fixed, this code appears to be faster than the old version. =] So why is this useful? Because the previous requirement for promotion required a *specific* visit pattern of the uses of the alloca to verify: we *had* to look for no more than 1 intervening use. The end goal is to have SROA automatically detect when an alloca is already promotable and directly hand it to the mem2reg machinery rather than trying to partition and rewrite it. This is a 25% or more performance improvement for SROA, and a significant chunk of the delta between it and ScalarRepl. To get there, we need to make mem2reg actually capable of promoting allocas which *look* promotable to SROA without have SROA do tons of work to massage the code into just the right form. This is actually the tip of the iceberg. There are tremendous potential savings we can realize here by de-duplicating work between mem2reg and SROA. llvm-svn: 187191
* Respect llvm.used in Internalize.Rafael Espindola2013-07-251-0/+18
| | | | | | | | | | | | | | | The language reference says that: "If a symbol appears in the @llvm.used list, then the compiler, assembler, and linker are required to treat the symbol as if there is a reference to the symbol that it cannot see" Since even the linker cannot see the reference, we must assume that the reference can be using the symbol table. For example, a user can add __attribute__((used)) to a debug helper function like dump and use it from a debugger. llvm-svn: 187103
* Fix spellingMatt Arsenault2013-07-231-1/+1
| | | | llvm-svn: 186997
* Remove trailing spaces.Jakub Staszak2013-07-221-37/+37
| | | | llvm-svn: 186890
* mem2reg: Minor STL usage cleanup. No functionality change.Benjamin Kramer2013-07-211-11/+8
| | | | llvm-svn: 186790
* Make the mem2reg interface use an ArrayRef as it keeps a copy of theseChandler Carruth2013-07-211-5/+6
| | | | | | to iterate over. llvm-svn: 186788
* Hoist the rest of the logic for promoting single-store allocas into theChandler Carruth2013-07-211-23/+31
| | | | | | | | | | | | helper function. This leaves both trivial cases handled entirely in helper functions and merely manages the list of allocas to process in the run method. The next step will be to handle all of the trivial promotion work prior to even creating the core class and the subsequent simplifications that enables. llvm-svn: 186784
* Hoist the rest of the logic for fully promoting allocas with all uses inChandler Carruth2013-07-211-55/+33
| | | | | | | | | | | | | | a single block into the helper routine. This takes advantage of the fact that we can directly replace uses prior to any store with undef to simplify matters and unconditionally promote allocas only used within one block. I've removed the special handling for the case of no stores existing. This has no semantic effect but might slow things down. I'll fix that in a later patch when I refactor this entire thing to be easier to manage the different cases. llvm-svn: 186783
* Remove a method made dead by the prior refactoring.Chandler Carruth2013-07-211-5/+0
| | | | llvm-svn: 186782
* Hoist the two trivial promotion routines out of the big class thatChandler Carruth2013-07-201-161/+158
| | | | | | | | | | | | | | | handles the general cases. The hope is to refactor this so that we don't end up building the entire class for the trivial cases. I also want to lift a lot of the early pre-processing in the initial segment of run() into a separate routine, and really none of it needs to happen inside the primary promotion class. These routines in particular used none of the actual state in the promotion class, so they don't really make sense as members. llvm-svn: 186781
* Hoist the AllocaInfo struct to the top of the file.Chandler Carruth2013-07-201-59/+57
| | | | | | | | This struct is nicely independent of everything else, and we already needed a foward declaration here. It's simpler to just define it immediately. llvm-svn: 186780
* Sink a typedef and comparator down to the function that actually uses them.Chandler Carruth2013-07-201-8/+10
| | | | llvm-svn: 186779
* Don't allocate the DIBuilder on the heap and remove all the complexityChandler Carruth2013-07-201-16/+8
| | | | | | that ensued from that. llvm-svn: 186777
* Rename constructor parameters to follow the common member-shadowingChandler Carruth2013-07-201-3/+3
| | | | | | pattern and conform to the naming conventions. llvm-svn: 186776
* Reformat the implementation of mem2reg with clang-format so that myChandler Carruth2013-07-201-344/+360
| | | | | | subsequent changes don't introduce inconsistencies. llvm-svn: 186775
* Remove a DenseMapInfo specialization for std::pair -- we have one ofChandler Carruth2013-07-201-20/+0
| | | | | | those baked into DenseMap now. llvm-svn: 186773
* Update mem2reg's comments to conform to the new doxygen standards. NoChandler Carruth2013-07-201-74/+58
| | | | | | functionality changed. llvm-svn: 186772
* Make SpecialCaseList match full strings, as documented, using anchors.Peter Collingbourne2013-07-161-1/+1
| | | | | | Differential Revision: http://llvm-reviews.chandlerc.com/D1149 llvm-svn: 186431
* Add 'const' qualifier to some arrays.Craig Topper2013-07-151-1/+1
| | | | llvm-svn: 186312
* Use SmallVectorImpl& instead of SmallVector to avoid repeating small vector ↵Craig Topper2013-07-141-8/+9
| | | | | | size. llvm-svn: 186274
* Don't use a potentially expensive shift if all we want is one set bit.Benjamin Kramer2013-07-111-1/+1
| | | | | | No functionality change. llvm-svn: 186095
* TryToSimplifyUncondBranchFromEmptyBlock was checking that any commonDuncan Sands2013-07-111-23/+147
| | | | | | | | | | predecessors of the two blocks it is attempting to merge supply the same incoming values to any phi in the successor block. This change allows merging in the case where there is one or more incoming values that are undef. The undef values are rewritten to match the non-undef value that flows from the other edge. Patch by Mark Lacey. llvm-svn: 186069
* Implement categories for special case lists.Peter Collingbourne2013-07-091-26/+92
| | | | | | | | | | | | | | | | | | | | | | | | A special case list can now specify categories for specific globals, which can be used to instruct an instrumentation pass to treat certain functions or global variables in a specific way, such as by omitting certain aspects of instrumentation while keeping others, or informing the instrumentation pass that a specific uninstrumentable function has certain semantics, thus allowing the pass to instrument callers according to those semantics. For example, AddressSanitizer now uses the "init" category instead of global-init prefixes for globals whose initializers should not be instrumented, but which in all other respects should be instrumented. The motivating use case is DataFlowSanitizer, which will have a number of different categories for uninstrumentable functions, such as "functional" which specifies that a function has pure functional semantics, or "discard" which indicates that a function's return value should not be labelled. Differential Revision: http://llvm-reviews.chandlerc.com/D1092 llvm-svn: 185978
* Introduce a SpecialCaseList ctor which takes a MemoryBuffer to makePeter Collingbourne2013-07-091-1/+9
| | | | | | | | it more unit testable, and fix memory leak in the other ctor. Differential Revision: http://llvm-reviews.chandlerc.com/D1090 llvm-svn: 185976
* Rename BlackList class to SpecialCaseList and move it to Transforms/Utils.Peter Collingbourne2013-07-092-0/+127
| | | | | | Differential Revision: http://llvm-reviews.chandlerc.com/D1089 llvm-svn: 185975
* SimplifyCFG: Teach switch generation some patterns that instcombine forms.Benjamin Kramer2013-07-041-1/+27
| | | | | | | | This allows us to create switches even if instcombine has munged two of the incombing compares into one and some bit twiddling. This was motivated by enum compares that are common in clang. llvm-svn: 185632
* Use SmallVectorImpl::iterator/const_iterator instead of SmallVector to avoid ↵Craig Topper2013-07-044-5/+5
| | | | | | specifying the vector size. llvm-svn: 185606
OpenPOWER on IntegriCloud