poly_PolyAnalysis.cpp 17.1 KB
Newer Older
Ballabriga Clément's avatar
Ballabriga Clément committed
1
2
#include <ctime>
#include <otawa/cfg/Edge.h>
clement's avatar
init  
clement committed
3
#include <otawa/dfa/FastState.h>
Ballabriga Clément's avatar
Ballabriga Clément committed
4
#include <otawa/dfa/ai.h>
clement's avatar
init  
clement committed
5
6
#include <otawa/flowfact/features.h>
#include <otawa/graph/Graph.h>
Ballabriga Clément's avatar
Ballabriga Clément committed
7
8
9
#include <otawa/otawa.h>
#include <otawa/util/HalfAbsInt.h>
#include <otawa/util/WideningFixPoint.h>
10
#include <otawa/hard/Memory.h>
Ballabriga Clément's avatar
Ballabriga Clément committed
11
#include <otawa/util/WideningListener.h>
Ballabriga Clément's avatar
Ballabriga Clément committed
12
#include <otawa/oslice/features.h>
Ballabriga Clément's avatar
ok    
Ballabriga Clément committed
13
#include <otawa/ai/WorkListDriver.h>
clement's avatar
init  
clement committed
14
15
#include <ppl.hh>

Ballabriga Clément's avatar
Ballabriga Clément committed
16
17
18
#include "include/PPLDomain.h"
#include "include/PPLManager.h"
#include "include/PolyAnalysis.h"
Ballabriga Clément's avatar
Ballabriga Clément committed
19
20
namespace otawa {
namespace poly {
Ballabriga Clément's avatar
Ballabriga Clément committed
21
22
using namespace otawa;
using namespace util;
clement's avatar
init  
clement committed
23

Ballabriga Clément's avatar
Ballabriga Clément committed
24
25
26
27
p::declare PolyAnalysis::reg = p::init("otawa::poly::PolyAnalysis", Version(1, 0, 0))
                                   .require(COLLECTED_CFG_FEATURE)
                                   .require(LOOP_INFO_FEATURE)
                                   .require(dfa::INITIAL_STATE_FEATURE)
Ballabriga Clément's avatar
Ballabriga Clément committed
28
								   .require(MEMORY_ACCESS_FEATURE)
Ballabriga Clément's avatar
Ballabriga Clément committed
29
								   .require(oslice::LIVENESS_FEATURE)
Ballabriga Clément's avatar
Ballabriga Clément committed
30
                                   .provide(POLY_ANALYSIS_FEATURE);
clement's avatar
init  
clement committed
31

Ballabriga Clément's avatar
Ballabriga Clément committed
32
PolyAnalysis::PolyAnalysis(p::declare &r) : Processor(r) {}
clement's avatar
init  
clement committed
33
34

void PolyAnalysis::configure(const PropList &props) {
Ballabriga Clément's avatar
Ballabriga Clément committed
35

clement's avatar
init  
clement committed
36
	Processor::configure(props);
Ballabriga Clément's avatar
Ballabriga Clément committed
37
	_props = &props;
clement's avatar
init  
clement committed
38
39
}

40
41
PolyAnalysis::state_t PolyAnalysis::processHeader(ai::CFGGraph &graph, MyHTable<int,PPLDomain> &lb,
		BasicBlock *header, PPLManager& man, ai::EdgeStore<PPLManager, ai::CFGGraph>& store, MyHTable<int, state_t> &headerState) { 
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
	state_t entryState = man.bot();
	state_t backState = man.bot();

	for (ai::CFGGraph::Predecessor e(graph, header); e; e++) {
		state_t edgeState = store.get(*e);

		if (Dominance::dominates(e->sink(), e->source())) {
			/* back edge */
			backState = man.join(backState, edgeState);
		} else {
			/* entry edge */
			entryState = man.join(entryState, edgeState);
		}
	}

	if (!headerState.hasKey(header->id())) {
		headerState[header->id()] = man.bot();
	}

#ifdef POLY_DEBUG
	cout << "Widening, backState = " << backState << endl;
	cout << "Widening, entryState = " << entryState << endl;
	cout << "Widening, oldHeaderState = " << state_t(headerState[header->id()]) << endl;
#endif
	//state_t oldState = headerState[header->id()];

	bound_t bound = backState.getLoopBound(header->id());
	backState.setBound(header->id(), bound);

71
	PPLDomain linearBound = backState.getLinearExpr(Ident(header->id(), Ident::ID_LOOP));
72
	cout << "setLinBound: " << linearBound << endl;
73
74
	backState.setLinBound(header->id(), linearBound);

75
76
77
#ifdef POLY_DEBUG
			cout << "ITERATION: " << int(bound) << endl;
#endif
78
			/*
79
80
81
	if ((MAX_ITERATION(header) != bound_t::UNBOUNDED) &&
		((MAX_ITERATION(header) < bound) || (bound == bound_t::UNBOUNDED)))
		MAX_ITERATION(header) = bound;
82
83
84
85
86
		*/


	if (!lb.hasKey(header->id()))
		lb[header->id()] = PPLDomain();
87

88
89
90
	const PPLDomain &oldBound = lb[header->id()];

	lb[header->id()] = oldBound.onMerge(linearBound, false);
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
	headerState[header->id()] = man.widening(backState, headerState[header->id()]);

#ifdef POLY_DEBUG
	cout << "Widening, after Widening = " << headerState[header->id()] << endl;
#endif

	headerState[header->id()] = man.join(headerState[header->id()], entryState);

#ifdef POLY_DEBUG
	cout << "Widening, after Join with entryState = " << headerState[header->id()] << endl;
#endif
	/*
	cout << "Widening, newHeaderState = " << state_t(headerState[header->id()]) << endl;
	if (oldState.equals(headerState[header->id()])) {
		cout << "EQUAL" << endl;
	} else {
		cout << "NOT EQUAL" << endl;
	}
	*/
	return headerState[header->id()];
}

113
void PolyAnalysis::processBB(PPLManager *man, ai::CFGGraph &graph, MyHTable<int,PPLDomain> &lb,
Ballabriga Clément's avatar
ok    
Ballabriga Clément committed
114
                             WorkListDriver<PPLManager, ai::CFGGraph, ai::EdgeStore<PPLManager, ai::CFGGraph>, PseudoTopoOrder> &ana,
115
							 ai::EdgeStore<PPLManager, ai::CFGGraph>& store,
Ballabriga Clément's avatar
ok    
Ballabriga Clément committed
116
                             MyHTable<int, state_t> &headerState) {
Ballabriga Clément's avatar
Ballabriga Clément committed
117
118
119
120
121
122
	/*
	 * The processing is made up of two main parts:
	 *
	 * 1. Basic Block processing: Performing the actual abstract Update on the current basic block.
	 * 2. Edge Processing: Propagating state on successors, potentially taking care of filtering (conditional branches).
	 */
123
	state_t s = man->bot();
Ballabriga Clément's avatar
Ballabriga Clément committed
124

125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
	/* Special processing for loop headers, to handle loop bounds and widening */
	if (LOOP_HEADER(*ana)) {
#ifdef POLY_DEBUG
		cout << "Basic block is loop header: " << (*ana)->toBasic()->id() << endl;
#endif
		s = processHeader(graph, lb, (*ana)->toBasic(), *man, store, headerState);
	} else {
		s = ana.input();
	}

	if (s.isBottom()) {
#ifdef POLY_DEBUG
		cout << "! Skip block because input state is Bottom" << endl;
#endif
		return;
	}

#ifdef POLY_DEBUG
	cout << "State at basic block start: " << endl << s << endl;
	cout << "isSynth: " << (*ana)->isSynth() << endl;
#endif

Ballabriga Clément's avatar
Ballabriga Clément committed
147
148
	if ((*ana)->isSynth()) {
		/* Handle call to another function */
149

Ballabriga Clément's avatar
Ballabriga Clément committed
150
151
152
		CFG *subCFG = (*ana)->toSynth()->callee();
		cout << "Call from " << (*ana)->toSynth()->caller()->name() << " to " << subCFG->name() << endl;

153
154
		bool compose_ok = false;

Ballabriga Clément's avatar
Ballabriga Clément committed
155
156
157
158
		if (SUMMARIZE(workspace())) {
			state_t sum;
			if (SUMMARY(subCFG) == nullptr) {
				cout << "No summary exists for " << (*ana)->toSynth()->callee()->name() << ", creating one..." << endl;
159
160
				MyHTable<int, PPLDomain> *sublb = new MyHTable<int, PPLDomain>();
				processCFG(*subCFG, sum, *sublb, true, true); 
Ballabriga Clément's avatar
Ballabriga Clément committed
161
162
163

				cout << "Finished creating summary of " << subCFG->name() << ", returning to " << (*ana)->toSynth()->caller()->name() << endl;
				SUMMARY(subCFG) = new PPLDomain(sum);
164
				MAX_LINEAR(subCFG) = sublb;
Ballabriga Clément's avatar
Ballabriga Clément committed
165
#ifdef POLY_DEBUG				
166
167
168
169
170
171
172
				cout << "summary = " << endl;
				cout << sum << endl;
				cout << "parametric bounds = " << endl;
				for (MyHTable<int, PPLDomain>::PairIterator it(*sublb); it; it++) {
					cout << (*it).fst << " --> " << (*it).snd << endl;
				}
				cout << endl;
173
#endif				
Ballabriga Clément's avatar
Ballabriga Clément committed
174
			} else {
175
				cout << "Reusing to reusing existing summary." << endl;
Ballabriga Clément's avatar
Ballabriga Clément committed
176
177
178
				PPLDomain *p = SUMMARY(subCFG);
				sum = *p;
			}
179
#ifdef POLY_DEBUG
Ballabriga Clément's avatar
Ballabriga Clément committed
180
181
182
183
			cout << "Composing state with summary. Caller state = " << endl;
			cout << s << endl;
			cout << "Summary = " << endl;
			cout << sum << endl;
184
#endif
185
186
187
188
189
190
191
192
			state_t tmp = s.onCompose(sum);
			if (tmp.isBottom()) {
				cout << "Failed to use summary due to constraint violation" << endl;
			} else {
				compose_ok = true;
				MyHTable<int, PPLDomain> *sublb = MAX_LINEAR(subCFG);
				for (MyHTable<int, PPLDomain>::PairIterator it(*sublb); it; it++) {
						PPLDomain composed((*it).snd);
193
194
						cout << "linear bounds: " << composed << endl;
						cout << "caller state: " << s << endl;
195
						composed = s.onCompose(composed);
196
						cout << "composed bounds: " << composed << endl;
197
198
199
200
						composed = composed.getLinearExpr(Ident((*it).fst, Ident::ID_LOOP));
						if (!lb.hasKey((*it).fst))
							lb[(*it).fst] = PPLDomain();
						lb[(*it).fst] = lb.get((*it).fst).value().onMerge(composed, false);
201

202
				}
203
				s = tmp;
204

Ballabriga Clément's avatar
Ballabriga Clément committed
205
#ifdef POLY_DEBUG
206
207
				cout << "Composed state = " << endl;
				cout << s << endl;
208
#endif
209
210
211
			}
		} 
		if (!compose_ok) { // no summarizing
Ballabriga Clément's avatar
Ballabriga Clément committed
212
213
214
215
216
217
218
219
220
221
222
			if ((*ana)->toSynth()->callee()->name() == "gsignal" ||
			    (*ana)->toSynth()->callee()->name() == "__divsi3" ||  
			    (*ana)->toSynth()->callee()->name() == "__aeabi_i2d" ||  
			    (*ana)->toSynth()->callee()->name() == "__muldf3" ||  
			    (*ana)->toSynth()->callee()->name() == "__divdf3" ||  
			    (*ana)->toSynth()->callee()->name() == "__adddf3" ||  
			    (*ana)->toSynth()->callee()->name() == "__fixdfsi" ||  
			    (*ana)->toSynth()->callee()->name() == "__aeabi_dsub" || 
			    (*ana)->toSynth()->callee()->name() == "gsignal") {
				cout << "[FIXME] Ignoring call to function: " << (*ana)->toSynth()->callee()->name() << endl;
			} else {
223
				processCFG(*subCFG, s, lb, false, false);
Ballabriga Clément's avatar
Ballabriga Clément committed
224
225
				cout << "Return from " << subCFG->name() << " to " << (*ana)->toSynth()->caller()->name() << endl;
			}
Ballabriga Clément's avatar
Ballabriga Clément committed
226
		}
227
	
Ballabriga Clément's avatar
Ballabriga Clément committed
228
		for (ai::CFGGraph::Successor e(graph, *ana); e; e++) {
Ballabriga Clément's avatar
Ballabriga Clément committed
229
230
			ana.check(*e, s);
		}
Ballabriga Clément's avatar
Ballabriga Clément committed
231
232
233
	} else {
		/* Handle normal basic block */
		BasicBlock *bl = (*ana)->toBasic();
Ballabriga Clément's avatar
Ballabriga Clément committed
234
#ifdef POLY_DEBUG
Ballabriga Clément's avatar
ordre    
Ballabriga Clément committed
235
		cout << "Processing basic block: " << bl << " spaceDimension=" << s.getVarIDCount() << ", numCons=" << s.getConsCount() << "\n";
Ballabriga Clément's avatar
Ballabriga Clément committed
236
#endif
clement's avatar
init  
clement committed
237

Ballabriga Clément's avatar
Ballabriga Clément committed
238
239
		/* Basic block processing */
		for (BasicBlock::InstIter inst(bl); inst; inst++) {
Ballabriga Clément's avatar
Ballabriga Clément committed
240
#ifdef POLY_DEBUG
Ballabriga Clément's avatar
Ballabriga Clément committed
241
			cout << "Starting update for CPU (concrete) instruction: " << *inst << endl;
clement's avatar
clement committed
242
#endif
Ballabriga Clément's avatar
Ballabriga Clément committed
243
			sem::Block block;
Ballabriga Clément's avatar
Ballabriga Clément committed
244
			inst->semInsts(block);
Ballabriga Clément's avatar
Ballabriga Clément committed
245
246
247
			for (sem::Block::InstIter semi(block); semi; semi++) {
#ifdef POLY_DEBUG
				cout << "Updating for semantic instruction (IR): " << *semi << endl;
clement's avatar
clement committed
248
#endif
Ballabriga Clément's avatar
Ballabriga Clément committed
249
250
251
				s = s.onSemInst(*semi, inst->address());
#ifdef POLY_DEBUG
				cout << "State after semantic instruction update: " << endl << s << endl << endl;
clement's avatar
clement committed
252
#endif
Ballabriga Clément's avatar
Ballabriga Clément committed
253
				s.doIntegerWrap();
Clement's avatar
Clement committed
254
			}
Ballabriga Clément's avatar
Ballabriga Clément committed
255
#ifdef POLY_DEBUG
Clement's avatar
Clement committed
256
			cout << "Finished update for CPU (concrete) instruction: " << *inst << endl;
clement's avatar
clement committed
257
#endif
Ballabriga Clément's avatar
not bad    
Ballabriga Clément committed
258

Ballabriga Clément's avatar
ordre    
Ballabriga Clément committed
259
			s.doKillTemporaries();
Ballabriga Clément's avatar
ok    
Ballabriga Clément committed
260
			s.doFinalizeUpdate();
Ballabriga Clément's avatar
Ballabriga Clément committed
261
#ifdef POLY_DEBUG
Ballabriga Clément's avatar
Ballabriga Clément committed
262
			cout << "State after cleanup: " << endl << s << endl;
Clement's avatar
Clement committed
263
#endif
Ballabriga Clément's avatar
Ballabriga Clément committed
264
265
		}

Ballabriga Clément's avatar
Ballabriga Clément committed
266
267
		s.doKillRegisters(oslice::REG_BB_END_IN(bl));
		s.doFinalizeUpdate();
268
269
	}

Ballabriga Clément's avatar
Ballabriga Clément committed
270

271
272
	/* Edge Processing, propagate updated state to successors */
	for (int doExit = 0; doExit < 2; doExit++) {
Ballabriga Clément's avatar
Ballabriga Clément committed
273

274
275
276
277
278
279
		/* Do loop exit edges last (improves performance) */
		for (ai::CFGGraph::Successor e(graph, *ana); e; e++) {
			if ((LOOP_EXIT_EDGE(e) == nullptr) && !doExit)
				continue;
			if ((LOOP_EXIT_EDGE(e) != nullptr) && doExit)
				continue;
Ballabriga Clément's avatar
Ballabriga Clément committed
280
#ifdef POLY_DEBUG
281
			cout << "OutEdge: " << *e << ", taken= " << (e->isTaken()) << endl;
clement's avatar
clement committed
282
#endif
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
			/*
			 * In most cases, the state is not updated (i.e. modified) by edge processing.
			 * We need update on edge if any of these (non-mutually-exclusive) following conditions are true:
			 *
			 * 1. The current successor of current block is a loop header (need to do onLoopEntry or onLoopIter)
			 * 2. The current output edge of current block is an exit-edge (need to do onLoopExit)
			 * 3. The current block has a conditional branch (need to do onBranch, for filtering)
			 */
			if (!LOOP_HEADER(e->sink()) && (LOOP_EXIT_EDGE(e) == nullptr) && !s.hasFilter()) {
				/* no edge update: simply copy output state to successor input state */
				ana.check(*e, s);
			} else {
				/* process edge update */
				state_t edgeState = s;

				if (edgeState.hasFilter()) {
					/* Filtering: apply branch condition on edge state */
Ballabriga Clément's avatar
Ballabriga Clément committed
300
#ifdef POLY_DEBUG
301
302
					cout << "BEFORE FILTERING: " << endl;
					cout << edgeState;
clement's avatar
clement committed
303
#endif
304
305
306
307
					edgeState = edgeState.onBranch(e->isTaken());
					if (edgeState.isBottom()) {
						continue;
					}
Ballabriga Clément's avatar
Ballabriga Clément committed
308
#ifdef POLY_DEBUG
309
310
					cout << "FILTERED STATE: " << endl;
					cout << edgeState;
clement's avatar
clement committed
311
#endif
312
				}
clement's avatar
init  
clement committed
313

314
315
316
317
318
319
320
321
322
323
324
				if (LOOP_HEADER(e->sink())) {
					if (Dominance::dominates(e->sink(), e->source())) {
						/* Back-Edge: increment virtual loop counter */
						edgeState = edgeState.onLoopIter(e->sink()->id());
						cout << "LOOPITER" << endl;
					} else {
						/* Entry-Edge: initialize virtal loop counter */
						edgeState = edgeState.onLoopEntry(e->sink()->id());

						/* Avoid unnecessary widening before first loop iteration of inner loops */
						// headerState.remove(e->sink()->id()); 
Ballabriga Clément's avatar
Ballabriga Clément committed
325
					}
326
				}
Ballabriga Clément's avatar
Ballabriga Clément committed
327

328
329
330
				if (LOOP_EXIT_EDGE(e) != nullptr) {
					/* Exit edge: remove virtual loop counter, and apply loop bound constraint on state */
					Block *bb = LOOP_EXIT_EDGE(e);
Ballabriga Clément's avatar
Ballabriga Clément committed
331

332
333
334
335
336
					/* 
					 * FIXME: should be bound = s.getLoopBound(bb->id()) but we need to fix the widening to make it work
					 */
					int bound = edgeState.getBound(bb->id());
					PPLDomain linBound = edgeState.getLinBound(bb->id());
Ballabriga Clément's avatar
Ballabriga Clément committed
337
#ifdef POLY_DEBUG
338
					cout << "Bound on loop exit: " << bound << endl;
Ballabriga Clément's avatar
Ballabriga Clément committed
339
#endif
340
341
342
343
344
					if (!linBound.isBottom()) {
						edgeState = edgeState.onLoopExitLinear(bb->id(), linBound);
						if (edgeState.isBottom())
							continue;
					}
345
#ifdef POLY_DEBUG
346
					cout << "linbound for " << bb->id() << " is " << linBound << endl;
347
#endif
348
349
350
351
352
					/*
					if (bound >= 0) {
						edgeState = edgeState.onLoopExit(bb->id(), bound);
						if (edgeState.isBottom()) {
							continue;
Ballabriga Clément's avatar
Ballabriga Clément committed
353
						}
Ballabriga Clément's avatar
Ballabriga Clément committed
354
					}
355
					*/
Ballabriga Clément's avatar
Ballabriga Clément committed
356
				}
357
358
				edgeState.doFinalizeUpdate();
				ana.check(*e, edgeState);
clement's avatar
clement committed
359
			}
clement's avatar
init  
clement committed
360
		}
Ballabriga Clément's avatar
Ballabriga Clément committed
361
362
363
	}
}

Ballabriga Clément's avatar
ordre    
Ballabriga Clément committed
364

Ballabriga Clément's avatar
ok    
Ballabriga Clément committed
365
void PolyAnalysis::PseudoTopoOrder::_topoLoopHelper(const ai::CFGGraph &graph, Block *start, int currentLoop) {
Ballabriga Clément's avatar
ordre    
Ballabriga Clément committed
366
367
368
369
370
371
372
373
374
375
376
	for (ai::CFGGraph::Iterator it(graph); !it.ended(); it++) {
		Block *bb = (*it);
		if (LOOP_HEADER(bb)) {
			if (((currentLoop == -1) && (ENCLOSING_LOOP_HEADER(bb) == nullptr)) ||
				((currentLoop != -1) && (ENCLOSING_LOOP_HEADER(bb) != nullptr) && (ENCLOSING_LOOP_HEADER(bb)->index() == currentLoop))) {
				_topoLoopHelper(graph, bb, bb->index());
			}
		}
	}

	if (currentLoop != -1) {
Ballabriga Clément's avatar
ok    
Ballabriga Clément committed
377
		_loopOrder[currentLoop] = _current;
Ballabriga Clément's avatar
ordre    
Ballabriga Clément committed
378
379
380
381
		_current++;
	}
}

Ballabriga Clément's avatar
ok    
Ballabriga Clément committed
382
383
384
bool PolyAnalysis::PseudoTopoOrder::isBefore(const Block *b1, const Block *b2) const {
	if (_belongsToLoop.hasKey(b1->index()) && !_belongsToLoop.hasKey(b2->index()))
		return true;
Ballabriga Clément's avatar
ordre    
Ballabriga Clément committed
385

Ballabriga Clément's avatar
ok    
Ballabriga Clément committed
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
	if (!_belongsToLoop.hasKey(b1->index()) && _belongsToLoop.hasKey(b2->index()))
		return false;

	if (_belongsToLoop.hasKey(b1->index())) {
		int loopId = _belongsToLoop[b1->index()];

		if (_loopOrder[loopId] < _loopOrder[loopId]) 
			return true;

		if (_loopOrder[loopId] > _loopOrder[loopId]) 
			return false;
	}

	return (_blockOrder[b1->index()] < _blockOrder[b2->index()]);
}

void PolyAnalysis::PseudoTopoOrder::_topoNodeHelper(const ai::CFGGraph &graph, Block *end) {
Ballabriga Clément's avatar
ordre    
Ballabriga Clément committed
403
404
405
406
407
408
409
410
411
	if (_visited->bit(end->index()))
		return;

	for (ai::CFGGraph::Predecessor e(graph, end); e; e++) {
		if (!BACK_EDGE(e))
			_topoNodeHelper(graph, e->source());
	}

	if (LOOP_HEADER(end)) {
Ballabriga Clément's avatar
ok    
Ballabriga Clément committed
412
413
414
		_belongsToLoop[end->index()] = end->index();
	} else if (ENCLOSING_LOOP_HEADER(end) != nullptr)
		_belongsToLoop[end->index()] = ENCLOSING_LOOP_HEADER(end)->index();
Ballabriga Clément's avatar
ordre    
Ballabriga Clément committed
415

Ballabriga Clément's avatar
ok    
Ballabriga Clément committed
416
	_blockOrder[end->index()] = _current;
Ballabriga Clément's avatar
ordre    
Ballabriga Clément committed
417
418
419
420
	_current++;
	_visited->set(end->index());
}

Ballabriga Clément's avatar
ok    
Ballabriga Clément committed
421
void PolyAnalysis::PseudoTopoOrder::_getPseudoTopo(const ai::CFGGraph &graph) {
Ballabriga Clément's avatar
ordre    
Ballabriga Clément committed
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
	_visited = new BitVector(graph.count());

	_current = 0;
	_topoLoopHelper(graph, graph.entry(), -1);

	_current = 0;
	for (ai::CFGGraph::Iterator it(graph); !it.ended(); it++) {
		bool hasNonBackEdges = false;
		for (ai::CFGGraph::Successor e(graph, (*it)); !e.ended() && !hasNonBackEdges; e++) {
			if (!BACK_EDGE(e))
				hasNonBackEdges = true;
		}
		if (!hasNonBackEdges)
			_topoNodeHelper(graph, *it);
	}
	delete _visited;
	_visited = nullptr;
}

441
void PolyAnalysis::processCFG(CFG &cfg, state_t &s, MyHTable<int, PPLDomain> &lb, bool isEntryCFG, bool summarize){
Ballabriga Clément's avatar
suite    
Ballabriga Clément committed
442
	PPLManager *man = isEntryCFG ? (new PPLManager(*_props, workspace())) : (new PPLManager(s, *_props, workspace()));
443
444
445
446
	if (summarize) {
		ASSERT(isEntryCFG);
		man->enableSummary();
	}
Ballabriga Clément's avatar
ok    
Ballabriga Clément committed
447
	MyHTable<int, state_t> headerState;
Ballabriga Clément's avatar
Ballabriga Clément committed
448
449
	ai::CFGGraph graph(&cfg);
	ai::EdgeStore<PPLManager, ai::CFGGraph> store(*man, graph);
Ballabriga Clément's avatar
Ballabriga Clément committed
450

Ballabriga Clément's avatar
Ballabriga Clément committed
451
#ifdef POLY_DEBUG
452
	cout << "Init state: " << s << endl;
Ballabriga Clément's avatar
Ballabriga Clément committed
453
#endif
Ballabriga Clément's avatar
Ballabriga Clément committed
454
	cout << "Entering CFG: " << cfg.name() << endl;
Ballabriga Clément's avatar
ok    
Ballabriga Clément committed
455
	WorkListDriver<PPLManager, ai::CFGGraph, ai::EdgeStore<PPLManager, ai::CFGGraph>, PseudoTopoOrder> ana(*man, graph, store, _orders[cfg.index()]);
Ballabriga Clément's avatar
Ballabriga Clément committed
456
457

	while (ana) {
458
		processBB(man, graph, lb, ana, store, headerState);
clement's avatar
init  
clement committed
459
460
		ana++;
	}
Ballabriga Clément's avatar
Ballabriga Clément committed
461
462
463
464

	cout << "Exiting CFG: " << cfg.name() << endl;

	Block *bb = graph.exit();
clement's avatar
init  
clement committed
465
	Block::EdgeIter edge(bb->ins());
clement's avatar
clement committed
466
	s = store.get(edge);
Ballabriga Clément's avatar
Ballabriga Clément committed
467

468
#ifdef POLY_DEBUG
469
470
	cout << "FINAL STATE: " << endl;
	cout << s;
471
#endif
472
	if (isEntryCFG && !summarize) {
473
		// ...
474
    cout << endl << "---- ANALYSIS ENDS ----" << endl << endl;
475
476
	cout << "FINAL STATE: " << endl;
	cout << s;
477
478
479
	} else {
		s.doLeaveFunction();
		s.doFinalizeUpdate();
480
#ifdef POLY_DEBUG
481
482
		cout << "SUMMARY STATE: " << endl;
		cout << s;
483
#endif
clement's avatar
clement committed
484
	}
485

clement's avatar
clement committed
486
487
488
489
490
}

void PolyAnalysis::processWorkSpace(WorkSpace *ws) {
	const CFGCollection *coll = INVOLVED_CFGS(ws);
	ASSERT(coll);
491

Ballabriga Clément's avatar
ok    
Ballabriga Clément committed
492
	_orders.setLength(coll->count());
Ballabriga Clément's avatar
not bad    
Ballabriga Clément committed
493
	for (CFGCollection::Iter iter2(coll); iter2; iter2++) {
Ballabriga Clément's avatar
ordre    
Ballabriga Clément committed
494
495
		cout << "Preparing CFG: " << (*iter2)->name() << endl;
		ai::CFGGraph graph((*iter2));
Ballabriga Clément's avatar
ok    
Ballabriga Clément committed
496
497
		PseudoTopoOrder *pto = new PseudoTopoOrder(graph);
		_orders[(*iter2)->index()] = pto;
Ballabriga Clément's avatar
ordre    
Ballabriga Clément committed
498
499
	}

Ballabriga Clément's avatar
Ballabriga Clément committed
500
501

	CFG *entry = coll->get(0);
clement's avatar
clement committed
502
	state_t dummy;
503
	ASSERT(dummy.getSummary() == nullptr);
504
505
506
507
	SUMMARIZE(ws) = true;
	MyHTable<int, PPLDomain> bounds;
	MyHTable<int, int> static_bounds;
	processCFG(*entry, dummy, bounds, true /* is entry */, false /* summarize */);
508
	cout << "PARAMETRIC LOOP BOUNDS: " << endl;
509
	for (MyHTable<int, PPLDomain>::PairIterator it(bounds); it; it++) {
Ballabriga Clément's avatar
Ballabriga Clément committed
510
		cout << "linear bound expr for (" << (*it).fst << "): " << (*it).snd << endl;
511
512
513
514
515
516
517
518
519
520
521
522
		PPL::Coefficient binf_n, binf_d, bsup_n, bsup_d;
		Ident id((*it).fst, Ident::ID_LOOP);
		if (!(*it).snd.hasIdent(id)) {
			static_bounds[(*it).fst] = bound_t::UNREACHABLE;
			continue;
		}
	    (*it).snd.getRange(id, binf_n, binf_d, bsup_n, bsup_d);
		if (PPL::raw_value(bsup_d).get_ui() != 0) {
			static_bounds[(*it).fst] = 
				static_cast<bound_t>(PPL::raw_value(bsup_n).get_ui() / PPL::raw_value(bsup_d).get_ui());
		} else static_bounds[(*it).fst] = bound_t::UNBOUNDED;
	}
Ballabriga Clément's avatar
Ballabriga Clément committed
523

524
	cout << endl;
clement's avatar
init  
clement committed
525
	cout << "LOOP BOUNDS: " << endl;
Ballabriga Clément's avatar
not bad    
Ballabriga Clément committed
526
	for (CFGCollection::Iter iter2(coll); iter2; iter2++) {
clement's avatar
clement committed
527
		for (CFG::BlockIter iter((*iter2)->blocks()); iter; iter++) {
Ballabriga Clément's avatar
ok    
Ballabriga Clément committed
528
			Block *bb = (*iter);
clement's avatar
clement committed
529
			if (LOOP_HEADER(bb)) {
530
				MAX_ITERATION(bb) = static_bounds[bb->id()];
Ballabriga Clément's avatar
Ballabriga Clément committed
531
				cout << "[" << (*iter2)->name() << "]"
Ballabriga Clément's avatar
Ballabriga Clément committed
532
				     << "MAX_ITERATION(" << bb->id() << ") = " << MAX_ITERATION(bb) << endl;
533
				/*
Ballabriga Clément's avatar
Ballabriga Clément committed
534
535
				cout << "[" << (*iter2)->name() << "]"
				     << "TOTAL_ITERATION(" << bb->id() << ") = " << TOTAL_ITERATION(bb) << endl;
536
					 */
clement's avatar
clement committed
537
			}
clement's avatar
clement committed
538
		}
Ballabriga Clément's avatar
ok    
Ballabriga Clément committed
539
		delete _orders[(*iter2)->index()];
clement's avatar
init  
clement committed
540
	}
Ballabriga Clément's avatar
ok    
Ballabriga Clément committed
541
}
Ballabriga Clément's avatar
ordre    
Ballabriga Clément committed
542

Ballabriga Clément's avatar
Ballabriga Clément committed
543
544
} // namespace poly
} // namespace otawa