Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Transforms/Utils/SSAUpdaterImpl.h
Line
Count
Source
1
//===- SSAUpdaterImpl.h - SSA Updater Implementation ------------*- 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
// This file provides a template that implements the core algorithm for the
10
// SSAUpdater and MachineSSAUpdater.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H
15
#define LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H
16
17
#include "llvm/ADT/DenseMap.h"
18
#include "llvm/ADT/SmallVector.h"
19
#include "llvm/Support/Allocator.h"
20
#include "llvm/Support/Debug.h"
21
#include "llvm/Support/raw_ostream.h"
22
23
#define DEBUG_TYPE "ssaupdater"
24
25
namespace llvm {
26
27
template<typename T> class SSAUpdaterTraits;
28
29
template<typename UpdaterT>
30
class SSAUpdaterImpl {
31
private:
32
  UpdaterT *Updater;
33
34
  using Traits = SSAUpdaterTraits<UpdaterT>;
35
  using BlkT = typename Traits::BlkT;
36
  using ValT = typename Traits::ValT;
37
  using PhiT = typename Traits::PhiT;
38
39
  /// BBInfo - Per-basic block information used internally by SSAUpdaterImpl.
40
  /// The predecessors of each block are cached here since pred_iterator is
41
  /// slow and we need to iterate over the blocks at least a few times.
42
  class BBInfo {
43
  public:
44
    // Back-pointer to the corresponding block.
45
    BlkT *BB;
46
47
    // Value to use in this block.
48
    ValT AvailableVal;
49
50
    // Block that defines the available value.
51
    BBInfo *DefBB;
52
53
    // Postorder number.
54
    int BlkNum = 0;
55
56
    // Immediate dominator.
57
    BBInfo *IDom = nullptr;
58
59
    // Number of predecessor blocks.
60
    unsigned NumPreds = 0;
61
62
    // Array[NumPreds] of predecessor blocks.
63
    BBInfo **Preds = nullptr;
64
65
    // Marker for existing PHIs that match.
66
    PhiT *PHITag = nullptr;
67
68
    BBInfo(BlkT *ThisBB, ValT V)
69
1.85M
      : BB(ThisBB), AvailableVal(V), DefBB(V ? this : nullptr) {}
llvm::SSAUpdaterImpl<llvm::MachineSSAUpdater>::BBInfo::BBInfo(llvm::MachineBasicBlock*, unsigned int)
Line
Count
Source
69
1.72k
      : BB(ThisBB), AvailableVal(V), DefBB(V ? this : nullptr) {}
llvm::SSAUpdaterImpl<llvm::SSAUpdater>::BBInfo::BBInfo(llvm::BasicBlock*, llvm::Value*)
Line
Count
Source
69
1.84M
      : BB(ThisBB), AvailableVal(V), DefBB(V ? this : nullptr) {}
70
  };
71
72
  using AvailableValsTy = DenseMap<BlkT *, ValT>;
73
74
  AvailableValsTy *AvailableVals;
75
76
  SmallVectorImpl<PhiT *> *InsertedPHIs;
77
78
  using BlockListTy = SmallVectorImpl<BBInfo *>;
79
  using BBMapTy = DenseMap<BlkT *, BBInfo *>;
80
81
  BBMapTy BBMap;
82
  BumpPtrAllocator Allocator;
83
84
public:
85
  explicit SSAUpdaterImpl(UpdaterT *U, AvailableValsTy *A,
86
                          SmallVectorImpl<PhiT *> *Ins) :
87
255k
    Updater(U), AvailableVals(A), InsertedPHIs(Ins) {}
llvm::SSAUpdaterImpl<llvm::MachineSSAUpdater>::SSAUpdaterImpl(llvm::MachineSSAUpdater*, llvm::DenseMap<llvm::MachineBasicBlock*, unsigned int, llvm::DenseMapInfo<llvm::MachineBasicBlock*>, llvm::detail::DenseMapPair<llvm::MachineBasicBlock*, unsigned int> >*, llvm::SmallVectorImpl<llvm::MachineInstr*>*)
Line
Count
Source
87
383
    Updater(U), AvailableVals(A), InsertedPHIs(Ins) {}
llvm::SSAUpdaterImpl<llvm::SSAUpdater>::SSAUpdaterImpl(llvm::SSAUpdater*, llvm::DenseMap<llvm::BasicBlock*, llvm::Value*, llvm::DenseMapInfo<llvm::BasicBlock*>, llvm::detail::DenseMapPair<llvm::BasicBlock*, llvm::Value*> >*, llvm::SmallVectorImpl<llvm::PHINode*>*)
Line
Count
Source
87
255k
    Updater(U), AvailableVals(A), InsertedPHIs(Ins) {}
88
89
  /// GetValue - Check to see if AvailableVals has an entry for the specified
90
  /// BB and if so, return it.  If not, construct SSA form by first
91
  /// calculating the required placement of PHIs and then inserting new PHIs
92
  /// where needed.
93
255k
  ValT GetValue(BlkT *BB) {
94
255k
    SmallVector<BBInfo *, 100> BlockList;
95
255k
    BBInfo *PseudoEntry = BuildBlockList(BB, &BlockList);
96
255k
97
255k
    // Special case: bail out if BB is unreachable.
98
255k
    if (BlockList.size() == 0) {
99
5
      ValT V = Traits::GetUndefVal(BB, Updater);
100
5
      (*AvailableVals)[BB] = V;
101
5
      return V;
102
5
    }
103
255k
104
255k
    FindDominators(&BlockList, PseudoEntry);
105
255k
    FindPHIPlacement(&BlockList);
106
255k
    FindAvailableVals(&BlockList);
107
255k
108
255k
    return BBMap[BB]->DefBB->AvailableVal;
109
255k
  }
llvm::SSAUpdaterImpl<llvm::MachineSSAUpdater>::GetValue(llvm::MachineBasicBlock*)
Line
Count
Source
93
383
  ValT GetValue(BlkT *BB) {
94
383
    SmallVector<BBInfo *, 100> BlockList;
95
383
    BBInfo *PseudoEntry = BuildBlockList(BB, &BlockList);
96
383
97
383
    // Special case: bail out if BB is unreachable.
98
383
    if (BlockList.size() == 0) {
99
0
      ValT V = Traits::GetUndefVal(BB, Updater);
100
0
      (*AvailableVals)[BB] = V;
101
0
      return V;
102
0
    }
103
383
104
383
    FindDominators(&BlockList, PseudoEntry);
105
383
    FindPHIPlacement(&BlockList);
106
383
    FindAvailableVals(&BlockList);
107
383
108
383
    return BBMap[BB]->DefBB->AvailableVal;
109
383
  }
llvm::SSAUpdaterImpl<llvm::SSAUpdater>::GetValue(llvm::BasicBlock*)
Line
Count
Source
93
255k
  ValT GetValue(BlkT *BB) {
94
255k
    SmallVector<BBInfo *, 100> BlockList;
95
255k
    BBInfo *PseudoEntry = BuildBlockList(BB, &BlockList);
96
255k
97
255k
    // Special case: bail out if BB is unreachable.
98
255k
    if (BlockList.size() == 0) {
99
5
      ValT V = Traits::GetUndefVal(BB, Updater);
100
5
      (*AvailableVals)[BB] = V;
101
5
      return V;
102
5
    }
103
255k
104
255k
    FindDominators(&BlockList, PseudoEntry);
105
255k
    FindPHIPlacement(&BlockList);
106
255k
    FindAvailableVals(&BlockList);
107
255k
108
255k
    return BBMap[BB]->DefBB->AvailableVal;
109
255k
  }
110
111
  /// BuildBlockList - Starting from the specified basic block, traverse back
112
  /// through its predecessors until reaching blocks with known values.
113
  /// Create BBInfo structures for the blocks and append them to the block
114
  /// list.
115
255k
  BBInfo *BuildBlockList(BlkT *BB, BlockListTy *BlockList) {
116
255k
    SmallVector<BBInfo *, 10> RootList;
117
255k
    SmallVector<BBInfo *, 64> WorkList;
118
255k
119
255k
    BBInfo *Info = new (Allocator) BBInfo(BB, 0);
120
255k
    BBMap[BB] = Info;
121
255k
    WorkList.push_back(Info);
122
255k
123
255k
    // Search backward from BB, creating BBInfos along the way and stopping
124
255k
    // when reaching blocks that define the value.  Record those defining
125
255k
    // blocks on the RootList.
126
255k
    SmallVector<BlkT *, 10> Preds;
127
1.42M
    while (!WorkList.empty()) {
128
1.16M
      Info = WorkList.pop_back_val();
129
1.16M
      Preds.clear();
130
1.16M
      Traits::FindPredecessorBlocks(Info->BB, &Preds);
131
1.16M
      Info->NumPreds = Preds.size();
132
1.16M
      if (Info->NumPreds == 0)
133
826
        Info->Preds = nullptr;
134
1.16M
      else
135
1.16M
        Info->Preds = static_cast<BBInfo **>(Allocator.Allocate(
136
1.16M
            Info->NumPreds * sizeof(BBInfo *), alignof(BBInfo *)));
137
1.16M
138
2.92M
      for (unsigned p = 0; p != Info->NumPreds; 
++p1.76M
) {
139
1.76M
        BlkT *Pred = Preds[p];
140
1.76M
        // Check if BBMap already has a BBInfo for the predecessor block.
141
1.76M
        typename BBMapTy::value_type &BBMapBucket =
142
1.76M
          BBMap.FindAndConstruct(Pred);
143
1.76M
        if (BBMapBucket.second) {
144
421k
          Info->Preds[p] = BBMapBucket.second;
145
421k
          continue;
146
421k
        }
147
1.33M
148
1.33M
        // Create a new BBInfo for the predecessor.
149
1.33M
        ValT PredVal = AvailableVals->lookup(Pred);
150
1.33M
        BBInfo *PredInfo = new (Allocator) BBInfo(Pred, PredVal);
151
1.33M
        BBMapBucket.second = PredInfo;
152
1.33M
        Info->Preds[p] = PredInfo;
153
1.33M
154
1.33M
        if (PredInfo->AvailableVal) {
155
430k
          RootList.push_back(PredInfo);
156
430k
          continue;
157
430k
        }
158
909k
        WorkList.push_back(PredInfo);
159
909k
      }
160
1.16M
    }
161
255k
162
255k
    // Now that we know what blocks are backwards-reachable from the starting
163
255k
    // block, do a forward depth-first traversal to assign postorder numbers
164
255k
    // to those blocks.
165
255k
    BBInfo *PseudoEntry = new (Allocator) BBInfo(nullptr, 0);
166
255k
    unsigned BlkNum = 1;
167
255k
168
255k
    // Initialize the worklist with the roots from the backward traversal.
169
685k
    while (!RootList.empty()) {
170
430k
      Info = RootList.pop_back_val();
171
430k
      Info->IDom = PseudoEntry;
172
430k
      Info->BlkNum = -1;
173
430k
      WorkList.push_back(Info);
174
430k
    }
175
255k
176
3.44M
    while (!WorkList.empty()) {
177
3.18M
      Info = WorkList.back();
178
3.18M
179
3.18M
      if (Info->BlkNum == -2) {
180
1.59M
        // All the successors have been handled; assign the postorder number.
181
1.59M
        Info->BlkNum = BlkNum++;
182
1.59M
        // If not a root, put it on the BlockList.
183
1.59M
        if (!Info->AvailableVal)
184
1.16M
          BlockList->push_back(Info);
185
1.59M
        WorkList.pop_back();
186
1.59M
        continue;
187
1.59M
      }
188
1.59M
189
1.59M
      // Leave this entry on the worklist, but set its BlkNum to mark that its
190
1.59M
      // successors have been put on the worklist.  When it returns to the top
191
1.59M
      // the list, after handling its successors, it will be assigned a
192
1.59M
      // number.
193
1.59M
      Info->BlkNum = -2;
194
1.59M
195
1.59M
      // Add unvisited successors to the work list.
196
1.59M
      for (typename Traits::BlkSucc_iterator SI =
197
1.59M
             Traits::BlkSucc_begin(Info->BB),
198
4.63M
             E = Traits::BlkSucc_end(Info->BB); SI != E; 
++SI3.03M
) {
199
3.03M
        BBInfo *SuccInfo = BBMap[*SI];
200
3.03M
        if (!SuccInfo || 
SuccInfo->BlkNum1.83M
)
201
1.87M
          continue;
202
1.16M
        SuccInfo->BlkNum = -1;
203
1.16M
        WorkList.push_back(SuccInfo);
204
1.16M
      }
205
1.59M
    }
206
255k
    PseudoEntry->BlkNum = BlkNum;
207
255k
    return PseudoEntry;
208
255k
  }
llvm::SSAUpdaterImpl<llvm::MachineSSAUpdater>::BuildBlockList(llvm::MachineBasicBlock*, llvm::SmallVectorImpl<llvm::SSAUpdaterImpl<llvm::MachineSSAUpdater>::BBInfo*>*)
Line
Count
Source
115
383
  BBInfo *BuildBlockList(BlkT *BB, BlockListTy *BlockList) {
116
383
    SmallVector<BBInfo *, 10> RootList;
117
383
    SmallVector<BBInfo *, 64> WorkList;
118
383
119
383
    BBInfo *Info = new (Allocator) BBInfo(BB, 0);
120
383
    BBMap[BB] = Info;
121
383
    WorkList.push_back(Info);
122
383
123
383
    // Search backward from BB, creating BBInfos along the way and stopping
124
383
    // when reaching blocks that define the value.  Record those defining
125
383
    // blocks on the RootList.
126
383
    SmallVector<BlkT *, 10> Preds;
127
1.01k
    while (!WorkList.empty()) {
128
633
      Info = WorkList.pop_back_val();
129
633
      Preds.clear();
130
633
      Traits::FindPredecessorBlocks(Info->BB, &Preds);
131
633
      Info->NumPreds = Preds.size();
132
633
      if (Info->NumPreds == 0)
133
0
        Info->Preds = nullptr;
134
633
      else
135
633
        Info->Preds = static_cast<BBInfo **>(Allocator.Allocate(
136
633
            Info->NumPreds * sizeof(BBInfo *), alignof(BBInfo *)));
137
633
138
1.71k
      for (unsigned p = 0; p != Info->NumPreds; 
++p1.08k
) {
139
1.08k
        BlkT *Pred = Preds[p];
140
1.08k
        // Check if BBMap already has a BBInfo for the predecessor block.
141
1.08k
        typename BBMapTy::value_type &BBMapBucket =
142
1.08k
          BBMap.FindAndConstruct(Pred);
143
1.08k
        if (BBMapBucket.second) {
144
125
          Info->Preds[p] = BBMapBucket.second;
145
125
          continue;
146
125
        }
147
958
148
958
        // Create a new BBInfo for the predecessor.
149
958
        ValT PredVal = AvailableVals->lookup(Pred);
150
958
        BBInfo *PredInfo = new (Allocator) BBInfo(Pred, PredVal);
151
958
        BBMapBucket.second = PredInfo;
152
958
        Info->Preds[p] = PredInfo;
153
958
154
958
        if (PredInfo->AvailableVal) {
155
708
          RootList.push_back(PredInfo);
156
708
          continue;
157
708
        }
158
250
        WorkList.push_back(PredInfo);
159
250
      }
160
633
    }
161
383
162
383
    // Now that we know what blocks are backwards-reachable from the starting
163
383
    // block, do a forward depth-first traversal to assign postorder numbers
164
383
    // to those blocks.
165
383
    BBInfo *PseudoEntry = new (Allocator) BBInfo(nullptr, 0);
166
383
    unsigned BlkNum = 1;
167
383
168
383
    // Initialize the worklist with the roots from the backward traversal.
169
1.09k
    while (!RootList.empty()) {
170
708
      Info = RootList.pop_back_val();
171
708
      Info->IDom = PseudoEntry;
172
708
      Info->BlkNum = -1;
173
708
      WorkList.push_back(Info);
174
708
    }
175
383
176
3.06k
    while (!WorkList.empty()) {
177
2.68k
      Info = WorkList.back();
178
2.68k
179
2.68k
      if (Info->BlkNum == -2) {
180
1.34k
        // All the successors have been handled; assign the postorder number.
181
1.34k
        Info->BlkNum = BlkNum++;
182
1.34k
        // If not a root, put it on the BlockList.
183
1.34k
        if (!Info->AvailableVal)
184
633
          BlockList->push_back(Info);
185
1.34k
        WorkList.pop_back();
186
1.34k
        continue;
187
1.34k
      }
188
1.34k
189
1.34k
      // Leave this entry on the worklist, but set its BlkNum to mark that its
190
1.34k
      // successors have been put on the worklist.  When it returns to the top
191
1.34k
      // the list, after handling its successors, it will be assigned a
192
1.34k
      // number.
193
1.34k
      Info->BlkNum = -2;
194
1.34k
195
1.34k
      // Add unvisited successors to the work list.
196
1.34k
      for (typename Traits::BlkSucc_iterator SI =
197
1.34k
             Traits::BlkSucc_begin(Info->BB),
198
3.72k
             E = Traits::BlkSucc_end(Info->BB); SI != E; 
++SI2.38k
) {
199
2.38k
        BBInfo *SuccInfo = BBMap[*SI];
200
2.38k
        if (!SuccInfo || 
SuccInfo->BlkNum1.38k
)
201
1.75k
          continue;
202
633
        SuccInfo->BlkNum = -1;
203
633
        WorkList.push_back(SuccInfo);
204
633
      }
205
1.34k
    }
206
383
    PseudoEntry->BlkNum = BlkNum;
207
383
    return PseudoEntry;
208
383
  }
llvm::SSAUpdaterImpl<llvm::SSAUpdater>::BuildBlockList(llvm::BasicBlock*, llvm::SmallVectorImpl<llvm::SSAUpdaterImpl<llvm::SSAUpdater>::BBInfo*>*)
Line
Count
Source
115
255k
  BBInfo *BuildBlockList(BlkT *BB, BlockListTy *BlockList) {
116
255k
    SmallVector<BBInfo *, 10> RootList;
117
255k
    SmallVector<BBInfo *, 64> WorkList;
118
255k
119
255k
    BBInfo *Info = new (Allocator) BBInfo(BB, 0);
120
255k
    BBMap[BB] = Info;
121
255k
    WorkList.push_back(Info);
122
255k
123
255k
    // Search backward from BB, creating BBInfos along the way and stopping
124
255k
    // when reaching blocks that define the value.  Record those defining
125
255k
    // blocks on the RootList.
126
255k
    SmallVector<BlkT *, 10> Preds;
127
1.41M
    while (!WorkList.empty()) {
128
1.16M
      Info = WorkList.pop_back_val();
129
1.16M
      Preds.clear();
130
1.16M
      Traits::FindPredecessorBlocks(Info->BB, &Preds);
131
1.16M
      Info->NumPreds = Preds.size();
132
1.16M
      if (Info->NumPreds == 0)
133
826
        Info->Preds = nullptr;
134
1.16M
      else
135
1.16M
        Info->Preds = static_cast<BBInfo **>(Allocator.Allocate(
136
1.16M
            Info->NumPreds * sizeof(BBInfo *), alignof(BBInfo *)));
137
1.16M
138
2.92M
      for (unsigned p = 0; p != Info->NumPreds; 
++p1.76M
) {
139
1.76M
        BlkT *Pred = Preds[p];
140
1.76M
        // Check if BBMap already has a BBInfo for the predecessor block.
141
1.76M
        typename BBMapTy::value_type &BBMapBucket =
142
1.76M
          BBMap.FindAndConstruct(Pred);
143
1.76M
        if (BBMapBucket.second) {
144
421k
          Info->Preds[p] = BBMapBucket.second;
145
421k
          continue;
146
421k
        }
147
1.33M
148
1.33M
        // Create a new BBInfo for the predecessor.
149
1.33M
        ValT PredVal = AvailableVals->lookup(Pred);
150
1.33M
        BBInfo *PredInfo = new (Allocator) BBInfo(Pred, PredVal);
151
1.33M
        BBMapBucket.second = PredInfo;
152
1.33M
        Info->Preds[p] = PredInfo;
153
1.33M
154
1.33M
        if (PredInfo->AvailableVal) {
155
429k
          RootList.push_back(PredInfo);
156
429k
          continue;
157
429k
        }
158
909k
        WorkList.push_back(PredInfo);
159
909k
      }
160
1.16M
    }
161
255k
162
255k
    // Now that we know what blocks are backwards-reachable from the starting
163
255k
    // block, do a forward depth-first traversal to assign postorder numbers
164
255k
    // to those blocks.
165
255k
    BBInfo *PseudoEntry = new (Allocator) BBInfo(nullptr, 0);
166
255k
    unsigned BlkNum = 1;
167
255k
168
255k
    // Initialize the worklist with the roots from the backward traversal.
169
684k
    while (!RootList.empty()) {
170
429k
      Info = RootList.pop_back_val();
171
429k
      Info->IDom = PseudoEntry;
172
429k
      Info->BlkNum = -1;
173
429k
      WorkList.push_back(Info);
174
429k
    }
175
255k
176
3.44M
    while (!WorkList.empty()) {
177
3.18M
      Info = WorkList.back();
178
3.18M
179
3.18M
      if (Info->BlkNum == -2) {
180
1.59M
        // All the successors have been handled; assign the postorder number.
181
1.59M
        Info->BlkNum = BlkNum++;
182
1.59M
        // If not a root, put it on the BlockList.
183
1.59M
        if (!Info->AvailableVal)
184
1.16M
          BlockList->push_back(Info);
185
1.59M
        WorkList.pop_back();
186
1.59M
        continue;
187
1.59M
      }
188
1.59M
189
1.59M
      // Leave this entry on the worklist, but set its BlkNum to mark that its
190
1.59M
      // successors have been put on the worklist.  When it returns to the top
191
1.59M
      // the list, after handling its successors, it will be assigned a
192
1.59M
      // number.
193
1.59M
      Info->BlkNum = -2;
194
1.59M
195
1.59M
      // Add unvisited successors to the work list.
196
1.59M
      for (typename Traits::BlkSucc_iterator SI =
197
1.59M
             Traits::BlkSucc_begin(Info->BB),
198
4.62M
             E = Traits::BlkSucc_end(Info->BB); SI != E; 
++SI3.03M
) {
199
3.03M
        BBInfo *SuccInfo = BBMap[*SI];
200
3.03M
        if (!SuccInfo || 
SuccInfo->BlkNum1.83M
)
201
1.87M
          continue;
202
1.16M
        SuccInfo->BlkNum = -1;
203
1.16M
        WorkList.push_back(SuccInfo);
204
1.16M
      }
205
1.59M
    }
206
255k
    PseudoEntry->BlkNum = BlkNum;
207
255k
    return PseudoEntry;
208
255k
  }
209
210
  /// IntersectDominators - This is the dataflow lattice "meet" operation for
211
  /// finding dominators.  Given two basic blocks, it walks up the dominator
212
  /// tree until it finds a common dominator of both.  It uses the postorder
213
  /// number of the blocks to determine how to do that.
214
1.24M
  BBInfo *IntersectDominators(BBInfo *Blk1, BBInfo *Blk2) {
215
2.38M
    while (Blk1 != Blk2) {
216
2.42M
      while (Blk1->BlkNum < Blk2->BlkNum) {
217
1.15M
        Blk1 = Blk1->IDom;
218
1.15M
        if (!Blk1)
219
98.8k
          return Blk2;
220
1.15M
      }
221
2.70M
      
while (1.26M
Blk2->BlkNum < Blk1->BlkNum) {
222
1.56M
        Blk2 = Blk2->IDom;
223
1.56M
        if (!Blk2)
224
122k
          return Blk1;
225
1.56M
      }
226
1.26M
    }
227
1.24M
    
return Blk11.02M
;
228
1.24M
  }
llvm::SSAUpdaterImpl<llvm::MachineSSAUpdater>::IntersectDominators(llvm::SSAUpdaterImpl<llvm::MachineSSAUpdater>::BBInfo*, llvm::SSAUpdaterImpl<llvm::MachineSSAUpdater>::BBInfo*)
Line
Count
Source
214
900
  BBInfo *IntersectDominators(BBInfo *Blk1, BBInfo *Blk2) {
215
1.76k
    while (Blk1 != Blk2) {
216
1.59k
      while (Blk1->BlkNum < Blk2->BlkNum) {
217
710
        Blk1 = Blk1->IDom;
218
710
        if (!Blk1)
219
17
          return Blk2;
220
710
      }
221
2.05k
      
while (885
Blk2->BlkNum < Blk1->BlkNum) {
222
1.18k
        Blk2 = Blk2->IDom;
223
1.18k
        if (!Blk2)
224
19
          return Blk1;
225
1.18k
      }
226
885
    }
227
900
    
return Blk1864
;
228
900
  }
llvm::SSAUpdaterImpl<llvm::SSAUpdater>::IntersectDominators(llvm::SSAUpdaterImpl<llvm::SSAUpdater>::BBInfo*, llvm::SSAUpdaterImpl<llvm::SSAUpdater>::BBInfo*)
Line
Count
Source
214
1.24M
  BBInfo *IntersectDominators(BBInfo *Blk1, BBInfo *Blk2) {
215
2.38M
    while (Blk1 != Blk2) {
216
2.42M
      while (Blk1->BlkNum < Blk2->BlkNum) {
217
1.15M
        Blk1 = Blk1->IDom;
218
1.15M
        if (!Blk1)
219
98.8k
          return Blk2;
220
1.15M
      }
221
2.70M
      
while (1.26M
Blk2->BlkNum < Blk1->BlkNum) {
222
1.56M
        Blk2 = Blk2->IDom;
223
1.56M
        if (!Blk2)
224
122k
          return Blk1;
225
1.56M
      }
226
1.26M
    }
227
1.24M
    
return Blk11.02M
;
228
1.24M
  }
229
230
  /// FindDominators - Calculate the dominator tree for the subset of the CFG
231
  /// corresponding to the basic blocks on the BlockList.  This uses the
232
  /// algorithm from: "A Simple, Fast Dominance Algorithm" by Cooper, Harvey
233
  /// and Kennedy, published in Software--Practice and Experience, 2001,
234
  /// 4:1-10.  Because the CFG subset does not include any edges leading into
235
  /// blocks that define the value, the results are not the usual dominator
236
  /// tree.  The CFG subset has a single pseudo-entry node with edges to a set
237
  /// of root nodes for blocks that define the value.  The dominators for this
238
  /// subset CFG are not the standard dominators but they are adequate for
239
  /// placing PHIs within the subset CFG.
240
255k
  void FindDominators(BlockListTy *BlockList, BBInfo *PseudoEntry) {
241
255k
    bool Changed;
242
517k
    do {
243
517k
      Changed = false;
244
517k
      // Iterate over the list in reverse order, i.e., forward on CFG edges.
245
517k
      for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
246
2.93M
             E = BlockList->rend(); I != E; 
++I2.41M
) {
247
2.41M
        BBInfo *Info = *I;
248
2.41M
        BBInfo *NewIDom = nullptr;
249
2.41M
250
2.41M
        // Iterate through the block's predecessors.
251
6.07M
        for (unsigned p = 0; p != Info->NumPreds; 
++p3.66M
) {
252
3.66M
          BBInfo *Pred = Info->Preds[p];
253
3.66M
254
3.66M
          // Treat an unreachable predecessor as a definition with 'undef'.
255
3.66M
          if (Pred->BlkNum == 0) {
256
820
            Pred->AvailableVal = Traits::GetUndefVal(Pred->BB, Updater);
257
820
            (*AvailableVals)[Pred->BB] = Pred->AvailableVal;
258
820
            Pred->DefBB = Pred;
259
820
            Pred->BlkNum = PseudoEntry->BlkNum;
260
820
            PseudoEntry->BlkNum++;
261
820
          }
262
3.66M
263
3.66M
          if (!NewIDom)
264
2.41M
            NewIDom = Pred;
265
1.24M
          else
266
1.24M
            NewIDom = IntersectDominators(NewIDom, Pred);
267
3.66M
        }
268
2.41M
269
2.41M
        // Check if the IDom value has changed.
270
2.41M
        if (NewIDom && NewIDom != Info->IDom) {
271
1.17M
          Info->IDom = NewIDom;
272
1.17M
          Changed = true;
273
1.17M
        }
274
2.41M
      }
275
517k
    } while (Changed);
276
255k
  }
llvm::SSAUpdaterImpl<llvm::MachineSSAUpdater>::FindDominators(llvm::SmallVectorImpl<llvm::SSAUpdaterImpl<llvm::MachineSSAUpdater>::BBInfo*>*, llvm::SSAUpdaterImpl<llvm::MachineSSAUpdater>::BBInfo*)
Line
Count
Source
240
383
  void FindDominators(BlockListTy *BlockList, BBInfo *PseudoEntry) {
241
383
    bool Changed;
242
766
    do {
243
766
      Changed = false;
244
766
      // Iterate over the list in reverse order, i.e., forward on CFG edges.
245
766
      for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
246
2.03k
             E = BlockList->rend(); I != E; 
++I1.26k
) {
247
1.26k
        BBInfo *Info = *I;
248
1.26k
        BBInfo *NewIDom = nullptr;
249
1.26k
250
1.26k
        // Iterate through the block's predecessors.
251
3.43k
        for (unsigned p = 0; p != Info->NumPreds; 
++p2.16k
) {
252
2.16k
          BBInfo *Pred = Info->Preds[p];
253
2.16k
254
2.16k
          // Treat an unreachable predecessor as a definition with 'undef'.
255
2.16k
          if (Pred->BlkNum == 0) {
256
0
            Pred->AvailableVal = Traits::GetUndefVal(Pred->BB, Updater);
257
0
            (*AvailableVals)[Pred->BB] = Pred->AvailableVal;
258
0
            Pred->DefBB = Pred;
259
0
            Pred->BlkNum = PseudoEntry->BlkNum;
260
0
            PseudoEntry->BlkNum++;
261
0
          }
262
2.16k
263
2.16k
          if (!NewIDom)
264
1.26k
            NewIDom = Pred;
265
900
          else
266
900
            NewIDom = IntersectDominators(NewIDom, Pred);
267
2.16k
        }
268
1.26k
269
1.26k
        // Check if the IDom value has changed.
270
1.26k
        if (NewIDom && NewIDom != Info->IDom) {
271
633
          Info->IDom = NewIDom;
272
633
          Changed = true;
273
633
        }
274
1.26k
      }
275
766
    } while (Changed);
276
383
  }
