[TargetPassConfig] Add CanonicalizeFreezeInLoops before LSR

[aqjune]

Summary

This patch adds CanonicalizeFreezeInLoops before LSR.
Relevant patch: https://reviews.llvm.org/D77523

[lebedev.ri]

This deserves a PhaseOrdering test (going from the most underoptimized but minimized IR, -O3)

[aqjune]

Add a test with llc -O3 showing that freeze does not affect codegen

[aqjune]

Update the test so it diverges without CanonicalizeFreezeInLoops

[nikic]

llvm/test/Transforms/CanonicalizeFreezeInLoops/aarch64.ll

5

Probably needs REQUIRES?

[aqjune]

llvm/test/Transforms/CanonicalizeFreezeInLoops/aarch64.ll

5

I'm not familiar with REQUIRES: directive, would this work?

; REQUIRES: arm-registered-target

[xbolva00]

llvm/test/Transforms/CanonicalizeFreezeInLoops/aarch64.ll

2

Precommit testcase?

[nikic]

llvm/test/Transforms/CanonicalizeFreezeInLoops/aarch64.ll

5

I believe for this triple it should be aarch64-registered-target.

[aqjune]

Add REQUIRES

[aqjune]

llvm/test/Transforms/CanonicalizeFreezeInLoops/aarch64.ll

2

Once D77523 is accepted, I'll precommit this test.

[aqjune]

Precommit test

[aqjune]

As the main patch is landed, probably it is okay to land this too?
If there is a non-trivial regression, I can temporarily revert this and work on it.

[aqjune]

Rebase

[aqjune]

ping

I evaluated the performance impact on linking time by compiling CTMark with -O3 + LTO enabled, and the result was as follows:

(unit: sec.)
			bed7884	+D77524	speedup
7zip			47.34	47.29	0.12%
bullet			9.83	9.62	2.28%
clamscan		25.42	25.44	-0.06%
SPASS			19.91	19.93	-0.12%
consumer-typeset	19.12	19.24	-0.64%
kimwitu++		15.19	15.06	0.88%
lencod			39.91	40.03	-0.30%
mafft			8.77	8.77	0.05%
sqlite3			25.07	25.33	-1.02%
tramp3d-v4		36.23	36.21	0.06%

The geometric mean of speedup is -0.13%, which seems to be within an error, considering that compilation time (without linking time) showed 0.1% average speedup which should be 0% in theory because LTO is enabled.

As the validity of this patch has been discussed at D77523, I think it is okay to add the pass before LSR.

[nikic]

LGTM

[aqjune]

Thanks!

[sanwou01]

@aqjune thanks again for working on this pass. I can confirm that the regression in mcf we originally reported on D76483 is now resolved!

[aqjune]

Glad to hear that! :)

[nickdesaulniers]

https://bugs.llvm.org/show_bug.cgi?id=50440 was filed as a response to this. Since it doesn't look like we'll be able to fix forward quickly and clang 12.0.1 is about to release, I've filed https://bugs.llvm.org/show_bug.cgi?id=50573 to revert this from the main and release/12.x branches.

llvm/lib/CodeGen/TargetPassConfig.cpp

 //===- TargetPassConfig.cpp - Target independent code generation passes ---===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
