summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Utils/LowerSwitch.cpp
Commit message (Collapse)AuthorAgeFilesLines
* 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
* improve portability to avoid conflicting with std::next in c++'0x.Chris Lattner2009-12-031-1/+1
| | | | | | Patch by Howard Hinnant! llvm-svn: 90365
* Remove FreeInst.Victor Hernandez2009-10-261-1/+0
| | | | | | | Remove LowerAllocations pass. Update some more passes to treate free calls just like they were treating FreeInst. llvm-svn: 85176
* Remove includes of Support/Compiler.h that are no longer needed after theNick Lewycky2009-10-251-1/+1
| | | | | | VISIBILITY_HIDDEN removal. llvm-svn: 85043
* Remove VISIBILITY_HIDDEN from class/struct found inside anonymous namespaces.Nick Lewycky2009-10-251-1/+1
| | | | | | | Chris claims we should never have visibility_hidden inside any .cpp file but that's still not true even after this commit. llvm-svn: 85042
* Eliminate the unused Context argument on one of the ICmpInst and FCmpInstDan Gohman2009-08-251-1/+1
| | | | | | constructors. llvm-svn: 80049
* Push LLVMContexts through the IntegerType APIs.Owen Anderson2009-08-131-3/+3
| | | | llvm-svn: 78948
* Remove now unused Context variables.Benjamin Kramer2009-07-291-1/+0
| | | | llvm-svn: 77495
* Move ConstantExpr to 2.5 API.Owen Anderson2009-07-291-2/+2
| | | | llvm-svn: 77494
* Fix a small little typo.Mike Stump2009-07-281-1/+1
| | | | llvm-svn: 77289
* Fix a release-asserts warning. Debug functions should be marked used,Mike Stump2009-07-271-0/+2
| | | | | | | if there are no other uses. If people don't need this routine anymore, if should be deleted. llvm-svn: 77274
* Avoid build warnings.Mike Stump2009-07-271-0/+1
| | | | llvm-svn: 77271
* Convert a few more uses of llvm/Support/Streams.h to raw_ostream.Dan Gohman2009-07-251-13/+5
| | | | llvm-svn: 77033
* Move more to raw_ostream, provide support for writing MachineBasicBlock,Daniel Dunbar2009-07-241-3/+6
| | | | | | LiveInterval, etc to raw_ostream. llvm-svn: 76965
* Get rid of the Pass+Context magic.Owen Anderson2009-07-221-3/+4
| | | | llvm-svn: 76702
* This started as a small change, I swear. Unfortunately, lots of things call ↵Owen Anderson2009-07-091-9/+10
| | | | | | the [I|F]CmpInst constructors. Who knew!? llvm-svn: 75200
* More LLVMContext-ification.Owen Anderson2009-07-051-2/+3
| | | | llvm-svn: 74807
* Now that errs() is properly non-buffered, there's no need toDan Gohman2009-03-231-2/+1
| | | | | | explicitly flush it. llvm-svn: 67526
* Tidy up several unbeseeming casts from pointer to intptr_t.Dan Gohman2008-09-041-1/+1
| | | | llvm-svn: 55779
OpenPOWER on IntegriCloud