llvm::SSAUpdaterImpl<llvm::SSAUpdater>::FindDominators(llvm::SmallVectorImpl<llvm::SSAUpdaterImpl<llvm::SSAUpdater>::BBInfo*>*, llvm::SSAUpdaterImpl<llvm::SSAUpdater>::BBInfo*)
Line
Count
Source
240
255k
  void FindDominators(BlockListTy *BlockList, BBInfo *PseudoEntry) {
241
255k
    bool Changed;
242
517k
    do {
243
517k
      Changed = false;
244
517k
      // Iterate over the list in reverse order, i.e., forward on CFG edges.
245
517k
      for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
246
2.93M
             E = BlockList->rend(); I != E; 
++I2.41M
) {
247
2.41M
        BBInfo *Info = *I;
248
2.41M
        BBInfo *NewIDom = nullptr;
249
2.41M
250
2.41M
        // Iterate through the block's predecessors.
251
6.07M
        for (unsigned p = 0; p != Info->NumPreds; 
++p3.65M
) {
252
3.65M
          BBInfo *Pred = Info->Preds[p];
253
3.65M
254
3.65M
          // Treat an unreachable predecessor as a definition with 'undef'.
255
3.65M
          if (Pred->BlkNum == 0) {
256
820
            Pred->AvailableVal = Traits::GetUndefVal(Pred->BB, Updater);
257
820
            (*AvailableVals)[Pred->BB] = Pred->AvailableVal;
258
820
            Pred->DefBB = Pred;
259
820
            Pred->BlkNum = PseudoEntry->BlkNum;
260
820
            PseudoEntry->BlkNum++;
261
820
          }
262
3.65M
263
3.65M
          if (!NewIDom)
264
2.41M
            NewIDom = Pred;
265
1.24M
          else
266
1.24M
            NewIDom = IntersectDominators(NewIDom, Pred);
267
3.65M
        }
268
2.41M
269
2.41M
        // Check if the IDom value has changed.
270
2.41M
        if (NewIDom && NewIDom != Info->IDom) {
271
1.17M
          Info->IDom = NewIDom;
272
1.17M
          Changed = true;
273
1.17M
        }
274
2.41M
      }
275
517k
    } while (Changed);
