summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Utils/LowerSwitch.cpp
Commit message (Collapse)AuthorAgeFilesLines
* TransformUtils: Remove implicit ilist iterator conversions, NFCDuncan P. N. Exon Smith2015-10-131-7/+6
| | | | | | | | | | | Continuing the work from last week to remove implicit ilist iterator conversions. First related commit was probably r249767, with some more motivation in r249925. This edition gets LLVMTransformUtils compiling without the implicit conversions. No functional change intended. llvm-svn: 250142
* don't repeat function names in comments; NFCSanjay Patel2015-09-161-29/+24
| | | | llvm-svn: 247813
* [LowerSwitch] Skip dead blocks for processSwitchInst()Chen Li2015-08-111-4/+10
| | | | | | | | | | | | Summary: This patch adds check for dead blocks and skip them for processSwitchInst(). This will help reduce compilation time. Reviewers: reames, hans Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D11953 llvm-svn: 244656
* [LowerSwitch] Fix a bug when LowerSwitch deletes the default blockChen Li2015-08-111-5/+10
| | | | | | | | | | | | Summary: LowerSwitch crashed with the attached test case after deleting the default block. This happened because the current implementation of deleting dead blocks is wrong. After the default block being deleted, it contains no instruction or terminator, and it should no be traversed anymore. However, since the iterator is advanced before processSwitchInst() function is executed, the block advanced to could be deleted inside processSwitchInst(). The deleted block would then be visited next and crash dyn_cast<SwitchInst>(Cur->getTerminator()) because Cur->getTerminator() returns a nullptr. This patch fixes this problem by recording dead default blocks into a list, and delete them after all processSwitchInst() has been done. It still possible to visit dead default blocks and waste time process them. But it is a compile time issue, and I plan to have another patch to add support to skip dead blocks. Reviewers: kariddi, resistor, hans, reames Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D11852 llvm-svn: 244642
* Fix some comment typos.Benjamin Kramer2015-08-081-3/+3
| | | | llvm-svn: 244402
* Revert r240137 (Fixed/added namespace ending comments using clang-tidy. NFC)Alexander Kornienko2015-06-231-1/+1
| | | | | | Apparently, the style needs to be agreed upon first. llvm-svn: 240390
* [SwitchLowering] Remove quadratic vector removal.Benjamin Kramer2015-06-201-12/+12
| | | | | | | This can be triggered with giant switches. No functionality change intended. llvm-svn: 240221
* LowerSwitch: Avoid some undefined behaviourJustin Bogner2015-06-201-1/+2
| | | | | | | | | | | | When a case of INT64_MIN was followed by a case that was greater than zero, we were overflowing a signed integer here. Since we've sorted the cases here anyway (and thus currentValue must be greater than nextValue) it's simple enough to avoid this by using addition rather than subtraction. Found by UBSAN on existing tests. llvm-svn: 240201
* Fixed/added namespace ending comments using clang-tidy. NFCAlexander Kornienko2015-06-191-1/+1
| | | | | | | | | | | | | The patch is generated using this command: tools/clang/tools/extra/clang-tidy/tool/run-clang-tidy.py -fix \ -checks=-*,llvm-namespace-comment -header-filter='llvm/.*|clang/.*' \ llvm/lib/ Thanks to Eugene Kosov for the original patch! llvm-svn: 240137
* Re-sort includes with sort-includes.py and insert raw_ostream.h where it's used.Benjamin Kramer2015-03-231-2/+2
| | | | llvm-svn: 232998
* [SwitchLowering] Remove incoming values in the reverse orderMichael Liao2015-03-171-1/+6
| | | | | | | - To prevent invalidating *successive* indices. llvm-svn: 232510
* LowerSwitch: Use ConstantInt for CaseRange::{Low,High}Hans Wennborg2015-02-051-20/+20
| | | | | | | Case values are always ConstantInt. This allows us to remove a bunch of casts. NFC. llvm-svn: 228312
* LowerSwitch: remove default args from CaseRange ctor; NFCHans Wennborg2015-02-051-3/+2
| | | | llvm-svn: 228311
* [LPM] Stop using the string based preservation API. It is anChandler Carruth2015-01-281-1/+0
| | | | | | | | | | | | | | | | | | | | | | | | | | | abomination. For starters, this API is incredibly slow. In order to lookup the name of a pass it must take a memory fence to acquire a pointer to the managed static pass registry, and then potentially acquire locks while it consults this registry for information about what passes exist by that name. This stops the world of LLVMs in your process no matter how little they cared about the result. To make this more joyful, you'll note that we are preserving many passes which *do not exist* any more, or are not even analyses which one might wish to have be preserved. This means we do all the work only to say "nope" with no error to the user. String-based APIs are a *bad idea*. String-based APIs that cannot produce any meaningful error are an even worse idea. =/ I have a patch that simply removes this API completely, but I'm hesitant to commit it as I don't really want to perniciously break out-of-tree users of the old pass manager. I'd rather they just have to migrate to the new one at some point. If others disagree and would like me to kill it with fire, just say the word. =] llvm-svn: 227294
* LowerSwitch: replace unreachable default with popular case destinationHans Wennborg2015-01-231-63/+135
| | | | | | | | | | | | SimplifyCFG currently does this transformation, but I'm planning to remove that to allow other passes, such as this one, to exploit the unreachable default. This patch takes care to keep track of what case values are unreachable even after the transformation, allowing for more efficient lowering. Differential Revision: http://reviews.llvm.org/D6697 llvm-svn: 226934
* [SwitchLowering] Handle destinations on multiple phi instructionsBruno Cardoso Lopes2014-12-021-2/+3
| | | | | | | | | Follow up from r222926. Also handle multiple destinations from merged cases on multiple and subsequent phi instructions. rdar://problem/19106978 llvm-svn: 223135
* [SwitchLowering] Handle multiple destinations on condensed case stmtsBruno Cardoso Lopes2014-11-281-12/+29
| | | | | | | | | | | | | | Switch cases statements with sequential values that branch to the same destination BB may often be handled together in a single new source BB. In this scenario we need to remove remaining incoming values from PHI instructions in the destination BB, as to match the number of source branches. Differential Revision: http://reviews.llvm.org/D6415 rdar://problem/19040894 llvm-svn: 222926
* [SwitchLowering] Fix the "fixPhis" function.Juergen Ributzka2014-11-101-8/+15
| | | | | | | | | | | | | | | Switch statements may have more than one incoming edge into the same BB if they all have the same value. When the switch statement is converted these incoming edges are now coming from multiple BBs. Updating all incoming values to be from a single BB is incorrect and would generate invalid LLVM IR. The fix is to only update the first occurrence of an incoming value. Switch lowering will perform subsequent calls to this helper function for each incoming edge with a new basic block - updating all edges in the process. This fixes rdar://problem/18916275. llvm-svn: 221627
* Fixup PHIs in LowerSwitch when a Leaf node is not emitted.Marcello Maggioni2014-07-111-10/+31
| | | | | | | | This commit fixes bug http://llvm.org/bugs/show_bug.cgi?id=20103. Thanks to Qwertyuiop for the report and the proposed fix. llvm-svn: 212802
* LowerSwitch: track bounding range for the condition tree.Jim Grosbach2014-06-161-27/+102
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | When LowerSwitch transforms a switch instruction into a tree of ifs it is actually performing a binary search into the various case ranges, to see if the current value falls into one cases range of values. So, if we have a program with something like this: switch (a) { case 0: do0(); break; case 1: do1(); break; case 2: do2(); break; default: break; } the code produced is something like this: if (a < 1) { if (a == 0) { do0(); } } else { if (a < 2) { if (a == 1) { do1(); } } else { if (a == 2) { do2(); } } } This code is inefficient because the check (a == 1) to execute do1() is not needed. The reason is that because we already checked that (a >= 1) initially by checking that also (a < 2) we basically already inferred that (a == 1) without the need of an extra basic block spawned to check if actually (a == 1). The patch addresses this problem by keeping track of already checked bounds in the LowerSwitch algorithm, so that when the time arrives to produce a Leaf Block that checks the equality with the case value / range the algorithm can decide if that block is really needed depending on the already checked bounds . For example, the above with "a = 1" would work like this: the bounds start as LB: NONE , UB: NONE as (a < 1) is emitted the bounds for the else path become LB: 1 UB: NONE. This happens because by failing the test (a < 1) we know that the value "a" cannot be smaller than 1 if we enter the else branch. After the emitting the check (a < 2) the bounds in the if branch become LB: 1 UB: 1. This is because by checking that "a" is smaller than 2 then the upper bound becomes 2 - 1 = 1. When it is time to emit the leaf block for "case 1:" we notice that 1 can be squeezed exactly in between the LB and UB, which means that if we arrived to that block there is no need to emit a block that checks if (a == 1). Patch by: Marcello Maggioni <hayarms@gmail.com> llvm-svn: 211038
* [C++] Use 'nullptr'. Transforms edition.Craig Topper2014-04-251-2/+3
| | | | llvm-svn: 207196
* [Modules] Make Support/Debug.h modular. This requires it to not changeChandler Carruth2014-04-211-0/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | behavior based on other files defining DEBUG_TYPE, which means it cannot define DEBUG_TYPE at all. This is actually better IMO as it forces folks to define relevant DEBUG_TYPEs for their files. However, it requires all files that currently use DEBUG(...) to define a DEBUG_TYPE if they don't already. I've updated all such files in LLVM and will do the same for other upstream projects. This still leaves one important change in how LLVM uses the DEBUG_TYPE macro going forward: we need to only define the macro *after* header files have been #include-ed. Previously, this wasn't possible because Debug.h required the macro to be pre-defined. This commit removes that. By defining DEBUG_TYPE after the includes two things are fixed: - Header files that need to provide a DEBUG_TYPE for some inline code can do so by defining the macro before their inline code and undef-ing it afterward so the macro does not escape. - We no longer have rampant ODR violations due to including headers with different DEBUG_TYPE definitions. This may be mostly an academic violation today, but with modules these types of violations are easy to check for and potentially very relevant. Where necessary to suppor headers with DEBUG_TYPE, I have moved the definitions below the includes in this commit. I plan to move the rest of the DEBUG_TYPE macros in LLVM in subsequent commits; this one is big enough. The comments in Debug.h, which were hilariously out of date already, have been updated to reflect the recommended practice going forward. llvm-svn: 206822
* [C++11] Add 'override' keyword to virtual methods that override their base ↵Craig Topper2014-03-051-3/+3
| | | | | | class. llvm-svn: 202953
* [C++11] Replace llvm::next and llvm::prior with std::next and std::prev.Benjamin Kramer2014-03-021-1/+2
| | | | | | Remove the old functions. llvm-svn: 202636
* Revert patches to add case-range support for PR1255.Bob Wilson2013-09-091-22/+40
| | | | | | | | | | | | | | | | | The work on this project was left in an unfinished and inconsistent state. Hopefully someone will eventually get a chance to implement this feature, but in the meantime, it is better to put things back the way the were. I have left support in the bitcode reader to handle the case-range bitcode format, so that we do not lose bitcode compatibility with the llvm 3.3 release. This reverts the following commits: 155464, 156374, 156377, 156613, 156704, 156757, 156804 156808, 156985, 157046, 157112, 157183, 157315, 157384, 157575, 157576, 157586, 157612, 157810, 157814, 157815, 157880, 157881, 157882, 157884, 157887, 157901, 158979, 157987, 157989, 158986, 158997, 159076, 159101, 159100, 159200, 159201, 159207, 159527, 159532, 159540, 159583, 159618, 159658, 159659, 159660, 159661, 159703, 159704, 160076, 167356, 172025, 186736 llvm-svn: 190328
* Move all of the header files which are involved in modelling the LLVM IRChandler Carruth2013-01-021-4/+4
| | | | | | | | | | | | | | | | | | | | | into their new header subdirectory: include/llvm/IR. This matches the directory structure of lib, and begins to correct a long standing point of file layout clutter in LLVM. There are still more header files to move here, but I wanted to handle them in separate commits to make tracking what files make sense at each layer easier. The only really questionable files here are the target intrinsic tablegen files. But that's a battle I'd rather not fight today. I've updated both CMake and Makefile build systems (I think, and my tests think, but I may have missed something). I've also re-sorted the includes throughout the project. I'll be committing updates to Clang, DragonEgg, and Polly momentarily. llvm-svn: 171366
* Use the new script to sort the includes of every file under lib.Chandler Carruth2012-12-031-2/+2
| | | | | | | | | | | | | | | | | Sooooo many of these had incorrect or strange main module includes. I have manually inspected all of these, and fixed the main module include to be the nearest plausible thing I could find. If you own or care about any of these source files, I encourage you to take some time and check that these edits were sensible. I can't have broken anything (I strictly added headers, and reordered them, never removed), but they may not be the headers you'd really like to identify as containing the API being implemented. Many forward declarations and missing includes were added to a header files to allow them to parse cleanly when included first. The main module rule does in fact have its merits. =] llvm-svn: 169131
* Reverted r156659, due to probable performance regressions, DenseMap should ↵Stepan Dyatkovskiy2012-07-041-5/+4
| | | | | | | | | | be used here: IntegersSubsetMapping - Replaced type of Items field from std::list with std::map. In neares future I'll test it with DenseMap and do the correspond replacement if possible. llvm-svn: 159703
* Part of r159527. Splitted into series of patches and gone with fixed PR13256:Stepan Dyatkovskiy2012-07-031-4/+5
| | | | | | | | IntegersSubsetMapping - Replaced type of Items field from std::list with std::map. In neares future I'll test it with DenseMap and do the correspond replacement if possible. llvm-svn: 159659
* Revert "IntRange:" as it appears to be breaking self hosting.Eric Christopher2012-07-021-5/+4
| | | | | | This reverts commit b2833d9dcba88c6f0520cad760619200adc0442c. llvm-svn: 159618
* IntRange:Stepan Dyatkovskiy2012-07-021-4/+5
| | | | | | | | | | | | | | | | | | | | | | - Changed isSingleNumber method behaviour. Now this flag is calculated on demand. IntegersSubsetMapping - Optimized diff operation. - Replaced type of Items field from std::list with std::map. - Added new methods: bool isOverlapped(self &RHS) void add(self& RHS, SuccessorClass *S) void detachCase(self& NewMapping, SuccessorClass *Succ) void removeCase(SuccessorClass *Succ) SuccessorClass *findSuccessor(const IntTy& Val) const IntTy* getCaseSingleNumber(SuccessorClass *Succ) IntegersSubsetTest - DiffTest: Added checks for successors. SimplifyCFG Updated SwitchInst usage (now it is case-ragnes compatible) for - SimplifyEqualityComparisonWithOnlyPredecessor - FoldValueComparisonIntoPredecessors llvm-svn: 159527
* PR1255: case ranges.Stepan Dyatkovskiy2012-06-021-3/+3
| | | | | | IntRange converted from struct to class. So main change everywhere is replacement of ".Low/High" with ".getLow/getHigh()" llvm-svn: 157884
* ConstantRangesSet renamed to IntegersSubset. CRSBuilder renamed to ↵Stepan Dyatkovskiy2012-05-291-5/+5
| | | | | | IntegersSubsetMapping. llvm-svn: 157612
* PR1255: Case RangesStepan Dyatkovskiy2012-05-281-1/+5
| | | | | | | | | | | | | | | | | | | | | | | | | Implemented IntItem - the wrapper around APInt. Why not to use APInt item directly right now? 1. It will very difficult to implement case ranges as series of small patches. We got several large and heavy patches. Each patch will about 90-120 kb. If you replace ConstantInt with APInt in SwitchInst you will need to changes at the same time all Readers,Writers and absolutely all passes that uses SwitchInst. 2. We can implement APInt pool inside and save memory space. E.g. we use several switches that works with 256 bit items (switch on signatures, or strings). We can avoid value duplicates in this case. 3. IntItem can be easyly easily replaced with APInt. 4. Currenly we can interpret IntItem both as ConstantInt and as APInt. It allows to provide SwitchInst methods that works with ConstantInt for non-updated passes. Why I need it right now? Currently I need to update SimplifyCFG pass (EqualityComparisons). I need to work with APInts directly a lot, so peaces of code ConstantInt *V = ...; if (V->getValue().ugt(AnotherV->getValue()) { ... } will look awful. Much more better this way: IntItem V = ConstantIntVal->getValue(); if (AnotherV < V) { } Of course any reviews are welcome. P.S.: I'm also going to rename ConstantRangesSet to IntegersSubset, and CRSBuilder to IntegersSubsetMapping (allows to map individual subsets of integers to the BasicBlocks). Since in future these classes will founded on APInt, it will possible to use them in more generic ways. llvm-svn: 157576
* PR1255 related changes (case ranges):Stepan Dyatkovskiy2012-05-241-40/+18
| | | | | | | LowerSwitch::Clusterify : main functinality was replaced with CRSBuilder::optimize, so big part of Clusterify's code was reduced. test/Transform/LowerSwitch/feature.ll - this test was refactored: grep + count was replaced with FileCheck usage. llvm-svn: 157384
* llvm::SwitchInstStepan Dyatkovskiy2012-03-111-1/+1
| | | | | | | Renamed methods caseBegin, caseEnd and caseDefault with case_begin, case_end, and case_default. Added some notes relative to case iterators. llvm-svn: 152532
* Taken into account Duncan's comments for r149481 dated by 2nd Feb 2012:Stepan Dyatkovskiy2012-03-081-4/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20120130/136146.html Implemented CaseIterator and it solves almost all described issues: we don't need to mix operand/case/successor indexing anymore. Base iterator class is implemented as a template since it may be initialized either from "const SwitchInst*" or from "SwitchInst*". ConstCaseIt is just a read-only iterator. CaseIt is read-write iterator; it allows to change case successor and case value. Usage of iterator allows totally remove resolveXXXX methods. All indexing convertions done automatically inside the iterator's getters. Main way of iterator usage looks like this: SwitchInst *SI = ... // intialize it somehow for (SwitchInst::CaseIt i = SI->caseBegin(), e = SI->caseEnd(); i != e; ++i) { BasicBlock *BB = i.getCaseSuccessor(); ConstantInt *V = i.getCaseValue(); // Do something. } If you want to convert case number to TerminatorInst successor index, just use getSuccessorIndex iterator's method. If you want initialize iterator from TerminatorInst successor index, use CaseIt::fromSuccessorIndex(...) method. There are also related changes in llvm-clients: klee and clang. llvm-svn: 152297
* SwitchInst refactoring.Stepan Dyatkovskiy2012-02-011-5/+5
| | | | | | | | | | | | | | | | | The purpose of refactoring is to hide operand roles from SwitchInst user (programmer). If you want to play with operands directly, probably you will need lower level methods than SwitchInst ones (TerminatorInst or may be User). After this patch we can reorganize SwitchInst operands and successors as we want. What was done: 1. Changed semantics of index inside the getCaseValue method: getCaseValue(0) means "get first case", not a condition. Use getCondition() if you want to resolve the condition. I propose don't mix SwitchInst case indexing with low level indexing (TI successors indexing, User's operands indexing), since it may be dangerous. 2. By the same reason findCaseValue(ConstantInt*) returns actual number of case value. 0 means first case, not default. If there is no case with given value, ErrorIndex will returned. 3. Added getCaseSuccessor method. I propose to avoid usage of TerminatorInst::getSuccessor if you want to resolve case successor BB. Use getCaseSuccessor instead, since internal SwitchInst organization of operands/successors is hidden and may be changed in any moment. 4. Added resolveSuccessorIndex and resolveCaseIndex. The main purpose of these methods is to see how case successors are really mapped in TerminatorInst. 4.1 "resolveSuccessorIndex" was created if you need to level down from SwitchInst to TerminatorInst. It returns TerminatorInst's successor index for given case successor. 4.2 "resolveCaseIndex" converts low level successors index to case index that curresponds to the given successor. Note: There are also related compatability fix patches for dragonegg, klee, llvm-gcc-4.0, llvm-gcc-4.2, safecode, clang. llvm-svn: 149481
* Clean up uses of switch instructions so they are not dependent on the ↵Eli Friedman2011-09-291-2/+2
| | | | | | operand ordering. Patch by Stepan Dyatkovskiy. llvm-svn: 140803
* Fix a ton of comment typos found by codespell. Patch byChris Lattner2011-04-151-1/+1
| | | | | | Luis Felipe Strano Moraes! llvm-svn: 129558
* Switch attribute macros to use 'LLVM_' as a prefix. We retain the old namesChandler Carruth2010-10-231-1/+2
| | | | | | until other LLVM projects using these are cleaned up. llvm-svn: 117200
* Get rid of static constructors for pass registration. Instead, every pass ↵Owen Anderson2010-10-191-1/+3
| | | | | | | | | | | | | | | | | exposes an initializeMyPassFunction(), which must be called in the pass's constructor. This function uses static dependency declarations to recursively initialize the pass's dependencies. Clients that only create passes through the createFooPass() APIs will require no changes. Clients that want to use the CommandLine options for passes will need to manually call the appropriate initialization functions in PassInitialization.h before parsing commandline arguments. I have tested this with all standard configurations of clang and llvm-gcc on Darwin. It is possible that there are problems with the static dependencies that will only be visible with non-standard options. If you encounter any crash in pass registration/creation, please send the testcase to me directly. llvm-svn: 116820
* Now with fewer extraneous semicolons!Owen Anderson2010-10-071-1/+1
| | | | llvm-svn: 115996
* Now that PassInfo and Pass::ID have been separated, move the rest of the ↵Owen Anderson2010-08-231-2/+2
| | | | | | passes over to the new registration API. llvm-svn: 111815
* remove some dead code.Chris Lattner2010-08-181-4/+2
| | | | llvm-svn: 111344
* Eliminate PromoteMemoryToRegisterID; just use addPreserved("mem2reg")Dan Gohman2010-08-061-1/+1
| | | | | | instead, as an example of what this looks like. llvm-svn: 110478
* Reapply r110396, with fixes to appease the Linux buildbot gods.Owen Anderson2010-08-061-2/+2
| | | | llvm-svn: 110460
* Revert r110396 to fix buildbots.Owen Anderson2010-08-061-2/+2
| | | | llvm-svn: 110410
* Don't use PassInfo* as a type identifier for passes. Instead, use the ↵Owen Anderson2010-08-051-2/+2
| | | | | | | | address of the static ID member as the sole unique type identifier. Clean up APIs related to this change. llvm-svn: 110396
* Change errs() to dbgs().David Greene2010-01-051-5/+5
| | | | llvm-svn: 92602
OpenPOWER on IntegriCloud