void TargetPassConfig::addIRPasses() {
 
   // Before running any passes, run the verifier to determine if the input
   // coming from the front-end and/or optimizer is valid.
   if (!DisableVerify)
     addPass(createVerifierPass());
 
   // Run loop strength reduction before anything else.
   if (getOptLevel() != CodeGenOpt::None && !DisableLSR) {
+    addPass(createCanonicalizeFreezeInLoopsPass());
     addPass(createLoopStrengthReducePass());
     if (PrintLSR)
       addPass(createPrintFunctionPass(dbgs(), "\n\n*** Code after LSR ***\n"));
   }
 
   if (getOptLevel() != CodeGenOpt::None) {
     // The MergeICmpsPass tries to create memcmp calls by grouping sequences of
     // loads and compares. ExpandMemCmpPass then tries to expand those calls

llvm/test/CodeGen/AArch64/O3-pipeline.ll

 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Scalar Evolution Analysis
 ; CHECK-NEXT:       Loop Data Prefetch
 ; CHECK-NEXT:       Falkor HW Prefetch Fix
 ; CHECK-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:       Module Verifier
 ; CHECK-NEXT:       Canonicalize natural loops
 ; CHECK-NEXT:       Loop Pass Manager
+; CHECK-NEXT:         Canonicalize Freeze Instructions in Loops
 ; CHECK-NEXT:         Induction Variable Users
 ; CHECK-NEXT:         Loop Strength Reduction
 ; CHECK-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:       Merge contiguous icmps into a memcmp
 ; CHECK-NEXT:       Natural Loop Information
 ; CHECK-NEXT:       Lazy Branch Probability Analysis
 ; CHECK-NEXT:       Lazy Block Frequency Analysis

llvm/test/CodeGen/ARM/O3-pipeline.ll

 ; CHECK-NEXT:      Dominator Tree Construction
 ; CHECK-NEXT:      Natural Loop Information
 ; CHECK-NEXT:      MVE gather/scatter lowering
 ; CHECK-NEXT:      Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:      Module Verifier
 ; CHECK-NEXT:      Canonicalize natural loops
 ; CHECK-NEXT:      Scalar Evolution Analysis
 ; CHECK-NEXT:      Loop Pass Manager
+; CHECK-NEXT:        Canonicalize Freeze Instructions in Loops
 ; CHECK-NEXT:        Induction Variable Users
 ; CHECK-NEXT:        Loop Strength Reduction
 ; CHECK-NEXT:      Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:      Function Alias Analysis Results
 ; CHECK-NEXT:      Merge contiguous icmps into a memcmp
 ; CHECK-NEXT:      Natural Loop Information
 ; CHECK-NEXT:      Lazy Branch Probability Analysis
 ; CHECK-NEXT:      Lazy Block Frequency Analysis

llvm/test/CodeGen/X86/O3-pipeline.ll

 ; CHECK-NEXT:       Expand Atomic instructions
 ; CHECK-NEXT:       Dominator Tree Construction
 ; CHECK-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:       Module Verifier
 ; CHECK-NEXT:       Natural Loop Information
 ; CHECK-NEXT:       Canonicalize natural loops
 ; CHECK-NEXT:       Scalar Evolution Analysis
 ; CHECK-NEXT:       Loop Pass Manager
+; CHECK-NEXT:         Canonicalize Freeze Instructions in Loops
 ; CHECK-NEXT:         Induction Variable Users
 ; CHECK-NEXT:         Loop Strength Reduction
 ; CHECK-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:       Merge contiguous icmps into a memcmp
 ; CHECK-NEXT:       Natural Loop Information
 ; CHECK-NEXT:       Lazy Branch Probability Analysis
 ; CHECK-NEXT:       Lazy Block Frequency Analysis

llvm/test/Transforms/CanonicalizeFreezeInLoops/aarch64.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc -mtriple=arm64-unknown-unknown -O3 < %s | FileCheck %s
+; This test should show that @f and @f_without_freeze generate equivalent
+; assembly
+; REQUIRES: aarch64-registered-target
+
+define void @f(i8* %p, i32 %n, i32 %m) {
+; CHECK-LABEL: f:
+; CHECK:       // %bb.0: // %entry
+; CHECK-NEXT:    add w8, w2, #1 // =1
+; CHECK-NEXT:  .LBB0_1: // %loop
+; CHECK-NEXT:    // =>This Inner Loop Header: Depth=1
+; CHECK-NEXT:    strb wzr, [x0, w8, sxtw]
+; CHECK-NEXT:    subs w1, w1, #1 // =1
+; CHECK-NEXT:    add w8, w8, #1 // =1
+; CHECK-NEXT:    b.ne .LBB0_1
+; CHECK-NEXT:  // %bb.2: // %exit
+; CHECK-NEXT:    ret
+entry:
+  br label %loop
+loop:
+  %i = phi i32 [0, %entry], [%i.next, %loop]
+  %i.next = add i32 %i, 1
+  %i.next.fr = freeze i32 %i.next
+  %j = add i32 %m, %i.next.fr
+  %q = getelementptr i8, i8* %p, i32 %j
+  store i8 0, i8* %q
+  %cond = icmp eq i32 %i.next.fr, %n
+  br i1 %cond, label %exit, label %loop
+exit:
+  ret void
+}
+
+define void @f_without_freeze(i8* %p, i32 %n, i32 %m) {
+; CHECK-LABEL: f_without_freeze:
+; CHECK:       // %bb.0: // %entry
+; CHECK-NEXT:    add w8, w2, #1 // =1
+; CHECK-NEXT:  .LBB1_1: // %loop
+; CHECK-NEXT:    // =>This Inner Loop Header: Depth=1
+; CHECK-NEXT:    strb wzr, [x0, w8, sxtw]
+; CHECK-NEXT:    subs w1, w1, #1 // =1
+; CHECK-NEXT:    add w8, w8, #1 // =1
+; CHECK-NEXT:    b.ne .LBB1_1
+; CHECK-NEXT:  // %bb.2: // %exit
+; CHECK-NEXT:    ret
+entry:
+  br label %loop
+loop:
+  %i = phi i32 [0, %entry], [%i.next, %loop]
+  %i.next = add i32 %i, 1
+  %j = add i32 %m, %i.next
+  %q = getelementptr i8, i8* %p, i32 %j
+  store i8 0, i8* %q
+  %cond = icmp eq i32 %i.next, %n
+  br i1 %cond, label %exit, label %loop
+exit:
+  ret void
+}