276
255k
  }
277
278
  /// IsDefInDomFrontier - Search up the dominator tree from Pred to IDom for
279
  /// any blocks containing definitions of the value.  If one is found, then
280
  /// the successor of Pred is in the dominance frontier for the definition,
281
  /// and this function returns true.
282
2.92M
  bool IsDefInDomFrontier(const BBInfo *Pred, const BBInfo *IDom) {
283
4.88M
    for (; Pred != IDom; 
Pred = Pred->IDom1.95M
) {
284
2.12M
      if (Pred->DefBB == Pred)
285
174k
        return true;
286
2.12M
    }
287
2.92M
    
return false2.75M
;
288
2.92M
  }
llvm::SSAUpdaterImpl<llvm::MachineSSAUpdater>::IsDefInDomFrontier(llvm::SSAUpdaterImpl<llvm::MachineSSAUpdater>::BBInfo const*, llvm::SSAUpdaterImpl<llvm::MachineSSAUpdater>::BBInfo const*)
Line
Count
Source
282
1.19k
  bool IsDefInDomFrontier(const BBInfo *Pred, const BBInfo *IDom) {
283
1.83k
    for (; Pred != IDom; 
Pred = Pred->IDom638
) {
284
923
      if (Pred->DefBB == Pred)
285
285
        return true;
286
923
    }
287
1.19k
    
return false912
;
288
1.19k
  }
