summaryrefslogtreecommitdiffstats
path: root/llvm/unittests/Analysis
Commit message (Collapse)AuthorAgeFilesLines
* [LOOPGUARD] Remove asserts in getLoopGuardBranchWhitney Tsang2019-10-061-0/+85
| | | | | | | | | | | | | Summary: The assertion in getLoopGuardBranch can be a 'return nullptr' under if condition. Authored By: DTharun Reviewer: Whitney, fhahn Reviewed By: Whitney, fhahn Subscribers: fhahn, llvm-commits Tag: LLVM Differential Revision: https://reviews.llvm.org/D66084 llvm-svn: 373857
* [LOOPGUARD] Disable loop with multiple loop exiting blocks.Whitney Tsang2019-09-261-0/+120
| | | | | | | | | | | | | | | | | | | | Summary: As discussed in the loop group meeting. With the current definition of loop guard, we should not allow multiple loop exiting blocks. For loops that has multiple loop exiting blocks, we can simply unable to find the loop guard. When getUniqueExitBlock() obtains a vector size not equals to one, that means there is either no exit blocks or there exists more than one unique block the loop exit to. If we don't disallow loop with multiple loop exit blocks, then with our current implementation, there can exist exit blocks don't post dominated by the non pre-header successor of the guard block. Reviewer: reames, Meinersbur, kbarton, etiotto, bmahjour Reviewed By: Meinersbur, kbarton Subscribers: fhahn, hiraditya, llvm-commits Tag: LLVM Differential Revision: https://reviews.llvm.org/D66529 llvm-svn: 373011
* [SCEV] Disable canonical expansion for non-affine addrecs.Artur Pilipenko2019-09-241-0/+182
| | | | | | | | | | Reviewed By: apilipenko Differential Revision: https://reviews.llvm.org/D65276 Patch by Evgeniy Brevnov (ybrevnov@azul.com) llvm-svn: 372789
* [PGO][PGSO] ProfileSummary changes.Hiroshi Yamauchi2019-09-241-0/+42
| | | | | | | | | | (Split of off D67120) ProfileSummary changes for profile guided size optimization. Differential Revision: https://reviews.llvm.org/D67377 llvm-svn: 372783
* [SVFS] Vector Function ABI demangling.Francesco Petrogalli2019-09-192-0/+440
| | | | | | | | | | | | | | | | This patch implements the demangling functionality as described in the Vector Function ABI. This patch will be used to implement the SearchVectorFunctionSystem (SVFS) as described in the RFC: http://lists.llvm.org/pipermail/llvm-dev/2019-June/133484.html A fuzzer is added to test the demangling utility. Patch by Sumedh Arani <sumedh.arani@arm.com> Differential revision: https://reviews.llvm.org/D66024 llvm-svn: 372343
* Change TargetLibraryInfo analysis passes to always require FunctionTeresa Johnson2019-09-073-3/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This is the first change to enable the TLI to be built per-function so that -fno-builtin* handling can be migrated to use function attributes. See discussion on D61634 for background. This is an enabler for fixing handling of these options for LTO, for example. This change should not affect behavior, as the provided function is not yet used to build a specifically per-function TLI, but rather enables that migration. Most of the changes were very mechanical, e.g. passing a Function to the legacy analysis pass's getTLI interface, or in Module level cases, adding a callback. This is similar to the way the per-function TTI analysis works. There was one place where we were looking for builtins but not in the context of a specific function. See FindCXAAtExit in lib/Transforms/IPO/GlobalOpt.cpp. I'm somewhat concerned my workaround could provide the wrong behavior in some corner cases. Suggestions welcome. Reviewers: chandlerc, hfinkel Subscribers: arsenm, dschuff, jvesely, nhaehnle, mehdi_amini, javed.absar, sbc100, jgravelle-google, eraman, aheejin, steven_wu, george.burgess.iv, dexonsmith, jfb, asbirlea, gchatelet, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D66428 llvm-svn: 371284
* [llvm] Migrate llvm::make_unique to std::make_uniqueJonas Devlieghere2019-08-151-4/+4
| | | | | | | | Now that we've moved to C++14, we no longer need the llvm::make_unique implementation from STLExtras.h. This patch is a mechanical replacement of (hopefully) all the llvm::make_unique instances across the monorepo. llvm-svn: 369013
* [SCEV] Return zero from computeConstantDifference(X, X)Nikolai Bozhenov2019-08-071-2/+68
| | | | | | | | | | | | Without this patch computeConstantDifference returns None for cases like these: computeConstantDifference(%x, %x) computeConstantDifference({%x,+,16}, {%x,+,16}) Differential Revision: https://reviews.llvm.org/D65474 llvm-svn: 368193
* [AliasAnalysis] Initialize a member variable that may be used by unit test.Peter Smith2019-08-021-5/+2
| | | | | | | | | | | | | | | | | | The unit tests in BasicAliasAnalysisTest use the alias analysis API directly and do not call setAAResults to initalize AAR. This gives a valgrind error "Conditional Jump depends on unitialized variable". On most buildbots the variable is nullptr, but in some cases it can be non nullptr leading to seemingly random failures. These tests were disabled in r366986. With the initialization they can be enabled again. Fixes PR42719 Differential Revision: https://reviews.llvm.org/D65568 llvm-svn: 367662
* [LOOPINFO] Introduce the loop guard API.Whitney Tsang2019-07-251-61/+102
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This is the first patch for the loop guard. We introduced getLoopGuardBranch() and isGuarded(). This currently only works on simplified loop, as it requires a preheader and a latch to identify the guard. It will work on loops of the form: /// GuardBB: /// br cond1, Preheader, ExitSucc <== GuardBranch /// Preheader: /// br Header /// Header: /// ... /// br Latch /// Latch: /// br cond2, Header, ExitBlock /// ExitBlock: /// br ExitSucc /// ExitSucc: Prior discussions leading upto the decision to introduce the loop guard API: http://lists.llvm.org/pipermail/llvm-dev/2019-May/132607.html Reviewer: reames, kbarton, hfinkel, jdoerfert, Meinersbur, dmgreen Reviewed By: reames Subscribers: wuzish, hiraditya, jsji, llvm-commits, bmahjour, etiotto Tag: LLVM Differential Revision: https://reviews.llvm.org/D63885 llvm-svn: 367033
* [BasicAA] Temporarily disable two testsGeorge Burgess IV2019-07-251-2/+5
| | | | | | | | | | | | | | | These tests are breaking three independent upstream buildbots (as well downstream ones). These breakages have appeared mysteriously, consistently, and during different revisions. Sadly, none of {ASAN,TSAN,MSAN,UBSAN} flag anything, so the cause here is nonobvious. Until we've figured this out, it seems best to disable these tests entirely, so that the affected bots don't remain silent about any other, unrelated failures. Please see PR42719 for more information. llvm-svn: 366986
* [LoopInfo] Fix getUniqueNonLatchExitBlocksSerguei Katkov2019-07-171-0/+43
| | | | | | | | | | | | | | | | | | | | | | | | It is possible that exit block has two predecessors and one of them is a latch block while another is not. Current algorithm is based on the assumption that all exits are dedicated and therefore we can check only first predecessor of loop exit to find all unique exits. However if we do not consider latch block and it is first predecessor of some exit then this exit will be found. Regression test is added. As a side effect of algorithm re-writing, the restriction that all exits are dedicated is eliminated. Reviewers: reames, fhahn, efriedma Reviewed By: efriedma Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D64787 llvm-svn: 366294
* [LoopInfo] Introduce getUniqueNonLatchExitBlocks utility functionSerguei Katkov2019-07-151-0/+46
| | | | | | | | | | | | Extract the code from LoopUnrollRuntime into utility function to re-use it in D63923. Reviewers: reames, mkuper Reviewed By: reames Subscribers: fhahn, hiraditya, zzheng, dmgreen, llvm-commits Differential Revision: https://reviews.llvm.org/D64548 llvm-svn: 366040
* isBytewiseValue checks ConstantVector element by elementVitaly Buka2019-07-121-1/+1
| | | | | | | | | | | | | | | | Summary: Vector of the same value with few undefs will sill be considered "Bytewise" Reviewers: eugenis, pcc, jfb Reviewed By: jfb Subscribers: dexonsmith, hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D64031 llvm-svn: 365971
* Return Undef from isBytewiseValue for empty arrays or structsVitaly Buka2019-07-121-4/+4
| | | | | | | | | | | | Reviewers: pcc, eugenis Subscribers: hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D64052 llvm-svn: 365864
* Handle IntToPtr in isBytewiseValueVitaly Buka2019-07-121-3/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This helps with more efficient use of memset for pattern initialization From @pcc prototype for -ftrivial-auto-var-init=pattern optimizations Binary size change on CTMark, (with -fuse-ld=lld -Wl,--icf=all, similar results with default linker options) ``` master patch diff Os 8.238864e+05 8.238864e+05 0.0 O3 1.054797e+06 1.054797e+06 0.0 Os zero 8.292384e+05 8.292384e+05 0.0 O3 zero 1.062626e+06 1.062626e+06 0.0 Os pattern 8.579712e+05 8.338048e+05 -0.030299 O3 pattern 1.090502e+06 1.067574e+06 -0.020481 ``` Zero vs Pattern on master ``` zero pattern diff Os 8.292384e+05 8.579712e+05 0.036578 O3 1.062626e+06 1.090502e+06 0.025124 ``` Zero vs Pattern with the patch ``` zero pattern diff Os 8.292384e+05 8.338048e+05 0.003333 O3 1.062626e+06 1.067574e+06 0.003193 ``` Reviewers: pcc, eugenis Subscribers: hiraditya, cfe-commits, llvm-commits Tags: #clang, #llvm Differential Revision: https://reviews.llvm.org/D63967 llvm-svn: 365858
* [test] Silence gcc 7.4 warning [NFC]Mikael Holmen2019-07-111-1/+1
| | | | | | | | | Without this gcc 7.4.0 complains with ../unittests/Analysis/ValueTrackingTest.cpp:937:66: error: ISO C++11 requires at least one argument for the "..." in a variadic macro [-Werror] ::testing::ValuesIn(IsBytewiseValueTests)); ^ llvm-svn: 365738
* Add IsBytewiseValue unit testVitaly Buka2019-07-101-11/+268
| | | | | | | | | | Subscribers: llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D63966 llvm-svn: 365710
* [SCEV] Fix for PR42397. SCEVExpander wrongly adds nsw to shl instruction.Denis Bakhvalov2019-07-081-0/+41
| | | | | Change-Id: I76c9f628c092ae3e6e78ebdaf55cec726e25d692 llvm-svn: 365363
* Use "willreturn" in isGuaranteedToTransferExecutionToSuccessorJohannes Doerfert2019-06-271-0/+3
| | | | | | | | | | | | | | | | | | | | | The `willreturn` function attribute guarantees that a function call will come back to the call site if the call is also known not to throw. Therefore, this attribute can be used in `isGuaranteedToTransferExecutionToSuccessor`. Patch by Hideto Ueno (@uenoku) Reviewers: jdoerfert, sstefan1 Reviewed By: jdoerfert Subscribers: hiraditya, jfb, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D63372 llvm-svn: 364580
* [Analysis] add isSplatValue() for vectors in IRSanjay Patel2019-06-111-0/+190
| | | | | | | | | | | | | | We have the related getSplatValue() already in IR (see code just above the proposed addition). But sometimes we only need to know that the value is a splat rather than capture the splatted scalar value. Also, we have an isSplatValue() function already in SDAG. Motivation - recent bugs that would potentially benefit from improved splat analysis in IR: https://bugs.llvm.org/show_bug.cgi?id=37428 https://bugs.llvm.org/show_bug.cgi?id=42174 Differential Revision: https://reviews.llvm.org/D63138 llvm-svn: 363106
* [Analysis] add unit test file for VectorUtils; NFCSanjay Patel2019-06-102-0/+92
| | | | llvm-svn: 362972
* [LOOPINFO] Extend Loop object to add utilities to get the loop bounds,Whitney Tsang2019-06-051-0/+900
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | step, and loop induction variable. Summary: This PR extends the loop object with more utilities to get loop bounds, step, and loop induction variable. There already exists passes which try to obtain the loop induction variable in their own pass, e.g. loop interchange. It would be useful to have a common area to get these information. /// Example: /// for (int i = lb; i < ub; i+=step) /// <loop body> /// --- pseudo LLVMIR --- /// beforeloop: /// guardcmp = (lb < ub) /// if (guardcmp) goto preheader; else goto afterloop /// preheader: /// loop: /// i1 = phi[{lb, preheader}, {i2, latch}] /// <loop body> /// i2 = i1 + step /// latch: /// cmp = (i2 < ub) /// if (cmp) goto loop /// exit: /// afterloop: /// /// getBounds /// getInitialIVValue --> lb /// getStepInst --> i2 = i1 + step /// getStepValue --> step /// getFinalIVValue --> ub /// getCanonicalPredicate --> '<' /// getDirection --> Increasing /// getInductionVariable --> i1 /// getAuxiliaryInductionVariable --> {i1} /// isCanonical --> false Reviewers: kbarton, hfinkel, dmgreen, Meinersbur, jdoerfert, syzaara, fhahn Reviewed By: kbarton Subscribers: tvvikram, bmahjour, etiotto, fhahn, jsji, hiraditya, llvm-commits Tag: LLVM Differential Revision: https://reviews.llvm.org/D60565 llvm-svn: 362644
* Revert "Title: [LOOPINFO] Extend Loop object to add utilities to get the loop"Whitney Tsang2019-06-051-900/+0
| | | | | | This reverts commit d34797dfc26c61cea19f45669a13ea572172ba34. llvm-svn: 362615
* Title: [LOOPINFO] Extend Loop object to add utilities to get the loopWhitney Tsang2019-06-051-0/+900
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | bounds, step, and loop induction variable. Summary: This PR extends the loop object with more utilities to get loop bounds, step, and loop induction variable. There already exists passes which try to obtain the loop induction variable in their own pass, e.g. loop interchange. It would be useful to have a common area to get these information. /// Example: /// for (int i = lb; i < ub; i+=step) /// <loop body> /// --- pseudo LLVMIR --- /// beforeloop: /// guardcmp = (lb < ub) /// if (guardcmp) goto preheader; else goto afterloop /// preheader: /// loop: /// i1 = phi[{lb, preheader}, {i2, latch}] /// <loop body> /// i2 = i1 + step /// latch: /// cmp = (i2 < ub) /// if (cmp) goto loop /// exit: /// afterloop: /// /// getBounds /// getInitialIVValue --> lb /// getStepInst --> i2 = i1 + step /// getStepValue --> step /// getFinalIVValue --> ub /// getCanonicalPredicate --> '<' /// getDirection --> Increasing /// getInductionVariable --> i1 /// getAuxiliaryInductionVariable --> {i1} /// isCanonical --> false Reviewers: kbarton, hfinkel, dmgreen, Meinersbur, jdoerfert, syzaara, fhahn Reviewed By: kbarton Subscribers: tvvikram, bmahjour, etiotto, fhahn, jsji, hiraditya, llvm-commits Tag: LLVM Differential Revision: https://reviews.llvm.org/D60565 llvm-svn: 362609
* Add ScalarEvolutionsTest::SCEVExpandInsertCanonicalIV tests Artur Pilipenko2019-06-031-0/+193
| | | | | | Test insertion of canonical IV in canonical expansion mode. llvm-svn: 362432
* [SimplifyLibCalls] Fold more fortified functions into non-fortified variantsErik Pilkington2019-05-311-0/+11
| | | | | | | | | | | | When the object size argument is -1, no checking can be done, so calling the _chk variant is unnecessary. We already did this for a bunch of these functions. rdar://50797197 Differential revision: https://reviews.llvm.org/D62358 llvm-svn: 362272
* Revert [LOOPINFO] Extend Loop object to add utilities to get the loop ↵Kit Barton2019-05-231-900/+0
| | | | | | | | bounds, step, induction variable, and guard branch. This reverts r361517 (git commit 2049e4dd8f61100f88f14db33bd95d197bcbfbbc) llvm-svn: 361553
* [LOOPINFO] Extend Loop object to add utilities to get the loop bounds, ↵Kit Barton2019-05-231-0/+900
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | step, induction variable, and guard branch. Summary: This PR extends the loop object with more utilities to get loop bounds, step, induction variable, and guard branch. There already exists passes which try to obtain the loop induction variable in their own pass, e.g. loop interchange. It would be useful to have a common area to get these information. Moreover, loop fusion (https://reviews.llvm.org/D55851) is planning to use getGuard() to extend the kind of loops it is able to fuse, e.g. rotated loop with non-constant upper bound, which would have a loop guard. /// Example: /// for (int i = lb; i < ub; i+=step) /// <loop body> /// --- pseudo LLVMIR --- /// beforeloop: /// guardcmp = (lb < ub) /// if (guardcmp) goto preheader; else goto afterloop /// preheader: /// loop: /// i1 = phi[{lb, preheader}, {i2, latch}] /// <loop body> /// i2 = i1 + step /// latch: /// cmp = (i2 < ub) /// if (cmp) goto loop /// exit: /// afterloop: /// /// getBounds /// getInitialIVValue --> lb /// getStepInst --> i2 = i1 + step /// getStepValue --> step /// getFinalIVValue --> ub /// getCanonicalPredicate --> '<' /// getDirection --> Increasing /// getGuard --> if (guardcmp) goto loop; else goto afterloop /// getInductionVariable --> i1 /// getAuxiliaryInductionVariable --> {i1} /// isCanonical --> false Committed on behalf of @Whitney (Whitney Tsang). Reviewers: kbarton, hfinkel, dmgreen, Meinersbur, jdoerfert, syzaara, fhahn Reviewed By: kbarton Subscribers: tvvikram, bmahjour, etiotto, fhahn, jsji, hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D60565 llvm-svn: 361517
* [INLINER] allow inlining of blockaddresses if sole uses are callbrsNick Desaulniers2019-05-201-0/+29
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: It was supposed that Ref LazyCallGraph::Edge's were being inserted by inlining, but that doesn't seem to be the case. Instead, it seems that there was no test for a blockaddress Constant in an instruction that referenced the function that contained the instruction. Ex: ``` define void @f() { %1 = alloca i8*, align 8 2: store i8* blockaddress(@f, %2), i8** %1, align 8 ret void } ``` When iterating blockaddresses, do not add the function they refer to back to the worklist if the blockaddress is referring to the contained function (as opposed to an external function). Because blockaddress has sligtly different semantics than GNU C's address of labels, there are 3 cases that can occur with blockaddress, where only 1 can happen in GNU C due to C's scoping rules: * blockaddress is within the function it refers to (possible in GNU C). * blockaddress is within a different function than the one it refers to (not possible in GNU C). * blockaddress is used in to declare a global (not possible in GNU C). The second case is tested in: ``` $ ./llvm/build/unittests/Analysis/AnalysisTests \ --gtest_filter=LazyCallGraphTest.HandleBlockAddress ``` This patch adjusts the iteration of blockaddresses in LazyCallGraph::visitReferences to not revisit the blockaddresses function in the first case. The Linux kernel contains code that's not semantically valid at -O0; specifically code passed to asm goto. It requires that asm goto be inline-able. This patch conservatively does not attempt to handle the more general case of inlining blockaddresses that have non-callbr users (pr/39560). https://bugs.llvm.org/show_bug.cgi?id=39560 https://bugs.llvm.org/show_bug.cgi?id=40722 https://github.com/ClangBuiltLinux/linux/issues/6 https://reviews.llvm.org/rL212077 Reviewers: jyknight, eli.friedman, chandlerc Reviewed By: chandlerc Subscribers: george.burgess.iv, nathanchance, mgorny, craig.topper, mengxu.gatech, void, mehdi_amini, E5ten, chandlerc, efriedma, eraman, hiraditya, haicheng, pirama, llvm-commits, srhines Tags: #llvm Differential Revision: https://reviews.llvm.org/D58260 llvm-svn: 361173
* Save the induction binary operator in IVDescriptors for non FP induction ↵Kit Barton2019-05-142-0/+101
| | | | | | | | | | | | | | | | | | | | | | | | | variables. Summary: Currently InductionBinOps are only saved for FP induction variables, the PR extends it with non FP induction variable, so user of IVDescriptors can query the InductionBinOps for integer induction variables. The changes in hasUnsafeAlgebra() and getUnsafeAlgebraInst() are required for the existing LIT test cases to pass. As described in the comment of the two functions, one of the requirement to return true is it is a FP induction variable. The checks was not needed because InductionBinOp was not set on non FP cases before. https://reviews.llvm.org/D60565 depends on the patch. Committed on behalf of @Whitney (Whitney Tsang). Reviewers: jdoerfert, kbarton, fhahn, hfinkel, dmgreen, Meinersbur Reviewed By: jdoerfert Subscribers: mgorny, hiraditya, jsji, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D61329 llvm-svn: 360671
* An unreachable block may have a route to a reachable block, don't fast-path ↵Nick Lewycky2019-04-041-0/+14
| | | | | | | | | | return that it can't. A block reachable from the entry block can't have any route to a block that's not reachable from the entry block (if it did, that route would make it reachable from the entry block). That is the intended performance optimization for isPotentiallyReachable. For the case where we ask whether an unreachable from entry block has a route to a reachable from entry block, we can't conclude one way or the other. Fix a bug where we claimed there could be no such route. The fix in rL357425 ironically reintroduced the very bug it was fixing but only when a DominatorTree is provided. This fixes the remaining bug. llvm-svn: 357734
* Fix TargetLibraryInfoTest.ValidProto after rL357552Sam Clegg2019-04-031-0/+5
| | | | llvm-svn: 357559
* Add an optional list of blocks to avoid when looking for a path in ↵Nick Lewycky2019-04-021-17/+83
| | | | | | | | | | isPotentiallyReachable. The leads to some ambiguous overloads, so update three callers. Differential Revision: https://reviews.llvm.org/D60085 llvm-svn: 357447
* Not all blocks are reachable from entry. Don't assume they are.Nick Lewycky2019-04-011-0/+40
| | | | | | Fixes a bug in isPotentiallyReachable, noticed by inspection. llvm-svn: 357425
* [NewPM] Fix a nasty bug with analysis invalidation in the new PM.Chandler Carruth2019-03-281-10/+14
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The issue here is that we actually allow CGSCC passes to mutate IR (and therefore invalidate analyses) outside of the current SCC. At a minimum, we need to support mutating parent and ancestor SCCs to support the ArgumentPromotion pass which rewrites all calls to a function. However, the analysis invalidation infrastructure is heavily based around not needing to invalidate the same IR-unit at multiple levels. With Loop passes for example, they don't invalidate other Loops. So we need to customize how we handle CGSCC invalidation. Doing this without gratuitously re-running analyses is even harder. I've avoided most of these by using an out-of-band preserved set to accumulate the cross-SCC invalidation, but it still isn't perfect in the case of re-visiting the same SCC repeatedly *but* it coming off the worklist. Unclear how important this use case really is, but I wanted to call it out. Another wrinkle is that in order for this to successfully propagate to function analyses, we have to make sure we have a proxy from the SCC to the Function level. That requires pre-creating the necessary proxy. The motivating test case now works cleanly and is added for ArgumentPromotion. Thanks for the review from Philip and Wei! Differential Revision: https://reviews.llvm.org/D59869 llvm-svn: 357137
* [AliasAnalysis] Second prototype to cache BasicAA / anyAA state.Alina Sbirlea2019-03-222-10/+19
| | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Adding contained caching to AliasAnalysis. BasicAA is currently the only one using it. AA changes: - This patch is pulling the caches from BasicAAResults to AAResults, meaning the getModRefInfo call benefits from the IsCapturedCache as well when in "batch mode". - All AAResultBase implementations add the QueryInfo member to all APIs. AAResults APIs maintain wrapper APIs such that all alias()/getModRefInfo call sites are unchanged. - AA now provides a BatchAAResults type as a wrapper to AAResults. It keeps the AAResults instance and a QueryInfo instantiated to batch mode. It delegates all work to the AAResults instance with the batched QueryInfo. More API wrappers may be needed in BatchAAResults; only the minimum needed is currently added. MemorySSA changes: - All walkers are now templated on the AA used (AliasAnalysis=AAResults or BatchAAResults). - At build time, we optimize uses; now we create a local walker (lives only as long as OptimizeUses does) using BatchAAResults. - All Walkers have an internal AA and only use that now, never the AA in MemorySSA. The Walkers receive the AA they will use when built. - The walker we use for queries after the build is instantiated on AliasAnalysis and is built after building MemorySSA and setting AA. - All static methods doing walking are now templated on AliasAnalysisType if they are used both during build and after. If used only during build, the method now only takes a BatchAAResults. If used only after build, the method now takes an AliasAnalysis. Subscribers: sanjoy, arsenm, jvesely, nhaehnle, jlebar, george.burgess.iv, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D59315 llvm-svn: 356783
* [ValueTracking] Known bits support for unsigned saturating add/subNikita Popov2019-03-011-0/+71
| | | | | | | | | | | | | | | | We have two sources of known bits: 1. For adds leading ones of either operand are preserved. For sub leading zeros of LHS and leading ones of RHS become leading zeros in the result. 2. The saturating math is a select between add/sub and an all-ones/ zero value. As such we can carry out the add/sub known bits calculation, and only preseve the known one/zero bits respectively. Differential Revision: https://reviews.llvm.org/D58329 llvm-svn: 355223
* [MemorySSA] Make insertDef insert corresponding phi nodes.Alina Sbirlea2019-02-271-9/+9
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: The original assumption for the insertDef method was that it would not materialize Defs out of no-where, hence it will not insert phis needed after inserting a Def. However, when cloning an instruction (use case used in LICM), we do materialize Defs "out of no-where". If the block receiving a Def has at least one other Def, then no processing is needed. If the block just received its first Def, we must check where Phi placement is needed. The only new usage of insertDef is in LICM, hence the trigger for the bug. But the original goal of the method also fails to apply for the move() method. If we move a Def from the entry point of a diamond to either the left or right blocks, then the merge block must add a phi. While this usecase does not currently occur, or may be viewed as an incorrect transformation, MSSA must behave corectly given the scenario. Resolves PR40749 and PR40754. Reviewers: george.burgess.iv Subscribers: sanjoy, jlebar, Prazek, jdoerfert, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D58652 llvm-svn: 355040
* [DTU] Refine the interface and logic of applyUpdatesChijun Sima2019-02-221-25/+88
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This patch separates two semantics of `applyUpdates`: 1. User provides an accurate CFG diff and the dominator tree is updated according to the difference of `the number of edge insertions` and `the number of edge deletions` to infer the status of an edge before and after the update. 2. User provides a sequence of hints. Updates mentioned in this sequence might never happened and even duplicated. Logic changes: Previously, removing invalid updates is considered a side-effect of deduplication and is not guaranteed to be reliable. To handle the second semantic, `applyUpdates` does validity checking before deduplication, which can cause updates that have already been applied to be submitted again. Then, different calls to `applyUpdates` might cause unintended consequences, for example, ``` DTU(Lazy) and Edge A->B exists. 1. DTU.applyUpdates({{Delete, A, B}, {Insert, A, B}}) // User expects these 2 updates result in a no-op, but {Insert, A, B} is queued 2. Remove A->B 3. DTU.applyUpdates({{Delete, A, B}}) // DTU cancels this update with {Insert, A, B} mentioned above together (Unintended) ``` But by restricting the precondition that updates of an edge need to be strictly ordered as how CFG changes were made, we can infer the initial status of this edge to resolve this issue. Interface changes: The second semantic of `applyUpdates` is separated to `applyUpdatesPermissive`. These changes enable DTU(Lazy) to use the first semantic if needed, which is quite useful in `transforms/utils`. Reviewers: kuhar, brzycki, dmgreen, grosser Reviewed By: brzycki Subscribers: hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D58170 llvm-svn: 354669
* [DTU] Deprecate insertEdge*/deleteEdge*Chijun Sima2019-02-221-13/+18
| | | | | | | | | | | | | | | | Summary: This patch converts all existing `insertEdge*/deleteEdge*` to `applyUpdates` and marks `insertEdge*/deleteEdge*` as deprecated. Reviewers: kuhar, brzycki Reviewed By: kuhar, brzycki Subscribers: hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D58443 llvm-svn: 354652
* Move DomTreeUpdater from IR to AnalysisRichard Trieu2019-02-062-1/+728
| | | | | | | | DomTreeUpdater depends on headers from Analysis, but is in IR. This is a layering violation since Analysis depends on IR. Relocate this code from IR to Analysis to fix the layering violation. llvm-svn: 353265
* [opaque pointer types] Pass value type to GetElementPtr creation.James Y Knight2019-02-013-3/+4
| | | | | | | | | This cleans up all GetElementPtr creation in LLVM to explicitly pass a value type rather than deriving it from the pointer's element-type. Differential Revision: https://reviews.llvm.org/D57173 llvm-svn: 352913
* [opaque pointer types] Pass value type to LoadInst creation.James Y Knight2019-02-016-43/+45
| | | | | | | | | This cleans up all LoadInst creation in LLVM to explicitly pass the value type rather than deriving it from the pointer's element-type. Differential Revision: https://reviews.llvm.org/D57172 llvm-svn: 352911
* [opaque pointer types] Add a FunctionCallee wrapper type, and use it.James Y Knight2019-02-017-26/+30
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Recommit r352791 after tweaking DerivedTypes.h slightly, so that gcc doesn't choke on it, hopefully. Original Message: The FunctionCallee type is effectively a {FunctionType*,Value*} pair, and is a useful convenience to enable code to continue passing the result of getOrInsertFunction() through to EmitCall, even once pointer types lose their pointee-type. Then: - update the CallInst/InvokeInst instruction creation functions to take a Callee, - modify getOrInsertFunction to return FunctionCallee, and - update all callers appropriately. One area of particular note is the change to the sanitizer code. Previously, they had been casting the result of `getOrInsertFunction` to a `Function*` via `checkSanitizerInterfaceFunction`, and storing that. That would report an error if someone had already inserted a function declaraction with a mismatching signature. However, in general, LLVM allows for such mismatches, as `getOrInsertFunction` will automatically insert a bitcast if needed. As part of this cleanup, cause the sanitizer code to do the same. (It will call its functions using the expected signature, however they may have been declared.) Finally, in a small number of locations, callers of `getOrInsertFunction` actually were expecting/requiring that a brand new function was being created. In such cases, I've switched them to Function::Create instead. Differential Revision: https://reviews.llvm.org/D57315 llvm-svn: 352827
* Revert "[opaque pointer types] Add a FunctionCallee wrapper type, and use it."James Y Knight2019-01-317-30/+26
| | | | | | | | | This reverts commit f47d6b38c7a61d50db4566b02719de05492dcef1 (r352791). Seems to run into compilation failures with GCC (but not clang, where I tested it). Reverting while I investigate. llvm-svn: 352800
* [opaque pointer types] Add a FunctionCallee wrapper type, and use it.James Y Knight2019-01-317-26/+30
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The FunctionCallee type is effectively a {FunctionType*,Value*} pair, and is a useful convenience to enable code to continue passing the result of getOrInsertFunction() through to EmitCall, even once pointer types lose their pointee-type. Then: - update the CallInst/InvokeInst instruction creation functions to take a Callee, - modify getOrInsertFunction to return FunctionCallee, and - update all callers appropriately. One area of particular note is the change to the sanitizer code. Previously, they had been casting the result of `getOrInsertFunction` to a `Function*` via `checkSanitizerInterfaceFunction`, and storing that. That would report an error if someone had already inserted a function declaraction with a mismatching signature. However, in general, LLVM allows for such mismatches, as `getOrInsertFunction` will automatically insert a bitcast if needed. As part of this cleanup, cause the sanitizer code to do the same. (It will call its functions using the expected signature, however they may have been declared.) Finally, in a small number of locations, callers of `getOrInsertFunction` actually were expecting/requiring that a brand new function was being created. In such cases, I've switched them to Function::Create instead. Differential Revision: https://reviews.llvm.org/D57315 llvm-svn: 352791
* [NFC] Fix warnings in unit test of r351725Max Kazantsev2019-01-211-6/+6
| | | | llvm-svn: 351726
* [SCEV][NFC] Introduces expression sizes estimationMax Kazantsev2019-01-211-0/+50
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch introduces the field `ExpressionSize` in SCEV. This field is calculated only once on SCEV creation, and it represents the complexity of this SCEV from arithmetical point of view (not from the point of the number of actual different SCEV nodes that are used in the expression). Roughly saying, it is the number of operands and operations symbols when we print this SCEV. A formal definition is following: if SCEV `X` has operands `Op1`, `Op2`, ..., `OpN`, then Size(X) = 1 + Size(Op1) + Size(Op2) + ... + Size(OpN). Size of SCEVConstant and SCEVUnknown is one. Expression size may be used as a universal way to limit SCEV transformations for huge SCEVs. Currently, we have a bunch of options that represents various limits (such as recursion depth limit) that may not make any sense from the point of view of a LLVM users who is not familiar with SCEV internals, and all these different options pursue one goal. A more general rule that may potentially allow us to get rid of this redundancy in options is "do not make transformations with SCEVs of huge size". It can apply to all SCEV traversals and transformations that may need to visit a SCEV node more than once, hence they are prone to combinatorial explosions. This patch only introduces SCEV sizes calculation as NFC, its utilization will be introduced in follow-up patches. Differential Revision: https://reviews.llvm.org/D35989 Reviewed By: reames llvm-svn: 351725
* Replace llvm::isPodLike<...> by llvm::is_trivially_copyable<...>Serge Guelton2019-01-201-0/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | As noted in https://bugs.llvm.org/show_bug.cgi?id=36651, the specialization for isPodLike<std::pair<...>> did not match the expectation of std::is_trivially_copyable which makes the memcpy optimization invalid. This patch renames the llvm::isPodLike trait into llvm::is_trivially_copyable. Unfortunately std::is_trivially_copyable is not portable across compiler / STL versions. So a portable version is provided too. Note that the following specialization were invalid: std::pair<T0, T1> llvm::Optional<T> Tests have been added to assert that former specialization are respected by the standard usage of llvm::is_trivially_copyable, and that when a decent version of std::is_trivially_copyable is available, llvm::is_trivially_copyable is compared to std::is_trivially_copyable. As of this patch, llvm::Optional is no longer considered trivially copyable, even if T is. This is to be fixed in a later patch, as it has impact on a long-running bug (see r347004) Note that GCC warns about this UB, but this got silented by https://reviews.llvm.org/D50296. Differential Revision: https://reviews.llvm.org/D54472 llvm-svn: 351701
OpenPOWER on IntegriCloud