Update copyright to LGPL on all files
[dyninst.git] / dyninstAPI / src / BPatch_basicBlock.C
1 /*
2  * Copyright (c) 1996-2009 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as "Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * By your use of Paradyn, you understand and agree that we (or any
12  * other person or entity with proprietary rights in Paradyn) are
13  * under no obligation to provide either maintenance services,
14  * update services, notices of latent defects, or correction of
15  * defects for Paradyn.
16  * 
17  * This library is free software; you can redistribute it and/or
18  * modify it under the terms of the GNU Lesser General Public
19  * License as published by the Free Software Foundation; either
20  * version 2.1 of the License, or (at your option) any later version.
21  * 
22  * This library is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
25  * Lesser General Public License for more details.
26  * 
27  * You should have received a copy of the GNU Lesser General Public
28  * License along with this library; if not, write to the Free Software
29  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
30  */
31
32 #define BPATCH_FILE
33
34 #include <stdio.h>
35 #include <iostream>
36 #include "util.h"
37 #include "common/h/Types.h"
38
39 #include "BPatch_flowGraph.h"
40 #include "BPatch_collections.h"
41 #include "BPatch_basicBlock.h"
42 #include "process.h"
43 #include "function.h"
44 #if !defined(cap_instruction_api)
45 #include "InstrucIter.h"
46 #endif
47 #include "BPatch_instruction.h"
48 #include "Instruction.h"
49 #include "InstructionDecoder.h"
50 #include "BPatch_libInfo.h"
51 #include "BPatch_edge.h"
52
53 int bpatch_basicBlock_count = 0;
54
55 BPatch_basicBlock::BPatch_basicBlock(int_basicBlock *ib, BPatch_flowGraph *fg):
56    iblock(ib),
57    flowGraph(fg),
58    immediateDominates(NULL),
59    immediateDominator(NULL),
60    immediatePostDominates(NULL),
61    immediatePostDominator(NULL),
62    sourceBlocks(NULL),
63    instructions(NULL)
64 {
65
66 #if defined(ROUGH_MEMORY_PROFILE)
67     bpatch_basicBlock_count++;
68     if ((bpatch_basicBlock_count % 10) == 0)
69         fprintf(stderr, "bpatch_basicBlock_count: %d (%d)\n",
70                 bpatch_basicBlock_count, bpatch_basicBlock_count*sizeof(BPatch_basicBlock));
71 #endif
72
73    ib->setHighLevelBlock(this);
74 }
75
76 //destructor of the class BPatch_basicBlock
77 void BPatch_basicBlock::BPatch_basicBlock_dtor(){
78         if (immediatePostDominates)
79                 delete immediatePostDominates;
80         if (immediateDominates)
81                 delete immediateDominates;
82         if (sourceBlocks)
83                 delete sourceBlocks;
84         if (instructions)
85                 delete instructions;
86
87         BPatch_Set<BPatch_edge *>::iterator eIter;
88         eIter = incomingEdges.begin();
89         while (eIter != incomingEdges.end()) {
90             delete (*eIter);
91             eIter++;
92         }
93         eIter = outgoingEdges.begin();
94         while (eIter != outgoingEdges.end()) {
95             delete (*eIter);
96             eIter++;
97         }
98         return;
99 }
100
101 //returns the predecessors of the basic block in aset 
102 void BPatch_basicBlock::getSourcesInt(BPatch_Vector<BPatch_basicBlock*>& srcs){
103    BPatch_basicBlock *b;
104    pdvector<int_basicBlock *> in_blocks;
105    unsigned i;
106
107    iblock->getSources(in_blocks);
108    for (i=0; i<in_blocks.size(); i++)
109    {
110       b = (BPatch_basicBlock *) in_blocks[i]->getHighLevelBlock();
111       if (b) srcs.push_back(b);
112    }
113 }
114
115 //returns the successors of the basic block in a set 
116 void BPatch_basicBlock::getTargetsInt(BPatch_Vector<BPatch_basicBlock*>& tgrts){
117    BPatch_basicBlock *b;
118    pdvector<int_basicBlock *> out_blocks;
119    unsigned i;
120
121    iblock->getTargets(out_blocks);
122    for (i=0; i<out_blocks.size(); i++)
123    {
124       b = (BPatch_basicBlock *) out_blocks[i]->getHighLevelBlock();
125       if (b) tgrts.push_back(b);
126    }
127 }
128
129 //returns the dominates of the basic block in a set 
130 void BPatch_basicBlock::getImmediateDominatesInt(BPatch_Vector<BPatch_basicBlock*>& imds){
131         flowGraph->fillDominatorInfo();
132
133         if(!immediateDominates)
134                 return;
135         BPatch_basicBlock** elements = 
136                 new BPatch_basicBlock*[immediateDominates->size()];
137         immediateDominates->elements(elements);
138         for(unsigned i=0;i<immediateDominates->size();i++)
139                 imds.push_back(elements[i]);
140         delete[] elements;
141         return;
142 }
143
144
145 void BPatch_basicBlock::getImmediatePostDominatesInt(BPatch_Vector<BPatch_basicBlock*>& imds){
146         flowGraph->fillPostDominatorInfo();
147
148         if(!immediatePostDominates)
149                 return;
150         BPatch_basicBlock** elements = 
151                 new BPatch_basicBlock*[immediatePostDominates->size()];
152         immediatePostDominates->elements(elements);
153         for(unsigned i=0;i<immediatePostDominates->size();i++)
154                 imds.push_back(elements[i]);
155         delete[] elements;
156         return;
157 }
158
159 //returns the dominates of the basic block in a set 
160 void
161 BPatch_basicBlock::getAllDominatesInt(BPatch_Set<BPatch_basicBlock*>& buffer){
162         flowGraph->fillDominatorInfo();
163
164         buffer += (BPatch_basicBlock*)this;
165         if(immediateDominates){
166                 BPatch_basicBlock** elements = 
167                         new BPatch_basicBlock*[immediateDominates->size()];
168                 immediateDominates->elements(elements);
169                 for(unsigned i=0;i<immediateDominates->size();i++)
170                         elements[i]->getAllDominates(buffer);
171                 delete[] elements;
172         }
173         return;
174 }
175
176 void
177 BPatch_basicBlock::getAllPostDominatesInt(BPatch_Set<BPatch_basicBlock*>& buffer){
178         flowGraph->fillPostDominatorInfo();
179
180         buffer += (BPatch_basicBlock*)this;
181         if(immediatePostDominates){
182                 BPatch_basicBlock** elements = 
183                         new BPatch_basicBlock*[immediatePostDominates->size()];
184                 immediatePostDominates->elements(elements);
185                 for(unsigned i=0;i<immediatePostDominates->size();i++)
186                         elements[i]->getAllPostDominates(buffer);
187                 delete[] elements;
188         }
189         return;
190 }
191
192 //returns the immediate dominator of the basic block
193 BPatch_basicBlock* BPatch_basicBlock::getImmediateDominatorInt(){
194         flowGraph->fillDominatorInfo();
195
196         return immediateDominator;
197 }
198
199 BPatch_basicBlock* BPatch_basicBlock::getImmediatePostDominatorInt(){
200         flowGraph->fillPostDominatorInfo();
201
202         return immediatePostDominator;
203 }
204
205 //returns whether this basic block dominates the argument
206 bool BPatch_basicBlock::dominatesInt(BPatch_basicBlock* bb){
207         if(!bb)
208                 return false;
209
210         if(bb == this)
211                 return true;
212
213         flowGraph->fillDominatorInfo();
214         
215         if(!immediateDominates)
216                 return false;
217
218         bool done = false;
219         BPatch_basicBlock** elements = 
220                 new BPatch_basicBlock*[immediateDominates->size()];
221         immediateDominates->elements(elements);
222         for(unsigned i=0;!done && (i<immediateDominates->size());i++)
223                 done = done || elements[i]->dominates(bb);
224         delete[] elements;
225         return done;
226 }
227
228 bool BPatch_basicBlock::postdominatesInt(BPatch_basicBlock* bb){
229         if(!bb)
230                 return false;
231
232         if(bb == this)
233                 return true;
234
235         flowGraph->fillPostDominatorInfo();
236
237         if(!immediatePostDominates)
238                 return false;
239
240         bool done = false;
241         BPatch_basicBlock** elements = 
242                 new BPatch_basicBlock*[immediatePostDominates->size()];
243         immediatePostDominates->elements(elements);
244         for(unsigned i=0;!done && (i<immediatePostDominates->size());i++)
245                 done = done || elements[i]->postdominates(bb);
246         delete[] elements;
247         return done;
248 }
249
250 //returns the source block corresponding to the basic block
251 //which is created looking at the machine code.
252 bool
253 BPatch_basicBlock::getSourceBlocksInt(BPatch_Vector<BPatch_sourceBlock*>& sBlocks)
254 {
255     if(!sourceBlocks)
256         flowGraph->createSourceBlocks();
257     
258     if(!sourceBlocks)
259         return false;
260     
261     for(unsigned int i=0;i<sourceBlocks->size();i++)
262         sBlocks.push_back((*sourceBlocks)[i]);
263
264     return true;
265 }
266
267 //returns the block number of the basic block
268 int BPatch_basicBlock::getBlockNumberInt() {
269         return iblock->id();
270 }
271
272 // returns the range of addresses of the code for the basic block
273 bool BPatch_basicBlock::getAddressRangeInt(void*& _startAddress,
274                                            void*& _lastInsnAddress)
275 {
276         _startAddress = (void *) getStartAddress();
277         _lastInsnAddress = (void *) getLastInsnAddress();
278    return true;
279 }
280
281 #ifdef IBM_BPATCH_COMPAT
282 bool BPatch_basicBlock::getLineNumbersInt(unsigned int &_startLine,
283                                           unsigned int  &_endLine)
284 {
285   BPatch_Vector<BPatch_sourceBlock *> sbvec;
286   getSourceBlocks(sbvec);
287   if (!sbvec.size()) return false;
288
289   unsigned int temp_start = UINT_MAX, temp_end = 0;
290   _startLine = UINT_MAX;
291   _endLine = 0;
292
293   //  Loop through all source blocks and accumulate the smallest start line
294   //  and the largest end line.  (is there a better way? -- don't we know this a priori?)
295   for (unsigned int i = 0; i < sbvec.size(); ++i) {
296     sbvec[i]->getLineNumbers(temp_start, temp_end);
297     if (temp_start < _startLine) _startLine = temp_start;
298     if (temp_end > _endLine) _endLine = temp_end;
299   }
300   return true;
301 }
302 #endif
303
304 ostream& operator<<(ostream& os,BPatch_basicBlock& bb)
305 {
306    unsigned i;
307         os << "^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n";
308         os << "Basic Block : " << bb.blockNo() <<" : [ ";
309         os << ostream::hex << bb.getStartAddress() << " , ";
310         os << ostream::hex << bb.getLastInsnAddress() << " | ";
311         os << ostream::dec << bb.getEndAddress() - bb.getStartAddress() << " ]\n";
312
313         if(bb.isEntryBlock())
314                 os <<"Type : ENTRY TO CFG\n"; 
315         else if(bb.isExitBlock())
316                 os <<"Type : EXIT FROM CFG\n"; 
317
318         cout << "Pred :\n";
319    BPatch_Vector<BPatch_basicBlock *> elements;
320    bb.getSources(elements);
321    for (i=0; i<elements.size(); i++)
322                 os << "\t<- " << elements[i]->blockNo() << "\n";
323
324         cout << "Succ:\n";
325    elements.clear();
326    bb.getTargets(elements);
327    for (i=0; i<elements.size(); i++)
328                 os << "\t-> " << elements[i]->blockNo() << "\n";
329
330    BPatch_basicBlock **belements;
331         os << "Immediate Dominates: ";
332         if(bb.immediateDominates){
333                 belements = new BPatch_basicBlock*[bb.immediateDominates->size()];
334                 bb.immediateDominates->elements(belements);
335                 for(i=0; i<bb.immediateDominates->size(); i++)
336                         os << belements[i]->blockNo() << " ";
337                 delete[] belements;
338         }
339         os << "\n";
340
341         os << "Immediate Dominator: ";
342         if(!bb.immediateDominator)
343                 os << "None\n";
344         else
345                 os << bb.immediateDominator->blockNo() << "\n";
346
347         os << "\n";
348         os << "^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n";
349         return os;
350 }
351
352 /*
353  * BPatch_basicBlock::findPoint (based on VG 09/05/01)
354  *
355  * Returns a vector of the instrumentation points from a basic block that is
356  * identified by the parameters, or returns NULL upon failure.
357  * (Points are sorted by address in the vector returned.)
358  *
359  * ops          The points within the basic block to return. A set of op codes
360  *              defined in BPatch_opCode (BPatch_point.h)
361  */
362 #if defined(cap_instruction_api)
363 using namespace Dyninst::InstructionAPI;
364 bool isLoad(Instruction::Ptr i)
365 {
366     return i->readsMemory();
367
368 bool isStore(Instruction::Ptr i)
369 {
370     return i->writesMemory();
371 }
372 bool isPrefetch(Instruction::Ptr i)
373 {
374     return i->getCategory() == c_PrefetchInsn;
375 }
376
377 struct funcPtrPredicate : public insnPredicate
378 {
379     result_type(*m_func)(argument_type);
380     funcPtrPredicate(result_type(*func)(argument_type)) :
381             m_func(func) {}
382     result_type operator()(argument_type arg) {
383         return m_func(arg);
384     }
385 };
386
387 struct findInsns : public insnPredicate
388 {
389     findInsns(const BPatch_Set<BPatch_opCode>& ops)
390     : findLoads(false), findStores(false), findPrefetch(false)
391     {
392         BPatch_opCode* opa = new BPatch_opCode[ops.size()];
393         ops.elements(opa);
394     
395     
396         for(unsigned int i=0; i<ops.size(); ++i) {
397             switch(opa[i]) {
398                 case BPatch_opLoad: findLoads = true; break;
399                 case BPatch_opStore: findStores = true; break;
400                 case BPatch_opPrefetch: findPrefetch = true; break;
401             }
402         }
403         delete[] opa;
404     }
405     result_type operator()(argument_type i)
406     {
407         //static int counter = 0;
408         if(findLoads && isLoad(i))
409         {
410             //counter++;
411             //fprintf(stderr, "Instruction #%d %s is a load\n", counter, i->format().c_str());
412             return true;
413         }
414         if(findStores && isStore(i))
415         {
416             //counter++;
417             //fprintf(stderr, "Instruction #%d %s is a store\n", counter, i->format().c_str());
418           return true;
419         }
420         if(findPrefetch && isPrefetch(i))
421         {
422             //counter++;
423             //fprintf(stderr, "Instruction #%d %s is a prefetch\n", counter, i->format().c_str());
424             return true;
425         }
426         //      fprintf(stderr, "Instruction %s failed filter\n", i->format().c_str());
427         return false;
428     }
429     bool findLoads;
430     bool findStores;
431     bool findPrefetch;
432 };
433 #endif
434         
435 BPatch_point* BPatch_basicBlock::findEntryPointInt()
436 {
437     return BPatch_point::createInstructionInstPoint(flowGraph->getAddSpace(), (void*)this->getStartAddressInt(),
438         flowGraph->getBFunction());
439 }
440
441 BPatch_point* BPatch_basicBlock::findExitPointInt()
442 {
443     return BPatch_point::createInstructionInstPoint(flowGraph->getAddSpace(), (void*)this->getEndAddressInt(),
444             flowGraph->getBFunction());
445 }
446         
447 BPatch_Vector<BPatch_point*>*
448     BPatch_basicBlock::findPointByPredicate(insnPredicate& f)
449 {
450     BPatch_Vector<BPatch_point*>* ret = new BPatch_Vector<BPatch_point*>;
451     std::vector<std::pair<Dyninst::InstructionAPI::Instruction::Ptr, Address> > insns;
452     getInstructions(insns);
453     for(std::vector<std::pair<Dyninst::InstructionAPI::Instruction::Ptr, Address> >::iterator curInsn = insns.begin();
454         curInsn != insns.end();
455         ++curInsn)
456     {
457 //        fprintf(stderr, "Checking insn at 0x%lx...", curInsn->second);
458         if(f(curInsn->first))
459         {
460             BPatch_point* tmp = BPatch_point::createInstructionInstPoint(flowGraph->getAddSpace(), (void*) curInsn->second,
461                     flowGraph->getBFunction());
462             if(!tmp)
463             {
464 #if defined(cap_instruction_api)
465                 fprintf(stderr, "WARNING: failed to create instpoint for load/store/prefetch %s at 0x%lx\n",
466                     curInsn->first->format().c_str(), curInsn->second);
467 #endif //defined(cap_instruction_api)
468             }
469             else
470             {
471                 ret->push_back(tmp);
472             }
473         }
474     }
475     return ret;
476     
477 }
478         
479 BPatch_Vector<BPatch_point*> *BPatch_basicBlock::findPointInt(const BPatch_Set<BPatch_opCode>& ops) 
480 {
481
482     // function is generally uninstrumentable (with current technology)
483     if (!flowGraph->getBFunction()->func->isInstrumentable())
484         return NULL;
485     
486 #if defined(cap_instruction_api)
487     findInsns filter(ops);
488     return findPointByPredicate(filter);
489 #else
490     // Use an instruction iterator
491     InstrucIter ii(this);
492     BPatch_function *func = flowGraph->getBFunction();
493     
494     return BPatch_point::getPoints(ops, ii, func);
495 #endif
496 }
497
498 #if defined(cap_instruction_api)
499 BPatch_Vector<BPatch_point*> *BPatch_basicBlock::findPointInt(bool(*filter)(Instruction::Ptr))
500 {
501
502     funcPtrPredicate filterPtr(filter);
503     return findPointByPredicate(filterPtr);
504 }
505 #endif
506
507 /*
508  * BPatch_basicBlock::getInstructions
509  *
510  * Returns a vector of the instructions contained within this block
511  *
512  */
513 #if defined(cap_instruction_api)
514 BPatch_Vector<BPatch_instruction*> *BPatch_basicBlock::getInstructionsInt(void) {
515   return NULL;
516   
517 }
518
519 #else
520 BPatch_Vector<BPatch_instruction*> *BPatch_basicBlock::getInstructionsInt(void) {
521
522   if (!instructions) {
523
524     instructions = new BPatch_Vector<BPatch_instruction*>;
525     InstrucIter ii(this);
526     
527     while(ii.hasMore()) {
528       BPatch_instruction *instr = ii.getBPInstruction();
529       instr->parent = this;
530       instructions->push_back(instr);
531       ii++;
532     }
533   }
534
535   return instructions;
536 }
537 #endif
538
539 /*
540  * BPatch_basicBlock::getInstructions
541  *
542  * Returns a vector of the instructions contained within this block
543  *
544  */
545 #if defined(cap_instruction_api)
546 bool BPatch_basicBlock::getInstructionsInt(std::vector<InstructionAPI::Instruction::Ptr>& insns) {
547   using namespace InstructionAPI;
548
549   InstructionDecoder d((const unsigned char*)(iblock->proc()->getPtrToInstruction(getStartAddress())), size());
550   d.setMode(iblock->proc()->getAddressWidth() == 8);
551   do {
552       insns.push_back(d.decode());
553   } while (insns.back() && insns.back()->isValid());
554
555   // Remove final invalid instruction
556   if (!insns.empty()) insns.pop_back();
557
558   return !insns.empty();  
559 }
560
561 bool BPatch_basicBlock::getInstructionsAddrs(std::vector<std::pair<InstructionAPI::Instruction::Ptr, Address> >& insnInstances) {
562   using namespace InstructionAPI;
563   Address addr = getStartAddress();
564   const unsigned char *ptr = (const unsigned char *)iblock->proc()->getPtrToInstruction(addr);
565   if (ptr == NULL) return false;
566   InstructionDecoder d(ptr, size());
567   d.setMode(iblock->proc()->getAddressWidth() == 8);
568
569   while (addr < getEndAddress()) {
570       insnInstances.push_back(std::make_pair(d.decode(), addr));
571       addr += insnInstances.back().first->size();
572   }
573
574   return !insnInstances.empty();  
575 }
576 #else
577 bool BPatch_basicBlock::getInstructionsInt(std::vector<InstructionAPI::Instruction::Ptr>& insns)
578 {
579   return false;
580 }
581
582 bool BPatch_basicBlock::getInstructionsAddrs(std::vector<std::pair<InstructionAPI::Instruction::Ptr, Address> >& insnInstances)
583 {
584   return false;
585 }
586 #endif // defined(cap_instruction_api)
587
588 unsigned long BPatch_basicBlock::getStartAddressInt() CONST_EXPORT 
589 {
590    return iblock->origInstance()->firstInsnAddr();
591 }
592
593 unsigned long BPatch_basicBlock::getLastInsnAddressInt() CONST_EXPORT 
594 {
595    return iblock->origInstance()->lastInsnAddr();
596 }
597
598 unsigned long BPatch_basicBlock::getEndAddressInt() CONST_EXPORT
599 {
600    return iblock->origInstance()->endAddr();
601 }
602
603 unsigned BPatch_basicBlock::sizeInt() CONST_EXPORT
604 {
605    return getEndAddress() - getStartAddress();
606 }
607
608 void BPatch_basicBlock::getIncomingEdgesInt(BPatch_Vector<BPatch_edge*>& inc)
609 {
610     BPatch_Set<BPatch_edge*>::iterator incIter = incomingEdges.begin();
611     while (incIter != incomingEdges.end()) {
612         inc.push_back(*incIter);
613         incIter++;
614     }
615 }
616         
617 void BPatch_basicBlock::getOutgoingEdgesInt(BPatch_Vector<BPatch_edge*>& out)
618 {
619     BPatch_Set<BPatch_edge*>::iterator outIter = outgoingEdges.begin();
620     while (outIter != outgoingEdges.end()) {
621         out.push_back(*outIter);
622         outIter++;
623     }
624 }
625
626 int BPatch_basicBlock::blockNo() const
627
628    return iblock->id();
629 }
630
631 bool BPatch_basicBlock::isEntryBlockInt() CONST_EXPORT {
632    return iblock->isEntryBlock();
633 }
634
635 bool BPatch_basicBlock::isExitBlockInt() CONST_EXPORT {
636    return iblock->isExitBlock();
637 }