Fix for bug 1141: bad register from fld ST0, foo with a REX prefix.
[dyninst.git] / dyninstAPI / src / liveness.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 // $Id: liveness.C,v 1.12 2008/09/04 21:06:20 bill Exp $
33
34 #if defined(cap_liveness)
35
36 #include "debug.h"
37 #include "image-func.h"
38 #include "function.h"
39 #include "instPoint.h"
40 #include "registerSpace.h"
41 #include "debug.h"
42 #include "instructionAPI/h/InstructionDecoder.h"
43 #include "instructionAPI/h/Register.h"
44 #include "instructionAPI/h/Instruction.h"
45 #include "addressSpace.h"
46 using namespace Dyninst::InstructionAPI;
47 #include "symtab.h"
48
49 #if defined(arch_x86) || defined(arch_x86_64)
50 // Special-casing for IA-32...
51 #include "RegisterConversion-x86.h"
52 #include "inst-x86.h"
53 #endif
54
55 #include "Parsing.h"
56 using namespace Dyninst::ParseAPI;
57
58 ReadWriteInfo calcRWSets(Instruction::Ptr insn, image_basicBlock* blk, unsigned width, Address a);
59 InstructionCache image_basicBlock::cachedLivenessInfo = InstructionCache();
60
61   
62
63
64 // Code for register liveness detection
65
66 // Takes information from instPoint and resets
67 // regSpace liveness information accordingly
68 // Right now, all the registers are assumed to be live by default
69 void registerSpace::specializeSpace(const bitArray &liveRegs) {
70     // Liveness info is stored as a single bitarray for all registers.
71
72 #if defined(arch_x86) || defined(arch_x86_64) 
73     // We use "virtual" registers on the IA-32 platform (or AMD-64 in 
74     // 32-bit mode), and thus the registerSlot objects have _no_ relation
75     // to the liveRegs input set. We handle this as a special case, and
76     // look only for the flags representation (which is used to set
77     // the IA32_FLAG_VIRTUAL_REGISTER "register"
78     assert(liveRegs.size() == getBitArray().size());
79     if (addr_width == 4) {
80         for (unsigned i = 1; i <= NUM_VIRTUAL_REGISTERS; i++) {
81             registers_[i]->liveState = registerSlot::dead;
82         }
83         registers_[IA32_FLAG_VIRTUAL_REGISTER]->liveState = registerSlot::dead;
84         for (unsigned i = REGNUM_OF; i <= REGNUM_RF; i++) {
85             if (liveRegs[i]) {
86                 registers_[IA32_FLAG_VIRTUAL_REGISTER]->liveState = registerSlot::live;
87                 break;
88             }
89         }
90         // All we care about for now.
91         return;
92     }
93 #endif
94     assert(liveRegs.size() == getBitArray().size());
95     for (regDictIter i = registers_.begin(); i != registers_.end(); i++) {
96         if (liveRegs[i.currval()->number])
97             i.currval()->liveState = registerSlot::live;
98         else
99         {
100             i.currval()->liveState = registerSlot::dead;
101         }
102     }
103 #if defined(arch_x86_64)
104     // ???
105     registers_[REGNUM_RAX]->liveState = registerSlot::live;
106 #endif
107
108 }
109
110 const bitArray &image_basicBlock::getLivenessIn(image_func * context) {
111     // Calculate if it hasn't been done already
112     if (in.size() == 0)
113         summarizeBlockLivenessInfo(context);
114     return in;
115 }
116
117 const bitArray image_basicBlock::getLivenessOut(image_func * context) {
118     bitArray out(in.size());
119
120     // ignore call, return edges
121     Intraproc epred;
122
123     // OUT(X) = UNION(IN(Y)) for all successors Y of X
124     Block::edgelist & target_edges = targets();
125     Block::edgelist::iterator eit = target_edges.begin(&epred);
126    
127     for( ; eit != target_edges.end(); ++eit) { 
128         // covered by Intraproc predicate
129         //if ((*eit)->type() == CALL) continue;
130         // Is this correct?
131         if ((*eit)->type() == CATCH) continue;
132         
133         // TODO: multiple entry functions and you?
134        
135         out |= ((image_basicBlock*)(*eit)->trg())->getLivenessIn(context);
136     }
137     return out;
138 }
139
140 void image_basicBlock::summarizeBlockLivenessInfo(image_func *context) 
141 {
142    if(in.size())
143    {
144       return;
145    }
146
147    stats_codegen.startTimer(CODEGEN_LIVENESS_TIMER);
148
149    unsigned width = region()->getAddressWidth();
150
151    in = registerSpace::getBitArray();
152    def = in;
153    use = in;
154
155    liveness_printf("%s[%d]: Getting liveness summary for block starting at 0x%lx in %s\n",
156                    FILE__, __LINE__, firstInsnOffset(), context->img()->pathname().c_str());
157
158
159    using namespace Dyninst::InstructionAPI;
160    Address current = firstInsnOffset();
161    InstructionDecoder decoder(
162                        reinterpret_cast<const unsigned char*>(getPtrToInstruction(firstInsnOffset())),
163                        getSize(),
164                        obj()->cs()->getArch());
165    Instruction::Ptr curInsn = decoder.decode();
166    while(curInsn)
167    {
168      ReadWriteInfo curInsnRW;
169      liveness_printf("%s[%d] After instruction %s at address 0x%lx:\n",
170                      FILE__, __LINE__, curInsn->format().c_str(), current);
171      if(!cachedLivenessInfo.getLivenessInfo(current, context, curInsnRW))
172      {
173        curInsnRW = calcRWSets(curInsn, this, width, current);
174        cachedLivenessInfo.insertInstructionInfo(current, curInsnRW, context);
175      }
176
177      use |= (curInsnRW.read & ~def);
178      // And if written, then was defined
179      def |= curInsnRW.written;
180       
181      liveness_cerr << "Read    " << curInsnRW.read << endl;
182      liveness_cerr << "Written " << curInsnRW.written << endl;
183      liveness_cerr << "Used    " << use << endl;
184      liveness_cerr << "Defined " << def << endl;
185
186       current += curInsn->size();
187       curInsn = decoder.decode();
188    }
189      //liveness_printf("%s[%d] Liveness summary for block:\n", FILE__, __LINE__);
190      //liveness_cerr << in << endl << def << endl << use << endl;
191      //liveness_printf("%s[%d] --------------------\n---------------------\n", FILE__, __LINE__);
192
193    stats_codegen.stopTimer(CODEGEN_LIVENESS_TIMER);
194    return;
195 }
196
197 /* This is used to do fixed point iteration until 
198    the in and out don't change anymore */
199 bool image_basicBlock::updateBlockLivenessInfo(image_func * context) 
200 {
201   bool change = false;
202
203   stats_codegen.startTimer(CODEGEN_LIVENESS_TIMER);
204
205   // old_IN = IN(X)
206   bitArray oldIn = in;
207   // tmp is an accumulator
208   bitArray out = getLivenessOut(context);
209   
210   // Liveness is a reverse dataflow algorithm
211  
212   // OUT(X) = UNION(IN(Y)) for all successors Y of X
213
214   // IN(X) = USE(X) + (OUT(X) - DEF(X))
215   in = use | (out - def);
216   
217   // if (old_IN != IN(X)) then change = true
218   if (in != oldIn)
219       change = true;
220       
221   //liveness_printf("%s[%d] Step: block 0x%lx, hasChanged %d\n", FILE__, __LINE__, firstInsnOffset(), change);
222   //liveness_cerr << in << endl;
223
224   stats_codegen.stopTimer(CODEGEN_LIVENESS_TIMER);
225
226   return change;
227 }
228
229 // Calculate basic block summaries of liveness information
230 // TODO: move this to an image_func level. 
231
232 void image_func::calcBlockLevelLiveness() {
233     if (livenessCalculated_) return;
234
235     // Step 1: gather the block summaries
236     Function::blocklist::iterator sit = blocks().begin();
237     for( ; sit != blocks().end(); sit++) {
238         ((image_basicBlock*)(*sit))->summarizeBlockLivenessInfo(this);
239     }
240     
241     // We now have block-level summaries of gen/kill info
242     // within the block. Propagate this via standard fixpoint
243     // calculation
244     bool changed = true;
245     while (changed) {
246         changed = false;
247         for(sit = blocks().begin(); sit != blocks().end(); sit++) {
248             if (((image_basicBlock*)(*sit))->updateBlockLivenessInfo(this)) {
249                 changed = true;
250             }
251         }
252     }
253
254     livenessCalculated_ = true;
255 }
256
257 // This function does two things.
258 // First, it does a backwards iteration over instructions in its
259 // block to calculate its liveness.
260 // At the same time, we cache liveness (which was calculated) in
261 // any instPoints we cover. Since an iP only exists if the user
262 // asked for it, we take its existence to indicate that they'll
263 // also be instrumenting. 
264 void instPoint::calcLiveness() {
265    // Assume that the presence of information means we
266    // did this already.
267    if (postLiveRegisters_.size()) {
268       return;
269    }
270    // First, ensure that the block liveness is done.
271    func()->ifunc()->calcBlockLevelLiveness();
272
273    unsigned width = func()->ifunc()->img()->getObject()->getAddressWidth();
274
275    if (func()->ifunc()->instLevel() == HAS_BR_INDIR)
276    {
277      //Unresolved indirect jumps could go anywhere.  
278      //We'll be the most conservative possible in these cases, since
279      //we're missing control flow.
280      postLiveRegisters_ = (registerSpace::getRegisterSpace(width)->getAllRegs());
281      return;
282    }
283
284    // We know: 
285    //    liveness _out_ at the block level:
286    const bitArray &block_out = block()->llb()->getLivenessOut(func()->ifunc());
287
288    postLiveRegisters_ = block_out;
289
290    assert(postLiveRegisters_.size());
291
292    // We now want to do liveness analysis for straight-line code. 
293         
294    stats_codegen.startTimer(CODEGEN_LIVENESS_TIMER);
295    using namespace Dyninst::InstructionAPI;
296     
297    Address blockBegin = block()->origInstance()->firstInsnAddr();
298    Address blockEnd = block()->origInstance()->endAddr();
299    std::vector<Address> blockAddrs;
300    
301    const unsigned char* insnBuffer = 
302       reinterpret_cast<const unsigned char*>(block()->origInstance()->getPtrToInstruction(blockBegin));
303     
304    InstructionDecoder decoder(insnBuffer,block()->origInstance()->getSize(),
305         func()->ifunc()->isrc()->getArch());
306    Address curInsnAddr = blockBegin;
307    do
308    {
309      ReadWriteInfo rw;
310      if(!block()->llb()->cachedLivenessInfo.getLivenessInfo(curInsnAddr, func()->ifunc(), rw))
311      {
312        Instruction::Ptr tmp = decoder.decode(insnBuffer);
313        rw = calcRWSets(tmp, block()->llb(), width, curInsnAddr);
314        block()->llb()->cachedLivenessInfo.insertInstructionInfo(curInsnAddr, rw, func()->ifunc());
315      }
316      blockAddrs.push_back(curInsnAddr);
317      curInsnAddr += rw.insnSize;
318      insnBuffer += rw.insnSize;
319    } while(curInsnAddr < blockEnd);
320     
321     
322    // We iterate backwards over instructions in the block. 
323
324    std::vector<Address>::reverse_iterator current = blockAddrs.rbegin();
325
326    //liveness_printf("%s[%d] instPoint calcLiveness: %d, 0x%lx, 0x%lx\n", 
327    //                FILE__, __LINE__, current != blockAddrs.rend(), *current, addr());
328
329    while(current != blockAddrs.rend() && *current > addr())
330    {
331       // Cache it in the instPoint we just covered (if such exists)
332       instPoint *possiblePoint = func()->findInstPByAddr(*current);
333       if (possiblePoint) {
334          if (possiblePoint->postLiveRegisters_.size() == 0) {
335             possiblePoint->postLiveRegisters_ = postLiveRegisters_;
336          }
337       }
338       
339       ReadWriteInfo rwAtCurrent;
340       if(block()->llb()->cachedLivenessInfo.getLivenessInfo(*current, func()->ifunc(), rwAtCurrent))
341       {
342         liveness_printf("%s[%d] Calculating liveness for iP 0x%lx, insn at 0x%lx\n",
343                         FILE__, __LINE__, addr(), *current);
344         //liveness_cerr << "        " << "?XXXXXXXXMMMMMMMMRNDITCPAZSOF11111100DSBSBDCA" << endl;
345         //liveness_cerr << "        " << "?7654321076543210FTFFFFFFFFFP54321098IIPPXXXX" << endl;
346         liveness_cerr << "Pre:    " << postLiveRegisters_ << endl;
347         
348         postLiveRegisters_ &= (~rwAtCurrent.written);
349         postLiveRegisters_ |= rwAtCurrent.read;
350         liveness_cerr << "Post:   " << postLiveRegisters_ << endl;
351       
352         ++current;
353       }
354       else
355       {
356         Instruction::Ptr tmp = decoder.decode((const unsigned char*)(block()->origInstance()->getPtrToInstruction(*current)));
357         rwAtCurrent = calcRWSets(tmp, block()->llb(), width, *current);
358         assert(!"SERIOUS ERROR: read/write info cache state inconsistent");
359         liveness_printf("%s[%d] Calculating liveness for iP 0x%lx, insn at 0x%lx\n",
360                         FILE__, __LINE__, addr(), *current);
361         liveness_cerr << "Pre:  " << postLiveRegisters_ << endl;
362         
363         postLiveRegisters_ &= (~rwAtCurrent.written);
364         postLiveRegisters_ |= rwAtCurrent.read;
365         liveness_cerr << "Post: " << postLiveRegisters_ << endl;
366         
367         ++current;
368       }
369       
370    }
371    stats_codegen.stopTimer(CODEGEN_LIVENESS_TIMER);
372
373    assert(postLiveRegisters_.size());
374
375    return;
376 }
377
378
379 // It'd be nice to do the calcLiveness here, but it's defined as const...
380 bitArray instPoint::liveRegisters(callWhen when) {
381     // postLiveRegisters_ is our _output_ liveness. If the 
382     // instrumentation is pre-point, we need to update it with
383     // the effects of this instruction.
384
385     unsigned width = func()->ifunc()->img()->getObject()->getAddressWidth();
386
387     // Override: if we have an unparsed jump table in the _function_,
388     // return "everything could be live".
389     if (func()->ifunc()->instLevel() == HAS_BR_INDIR ||
390         func()->ifunc()->instLevel() == UNINSTRUMENTABLE) {
391         bitArray allOn(registerSpace::getBitArray().size());
392         allOn.set();
393         return allOn;
394     }
395         
396     calcLiveness();
397
398     if ((when == callPostInsn) ||
399         (when == callBranchTargetInsn)) {
400         return postLiveRegisters_;
401     }
402     assert(when == callPreInsn);
403
404     bitArray ret(postLiveRegisters_);
405
406     ReadWriteInfo curInsnRW;
407     if(!block()->llb()->cachedLivenessInfo.getLivenessInfo(addr(), func()->ifunc(), curInsnRW))
408     {
409       using namespace Dyninst::InstructionAPI;
410       const unsigned char* bufferToDecode =
411               reinterpret_cast<const unsigned char*>(proc()->getPtrToInstruction(addr()));
412       InstructionDecoder decoder(bufferToDecode, 
413             InstructionDecoder::maxInstructionLength,
414             func()->ifunc()->isrc()->getArch());
415       Instruction::Ptr currentInsn = decoder.decode(bufferToDecode);
416
417       curInsnRW = calcRWSets(currentInsn, block()->llb(), width, addr());
418
419     }
420     
421     ret &= (~curInsnRW.written);
422     ret |= curInsnRW.read;
423
424     liveness_printf("Liveness out for instruction at 0x%lx\n",
425                       addr());
426     //liveness_cerr << "        " << "?XXXXXXXXMMMMMMMMRNDITCPAZSOF11111100DSBSBDCA" << endl;
427     //liveness_cerr << "        " << "?7654321076543210FTFFFFFFFFFP54321098IIPPXXXX" << endl;
428     liveness_cerr << "Read    " << curInsnRW.read << endl;
429     liveness_cerr << "Written " << curInsnRW.written << endl;
430     liveness_cerr << "Live    " << ret << endl;
431
432     return ret;
433 }
434
435 #if defined(arch_power)
436 int convertRegID(int in)
437 {
438     if(in >= ppc32::r0 && in <= ppc32::r31)
439     {
440       return in - ppc32::r0 + registerSpace::r0;
441     }
442     else if(in >= ppc32::fpr0 && in <= ppc32::fpr31)
443     {
444         return in - ppc32::fpr0 + registerSpace::fpr0;
445     }
446 /*    else if(in >= ppc32::fsr0 && in <= ppc32::fsr31)
447     {
448         return in - ppc32::fsr0 + registerSpace::fsr0;
449     }
450     */    else if(in == ppc32::xer)
451     {
452         return registerSpace::xer;
453     }
454     else if(in == ppc32::lr)
455     {
456         return registerSpace::lr;
457     }
458     else if(in == ppc32::mq)
459     {
460         return registerSpace::mq;
461     }
462     else if(in == ppc32::ctr)
463     {
464         return registerSpace::ctr;
465     }
466     else if(in >= ppc32::cr0 && in <= ppc32::cr7)
467     {
468         return registerSpace::cr;
469     }
470     else
471     {
472         return registerSpace::ignored;
473     }
474 }
475
476 #endif
477
478 ReadWriteInfo calcRWSets(Instruction::Ptr curInsn, image_basicBlock* blk, unsigned int width,
479                         Address a)
480 {
481   ReadWriteInfo ret;
482   ret.read = registerSpace::getBitArray();
483   ret.written = registerSpace::getBitArray();
484   ret.insnSize = curInsn->size();
485   
486   std::set<RegisterAST::Ptr> cur_read, cur_written;
487   curInsn->getReadSet(cur_read);
488   curInsn->getWriteSet(cur_written);
489   //  liveness_printf("Read registers: \n");
490       
491   for (std::set<RegisterAST::Ptr>::const_iterator i = cur_read.begin(); 
492        i != cur_read.end(); i++) 
493   {
494     //liveness_printf("%s \n", (*i)->format().c_str());
495 #if defined(arch_x86) || defined(arch_x86_64)
496         bool unused;
497         Register converted = convertRegID(*i, unused);
498         if(converted != REGNUM_EFLAGS)
499         {
500             ret.read[converted] = true;
501         }
502         else
503         {
504             ret.read[REGNUM_OF] = true;
505             ret.read[REGNUM_CF] = true;
506             ret.read[REGNUM_PF] = true;
507             ret.read[REGNUM_AF] = true;
508             ret.read[REGNUM_ZF] = true;
509             ret.read[REGNUM_SF] = true;
510             ret.read[REGNUM_DF] = true;
511             ret.read[REGNUM_TF] = true;
512             ret.read[REGNUM_NT] = true;
513         }
514 #else
515     int id = convertRegID((*i)->getID());
516     if(id != registerSpace::ignored)
517     {
518         assert(id < registerSpace::lastReg && id >= registerSpace::r0);
519         ret.read[id] = true;
520     }
521 #endif
522   }
523   //liveness_printf("Written registers: \n");
524       
525   for (std::set<RegisterAST::Ptr>::const_iterator i = cur_written.begin(); 
526        i != cur_written.end(); i++) {
527     //liveness_printf("%s \n", (*i)->format().c_str());
528 #if defined(arch_x86) || defined(arch_x86_64)
529     bool treatAsRead = false;
530     Register r = convertRegID(*i, treatAsRead);
531     if(r != REGNUM_EFLAGS)
532     {
533         ret.written[r] = true;
534         if(treatAsRead) ret.read[r] = true;
535     }
536     else
537     {
538         ret.written[REGNUM_OF] = true;
539         ret.written[REGNUM_CF] = true;
540         ret.written[REGNUM_PF] = true;
541         ret.written[REGNUM_AF] = true;
542         ret.written[REGNUM_ZF] = true;
543         ret.written[REGNUM_SF] = true;
544         ret.written[REGNUM_DF] = true;
545         ret.written[REGNUM_TF] = true;
546         ret.written[REGNUM_NT] = true;
547     }
548         
549 #else
550     
551     int id = convertRegID((*i)->getID());
552     
553     if(id != registerSpace::ignored)
554     {
555         assert(id < registerSpace::lastReg && id >= registerSpace::r0);
556         ret.written[id] = true;
557     }
558 #endif
559   }
560   InsnCategory category = curInsn->getCategory();
561   switch(category)
562   {
563   case c_CallInsn:
564       // Call instructions not at the end of a block are thunks, which are not ABI-compliant.
565       // So make conservative assumptions about what they may read (ABI) but don't assume they write anything.
566       ret.read |= (registerSpace::getRegisterSpace(width)->getCallReadRegisters());
567       if(blk->end() == a)
568       {
569           ret.written |= (registerSpace::getRegisterSpace(width)->getCallWrittenRegisters());
570       }
571     break;
572   case c_ReturnInsn:
573     ret.read |= (registerSpace::getRegisterSpace(width)->getReturnReadRegisters());
574     // Nothing written implicitly by a return
575     break;
576   case c_BranchInsn:
577     if(!curInsn->allowsFallThrough() && blk->isExitBlock())
578     {
579       //Tail call, union of call and return
580       ret.read |= ((registerSpace::getRegisterSpace(width)->getCallReadRegisters()) |
581                    (registerSpace::getRegisterSpace(width)->getReturnReadRegisters()));
582       ret.written |= (registerSpace::getRegisterSpace(width)->getCallWrittenRegisters());
583     }
584     break;
585   default:
586     {
587       bool isInterrupt = false;
588       bool isSyscall = false;
589
590
591       if ((curInsn->getOperation().getID() == e_int) ||
592           (curInsn->getOperation().getID() == e_int3)) {
593         isInterrupt = true;
594       }
595       static RegisterAST::Ptr gs(new RegisterAST(x86::gs));
596       if (((curInsn->getOperation().getID() == e_call) &&
597            /*(curInsn()->getOperation().isRead(gs))) ||*/
598            (curInsn->getOperand(0).format() == "16")) ||
599           (curInsn->getOperation().getID() == e_syscall) || 
600           (curInsn->getOperation().getID() == e_int) || 
601           (curInsn->getOperation().getID() == power_op_sc)) {
602         isSyscall = true;
603       }
604
605       if (curInsn->getOperation().getID() == power_op_svcs) {
606         isSyscall = true;
607       }
608
609       if (isInterrupt || isSyscall) {
610         ret.read |= (registerSpace::getRegisterSpace(width)->getSyscallReadRegisters());
611         ret.written |= (registerSpace::getRegisterSpace(width)->getSyscallWrittenRegisters());
612       }
613     }
614     break;
615   }
616   
617   return ret;
618 }
619
620 #endif // cap_liveness