llvm::SSAUpdaterImpl<llvm::SSAUpdater>::IsDefInDomFrontier(llvm::SSAUpdaterImpl<llvm::SSAUpdater>::BBInfo const*, llvm::SSAUpdaterImpl<llvm::SSAUpdater>::BBInfo const*)
Line
Count
Source
282
2.92M
  bool IsDefInDomFrontier(const BBInfo *Pred, const BBInfo *IDom) {
283
4.87M
    for (; Pred != IDom; 
Pred = Pred->IDom1.95M
) {
284
2.12M
      if (Pred->DefBB == Pred)
285
174k
        return true;
286
2.12M
    }
287
2.92M
    
return false2.74M
;
288
2.92M
  }
289
290
  /// FindPHIPlacement - PHIs are needed in the iterated dominance frontiers
291
  /// of the known definitions.  Iteratively add PHIs in the dom frontiers
292
  /// until nothing changes.  Along the way, keep track of the nearest
293
  /// dominating definitions for non-PHI blocks.
294
255k
  void FindPHIPlacement(BlockListTy *BlockList) {
295
255k
    bool Changed;
296
511k
    do {
297
511k
      Changed = false;
298
511k
      // Iterate over the list in reverse order, i.e., forward on CFG edges.
299
511k
      for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
300
2.83M
             E = BlockList->rend(); I != E; 
++I2.32M
) {
301
2.32M
        BBInfo *Info = *I;
302
2.32M
303
2.32M
        // If this block already needs a PHI, there is nothing to do here.
304
2.32M
        if (Info->DefBB == Info)
305
174k
          continue;
306
2.15M
307
2.15M
        // Default to use the same def as the immediate dominator.
308
2.15M
        BBInfo *NewDefBB = Info->IDom->DefBB;
309
4.90M
        for (unsigned p = 0; p != Info->NumPreds; 
++p2.75M
) {
310
2.92M
          if (IsDefInDomFrontier(Info->Preds[p], Info->IDom)) {
311
174k
            // Need a PHI here.
312
174k
            NewDefBB = Info;
313
174k
            break;
314
174k
          }
315
2.92M
        }
316
2.15M
317
2.15M
        // Check if anything changed.
318
2.15M
        if (NewDefBB != Info->DefBB) {
319
1.16M
          Info->DefBB = NewDefBB;
320
1.16M
          Changed = true;
321
1.16M
        }
322
2.15M
      }
323
511k
    } while (Changed);
