BypassSlowDivision: Fix dropping debug info

I don't know anything about debug info, but this seems like more work
should be necessary. This constructs a new IRBuilder and reconstructs
the original d

BypassSlowDivision: Fix dropping debug info

I don't know anything about debug info, but this seems like more work
should be necessary. This constructs a new IRBuilder and reconstructs
the original divides rather than moving the original.

One problem this has is if a div/rem pair are handled, both end up
with the same debugloc. I'm not sure how to fix this, since this uses
a cache when it sees the same input operands again, which will have
the first instance's location attached.

show more ...

SmallPtrSet::find -> SmallPtrSet::count

The latter is more readable and more efficient. While there clean up
some double lookups. NFCI.

[BypassSlowDivision][CodeGenPrepare] avoid crashing on unused code (PR43514)

https://bugs.llvm.org/show_bug.cgi?id=43514

llvm-svn: 373394

Update the file headers across all of the LLVM projects in the monorepo
to reflect the new license.

We understand that people may be surprised that we're moving the header
entirely to discuss the ne

Update the file headers across all of the LLVM projects in the monorepo
to reflect the new license.

We understand that people may be surprised that we're moving the header
entirely to discuss the new license. We checked this carefully with the
Foundation's lawyer and we believe this is the correct approach.

Essentially, all code in the project is now made available by the LLVM
project under our new license, so you will see that the license headers
include that license only. Some of our contributors have contributed
code under our old license, and accordingly, we have retained a copy of
our old license notice in the top-level files in each project and
repository.

llvm-svn: 351636

show more ...

[BypassSlowDivision] Teach bypass slow division not to interfere with div by constant where constants have been constant hoisted, but not moved from their basic block

DAGCombiner doesn't pay attenti

[BypassSlowDivision] Teach bypass slow division not to interfere with div by constant where constants have been constant hoisted, but not moved from their basic block

DAGCombiner doesn't pay attention to whether constants are opaque before doing the div by constant optimization. So BypassSlowDivision shouldn't introduce control flow that would make DAGCombiner unable to see an opaque constant. This can occur when a div and rem of the same constant are used in the same basic block. it will be hoisted, but not leave the block.

Longer term we probably need to look into the X86 immediate cost model used by constant hoisting and maybe not mark div/rem immediates for hoisting at all.

This fixes the case from PR38649.

Differential Revision: https://reviews.llvm.org/D51000

llvm-svn: 340303

show more ...

Move Analysis/Utils/Local.h back to Transforms

Review feedback from r328165. Split out just the one function from the
file that's used by Analysis. (As chandlerc pointed out, the original
change onl

Move Analysis/Utils/Local.h back to Transforms

Review feedback from r328165. Split out just the one function from the
file that's used by Analysis. (As chandlerc pointed out, the original
change only moved the header and not the implementation anyway - which
was fine for the one function that was used (since it's a
template/inlined in the header) but not in general)

llvm-svn: 333954

show more ...

Remove \brief commands from doxygen comments.

We've been running doxygen with the autobrief option for a couple of
years now. This makes the \brief markers into our comments
redundant. Since they ar

Remove \brief commands from doxygen comments.

We've been running doxygen with the autobrief option for a couple of
years now. This makes the \brief markers into our comments
redundant. Since they are a visual distraction and we don't want to
encourage more \brief markers in new code either, this patch removes
them all.

Patch produced by

for i in $(git grep -l '\\brief'); do perl -pi -e 's/\\brief //g' $i & done

Differential Revision: https://reviews.llvm.org/D46290

llvm-svn: 331272

show more ...

Fix a couple of layering violations in Transforms

Remove #include of Transforms/Scalar.h from Transform/Utils to fix layering.

Transforms depends on Transforms/Utils, not the other way around. So
r

Fix a couple of layering violations in Transforms

Remove #include of Transforms/Scalar.h from Transform/Utils to fix layering.

Transforms depends on Transforms/Utils, not the other way around. So
remove the header and the "createStripGCRelocatesPass" function
declaration (& definition) that is unused and motivated this dependency.

Move Transforms/Utils/Local.h into Analysis because it's used by
Analysis/MemoryBuiltins.cpp.

llvm-svn: 328165

show more ...

[BypassSlowDivision] Improve our handling of divisions by constants

