← Back to branch summary

~ryan-rmarcus/pocl/pocl

« back to all changes in this revision

Viewing changes to lib/llvmopencl/BarrierTailReplication.cc

  • Committer: Carlos Sánchez de La Lama
  • Date: 2011-11-11 11:51:00 UTC
  • mfrom: (57.1.16 pocl.loopbarriers)
  • Revision ID: carlos.delalama@urjc.es-20111111115100-mcchrwx8o16g0ymc
Merge.
Barriers in for loops are still not fully tested but I merge to
include the ReferenceMap indexing fix in trunk.

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/llvmopencl/BarrierTailReplication.cc
21
21
// THE SOFTWARE.
22
22
 
23
23
#include "BarrierTailReplication.h"
24
 
#include "llvm/Function.h"
25
24
#include "llvm/InstrTypes.h"
26
25
#include "llvm/Instructions.h"
27
 
#include <map>
28
 
#include <set>
29
26
 
30
27
using namespace llvm;
31
28
using namespace pocl;
32
29
 
33
30
#define BARRIER_FUNCTION_NAME "barrier"
34
31
 
35
 
static void find_barriers_dfs(BasicBlock *bb, std::set<BasicBlock *> &processed_bbs);
36
32
static bool block_has_barrier(const BasicBlock *bb);
37
 
static BasicBlock *replicate_subgraph(BasicBlock *entry,
38
 
                                      Function *f);
39
 
static void find_subgraph(std::set<BasicBlock *> &subgraph,
40
 
                          BasicBlock *entry);
41
 
static void replicate_basicblocks(std::set<BasicBlock *> &new_graph,
42
 
                                  std::map<Value *, Value *> &reference_map,
43
 
                                  const std::set<BasicBlock *> &graph,
44
 
                                  Function *f);
45
 
static void update_references(const std::set<BasicBlock *>&graph,
46
 
                              const std::map<Value *, Value *> &reference_map);
47
33
  
48
34
namespace {
49
35
  static
50
36
  RegisterPass<BarrierTailReplication> X("barriertails",
51
 
                                         "Barrier tail replication pass",
52
 
                                         false, false);
 
37
                                         "Barrier tail replication pass");
53
38
}
54
39
 
55
40
char BarrierTailReplication::ID = 0;
56
41
 
 
42
void
 
43
BarrierTailReplication::getAnalysisUsage(AnalysisUsage &AU) const
 
44
{
 
45
  AU.addRequired<DominatorTree>();
 
46
  AU.addPreserved<DominatorTree>();
 
47
  AU.addRequired<LoopInfo>();
 
48
  AU.addPreserved<LoopInfo>();
 
49
}
 
50
 
57
51
bool
58
52
BarrierTailReplication::runOnFunction(Function &F)
59
53
{
60
 
  std::set<BasicBlock *> processed_bbs;
61
 
 
62
 
  find_barriers_dfs(&(F.getEntryBlock()), processed_bbs);
 
54
  DT = &getAnalysis<DominatorTree>();
 
55
  LI = &getAnalysis<LoopInfo>();
 
56
 
 
57
  return ProcessFunction(F);
 
58
}
 
59
 
 
60
bool
 
61
BarrierTailReplication::ProcessFunction(Function &F)
 
62
{
 
63
  BasicBlockSet processed_bbs;
 
64
 
 
65
  FindBarriersDFS(&F.getEntryBlock(), processed_bbs);
 
66
 
 
67
  DT->verifyAnalysis();
 
68
  LI->verifyAnalysis();
63
69
 
64
70
  return true;
65
 
}
 
71
}  
66
72
 
67
 
static void
68
 
find_barriers_dfs(BasicBlock *bb, std::set<BasicBlock *> &processed_bbs)
 
73
 
 
74
// Recursively (depht-first) look for barriers in all possible
 
75
// execution paths starting on entry, replicating the barrier
 
76
// successors to ensure there is a separate function exit BB
 
77
// for each combination of traversed barriers. The set
 
78
// processed_bbs stores the 
 
79
void
 
80
BarrierTailReplication::FindBarriersDFS(BasicBlock *bb,
 
81
                                        BasicBlockSet &processed_bbs)