324
255k
  }
llvm::SSAUpdaterImpl<llvm::MachineSSAUpdater>::FindPHIPlacement(llvm::SmallVectorImpl<llvm::SSAUpdaterImpl<llvm::MachineSSAUpdater>::BBInfo*>*)
Line
Count
Source
294
383
  void FindPHIPlacement(BlockListTy *BlockList) {
295
383
    bool Changed;
296
766
    do {
297
766
      Changed = false;
298
766
      // Iterate over the list in reverse order, i.e., forward on CFG edges.
299
766
      for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
300
2.03k
             E = BlockList->rend(); I != E; 
++I1.26k
) {
301
1.26k
        BBInfo *Info = *I;
302
1.26k
303
1.26k
        // If this block already needs a PHI, there is nothing to do here.
304
1.26k
        if (Info->DefBB == Info)
305
285
          continue;
306
981
307
981
        // Default to use the same def as the immediate dominator.
308
981
        BBInfo *NewDefBB = Info->IDom->DefBB;
309
1.89k
        for (unsigned p = 0; p != Info->NumPreds; 
++p912
) {
310
1.19k
          if (IsDefInDomFrontier(Info->Preds[p], Info->IDom)) {
311
285
            // Need a PHI here.
312
285
            NewDefBB = Info;
313
285
            break;
314
285
          }
315
1.19k
        }
316
981
317
981
        // Check if anything changed.
318
981
        if (NewDefBB != Info->DefBB) {
319
633
          Info->DefBB = NewDefBB;
320
633
          Changed = true;
321
633
        }
322
981
      }
323
766
    } while (Changed);
324
383
  }