(This reapplies r314253. r314253 was reverted on r314482 because of a
correctness regression on P100, but that regression was ide

[BypassSlowDivision] Improve our handling of divisions by constants

(This reapplies r314253. r314253 was reverted on r314482 because of a
correctness regression on P100, but that regression was identified to be
something else.)

Summary:
Don't bail out on constant divisors for divisions that can be narrowed without
introducing control flow . This gives us a 32 bit multiply instead of an
emulated 64 bit multiply in the generated PTX assembly.

Reviewers: jlebar

Subscribers: jholewinski, mcrosier, llvm-commits

Differential Revision: https://reviews.llvm.org/D38265

llvm-svn: 319677

show more ...

[Transforms] Fix some Clang-tidy modernize and Include What You Use warnings; other minor fixes (NFC).

llvm-svn: 316034

Revert "[BypassSlowDivision] Improve our handling of divisions by constants"

This reverts commit r314253. It causes a miscompile on P100 in an internal
benchmark. Reverting while I investigate.

l

Revert "[BypassSlowDivision] Improve our handling of divisions by constants"

This reverts commit r314253. It causes a miscompile on P100 in an internal
benchmark. Reverting while I investigate.

llvm-svn: 314482

show more ...

[BypassSlowDivision] Improve our handling of divisions by constants

Summary:
Don't bail out on constant divisors for divisions that can be narrowed without
introducing control flow . This gives us

[BypassSlowDivision] Improve our handling of divisions by constants

Summary:
Don't bail out on constant divisors for divisions that can be narrowed without
introducing control flow . This gives us a 32 bit multiply instead of an
emulated 64 bit multiply in the generated PTX assembly.

Reviewers: jlebar

Subscribers: jholewinski, mcrosier, llvm-commits

Differential Revision: https://reviews.llvm.org/D38265

llvm-svn: 314253

show more ...

[BypassSlowDivision] move map helper code to header; NFC

We can reuse this code with other div/rem transforms as shown in:
https://reviews.llvm.org/D31037
https://bugs.llvm.org/show_bug.cgi?id=3102

[BypassSlowDivision] move map helper code to header; NFC

We can reuse this code with other div/rem transforms as shown in:
https://reviews.llvm.org/D31037
https://bugs.llvm.org/show_bug.cgi?id=31028

llvm-svn: 311661

show more ...

[KnownBits] Add bit counting methods to KnownBits struct and use them where possible

This patch adds min/max population count, leading/trailing zero/one bit counting methods.

The min methods return

[KnownBits] Add bit counting methods to KnownBits struct and use them where possible

This patch adds min/max population count, leading/trailing zero/one bit counting methods.

The min methods return answers based on bits that are known without considering unknown bits. The max methods give answers taking into account the largest count that unknown bits could give.

Differential Revision: https://reviews.llvm.org/D32931

llvm-svn: 302925

show more ...

[ValueTracking] Introduce a KnownBits struct to wrap the two APInts for computeKnownBits

This patch introduces a new KnownBits struct that wraps the two APInt used by computeKnownBits. This allows u

[ValueTracking] Introduce a KnownBits struct to wrap the two APInts for computeKnownBits

This patch introduces a new KnownBits struct that wraps the two APInt used by computeKnownBits. This allows us to treat them as more of a unit.

Initially I've just altered the signatures of computeKnownBits and InstCombine's simplifyDemandedBits to pass a KnownBits reference instead of two separate APInt references. I'll do similar to the SelectionDAG version of computeKnownBits/simplifyDemandedBits as a separate patch.

I've added a constructor that allows initializing both APInts to the same bit width with a starting value of 0. This reduces the repeated pattern of initializing both APInts. Once place default constructed the APInts so I added a default constructor for those cases.

Going forward I would like to add more methods that will work on the pairs. For example trunc, zext, and sext occur on both APInts together in several places. We should probably add a clear method that can be used to clear both pieces. Maybe a method to check for conflicting information. A method to return (Zero|One) so we don't write it out everywhere. Maybe a method for (Zero|One).isAllOnesValue() to determine if all bits are known. I'm sure there are many other methods we can come up with.

Differential Revision: https://reviews.llvm.org/D32376

llvm-svn: 301432

show more ...

[BypassSlowDivision] Do not bypass division of hash-like values

Disable bypassing if one of the operands looks like a hash value. Slow
division often occurs in hashtable implementations and fast div

[BypassSlowDivision] Do not bypass division of hash-like values

Disable bypassing if one of the operands looks like a hash value. Slow
division often occurs in hashtable implementations and fast division is
never taken there because a hash value is extremely unlikely to have
enough upper bits set to zero.

A value is considered to be hash-like if it is produced by

1) XOR operation
2) Multiplication by a constant wider than the shorter type
3) PHI node with all incoming values being hash-like

Differential Revision: https://reviews.llvm.org/D28200

llvm-svn: 299329

show more ...

[BypassSlowDivision] Use ValueTracking to simplify run-time checks

ValueTracking is used for more thorough analysis of operands. Based on the
analysis, either run-time checks can be simplified (e.g.

[BypassSlowDivision] Use ValueTracking to simplify run-time checks

ValueTracking is used for more thorough analysis of operands. Based on the
analysis, either run-time checks can be simplified (e.g. check only one operand
instead of two) or the transformation can be avoided. For example, it is quite
often the case that a divisor is promoted from a shorter type and run-time
checks for it are redundant.

With additional compile-time analysis of values, two special cases naturally
arise and are addressed by the patch:

1) Both operands are known to be short enough. Then, the long division can be
simply replaced with a short one without CFG modification.

