[NFC] Switch a few uses of undef to poison as placeholders for unreachble code

Pipe potentially invalid InstructionCost through CodeMetrics

Per the documentation in Support/InstructionCost.h, the purpose of an invalid cost is so that clients can change behavior on impossible t

Pipe potentially invalid InstructionCost through CodeMetrics

Per the documentation in Support/InstructionCost.h, the purpose of an invalid cost is so that clients can change behavior on impossible to cost inputs. CodeMetrics was instead asserting that invalid costs never occurred.

On a target with an incomplete cost model - e.g. RISCV - this means that transformations would crash on (falsely) invalid constructs - e.g. scalable vectors. While we certainly should improve the cost model - and I plan to do so in the near future - we also shouldn't be crashing. This violates the explicitly stated purpose of an invalid InstructionCost.

I updated all of the "easy" consumers where bailouts were locally obvious. I plan to follow up with loop unroll in a following change.

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

show more ...

[Transforms] Use llvm::is_contained (NFC)

[DFAJumpThreading] Relax analysis to handle unpredictable initial values

Responding to a feature request from the Rust community:

https://github.com/rust-lang/rust/issues/80630

void foo(X) {

[DFAJumpThreading] Relax analysis to handle unpredictable initial values

Responding to a feature request from the Rust community:

https://github.com/rust-lang/rust/issues/80630

void foo(X) {
for (...)
switch (X)
case A
X = B
case B
X = C
}

Even though the initial switch value is non-constant, the switch
statement can still be threaded: the initial value will hit the switch
statement but the rest of the state changes will proceed by jumping
unconditionally.

The early predictability check is relaxed to allow unpredictable values
anywhere, but later, after the paths through the switch statement have
been enumerated, no non-constant state values are allowed along the
paths. Any state value not along a path will be an initial switch value,
which can be safely ignored.

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

show more ...

Add missing include under -DEXPENSIVE_CHECKS

This is a follow-up to 59630917d6cc7c4a273f617f92bf6190ee2992e1

Cleanup includes: Transform/Scalar

Estimated impact on preprocessor output line:
before: 1062981579
after: 1062494547

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cl

Cleanup includes: Transform/Scalar

Estimated impact on preprocessor output line:
before: 1062981579
after: 1062494547

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cleanup
Differential Revision: https://reviews.llvm.org/D120817

show more ...

Cleanup includes: TransformsUtils

Estimation on the impact on preprocessor output:
before: 1065307662
after: 1064800684

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-

Cleanup includes: TransformsUtils

Estimation on the impact on preprocessor output:
before: 1065307662
after: 1064800684

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cleanup
Differential Revision: https://reviews.llvm.org/D120741

show more ...

[DFAJumpThreading] make update order deterministic

We tracked down some non-determinism in compilation output to the
DFAJumpThreading pass. These changes fixed our issue:

* Make the DefMap type a M

[DFAJumpThreading] make update order deterministic

We tracked down some non-determinism in compilation output to the
DFAJumpThreading pass. These changes fixed our issue:

* Make the DefMap type a MapVector to make its iteration order depend on
insertion order.
* Sort the values to be inserted into NewDefs by instruction order to
make the insertion order deterministic. Since these values come from
iterating over a ValueMap, which doesn't have deterministic iteration
order, I couldn't fix this at its source.

Reviewed By: alexey.zhikhar

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

show more ...

[DFAJumpThreading] Determinator BB should precede switch-defining BB

Otherwise, it is possible that the state defined in the determinator
block defines the state for the next iteration of the loop,

[DFAJumpThreading] Determinator BB should precede switch-defining BB

Otherwise, it is possible that the state defined in the determinator
block defines the state for the next iteration of the loop, rather than
for the current one.

Fixes llvm-test-suite's
SingleSource/Regression/C/gcc-c-torture/execute/pr80421.c

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

show more ...

Use {DenseSet,SmallPtrSet}::contains (NFC)

[llvm] Use pop_back_val (NFC)

MainSwitch::isValidSelectInst - don't dereference dyn_cast<> results.

We've already checked that the pointer isa<PHINode>, so we can use cast<Instruction> safely.

Fixes static analyser warning.

[llvm][clang][NFC] updates inline licence info

Some files still contained the old University of Illinois Open Source
Licence header. This patch replaces that with the Apache 2 with LLVM
Exception li

[llvm][clang][NFC] updates inline licence info

Some files still contained the old University of Illinois Open Source
Licence header. This patch replaces that with the Apache 2 with LLVM
Exception licence.

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

show more ...

[DFAJumpThreading] Use SmallPtrSet for Visited (NFC)

This set is only used for contains checks, so there is no need to
use std::set.

[DFAJumpThreading] Use insert return value (NFC)

Rather than find + insert. Also use range based for loop.

[DFAJumpThreading] Remove unnecessary includes (NFC)

This file uses neither unordered_map nor unordered_set.

[DFAJumpThreading] Mark DT as preserved in LegacyPM

It is marked as preserved in NewPM, but not LegacyPM.

Remove unused include that's also a layering violation. NFC.

Add jump-threading optimization for deterministic finite automata

The current JumpThreading pass does not jump thread loops since it can
result in irreducible control flow that harms other optimizat

Add jump-threading optimization for deterministic finite automata

The current JumpThreading pass does not jump thread loops since it can
result in irreducible control flow that harms other optimizations. This
prevents switch statements inside a loop from being optimized to use
unconditional branches.

This code pattern occurs in the core_state_transition function of
Coremark. The state machine can be implemented manually with goto
statements resulting in a large runtime improvement, and this transform
makes the switch implementation match the goto version in performance.

This patch specifically targets switch statements inside a loop that
have the opportunity to be threaded. Once it identifies an opportunity,
it creates new paths that branch directly to the correct code block.
For example, the left CFG could be transformed to the right CFG:

```
sw.bb sw.bb
/ | \ / | \
case1 case2 case3 case1 case2 case3
\ | / / | \
latch.bb latch.2 latch.3 latch.1
br sw.bb / | \
sw.bb.2 sw.bb.3 sw.bb.1
br case2 br case3 br case1
```

Co-author: Justin Kreiner @jkreiner
Co-author: Ehsan Amiri @amehsan

Reviewed By: SjoerdMeijer

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

show more ...