llvm::SSAUpdaterImpl<llvm::SSAUpdater>::FindPHIPlacement(llvm::SmallVectorImpl<llvm::SSAUpdaterImpl<llvm::SSAUpdater>::BBInfo*>*)
Line
Count
Source
294
255k
  void FindPHIPlacement(BlockListTy *BlockList) {
295
255k
    bool Changed;
296
510k
    do {
297
510k
      Changed = false;
298
510k
      // Iterate over the list in reverse order, i.e., forward on CFG edges.
299
510k
      for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
300
2.83M
             E = BlockList->rend(); I != E; 
++I2.32M
) {
301
2.32M
        BBInfo *Info = *I;
302
2.32M
303
2.32M
        // If this block already needs a PHI, there is nothing to do here.
304
2.32M
        if (Info->DefBB == Info)
305
174k
          continue;
306
2.15M
307
2.15M
        // Default to use the same def as the immediate dominator.
308
2.15M
        BBInfo *NewDefBB = Info->IDom->DefBB;
309
4.90M
        for (unsigned p = 0; p != Info->NumPreds; 
++p2.74M
) {
310
2.92M
          if (IsDefInDomFrontier(Info->Preds[p], Info->IDom)) {
311
174k
            // Need a PHI here.
312
174k
            NewDefBB = Info;
313
174k
            break;
314
174k
          }
315
2.92M
        }
316
2.15M
317
2.15M
        // Check if anything changed.
318
2.15M
        if (NewDefBB != Info->DefBB) {
319
1.16M
          Info->DefBB = NewDefBB;
320
1.16M
          Changed = true;
321
1.16M
        }
322
2.15M
      }
323
510k
    } while (Changed);
324
255k
  }
325
326
  /// FindAvailableVal - If this block requires a PHI, first check if an
327
  /// existing PHI matches the PHI placement and reaching definitions computed
328
  /// earlier, and if not, create a new PHI.  Visit all the block's
329
  /// predecessors to calculate the available value for each one and fill in
330
  /// the incoming values for a new PHI.
331
255k
  void FindAvailableVals(BlockListTy *BlockList) {
332
255k
    // Go through the worklist in forward order (i.e., backward through the CFG)
333
255k
    // and check if existing PHIs can be used.  If not, create empty PHIs where
334
255k
    // they are needed.
335
255k
    for (typename BlockListTy::iterator I = BlockList->begin(),
336
1.41M
           E = BlockList->end(); I != E; 
++I1.16M
) {
337
1.16M
      BBInfo *Info = *I;
338
1.16M
      // Check if there needs to be a PHI in BB.
339
1.16M
      if (Info->DefBB != Info)
340
989k
        continue;
341
174k
342
174k
      // Look for an existing PHI.
343
174k
      FindExistingPHI(Info->BB, BlockList);
344
174k
      if (Info->AvailableVal)
345
12.3k
        continue;
346
162k
347
162k
      ValT PHI = Traits::CreateEmptyPHI(Info->BB, Info->NumPreds, Updater);
348
162k
      Info->AvailableVal = PHI;
349
162k
      (*AvailableVals)[Info->BB] = PHI;
350
162k
    }
351
255k
352
255k
    // Now go back through the worklist in reverse order to fill in the
353
255k
    // arguments for any new PHIs added in the forward traversal.
354
255k
    for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
355
1.41M
           E = BlockList->rend(); I != E; 
++I1.16M
) {
356
1.16M
      BBInfo *Info = *I;
357
1.16M
358
1.16M
      if (Info->DefBB != Info) {
359
989k
        // Record the available value to speed up subsequent uses of this
360
989k
        // SSAUpdater for the same value.
361
989k
        (*AvailableVals)[Info->BB] = Info->DefBB->AvailableVal;
362
989k
        continue;
363
989k
      }
364
174k
365
174k
      // Check if this block contains a newly added PHI.
366
174k
      PhiT *PHI = Traits::ValueIsNewPHI(Info->AvailableVal, Updater);
367
174k
      if (!PHI)
368
12.3k
        continue;
369
162k
370
162k
      // Iterate through the block's predecessors.
371
521k
      
for (unsigned p = 0; 162k
p != Info->NumPreds;
++p359k
) {
372
359k
        BBInfo *PredInfo = Info->Preds[p];
373
359k
        BlkT *Pred = PredInfo->BB;
374
359k
        // Skip to the nearest preceding definition.
375
359k
        if (PredInfo->DefBB != PredInfo)
376
59.4k
          PredInfo = PredInfo->DefBB;
377
359k
        Traits::AddPHIOperand(PHI, PredInfo->AvailableVal, Pred);
378
359k
      }
379
162k
380
162k
      LLVM_DEBUG(dbgs() << "  Inserted PHI: " << *PHI << "\n");
381
162k
382
162k
      // If the client wants to know about all new instructions, tell it.
383
162k
      if (InsertedPHIs) 
InsertedPHIs->push_back(PHI)129k
;
384
162k
    }
385
255k
  }
llvm::SSAUpdaterImpl<llvm::MachineSSAUpdater>::FindAvailableVals(llvm::SmallVectorImpl<llvm::SSAUpdaterImpl<llvm::MachineSSAUpdater>::BBInfo*>*)
Line
Count
Source
331
383
  void FindAvailableVals(BlockListTy *BlockList) {
332
383
    // Go through the worklist in forward order (i.e., backward through the CFG)
333
383
    // and check if existing PHIs can be used.  If not, create empty PHIs where
334
383
    // they are needed.
335
383
    for (typename BlockListTy::iterator I = BlockList->begin(),
336
1.01k
           E = BlockList->end(); I != E; 
++I633
) {
337
633
      BBInfo *Info = *I;
338
633
      // Check if there needs to be a PHI in BB.
339
633
      if (Info->DefBB != Info)
340
348
        continue;
341
285
342
285
      // Look for an existing PHI.
343
285
      FindExistingPHI(Info->BB, BlockList);
344
285
      if (Info->AvailableVal)
345
1
        continue;
346
284
347
284
      ValT PHI = Traits::CreateEmptyPHI(Info->BB, Info->NumPreds, Updater);
348
284
      Info->AvailableVal = PHI;
349
284
      (*AvailableVals)[Info->BB] = PHI;
350
284
    }
351
383
352
383
    // Now go back through the worklist in reverse order to fill in the
353
383
    // arguments for any new PHIs added in the forward traversal.
354
383
    for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
355
1.01k
           E = BlockList->rend(); I != E; 
++I633
) {
356
633
      BBInfo *Info = *I;
357
633
358
633
      if (Info->DefBB != Info) {
359
348
        // Record the available value to speed up subsequent uses of this
360
348
        // SSAUpdater for the same value.
361
348
        (*AvailableVals)[Info->BB] = Info->DefBB->AvailableVal;
362
348
        continue;
363
348
      }
364
285
365
285
      // Check if this block contains a newly added PHI.
366
285
      PhiT *PHI = Traits::ValueIsNewPHI(Info->AvailableVal, Updater);
367
285
      if (!PHI)
368
1
        continue;
369
284
370
284
      // Iterate through the block's predecessors.
371
918
      
for (unsigned p = 0; 284
p != Info->NumPreds;
++p634
) {
372
634
        BBInfo *PredInfo = Info->Preds[p];
373
634
        BlkT *Pred = PredInfo->BB;
374
634
        // Skip to the nearest preceding definition.
375
634
        if (PredInfo->DefBB != PredInfo)
376
27
          PredInfo = PredInfo->DefBB;
377
634
        Traits::AddPHIOperand(PHI, PredInfo->AvailableVal, Pred);
378
634
      }
379
284
380
284
      LLVM_DEBUG(dbgs() << "  Inserted PHI: " << *PHI << "\n");
381
284
382
284
      // If the client wants to know about all new instructions, tell it.
383
284
      if (InsertedPHIs) 
InsertedPHIs->push_back(PHI)41
;
384
284
    }
385
383
  }