69
82
{
 
83
  // Check if we already visited this BB (to avoid
 
84
  // infinite recursion in case of unbarriered loops).
70
85
  if (processed_bbs.count(bb) != 0)
71
86
    return;
72
87
 
73
88
  processed_bbs.insert(bb);
74
89
 
 
90
  TerminatorInst *t = bb->getTerminator();
75
91
  Function *f = bb->getParent();
76
 
  TerminatorInst *t = bb->getTerminator();
77
92
 
78
93
  if (block_has_barrier(bb)) {
79
 
    // Replicate all successors.
80
 
    for (unsigned i = 0, e = t->getNumSuccessors(); i != e; ++i) {
81
 
      BasicBlock *subgraph_entry = t->getSuccessor(i);
82
 
      BasicBlock *replicated_subgraph_entry =
83
 
        replicate_subgraph(subgraph_entry, f);
84
 
      t->setSuccessor(i, replicated_subgraph_entry);
85
 
    }
 
94
    // This block has a barrier, replicate all successors.
 
95
    // Even the path starting in an unique successor is replicated,
 
96
    // as it the path might be joined by another path in a
 
97
    // sucessor BB (see ifbarrier4.ll in tests).
 
98
 
 
99
    // Loop check should not be needed here anymore, barriers
 
100
    // have been canonicalized so they have exactly one succesor.
 
101
    assert((t->getNumSuccessors() == 1) && "Not canonicalized barrier found!");
 
102
    BasicBlock *subgraph_entry = t->getSuccessor(0);
 
103
    BasicBlock *replicated_subgraph_entry =
 
104
      ReplicateSubgraph(subgraph_entry, f);
 
105
    t->setSuccessor(0, replicated_subgraph_entry);
 
106
    
 
107
    // We have modified the function. Possibly created new loops.
 
108
    // Update analysis passes.
 
109
    DT->runOnFunction(*f);
 
110
    LI->releaseMemory();
 
111
    LI->getBase().Calculate(DT->getBase());
86
112
  }
87
113
 
88
114
  // Find barriers in the successors (depth first).
89
115
  for (unsigned i = 0, e = t->getNumSuccessors(); i != e; ++i)
90
 
    find_barriers_dfs(t->getSuccessor(i), processed_bbs);
91
 
}
92
 
 
93
 
static bool
94
 
block_has_barrier(const BasicBlock *bb)
95
 
{
96
 
  for (BasicBlock::const_iterator i = bb->begin(), e = bb->end();
97
 
       i != e; ++i) {
98
 
    if (const CallInst *c = dyn_cast<CallInst>(i)) {
99
 
      const Value *v = c->getCalledValue();
100
 
      if (v->getName().equals(BARRIER_FUNCTION_NAME))
101
 
        return true;
102
 
    }
103
 
  }
104
 
 
105
 
  return false;
106
 
}
107
 
 
108
 
static BasicBlock *
109
 
replicate_subgraph(BasicBlock *entry, Function *f)
 
116
    FindBarriersDFS(t->getSuccessor(i), processed_bbs);
 
117
}
 
118
 
 
119
 
 
120
BasicBlock *
 
121
BarrierTailReplication::ReplicateSubgraph(BasicBlock *entry,
 
122
                                          Function *f)
110
123
{
111
124
  // Find all basic blocks to replicate.
112
 
  std::set<BasicBlock *> subgraph;
113
 
  find_subgraph(subgraph, entry);
 
125
  BasicBlockSet subgraph;
 
126
  FindSubgraph(subgraph, entry);
114
127
 
115
128
  // Replicate subgraph maintaining control flow.
116
 
  std::set<BasicBlock *> v;
117
 
  std::map<Value *, Value *> m;
118
 
  replicate_basicblocks(v, m, subgraph, f);
119
 
  update_references(v, m);
 
129
  BasicBlockSet v;
 
130
  ValueValueMap m;
 
131
  ReplicateBasicBlocks(v, m, subgraph, f);
 
132
  UpdateReferences(v, m);
120
133
 
121
134
  // Return entry block of replicated subgraph.
122
135
  return cast<BasicBlock>(m[entry]);
123
136
}
124
137
 
