Hi Alon, Thanks for the patch!

This is a great addition. Thanks!

I've tested this patch with our version of LLVM and it passes our tests. I'm ok with adding the patch as-is, as long as no one else would object.

Unfortunately, I've had no luck producing a test case that generates this type of graph.

In D75918#1916326, @lsaba wrote:

In D75918#1916156, @bcahoon wrote:

Hi @lsaba - this fix looks good to me. Thanks! It will be challenging to create a test case on Hexagon due to the output dependences. How to do get so many output dependences on your target?

re
Thanks for the fast reply!
we have an implicit physical register that certain instructions define, thus having several instructions in the code would create these output chains, the most similar to this that I found in Hexagon was the usr_ovf register, but I also saw that the Output Deps for these registers get removed in HexagonSubtarget::UsrOverflowMutation::apply.

(In powerPC there's a carry register, but the Output latency is 0)

I think stores to physical registers would also create such output chains?

This calculation could also happen with Data dependencies if there is more than one def,use chain between two instructions (for example multiple output instructions), are those present in Hexagon?

Hi @lsaba - this fix looks good to me. Thanks! It will be challenging to create a test case on Hexagon due to the output dependences. How to do get so many output dependences on your target?

Thanks for the patch! Your suggested change is correct. The original code only "worked" because output dependences are rare. But, I can see that if the DAG is more complicated, and there is a mix of output and order dependences, that the original code would cause problems when computing the MII. If you have a test case, please add one.

Hi James,

Thanks for the patch! My only concern is with all the checks in the test case. Checking for the exact code sequence can be very sensitive to other changes in the compiler that are unrelated to this patch.

Looks good to me. Thanks for the fix!

Looks good to me. Thanks for the contribution!

Thanks for the patch! I've been trying to create a test case, but haven't had much luck.

Hi Yan,

Thanks. I didn't realise there could be nested hardware loops. Good to see there are not worse. Are you OK with me leaving them as they are here, and you fixing them as you think is best?

Hi David,

Hi Alexey,

Just a couple of minor comments on formatting. Otherwise, it looks good to me. Thanks!

In D49671#1277445, @kparzysz wrote:

Hexagon packets (bundles) have 4 slots, numbered 0..3. Each one of the three instructions (2 x S2_extractu, and PS_call_nr) can only go in slots 2 or 3, so something went horribly wrong.

As it is now, this is very bad, so please do not commit this until we figure this out.

Looks good to me.

Just a minor question - looks good otherwise.

Changed code in the patch to use static_cast. I'll submit a separate patch to fix the other occurrences of a cast.

Fixed test case. Needed an extra llc option to work correctly.

Hi David,

This patch looks good to me. I applied it to our code and ran some of our internal correctness and performance tests (for Hexagon), and the results came back clean.

This change looks correct to me. I agree with you that those functions shouldn't return the same direction vectors and that the Src version is wrong.

I did some debugging:
For the given example, after the node order is generated, the pipeliner is able to find a schedule with II=1.
However, when the "orderDependence" function is called from inside the "finalizeSchedule" function,
it gets caught in an infinite recursion. This warrants further investigation.

Thanks again for the patch to the pipeliner. I think it looks good, so feel free to commit if you're able to after addressing the final comment.

Thanks for the detailed explanation. That make sense, and I agree that the ZLD/ZLH is a more general/better solution.

Thanks for adding a patch to the pipeliner! I think what the patch is attempting is a good thing to add to the heuristic. Though I would have expected that the check for hasDataDependence would generate the correct node order for the example provided in the comment? Maybe only if hasDataDependence is extended to handle other types of dependences? But, this patch is probably cheaper since it pre-computes the information. I like the addition of the isValidNode as well.

Hi Ning,

Sorry for the delay in responding. I've been trying to create a simple test case for this patch, but no luck yet. Otherwise, the patch looks good to me. Thanks!

Hi Ning,

Hi Philip - thanks for the review. I made the changes you suggested.

Thanks for the comments - much appreciated. I'll update the test case and then push.

I've created a test case using the AMDGPU target that shows the error. This required a couple of steps. I took an existing AMDGPU lit test, and added debug metadata manually. Then, created MIR for the test by stopping after the TwoAddressInstruction pass. Then, I needed to insert a DBG_VALUE instruction in the correct location. I'm not really sure if it's possible for a DBG_VALUE instruction to appear in the specific place that I put it. But, with these changes, the test case causes an assert because there is a call to getInstructionIndex with a DBG_VALUE insruction.

In D29048#653998, @MatzeB wrote:

At a first glance this looks like it fixes symptoms but not the root cause. It would probably be good if we could get a public reproducer.

In D16829#638891, @lihan2011 wrote:

when i use SMS.enterRegion(MBB, MBB->begin(), MBB->getFirstTerminator(), size); it occurs
Assertion failed: VNI && "No value to read by operand"
but if use SMS.enterRegion(MBB, MBB->getFirstNonPHI(), MBB->getFirstTerminator(), size2); it has no error.
Am i use the wrong version of LLVM?

The change to the Hexagon test looks good to me. As you mention correctly, the intent is to check that the compiler generates one of special add variants on Hexagon, so the reduced test case is a good change.

The changes look good to me. The only nitpick is that you should run clang-format on your changes.

I think it's a good idea to try to move some of the code in the Hexagon hardware loop pass so that it can be reused. The getExitingBlock() function in HexagonHardwareLoops.cpp is probably poorly named since it's doing something different than the existing function that is in MachineLoop. If the function is moved, it seems to fit better in the MachineLoop class vs the MachineLoopInfo class.

Rebased the patch. There were some API changes to resolve.

I'm seeing the same problem, which is fixed with this patch. I'm seeing a hang when running llvm-lit with test/Bugpoint/crash-narrowfunctiontest.ll. The hang appears to be caused because data in the stack frame is corrupted, and the clear() method in a vector never returns, when executing CallBacksToRun->clear() in RunSignalHandlers().

In D16829#460066, @marksl wrote:

After ISEL our compare instructions, multiply, and MAC instructions have real physical register side effects. I'm getting errors from SWP for loops containing these physical register dependencies. Are you aware of this? Is there a way to model physical register dependencies with loop carried dependencies such that we would generate correct code for them?

Hi Matthias - thank you for the review and the comments. I really appreciate it. I think I've addressed all of your comments, unless I've inadvertently missed something. The new patch includes a lot of changes based upon your comments. The code has also been rebased.

Hi James - I think your patch is reasonable. You're correct about our hardware loop pass. We would need to improve it to catch this case. I'm not sure how easy/hard it is to do that without a little more investigation. Until we do that, I'm fine with either xfailing or removing the test (or some other suggestion?).

Hi Hal - thanks for the review and your comments. I've looked into this issue some more, and I think that the problem (or part of the problem) is that Hexagon code adds a kill flag to the register use of the tied operand. For example,

I tried this patch on our Hexagon compiler to see what impact the pass had on some of our performance benchmarks (mostly embedded programs). The biggest improvement was 1.5% and the biggest degradation was -1.8% (in spec2K/twolf). Most differences were under 1%. Many benchmarks were unchanged. I didn't look at code size though.