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