llvm::SSAUpdaterImpl<llvm::SSAUpdater>::FindAvailableVals(llvm::SmallVectorImpl<llvm::SSAUpdaterImpl<llvm::SSAUpdater>::BBInfo*>*)
Line
Count
Source
331
255k
  void FindAvailableVals(BlockListTy *BlockList) {
332
255k
    // Go through the worklist in forward order (i.e., backward through the CFG)
333
255k
    // and check if existing PHIs can be used.  If not, create empty PHIs where
334
255k
    // they are needed.
335
255k
    for (typename BlockListTy::iterator I = BlockList->begin(),
336
1.41M
           E = BlockList->end(); I != E; 
++I1.16M
) {
337
1.16M
      BBInfo *Info = *I;
338
1.16M
      // Check if there needs to be a PHI in BB.
339
1.16M
      if (Info->DefBB != Info)
340
989k
        continue;
341
174k
342
174k
      // Look for an existing PHI.
343
174k
      FindExistingPHI(Info->BB, BlockList);
344
174k
      if (Info->AvailableVal)
345
12.3k
        continue;
346
162k
347
162k
      ValT PHI = Traits::CreateEmptyPHI(Info->BB, Info->NumPreds, Updater);
348
162k
      Info->AvailableVal = PHI;
349
162k
      (*AvailableVals)[Info->BB] = PHI;
350
162k
    }
351
255k
352
255k
    // Now go back through the worklist in reverse order to fill in the
353
255k
    // arguments for any new PHIs added in the forward traversal.
354
255k
    for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
355
1.41M
           E = BlockList->rend(); I != E; 
++I1.16M
) {
356
1.16M
      BBInfo *Info = *I;
357
1.16M
358
1.16M
      if (Info->DefBB != Info) {
359
989k
        // Record the available value to speed up subsequent uses of this
360
989k
        // SSAUpdater for the same value.
361
989k
        (*AvailableVals)[Info->BB] = Info->DefBB->AvailableVal;
362
989k
        continue;
363
989k
      }
364
174k
365
174k
      // Check if this block contains a newly added PHI.
366
174k
      PhiT *PHI = Traits::ValueIsNewPHI(Info->AvailableVal, Updater);
367
174k
      if (!PHI)
368
12.3k
        continue;
369
162k
370
162k
      // Iterate through the block's predecessors.
371
520k
      
for (unsigned p = 0; 162k
p != Info->NumPreds;
++p358k
) {
372
358k
        BBInfo *PredInfo = Info->Preds[p];
373
358k
        BlkT *Pred = PredInfo->BB;
374
358k
        // Skip to the nearest preceding definition.
375
358k
        if (PredInfo->DefBB != PredInfo)
376
59.4k
          PredInfo = PredInfo->DefBB;
377
358k
        Traits::AddPHIOperand(PHI, PredInfo->AvailableVal, Pred);
378
358k
      }
379
162k
380
162k
      LLVM_DEBUG(dbgs() << "  Inserted PHI: " << *PHI << "\n");
381
162k
382
162k
      // If the client wants to know about all new instructions, tell it.
383
162k
      if (InsertedPHIs) 
InsertedPHIs->push_back(PHI)129k
;
384
162k
    }
385
255k
  }
386
387
  /// FindExistingPHI - Look through the PHI nodes in a block to see if any of
388
  /// them match what is needed.
389
174k
  void FindExistingPHI(BlkT *BB, BlockListTy *BlockList) {
390
288k
    for (auto &SomePHI : BB->phis()) {
391
288k
      if (CheckIfPHIMatches(&SomePHI)) {
392
12.3k
        RecordMatchingPHIs(BlockList);
393
12.3k
        break;
394
12.3k
      }
395
276k
      // Match failed: clear all the PHITag values.
396
276k
      for (typename BlockListTy::iterator I = BlockList->begin(),
397
3.74M
             E = BlockList->end(); I != E; 
++I3.47M
)
398
3.47M
        (*I)->PHITag = nullptr;
399
276k
    }
400
174k
  }
llvm::SSAUpdaterImpl<llvm::MachineSSAUpdater>::FindExistingPHI(llvm::MachineBasicBlock*, llvm::SmallVectorImpl<llvm::SSAUpdaterImpl<llvm::MachineSSAUpdater>::BBInfo*>*)
Line
Count
Source
389
285
  void FindExistingPHI(BlkT *BB, BlockListTy *BlockList) {
390
1.61k
    for (auto &SomePHI : BB->phis()) {
391
1.61k
      if (CheckIfPHIMatches(&SomePHI)) {
392
1
        RecordMatchingPHIs(BlockList);
393
1
        break;
394
1
      }
395
1.61k
      // Match failed: clear all the PHITag values.
396
1.61k
      for (typename BlockListTy::iterator I = BlockList->begin(),
397
3.56k
             E = BlockList->end(); I != E; 
++I1.94k
)
398
1.94k
        (*I)->PHITag = nullptr;
399
1.61k
    }
400
285
  }
llvm::SSAUpdaterImpl<llvm::SSAUpdater>::FindExistingPHI(llvm::BasicBlock*, llvm::SmallVectorImpl<llvm::SSAUpdaterImpl<llvm::SSAUpdater>::BBInfo*>*)
Line
Count
Source
389
174k
  void FindExistingPHI(BlkT *BB, BlockListTy *BlockList) {
390
286k
    for (auto &SomePHI : BB->phis()) {
391
286k
      if (CheckIfPHIMatches(&SomePHI)) {
392
12.3k
        RecordMatchingPHIs(BlockList);
393
12.3k
        break;
394
12.3k
      }
395
274k
      // Match failed: clear all the PHITag values.
396
274k
      for (typename BlockListTy::iterator I = BlockList->begin(),
397
3.74M
             E = BlockList->end(); I != E; 
++I3.46M
)
398
3.46M
        (*I)->PHITag = nullptr;
399
274k
    }
400
174k
  }
401
402
  /// CheckIfPHIMatches - Check if a PHI node matches the placement and values
403
  /// in the BBMap.
404
288k
  bool CheckIfPHIMatches(PhiT *PHI) {
405
288k
    SmallVector<PhiT *, 20> WorkList;
406
288k
    WorkList.push_back(PHI);
407
288k
408
288k
    // Mark that the block containing this PHI has been visited.
409
288k
    BBMap[PHI->getParent()]->PHITag = PHI;
410
288k
411
317k
    while (!WorkList.empty()) {
412
305k
      PHI = WorkList.pop_back_val();
413
305k
414
305k
      // Iterate through the PHI's incoming values.
415
305k
      for (typename Traits::PHI_iterator I = Traits::PHI_begin(PHI),
416
403k
             E = Traits::PHI_end(PHI); I != E; 
++I97.5k
) {
417
373k
        ValT IncomingVal = I.getIncomingValue();
418
373k
        BBInfo *PredInfo = BBMap[I.getIncomingBlock()];
419
373k
        // Skip to the nearest preceding definition.
420
373k
        if (PredInfo->DefBB != PredInfo)
421
77.2k
          PredInfo = PredInfo->DefBB;
422
373k
423
373k
        // Check if it matches the expected value.
424
373k
        if (PredInfo->AvailableVal) {
425
313k
          if (IncomingVal == PredInfo->AvailableVal)
426
49.9k
            continue;
427
263k
          return false;
428
263k
        }
429
60.6k
430
60.6k
        // Check if the value is a PHI in the correct block.
431
60.6k
        PhiT *IncomingPHIVal = Traits::ValueIsPHI(IncomingVal, Updater);
432
60.6k
        if (!IncomingPHIVal || 
IncomingPHIVal->getParent() != PredInfo->BB49.1k
)
433
12.9k
          return false;
434
47.6k
435
47.6k
        // If this block has already been visited, check if this PHI matches.
436
47.6k
        if (PredInfo->PHITag) {
437
7.44k
          if (IncomingPHIVal == PredInfo->PHITag)
438
7.41k
            continue;
439
29
          return false;
440
29
        }
441
40.2k
        PredInfo->PHITag = IncomingPHIVal;
442
40.2k
443
40.2k
        WorkList.push_back(IncomingPHIVal);
444
40.2k
      }
445
305k
    }
446
288k
    
return true12.3k
;
447
288k
  }
