Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Transforms/Scalar/SimpleLoopUnswitch.h
Line
Count
Source
1
//===- SimpleLoopUnswitch.h - Hoist loop-invariant control flow -*- C++ -*-===//
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
#ifndef LLVM_TRANSFORMS_SCALAR_SIMPLELOOPUNSWITCH_H
10
#define LLVM_TRANSFORMS_SCALAR_SIMPLELOOPUNSWITCH_H
11
12
#include "llvm/Analysis/LoopAnalysisManager.h"
13
#include "llvm/Analysis/LoopInfo.h"
14
#include "llvm/IR/PassManager.h"
15
#include "llvm/Transforms/Scalar/LoopPassManager.h"
16
17
namespace llvm {
18
19
/// This pass transforms loops that contain branches or switches on loop-
20
/// invariant conditions to have multiple loops. For example, it turns the left
21
/// into the right code:
22
///
23
///  for (...)                  if (lic)
24
///    A                          for (...)
25
///    if (lic)                     A; B; C
26
///      B                      else
27
///    C                          for (...)
28
///                                 A; C
29
///
30
/// This can increase the size of the code exponentially (doubling it every time
31
/// a loop is unswitched) so we only unswitch if the resultant code will be
32
/// smaller than a threshold.
33
///
34
/// This pass expects LICM to be run before it to hoist invariant conditions out
35
/// of the loop, to make the unswitching opportunity obvious.
36
///
37
/// There is a taxonomy of unswitching that we use to classify different forms
38
/// of this transformaiton:
39
///
40
/// - Trival unswitching: this is when the condition can be unswitched without
41
///   cloning any code from inside the loop. A non-trivial unswitch requires
42
///   code duplication.
43
///
44
/// - Full unswitching: this is when the branch or switch is completely moved
45
///   from inside the loop to outside the loop. Partial unswitching removes the
46
///   branch from the clone of the loop but must leave a (somewhat simplified)
47
///   branch in the original loop. While theoretically partial unswitching can
48
///   be done for switches, the requirements are extreme - we need the loop
49
///   invariant input to the switch to be sufficient to collapse to a single
50
///   successor in each clone.
51
///
52
/// This pass always does trivial, full unswitching for both branches and
53
/// switches. For branches, it also always does trivial, partial unswitching.
54
///
55
/// If enabled (via the constructor's `NonTrivial` parameter), this pass will
56
/// additionally do non-trivial, full unswitching for branches and switches, and
57
/// will do non-trivial, partial unswitching for branches.
58
///
59
/// Because partial unswitching of switches is extremely unlikely to be possible
60
/// in practice and significantly complicates the implementation, this pass does
61
/// not currently implement that in any mode.
62
class SimpleLoopUnswitchPass : public PassInfoMixin<SimpleLoopUnswitchPass> {
63
  bool NonTrivial;
64
65
public:
66
204
  SimpleLoopUnswitchPass(bool NonTrivial = false) : NonTrivial(NonTrivial) {}
67
68
  PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,
69
                        LoopStandardAnalysisResults &AR, LPMUpdater &U);
70
};
71
72
/// Create the legacy pass object for the simple loop unswitcher.
73
///
74
/// See the documentaion for `SimpleLoopUnswitchPass` for details.
75
Pass *createSimpleLoopUnswitchLegacyPass(bool NonTrivial = false);
76
77
} // end namespace llvm
78
79
#endif // LLVM_TRANSFORMS_SCALAR_SIMPLELOOPUNSWITCH_H