llvm/unittests/Transforms/Utils/LoopRotationUtilsTest.cpp

   1 //===- LoopRotationUtilsTest.cpp - Unit tests for LoopRotation utility ----===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/Transforms/Utils/LoopRotationUtils.h"
  10 #include "llvm/Analysis/AssumptionCache.h"
  11 #include "llvm/Analysis/InstructionSimplify.h"
  12 #include "llvm/Analysis/LoopInfo.h"
  13 #include "llvm/Analysis/ScalarEvolution.h"
  14 #include "llvm/Analysis/TargetLibraryInfo.h"
  15 #include "llvm/Analysis/TargetTransformInfo.h"
  16 #include "llvm/AsmParser/Parser.h"
  17 #include "llvm/IR/Dominators.h"
  18 #include "llvm/IR/LLVMContext.h"
  19 #include "llvm/Support/SourceMgr.h"
  20 #include "gtest/gtest.h"
  21
  22 using namespace llvm;
  23
  24 static std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) {
  25   SMDiagnostic Err;
  26   std::unique_ptr<Module> Mod = parseAssemblyString(IR, Err, C);
  27   if (!Mod)
  28     Err.print("LoopRotationUtilsTest", errs());
  29   return Mod;
  30 }
  31
  32 /// This test contains multi-deopt-exits pattern that might allow loop rotation
  33 /// to trigger multiple times if multiple rotations are enabled.
  34 /// At least one rotation should be performed, no matter what loop rotation settings are.
  35 TEST(LoopRotate, MultiDeoptExit) {
  36   LLVMContext C;
  37
  38   std::unique_ptr<Module> M = parseIR(
  39     C,
  40     R"(
  41 declare i32 @llvm.experimental.deoptimize.i32(...)
  42
  43 define i32 @test(i32 * nonnull %a, i64 %x) {
  44 entry:
  45   br label %for.cond1
  46
  47 for.cond1:
  48   %idx = phi i64 [ 0, %entry ], [ %idx.next, %for.tail ]
  49   %sum = phi i32 [ 0, %entry ], [ %sum.next, %for.tail ]
  50   %a.idx = getelementptr inbounds i32, i32 *%a, i64 %idx
  51   %val.a.idx = load i32, i32* %a.idx, align 4
  52   %zero.check = icmp eq i32 %val.a.idx, 0
  53   br i1 %zero.check, label %deopt.exit, label %for.cond2
  54
  55 for.cond2:
  56   %for.check = icmp ult i64 %idx, %x
  57   br i1 %for.check, label %for.body, label %return
  58
  59 for.body:
  60   br label %for.tail
  61
  62 for.tail:
  63   %sum.next = add i32 %sum, %val.a.idx
  64   %idx.next = add nuw nsw i64 %idx, 1
  65   br label %for.cond1
  66
  67 return:
  68   ret i32 %sum
  69
  70 deopt.exit:
  71   %deopt.val = call i32(...) @llvm.experimental.deoptimize.i32() [ "deopt"(i32 %val.a.idx) ]
  72   ret i32 %deopt.val
  73 })"
  74     );
  75
  76   auto *F = M->getFunction("test");
  77   DominatorTree DT(*F);
  78   LoopInfo LI(DT);
  79   AssumptionCache AC(*F);
  80   TargetTransformInfo TTI(M->getDataLayout());
  81   TargetLibraryInfoImpl TLII;
  82   TargetLibraryInfo TLI(TLII);
  83   ScalarEvolution SE(*F, TLI, AC, DT, LI);
  84   SimplifyQuery SQ(M->getDataLayout());
  85
  86   Loop *L = *LI.begin();
  87
  88   bool ret = LoopRotation(L, &LI, &TTI,
  89                           &AC, &DT,
  90                           &SE, nullptr,
  91                           SQ, true, -1, false);
  92   EXPECT_TRUE(ret);
  93 }
  94
  95 /// Checking a special case of multi-deopt exit loop that can not perform
  96 /// required amount of rotations due to the desired header containing
  97 /// non-duplicatable code.
  98 /// Similar to MultiDeoptExit test this one should do at least one rotation and
  99 /// pass no matter what loop rotation settings are.
 100 TEST(LoopRotate, MultiDeoptExit_Nondup) {
 101   LLVMContext C;
 102
 103   std::unique_ptr<Module> M = parseIR(
 104     C,
 105     R"(
 106 ; Rotation should be done once, attempted twice.
 107 ; Second time fails due to non-duplicatable header.
 108
 109 declare i32 @llvm.experimental.deoptimize.i32(...)
 110
 111 declare void @nondup()
 112
 113 define i32 @test_nondup(i32 * nonnull %a, i64 %x) {
 114 entry:
 115   br label %for.cond1
 116
 117 for.cond1:
 118   %idx = phi i64 [ 0, %entry ], [ %idx.next, %for.tail ]
 119   %sum = phi i32 [ 0, %entry ], [ %sum.next, %for.tail ]
 120   %a.idx = getelementptr inbounds i32, i32 *%a, i64 %idx
 121   %val.a.idx = load i32, i32* %a.idx, align 4
 122   %zero.check = icmp eq i32 %val.a.idx, 0
 123   br i1 %zero.check, label %deopt.exit, label %for.cond2
 124
 125 for.cond2:
 126   call void @nondup() noduplicate
 127   %for.check = icmp ult i64 %idx, %x
 128   br i1 %for.check, label %for.body, label %return
 129
 130 for.body:
 131   br label %for.tail
 132
 133 for.tail:
 134   %sum.next = add i32 %sum, %val.a.idx
 135   %idx.next = add nuw nsw i64 %idx, 1
 136   br label %for.cond1
 137
 138 return:
 139   ret i32 %sum
 140
 141 deopt.exit:
 142   %deopt.val = call i32(...) @llvm.experimental.deoptimize.i32() [ "deopt"(i32 %val.a.idx) ]
 143   ret i32 %deopt.val
 144 })"
 145     );
 146
 147   auto *F = M->getFunction("test_nondup");
 148   DominatorTree DT(*F);
 149   LoopInfo LI(DT);
 150   AssumptionCache AC(*F);
 151   TargetTransformInfo TTI(M->getDataLayout());
 152   TargetLibraryInfoImpl TLII;
 153   TargetLibraryInfo TLI(TLII);
 154   ScalarEvolution SE(*F, TLI, AC, DT, LI);
 155   SimplifyQuery SQ(M->getDataLayout());
 156
 157   Loop *L = *LI.begin();
 158
 159   bool ret = LoopRotation(L, &LI, &TTI,
 160                           &AC, &DT,
 161                           &SE, nullptr,
 162                           SQ, true, -1, false);
 163   /// LoopRotation should properly report "true" as we still perform the first rotation
 164   /// so we do change the IR.
 165   EXPECT_TRUE(ret);
 166 }