llvm::SSAUpdaterImpl<llvm::MachineSSAUpdater>::CheckIfPHIMatches(llvm::MachineInstr*)
Line
Count
Source
404
1.61k
  bool CheckIfPHIMatches(PhiT *PHI) {
405
1.61k
    SmallVector<PhiT *, 20> WorkList;
406
1.61k
    WorkList.push_back(PHI);
407
1.61k
408
1.61k
    // Mark that the block containing this PHI has been visited.
409
1.61k
    BBMap[PHI->getParent()]->PHITag = PHI;
410
1.61k
411
1.61k
    while (!WorkList.empty()) {
412
1.61k
      PHI = WorkList.pop_back_val();
413
1.61k
414
1.61k
      // Iterate through the PHI's incoming values.
415
1.61k
      for (typename Traits::PHI_iterator I = Traits::PHI_begin(PHI),
416
1.69k
             E = Traits::PHI_end(PHI); I != E; 
++I79
) {
417
1.69k
        ValT IncomingVal = I.getIncomingValue();
418
1.69k
        BBInfo *PredInfo = BBMap[I.getIncomingBlock()];
419
1.69k
        // Skip to the nearest preceding definition.
420
1.69k
        if (PredInfo->DefBB != PredInfo)
421
19
          PredInfo = PredInfo->DefBB;
422
1.69k
423
1.69k
        // Check if it matches the expected value.
424
1.69k
        if (PredInfo->AvailableVal) {
425
1.67k
          if (IncomingVal == PredInfo->AvailableVal)
426
67
            continue;
427
1.61k
          return false;
428
1.61k
        }
429
17
430
17
        // Check if the value is a PHI in the correct block.
431
17
        PhiT *IncomingPHIVal = Traits::ValueIsPHI(IncomingVal, Updater);
432
17
        if (!IncomingPHIVal || 
IncomingPHIVal->getParent() != PredInfo->BB12
)
433
5
          return false;
434
12
435
12
        // If this block has already been visited, check if this PHI matches.
436
12
        if (PredInfo->PHITag) {
437
12
          if (IncomingPHIVal == PredInfo->PHITag)
438
12
            continue;
439
0
          return false;
440
0
        }
441
0
        PredInfo->PHITag = IncomingPHIVal;
442
0
443
0
        WorkList.push_back(IncomingPHIVal);
444
0
      }
445
1.61k
    }
446
1.61k
    
return true1
;
447
1.61k
  }
llvm::SSAUpdaterImpl<llvm::SSAUpdater>::CheckIfPHIMatches(llvm::PHINode*)
Line
Count
Source
404
286k
  bool CheckIfPHIMatches(PhiT *PHI) {
405
286k
    SmallVector<PhiT *, 20> WorkList;
406
286k
    WorkList.push_back(PHI);
407
286k
408
286k
    // Mark that the block containing this PHI has been visited.
409
286k
    BBMap[PHI->getParent()]->PHITag = PHI;
410
286k
411
316k
    while (!WorkList.empty()) {
412
303k
      PHI = WorkList.pop_back_val();
413
303k
414
303k
      // Iterate through the PHI's incoming values.
415
303k
      for (typename Traits::PHI_iterator I = Traits::PHI_begin(PHI),
416
401k
             E = Traits::PHI_end(PHI); I != E; 
++I97.5k
) {
417
371k
        ValT IncomingVal = I.getIncomingValue();
418
371k
        BBInfo *PredInfo = BBMap[I.getIncomingBlock()];
419
371k
        // Skip to the nearest preceding definition.
420
371k
        if (PredInfo->DefBB != PredInfo)
421
77.2k
          PredInfo = PredInfo->DefBB;
422
371k
423
371k
        // Check if it matches the expected value.
424
371k
        if (PredInfo->AvailableVal) {
425
311k
          if (IncomingVal == PredInfo->AvailableVal)
426
49.8k
            continue;
427
261k
          return false;
428
261k
        }
429
60.5k
430
60.5k
        // Check if the value is a PHI in the correct block.
431
60.5k
        PhiT *IncomingPHIVal = Traits::ValueIsPHI(IncomingVal, Updater);
432
60.5k
        if (!IncomingPHIVal || 
IncomingPHIVal->getParent() != PredInfo->BB49.1k
)
433
12.9k
          return false;
434
47.6k
435
47.6k
        // If this block has already been visited, check if this PHI matches.
436
47.6k
        if (PredInfo->PHITag) {
437
7.42k
          if (IncomingPHIVal == PredInfo->PHITag)
438
7.39k
            continue;
439
29
          return false;
440
29
        }
441
40.2k
        PredInfo->PHITag = IncomingPHIVal;
442
40.2k
443
40.2k
        WorkList.push_back(IncomingPHIVal);
444
40.2k
      }
445
303k
    }
446
286k
    
return true12.3k
;
447
286k
  }
448
449
  /// RecordMatchingPHIs - For each PHI node that matches, record it in both
450
  /// the BBMap and the AvailableVals mapping.
451
12.3k
  void RecordMatchingPHIs(BlockListTy *BlockList) {
452
12.3k
    for (typename BlockListTy::iterator I = BlockList->begin(),
453
253k
           E = BlockList->end(); I != E; 
++I241k
)
454
241k
      if (PhiT *PHI = (*I)->PHITag) {
455
52.0k
        BlkT *BB = PHI->getParent();
456
52.0k
        ValT PHIVal = Traits::GetPHIValue(PHI);
457
52.0k
        (*AvailableVals)[BB] = PHIVal;
458
52.0k
        BBMap[BB]->AvailableVal = PHIVal;
459
52.0k
      }
460
12.3k
  }
llvm::SSAUpdaterImpl<llvm::MachineSSAUpdater>::RecordMatchingPHIs(llvm::SmallVectorImpl<llvm::SSAUpdaterImpl<llvm::MachineSSAUpdater>::BBInfo*>*)
Line
Count
Source
451
1
  void RecordMatchingPHIs(BlockListTy *BlockList) {
452
1
    for (typename BlockListTy::iterator I = BlockList->begin(),
453
2
           E = BlockList->end(); I != E; 
++I1
)
454
1
      if (PhiT *PHI = (*I)->PHITag) {
455
1
        BlkT *BB = PHI->getParent();
456
1
        ValT PHIVal = Traits::GetPHIValue(PHI);
457
1
        (*AvailableVals)[BB] = PHIVal;
458
1
        BBMap[BB]->AvailableVal = PHIVal;
459
1
      }
460
1
  }
llvm::SSAUpdaterImpl<llvm::SSAUpdater>::RecordMatchingPHIs(llvm::SmallVectorImpl<llvm::SSAUpdaterImpl<llvm::SSAUpdater>::BBInfo*>*)
Line
Count
Source
451
12.3k
  void RecordMatchingPHIs(BlockListTy *BlockList) {
452
12.3k
    for (typename BlockListTy::iterator I = BlockList->begin(),
453
253k
           E = BlockList->end(); I != E; 
++I241k
)
454
241k
      if (PhiT *PHI = (*I)->PHITag) {
455
52.0k
        BlkT *BB = PHI->getParent();
456
52.0k
        ValT PHIVal = Traits::GetPHIValue(PHI);
457
52.0k
        (*AvailableVals)[BB] = PHIVal;
458
52.0k
        BBMap[BB]->AvailableVal = PHIVal;
459
52.0k
      }
460
12.3k
  }
461
};
462
463
} // end namespace llvm
464
465
#undef DEBUG_TYPE // "ssaupdater"
466
467
#endif // LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H