125
 
static void
126
 
find_subgraph(std::set<BasicBlock *> &subgraph,
127
 
              BasicBlock *entry)
 
138
 
 
139
void
 
140
BarrierTailReplication::FindSubgraph(BasicBlockSet &subgraph,
 
141
                                     BasicBlock *entry)
128
142
{
129
 
  if (subgraph.count(entry) != 0)
130
 
    return;
131
 
 
132
143
  subgraph.insert(entry);
133
144
 
134
145
  const TerminatorInst *t = entry->getTerminator();
135
 
  for (unsigned i = 0, e = t->getNumSuccessors(); i != e; ++i)
136
 
    find_subgraph(subgraph, t->getSuccessor(i));
 
146
  Loop *l = LI->getLoopFor(entry);
 
147
  for (unsigned i = 0, e = t->getNumSuccessors(); i != e; ++i) {
 
148
    BasicBlock *successor = t->getSuccessor(i);
 
149
    if ((l != NULL)  && (l->getHeader() == successor)) {
 
150
      // This is a loop backedge. Do not find subgraphs across
 
151
      // those.
 
152
      continue;
 
153
    }
 
154
    FindSubgraph(subgraph, successor);
 
155
  }
137
156
}
138
157
 
139
 
static void
140
 
replicate_basicblocks(std::set<BasicBlock *> &new_graph,
141
 
                      std::map<Value *, Value *> &reference_map,
142
 
                      const std::set<BasicBlock *> &graph,
143
 
                      Function *f)
 
158
 
 
159
void
 
160
BarrierTailReplication::ReplicateBasicBlocks(BasicBlockSet &new_graph,
 
161
                                             ValueValueMap &reference_map,
 
162
                                             BasicBlockSet &graph,
 
163
                                             Function *f)
144
164
{
145
 
  for (std::set<BasicBlock *>::const_iterator i = graph.begin(),
 
165
  for (BasicBlockSet::const_iterator i = graph.begin(),
146
166
         e = graph.end();
147
167
       i != e; ++i) {
148
168
    BasicBlock *b = *i;
149
169
    BasicBlock *new_b = BasicBlock::Create(b->getContext(),
150
 
                                           b->getName(),
 
170
                                           b->getName() + ".btr",
151
171
                                           f);
152
172
    reference_map.insert(std::make_pair(b, new_b));
153
173
    new_graph.insert(new_b);
161
181
  }
162
182
}
163
183
 
164
 
static void
165
 
update_references(const std::set<BasicBlock *>&graph,
166
 
                  const std::map<Value *, Value *> &reference_map)
 
184
 
 
185
void
 
186
BarrierTailReplication::UpdateReferences(const BasicBlockSet &graph,
 
187
                                         const ValueValueMap &reference_map)
167
188
{
168
 
  for (std::set<BasicBlock *>::const_iterator i = graph.begin(),
 
189
  for (BasicBlockSet::const_iterator i = graph.begin(),
169
190
         e = graph.end();
170
191
       i != e; ++i) {
171
192
    BasicBlock *b = *i;
172
193
    for (BasicBlock::iterator i2 = b->begin(), e2 = b->end();
173
194
         i2 != e2; ++i2) {
174
195
      Instruction *i = i2;
175
 
      for (std::map<Value *, Value *>::const_iterator i3 =
 
196
      for (ValueValueMap::const_iterator i3 =
176
197
             reference_map.begin(), e3 = reference_map.end();
177
198
           i3 != e3; ++i3) {
178
199
        i->replaceUsesOfWith(i3->first, i3->second);
181
202
  }
182
203
}
183
204
 
 
205
 
 
206
static bool
 
207
block_has_barrier(const BasicBlock *bb)
 
208
{
 
209
  for (BasicBlock::const_iterator i = bb->begin(), e = bb->end();
 
210
       i != e; ++i) {
 
211
    if (const CallInst *c = dyn_cast<CallInst>(i)) {
 
212
      const Value *v = c->getCalledValue();
 
213
      if (v->getName().equals(BARRIER_FUNCTION_NAME))
 
214
        return true;
 
215
    }
 
216
  }
 
217
 
 
218
  return false;
 
219
}