Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Vectorize/VPlanPredicator.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- VPlanPredicator.cpp -------------------------------------*- 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
/// \file
10
/// This file implements the VPlanPredicator class which contains the public
11
/// interfaces to predicate and linearize the VPlan region.
12
///
13
//===----------------------------------------------------------------------===//
14
15
#include "VPlanPredicator.h"
16
#include "VPlan.h"
17
#include "llvm/ADT/DepthFirstIterator.h"
18
#include "llvm/ADT/GraphTraits.h"
19
#include "llvm/ADT/PostOrderIterator.h"
20
#include "llvm/Support/Debug.h"
21
#include "llvm/Support/raw_ostream.h"
22
23
#define DEBUG_TYPE "VPlanPredicator"
24
25
using namespace llvm;
26
27
// Generate VPInstructions at the beginning of CurrBB that calculate the
28
// predicate being propagated from PredBB to CurrBB depending on the edge type
29
// between them. For example if:
30
//  i.  PredBB is controlled by predicate %BP, and
31
//  ii. The edge PredBB->CurrBB is the false edge, controlled by the condition
32
//  bit value %CBV then this function will generate the following two
33
//  VPInstructions at the start of CurrBB:
34
//   %IntermediateVal = not %CBV
35
//   %FinalVal        = and %BP %IntermediateVal
36
// It returns %FinalVal.
37
VPValue *VPlanPredicator::getOrCreateNotPredicate(VPBasicBlock *PredBB,
38
5
                                                  VPBasicBlock *CurrBB) {
39
5
  VPValue *CBV = PredBB->getCondBit();
40
5
41
5
  // Set the intermediate value - this is either 'CBV', or 'not CBV'
42
5
  // depending on the edge type.
43
5
  EdgeType ET = getEdgeTypeBetween(PredBB, CurrBB);
44
5
  VPValue *IntermediateVal = nullptr;
45
5
  switch (ET) {
46
5
  case EdgeType::TRUE_EDGE:
47
4
    // CurrBB is the true successor of PredBB - nothing to do here.
48
4
    IntermediateVal = CBV;
49
4
    break;
50
5
51
5
  case EdgeType::FALSE_EDGE:
52
1
    // CurrBB is the False successor of PredBB - compute not of CBV.
53
1
    IntermediateVal = Builder.createNot(CBV);
54
1
    break;
55
5
  }
56
5
57
5
  // Now AND intermediate value with PredBB's block predicate if it has one.
58
5
  VPValue *BP = PredBB->getPredicate();
59
5
  if (BP)
60
3
    return Builder.createAnd(BP, IntermediateVal);
61
2
  else
62
2
    return IntermediateVal;
63
5
}
64
65
// Generate a tree of ORs for all IncomingPredicates in  WorkList.
66
// Note: This function destroys the original Worklist.
67
//
68
// P1 P2 P3 P4 P5
69
//  \ /   \ /  /
70
//  OR1   OR2 /
71
//    \    | /
72
//     \   +/-+
73
//      \  /  |
74
//       OR3  |
75
//         \  |
76
//          OR4 <- Returns this
77
//           |
78
//
79
// The algorithm uses a worklist of predicates as its main data structure.
80
// We pop a pair of values from the front (e.g. P1 and P2), generate an OR
81
// (in this example OR1), and push it back. In this example the worklist
82
// contains {P3, P4, P5, OR1}.
83
// The process iterates until we have only one element in the Worklist (OR4).
84
// The last element is the root predicate which is returned.
85
6
VPValue *VPlanPredicator::genPredicateTree(std::list<VPValue *> &Worklist) {
86
6
  if (Worklist.empty())
87
0
    return nullptr;
88
6
89
6
  // The worklist initially contains all the leaf nodes. Initialize the tree
90
6
  // using them.
91
7
  
while (6
Worklist.size() >= 2) {
92
1
    // Pop a pair of values from the front.
93
1
    VPValue *LHS = Worklist.front();
94
1
    Worklist.pop_front();
95
1
    VPValue *RHS = Worklist.front();
96
1
    Worklist.pop_front();
97
1
98
1
    // Create an OR of these values.
99
1
    VPValue *Or = Builder.createOr(LHS, RHS);
100
1
101
1
    // Push OR to the back of the worklist.
102
1
    Worklist.push_back(Or);
103
1
  }
104
6
105
6
  assert(Worklist.size() == 1 && "Expected 1 item in worklist");
106
6
107
6
  // The root is the last node in the worklist.
108
6
  VPValue *Root = Worklist.front();
109
6
110
6
  // This root needs to replace the existing block predicate. This is done in
111
6
  // the caller function.
112
6
  return Root;
113
6
}
114
115
// Return whether the edge FromBlock -> ToBlock is a TRUE_EDGE or FALSE_EDGE
116
VPlanPredicator::EdgeType
117
VPlanPredicator::getEdgeTypeBetween(VPBlockBase *FromBlock,
118
5
                                    VPBlockBase *ToBlock) {
119
5
  unsigned Count = 0;
120
6
  for (VPBlockBase *SuccBlock : FromBlock->getSuccessors()) {
121
6
    if (SuccBlock == ToBlock) {
122
5
      assert(Count < 2 && "Switch not supported currently");
123
5
      return (Count == 0) ? 
EdgeType::TRUE_EDGE4
:
EdgeType::FALSE_EDGE1
;
124
5
    }
125
1
    Count++;
126
1
  }
127
5
128
5
  
llvm_unreachable0
("Broken getEdgeTypeBetween");
129
5
}
130
131
// Generate all predicates needed for CurrBlock by going through its immediate
132
// predecessor blocks.
133
void VPlanPredicator::createOrPropagatePredicates(VPBlockBase *CurrBlock,
134
18
                                                  VPRegionBlock *Region) {
135
18
  // Blocks that dominate region exit inherit the predicate from the region.
136
18
  // Return after setting the predicate.
137
18
  if (VPDomTree.dominates(CurrBlock, Region->getExit())) {
138
12
    VPValue *RegionBP = Region->getPredicate();
139
12
    CurrBlock->setPredicate(RegionBP);
140
12
    return;
141
12
  }
142
6
143
6
  // Collect all incoming predicates in a worklist.
144
6
  std::list<VPValue *> IncomingPredicates;
145
6
146
6
  // Set the builder's insertion point to the top of the current BB
147
6
  VPBasicBlock *CurrBB = cast<VPBasicBlock>(CurrBlock->getEntryBasicBlock());
148
6
  Builder.setInsertPoint(CurrBB, CurrBB->begin());
149
6
150
6
  // For each predecessor, generate the VPInstructions required for
151
6
  // computing 'BP AND (not) CBV" at the top of CurrBB.
152
6
  // Collect the outcome of this calculation for all predecessors
153
6
  // into IncomingPredicates.
154
7
  for (VPBlockBase *PredBlock : CurrBlock->getPredecessors()) {
155
7
    // Skip back-edges
156
7
    if (VPBlockUtils::isBackEdge(PredBlock, CurrBlock, VPLI))
157
0
      continue;
158
7
159
7
    VPValue *IncomingPredicate = nullptr;
160
7
    unsigned NumPredSuccsNoBE =
161
7
        VPBlockUtils::countSuccessorsNoBE(PredBlock, VPLI);
162
7
163
7
    // If there is an unconditional branch to the currBB, then we don't create
164
7
    // edge predicates. We use the predecessor's block predicate instead.
165
7
    if (NumPredSuccsNoBE == 1)
166
2
      IncomingPredicate = PredBlock->getPredicate();
167
5
    else if (NumPredSuccsNoBE == 2) {
168
5
      // Emit recipes into CurrBlock if required
169
5
      assert(isa<VPBasicBlock>(PredBlock) && "Only BBs have multiple exits");
170
5
      IncomingPredicate =
171
5
          getOrCreateNotPredicate(cast<VPBasicBlock>(PredBlock), CurrBB);
172
5
    } else
173
5
      
llvm_unreachable0
("FIXME: switch statement ?");
174
7
175
7
    if (IncomingPredicate)
176
7
      IncomingPredicates.push_back(IncomingPredicate);
177
7
  }
178
6
179
6
  // Logically OR all incoming predicates by building the Predicate Tree.
180
6
  VPValue *Predicate = genPredicateTree(IncomingPredicates);
181
6
182
6
  // Now update the block's predicate with the new one.
183
6
  CurrBlock->setPredicate(Predicate);
184
6
}
185
186
// Generate all predicates needed for Region.
187
2
void VPlanPredicator::predicateRegionRec(VPRegionBlock *Region) {
188
2
  VPBasicBlock *EntryBlock = cast<VPBasicBlock>(Region->getEntry());
189
2
  ReversePostOrderTraversal<VPBlockBase *> RPOT(EntryBlock);
190
2
191
2
  // Generate edge predicates and append them to the block predicate. RPO is
192
2
  // necessary since the predecessor blocks' block predicate needs to be set
193
2
  // before the current block's block predicate can be computed.
194
18
  for (VPBlockBase *Block : make_range(RPOT.begin(), RPOT.end())) {
195
18
    // TODO: Handle nested regions once we start generating the same.
196
18
    assert(!isa<VPRegionBlock>(Block) && "Nested region not expected");
197
18
    createOrPropagatePredicates(Block, Region);
198
18
  }
199
2
}
200
201
// Linearize the CFG within Region.
202
// TODO: Predication and linearization need RPOT for every region.
203
// This traversal is expensive. Since predication is not adding new
204
// blocks, we should be able to compute RPOT once in predication and
205
// reuse it here. This becomes even more important once we have nested
206
// regions.
207
2
void VPlanPredicator::linearizeRegionRec(VPRegionBlock *Region) {
208
2
  ReversePostOrderTraversal<VPBlockBase *> RPOT(Region->getEntry());
209
2
  VPBlockBase *PrevBlock = nullptr;
210
2
211
18
  for (VPBlockBase *CurrBlock : make_range(RPOT.begin(), RPOT.end())) {
212
18
    // TODO: Handle nested regions once we start generating the same.
213
18
    assert(!isa<VPRegionBlock>(CurrBlock) && "Nested region not expected");
214
18
215
18
    // Linearize control flow by adding an unconditional edge between PrevBlock
216
18
    // and CurrBlock skipping loop headers and latches to keep intact loop
217
18
    // header predecessors and loop latch successors.
218
18
    if (PrevBlock && 
!VPLI->isLoopHeader(CurrBlock)16
&&
219
18
        
!VPBlockUtils::blockIsLoopLatch(PrevBlock, VPLI)12
) {
220
8
221
8
      LLVM_DEBUG(dbgs() << "Linearizing: " << PrevBlock->getName() << "->"
222
8
                        << CurrBlock->getName() << "\n");
223
8
224
8
      PrevBlock->clearSuccessors();
225
8
      CurrBlock->clearPredecessors();
226
8
      VPBlockUtils::connectBlocks(PrevBlock, CurrBlock);
227
8
    }
228
18
229
18
    PrevBlock = CurrBlock;
230
18
  }
231
2
}
232
233
// Entry point. The driver function for the predicator.
234
2
void VPlanPredicator::predicate(void) {
235
2
  // Predicate the blocks within Region.
236
2
  predicateRegionRec(cast<VPRegionBlock>(Plan.getEntry()));
237
2
238
2
  // Linearlize the blocks with Region.
239
2
  linearizeRegionRec(cast<VPRegionBlock>(Plan.getEntry()));
240
2
}
241
242
VPlanPredicator::VPlanPredicator(VPlan &Plan)
243
2
    : Plan(Plan), VPLI(&(Plan.getVPLoopInfo())) {
244
2
  // FIXME: Predicator is currently computing the dominator information for the
245
2
  // top region. Once we start storing dominator information in a VPRegionBlock,
246
2
  // we can avoid this recalculation.
247
2
  VPDomTree.recalculate(*(cast<VPRegionBlock>(Plan.getEntry())));
248
2
}