2) If a division is unsigned and the dividend is known to be short then the
long division is not needed at all. Because if the divisor is too big for
short division then the quotient is obviously zero (and the remainder is
equal to the dividend). Actually, the division is not needed when
(divisor > dividend).

Differential Revision: https://reviews.llvm.org/D29897

llvm-svn: 296832

show more ...

[BypassSlowDivision] Refactor fast division insertion logic (NFC)

The most important goal of the patch is to break large insertFastDiv function
into separate pieces, so that later a different fast i

[BypassSlowDivision] Refactor fast division insertion logic (NFC)

The most important goal of the patch is to break large insertFastDiv function
into separate pieces, so that later a different fast insertion logic can be
implemented using some of these pieces.

Differential Revision: https://reviews.llvm.org/D29896

llvm-svn: 296828

show more ...

[BypassSlowDivision] Handle division by constant numerators better.

Summary:
We don't do BypassSlowDivision when the denominator is a constant, but
we do do it when the numerator is a constant.

Thi

[BypassSlowDivision] Handle division by constant numerators better.

Summary:
We don't do BypassSlowDivision when the denominator is a constant, but
we do do it when the numerator is a constant.

This patch makes two related changes to BypassSlowDivision when the
numerator is a constant:

* If the numerator is too large to fit into the bypass width, don't
bypass slow division (because we'll never run the smaller-width
code).

* If we bypass slow division where the numerator is a constant, don't
OR together the numerator and denominator when determining whether
both operands fit within the bypass width. We need to check only the
denominator.

Reviewers: tra

Subscribers: llvm-commits, jholewinski

Differential Revision: https://reviews.llvm.org/D26699

llvm-svn: 287062

show more ...

[BypassSlowDivision] Simplify partially-tautological if statement.

if (A || (B && A)) --> if (A).

llvm-svn: 287061

Don't leave unused divs/rems sitting around in BypassSlowDivision.

Summary:
This "pass" eagerly creates div and rem instructions even when only one
is needed -- it relies on a later pass (machine DC

Don't leave unused divs/rems sitting around in BypassSlowDivision.

Summary:
This "pass" eagerly creates div and rem instructions even when only one
is needed -- it relies on a later pass (machine DCE?) to clean them up.

This is problematic not just from a cleanliness perspective (this pass
is running during CodeGenPrepare, so should leave the IR in a better
state), but it also creates a problem for instruction selection. If we
always have a div+rem, isel will always select a divrem instruction (if
possible), even when a single div or rem would do.

Specifically, in NVPTX, we want to compute rem from the output of div,
if available. But if a div is not available, we want to leave the rem
alone. This transformation is overeager if div is always available.

Because this code runs as part of CodeGenPrepare, it's nontrivial to
write a test for this change. But this will effectively be tested by
a later patch which adds the aforementioned change to NVPTX isel.

Reviewers: tra

Subscribers: llvm-commits

Differential Revision: https://reviews.llvm.org/D26088

llvm-svn: 285460

show more ...

Don't claim the udiv created in BypassSlowDivision is exact.

Summary:
In BypassSlowDivision's short-dividend path, we would create e.g.

udiv exact i32 %a, %b

"exact" here means that we are asser

Don't claim the udiv created in BypassSlowDivision is exact.

Summary:
In BypassSlowDivision's short-dividend path, we would create e.g.

udiv exact i32 %a, %b

"exact" here means that we are asserting that %a is a multiple of %b.
But we have no reason to believe this must be true -- this is just a
bug, as far as I can tell.

Reviewers: tra

Subscribers: jholewinski, llvm-commits

Differential Revision: https://reviews.llvm.org/D26097

llvm-svn: 285459

show more ...

Clarify that the bypassSlowDivision optimization operates on a single BB [v2]

Update some comments to be more explicit.

Change bypassSlowDivision and the functions it calls so that they take
BasicB

Clarify that the bypassSlowDivision optimization operates on a single BB [v2]

Update some comments to be more explicit.

Change bypassSlowDivision and the functions it calls so that they take
BasicBlock*s and Instruction*s, rather than Function::iterator&s and
BasicBlock::iterator&s.

Change the APIs so that the caller is responsible for updating the
iterator, rather than the callee. This makes control flow much easier
to follow.

Patch by Justin Lebar!

llvm-svn: 256789

show more ...

TransformUtils: Remove implicit ilist iterator conversions, NFC

Continuing the work from last week to remove implicit ilist iterator
conversions. First related commit was probably r249767, with som

TransformUtils: Remove implicit ilist iterator conversions, NFC

Continuing the work from last week to remove implicit ilist iterator
conversions. First related commit was probably r249767, with some more
motivation in r249925. This edition gets LLVMTransformUtils compiling
without the implicit conversions.

No functional change intended.

llvm-svn: 250142

show more ...

Revert r240137 (Fixed/added namespace ending comments using clang-tidy. NFC)

Apparently, the style needs to be agreed upon first.

llvm-svn: 240390