aboutsummaryrefslogtreecommitdiff
path: root/lib/Transforms/Utils/SimplifyCFG.cpp
AgeCommit message (Collapse)Author
2012-09-26SimplifyCFG: Make the switch-to-lookup table transformation store theHans Wennborg
tables in bitmaps when they fit in a target-legal register. This saves some space, and it also allows for building tables that would otherwise be deemed too sparse. One interesting case that this hits is example 7 from http://blog.regehr.org/archives/320. We currently generate good code for this when lowering the switch to the selection DAG: we build a bitmask to decide whether to jump to one block or the other. My patch will result in the same bitmask, but it removes the need for the jump, as the return value can just be retrieved from the mask. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164684 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-26SimplifyCFG: Refactor the switch-to-lookup table transformation byHans Wennborg
breaking out the building of lookup tables into a separate class. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164682 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-20SimplifyCFG: sink common codes from IF, ELSE blocks down to END block.Manman Ren
We already have HoistThenElseCodeToIf, this patch implements SinkThenElseCodeToEnd. When END block has only two predecessors and each predecessor terminates with unconditional branches, we compare instructions in IF and ELSE blocks backwards and check whether we can sink the common instructions down. rdar://12191395 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164325 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-19SimplifyCFG: Don't generate invalid code for switch used to initializeHans Wennborg
two variables where the first variable is returned and the second ignored. I don't think this occurs in practice (other passes should have cleaned up the unused phi node), but it should still be handled correctly. Also make the logic for determining if we should return early less sketchy. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164225 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-18PGO: preserve branch-weight metadata when simplifying Switch to a sub, an icmpManman Ren
and a conditional branch; also when removing dead cases from a switch. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164084 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-17PGO: preserve branch-weight metadata when simplifying SwitchManman Ren
Hanlde the case when we split the default edge if the default target has "icmp" and unconditinal branch. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164076 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-17PGO: preserve branch-weight metadata when simplifying SwitchOnSelect.Manman Ren
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164068 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-17PGO: preserve branch-weight metadata when simplifying two branches with a commonManman Ren
destination in SimplifyCondBranchToCondBranch. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164054 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-17Fix a few vars that can end up being used without initialization.Axel Naumann
The cases where no initialization happens should still be checked for logic flaws. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164032 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-15PGO: preserve branch-weight metadata when simplifying two branches with a commonManman Ren
destination. Updated previous implementation to fix a case not covered: // PBI: br i1 %x, TrueDest, BB // BI: br i1 %y, TrueDest, FalseDest The other case was handled correctly. // PBI: br i1 %x, BB, FalseDest // BI: br i1 %y, TrueDest, FalseDest Also tried to use 64-bit arithmetic instead of APInt with scale to simplify the computation. Let me know if you have other opinions about this. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163954 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-14PGO: preserve branch-weight metadata when simplifying a switch with a singleManman Ren
case to a conditional branch and when removing dead cases. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163942 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-14Try to fix the bots by detecting inconsistant branch-weight metadata.Manman Ren
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163926 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-14PGO: preserve branch-weight metadata when merging two switches whereManman Ren
the default target of the first switch is not the basic block the second switch is in (PredDefault != BB). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163916 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-11SimplifyCFG: preserve branch-weight metadata when creating a new switch fromManman Ren
a pair of switch/branch where both depend on the value of the same variable and the default case of the first switch/branch goes to the second switch/branch. Code clean up and fixed a few issues: 1> handling the case where some cases of the 2nd switch are invalidated 2> correctly calculate the weight for the 2nd switch when it is a conditional eq Testing case is modified from Alastair's original patch. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163635 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-10Fix style issues from r163302 pointed out by Evan.Hans Wennborg
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163491 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-08Remove an incorrect assert during branch weight propagation.Andrew Trick
Patch and test case by Alastair Murray! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163437 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-07SimplifyCFG: ValidLookupTableConstant should be staticHans Wennborg
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163378 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-06Fix switch_to_lookup_table.ll test from r163302.Hans Wennborg
The lookup tables did not get built in a deterministic order. This makes them get built in the order that the corresponding phi nodes were found. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163305 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-06Build lookup tables for switches (PR884)Hans Wennborg
This adds a transformation to SimplifyCFG that attemps to turn switch instructions into loads from lookup tables. It works on switches that are only used to initialize one or more phi nodes in a common successor basic block, for example: int f(int x) { switch (x) { case 0: return 5; case 1: return 4; case 2: return -2; case 5: return 7; case 6: return 9; default: return 42; } This speeds up the code by removing the hard-to-predict jump, and reduces code size by removing the code for the jump targets. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163302 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-05Stop casting away const qualifier needlessly.Roman Divacky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163258 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-30testMichael Ilseman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162914 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-29Preserve branch profile metadata during switch formation.Andrew Trick
Patch by Michael Ilseman! This fixes SimplifyCFGOpt::FoldValueComparisonIntoPredecessors to preserve metata when folding conditional branches into switches. void foo(int x) { if (x == 0) bar(1); else if (__builtin_expect(x == 10, 1)) bar(2); else if (x == 20) bar(3); } CFG: B0 | \ | X0 B10 | \ | X10 B20 | \ E X20 Merge B0-B10: w(B0-X0) = w(B0-X0)*sum-weights(B10) = w(B0-X0) * (w(B10-X10) + w(B10-B20)) w(B0-X10) = w(B0-B10) * w(B10-X10) w(B0-B20) = w(B0-B10) * w(B10-B20) B0 __ | \ \ | X10 X0 B20 | \ E X20 Merge B0-B20: w(B0-X0) = w(B0-X0) * sum-weights(B20) = w(B0-X0) * (w(B20-E) + w(B20-X20)) w(B0-X10) = w(B0-X10) * sum-weights(B20) = ... w(B0-X20) = w(B0-B20) * w(B20-X20) w(B0-E) = w(B0-B20) * w(B20-E) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162868 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-29whitespaceAndrew Trick
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162867 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-23Fix a typo (the the => the)Sylvestre Ledru
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160621 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-15Move llvm/Support/MDBuilder.h to llvm/MDBuilder.h, to live withChandler Carruth
IRBuilder, DIBuilder, etc. This is the proper layering as MDBuilder can't be used (or implemented) without the Core Metadata representation. Patches to Clang and Dragonegg coming up. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160237 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-13Make helper functions static.Benjamin Kramer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160173 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-02Revert "IntRange:" as it appears to be breaking self hosting.Eric Christopher
This reverts commit b2833d9dcba88c6f0520cad760619200adc0442c. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159618 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-02IntRange:Stepan Dyatkovskiy
- 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 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159527 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-29Move llvm/Support/IRBuilder.h -> llvm/IRBuilder.hChandler Carruth
This was always part of the VMCore library out of necessity -- it deals entirely in the IR. The .cpp file in fact was already part of the VMCore library. This is just a mechanical move. I've tried to go through and re-apply the coding standard's preferred header sort, but at 40-ish files, I may have gotten some wrong. Please let me know if so. I'll be committing the corresponding updates to Clang and Polly, and Duncan has DragonEgg. Thanks to Bill and Eric for giving the green light for this bit of cleanup. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159421 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-24Remove dyn_cast + dereference pattern by replacing it with a cast and changingNick Lewycky
the safety check to look for the same type we're going to actually cast to. Fixes PR13180! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159110 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-13SimplifyCFG: fold unconditional branch to its predecessor if profitable.Manman Ren
This patch extends FoldBranchToCommonDest to fold unconditional branches. For unconditional branches, we fold them if it is easy to update the phi nodes in the common successors. rdar://10554090 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158392 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-26SimplifyCFG: Turn the ad-hoc std::pair that represents switch cases into an ↵Benjamin Kramer
explicit struct. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157516 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-26Add support for branch weight metadata to MDBuilder and use it in various ↵Benjamin Kramer
places. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157515 91177308-0d34-0410-b5e6-96231b3b80d8
2012-04-04Always compute all the bits in ComputeMaskedBits.Rafael Espindola
This allows us to keep passing reduced masks to SimplifyDemandedBits, but know about all the bits if SimplifyDemandedBits fails. This allows instcombine to simplify cases like the one in the included testcase. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@154011 91177308-0d34-0410-b5e6-96231b3b80d8
2012-03-11llvm::SwitchInstStepan Dyatkovskiy
Renamed methods caseBegin, caseEnd and caseDefault with case_begin, case_end, and case_default. Added some notes relative to case iterators. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152532 91177308-0d34-0410-b5e6-96231b3b80d8
2012-03-08Taken into account Duncan's comments for r149481 dated by 2nd Feb 2012:Stepan Dyatkovskiy
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152297 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-06[unwind removal] We no longer have 'unwind' instructions being generated, soBill Wendling
remove the code that handles them. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@149901 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-01SwitchInst refactoring.Stepan Dyatkovskiy
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@149481 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-25Gracefully degrade precision in branch probability numbers.Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@148946 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-19Actually, this code handles wrapped sets just fine. Noticed by inspection.Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@148487 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-05Fix SpeculativelyExecuteBB to either speculate all or none of the phisDan Gohman
present in the bottom of the CFG triangle, as the transformation isn't ever valuable if the branch can't be eliminated. Also, unify some heuristics between SimplifyCFG's multiple if-converters, for consistency. This fixes rdar://10627242. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147630 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-05Revert r56315. When the instruction to speculate is a load, thisDan Gohman
code can incorrectly move the load across a store. This never happens in practice today, but only because the current heuristics accidentally preclude it. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147623 91177308-0d34-0410-b5e6-96231b3b80d8
2011-12-28Demystify this comment.Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147307 91177308-0d34-0410-b5e6-96231b3b80d8
2011-12-27Use false not zero, as a bool.Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147292 91177308-0d34-0410-b5e6-96231b3b80d8
2011-12-27Teach simplifycfg to recompute branch weights when merging some branches, andNick Lewycky
to discard weights when appropriate. Still more to do (and a new TODO), but it's a start! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147286 91177308-0d34-0410-b5e6-96231b3b80d8
2011-12-26Update the branch weight metadata when reversing the order of a branch.Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147280 91177308-0d34-0410-b5e6-96231b3b80d8
2011-12-26Sort includes, canonicalize whitespace, fix typos. No functionality change.Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147279 91177308-0d34-0410-b5e6-96231b3b80d8
2011-12-21Make some intrinsics safe to speculatively execute.Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147036 91177308-0d34-0410-b5e6-96231b3b80d8
2011-12-17Revert r146822 at Pete Cooper's request as it broke clang self hosting.Kevin Enderby
Hope I did this correctly :) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@146834 91177308-0d34-0410-b5e6-96231b3b80d8
2011-12-17SimplifyCFG now predicts some conditional branches to true or false ↵Pete Cooper
depending on previous branch on same comparison operands. For example, if (a == b) { if (a > b) // this is false Fixes some of the issues on <rdar://problem/10554090> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@146822 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-04-29 21:22:34 +0000