[Support] Add KnownBits implementations for avgFloor and avgCeil

[RKSimon]

Followup to #84211

These are implemented as part of #76644 but in SelectionDAG not in the KnownBits class directly

• Add KnownBIts::avgfloors/avgflooru/avgceils/avgceilu implementations based off [AArch64] SimplifyDemandedBitsForTargetNode - add AArch64ISD::BICi handling #76644
• Add exhaustive KnownBits test coverage (can it be optimal or just correct?)
• Depending upon whether [AArch64] SimplifyDemandedBitsForTargetNode - add AArch64ISD::BICi handling #76644 lands before or after this, you might need to update the SelectionDAG code or coordinate with @snikitav

[llvmbot]

Hi!

This issue may be a good introductory issue for people new to working on LLVM. If you would like to work on this issue, your first steps are:

1. In the comments of the issue, request for it to be assigned to you.
2. Fix the issue locally.
3. Run the test suite locally. Remember that the subdirectories under test/ create fine-grained testing targets, so you can e.g. use make check-clang-ast to only run Clang's AST tests.
4. Create a Git commit.
5. Run git clang-format HEAD~1 to format your changes.
6. Open a pull request to the upstream repository on GitHub. Detailed instructions can be found in GitHub's documentation.

If you have any further questions about this issue, don't hesitate to ask via a comment in the thread below.

[llvmbot]

@llvm/issue-subscribers-good-first-issue

Author: Simon Pilgrim (RKSimon)

Followup to #84211

These are implemented as part of #76644 but in SelectionDAG not in the KnownBits class directly

• Add KnownBIts::avgfloors/avgflooru/avgceils/avgceilu implementations based off #76644
• Add exhaustive KnownBits test coverage (can it be optimal or just correct?)
• Depending upon whether #76644 lands before or after this, you might need to update the SelectionDAG code or coordinate with @snikitav

[Sh0g0-1758]

Hey @RKSimon, I would like to work on this.

[changkhothuychung]

Hi I would like to work on this if this is available

[EugeneZelenko]

@changkhothuychung: Just create pull request and mention it on this page.

[RKSimon]

@changkhothuychung @Sh0g0-1758 Both of you have requested assignment for #84640 and #84639 - do either of you have a preference? I'd prefer to keep the good-first-issue tickets distributed.

[Sh0g0-1758]

I have started working on #84639

[changkhothuychung]

@RKSimon RK
Thank you for assigning this ticket to me. I have a few questions for direction.

• I am supposed to add the implementations in the file KnownBits.cpp right?
• Is there any documentation which explains what KnownBits are for and the use case of it? So I can have a better understanding of what I am doing. Thanks.

[RKSimon]

KnownBits are for analysis to allow us to track whether any specific bits of a variable are guaranteed to be zero or one, and help considerably with codegen simplification.

The implementations need moving into KnownBits.cpp - #76644 has the 4 implementations merged into 1 case, but ideally we'd want them separate.

KnownBits::avgCeilS
KnownBits::avgCeilU
KnownBits::avgFloorS
KnownBits::avglFoorU

The exhaustive tests will need to be added around here:

llvm-project/llvm/unittests/Support/KnownBitsTest.cpp

Lines 601 to 609 in 995d1d1

	testBinaryOpExhaustive(
	[](const KnownBits &Known1, const KnownBits &Known2) {
	return KnownBits::mulhu(Known1, Known2);
	},
	[](const APInt &N1, const APInt &N2) {
	unsigned Bits = N1.getBitWidth();
	return (N1.zext(2 * Bits) * N2.zext(2 * Bits)).extractBits(Bits, Bits);
	},
	checkCorrectnessOnlyBinary);

You will need to wait until #84431 is completed so the equivalent APInt constant methods are available.

[RKSimon]

@changkhothuychung reverse-ping

[changkhothuychung]

@RKSimon Hi, I am figuring out how to do the implementations, I will make a PR as soon as I have something.

[RKSimon]

You can begin be converting the APInt expansions into KnownBits equivalents:

llvm-project/llvm/lib/Support/APInt.cpp

Lines 3105 to 3123 in 6f44bb7

	APInt APIntOps::avgFloorS(const APInt &C1, const APInt &C2) {
	// Return floor((C1 + C2) / 2)
	return (C1 & C2) + (C1 ^ C2).ashr(1);
	}
	APInt APIntOps::avgFloorU(const APInt &C1, const APInt &C2) {
	// Return floor((C1 + C2) / 2)
	return (C1 & C2) + (C1 ^ C2).lshr(1);
	}
	APInt APIntOps::avgCeilS(const APInt &C1, const APInt &C2) {
	// Return ceil((C1 + C2) / 2)
	return (C1 | C2) - (C1 ^ C2).ashr(1);
	}
	APInt APIntOps::avgCeilU(const APInt &C1, const APInt &C2) {
	// Return ceil((C1 + C2) / 2)
	return (C1 | C2) - (C1 ^ C2).lshr(1);
	}

[RKSimon]

Fixed by #86445 ( we might be able to improve optimal testing in a future commit)

[changkhothuychung]

@RKSimon
I have a quick conceptual question about this part of llvm since im still new to the repo. It seems like to me SelectionDAG is a graph, and each node will contain an assembly instruction for later stages to generate assembly code is it correct? What parts of llvm will take in a SelectionDAG and begin the code generation process?

And also, are all the code optimizations done at SelectionDAG level? Thanks.

[RKSimon]

Most optimization is done in the middle end (InstCombine etc.), aiming for optimized, canonical code but very little is platform specific (just some combining of target intrinsics and some cost driven optimizations).

The Instruction selection stage (SelectionDAG, FastISel, GlobalISel) then transforms the IR into types/ops suitable for a specific target: https://llvm.org/docs/CodeGenerator.html#introduction-to-selectiondags, and then converts to a DAG of target instructions and then MachineInstructions.