summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Utils
Commit message (Collapse)AuthorAgeFilesLines
* This patch teaches IndVarSimplify to add nuw and nsw to certain kindsSanjoy Das2015-01-061-0/+125
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | of operations that provably don't overflow. For example, we can prove %civ.inc below does not sign-overflow. With this change, IndVarSimplify changes %civ.inc to an add nsw. define i32 @foo(i32* %array, i32* %length_ptr, i32 %init) { entry: %length = load i32* %length_ptr, !range !0 %len.sub.1 = sub i32 %length, 1 %upper = icmp slt i32 %init, %len.sub.1 br i1 %upper, label %loop, label %exit loop: %civ = phi i32 [ %init, %entry ], [ %civ.inc, %latch ] %civ.inc = add i32 %civ, 1 %cmp = icmp slt i32 %civ.inc, %length br i1 %cmp, label %latch, label %break latch: store i32 0, i32* %array %check = icmp slt i32 %civ.inc, %len.sub.1 br i1 %check, label %loop, label %break break: ret i32 %civ.inc exit: ret i32 42 } Differential Revision: http://reviews.llvm.org/D6748 llvm-svn: 225282
* SymbolRewriter: use iplist::spliceSaleem Abdulrasool2015-01-051-1/+1
| | | | | | | | The swap implementation for iplist is currently unsupported. Simply splice the old list into place, which achieves the same purpose. This is needed in order to thread the -frewrite-map-file frontend option correctly. NFC. llvm-svn: 225186
* SymbolRewriter: 80-columnSaleem Abdulrasool2015-01-051-2/+4
| | | | | | Wrap a couple of lines. NFC. llvm-svn: 225185
* [PM] Split the AssumptionTracker immutable pass into two separate APIs:Chandler Carruth2015-01-048-88/+93
| | | | | | | | | | | | | | | | | | | | | | | | | | | | a cache of assumptions for a single function, and an immutable pass that manages those caches. The motivation for this change is two fold. Immutable analyses are really hacks around the current pass manager design and don't exist in the new design. This is usually OK, but it requires that the core logic of an immutable pass be reasonably partitioned off from the pass logic. This change does precisely that. As a consequence it also paves the way for the *many* utility functions that deal in the assumptions to live in both pass manager worlds by creating an separate non-pass object with its own independent API that they all rely on. Now, the only bits of the system that deal with the actual pass mechanics are those that actually need to deal with the pass mechanics. Once this separation is made, several simplifications become pretty obvious in the assumption cache itself. Rather than using a set and callback value handles, it can just be a vector of weak value handles. The callers can easily skip the handles that are null, and eventually we can wrap all of this up behind a filter iterator. For now, this adds boiler plate to the various passes, but this kind of boiler plate will end up making it possible to port these passes to the new pass manager, and so it will end up factored away pretty reasonably. llvm-svn: 225131
* [SimplifyCFG] Revise common code sinkingMichael Liao2014-12-231-30/+30
| | | | | | | | | | - Fix the case where more than 1 common instructions derived from the same operand cannot be sunk. When a pair of value has more than 1 derived values in both branches, only 1 derived value could be sunk. - Replace BB1 -> (BB2, PN) map with joint value map, i.e. map of (BB1, BB2) -> PN, which is more accurate to track common ops. llvm-svn: 224757
* Remove a bad cast in CloneModule()Michael Kuperstein2014-12-231-1/+1
| | | | | | A cast that was introduced in r209007 was accidentally left in after the changes made to GlobalAlias rules in r210062. This crashes if the aliasee is a now-leggal ConstantExpr. llvm-svn: 224756
* [LCSSA] Handle PHI insertion in disjoint loopsBruno Cardoso Lopes2014-12-222-9/+42
| | | | | | | | | | | | | | | | | | | | Take two disjoint Loops L1 and L2. LoopSimplify fails to simplify some loops (e.g. when indirect branches are involved). In such situations, it can happen that an exit for L1 is the header of L2. Thus, when we create PHIs in one of such exits we are also inserting PHIs in L2 header. This could break LCSSA form for L2 because these inserted PHIs can also have uses in L2 exits, which are never handled in the current implementation. Provide a fix for this corner case and test that we don't assert/crash on that. Differential Revision: http://reviews.llvm.org/D6624 rdar://problem/19166231 llvm-svn: 224740
* Rename MapValue(Metadata*) to MapMetadata()Duncan P. N. Exon Smith2014-12-193-18/+18
| | | | | | | | Instead of reusing the name `MapValue()` when mapping `Metadata`, use `MapMetadata()`. The old name doesn't make much sense after the `Metadata`/`Value` split. llvm-svn: 224566
* The inliner needs to fix up debug information for llvm.dbg.declare, not only ↵Michael Kuperstein2014-12-111-0/+6
| | | | | | | | | | for llvm.dbg.value. Patch by Amjad Aboud Differential Revision: http://reviews.llvm.org/D6525 llvm-svn: 224015
* Rename static functiom "map" to be more descriptive and to avoidKaelyn Takata2014-12-091-5/+5
| | | | | | potential confusion with the std::map type. llvm-svn: 223853
* Remove unneeded curly braces.Frederic Riss2014-12-091-4/+2
| | | | llvm-svn: 223809
* Reorder the code to avoid inserting at the beginning of a vector.Frederic Riss2014-12-091-1/+1
| | | | | | As per dblaikie suggestion, thanks\! llvm-svn: 223808
* IR: Split Metadata from ValueDuncan P. N. Exon Smith2014-12-098-83/+174
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Split `Metadata` away from the `Value` class hierarchy, as part of PR21532. Assembly and bitcode changes are in the wings, but this is the bulk of the change for the IR C++ API. I have a follow-up patch prepared for `clang`. If this breaks other sub-projects, I apologize in advance :(. Help me compile it on Darwin I'll try to fix it. FWIW, the errors should be easy to fix, so it may be simpler to just fix it yourself. This breaks the build for all metadata-related code that's out-of-tree. Rest assured the transition is mechanical and the compiler should catch almost all of the problems. Here's a quick guide for updating your code: - `Metadata` is the root of a class hierarchy with three main classes: `MDNode`, `MDString`, and `ValueAsMetadata`. It is distinct from the `Value` class hierarchy. It is typeless -- i.e., instances do *not* have a `Type`. - `MDNode`'s operands are all `Metadata *` (instead of `Value *`). - `TrackingVH<MDNode>` and `WeakVH` referring to metadata can be replaced with `TrackingMDNodeRef` and `TrackingMDRef`, respectively. If you're referring solely to resolved `MDNode`s -- post graph construction -- just use `MDNode*`. - `MDNode` (and the rest of `Metadata`) have only limited support for `replaceAllUsesWith()`. As long as an `MDNode` is pointing at a forward declaration -- the result of `MDNode::getTemporary()` -- it maintains a side map of its uses and can RAUW itself. Once the forward declarations are fully resolved RAUW support is dropped on the ground. This means that uniquing collisions on changing operands cause nodes to become "distinct". (This already happened fairly commonly, whenever an operand went to null.) If you're constructing complex (non self-reference) `MDNode` cycles, you need to call `MDNode::resolveCycles()` on each node (or on a top-level node that somehow references all of the nodes). Also, don't do that. Metadata cycles (and the RAUW machinery needed to construct them) are expensive. - An `MDNode` can only refer to a `Constant` through a bridge called `ConstantAsMetadata` (one of the subclasses of `ValueAsMetadata`). As a side effect, accessing an operand of an `MDNode` that is known to be, e.g., `ConstantInt`, takes three steps: first, cast from `Metadata` to `ConstantAsMetadata`; second, extract the `Constant`; third, cast down to `ConstantInt`. The eventual goal is to introduce `MDInt`/`MDFloat`/etc. and have metadata schema owners transition away from using `Constant`s when the type isn't important (and they don't care about referring to `GlobalValue`s). In the meantime, I've added transitional API to the `mdconst` namespace that matches semantics with the old code, in order to avoid adding the error-prone three-step equivalent to every call site. If your old code was: MDNode *N = foo(); bar(isa <ConstantInt>(N->getOperand(0))); baz(cast <ConstantInt>(N->getOperand(1))); bak(cast_or_null <ConstantInt>(N->getOperand(2))); bat(dyn_cast <ConstantInt>(N->getOperand(3))); bay(dyn_cast_or_null<ConstantInt>(N->getOperand(4))); you can trivially match its semantics with: MDNode *N = foo(); bar(mdconst::hasa <ConstantInt>(N->getOperand(0))); baz(mdconst::extract <ConstantInt>(N->getOperand(1))); bak(mdconst::extract_or_null <ConstantInt>(N->getOperand(2))); bat(mdconst::dyn_extract <ConstantInt>(N->getOperand(3))); bay(mdconst::dyn_extract_or_null<ConstantInt>(N->getOperand(4))); and when you transition your metadata schema to `MDInt`: MDNode *N = foo(); bar(isa <MDInt>(N->getOperand(0))); baz(cast <MDInt>(N->getOperand(1))); bak(cast_or_null <MDInt>(N->getOperand(2))); bat(dyn_cast <MDInt>(N->getOperand(3))); bay(dyn_cast_or_null<MDInt>(N->getOperand(4))); - A `CallInst` -- specifically, intrinsic instructions -- can refer to metadata through a bridge called `MetadataAsValue`. This is a subclass of `Value` where `getType()->isMetadataTy()`. `MetadataAsValue` is the *only* class that can legally refer to a `LocalAsMetadata`, which is a bridged form of non-`Constant` values like `Argument` and `Instruction`. It can also refer to any other `Metadata` subclass. (I'll break all your testcases in a follow-up commit, when I propagate this change to assembly.) llvm-svn: 223802
* Correctly handle complex locations expressions in replaceDbgDeclareForAlloca()Frederic Riss2014-12-091-2/+2
| | | | | | | | | | | | | | | | replaceDbgDeclareForAlloca() replaces an alloca by a value storing the address of what was the alloca. If there is a dbg.declare corresponding to that alloca, we need to lower it to a dbg.value describing the additional dereference operation to be performed to get to the underlying variable. This is done by adding a DW_OP_deref to the complex location part of the location description. This deref was added to the end of the operation list, which is wrong. The expression applies to what is described by the dbg.{declare,value}, and as we are changing this, we need to apply the DW_OP_deref as the first operation in the list. Part of the fix for rdar://19162268. llvm-svn: 223799
* Revert "Move function to obtain branch weights into the BranchInst class. NFC."Juergen Ributzka2014-12-091-6/+26
| | | | | | This reverts commit r223784 and copies the 'ExtractBranchMetadata' to CodeGenPrepare. llvm-svn: 223795
* Move function to obtain branch weights into the BranchInst class. NFC.Juergen Ributzka2014-12-091-26/+6
| | | | | | Make this function available to other parts of LLVM. llvm-svn: 223784
* Utils: Style cleanups, NFCDuncan P. N. Exon Smith2014-12-061-7/+7
| | | | llvm-svn: 223556
* Utils: Avoid RAUW on metadata in CloneFunction()Duncan P. N. Exon Smith2014-12-061-4/+4
| | | | llvm-svn: 223555
* correct spelling, NFCMatthias Braun2014-12-031-3/+3
| | | | llvm-svn: 223274
* [SimplifyLibCalls] Improve double->float shrinking to consider constantsMatthias Braun2014-12-031-14/+33
| | | | | | | | | | This allows cases like float x; fmin(1.0, x); to be optimized to fminf(1.0f, x); rdar://19049359 Differential Revision: http://reviews.llvm.org/D6496 llvm-svn: 223270
* [SimplifyLibCalls] Enable double to float shrinking for copysignMatthias Braun2014-12-031-0/+1
| | | | | | | | rdar://19049359 Differential Revision: http://reviews.llvm.org/D6495 llvm-svn: 223269
* [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
* Revert r223049, r223050 and r223051 while investigating test failures.Hans Wennborg2014-12-011-8/+56
| | | | | | I didn't foresee affecting the Clang test suite :/ llvm-svn: 223054
* SimplifyCFG: Omit range checks for switch lookup tables when default is ↵Hans Wennborg2014-12-011-7/+8
| | | | | | | | unreachable They would get optimized away later, but we might as well not emit them. llvm-svn: 223051
* SimplifyCFG: don't remove unreachable default switch destinationsHans Wennborg2014-12-011-49/+0
| | | | | | | | | | | | | An unreachable default destination can be exploited by other optimizations, and SDag lowering is now prepared to handle them efficiently. For example, branches to the unreachable destination will be optimized away, such as in the case of range checks for switch lookup tables. On 64-bit Linux, this reduces the size of a clang bootstrap by 80 kB (and Chromium by 30 kB). llvm-svn: 223050
* [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
* reinstate r222872: Peephole optimization in switch table lookup: reuse the ↵Erik Eckstein2014-11-271-7/+100
| | | | | | | | | | | | | | | | | | | | | | | | | | | guarding table comparison if possible. Fixed missing dominance check. Original commit message: This optimization tries to reuse the generated compare instruction, if there is a comparison against the default value after the switch. Example: if (idx < tablesize) r = table[idx]; // table does not contain default_value else r = default_value; if (r != default_value) ... Is optimized to: cond = idx < tablesize; if (cond) r = table[idx]; else r = default_value; if (cond) ... Jump threading will then eliminate the second if(cond). llvm-svn: 222891
* Revert "Peephole optimization in switch table lookup: reuse the guarding ↵Erik Eckstein2014-11-271-89/+7
| | | | | | | | table comparison if possible." It is breaking the clang bootstrag. llvm-svn: 222877
* Peephole optimization in switch table lookup: reuse the guarding table ↵Erik Eckstein2014-11-271-7/+89
| | | | | | | | | | | | | | | | | | | | | | | | | comparison if possible. This optimization tries to reuse the generated compare instruction, if there is a comparison against the default value after the switch. Example: if (idx < tablesize) r = table[idx]; // table does not contain default_value else r = default_value; if (r != default_value) ... Is optimized to: cond = idx < tablesize; if (cond) r = table[idx]; else r = default_value; if (cond) ... \endcode Jump threading will then eliminate the second if(cond). llvm-svn: 222872
* SimplifyCFG: Refactor GatherConstantCompares() result in a structMehdi Amini2014-11-201-133/+152
| | | | | | | | | | Code seems cleaner and easier to understand this way This is basically r222416, after fixes for MSVC lack of standard support, and a few cleaning (got rid of a warning). Thanks Nakamura Takumi and Nico Weber for the MSVC fixes. llvm-svn: 222472
* Fix a trip-count overflow issue in LoopUnroll.Michael Zolotukhin2014-11-201-2/+11
| | | | | | | | | | | | Currently LoopUnroll generates a prologue loop before the main loop body to execute first N%UnrollFactor iterations. Also, this loop is used if trip-count can overflow - it's determined by a runtime check. However, we've been mistakenly optimizing this loop to a linear code for UnrollFactor = 2, not taking into account that it also serves as a safe version of the loop if its trip-count overflows. llvm-svn: 222451
* Revert r222416, r222422, r222426: the former revision had problems and ↵Timur Iskhodzhanov2014-11-201-150/+136
| | | | | | fixing them introduced bugs llvm-svn: 222428
* Fix a typoTimur Iskhodzhanov2014-11-201-1/+1
| | | | llvm-svn: 222426
* SimplifyCFG.cpp: Tweak to let msc17 compliant.NAKAMURA Takumi2014-11-201-8/+11
| | | | | | | | - Use LLVM_DELETED_FUNCTION. - Don't use member initializers. - Don't use initializer list. llvm-svn: 222422
* SimplifyCFG: Refactor GatherConstantCompares() result in a structMehdi Amini2014-11-201-136/+147
| | | | | | Code seems cleaner and easier to understand this way llvm-svn: 222416
* Try to fix MSVS build after r222384. No intended behavior change.Nico Weber2014-11-191-3/+3
| | | | llvm-svn: 222386
* SimplifyCFG: turn recursive GatherConstantCompares into iterativeMehdi Amini2014-11-191-99/+138
| | | | | | A long sequence of || or && could lead to a stack explosion. llvm-svn: 222384
* Update SetVector to rely on the underlying set's insert to return a ↵David Blaikie2014-11-196-10/+10
| | | | | | | | | | | | | pair<iterator, bool> This is to be consistent with StringSet and ultimately with the standard library's associative container insert function. This lead to updating SmallSet::insert to return pair<iterator, bool>, and then to update SmallPtrSet::insert to return pair<iterator, bool>, and then to update all the existing users of those functions... llvm-svn: 222334
* Introduce llvm::SplitAllCriticalEdgesKostya Serebryany2014-11-192-19/+17
| | | | | | | | | | | | | | | | | | | | Summary: move the code from BreakCriticalEdges::runOnFunction() into a separate utility function llvm::SplitAllCriticalEdges() so that it can be used independently. No functionality change intended. Test Plan: check-llvm Reviewers: nlewycky Reviewed By: nlewycky Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D6313 llvm-svn: 222288
* SimplifyCFG: Range'ify some for-loops. No functional change.Hans Wennborg2014-11-181-12/+13
| | | | llvm-svn: 222215
* [SimplifyCFG] Make the value type of the hole check bitmask a power-of-2.Juergen Ributzka2014-11-171-2/+5
| | | | | | | | | | | | | | | When converting a switch to a lookup table we might have to generate a bitmaks to encode and check for holes in the original switch statement. The type of this mask depends on the number of switch statements, which can result in illegal types for pretty much all architectures. To avoid unnecessary type legalization and help FastISel this commit increases the size of the bitmask to next power-of-2 value when necessary. This fixes rdar://problem/18984639. llvm-svn: 222168
* Optimize switch lookup tables with linear mapping.Erik Eckstein2014-11-171-1/+58
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This is a simple optimization for switch table lookup: It computes the output value directly with an (optional) mul and add if there is a linear mapping between index and output. Example: int f1(int x) { switch (x) { case 0: return 10; case 1: return 11; case 2: return 12; case 3: return 13; } return 0; } generates: define i32 @f1(i32 %x) #0 { entry: %0 = icmp ult i32 %x, 4 br i1 %0, label %switch.lookup, label %return switch.lookup: %switch.offset = add i32 %x, 10 ret i32 %switch.offset return: ret i32 0 } llvm-svn: 222121
* Remove redundant virtual on overriden functions.David Blaikie2014-11-141-1/+1
| | | | llvm-svn: 222023
* Use nullptr instead of NULL for variadic sentinelsReid Kleckner2014-11-132-25/+25
| | | | | | | | | | Windows defines NULL to 0, which when used as an argument to a variadic function, is not a null pointer constant. As a result, Clang's -Wsentinel fires on this code. Using '0' would be wrong on most 64-bit platforms, but both MSVC and Clang make it work on Windows. Sidestep the issue with nullptr. llvm-svn: 221940
* Add fortified (__*_chk) library functions to TLI (NFC)Ahmed Bougacha2014-11-121-17/+9
| | | | | | | | | | | | One of them (__memcpy_chk) was already there, the others were checked by comparing function names. Note that the fortified libfuncs are now part of TLI, but are always available, because they aren't generated, only optimized into the non-checking versions. Differential Revision: http://reviews.llvm.org/D6179 llvm-svn: 221817
* remove function names from comments; NFCSanjay Patel2014-11-121-11/+10
| | | | llvm-svn: 221798
* Revert "IR: MDNode => Value"Duncan P. N. Exon Smith2014-11-114-23/+27
| | | | | | | | | | | | | | | | | Instead, we're going to separate metadata from the Value hierarchy. See PR21532. This reverts commit r221375. This reverts commit r221373. This reverts commit r221359. This reverts commit r221167. This reverts commit r221027. This reverts commit r221024. This reverts commit r221023. This reverts commit r220995. This reverts commit r220994. llvm-svn: 221711
* [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
* Fix extra semicolon warning. NFC.Vasileios Kalintiris2014-11-101-1/+1
| | | | llvm-svn: 221613
* Transforms: address some late commentsSaleem Abdulrasool2014-11-081-30/+13
| | | | | | | | | | We already use the llvm namespace. Remove the unnecessary prefix. Use the StringRef::equals method to compare with C strings rather than instantiating std::strings. Addresses late review comments from David Majnemer. llvm-svn: 221564
OpenPOWER on IntegriCloud