""" The Methods in this file appear on instructions. They attempt to refine an instruction, either by improving its type resolution or by eliminating it entirely. """ import types import util, typeset, knodes, values def refine_Instruction (self, refine): return None def refine_LoadParamInstruction (self, refine): tarval = self.get_first_value (self.TARGET) # If the value we load is not used, we can be removed. if not tarval: return (refine.ELIMINATE, self.FALLTHROUGH, ()) # Otherwise, check if we made any assumptions about the type of # this parameter idx = self.get_first_value (self.INDEX).get_value () passump = refine.jitted.get_param_assumptions () [idx] return _handle_loaded_knode (self, refine, tarval, passump) def refine_UnaryInstruction (self, refine): # Check for constant propagation input = self.get_named (self.INPUT)[0].get_value() if input.is_constant(): try: simres = self.simulate (input.get_value ()) simres = refine.comp.get_constant (simres) # If we were able to simulate this instruction, then we # can be removed and we can replace our output with the # result. output = self.get_first_value (self.OUTPUT) return (refine.ELIMINATE, self.FALLTHROUGH, ((output, simres),)) except util.PyntoException: pass pass return None def refine_BinaryInstruction (self, refine): indent = refine.log.indent ('Binary Instruction %s' % self) # Check for constant propagation left = self.get_named (self.LEFT)[0].get_value () right = self.get_named (self.RIGHT)[0].get_value () if left.is_constant() and right.is_constant(): try: simres = self.simulate (left.get_value(), right.get_value()) simres = refine.comp.get_constant (simres) # If we were able to simulate this instruction, then we # can be removed and we can replace our output with the # result. output = self.get_first_value (self.OUTPUT) return (refine.ELIMINATE, self.FALLTHROUGH, ((output, simres),)) except util.PyntoException: pass pass self.refine_types (refine) return def refine_types_BinaryCompareInstruction (self, refine): # You'd think that compares always yield booleans, but you'd be # wrong! I could do something sick like this: # # >>> class A: # ... def __lt__ (self, a): # ... return "hello" # ... # >>> a = A() # >>> a < 5 # 'hello' # # So we just say that if we are comparing built-in types, # then we know that the result will be boolean. left = self.get_first_value (self.LEFT) right = self.get_first_value (self.RIGHT) target = self.get_first_value (self.OUTPUT) lefttype = left.get_types().get_known_type().knode righttype = left.get_types().get_known_type().knode deftypes = refine.root.get_builtin_types () if lefttype in deftypes and righttype in deftypes: booltype = refine.root.get_builtin_type (types.BooleanType) refine.set_type_info (target, typeset.typeset_for_type (booltype)) pass return def refine_types_InplaceInstruction (self, refine): # TODO: specialize... return refine_types_BinaryArithmeticInstruction (self, refine) def refine_types_BinaryArithmeticInstruction (self, refine): # Check for type propagation left = self.get_first_value (self.LEFT) right = self.get_first_value (self.RIGHT) target = self.get_first_value (self.OUTPUT) lefttype = left.get_types().get_known_type().knode righttype = right.get_types().get_known_type().knode # if no useful information was available, give up if not lefttype or not righttype: return refine.log.mid ('left %s type = %s right %s type = %s' % (left, lefttype, right, righttype)) # The coersion rules are immensly complicated. # We'll implement some common ones here for now to prove the # concept. # If the right is a subclass of the left, then we try the left's # operators __op__ etc before switching to the right's operators. if righttype.is_subtype(lefttype): temp = lefttype lefttype = righttype righttype = temp pass inttype = refine.root.get_builtin_type (types.IntType) longtype = refine.root.get_builtin_type (types.LongType) floattype = refine.root.get_builtin_type (types.FloatType) if lefttype is inttype and righttype is inttype: refine.set_type_info (target, typeset.typeset_for_type (inttype)) pass elif lefttype in (inttype, longtype) and righttype in (inttype, longtype): refine.set_type_info (target, typeset.typeset_for_type (longtype)) pass elif lefttype in (inttype, longtype, floattype) and \ righttype in (inttype, longtype, floattype): refine.set_type_info (target, typeset.typeset_for_type (floattype)) pass return def refine_CallInstruction (self, refine): """ Looks for calls to known knodes and makes improvements to the IR based upon them. For example, calls to class constructors are converted to a BuildInstanceInstruction instruction. """ tar = self.get_first_value (self.TARGET) func = self.get_first_value (self.FUNC) # If this is a call of a constant value, it is almost certainly a # call to a knode. if func.is_constant(): functype = refine.root.get_builtin_type (types.FunctionType) classtype = refine.root.get_builtin_type (types.ClassType) # If this is a call of a class constructor, we want to convert the # current instruction to be a class constructor. if func.get_type() is classtype: assert isinstance (func.get_value(), knodes.ClassKNode) buildobj = refine.instrs.BuildInstanceInstruction () buildobj.set_named (buildobj.CLASS, func) # If there is no target, create one; otherwise, assign it to # the buildobj instruction if not tar: tar = values.TemporaryValue (buildobj) else: tar.set_instr (buildobj) # If there is target, then add it to the instruction and # set its type information to be an instance of the class # we're constructing. buildobj.add_named (buildobj.TARGET, tar) newtype = typeset.typeset_for_type (func.get_value()) refine.set_type_info (tar, newtype) # determine the init function; if we don't obtain a constant # ptr for some reason, just use a temp value... initnode = func.get_value().get_child ("__init__") initfunc = None if initnode: initfunc = initnode.node.get_value () if not initfunc: initfunc = values.TemporaryValue (buildobj) buildobj.add_named (buildobj.CONSTRUCTOR, initfunc) # Now we have to call the __init__ function; transfer the # arguments over to the init function, after adding the # implicit first argument. (Note that the BuildInstance # method does not return a closure) callinit = refine.instrs.CallInstruction () callinit.add_named (callinit.FUNC, initfunc) callinit.add_named (callinit.ARGS, tar) for arg in self.get_named (self.ARGS): callinit.add_named (callinit.ARGS, arg.get_value()) pass # If we ended up with a temporary for the __init__ function, # at least set some type info. if initfunc.is_temporary(): functype = refine.root.get_builtin_type (types.FunctionType) refine.set_type_info (initfunc, typeset.typeset_for_type (functype)) pass return (refine.REPLACE, (buildobj, callinit)) pass # Otherwise, check if this is a closure. If it is, we may be able # to eliminate the closure and substitute the implied arguments # directly. elif func.get_types().get_known_type().knode == \ refine.root.get_closure_type(): try: # The method get_closure() returns a value representing the # function being called and also a list of implied arguments, # or it raises an exception. truefunc, implied = func.get_instr().refine_closure(refine) # Set the function we're calling to the true function, # and add in any implied arguments in the front of the list of # arguments; unfortunately, we want to add them in reverse order. self.set_named (self.FUNC, truefunc) implied = list(implied) implied.reverse () # why must this be in place?? for imp in implied: self.insert_named (self.ARGS, imp) # Now add the WRITEr of the closure to the worklist because # that function may well be irrelevant refine.note_removed_use (func) return except util.PyntoException: pass pass pass def refine_PhiInstruction (self, refine): """ Looks for Phi isntructions of the form "a = phi (a*, b+)" where a and b are different values. If it finds one, replaces 'a' with 'b'. Also performs type propagation. """ tarval = self.get_first_value (self.TARGET) repval = None # If nobody wants to read the target of this instruction, just remove it if not tarval: return (refine.ELIMINATE, self.FALLTHROUGH, ()) #print "phiinstr %s: %s" % (self, tarval) for source in self.get_named (self.SOURCE): srcval = source.get_value () # Ignore uses of the target or the current repval (replacement value) if srcval is tarval: continue if srcval is repval: continue #print " source: %s" % srcval # If we haven't found a replacement value yet, use this one if not repval: repval = srcval # Otherwise we found two different values amongst the sources, # so give up. else: repval = None break pass if repval: return (refine.ELIMINATE, self.FALLTHROUGH, ((tarval, repval),)) # Otherwise, try to at least do some type propagation tset = typeset.TypeSet () # Merge the types of the various possibilities refine.log.mid ('merging types of various possibilities') for source in self.get_named (self.SOURCE): srcval = source.get_value () # Ignore the undefined value, it doesn't contribute to type # analysis if srcval.is_undefined(): continue type = srcval.get_types () # If the type of srcval has not yet been generated, ignore it. # When the type is generated, we'll be added back to the worklist. if not type.is_initialized(): refine.log.mid ('source value %s : not initialized, skipping' % srcval) continue # Add in the possibly types. Note that the add_hint() method # weeds out duplicates automatically. for hint in type.get_hints (): refine.log.mid ('source value %s : hint %s' % (srcval, hint)) # Ignore looped uncertainty: that is, if you have a = phi # (a, 1) then the fact that 'a' is uncertain is not # evidence that 'a' is uncertain, if you catch my drift! if srcval is tarval and not hint.knode: continue tset.add_hint (hint.relationship, hint.knode) pass pass refine.set_type_info (tarval, tset) return None def refine_JumpIfTrueInstruction (self, refine): test = self.get_named (self.TEST)[0].get_value() if test.is_constant(): if test.get_value(): return (refine.ELIMINATE, self.BRANCH, ()) return (refine.ELIMINATE, self.FALLTHROUGH, ()) return None def refine_JumpIfFalseInstruction (self, refine): test = self.get_named (self.TEST)[0].get_value() if test.is_constant(): if test.get_value(): return (refine.ELIMINATE, self.FALLTHROUGH, ()) return (refine.ELIMINATE, self.BRANCH, ()) return None def _handle_loaded_knode (self, refine, tarval, kedge): """ Helper for LoadGlobal and LoadAttribute; when we do a ktree lookup and end up with a knode, this helps us to set the data on the target, posibly by replacing the current instruction if the knode is a constant. """ # if we think this attribute/global will always map to a constant, # just embed the constant, but remember that we did so so if # this assumption turns out to be false we can throw away the # code based on it constval = kedge.node.get_value () if constval: refine.log.mid ("Found const value: " + str(constval)) refine.jitted.add_assumption (kedge) return (refine.ELIMINATE, self.FALLTHROUGH, ((tarval, constval),)) # Otherwise, see if we can scrape some type information out of this types = kedge.node.get_types () if types: refine.set_type_info (tarval, types) return # otherwise, ensure that we make no assumptions about our target refine.clear_type_info (tarval) return None def refine_LoadGlobalInstruction (self, refine): name = self.get_named (self.NAME)[0].get_value () dest = self.get_named (self.TARGET)[0].get_value () # If they're not loading a global with a constant name, # then we don't know nothin if not name.is_constant(): refine.clear_type_info (dest, None) return indent = refine.log.indent ("LoadGlobal with name %s" % name.get_value()) kmod = refine.module glob = kmod.get_child (name.get_value ()) if glob: refine.log.mid ("Found knode: " + str(glob.node)) return _handle_loaded_knode (self, refine, dest, glob) # Otherwise, make no assumptions about our dest refine.clear_type_info (dest) return def refine_LoadAttrInstruction (self, refine): ptrval = self.get_first_value (self.PTR) tarval = self.get_first_value (self.TARGET) # Get the name of the attribute we are fetching attrname = self.get_first_value (self.ATTRNAME).get_value () # If the pointer has a known type, we can lookup the attribute # on the ktree and see if anything turns up. ptrtype = ptrval.get_types().get_known_type() if ptrtype.knode: attr = ptrtype.knode.lookup (attrname) if attr: # If we found the attribute that is being loaded, then we # know that no custom getattr() method will be invoked. # This means that if no one cares about the result of this # instruction it can be removed. if not tarval: return (refine.ELIMINATE, self.FALLTHROUGH, ()) # if we know for certain this pointer is of the given type, # then we can take full advantage of the data we loaded if ptrtype.relationship == typeset.EXACT: return _handle_loaded_knode (self, refine, tarval, attr) # otherwise, we only want to take advantage of any type # information. Note that this raises an exception if such # information cannot be found. types = kedge.node.get_types () refine.set_type_info (tarval, types) return return return def refine_StoreAttrInstruction (self, refine): ptrval = self.get_first_value (self.PTR) srcval = self.get_first_value (self.SOURCE) attrname = self.get_first_value (self.ATTRNAME).get_value () srctypes = srcval.get_types() # If the pointer has a known type, we may be able to add to the ktree for ptrtype in ptrval.get_types().get_hints(): # ignore assigments to generic pointers that could be anything if not ptrtype.knode: continue # ignore assignments to instances of built-in types assert ptrtype.knode.is_class () if ptrtype.knode.is_builtin(): continue # otherwise, see if we have any instance attributes on record edge = ptrtype.knode.get_instance_attr (attrname) # if not, let's create an entry. We'll always create an InstanceKNode # for now, which means that we'll never add more than type hints. # Also, we'll mark the attribute as always having some level of # confusion if not edge: edge = knodes.KEdge \ (attrname, knodes.InstanceKNode (ptrtype.knode)) ptrtype.knode.add_instance_attr (edge) tset = edge.node.get_types() tset.set_unknown() else: tset = edge.node.get_types() pass tset.merge_in (srctypes) pass return # ---------------------------------------------------------------------- # refine_closure # # The refine_closure() method is set on those instructions which # generate a closure of one sort or another (LoadAttrInstruction, # MakeClosureInstruction). If possible, it returns two values: # # (truefunc, (implied*)) # # truefunc is some callable object that the closure wraps. Implied # are the set of implied arguments that were to be added to the front # of the argument list. In the case of a LoadAttrInstruction, for example, # this would be the self pointer. # # Note that truefunc could be another Closure, though it is generally a # FunctionKNode. def refine_closure_Instruction (self, refine): raise util.PyntoException ("Not implemented") def refine_closure_LoadAttrInstruction (self, refine): # If we are in this function, we must be generating a closure. The # only way we can do this is when the lookup on the class yielded # a function. This lets us assert than many of these routines # will not fail. ptrval = self.get_first_value (self.PTR) ptrtype = ptrval.get_types().get_known_type() assert ptrtype.knode # For now, we only accept EXACT relationships. Eventually, we # should be able to handle all relationships, but we have to be a # little clever there because we if the relationship is not exact # we can't pass back the true function, but instead still want to # load the attribute, only off of the class and without building a # closure. We'll need a new sort of instruction for that. if ptrtype.relationship != typeset.EXACT: raise util.PyntoException ("Not exact relationship") # Find the closure and santiy check that it's type is indeed a closure! tarval = self.get_first_value (self.TARGET) tarvaltype = tarval.get_types().get_known_type() assert tarval.get_types().get_known_type().knode is \ refine.root.get_closure_type() # Fetch the attribute from the class; we know we will find one and # it will be a function, because otherwise we wouldn't know for certain # we generating a closure attrname = self.get_first_value (self.ATTRNAME).get_value () attr = ptrtype.knode.get_child (attrname) assert attr and attr.node.is_function () refine.jitted.add_assumption (attr) truefunc = attr.node.get_value () assert truefunc return (truefunc, (ptrval,))