1//===- SCCP.cpp - Sparse Conditional Constant Propagation -----------------===//
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// This file implements sparse conditional constant propagation and merging:
10//
11// Specifically, this:
12//   * Assumes values are constant unless proven otherwise
13//   * Assumes BasicBlocks are dead unless proven otherwise
14//   * Proves values to be constant, and replaces them with constants
15//   * Proves conditional branches to be unconditional
16//
17//===----------------------------------------------------------------------===//
18
19#include "llvm/Transforms/Scalar/SCCP.h"
20#include "llvm/ADT/STLExtras.h"
21#include "llvm/ADT/SmallPtrSet.h"
22#include "llvm/ADT/SmallVector.h"
23#include "llvm/ADT/Statistic.h"
24#include "llvm/Analysis/DomTreeUpdater.h"
25#include "llvm/Analysis/GlobalsModRef.h"
26#include "llvm/Analysis/TargetLibraryInfo.h"
27#include "llvm/Analysis/ValueTracking.h"
28#include "llvm/IR/BasicBlock.h"
29#include "llvm/IR/Constant.h"
30#include "llvm/IR/DerivedTypes.h"
31#include "llvm/IR/Function.h"
32#include "llvm/IR/GlobalVariable.h"
33#include "llvm/IR/InstrTypes.h"
34#include "llvm/IR/Instruction.h"
35#include "llvm/IR/Instructions.h"
36#include "llvm/IR/Module.h"
37#include "llvm/IR/PassManager.h"
38#include "llvm/IR/Type.h"
39#include "llvm/IR/User.h"
40#include "llvm/IR/Value.h"
41#include "llvm/Pass.h"
42#include "llvm/Support/Casting.h"
43#include "llvm/Support/Debug.h"
44#include "llvm/Support/ErrorHandling.h"
45#include "llvm/Support/raw_ostream.h"
46#include "llvm/Transforms/Scalar.h"
47#include "llvm/Transforms/Utils/Local.h"
48#include "llvm/Transforms/Utils/SCCPSolver.h"
49#include <utility>
50
51using namespace llvm;
52
53#define DEBUG_TYPE "sccp"
54
55STATISTIC(NumInstRemoved, "Number of instructions removed");
56STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable");
57STATISTIC(NumInstReplaced,
58          "Number of instructions replaced with (simpler) instruction");
59
60// runSCCP() - Run the Sparse Conditional Constant Propagation algorithm,
61// and return true if the function was modified.
62static bool runSCCP(Function &F, const DataLayout &DL,
63                    const TargetLibraryInfo *TLI, DomTreeUpdater &DTU) {
64  LLVM_DEBUG(dbgs() << "SCCP on function '" << F.getName() << "'\n");
65  SCCPSolver Solver(
66      DL, [TLI](Function &F) -> const TargetLibraryInfo & { return *TLI; },
67      F.getContext());
68
69  // Mark the first block of the function as being executable.
70  Solver.markBlockExecutable(&F.front());
71
72  // Mark all arguments to the function as being overdefined.
73  for (Argument &AI : F.args())
74    Solver.markOverdefined(&AI);
75
76  // Solve for constants.
77  bool ResolvedUndefs = true;
78  while (ResolvedUndefs) {
79    Solver.solve();
80    LLVM_DEBUG(dbgs() << "RESOLVING UNDEFs\n");
81    ResolvedUndefs = Solver.resolvedUndefsIn(F);
82  }
83
84  bool MadeChanges = false;
85
86  // If we decided that there are basic blocks that are dead in this function,
87  // delete their contents now.  Note that we cannot actually delete the blocks,
88  // as we cannot modify the CFG of the function.
89
90  SmallPtrSet<Value *, 32> InsertedValues;
91  SmallVector<BasicBlock *, 8> BlocksToErase;
92  for (BasicBlock &BB : F) {
93    if (!Solver.isBlockExecutable(&BB)) {
94      LLVM_DEBUG(dbgs() << "  BasicBlock Dead:" << BB);
95      ++NumDeadBlocks;
96      BlocksToErase.push_back(&BB);
97      MadeChanges = true;
98      continue;
99    }
100
101    MadeChanges |= Solver.simplifyInstsInBlock(BB, InsertedValues,
102                                               NumInstRemoved, NumInstReplaced);
103  }
104
105  // Remove unreachable blocks and non-feasible edges.
106  for (BasicBlock *DeadBB : BlocksToErase)
107    NumInstRemoved += changeToUnreachable(DeadBB->getFirstNonPHI(),
108                                          /*PreserveLCSSA=*/false, &DTU);
109
110  BasicBlock *NewUnreachableBB = nullptr;
111  for (BasicBlock &BB : F)
112    MadeChanges |= Solver.removeNonFeasibleEdges(&BB, DTU, NewUnreachableBB);
113
114  for (BasicBlock *DeadBB : BlocksToErase)
115    if (!DeadBB->hasAddressTaken())
116      DTU.deleteBB(DeadBB);
117
118  return MadeChanges;
119}
120
121PreservedAnalyses SCCPPass::run(Function &F, FunctionAnalysisManager &AM) {
122  const DataLayout &DL = F.getParent()->getDataLayout();
123  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
124  auto *DT = AM.getCachedResult<DominatorTreeAnalysis>(F);
125  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
126  if (!runSCCP(F, DL, &TLI, DTU))
127    return PreservedAnalyses::all();
128
129  auto PA = PreservedAnalyses();
130  PA.preserve<DominatorTreeAnalysis>();
131  return PA;
132}
133